lib: Add hash function for nexthop groups

Add a hash function to turn a nexthop group into a
32 bit unsigned hash key with jhash. We do not care to
hash any recursively resolved nexthops, just the group.

Signed-off-by: Stephen Worley <sworley@cumulusnetworks.com>

diff --git a/lib/nexthop.c b/lib/nexthop.c
index 474abee3091c80e092b48c3b6c94d6ec223a41ab..8e16e705901b8a951b81bf108cba5b5e5dc5f7cb 100644 (file)
--- a/lib/nexthop.c
+++ b/lib/nexthop.c
@@ -314,14 +314,52 @@ unsigned int nexthop_level(struct nexthop *nexthop)
        return rv;
 }
 
-uint32_t nexthop_hash(struct nexthop *nexthop)
+uint32_t nexthop_hash(const struct nexthop *nexthop)
 {
-       uint32_t key;
+       uint32_t key = 0x45afe398;
 
-       key = jhash_1word(nexthop->vrf_id, 0x45afe398);
-       key = jhash_1word(nexthop->ifindex, key);
-       key = jhash_1word(nexthop->type, key);
-       key = jhash(&nexthop->gate, sizeof(union g_addr), key);
+       key = jhash_3words(nexthop->type, nexthop->vrf_id,
+                          nexthop->nh_label_type, key);
+       /* gate and blackhole are together in a union */
+       key = jhash(&nexthop->gate, sizeof(nexthop->gate), key);
+       key = jhash(&nexthop->src, sizeof(nexthop->src), key);
+       key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key);
 
+       if (nexthop->nh_label) {
+               int labels = nexthop->nh_label->num_labels;
+               int i = 0;
+
+               while (labels >= 3) {
+                       key = jhash_3words(nexthop->nh_label->label[i],
+                                          nexthop->nh_label->label[i + 1],
+                                          nexthop->nh_label->label[i + 2],
+                                          key);
+                       labels -= 3;
+                       i += 3;
+               }
+
+               if (labels >= 2) {
+                       key = jhash_2words(nexthop->nh_label->label[i],
+                                          nexthop->nh_label->label[i + 1],
+                                          key);
+                       labels -= 2;
+                       i += 2;
+               }
+
+               if (labels >= 1)
+                       key = jhash_1word(nexthop->nh_label->label[i], key);
+       }
+
+       switch (nexthop->type) {
+       case NEXTHOP_TYPE_IPV4_IFINDEX:
+       case NEXTHOP_TYPE_IPV6_IFINDEX:
+       case NEXTHOP_TYPE_IFINDEX:
+               key = jhash_1word(nexthop->ifindex, key);
+               break;
+       case NEXTHOP_TYPE_BLACKHOLE:
+       case NEXTHOP_TYPE_IPV4:
+       case NEXTHOP_TYPE_IPV6:
+               break;
+       }
        return key;
 }

diff --git a/lib/nexthop.h b/lib/nexthop.h
index 9cdb040fc4dd18fecd215ed66aa40780ffdd2a57..24b0953191efb74071c4a8e91f6f81ed87be8bfe 100644 (file)
--- a/lib/nexthop.h
+++ b/lib/nexthop.h
@@ -136,7 +136,7 @@ void nexthop_del_labels(struct nexthop *);
  * Returns:
  *    32-bit hash of nexthop
  */
-uint32_t nexthop_hash(struct nexthop *nexthop);
+uint32_t nexthop_hash(const struct nexthop *nexthop);
 
 extern bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2);
 

diff --git a/lib/nexthop_group.c b/lib/nexthop_group.c
index 5fb4ea5234f0f489f32178e4ed72dcf41f07b6d4..fa89b7708c632d9d66b78bedbec495a27f920bce 100644 (file)
--- a/lib/nexthop_group.c
+++ b/lib/nexthop_group.c
@@ -25,6 +25,7 @@
 #include <nexthop_group.h>
 #include <vty.h>
 #include <command.h>
+#include <jhash.h>
 
 #ifndef VTYSH_EXTRACT_PL
 #include "lib/nexthop_group_clippy.c"
@@ -147,6 +148,21 @@ void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh,
        }
 }
 
+uint32_t nexthop_group_hash(const struct nexthop_group *nhg)
+{
+       struct nexthop *nh;
+       uint32_t key = 0;
+
+       /*
+        * We are not interested in hashing over any recursively
+        * resolved nexthops
+        */
+       for (nh = nhg->nexthop; nh; nh = nh->next)
+               key = jhash_1word(nexthop_hash(nh), key);
+
+       return key;
+}
+
 static void nhgc_delete_nexthops(struct nexthop_group_cmd *nhgc)
 {
        struct nexthop *nexthop;

diff --git a/lib/nexthop_group.h b/lib/nexthop_group.h
index d96d0ab9f5d2f55c6008a2413f84f94c81cf9731..f68033c20c90d3092cff63f31f88517fa98143ce 100644 (file)
--- a/lib/nexthop_group.h
+++ b/lib/nexthop_group.h
@@ -47,6 +47,8 @@ void nexthop_del(struct nexthop_group *nhg, struct nexthop *nexthop);
 void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh,
                   struct nexthop *rparent);
 
+uint32_t nexthop_group_hash(const struct nexthop_group *nhg);
+
 /* The following for loop allows to iterate over the nexthop
  * structure of routes.
  *