From 6fe1d78a0d11f4389c651af03dd2b883f4d371f0 Mon Sep 17 00:00:00 2001 From: Jiri Horky Date: Thu, 23 Mar 2017 22:59:45 +0100 Subject: 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. --- .../plugins/kernel_netlink/kernel_netlink_shared.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to 'src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c') 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; } -- cgit v1.2.3