Date:	Fri, 10 Dec 2010 16:59:24 +0200
From:	Octavian Purdila <opurdila@...acom.com>
To:	netdev@...r.kernel.org
Cc:	Lucian Adrian Grijincu <lucian.grijincu@...il.com>,
	Vlad Dogaru <ddvlad@...edu.org>,
	Octavian Purdila <opurdila@...acom.com>
Subject: [PATCH] iproute2: add dynamic index and name hashes

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 <opurdila@...acom.com>
---
 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<<bits);
+}
+
+void grow_hashes(void)
+{
+	struct idxmap_head *new_idx_hash, *new_name_hash;
+	struct idxmap *next, *im;
+	int hidx, hname, i, new_size = 1<<(hbits+1);
+
+	if (hbits == 20)
+		return;
+
+	new_idx_hash = malloc(new_size * sizeof(struct idxmap_head));
+	new_name_hash = malloc(new_size * sizeof(struct idxmap_head));
+
+	if (!new_idx_hash || !new_name_hash)
+		return;
+
+	for (i = 0; i < (hbits<<1); i++)
+		for (im = idx_hash[i].next;
+		     im != NULL && (next = im->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<<hbits) * sizeof(struct idxmap_head));
+		if (!idx_hash)
+			return -1;
+	}
+
+	if (!name_hash) {
+		name_hash = malloc((1<<hbits) * sizeof(struct idxmap_head));
+		if (!name_hash)
+			return -1;
+	}
+
 	if (n->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<<hbits))
+		grow_hashes();
+
 	return 0;
 }
 
@@ -94,7 +174,7 @@ const char *ll_idx_n2a(unsigned idx, char *buf)
 
 	if (idx == 0)
 		return "*";
-	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->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);
 	}
-- 
1.7.1

--
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