bgpd: add the bgp_label_per_nexthop_cache struct and apis

This commit introduces the necessary structs and apis to
create the cache entries that store the label information
associated to a given nexthop.

A hash table is created in each BGP instance for all the
AFIs: IPv4 and IPv6. That hash table is initialised.
An API to look and/or create an entry based on a given
nexthop.

Signed-off-by: Philippe Guibert <philippe.guibert@6wind.com>

4 files changed, 107 insertions, 0 deletions

diff --git a/bgpd/bgp_labelpool.c b/bgpd/bgp_labelpool.c
index 3e43a41da..4d7019993 100644
--- a/bgpd/bgp_labelpool.c
+++ b/bgpd/bgp_labelpool.c
@@ -23,6 +23,7 @@
 #include "bgpd/bgp_debug.h"
 #include "bgpd/bgp_errors.h"
 #include "bgpd/bgp_route.h"
+#include "bgpd/bgp_zebra.h"
 
 #define BGP_LABELPOOL_ENABLE_TESTS 0
 
@@ -1558,3 +1559,57 @@ void bgp_lp_vty_init(void)
 	install_element(ENABLE_NODE, &clear_labelpool_perf_test_cmd);
 #endif /* BGP_LABELPOOL_ENABLE_TESTS */
 }
+
+DEFINE_MTYPE_STATIC(BGPD, LABEL_PER_NEXTHOP_CACHE,
+		    "BGP Label Per Nexthop entry");
+
+/* The nexthops values are compared to
+ * find in the tree the appropriate cache entry
+ */
+int bgp_label_per_nexthop_cache_cmp(const struct bgp_label_per_nexthop_cache *a,
+				    const struct bgp_label_per_nexthop_cache *b)
+{
+	return prefix_cmp(&a->nexthop, &b->nexthop);
+}
+
+struct bgp_label_per_nexthop_cache *
+bgp_label_per_nexthop_new(struct bgp_label_per_nexthop_cache_head *tree,
+			  struct prefix *nexthop)
+{
+	struct bgp_label_per_nexthop_cache *blnc;
+
+	blnc = XCALLOC(MTYPE_LABEL_PER_NEXTHOP_CACHE,
+		       sizeof(struct bgp_label_per_nexthop_cache));
+	blnc->tree = tree;
+	blnc->label = MPLS_INVALID_LABEL;
+	prefix_copy(&blnc->nexthop, nexthop);
+	LIST_INIT(&(blnc->paths));
+	bgp_label_per_nexthop_cache_add(tree, blnc);
+
+	return blnc;
+}
+
+struct bgp_label_per_nexthop_cache *
+bgp_label_per_nexthop_find(struct bgp_label_per_nexthop_cache_head *tree,
+			   struct prefix *nexthop)
+{
+	struct bgp_label_per_nexthop_cache blnc = {};
+
+	if (!tree)
+		return NULL;
+
+	memcpy(&blnc.nexthop, nexthop, sizeof(struct prefix));
+	return bgp_label_per_nexthop_cache_find(tree, &blnc);
+}
+
+void bgp_label_per_nexthop_free(struct bgp_label_per_nexthop_cache *blnc)
+{
+	if (blnc->label != MPLS_INVALID_LABEL) {
+		bgp_zebra_send_nexthop_label(ZEBRA_MPLS_LABELS_DELETE,
+					     blnc->label, ZEBRA_LSP_BGP,
+					     &blnc->nexthop);
+		bgp_lp_release(LP_TYPE_NEXTHOP, blnc, blnc->label);
+	}
+	bgp_label_per_nexthop_cache_del(blnc->tree, blnc);
+	XFREE(MTYPE_LABEL_PER_NEXTHOP_CACHE, blnc);
+}
diff --git a/bgpd/bgp_labelpool.h b/bgpd/bgp_labelpool.h
index 182aacec7..fd3656068 100644
--- a/bgpd/bgp_labelpool.h
+++ b/bgpd/bgp_labelpool.h
@@ -42,4 +42,47 @@ extern void bgp_lp_event_zebra_down(void);
 extern void bgp_lp_event_zebra_up(void);
 extern void bgp_lp_vty_init(void);
 
+struct bgp_label_per_nexthop_cache;
+PREDECL_RBTREE_UNIQ(bgp_label_per_nexthop_cache);
+
+extern int
+bgp_label_per_nexthop_cache_cmp(const struct bgp_label_per_nexthop_cache *a,
+				const struct bgp_label_per_nexthop_cache *b);
+
+struct bgp_label_per_nexthop_cache {
+
+	/* RB-tree entry. */
+	struct bgp_label_per_nexthop_cache_item entry;
+
+	/* the nexthop is the key of the list */
+	struct prefix nexthop;
+
+	/* calculated label */
+	mpls_label_t label;
+
+	/* number of path_vrfs */
+	unsigned int path_count;
+
+	/* back pointer to bgp instance */
+	struct bgp *to_bgp;
+
+	/* list of path_vrfs using it */
+	LIST_HEAD(path_lists, bgp_path_info) paths;
+
+	/* Back pointer to the cache tree this entry belongs to. */
+	struct bgp_label_per_nexthop_cache_head *tree;
+};
+
+DECLARE_RBTREE_UNIQ(bgp_label_per_nexthop_cache,
+		    struct bgp_label_per_nexthop_cache, entry,
+		    bgp_label_per_nexthop_cache_cmp);
+
+void bgp_label_per_nexthop_free(struct bgp_label_per_nexthop_cache *blnc);
+
+struct bgp_label_per_nexthop_cache *
+bgp_label_per_nexthop_new(struct bgp_label_per_nexthop_cache_head *tree,
+			  struct prefix *nexthop);
+struct bgp_label_per_nexthop_cache *
+bgp_label_per_nexthop_find(struct bgp_label_per_nexthop_cache_head *tree,
+			   struct prefix *nexthop);
 #endif /* _FRR_BGP_LABELPOOL_H */
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index 96c6a111c..5a46b4f3c 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -3352,6 +3352,11 @@ static struct bgp *bgp_create(as_t *as, const char *name,
 		SET_FLAG(bgp->af_flags[afi][SAFI_MPLS_VPN],
 			 BGP_VPNVX_RETAIN_ROUTE_TARGET_ALL);
 	}
+
+	for (afi = AFI_IP; afi < AFI_MAX; afi++)
+		bgp_label_per_nexthop_cache_init(
+			&bgp->mpls_labels_per_nexthop[afi]);
+
 	if (name)
 		bgp->name = XSTRDUP(MTYPE_BGP, name);
 
diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h
index 1be2cac0a..c59ab43c0 100644
--- a/bgpd/bgpd.h
+++ b/bgpd/bgpd.h
@@ -569,6 +569,10 @@ struct bgp {
 	/* Allocate MPLS labels */
 	uint8_t allocate_mpls_labels[AFI_MAX][SAFI_MAX];
 
+	/* Tree for next-hop lookup cache. */
+	struct bgp_label_per_nexthop_cache_head
+		mpls_labels_per_nexthop[AFI_MAX];
+
 	/* Allocate hash entries to store policy routing information
 	 * The hash are used to host pbr rules somewhere.
 	 * Actually, pbr will only be used by flowspec