bgpd: add mpls vpn nh label bind cache struct and apis

In the context of the ASBR facing an EBGP neighbor, or
facing an IBGP neighbor where the BGP updates received
are re-advertised with a modified next-hop, a new local
label will be re-advertised too, to replace the original
one.

Create a binding table, in the form of a hash list, from the
original labels to the new labels. Since labels can be the
same on several routers, set the next-hop and the label as
the keys. Add the needed API functions to manage the hash
list.

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

4 files changed, 125 insertions, 0 deletions

diff --git a/bgpd/bgp_mplsvpn.c b/bgpd/bgp_mplsvpn.c
index 6b93737282..0ac76c48b4 100644
--- a/bgpd/bgp_mplsvpn.c
+++ b/bgpd/bgp_mplsvpn.c
@@ -39,6 +39,9 @@
 #include "bgpd/rfapi/rfapi_backend.h"
 #endif
 
+DEFINE_MTYPE_STATIC(BGPD, MPLSVPN_NH_LABEL_BIND_CACHE,
+		    "BGP MPLSVPN nexthop label bind cache");
+
 /*
  * Definitions and external declarations.
  */
@@ -3860,3 +3863,61 @@ void bgp_vpn_leak_export(struct bgp *from_bgp)
 		}
 	}
 }
+
+/* The nexthops values are compared to
+ * find in the tree the appropriate cache entry
+ */
+int bgp_mplsvpn_nh_label_bind_cmp(
+	const struct bgp_mplsvpn_nh_label_bind_cache *a,
+	const struct bgp_mplsvpn_nh_label_bind_cache *b)
+{
+	if (prefix_cmp(&a->nexthop, &b->nexthop))
+		return 1;
+	if (a->orig_label > b->orig_label)
+		return 1;
+	if (a->orig_label < b->orig_label)
+		return -1;
+	return 0;
+}
+
+void bgp_mplsvpn_nh_label_bind_free(
+	struct bgp_mplsvpn_nh_label_bind_cache *bmnc)
+{
+	if (bmnc->new_label != MPLS_INVALID_LABEL)
+		bgp_lp_release(LP_TYPE_BGP_L3VPN_BIND, bmnc, bmnc->new_label);
+	bgp_mplsvpn_nh_label_bind_cache_del(
+		&bmnc->bgp_vpn->mplsvpn_nh_label_bind, bmnc);
+	XFREE(MTYPE_MPLSVPN_NH_LABEL_BIND_CACHE, bmnc);
+}
+
+struct bgp_mplsvpn_nh_label_bind_cache *
+bgp_mplsvpn_nh_label_bind_new(struct bgp_mplsvpn_nh_label_bind_cache_head *tree,
+			      struct prefix *p, mpls_label_t orig_label)
+{
+	struct bgp_mplsvpn_nh_label_bind_cache *bmnc;
+
+	bmnc = XCALLOC(MTYPE_MPLSVPN_NH_LABEL_BIND_CACHE,
+		       sizeof(struct bgp_mplsvpn_nh_label_bind_cache));
+	bmnc->new_label = MPLS_INVALID_LABEL;
+	prefix_copy(&bmnc->nexthop, p);
+	bmnc->orig_label = orig_label;
+
+	LIST_INIT(&(bmnc->paths));
+	bgp_mplsvpn_nh_label_bind_cache_add(tree, bmnc);
+
+	return bmnc;
+}
+
+struct bgp_mplsvpn_nh_label_bind_cache *bgp_mplsvpn_nh_label_bind_find(
+	struct bgp_mplsvpn_nh_label_bind_cache_head *tree, struct prefix *p,
+	mpls_label_t orig_label)
+{
+	struct bgp_mplsvpn_nh_label_bind_cache bmnc = {0};
+
+	if (!tree)
+		return NULL;
+	prefix_copy(&bmnc.nexthop, p);
+	bmnc.orig_label = orig_label;
+
+	return bgp_mplsvpn_nh_label_bind_cache_find(tree, &bmnc);
+}
diff --git a/bgpd/bgp_mplsvpn.h b/bgpd/bgp_mplsvpn.h
index 75758edcc2..5fe64ade48 100644
--- a/bgpd/bgp_mplsvpn.h
+++ b/bgpd/bgp_mplsvpn.h
@@ -325,4 +325,60 @@ extern void vpn_handle_router_id_update(struct bgp *bgp, bool withdraw,
 extern void bgp_vpn_leak_unimport(struct bgp *from_bgp);
 extern void bgp_vpn_leak_export(struct bgp *from_bgp);
 
+extern int
+bgp_mplsvpn_nh_label_bind_cmp(const struct bgp_mplsvpn_nh_label_bind_cache *a,
+			      const struct bgp_mplsvpn_nh_label_bind_cache *b);
+
+/* used to bind a local label to the (label, nexthop) values
+ * from an incoming BGP mplsvpn update
+ */
+struct bgp_mplsvpn_nh_label_bind_cache {
+
+	/* RB-tree entry. */
+	struct bgp_mplsvpn_nh_label_bind_cache_item entry;
+
+	/* The nexthop and the vpn label are the key of the list.
+	 * Only received BGP MPLSVPN updates may use that structure.
+	 * orig_label is the original label received from the BGP Update.
+	 */
+	struct prefix nexthop;
+	mpls_label_t orig_label;
+
+	/* number of mplsvpn path */
+	unsigned int path_count;
+
+	/* back pointer to bgp instance */
+	struct bgp *bgp_vpn;
+
+	/* MPLS label allocated value.
+	 * When the next-hop is changed because of 'next-hop-self' or
+	 * because it is an eBGP peer, the redistributed orig_label value
+	 * is unmodified, unless the 'l3vpn-multi-domain-switching'
+	 * is enabled: a new_label value is allocated:
+	 * - The new_label value is sent in the advertised BGP update,
+	 * instead of the label value.
+	 * - An MPLS entry is set to swap <new_label> with <orig_label>.
+	 */
+	mpls_label_t new_label;
+
+	/* list of path_vrfs using it */
+	LIST_HEAD(mplsvpn_nh_label_bind_path_lists, bgp_path_info) paths;
+
+	time_t last_update;
+};
+
+DECLARE_RBTREE_UNIQ(bgp_mplsvpn_nh_label_bind_cache,
+		    struct bgp_mplsvpn_nh_label_bind_cache, entry,
+		    bgp_mplsvpn_nh_label_bind_cmp);
+
+void bgp_mplsvpn_nh_label_bind_free(
+	struct bgp_mplsvpn_nh_label_bind_cache *bmnc);
+
+struct bgp_mplsvpn_nh_label_bind_cache *
+bgp_mplsvpn_nh_label_bind_new(struct bgp_mplsvpn_nh_label_bind_cache_head *tree,
+			      struct prefix *p, mpls_label_t orig_label);
+struct bgp_mplsvpn_nh_label_bind_cache *bgp_mplsvpn_nh_label_bind_find(
+	struct bgp_mplsvpn_nh_label_bind_cache_head *tree, struct prefix *p,
+	mpls_label_t orig_label);
+
 #endif /* _QUAGGA_BGP_MPLSVPN_H */
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index ba2985d304..22f48114d4 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -3361,6 +3361,8 @@ static struct bgp *bgp_create(as_t *as, const char *name,
 		bgp_label_per_nexthop_cache_init(
 			&bgp->mpls_labels_per_nexthop[afi]);
 
+	bgp_mplsvpn_nh_label_bind_cache_init(&bgp->mplsvpn_nh_label_bind);
+
 	if (name)
 		bgp->name = XSTRDUP(MTYPE_BGP, name);
 
diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h
index 0eb58773d0..d7caf840fd 100644
--- a/bgpd/bgpd.h
+++ b/bgpd/bgpd.h
@@ -331,6 +331,9 @@ struct as_confed {
 	char *as_pretty;
 };
 
+struct bgp_mplsvpn_nh_label_bind_cache;
+PREDECL_RBTREE_UNIQ(bgp_mplsvpn_nh_label_bind_cache);
+
 /* BGP instance structure.  */
 struct bgp {
 	/* AS number of this BGP instance.  */
@@ -578,6 +581,9 @@ struct bgp {
 	struct bgp_label_per_nexthop_cache_head
 		mpls_labels_per_nexthop[AFI_MAX];
 
+	/* Tree for mplsvpn next-hop label bind cache */
+	struct bgp_mplsvpn_nh_label_bind_cache_head mplsvpn_nh_label_bind;
+
 	/* 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