Re: [PATCH v2 3/3] Optimize route dependency solver.

[Stefano Brivio <sbrivio@redhat.com>]

On Tue,  8 Sep 2026 18:13:14 +0000
Martin Schitter <ms+git@mur.at> wrote:

> Avoid retransmitting routes that explicitly got reported as already
> existing.

Oops. I feel a bit dumb now.

> Never make more resolution attempts than there are still unresolved
> dependency errors.
> 
> In the context of my current mesh network with ~700 route entries
> these changes reduce the required processing time from 5.5s to 15ms.

Ouch. Nice.

> ---
>  netlink.c | 26 +++++++++++++++++++-------
>  1 file changed, 19 insertions(+), 7 deletions(-)
> 
> diff --git a/netlink.c b/netlink.c
> index 65cc5d7..0e1c82a 100644
> --- a/netlink.c
> +++ b/netlink.c
> @@ -703,13 +703,12 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  
>  	/* Routes might have dependencies between each other, and the kernel
>  	 * processes RTM_NEWROUTE messages sequentially. For n routes, we might
> -	 * need to send the requests up to n times to get all of them inserted.
> -	 * Routes that have been already inserted will return -EEXIST, but we
> -	 * can safely ignore that and repeat the requests. This avoids the need
> -	 * to calculate dependencies: let the kernel do that.
> +	 * need to send the requests up to n times in the worst case to get all
> +	 * of them inserted.
>  	 */
>  	clock_gettime(CLOCK_MONOTONIC, &start);
> -	for (i = 0; i < dup_routes; i++) {
> +	for (i = dup_routes; i > 0; i--) {
> +	    unsigned int dep_errors = 0;
>  		for (nh = (struct nlmsghdr *)buf, left = nlmsgs_size;
>  		     NLMSG_OK(nh, left);
>  		     nh = NLMSG_NEXT(nh, left)) {
> @@ -722,10 +721,23 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  			rc = nl_do(s_dst, nh, RTM_NEWROUTE,
>  				   (flags & ~NLM_F_DUMP_FILTERED) | NLM_F_CREATE,
>  				   nh->nlmsg_len);
> -			if (rc < 0 && rc != -EEXIST &&
> -			    rc != -ENETUNREACH && rc != -EHOSTUNREACH)
> +
> +			if ( rc == -EEXIST) {

Coding style: if (rc == -EEXIST) {

> +			    /* Exclude existing routes from further retry attempts */
> +			    nh->nlmsg_type = NLMSG_NOOP;
> +			    continue;
> +			}
> +			if ( rc == -ENETUNREACH || rc == -EHOSTUNREACH){

Coding style:

			if (rc == -ENETUNREACH || rc == -EHOSTUNREACH) {

> +			    dep_errors++;
> +			    continue;
> +			}
> +			if (rc < 0)
>  				return rc;
>  		}
> +		debug("route dependency errors: %d", dep_errors);

See my comments to debug() calls in 1/3.

> +		/* Avoid having much more resolution attempts than
> +		 * there are still unresolved dependency errors */
> +		i = MIN(i, dep_errors++);

It took me a while to understand how you do this, and I'm mostly
convinced it's correct, but I'm also convinced this is equivalent to a
much simpler implementation: stop when we get no errors at all for the
whole bunch.

That is, using dep_errors:

	for (i = 0; i < dup_routes; i++) {

		[...]

		if (!dep_errors) /* All inserted, done */
			break;
	}

...right?

>  	}
>  	clock_gettime(CLOCK_MONOTONIC, &now);
>  	debug("route dependency handling time: %f s",

-- 
Stefano