[PATCH v2] Fix for Bug #221 -- Issue concerning bigger routing tables
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.
---
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
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
On Tue, 8 Sep 2026 18:13:13 +0000
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
#include #include +#include #include #include #include @@ -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
On Tue, 8 Sep 2026 18:13:14 +0000
Martin Schitter
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
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.
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/e6471d772f3e15a813e6c9a81b4b7adcfa... 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.
participants (2)
-
Martin Schitter
-
Stefano Brivio