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

[Martin Schitter <ms+git@mur.at>]

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