From patchwork Fri Dec 10 14:59:24 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Octavian Purdila X-Patchwork-Id: 75097 X-Patchwork-Delegate: shemminger@vyatta.com Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 73A4AB70A3 for ; Sat, 11 Dec 2010 01:59:42 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755570Ab0LJO7g (ORCPT ); Fri, 10 Dec 2010 09:59:36 -0500 Received: from ixro-out-rtc.ixiacom.com ([92.87.192.98]:9376 "EHLO ixro-ex1.ixiacom.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1754899Ab0LJO7g (ORCPT ); Fri, 10 Dec 2010 09:59:36 -0500 Received: from ixro-opurdila.ixiacom.com ([10.205.9.176]) by ixro-ex1.ixiacom.com with Microsoft SMTPSVC(6.0.3790.3959); Fri, 10 Dec 2010 16:59:34 +0200 From: Octavian Purdila To: netdev@vger.kernel.org Cc: Lucian Adrian Grijincu , Vlad Dogaru , Octavian Purdila Subject: [PATCH] iproute2: add dynamic index and name hashes Date: Fri, 10 Dec 2010 16:59:24 +0200 Message-Id: <1291993164-8793-1-git-send-email-opurdila@ixiacom.com> X-Mailer: git-send-email 1.7.1 X-OriginalArrivalTime: 10 Dec 2010 14:59:34.0399 (UTC) FILETIME=[DB5DF0F0:01CB987A] Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org The hashes sizes start with 16 entries and grow up to 2^20 entries. The hashes double when the entries in the LL map is greater then the hash size. Signed-off-by: Octavian Purdila --- lib/ll_map.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++---------- 1 files changed, 103 insertions(+), 22 deletions(-) diff --git a/lib/ll_map.c b/lib/ll_map.c index b8b49aa..9831322 100644 --- a/lib/ll_map.c +++ b/lib/ll_map.c @@ -26,7 +26,8 @@ extern unsigned int if_nametoindex (const char *); struct idxmap { - struct idxmap * next; + struct idxmap *idx_next; + struct idxmap *name_next; unsigned index; int type; int alen; @@ -35,31 +36,100 @@ struct idxmap char name[16]; }; -static struct idxmap *idxmap[16]; +struct idxmap_head { + struct idxmap *next; +}; + +static int hbits = 4, entries; +static struct idxmap_head *idx_hash, *name_hash; + +static unsigned int name_hashfn(const char *name) +{ + const unsigned char *c = (const unsigned char *)name; + unsigned int hash = 0; + + while (*c) + hash = 31*hash + *c++; + + return hash; +} + +static inline unsigned int htrunc(unsigned int value, int bits) +{ + return value % (1<idx_next, 1); im = next) { + hidx = htrunc(im->index, hbits + 1); + im->idx_next = new_idx_hash[hidx].next; + new_idx_hash[hidx].next = im; + + hname = htrunc(name_hashfn(im->name), hbits + 1); + im->name_next = new_name_hash[hname].next; + new_name_hash[hname].next = im; + } + + free(idx_hash); + idx_hash = new_idx_hash; + + free(name_hash); + name_hash = new_name_hash; + + hbits = hbits + 1; +} int ll_remember_index(const struct sockaddr_nl *who, struct nlmsghdr *n, void *arg) { - int h; + int hidx, hname; struct ifinfomsg *ifi = NLMSG_DATA(n); - struct idxmap *im, **imp; + struct idxmap *im; struct rtattr *tb[IFLA_MAX+1]; + if (!idx_hash) { + idx_hash = malloc((1<nlmsg_type != RTM_NEWLINK) return 0; if (n->nlmsg_len < NLMSG_LENGTH(sizeof(ifi))) return -1; - memset(tb, 0, sizeof(tb)); parse_rtattr(tb, IFLA_MAX, IFLA_RTA(ifi), IFLA_PAYLOAD(n)); if (tb[IFLA_IFNAME] == NULL) return 0; - h = ifi->ifi_index&0xF; + hidx = htrunc(ifi->ifi_index, hbits); + hname = htrunc(name_hashfn(RTA_DATA(tb[IFLA_IFNAME])), hbits); - for (imp=&idxmap[h]; (im=*imp)!=NULL; imp = &im->next) + for (im = idx_hash[hidx].next; im != NULL; im = im->idx_next) if (im->index == ifi->ifi_index) break; @@ -67,9 +137,15 @@ int ll_remember_index(const struct sockaddr_nl *who, im = malloc(sizeof(*im)); if (im == NULL) return 0; - im->next = *imp; + + entries++; im->index = ifi->ifi_index; - *imp = im; + + im->idx_next = idx_hash[hidx].next; + idx_hash[hidx].next = im; + + im->name_next = name_hash[hname].next; + name_hash[hname].next = im; } im->type = ifi->ifi_type; @@ -85,6 +161,10 @@ int ll_remember_index(const struct sockaddr_nl *who, memset(im->addr, 0, sizeof(im->addr)); } strcpy(im->name, RTA_DATA(tb[IFLA_IFNAME])); + + if (entries > (1<next) + for (im = idx_hash[htrunc(idx, hbits)].next; im; im = im->idx_next) if (im->index == idx) return im->name; snprintf(buf, 16, "if%d", idx); @@ -115,7 +195,7 @@ int ll_index_to_type(unsigned idx) if (idx == 0) return -1; - for (im = idxmap[idx&0xF]; im; im = im->next) + for (im = idx_hash[htrunc(idx, hbits)].next; im; im = im->idx_next) if (im->index == idx) return im->type; return -1; @@ -128,7 +208,7 @@ unsigned ll_index_to_flags(unsigned idx) if (idx == 0) return 0; - for (im = idxmap[idx&0xF]; im; im = im->next) + for (im = idx_hash[htrunc(idx, hbits)].next; im; im = im->idx_next) if (im->index == idx) return im->flags; return 0; @@ -142,7 +222,7 @@ unsigned ll_index_to_addr(unsigned idx, unsigned char *addr, if (idx == 0) return 0; - for (im = idxmap[idx&0xF]; im; im = im->next) { + for (im = idx_hash[htrunc(idx, hbits)].next; im; im = im->idx_next) { if (im->index == idx) { if (alen > sizeof(im->addr)) alen = sizeof(im->addr); @@ -155,25 +235,26 @@ unsigned ll_index_to_addr(unsigned idx, unsigned char *addr, return 0; } + unsigned ll_name_to_index(const char *name) { static char ncache[16]; static int icache; struct idxmap *im; - int i; + int hname; unsigned idx; if (name == NULL) return 0; if (icache && strcmp(name, ncache) == 0) return icache; - for (i=0; i<16; i++) { - for (im = idxmap[i]; im; im = im->next) { - if (strcmp(im->name, name) == 0) { - icache = im->index; - strcpy(ncache, name); - return im->index; - } + + hname = htrunc(name_hashfn(name), hbits); + for (im = name_hash[hname].next; im; im = im->name_next) { + if (strcmp(im->name, name) == 0) { + icache = im->index; + strcpy(ncache, name); + return im->index; } } @@ -190,7 +271,7 @@ int ll_init_map(struct rtnl_handle *rth) exit(1); } - if (rtnl_dump_filter(rth, ll_remember_index, &idxmap, NULL, NULL) < 0) { + if (rtnl_dump_filter(rth, ll_remember_index, NULL, NULL, NULL) < 0) { fprintf(stderr, "Dump terminated\n"); exit(1); }