[quagga-dev 8197] [PATCH 3/3] BGP: use Jenkins hash for all attribute values

Stephen Hemminger shemminger at vyatta.com
Fri Aug 27 22:15:25 BST 2010


I observed while doing some debugging that even for simple tests
there was a lot of hash collisions for BGP attributes.

Mix BGP attribute hash using Jhash rather than additive hashing.
Probably overkill, but the function is fast and available.

Signed-off-by: Stephen Hemminger <shemminger at vyatta.com>
---
 bgpd/bgp_attr.c |   48 ++++++++++++++++++++++--------------------------
 1 files changed, 22 insertions(+), 26 deletions(-)

diff --git a/bgpd/bgp_attr.c b/bgpd/bgp_attr.c
index 7641edf..22950b0 100644
--- a/bgpd/bgp_attr.c
+++ b/bgpd/bgp_attr.c
@@ -335,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 */
     }
 
-- 
1.7.0.4




More information about the Quagga-dev mailing list