From c8e7b8959051bf525183bdbff605e54b4b532e2c Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <shemminger@vyatta.com>
Date: Fri, 27 Aug 2010 14:12:54 -0700
Subject: bgpd: use Jenkins hash for BGP transit, cluster and attr hashes

* bgp_attr.c: I observed while doing some debugging that even for simple
  tests there was a lot of hash collisions for BGP attributes.  Switch to
  using Jhash rather than additive hashing.  Probably overkill, but the
  function is fast and available.

  ({attrhash,cluster,transit}_hask_key_make) convert to Jenkins hash,
  instead of additive hash.
---
 bgpd/bgp_attr.c | 75 +++++++++++++++++++++------------------------------------
 1 file changed, 27 insertions(+), 48 deletions(-)

(limited to 'bgpd')

diff --git a/bgpd/bgp_attr.c b/bgpd/bgp_attr.c
index ae0dc88a..35473651 100644
--- a/bgpd/bgp_attr.c
+++ b/bgpd/bgp_attr.c
@@ -28,6 +28,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 #include "stream.h"
 #include "log.h"
 #include "hash.h"
+#include "jhash.h"
 
 #include "bgpd/bgpd.h"
 #include "bgpd/bgp_attr.h"
@@ -116,18 +117,9 @@ cluster_loop_check (struct cluster_list *cluster, struct in_addr originator)
 static unsigned int
 cluster_hash_key_make (void *p)
 {
-  struct cluster_list * cluster = (struct cluster_list *) p;
-  unsigned int key = 0;
-  int length;
-  caddr_t pnt;
+  const struct cluster_list *cluster = p;
 
-  length = cluster->length;
-  pnt = (caddr_t) cluster->list;
-  
-  while (length)
-    key += pnt[--length];
-
-  return key;
+  return jhash(cluster->list, cluster->length, 0);
 }
 
 static int
@@ -258,18 +250,9 @@ transit_unintern (struct transit *transit)
 static unsigned int
 transit_hash_key_make (void *p)
 {
-  struct transit * transit = (struct transit *) p;
-  unsigned int key = 0;
-  int length;
-  caddr_t pnt;
-
-  length = transit->length;
-  pnt = (caddr_t) transit->val;
-  
-  while (length)
-    key += pnt[--length];
+  const struct transit * transit = p;
 
-  return key;
+  return jhash(transit->val, transit->length, 0);
 }
 
 static int
@@ -352,51 +335,47 @@ attr_unknown_count (void)
 unsigned int
 attrhash_key_make (void *p)
 {
-  struct attr * attr = (struct attr *) p;
-  unsigned int key = 0;
+  const struct attr * attr = (struct attr *) p;
+  uint32_t key = 0;
+#define MIX(val)	key = jhash_1word(val, key)
+
+  MIX(attr->origin);
+  MIX(attr->nexthop.s_addr);
+  MIX(attr->med);
+  MIX(attr->local_pref);
 
-  key += attr->origin;
-  key += attr->nexthop.s_addr;
-  key += attr->med;
-  key += attr->local_pref;
   if (attr->pathlimit.as)
     {
-      key += attr->pathlimit.ttl;
-      key += attr->pathlimit.as;
+      MIX(attr->pathlimit.ttl);
+      MIX(attr->pathlimit.as);
     }
   
   if (attr->extra)
     {
-      key += attr->extra->aggregator_as;
-      key += attr->extra->aggregator_addr.s_addr;
-      key += attr->extra->weight;
-      key += attr->extra->mp_nexthop_global_in.s_addr;
+      MIX(attr->extra->aggregator_as);
+      MIX(attr->extra->aggregator_addr.s_addr);
+      MIX(attr->extra->weight);
+      MIX(attr->extra->mp_nexthop_global_in.s_addr);
     }
   
   if (attr->aspath)
-    key += aspath_key_make (attr->aspath);
+    MIX(aspath_key_make (attr->aspath));
   if (attr->community)
-    key += community_hash_make (attr->community);
+    MIX(community_hash_make (attr->community));
   
   if (attr->extra)
     {
       if (attr->extra->ecommunity)
-        key += ecommunity_hash_make (attr->extra->ecommunity);
+        MIX(ecommunity_hash_make (attr->extra->ecommunity));
       if (attr->extra->cluster)
-        key += cluster_hash_key_make (attr->extra->cluster);
+        MIX(cluster_hash_key_make (attr->extra->cluster));
       if (attr->extra->transit)
-        key += transit_hash_key_make (attr->extra->transit);
+        MIX(transit_hash_key_make (attr->extra->transit));
 
 #ifdef HAVE_IPV6
-      {
-        int i;
-        
-        key += attr->extra->mp_nexthop_len;
-        for (i = 0; i < 16; i++)
-          key += attr->extra->mp_nexthop_global.s6_addr[i];
-        for (i = 0; i < 16; i++)
-          key += attr->extra->mp_nexthop_local.s6_addr[i];
-      }
+      MIX(attr->extra->mp_nexthop_len);
+      key = jhash2(attr->extra->mp_nexthop_global.s6_addr32, 4, key);
+      key = jhash2(attr->extra->mp_nexthop_local.s6_addr32, 4, key);
 #endif /* HAVE_IPV6 */
     }
 
-- 
cgit v1.2.1