kernel-netlink: Avoid O(n^2) copy operations when concatenating Netlink responses

When constructing the result, all responses from Netlink were concatenated
iteratively, i.e. for each response, the previously acquired result was
copied to newly allocated memory and the current response appended to it.
This results in O(n^2) copy operations. Instead, we now check for the
total final length of the result and copy the individual responses to it
in one pass, i.e. in O(n) copy operations. In particular, this issue caused
very high CPU usage in memcpy() function as the result is copied over and
over. Common way how to hit the issue is when having 1000+ routes and 5+
connecting clients a second. In that case, the memcpy() function can
take 50%+ of one CPU thread on a decent CPU and the whole charon daemon
is stuck just reading routes and concatenating them together (connecting
clients are blocked in that particular case as this is done under mutex).

Closes strongswan/strongswan#65.
References #2055.

1 files changed, 13 insertions, 7 deletions

diff --git a/src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c b/src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c
index 44609002f..da54031a1 100644
--- a/src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c
+++ b/src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c
@@ -304,8 +304,9 @@ static status_t send_once(private_netlink_socket_t *this, struct nlmsghdr *in,
 						  uintptr_t seq, struct nlmsghdr **out, size_t *out_len)
 {
 	struct nlmsghdr *hdr;
-	chunk_t result = {};
 	entry_t *entry;
+	u_char *ptr;
+	int i;
 
 	in->nlmsg_seq = seq;
 	in->nlmsg_pid = getpid();
@@ -366,6 +367,14 @@ static status_t send_once(private_netlink_socket_t *this, struct nlmsghdr *in,
 		return OUT_OF_RES;
 	}
 
+	for (i = 0, *out_len = 0; i < array_count(entry->hdrs); i++)
+	{
+		array_get(entry->hdrs, i, &hdr);
+		*out_len += hdr->nlmsg_len;
+	}
+	ptr = malloc(*out_len);
+	*out = (struct nlmsghdr*)ptr;
+
 	while (array_remove(entry->hdrs, ARRAY_HEAD, &hdr))
 	{
 		if (this->names)
@@ -373,14 +382,11 @@ static status_t send_once(private_netlink_socket_t *this, struct nlmsghdr *in,
 			DBG3(DBG_KNL, "received %N %u: %b", this->names, hdr->nlmsg_type,
 				 hdr->nlmsg_seq, hdr, hdr->nlmsg_len);
 		}
-		result = chunk_cat("mm", result,
-						   chunk_create((char*)hdr, hdr->nlmsg_len));
+		memcpy(ptr, hdr, hdr->nlmsg_len);
+		ptr += hdr->nlmsg_len;
+		free(hdr);
 	}
 	destroy_entry(entry);
-
-	*out_len = result.len;
-	*out = (struct nlmsghdr*)result.ptr;
-
 	return SUCCESS;
 }