[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

[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

[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