kernel-netlink: Avoid O(n^2) copy operations when concatenating Netlink responses
authorJiri Horky <horky@avast.com>
Thu, 23 Mar 2017 21:59:45 +0000 (22:59 +0100)
committerTobias Brunner <tobias@strongswan.org>
Mon, 27 Mar 2017 09:05:26 +0000 (11:05 +0200)
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.

src/libcharon/plugins/kernel_netlink/kernel_netlink_shared.c

index 4460900..da54031 100644 (file)
@@ -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;
 }