zebra: Add hash of nexthop groups

This commit does nothing more than just create a hash structure
that we will use to track nexthop groups.

Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>

4 files changed, 109 insertions, 0 deletions

diff --git a/zebra/zebra_nhg.c b/zebra/zebra_nhg.c
index 4e696b39a..b3fc46a66 100644
--- a/zebra/zebra_nhg.c
+++ b/zebra/zebra_nhg.c
@@ -26,6 +26,7 @@
 #include "lib/nexthop_group_private.h"
 #include "lib/routemap.h"
 #include "lib/mpls.h"
+#include "lib/jhash.h"
 
 #include "zebra/connected.h"
 #include "zebra/debug.h"
@@ -558,3 +559,83 @@ int nexthop_active_update(struct route_node *rn, struct route_entry *re)
 	return re->nexthop_active_num;
 }
 
+static uint32_t zebra_nhg_hash_key_nexthop_group(struct nexthop_group *nhg)
+{
+	struct nexthop *nh;
+	uint32_t i;
+	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_2words(nh->vrf_id, nh->nh_label_type, key);
+		/* gate and blackhole are together in a union */
+		key = jhash(&nh->gate, sizeof(nh->gate), key);
+		key = jhash(&nh->src, sizeof(nh->src), key);
+		key = jhash(&nh->rmap_src, sizeof(nh->rmap_src), key);
+		if (nh->nh_label) {
+			for (i = 0; i < nh->nh_label->num_labels; i++)
+				key = jhash_1word(nh->nh_label->label[i], key);
+		}
+		switch (nh->type) {
+		case NEXTHOP_TYPE_IPV4_IFINDEX:
+		case NEXTHOP_TYPE_IPV6_IFINDEX:
+		case NEXTHOP_TYPE_IFINDEX:
+			key = jhash_1word(nh->ifindex, key);
+			break;
+		case NEXTHOP_TYPE_BLACKHOLE:
+		case NEXTHOP_TYPE_IPV4:
+		case NEXTHOP_TYPE_IPV6:
+			break;
+		}
+	}
+	return key;
+}
+
+uint32_t zebra_nhg_hash_key(const void *arg)
+{
+	const struct nhg_hash_entry *nhe = arg;
+	int key = 0x5a351234;
+
+	key = jhash_2words(nhe->vrf_id, nhe->afi, key);
+
+	return jhash_1word(zebra_nhg_hash_key_nexthop_group(&nhe->nhg), key);
+}
+
+bool zebra_nhg_hash_equal(const void *arg1, const void *arg2)
+{
+	const struct nhg_hash_entry *nhe1 = arg1;
+	const struct nhg_hash_entry *nhe2 = arg2;
+	struct nexthop *nh1, *nh2;
+	uint32_t nh_count = 0;
+
+	if (nhe1->vrf_id != nhe2->vrf_id)
+		return false;
+
+	if (nhe1->afi != nhe2->afi)
+		return false;
+
+	/*
+	 * Again we are not interested in looking at any recursively
+	 * resolved nexthops.  Top level only
+	 */
+	for (nh1 = nhe1->nhg.nexthop; nh1; nh1 = nh1->next) {
+		uint32_t inner_nh_count = 0;
+		for (nh2 = nhe2->nhg.nexthop; nh2; nh2 = nh2->next) {
+			if (inner_nh_count == nh_count) {
+				break;
+			}
+			inner_nh_count++;
+		}
+
+		if (!nexthop_same(nh1, nh2))
+			return false;
+
+		nh_count++;
+	}
+
+	return true;
+}
+
diff --git a/zebra/zebra_nhg.h b/zebra/zebra_nhg.h
index ff2351c75..58f8e18b7 100644
--- a/zebra/zebra_nhg.h
+++ b/zebra/zebra_nhg.h
@@ -24,6 +24,25 @@
 #define __ZEBRA_NHG_H__
 
 #include "zebra/rib.h"
+#include "lib/nexthop_group.h"
 
 extern int nexthop_active_update(struct route_node *rn, struct route_entry *re);
+
+struct nhg_hash_entry {
+	afi_t afi;
+	vrf_id_t vrf_id;
+
+	struct nexthop_group nhg;
+
+	uint32_t refcnt;
+	uint32_t dplane_ref;
+};
+
+void zebra_nhg_init(void);
+void zebra_nhg_terminate(void);
+
+extern uint32_t zebra_nhg_hash_key(const void *arg);
+
+extern bool zebra_nhg_hash_equal(const void *arg1, const void *arg2);
+
 #endif
diff --git a/zebra/zebra_router.c b/zebra/zebra_router.c
index 1e9f9e4ec..ffffa8c00 100644
--- a/zebra/zebra_router.c
+++ b/zebra/zebra_router.c
@@ -253,4 +253,8 @@ void zebra_router_init(void)
 	zrouter.iptable_hash = hash_create_size(8, zebra_pbr_iptable_hash_key,
 						zebra_pbr_iptable_hash_equal,
 						"IPtable Hash Entry");
+
+	zrouter.nhgs =
+		hash_create_size(8, zebra_nhg_hash_key, zebra_nhg_hash_equal,
+				 "Zebra Router Nexthop Groups");
 }
diff --git a/zebra/zebra_router.h b/zebra/zebra_router.h
index 25a7adac1..4bae701d2 100644
--- a/zebra/zebra_router.h
+++ b/zebra/zebra_router.h
@@ -132,6 +132,11 @@ struct zebra_router {
 	 * Time for when we sweep the rib from old routes
 	 */
 	time_t startup_time;
+
+	/*
+	 * The hash of nexthop groups associated with this router
+	 */
+	struct hash *nhgs;
 };
 
 #define GRACEFUL_RESTART_TIME 60