isisd: detect Prefix-SID collisions and handle them appropriately

isisd relies on its YANG module to prevent the same SID index
from being configured multiple times for different prefixes. It's
possible, however, to have different routers assigning the same SID
index for different prefixes. When that happens, we say we have a
Prefix-SID collision, which is ultimately a misconfiguration issue.

The problem with Prefix-SID collisions is that the Prefix-SID that
is processed later overwrites the previous ones. Then, once the
Prefix-SID collision is fixed in the configuration, the overwritten
Prefix-SID isn't reinstalled since it's already marked as installed
and it didn't change. To prevent such inconsistency from happening,
add a safeguard in the SPF code to detect Prefix-SID collisions and
handle them appropriately (i.e. log a warning + ignore the Prefix-SID
Sub-TLV since it's already in use by another prefix). That way,
once the configuration is fixed, no Prefix-SID label entry will be
missing in the LFIB.

Reported-by: Emanuele Di Pascale <emanuele@voltanet.io>
Signed-off-by: Renato Westphal <renato@opensourcerouting.org>

6 files changed, 127 insertions, 7 deletions

diff --git a/isisd/isis_errors.c b/isisd/isis_errors.c
index 7530d0b96..1d277ac5f 100644
--- a/isisd/isis_errors.c
+++ b/isisd/isis_errors.c
@@ -44,6 +44,12 @@ static struct log_ref ferr_isis_err[] = {
 		.suggestion = "Configure a larger SRGB"
 	},
 	{
+		.code = EC_ISIS_SID_COLLISION,
+		.title = "SID collision",
+		.description = "Isis has detected that two different prefixes share the same SID index",
+		.suggestion = "Identify the routers that are advertising the same SID index and fix the collision accordingly"
+	},
+	{
 		.code = END_FERR,
 	}
 };
diff --git a/isisd/isis_errors.h b/isisd/isis_errors.h
index d5674dbf3..6f3e5f85c 100644
--- a/isisd/isis_errors.h
+++ b/isisd/isis_errors.h
@@ -27,6 +27,7 @@ enum isis_log_refs {
 	EC_ISIS_PACKET = ISIS_FERR_START,
 	EC_ISIS_CONFIG,
 	EC_ISIS_SID_OVERFLOW,
+	EC_ISIS_SID_COLLISION,
 };
 
 extern void isis_error_init(void);
diff --git a/isisd/isis_nb_config.c b/isisd/isis_nb_config.c
index 6cb7d32c2..c1cb2ecee 100644
--- a/isisd/isis_nb_config.c
+++ b/isisd/isis_nb_config.c
@@ -22,6 +22,7 @@
 
 #include <zebra.h>
 
+#include "printfrr.h"
 #include "northbound.h"
 #include "linklist.h"
 #include "log.h"
@@ -1739,12 +1740,17 @@ int isis_instance_segment_routing_prefix_sid_map_prefix_sid_destroy(
 int isis_instance_segment_routing_prefix_sid_map_prefix_sid_pre_validate(
 	struct nb_cb_pre_validate_args *args)
 {
+	const struct lyd_node *area_dnode;
+	struct isis_area *area;
+	struct prefix prefix;
 	uint32_t srgb_lbound;
 	uint32_t srgb_ubound;
 	uint32_t srgb_range;
 	uint32_t sid;
 	enum sr_sid_value_type sid_type;
+	struct isis_prefix_sid psid = {};
 
+	yang_dnode_get_prefix(&prefix, args->dnode, "./prefix");
 	srgb_lbound = yang_dnode_get_uint32(args->dnode,
 					    "../../srgb/lower-bound");
 	srgb_ubound = yang_dnode_get_uint32(args->dnode,
@@ -1752,7 +1758,9 @@ int isis_instance_segment_routing_prefix_sid_map_prefix_sid_pre_validate(
 	sid = yang_dnode_get_uint32(args->dnode, "./sid-value");
 	sid_type = yang_dnode_get_enum(args->dnode, "./sid-value-type");
 
+	/* Check for invalid indexes/labels. */
 	srgb_range = srgb_ubound - srgb_lbound + 1;
+	psid.value = sid;
 	switch (sid_type) {
 	case SR_SID_VALUE_TYPE_INDEX:
 		if (sid >= srgb_range) {
@@ -1766,9 +1774,49 @@ int isis_instance_segment_routing_prefix_sid_map_prefix_sid_pre_validate(
 			zlog_warn("Invalid absolute SID %u", sid);
 			return NB_ERR_VALIDATION;
 		}
+		SET_FLAG(psid.flags, ISIS_PREFIX_SID_VALUE);
+		SET_FLAG(psid.flags, ISIS_PREFIX_SID_LOCAL);
 		break;
 	}
 
+	/* Check for Prefix-SID collisions. */
+	area_dnode = yang_dnode_get_parent(args->dnode, "instance");
+	area = nb_running_get_entry(area_dnode, NULL, false);
+	if (area) {
+		for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
+			for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2;
+			     level++) {
+				struct isis_spftree *spftree;
+				struct isis_vertex *vertex_psid;
+
+				if (!(area->is_type & level))
+					continue;
+				spftree = area->spftree[tree][level - 1];
+				if (!spftree)
+					continue;
+
+				vertex_psid = isis_spf_prefix_sid_lookup(
+					spftree, &psid);
+				if (vertex_psid
+				    && !prefix_same(&vertex_psid->N.ip.p.dest,
+						    &prefix)) {
+					snprintfrr(
+						args->errmsg, args->errmsg_len,
+						"Prefix-SID collision detected, SID %s %u is already in use by prefix %pFX (L%u)",
+						CHECK_FLAG(
+							psid.flags,
+							ISIS_PREFIX_SID_VALUE)
+							? "label"
+							: "index",
+						psid.value,
+						&vertex_psid->N.ip.p.dest,
+						level);
+					return NB_ERR_VALIDATION;
+				}
+			}
+		}
+	}
+
 	return NB_OK;
 }
 
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 690ea9f1a..5480a1b33 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -33,11 +33,13 @@
 #include "memory.h"
 #include "prefix.h"
 #include "if.h"
+#include "hash.h"
 #include "table.h"
 #include "spf_backoff.h"
 #include "srcdest_table.h"
 #include "vrf.h"
 
+#include "isis_errors.h"
 #include "isis_constants.h"
 #include "isis_common.h"
 #include "isis_flags.h"
@@ -184,6 +186,36 @@ const char *vid2string(const struct isis_vertex *vertex, char *buff, int size)
 	return "UNKNOWN";
 }
 
+static bool prefix_sid_cmp(const void *value1, const void *value2)
+{
+	const struct isis_vertex *c1 = value1;
+	const struct isis_vertex *c2 = value2;
+
+	if (CHECK_FLAG(c1->N.ip.sr.sid.flags,
+		       ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL)
+	    != CHECK_FLAG(c2->N.ip.sr.sid.flags,
+			  ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL))
+		return false;
+
+	return c1->N.ip.sr.sid.value == c2->N.ip.sr.sid.value;
+}
+
+static unsigned int prefix_sid_key_make(const void *value)
+{
+	const struct isis_vertex *vertex = value;
+
+	return jhash_1word(vertex->N.ip.sr.sid.value, 0);
+}
+
+struct isis_vertex *isis_spf_prefix_sid_lookup(struct isis_spftree *spftree,
+					       struct isis_prefix_sid *psid)
+{
+	struct isis_vertex lookup = {};
+
+	lookup.N.ip.sr.sid = *psid;
+	return hash_lookup(spftree->prefix_sids, &lookup);
+}
+
 static void isis_vertex_adj_free(void *arg)
 {
 	struct isis_vertex_adj *vadj = arg;
@@ -310,6 +342,8 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area,
 	tree->route_table_backup->cleanup = isis_route_node_cleanup;
 	tree->area = area;
 	tree->lspdb = lspdb;
+	tree->prefix_sids = hash_create(prefix_sid_key_make, prefix_sid_cmp,
+					"SR Prefix-SID Entries");
 	tree->sadj_list = list_new();
 	tree->sadj_list->del = isis_spf_adj_free;
 	tree->last_run_timestamp = 0;
@@ -332,6 +366,8 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area,
 
 void isis_spftree_del(struct isis_spftree *spftree)
 {
+	hash_clean(spftree->prefix_sids, NULL);
+	hash_free(spftree->prefix_sids);
 	if (spftree->type == SPF_TYPE_TI_LFA) {
 		isis_spf_node_list_clear(&spftree->lfa.q_space);
 		isis_spf_node_list_clear(&spftree->lfa.p_space);
@@ -515,14 +551,39 @@ isis_spf_add2tent(struct isis_spftree *spftree, enum vertextype vtype, void *id,
 	vertex->d_N = cost;
 	vertex->depth = depth;
 	if (VTYPE_IP(vtype) && psid) {
-		bool local;
+		struct isis_area *area = spftree->area;
+		struct isis_vertex *vertex_psid;
 
-		local = (vertex->depth == 1);
-		vertex->N.ip.sr.sid = *psid;
-		vertex->N.ip.sr.label =
-			sr_prefix_in_label(spftree->area, psid, local);
-		if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL)
-			vertex->N.ip.sr.present = true;
+		/*
+		 * Check if the Prefix-SID is already in use by another prefix.
+		 */
+		vertex_psid = isis_spf_prefix_sid_lookup(spftree, psid);
+		if (vertex_psid
+		    && !prefix_same(&vertex_psid->N.ip.p.dest,
+				    &vertex->N.ip.p.dest)) {
+			flog_warn(
+				EC_ISIS_SID_COLLISION,
+				"ISIS-Sr (%s): collision detected, prefixes %pFX and %pFX share the same SID %s (%u)",
+				area->area_tag, &vertex->N.ip.p.dest,
+				&vertex_psid->N.ip.p.dest,
+				CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_VALUE)
+					? "label"
+					: "index",
+				psid->value);
+			psid = NULL;
+		} else {
+			bool local;
+
+			local = (vertex->depth == 1);
+			vertex->N.ip.sr.sid = *psid;
+			vertex->N.ip.sr.label =
+				sr_prefix_in_label(area, psid, local);
+			if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL)
+				vertex->N.ip.sr.present = true;
+
+			hash_get(spftree->prefix_sids, vertex,
+				 hash_alloc_intern);
+		}
 	}
 
 	if (parent) {
@@ -1352,6 +1413,7 @@ static void add_to_paths(struct isis_spftree *spftree,
 static void init_spt(struct isis_spftree *spftree, int mtid)
 {
 	/* Clear data from previous run. */
+	hash_clean(spftree->prefix_sids, NULL);
 	isis_spf_node_list_clear(&spftree->adj_nodes);
 	list_delete_all_node(spftree->sadj_list);
 	isis_vertex_queue_clear(&spftree->tents);
diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h
index 15d3ff927..a9a14fc75 100644
--- a/isisd/isis_spf.h
+++ b/isisd/isis_spf.h
@@ -53,6 +53,8 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area,
 				      const uint8_t *sysid, int level,
 				      enum spf_tree_id tree_id,
 				      enum spf_type type, uint8_t flags);
+struct isis_vertex *isis_spf_prefix_sid_lookup(struct isis_spftree *spftree,
+					       struct isis_prefix_sid *psid);
 void isis_spf_invalidate_routes(struct isis_spftree *tree);
 void isis_spf_verify_routes(struct isis_area *area,
 			    struct isis_spftree **trees);
diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h
index e999f9653..9cb1a39b8 100644
--- a/isisd/isis_spf_private.h
+++ b/isisd/isis_spf_private.h
@@ -313,6 +313,7 @@ struct isis_spftree {
 	struct route_table *route_table;
 	struct route_table *route_table_backup;
 	struct lspdb_head *lspdb; /* link-state db */
+	struct hash *prefix_sids; /* SR Prefix-SIDs. */
 	struct list *sadj_list;
 	struct isis_spf_nodes adj_nodes;
 	struct isis_area *area;    /* back pointer to area */