netdev - [PATCH 1/2] iproute2: Improve list add.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 22 May 2012 15:37:19 -0700
From:	Pravin B Shelar <pshelar@...ira.com>
To:	shemminger@...tta.com, netdev@...r.kernel.org
Cc:	jpettit@...ira.com, jesse@...ira.com,
	Pravin B Shelar <pshelar@...ira.com>
Subject: [PATCH 1/2] iproute2: Improve list add.

ip command reads entire list of devices on every flush command.
While adding device record to list is does list traversal O(n).
This is time consuming for large batch commands.
Following patch improves list add operation to O(1).

Reported-by: Justin Pettit <jpettit@...ira.com>
Signed-off-by: Pravin B Shelar <pshelar@...ira.com>
---
 ip/ipaddress.c |   16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/ip/ipaddress.c b/ip/ipaddress.c
index 9ab65ec..7080c41 100644
--- a/ip/ipaddress.c
+++ b/ip/ipaddress.c
@@ -714,6 +714,7 @@ int print_addrinfo_secondary(const struct sockaddr_nl *who, struct nlmsghdr *n,
 struct nlmsg_list
 {
 	struct nlmsg_list *next;
+	struct nlmsg_list *last;
 	struct nlmsghdr	  h;
 };
 
@@ -744,17 +745,24 @@ static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n,
 {
 	struct nlmsg_list **linfo = (struct nlmsg_list**)arg;
 	struct nlmsg_list *h;
-	struct nlmsg_list **lp;
 
-	h = malloc(n->nlmsg_len+sizeof(void*));
+	h = malloc(n->nlmsg_len+sizeof(void*)+sizeof(void*));
 	if (h == NULL)
 		return -1;
 
 	memcpy(&h->h, n, n->nlmsg_len);
 	h->next = NULL;
 
-	for (lp = linfo; *lp; lp = &(*lp)->next) /* NOTHING */;
-	*lp = h;
+	if (!*linfo) {
+		/* First element. */
+		h->last = h;
+		*linfo = h;
+	} else {
+		struct nlmsg_list *last = (*linfo)->last;
+
+		last->next = h;
+		(*linfo)->last = h;
+	}
 
 	ll_remember_index(who, n, NULL);
 	return 0;
-- 
1.7.10

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html