| 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
| ||
|
Message-ID: <4AE1331D.6000604@gmail.com>
Date: Fri, 23 Oct 2009 06:37:49 +0200
From: Eric Dumazet <eric.dumazet@...il.com>
To: Stephen Hemminger <shemminger@...tta.com>
CC: Linux Netdev List <netdev@...r.kernel.org>
Subject: [PATCH iproute2] ip: speedup store_nlmsg()
ip link show command has O(N^2) complexity, because it loops until list end.
Adding pointer to last elements avoids this loop.
Before patch :
# time ip -o link | wc
15013 240212 2136365
real 0m0.738s
user 0m0.770s
sys 0m0.035s
# time ip link show dev eth0
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP qlen 1000
link/ether 00:1e:0b:ec:d3:dc brd ff:ff:ff:ff:ff:ff
real 0m0.565s
user 0m0.540s
sys 0m0.025s
After patch :
# time ip/ip -o link | wc
15013 210192 2031310
real 0m0.189s
user 0m0.221s
sys 0m0.032s
# time ip/ip link show dev eth0
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP qlen 1000
link/ether 00:1e:0b:ec:d3:dc brd ff:ff:ff:ff:ff:ff
real 0m0.032s
user 0m0.006s
sys 0m0.026s
Signed-off-by: Eric Dumazet <eric.dumazet@...il.com>
---
diff --git a/ip/ipaddress.c b/ip/ipaddress.c
index cadc1a3..7674256 100644
--- a/ip/ipaddress.c
+++ b/ip/ipaddress.c
@@ -570,13 +570,16 @@ static int print_selected_addrinfo(int ifindex, struct nlmsg_list *ainfo, FILE *
return 0;
}
+struct nlmsg_list_info {
+ struct nlmsg_list *first;
+ struct nlmsg_list *last;
+};
static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n,
void *arg)
{
- struct nlmsg_list **linfo = (struct nlmsg_list**)arg;
+ struct nlmsg_list_info *linfo = (struct nlmsg_list_info *)arg;
struct nlmsg_list *h;
- struct nlmsg_list **lp;
h = malloc(n->nlmsg_len+sizeof(void*));
if (h == NULL)
@@ -585,8 +588,11 @@ static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n,
memcpy(&h->h, n, n->nlmsg_len);
h->next = NULL;
- for (lp = linfo; *lp; lp = &(*lp)->next) /* NOTHING */;
- *lp = h;
+ if (linfo->first)
+ linfo->last->next = h;
+ else
+ linfo->first = h;
+ linfo->last = h;
ll_remember_index(who, n, NULL);
return 0;
@@ -594,8 +600,8 @@ static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n,
static int ipaddr_list_or_flush(int argc, char **argv, int flush)
{
- struct nlmsg_list *linfo = NULL;
- struct nlmsg_list *ainfo = NULL;
+ struct nlmsg_list_info linfo = {0};
+ struct nlmsg_list_info ainfo = {0};
struct nlmsg_list *l, *n;
char *filter_dev = NULL;
int no_link = 0;
@@ -750,7 +756,7 @@ static int ipaddr_list_or_flush(int argc, char **argv, int flush)
if (filter.family && filter.family != AF_PACKET) {
struct nlmsg_list **lp;
- lp=&linfo;
+ lp = &linfo.first;
if (filter.oneline)
no_link = 1;
@@ -760,7 +766,7 @@ static int ipaddr_list_or_flush(int argc, char **argv, int flush)
struct ifinfomsg *ifi = NLMSG_DATA(&l->h);
struct nlmsg_list *a;
- for (a=ainfo; a; a=a->next) {
+ for (a = ainfo.first; a; a = a->next) {
struct nlmsghdr *n = &a->h;
struct ifaddrmsg *ifa = NLMSG_DATA(n);
@@ -807,12 +813,12 @@ static int ipaddr_list_or_flush(int argc, char **argv, int flush)
}
}
- for (l=linfo; l; l = n) {
+ for (l = linfo.first; l; l = n) {
n = l->next;
if (no_link || print_linkinfo(NULL, &l->h, stdout) == 0) {
struct ifinfomsg *ifi = NLMSG_DATA(&l->h);
if (filter.family != AF_PACKET)
- print_selected_addrinfo(ifi->ifi_index, ainfo, stdout);
+ print_selected_addrinfo(ifi->ifi_index, ainfo.first, stdout);
}
fflush(stdout);
free(l);
--
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
Powered by blists - more mailing lists