Merge pull request #1099 from donaldsharp/hashing

Hashing

20 files changed, 105 insertions, 86 deletions

diff --git a/bgpd/bgp_advertise.c b/bgpd/bgp_advertise.c
index c7c9631512..a7f72974ca 100644
--- a/bgpd/bgp_advertise.c
+++ b/bgpd/bgp_advertise.c
@@ -246,7 +246,9 @@ void bgp_sync_init(struct peer *peer)
 			BGP_ADV_FIFO_INIT(&sync->withdraw_low);
 			peer->sync[afi][safi] = sync;
 			peer->hash[afi][safi] =
-				hash_create(baa_hash_key, baa_hash_cmp, NULL);
+				hash_create(baa_hash_key,
+					    baa_hash_cmp,
+					    "BGP Sync Hash");
 		}
 }
 
diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
index 4e55c5f264..2ce52d92a5 100644
--- a/bgpd/bgp_aspath.c
+++ b/bgpd/bgp_aspath.c
@@ -2019,7 +2019,10 @@ int aspath_cmp(const void *arg1, const void *arg2)
 /* AS path hash initialize. */
 void aspath_init(void)
 {
-	ashash = hash_create_size(32768, aspath_key_make, aspath_cmp, NULL);
+	ashash = hash_create_size(32768,
+				  aspath_key_make,
+				  aspath_cmp,
+				  "BGP AS Path");
 }
 
 void aspath_finish(void)
diff --git a/bgpd/bgp_attr.c b/bgpd/bgp_attr.c
index e15a7618b8..03cf3625b7 100644
--- a/bgpd/bgp_attr.c
+++ b/bgpd/bgp_attr.c
@@ -200,8 +200,9 @@ void cluster_unintern(struct cluster_list *cluster)
 
 static void cluster_init(void)
 {
-	cluster_hash =
-		hash_create(cluster_hash_key_make, cluster_hash_cmp, NULL);
+	cluster_hash = hash_create(cluster_hash_key_make,
+				   cluster_hash_cmp,
+				   "BGP Cluster");
 }
 
 static void cluster_finish(void)
@@ -377,9 +378,13 @@ static int encap_hash_cmp(const void *p1, const void *p2)
 
 static void encap_init(void)
 {
-	encap_hash = hash_create(encap_hash_key_make, encap_hash_cmp, NULL);
+	encap_hash = hash_create(encap_hash_key_make,
+				 encap_hash_cmp,
+				 "BGP Encap Hash");
 #if ENABLE_BGP_VNC
-	vnc_hash = hash_create(encap_hash_key_make, encap_hash_cmp, NULL);
+	vnc_hash = hash_create(encap_hash_key_make,
+			       encap_hash_cmp,
+			       "BGP VNC Hash");
 #endif
 }
 
@@ -479,8 +484,9 @@ static int transit_hash_cmp(const void *p1, const void *p2)
 
 static void transit_init(void)
 {
-	transit_hash =
-		hash_create(transit_hash_key_make, transit_hash_cmp, NULL);
+	transit_hash = hash_create(transit_hash_key_make,
+				   transit_hash_cmp,
+				   "BGP Transit Hash");
 }
 
 static void transit_finish(void)
@@ -645,8 +651,9 @@ int attrhash_cmp(const void *p1, const void *p2)
 
 static void attrhash_init(void)
 {
-	attrhash =
-		hash_create(attrhash_key_make, attrhash_cmp, "BGP Attributes");
+	attrhash = hash_create(attrhash_key_make,
+			       attrhash_cmp,
+			       "BGP Attributes");
 }
 
 /*
diff --git a/bgpd/bgp_community.c b/bgpd/bgp_community.c
index 7e8411b6a0..b0f00d67d6 100644
--- a/bgpd/bgp_community.c
+++ b/bgpd/bgp_community.c
@@ -23,6 +23,7 @@
 #include "command.h"
 #include "hash.h"
 #include "memory.h"
+#include "jhash.h"
 
 #include "bgpd/bgp_memory.h"
 #include "bgpd/bgp_community.h"
@@ -409,19 +410,9 @@ char *community_str(struct community *com)
    hash package.*/
 unsigned int community_hash_make(struct community *com)
 {
-	unsigned char *pnt = (unsigned char *)com->val;
-	int size = com->size * 4;
-	unsigned int key = 0;
-	int c;
-
-	for (c = 0; c < size; c += 4) {
-		key += pnt[c];
-		key += pnt[c + 1];
-		key += pnt[c + 2];
-		key += pnt[c + 3];
-	}
+	u_int32_t *pnt = (u_int32_t *)com->val;
 
-	return key;
+	return jhash2(pnt, com->size, 0x43ea96c1);
 }
 
 int community_match(const struct community *com1, const struct community *com2)
@@ -653,7 +644,8 @@ void community_init(void)
 {
 	comhash = hash_create(
 		(unsigned int (*)(void *))community_hash_make,
-		(int (*)(const void *, const void *))community_cmp, NULL);
+		(int (*)(const void *, const void *))community_cmp,
+		"BGP Community Hash");
 }
 
 void community_finish(void)
diff --git a/bgpd/bgp_ecommunity.c b/bgpd/bgp_ecommunity.c
index 7ac16896a2..ec52422d4c 100644
--- a/bgpd/bgp_ecommunity.c
+++ b/bgpd/bgp_ecommunity.c
@@ -26,6 +26,7 @@
 #include "command.h"
 #include "queue.h"
 #include "filter.h"
+#include "jhash.h"
 
 #include "bgpd/bgpd.h"
 #include "bgpd/bgp_ecommunity.h"
@@ -234,22 +235,8 @@ unsigned int ecommunity_hash_make(void *arg)
 {
 	const struct ecommunity *ecom = arg;
 	int size = ecom->size * ECOMMUNITY_SIZE;
-	u_int8_t *pnt = ecom->val;
-	unsigned int key = 0;
-	int c;
-
-	for (c = 0; c < size; c += ECOMMUNITY_SIZE) {
-		key += pnt[c];
-		key += pnt[c + 1];
-		key += pnt[c + 2];
-		key += pnt[c + 3];
-		key += pnt[c + 4];
-		key += pnt[c + 5];
-		key += pnt[c + 6];
-		key += pnt[c + 7];
-	}
 
-	return key;
+	return jhash(ecom->val, size, 0x564321ab);
 }
 
 /* Compare two Extended Communities Attribute structure.  */
@@ -272,7 +259,9 @@ int ecommunity_cmp(const void *arg1, const void *arg2)
 /* Initialize Extended Comminities related hash. */
 void ecommunity_init(void)
 {
-	ecomhash = hash_create(ecommunity_hash_make, ecommunity_cmp, NULL);
+	ecomhash = hash_create(ecommunity_hash_make,
+			       ecommunity_cmp,
+			       "BGP ecommunity hash");
 }
 
 void ecommunity_finish(void)
diff --git a/bgpd/bgp_lcommunity.c b/bgpd/bgp_lcommunity.c
index 395ae52712..d75f33f58b 100644
--- a/bgpd/bgp_lcommunity.c
+++ b/bgpd/bgp_lcommunity.c
@@ -25,6 +25,7 @@
 #include "prefix.h"
 #include "command.h"
 #include "filter.h"
+#include "jhash.h"
 
 #include "bgpd/bgpd.h"
 #include "bgpd/bgp_lcommunity.h"
@@ -230,26 +231,8 @@ unsigned int lcommunity_hash_make(void *arg)
 {
 	const struct lcommunity *lcom = arg;
 	int size = lcom_length(lcom);
-	u_int8_t *pnt = lcom->val;
-	unsigned int key = 0;
-	int c;
-
-	for (c = 0; c < size; c += LCOMMUNITY_SIZE) {
-		key += pnt[c];
-		key += pnt[c + 1];
-		key += pnt[c + 2];
-		key += pnt[c + 3];
-		key += pnt[c + 4];
-		key += pnt[c + 5];
-		key += pnt[c + 6];
-		key += pnt[c + 7];
-		key += pnt[c + 8];
-		key += pnt[c + 9];
-		key += pnt[c + 10];
-		key += pnt[c + 11];
-	}
 
-	return key;
+	return jhash(lcom->val, size, 0xab125423);
 }
 
 /* Compare two Large Communities Attribute structure.  */
@@ -272,7 +255,9 @@ struct hash *lcommunity_hash(void)
 /* Initialize Large Comminities related hash. */
 void lcommunity_init(void)
 {
-	lcomhash = hash_create(lcommunity_hash_make, lcommunity_cmp, NULL);
+	lcomhash = hash_create(lcommunity_hash_make,
+			       lcommunity_cmp,
+			       "BGP lcommunity hash");
 }
 
 void lcommunity_finish(void)
diff --git a/bgpd/bgp_nexthop.c b/bgpd/bgp_nexthop.c
index b7d7cd9fa3..1200d74d6a 100644
--- a/bgpd/bgp_nexthop.c
+++ b/bgpd/bgp_nexthop.c
@@ -122,8 +122,9 @@ static int bgp_tip_hash_cmp(const void *p1, const void *p2)
 
 void bgp_tip_hash_init(struct bgp *bgp)
 {
-	bgp->tip_hash =
-		hash_create(bgp_tip_hash_key_make, bgp_tip_hash_cmp, NULL);
+	bgp->tip_hash = hash_create(bgp_tip_hash_key_make,
+				    bgp_tip_hash_cmp,
+				    "BGP TIP hash");
 }
 
 void bgp_tip_hash_destroy(struct bgp *bgp)
@@ -204,7 +205,8 @@ static int bgp_address_hash_cmp(const void *p1, const void *p2)
 void bgp_address_init(struct bgp *bgp)
 {
 	bgp->address_hash = hash_create(bgp_address_hash_key_make,
-					bgp_address_hash_cmp, NULL);
+					bgp_address_hash_cmp,
+					"BGP Address Hash");
 }
 
 void bgp_address_destroy(struct bgp *bgp)
diff --git a/bgpd/bgp_updgrp.c b/bgpd/bgp_updgrp.c
index 77e6157150..9630afb717 100644
--- a/bgpd/bgp_updgrp.c
+++ b/bgpd/bgp_updgrp.c
@@ -84,7 +84,9 @@ static void sync_init(struct update_subgroup *subgrp)
 	BGP_ADV_FIFO_INIT(&subgrp->sync->update);
 	BGP_ADV_FIFO_INIT(&subgrp->sync->withdraw);
 	BGP_ADV_FIFO_INIT(&subgrp->sync->withdraw_low);
-	subgrp->hash = hash_create(baa_hash_key, baa_hash_cmp, NULL);
+	subgrp->hash = hash_create(baa_hash_key,
+				   baa_hash_cmp,
+				   "BGP SubGroup Hash");
 
 	/* We use a larger buffer for subgrp->work in the event that:
 	 * - We RX a BGP_UPDATE where the attributes alone are just
@@ -1549,8 +1551,10 @@ void update_bgp_group_init(struct bgp *bgp)
 	int afid;
 
 	AF_FOREACH(afid)
-	bgp->update_groups[afid] =
-		hash_create(updgrp_hash_key_make, updgrp_hash_cmp, NULL);
+		bgp->update_groups[afid] =
+			hash_create(updgrp_hash_key_make,
+				    updgrp_hash_cmp,
+				    "BGP Update Group Hash");
 }
 
 void update_bgp_group_free(struct bgp *bgp)
diff --git a/bgpd/bgp_vty.c b/bgpd/bgp_vty.c
index a29b7f7bec..f9105bfaf7 100644
--- a/bgpd/bgp_vty.c
+++ b/bgpd/bgp_vty.c
@@ -9934,7 +9934,7 @@ static void community_show_all_iterator(struct hash_backet *backet,
 	struct community *com;
 
 	com = (struct community *)backet->data;
-	vty_out(vty, "[%p] (%ld) %s\n", (void *)backet, com->refcnt,
+	vty_out(vty, "[%p] (%ld) %s\n", (void *)com, com->refcnt,
 		community_str(com));
 }
 
@@ -9963,7 +9963,7 @@ static void lcommunity_show_all_iterator(struct hash_backet *backet,
 	struct lcommunity *lcom;
 
 	lcom = (struct lcommunity *)backet->data;
-	vty_out(vty, "[%p] (%ld) %s\n", (void *)backet, lcom->refcnt,
+	vty_out(vty, "[%p] (%ld) %s\n", (void *)lcom, lcom->refcnt,
 		lcommunity_str(lcom));
 }
 
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index 86eea1b220..0d60047562 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -2833,7 +2833,9 @@ static struct bgp *bgp_create(as_t *as, const char *name,
 			XSTRDUP(MTYPE_BGP_PEER_HOST, cmd_domainname_get());
 	bgp->peer = list_new();
 	bgp->peer->cmp = (int (*)(void *, void *))peer_cmp;
-	bgp->peerhash = hash_create(peer_hash_key_make, peer_hash_same, NULL);
+	bgp->peerhash = hash_create(peer_hash_key_make,
+				    peer_hash_same,
+				    "BGP Peer Hash");
 	bgp->peerhash->max_size = BGP_PEER_MAX_HASH_SIZE;
 
 	bgp->group = list_new();
diff --git a/lib/command.c b/lib/command.c
index a303781370..d1b0867372 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -43,6 +43,7 @@
 #include "qobj.h"
 #include "defaults.h"
 #include "libfrr.h"
+#include "jhash.h"
 
 DEFINE_MTYPE(LIB, HOST, "Host config")
 DEFINE_MTYPE(LIB, STRVEC, "String vector")
@@ -278,7 +279,9 @@ int argv_find(struct cmd_token **argv, int argc, const char *text, int *index)
 
 static unsigned int cmd_hash_key(void *p)
 {
-	return (uintptr_t)p;
+	int size = sizeof(p);
+
+	return jhash(p, size, 0);
 }
 
 static int cmd_hash_cmp(const void *a, const void *b)
@@ -298,7 +301,9 @@ void install_node(struct cmd_node *node, int (*func)(struct vty *))
 		cmd_token_new(START_TKN, CMD_ATTR_NORMAL, NULL, NULL);
 	graph_new_node(node->cmdgraph, token,
 		       (void (*)(void *)) & cmd_token_del);
-	node->cmd_hash = hash_create(cmd_hash_key, cmd_hash_cmp, NULL);
+	node->cmd_hash = hash_create_size(16, cmd_hash_key,
+					  cmd_hash_cmp,
+					  "Command Hash");
 }
 
 /**
diff --git a/lib/if_rmap.c b/lib/if_rmap.c
index 968c087c3c..53c2824a99 100644
--- a/lib/if_rmap.c
+++ b/lib/if_rmap.c
@@ -294,7 +294,10 @@ void if_rmap_reset()
 
 void if_rmap_init(int node)
 {
-	ifrmaphash = hash_create(if_rmap_hash_make, if_rmap_hash_cmp, NULL);
+	ifrmaphash = hash_create_size(4,
+				      if_rmap_hash_make,
+				      if_rmap_hash_cmp,
+				      "Interface Route-Map Hash");
 	if (node == RIPNG_NODE) {
 	} else if (node == RIP_NODE) {
 		install_element(RIP_NODE, &if_rmap_cmd);
diff --git a/lib/qobj.c b/lib/qobj.c
index 5f450ca0d3..c75002052e 100644
--- a/lib/qobj.c
+++ b/lib/qobj.c
@@ -25,6 +25,7 @@
 #include "hash.h"
 #include "log.h"
 #include "qobj.h"
+#include "jhash.h"
 
 static pthread_rwlock_t nodes_lock;
 static struct hash *nodes = NULL;
@@ -97,7 +98,9 @@ void qobj_init(void)
 {
 	if (!nodes) {
 		pthread_rwlock_init(&nodes_lock, NULL);
-		nodes = hash_create(qobj_key, qobj_cmp, NULL);
+		nodes = hash_create_size(16, qobj_key,
+					 qobj_cmp,
+					 "QOBJ Hash");
 	}
 }
 
diff --git a/lib/routemap.c b/lib/routemap.c
index 409c9c3780..31afc33f58 100644
--- a/lib/routemap.c
+++ b/lib/routemap.c
@@ -1581,8 +1581,10 @@ static void *route_map_dep_hash_alloc(void *p)
 
 	dep_entry = XCALLOC(MTYPE_ROUTE_MAP_DEP, sizeof(struct route_map_dep));
 	dep_entry->dep_name = XSTRDUP(MTYPE_ROUTE_MAP_NAME, dep_name);
-	dep_entry->dep_rmap_hash = hash_create(route_map_dep_hash_make_key,
-					       route_map_rmap_hash_cmp, NULL);
+	dep_entry->dep_rmap_hash = hash_create_size(8,
+						    route_map_dep_hash_make_key,
+						    route_map_rmap_hash_cmp,
+						    "Route Map Dep Hash");
 	dep_entry->this_hash = NULL;
 
 	return ((void *)dep_entry);
@@ -2784,12 +2786,15 @@ void route_map_init(void)
 	route_match_vec = vector_init(1);
 	route_set_vec = vector_init(1);
 	route_map_master_hash =
-		hash_create(route_map_hash_key_make, route_map_hash_cmp, NULL);
+		hash_create_size(8, route_map_hash_key_make,
+				 route_map_hash_cmp,
+				 "Route Map Master Hash");
 
 	for (i = 1; i < ROUTE_MAP_DEP_MAX; i++)
 		route_map_dep_hash[i] =
-			hash_create(route_map_dep_hash_make_key,
-				    route_map_dep_hash_cmp, NULL);
+			hash_create_size(8, route_map_dep_hash_make_key,
+					 route_map_dep_hash_cmp,
+					 "Route Map Dep Hash");
 
 	cmd_variable_handler_register(rmap_var_handlers);
 
diff --git a/lib/thread.c b/lib/thread.c
index b39f2d55c2..0ce38dd340 100644
--- a/lib/thread.c
+++ b/lib/thread.c
@@ -31,6 +31,7 @@
 #include "command.h"
 #include "sigevent.h"
 #include "network.h"
+#include "jhash.h"
 
 DEFINE_MTYPE_STATIC(LIB, THREAD, "Thread")
 DEFINE_MTYPE_STATIC(LIB, THREAD_MASTER, "Thread master")
@@ -58,7 +59,9 @@ static struct list *masters;
 /* CLI start ---------------------------------------------------------------- */
 static unsigned int cpu_record_hash_key(struct cpu_thread_history *a)
 {
-	return (uintptr_t)a->func;
+	int size = sizeof (&a->func);
+
+	return jhash(&a->func, size, 0);
 }
 
 static int cpu_record_hash_cmp(const struct cpu_thread_history *a,
@@ -376,9 +379,11 @@ struct thread_master *thread_master_create(const char *name)
 		return NULL;
 	}
 
-	rv->cpu_record = hash_create(
+	rv->cpu_record = hash_create_size(
+		8,
 		(unsigned int (*)(void *))cpu_record_hash_key,
-		(int (*)(const void *, const void *))cpu_record_hash_cmp, NULL);
+		(int (*)(const void *, const void *))cpu_record_hash_cmp,
+		"Thread Hash");
 
 
 	/* Initialize the timer queues */
diff --git a/nhrpd/nhrp_cache.c b/nhrpd/nhrp_cache.c
index 3ebdbf27ba..3ff1a342dc 100644
--- a/nhrpd/nhrp_cache.c
+++ b/nhrpd/nhrp_cache.c
@@ -81,7 +81,9 @@ struct nhrp_cache *nhrp_cache_get(struct interface *ifp, union sockunion *remote
 	struct nhrp_cache key;
 
 	if (!nifp->cache_hash) {
-		nifp->cache_hash = hash_create(nhrp_cache_protocol_key, nhrp_cache_protocol_cmp, NULL);
+		nifp->cache_hash = hash_create(nhrp_cache_protocol_key,
+					       nhrp_cache_protocol_cmp,
+					       "NHRP Cache");
 		if (!nifp->cache_hash)
 			return NULL;
 	}
diff --git a/nhrpd/nhrp_peer.c b/nhrpd/nhrp_peer.c
index 4ee9afbd54..2bcddc0801 100644
--- a/nhrpd/nhrp_peer.c
+++ b/nhrpd/nhrp_peer.c
@@ -182,7 +182,9 @@ struct nhrp_peer *nhrp_peer_get(struct interface *ifp, const union sockunion *re
 	struct nhrp_vc *vc;
 
 	if (!nifp->peer_hash) {
-		nifp->peer_hash = hash_create(nhrp_peer_key, nhrp_peer_cmp, NULL);
+		nifp->peer_hash = hash_create(nhrp_peer_key,
+					      nhrp_peer_cmp,
+					      "NHRP Peer Hash");
 		if (!nifp->peer_hash) return NULL;
 	}
 
diff --git a/nhrpd/nhrp_vc.c b/nhrpd/nhrp_vc.c
index a5547a7a7e..d0915bc7a3 100644
--- a/nhrpd/nhrp_vc.c
+++ b/nhrpd/nhrp_vc.c
@@ -196,7 +196,9 @@ void nhrp_vc_init(void)
 {
 	size_t i;
 
-	nhrp_vc_hash = hash_create(nhrp_vc_key, nhrp_vc_cmp, NULL);
+	nhrp_vc_hash = hash_create(nhrp_vc_key,
+				   nhrp_vc_cmp,
+				   "NHRP VC hash");
 	for (i = 0; i < ZEBRA_NUM_OF(childlist_head); i++)
 		list_init(&childlist_head[i]);
 }
diff --git a/nhrpd/reqid.c b/nhrpd/reqid.c
index 61fbfd7795..e5bd45a8f4 100644
--- a/nhrpd/reqid.c
+++ b/nhrpd/reqid.c
@@ -17,7 +17,9 @@ static int nhrp_reqid_cmp(const void *data, const void *key)
 uint32_t nhrp_reqid_alloc(struct nhrp_reqid_pool *p, struct nhrp_reqid *r, void (*cb)(struct nhrp_reqid *, void *))
 {
 	if (!p->reqid_hash) {
-		p->reqid_hash = hash_create(nhrp_reqid_key, nhrp_reqid_cmp, NULL);
+		p->reqid_hash = hash_create(nhrp_reqid_key,
+					    nhrp_reqid_cmp,
+					    "NHRP reqid Hash");
 		p->next_request_id = 1;
 	}
 
diff --git a/zebra/zebra_mpls.c b/zebra/zebra_mpls.c
index 3c4de40db3..273945778a 100644
--- a/zebra/zebra_mpls.c
+++ b/zebra/zebra_mpls.c
@@ -2812,8 +2812,12 @@ void zebra_mpls_init_tables(struct zebra_vrf *zvrf)
 {
 	if (!zvrf)
 		return;
-	zvrf->slsp_table = hash_create(label_hash, label_cmp, NULL);
-	zvrf->lsp_table = hash_create(label_hash, label_cmp, NULL);
+	zvrf->slsp_table = hash_create(label_hash,
+				       label_cmp,
+				       "ZEBRA SLSP table");
+	zvrf->lsp_table = hash_create(label_hash,
+				      label_cmp,
+				      "ZEBRA LSP table");
 	zvrf->fec_table[AFI_IP] = route_table_init();
 	zvrf->fec_table[AFI_IP6] = route_table_init();
 	zvrf->mpls_flags = 0;