[PATCH v2] Fix for Bug #221 -- Issue concerning bigger routing tables

[PATCH v2] Fix for Bug #221 -- Issue concerning bigger routing tables

[Martin Schitter]

v2 includes some additional small changes/fixes.

[PATCH v2 1/3] Fix handling of netlink multipart route dumps.
[PATCH v2 2/3] Timekeeping: Resolving Route Dependencies
[PATCH v2 3/3] Optimize route dependency solver.

[PATCH v2 1/3] Fix handling of netlink multipart route dumps.

[Martin Schitter]

This patch adds a `nl_collect` function to store all datagram
chunks of a multipart route dump in one single interim buffer
for further processing and dependency resolution.
---
 netlink.c | 79 +++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 56 insertions(+), 23 deletions(-)

diff --git a/netlink.c b/netlink.c
index 225b666..650a6fd 100644
--- a/netlink.c
+++ b/netlink.c
@@ -229,6 +229,51 @@ static struct nlmsghdr *nl_next(int s, char *buf, struct nlmsghdr *nh, ssize_t *
 		/* NOLINTNEXTLINE(readability-inconsistent-ifelse-braces) */\
 		} else
 
+/**
+ * nl_collect() - Collect all respose Datagrams of a netlink multi part dump
+ * @s:      Netlink socket
+ * @buf:    Buffer for responses (at least NLBUFSIZ long)
+ * @buflen: Buffer size.
+ * @seq:    Sequence number of request we're getting responses for
+ *
+ * Return: Length of collected responses in bytes or error code < 0
+ */
+int nl_collect(int s, char *buf, size_t buflen, uint32_t seq)
+{
+    size_t collected = 0;
+    struct nlmsghdr *nh;
+    ssize_t n;
+    int res;
+    const struct nlmsghdr* tail;
+
+    #define NLMSG_DONE_SIZE NLMSG_LENGTH(4)
+
+    while(collected + NLBUFSIZ < buflen){
+        nh = nl_next(s, &buf[collected], NULL, &n);
+        debug("collect: add chunk of size n=%ld at offset=%ld, seq=%d nlmsg_len=%d",
+            n, collected, seq, ((const struct nlmsghdr *)&buf[collected])->nlmsg_len);
+        res = nl_status(nh, n, seq);
+        if (res < 0) /* error */
+            return res;
+        collected += n;
+
+        /* look for NLMSG_DONE -- it's ussualy transmitted in a seperate datagram,
+         * but in some rare cases also placed at the end of a multipart chunk.*/
+        tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];
+        if (res == 0 || (
+            collected >= NLMSG_DONE_SIZE
+            && (tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE])
+            && NLMSG_OK(tail, NLMSG_DONE_SIZE)
+            && (nl_status(tail, NLMSG_DONE_SIZE, seq) == 0))
+        ) {
+            debug("collected: %ld", collected);
+            return collected;
+        }
+    }
+    err("netlink: Too many routes to duplicate");
+    return -E2BIG;
+}
+
 /**
  * nl_do() - Send netlink "do" request, and wait for acknowledgement
  * @s:		Netlink socket
@@ -553,21 +598,21 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
 		.rta.rta_len	  = RTA_LENGTH(sizeof(unsigned int)),
 		.ifi		  = ifi_src,
 	};
-	ssize_t nlmsgs_size, left, status;
+	ssize_t nlmsgs_size, left, status = 0;
 	unsigned dup_routes = 0;
 	struct nlmsghdr *nh;
-	char buf[NLBUFSIZ];
+	char buf[NLBUFSIZ * 8];
 	uint32_t seq;
 	unsigned i;
 
 	seq = nl_send(s_src, &req, RTM_GETROUTE, NLM_F_DUMP, sizeof(req));
 
-	/* nl_foreach() will step through multiple response datagrams,
-	 * which we don't want here because we need to have all the
-	 * routes in the buffer at once.
-	 */
-	nh = nl_next(s_src, buf, NULL, &nlmsgs_size);
-	for (left = nlmsgs_size;
+	/* collect all the chunks of a multi part dump in one buffer.*/
+	nlmsgs_size = nl_collect(s_src, buf, sizeof(buf), seq);
+	if (nlmsgs_size < 0)
+	    return nlmsgs_size;
+
+	for (nh = (struct nlmsghdr *)buf, left = nlmsgs_size;
 	     NLMSG_OK(nh, left) && (status = nl_status(nh, left, seq)) > 0;
 	     nh = NLMSG_NEXT(nh, left)) {
 		struct rtmsg *rtm = (struct rtmsg *)NLMSG_DATA(nh);
@@ -648,24 +693,12 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
 			dup_routes++;
 	}
 
-	if (!NLMSG_OK(nh, left)) {
-		/* Process any remaining datagrams in a different
-		 * buffer so we don't overwrite the first one.
-		 */
-		char tail[NLBUFSIZ];
-		unsigned extra = 0;
-
-		nl_foreach_oftype(nh, status, s_src, tail, seq, RTM_NEWROUTE)
-			extra++;
-
-		if (extra) {
-			err("netlink: Too many routes to duplicate");
-			return -E2BIG;
-		}
-	}
+	/* status should be 0 (=NLMSG_DONE) */
 	if (status < 0)
 		return status;
 
+	debug("found %d routes in dump", dup_routes);
+
 	/* 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.
-- 
2.53.0

Re: [PATCH v2 1/3] Fix handling of netlink multipart route dumps.

[Stefano Brivio]

Here's my review, sorry for the delay.

I have mostly coding style remarks on this patch, and more substantial
comments in the following patches.

Conceptually, though, this patch entirely makes sense to me.

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

> This patch adds a `nl_collect` function to store all datagram
> chunks of a multipart route dump in one single interim buffer
> for further processing and dependency resolution.

Here, and in following patches: missing Signed-off-by: tag (see
CONTRIBUTING.md).

> ---
>  netlink.c | 79 +++++++++++++++++++++++++++++++++++++++----------------
>  1 file changed, 56 insertions(+), 23 deletions(-)
> 
> diff --git a/netlink.c b/netlink.c
> index 225b666..650a6fd 100644
> --- a/netlink.c
> +++ b/netlink.c
> @@ -229,6 +229,51 @@ static struct nlmsghdr *nl_next(int s, char *buf, struct nlmsghdr *nh, ssize_t *
>  		/* NOLINTNEXTLINE(readability-inconsistent-ifelse-braces) */\
>  		} else
>  
> +/**
> + * nl_collect() - Collect all respose Datagrams of a netlink multi part dump

Nits: 'response', 'datagrams'.

> + * @s:      Netlink socket
> + * @buf:    Buffer for responses (at least NLBUFSIZ long)
> + * @buflen: Buffer size.

"Buffer size"

> + * @seq:    Sequence number of request we're getting responses for
> + *
> + * Return: Length of collected responses in bytes or error code < 0

Exceedingly minor, but for consistency (I strongly believe in boring
code and comments): "length", ", negative error code" (see e.g.
nl_do()).

> + */
> +int nl_collect(int s, char *buf, size_t buflen, uint32_t seq)

Cppcheck (try 'make cppcheck') says:

netlink.c:242:5: style: The function 'nl_collect' should have static linkage since it is not used outside of its translation unit. [staticFunction]
int nl_collect(int s, char *buf, size_t buflen, uint32_t seq)
    ^

> +{
> +    size_t collected = 0;

Coding style: we use tabs, see CONTRIBUTING.md. It's essentially the
same coding style as the Linux kernel with the "netdev" variants.

> +    struct nlmsghdr *nh;

Cppcheck reports that:

netlink.c:245:22: style: The scope of the variable 'nh' can be reduced. [variableScope]
    struct nlmsghdr *nh;
                     ^

and also:

netlink.c:245:22: style: Variable 'nh' can be declared as pointer to const [constVariablePointer]
    struct nlmsghdr *nh;
                     ^

> +    ssize_t n;
> +    int res;
> +    const struct nlmsghdr* tail;

...and we also align variable declarations from the longest to the
shortest (see references in CONTRIBUTING.md).

Coding style: "struct nlmsghdr *tail".

Same here for these two:

netlink.c:247:9: style: The scope of the variable 'res' can be reduced. [variableScope]
    int res;
        ^
netlink.c:248:28: style: The scope of the variable 'tail' can be reduced. [variableScope]
    const struct nlmsghdr* tail;
                           ^

> +
> +    #define NLMSG_DONE_SIZE NLMSG_LENGTH(4)

It's just a header with no data, right? Shouldn't it be 0? Am I missing
something?

By the way we tend to group all the defines that are generally valid
for a compilation unit towards the beginning of the relevant file (so
that they can be used in all the functions), see #define directives
earlier in netlink.c.

Exceptions are macros that are only relevant or valid for a given
function (see e.g. tap6_handler() in tap.c).

> +
> +    while(collected + NLBUFSIZ < buflen){

Coding style: space before {.

It's not really idiomatic to "do something as long as we have space"
and, with this structure, we won't stop on errors or mismatching
sequence numbers (see nl_status()).

Would there be a way to encode this as a loop on nl_status() perhaps? I
haven't tried but it would look cleaner and less bug-prone.

> +        nh = nl_next(s, &buf[collected], NULL, &n);
> +        debug("collect: add chunk of size n=%ld at offset=%ld, seq=%d nlmsg_len=%d",
> +            n, collected, seq, ((const struct nlmsghdr *)&buf[collected])->nlmsg_len);

At some point, we should get a netlink monitor (see
https://bugs.passt.top/show_bug.cgi?id=141) which might run this function
quite frequently at runtime, and having this as debug() message would
risk flooding debug logs and making them otherwise unusable.

We have rate-limited versions of logging functions, but they wouldn't
help debugging this function specifically, because once rate-limiting
kicks in, the messages might become entirely useless.

I think we could consider trace(). My preference would actually to drop
this altogether because it seems to be specific to some particular
phase of your development and not something of general relevance.

If we want to keep this for some reason: "collect" isn't very
descriptive (mind that it will just be printed among other messages
coming from completely different parts of the code). I would rather use
__func__.

> +        res = nl_status(nh, n, seq);
> +        if (res < 0) /* error */
> +            return res;

Looping on nl_status() directly would get rid of this.

> +        collected += n;
> +
> +        /* look for NLMSG_DONE -- it's ussualy transmitted in a seperate datagram,

usually, separate

> +         * but in some rare cases also placed at the end of a multipart chunk.*/

	* [...] chunk.
	*/

> +        tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];

Cppcheck and clang-tidy (try also 'make clang-tidy') aren't
particularly impressed here. Cppcheck says:

netlink.c:266:22: style: Variable 'tail' is reassigned a value before the old one has been used. [redundantAssignment]
            && (tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE])
                     ^
netlink.c:263:14: note: tail is assigned
        tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];
             ^
netlink.c:266:22: note: tail is overwritten
            && (tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE])
                     ^

and clang-tidy, more clearly, states:

/home/sbrivio/passt/netlink.c:263:9: error: Value stored to 'tail' is never read [clang-analyzer-deadcode.DeadStores,-warnings-as-errors]
  263 |         tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];
      |         ^      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/sbrivio/passt/netlink.c:263:9: note: Value stored to 'tail' is never read
  263 |         tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];
      |         ^      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

> +        if (res == 0 || (
> +            collected >= NLMSG_DONE_SIZE
> +            && (tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE])
> +            && NLMSG_OK(tail, NLMSG_DONE_SIZE)
> +            && (nl_status(tail, NLMSG_DONE_SIZE, seq) == 0))

For readability: could we perhaps split this into different 'if'
conditions with gotos dealing with specific errors (for example if
!NLMSG_OK(tail, NLMSG_DONE_SIZE), we should report error and return
early I guess)?

> +        ) {
> +            debug("collected: %ld", collected);

Same comments as the debug() call above.

> +            return collected;
> +        }
> +    }
> +    err("netlink: Too many routes to duplicate");
> +    return -E2BIG;
> +}
> +
>  /**
>   * nl_do() - Send netlink "do" request, and wait for acknowledgement
>   * @s:		Netlink socket
> @@ -553,21 +598,21 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  		.rta.rta_len	  = RTA_LENGTH(sizeof(unsigned int)),
>  		.ifi		  = ifi_src,
>  	};
> -	ssize_t nlmsgs_size, left, status;
> +	ssize_t nlmsgs_size, left, status = 0;
>  	unsigned dup_routes = 0;
>  	struct nlmsghdr *nh;
> -	char buf[NLBUFSIZ];
> +	char buf[NLBUFSIZ * 8];

Reasonable, but perhaps it should be a #define just after #define
NLBUFSIZ.

If a change in a variable declaration changes its length (as
displayed), you should move it so that we keep the "reverse pyramid"
look.

>  	uint32_t seq;
>  	unsigned i;
>  
>  	seq = nl_send(s_src, &req, RTM_GETROUTE, NLM_F_DUMP, sizeof(req));
>  
> -	/* nl_foreach() will step through multiple response datagrams,
> -	 * which we don't want here because we need to have all the
> -	 * routes in the buffer at once.
> -	 */
> -	nh = nl_next(s_src, buf, NULL, &nlmsgs_size);
> -	for (left = nlmsgs_size;
> +	/* collect all the chunks of a multi part dump in one buffer.*/

/* Collect [...] buffer */

> +	nlmsgs_size = nl_collect(s_src, buf, sizeof(buf), seq);
> +	if (nlmsgs_size < 0)
> +	    return nlmsgs_size;
> +
> +	for (nh = (struct nlmsghdr *)buf, left = nlmsgs_size;
>  	     NLMSG_OK(nh, left) && (status = nl_status(nh, left, seq)) > 0;
>  	     nh = NLMSG_NEXT(nh, left)) {
>  		struct rtmsg *rtm = (struct rtmsg *)NLMSG_DATA(nh);
> @@ -648,24 +693,12 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  			dup_routes++;
>  	}
>  
> -	if (!NLMSG_OK(nh, left)) {
> -		/* Process any remaining datagrams in a different
> -		 * buffer so we don't overwrite the first one.
> -		 */
> -		char tail[NLBUFSIZ];
> -		unsigned extra = 0;
> -
> -		nl_foreach_oftype(nh, status, s_src, tail, seq, RTM_NEWROUTE)
> -			extra++;
> -
> -		if (extra) {
> -			err("netlink: Too many routes to duplicate");
> -			return -E2BIG;
> -		}
> -	}
> +	/* status should be 0 (=NLMSG_DONE) */

This comment is redundant: if status is not 0, then clearly we hit some
kind of issue.

>  	if (status < 0)
>  		return status;
>  
> +	debug("found %d routes in dump", dup_routes);

Same comments as debug() calls above.

> +
>  	/* 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.

-- 
Stefano

Re: [PATCH v2 1/3] Fix handling of netlink multipart route dumps.

[Martin Schitter]

On 9/17/26 21:08, Stefano Brivio wrote:
> Here's my review, sorry for the delay.

Thanks for your really extensive review!

I'll try to respect and solve most of your remarks in my next patch series.

In the meanwhile I also did a lot of additional recherche. At the end of 
this replay you'll see, that I'll simply have to rewrite everything 
again because this new insights.

> I have mostly coding style remarks on this patch, and more substantial
> comments in the following patches.

Please don't hesitate to modify and improve all these suggested patches 
anytime. It's often more efficient to simply correct little style issues 
and docstring flaws on the fly in a well configured development 
environment than communicating all needed changes.

Even in cases where I don't share your view, simply change it to your needs.

> Here, and in following patches: missing Signed-off-by: tag (see
> CONTRIBUTING.md).

o.k. I'll add it -- although I'm not convinced that it makes much sense 
in a modern jj based patch description workflow.


>> +    #define NLMSG_DONE_SIZE NLMSG_LENGTH(4)
> 
> It's just a header with no data, right? Shouldn't it be 0? Am I missing
> something?

4 is correct -- it stands for header size + 4*8bit (int) error code

(see: 
https://docs.kernel.org/userspace-api/netlink/intro.html#netlink-message-types)

> By the way we tend to group all the defines that are generally valid
> for a compilation unit towards the beginning of the relevant file (so
> that they can be used in all the functions), see #define directives
> earlier in netlink.c.
> 
> Exceptions are macros that are only relevant or valid for a given
> function (see e.g. tap6_handler() in tap.c).

I wouldn't move it. It is a helpful hint to easily grasp this particular 
code section and isn't very useful outside this scope.

>> +
>> +    while(collected + NLBUFSIZ < buflen){
> 
> Coding style: space before {.
> 
> It's not really idiomatic to "do something as long as we have space"
> and, with this structure, we won't stop on errors or mismatching
> sequence numbers (see nl_status()).
> 
> Would there be a way to encode this as a loop on nl_status() perhaps? I
> haven't tried but it would look cleaner and less bug-prone.

Hmm -- I'm also not very happy about this solution, but for much less 
cosmetic reasons.

I simply don't like this arbitrary set hard-coded memory resp. route 
entry capacity limit that doesn't correspond to any limitation given by 
the operating system.

Well -- it's at least an improvement, but it doesn't solve the 
fundamental issue as long as it doesn't handle routing tables of any size.

But within the given constraints of this code base (i.e. strict avoiding 
any dynamic memory allocation and not using a more memory save 
programming language) I don't see any better solution until now.

>> +        nh = nl_next(s, &buf[collected], NULL, &n);
>> +        debug("collect: add chunk of size n=%ld at offset=%ld, seq=%d nlmsg_len=%d",
>> +            n, collected, seq, ((const struct nlmsghdr *)&buf[collected])->nlmsg_len);
> 
> At some point, we should get a netlink monitor (see
> https://bugs.passt.top/show_bug.cgi?id=141) which might run this function
> quite frequently at runtime, and having this as debug() message would
> risk flooding debug logs and making them otherwise unusable.

You can eliminate all my debug print commands just as you like.

But as long as we do not have suitable unit tests to control at least a 
subset of common cases in advance, debug logs could be very helpful to 
iron out remaining mistakes and false assumptions.

btw.: I don't think you should run this kind of routines frequently. 
Kernel-userspace-transfers are rather expensive. Perhaps you could try 
to utilize eBPF to handle these route table duplication resp. transfer 
between namespaces in a more efficient manner.

> I think we could consider trace(). My preference would actually to drop
> this altogether because it seems to be specific to some particular
> phase of your development and not something of general relevance.

That's o.k. for me.

But please consider, that we do not have much control about many details 
of the actual kernel behavior in respect to this complex netlink 
multipart dumps. It can be rather challenging to reproduce and solve all 
related issues without useful debug log capabilities.

> If we want to keep this for some reason: "collect" isn't very
> descriptive (mind that it will just be printed among other messages
> coming from completely different parts of the code). I would rather use
> __func__.

__func__ and similar more precise code location prefixes would IMHO make 
the output even more dense, confusing, and cluttering.

But again: just change it however you like!

>> +        res = nl_status(nh, n, seq);
>> +        if (res < 0) /* error */
>> +            return res;
> 
> Looping on nl_status() directly would get rid of this.

Respecting the capacity limits of the given interim buffer is IMHO the 
most important aspect of this function. That's why I have chosen this 
particular loop design.

Nevertheless, we have to catch a few other less critical error 
conditions resp. return conditions as well.

>> +        tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE];
> 
> Cppcheck and clang-tidy (try also 'make clang-tidy') aren't
> particularly impressed here. Cppcheck says:
> 
> netlink.c:266:22: style: Variable 'tail' is reassigned a value before the old one has been used. [redundantAssignment]

Yes -- this line is indeed wrong.
I'll replace it by a simple declaration for '*tail'.

>> +        if (res == 0 || (
>> +            collected >= NLMSG_DONE_SIZE
>> +            && (tail = (const struct nlmsghdr*)&buf[collected - NLMSG_DONE_SIZE])
>> +            && NLMSG_OK(tail, NLMSG_DONE_SIZE)
>> +            && (nl_status(tail, NLMSG_DONE_SIZE, seq) == 0))
> 
> For readability: could we perhaps split this into different 'if'
> conditions with gotos dealing with specific errors (for example if
> !NLMSG_OK(tail, NLMSG_DONE_SIZE), we should report error and return
> early I guess)?

It's a rather simple logical chain of tests to look out for NLMSG_DONE 
at the end of an input chunk if not already found in the previous 
nl_status() call. In both cases it will stop collecting datagrams.
Additionally, it would catch an illegal pointer arithmetic condition, 
although this case should never happen in practice.


>> -	char buf[NLBUFSIZ];
>> +	char buf[NLBUFSIZ * 8];
> 
> Reasonable, but perhaps it should be a #define just after #define
> NLBUFSIZ.

o.k. -- I'll use a macro (NLBUFBLOCKS) for the buffsize multiplier.

[PATCH v2 2/3] Timekeeping: Resolving Route Dependencies

[Martin Schitter]

---
 netlink.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/netlink.c b/netlink.c
index 650a6fd..65cc5d7 100644
--- a/netlink.c
+++ b/netlink.c
@@ -18,6 +18,7 @@
 #include <errno.h>
 #include <sys/types.h>
 #include <limits.h>
+#include <time.h>
 #include <unistd.h>
 #include <signal.h>
 #include <stdlib.h>
@@ -604,6 +605,7 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
 	char buf[NLBUFSIZ * 8];
 	uint32_t seq;
 	unsigned i;
+	struct timespec start, now;
 
 	seq = nl_send(s_src, &req, RTM_GETROUTE, NLM_F_DUMP, sizeof(req));
 
@@ -706,6 +708,7 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
 	 * can safely ignore that and repeat the requests. This avoids the need
 	 * to calculate dependencies: let the kernel do that.
 	 */
+	clock_gettime(CLOCK_MONOTONIC, &start);
 	for (i = 0; i < dup_routes; i++) {
 		for (nh = (struct nlmsghdr *)buf, left = nlmsgs_size;
 		     NLMSG_OK(nh, left);
@@ -724,6 +727,9 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
 				return rc;
 		}
 	}
+	clock_gettime(CLOCK_MONOTONIC, &now);
+	debug("route dependency handling time: %f s",
+	    (now.tv_sec - start.tv_sec) + (now.tv_nsec - start.tv_nsec)/1.0e9);
 
 	return 0;
 }
-- 
2.53.0

Re: [PATCH v2 2/3] Timekeeping: Resolving Route Dependencies

[Stefano Brivio]

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

> ---
>  netlink.c | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/netlink.c b/netlink.c
> index 650a6fd..65cc5d7 100644
> --- a/netlink.c
> +++ b/netlink.c
> @@ -18,6 +18,7 @@
>  #include <errno.h>
>  #include <sys/types.h>
>  #include <limits.h>
> +#include <time.h>
>  #include <unistd.h>
>  #include <signal.h>
>  #include <stdlib.h>
> @@ -604,6 +605,7 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  	char buf[NLBUFSIZ * 8];
>  	uint32_t seq;
>  	unsigned i;
> +	struct timespec start, now;
>  
>  	seq = nl_send(s_src, &req, RTM_GETROUTE, NLM_F_DUMP, sizeof(req));
>  
> @@ -706,6 +708,7 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  	 * can safely ignore that and repeat the requests. This avoids the need
>  	 * to calculate dependencies: let the kernel do that.
>  	 */
> +	clock_gettime(CLOCK_MONOTONIC, &start);

This adds overhead (even if minimal) in a general case, but it's only
used for debug() messages.

>  	for (i = 0; i < dup_routes; i++) {
>  		for (nh = (struct nlmsghdr *)buf, left = nlmsgs_size;
>  		     NLMSG_OK(nh, left);
> @@ -724,6 +727,9 @@ int nl_route_dup(int s_src, unsigned int ifi_src,
>  				return rc;
>  		}
>  	}
> +	clock_gettime(CLOCK_MONOTONIC, &now);
> +	debug("route dependency handling time: %f s",
> +	    (now.tv_sec - start.tv_sec) + (now.tv_nsec - start.tv_nsec)/1.0e9);

And anyway, I'm not sure I see the value of this. Which other functions
should we profile? Does it help at all to do this once you're done
developing it?

I would suggest to simply drop this patch. I understand you needed that
for development but you already explain in the commit message for 3/3
how it improves thing, and that's all the documentation we possibly
need for the future, I think.

>  
>  	return 0;
>  }

-- 
Stefano

Re: [PATCH v2 2/3] Timekeeping: Resolving Route Dependencies

[Martin Schitter]

On 9/17/26 21:08, Stefano Brivio wrote:
>> +	clock_gettime(CLOCK_MONOTONIC, &now);
>> +	debug("route dependency handling time: %f s",
>> +	    (now.tv_sec - start.tv_sec) + (now.tv_nsec - start.tv_nsec)/1.0e9);
> 
> And anyway, I'm not sure I see the value of this. Which other functions
> should we profile? Does it help at all to do this once you're done
> developing it?
> 
> I would suggest to simply drop this patch. I understand you needed that
> for development but you already explain in the commit message for 3/3
> how it improves thing, and that's all the documentation we possibly
> need for the future, I think.

For this reason I placed these profiling related changes in a separate 
patch. They can be easily ignored.

Nevertheless, it's still very important to optimize and profile the 
actual handling of huge routing tables. The original implementation was 
really horrible in this regard.

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

[Martin Schitter]

Avoid retransmitting routes that explicitly got reported as already
existing.

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.
---
 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) {
+			    /* Exclude existing routes from further retry attempts */
+			    nh->nlmsg_type = NLMSG_NOOP;
+			    continue;
+			}
+			if ( rc == -ENETUNREACH || rc == -EHOSTUNREACH){
+			    dep_errors++;
+			    continue;
+			}
+			if (rc < 0)
 				return rc;
 		}
+		debug("route dependency errors: %d", dep_errors);
+		/* Avoid having much more resolution attempts than
+		 * there are still unresolved dependency errors */
+		i = MIN(i, dep_errors++);
 	}
 	clock_gettime(CLOCK_MONOTONIC, &now);
 	debug("route dependency handling time: %f s",
-- 
2.53.0

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

[Stefano Brivio]

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

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

[Martin Schitter]

On 9/17/26 21:08, Stefano Brivio wrote:
>> 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.

After searching for answers, how these ENETUNREACH and EHOSTUNREACH in 
the dependency solver routines are actually caused, I finally looked 
into the iproute2 code for the save and restore commands:

https://github.com/iproute2/iproute2/blob/e6471d772f3e15a813e6c9a81b4b7adcfad22899/ip/iproute.c#L2314

Now I finally see that this task can be handled without all this stupid 
trial-and-error play and doesn't require a limit of route entries if we 
just reassemble the routing tables in three successive steps resp. loops:

/* Restore routes in correct order:
  * 0. ones for local addresses,
  * 1. ones for local networks,
  * 2. others (remote networks/hosts).
  */

That's a much nicer and more efficient solution than all our previous 
attempts.

So I'll have to rewrite the whole thing again...

It will take a few days.

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

[Stefano Brivio]

On Sat, 19 Sep 2026 14:56:56 +0200
Martin Schitter <ms+git@mur.at> wrote:

> On 9/17/26 21:08, Stefano Brivio wrote:
> >> 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.  
> 
> After searching for answers, how these ENETUNREACH and EHOSTUNREACH in 
> the dependency solver routines are actually caused, I finally looked 
> into the iproute2 code for the save and restore commands:
> 
> https://github.com/iproute2/iproute2/blob/e6471d772f3e15a813e6c9a81b4b7adcfad22899/ip/iproute.c#L2314
> 
> Now I finally see that this task can be handled without all this stupid 
> trial-and-error play and doesn't require a limit of route entries if we 
> just reassemble the routing tables in three successive steps resp. loops:
> 
> /* Restore routes in correct order:
>   * 0. ones for local addresses,
>   * 1. ones for local networks,
>   * 2. others (remote networks/hosts).
>   */

Just a quick comment before you risk losing a lot of time (I'm really
not sure though): there *might* be interdependencies between routes in
1. and between routes in 2., especially with 'nexthop' objects. And
IPv6 has several scopes. Maybe it all works thought, I haven't checked
your iproute reference yet.

-- 
Stefano