isisd: Add Segment Routing Local Block support

Segment Routing Local Block (SRLB) is part of RFC8667. This change introduces
the possibility for isisd to advertize SRLB in LSP. Base and Range of SRLB
could be configured through CLI or Yang.

Adjacency-SID are now using this SRLB for label allocation. SRLB could also
be used for SID-Binding (e.g. LDP to SR).

Signed-off-by: Olivier Dugeon <olivier.dugeon@orange.com>

1 files changed, 293 insertions, 20 deletions

diff --git a/isisd/isis_sr.c b/isisd/isis_sr.c
index c24c0608b..32de71cca 100644
--- a/isisd/isis_sr.c
+++ b/isisd/isis_sr.c
@@ -52,6 +52,10 @@ DEFINE_MTYPE_STATIC(ISISD, ISIS_SR_INFO, "ISIS segment routing information")
 
 static void sr_prefix_uninstall(struct sr_prefix *srp);
 static void sr_prefix_reinstall(struct sr_prefix *srp, bool make_before_break);
+static void sr_local_block_delete(struct isis_area *area);
+static int sr_local_block_init(struct isis_area *area);
+static void sr_adj_sid_update(struct sr_adjacency *sra,
+			      struct sr_local_block *srlb);
 
 /* --- RB-Tree Management functions ----------------------------------------- */
 
@@ -135,7 +139,8 @@ int isis_sr_cfg_srgb_update(struct isis_area *area, uint32_t lower_bound,
 {
 	struct isis_sr_db *srdb = &area->srdb;
 
-	sr_debug("ISIS-Sr (%s): Update SRGB", area->area_tag);
+	sr_debug("ISIS-Sr (%s): Update SRGB with new range [%u/%u]",
+		 area->area_tag, lower_bound, upper_bound);
 
 	/* First release the old SRGB. */
 	if (srdb->config.enabled)
@@ -148,14 +153,14 @@ int isis_sr_cfg_srgb_update(struct isis_area *area, uint32_t lower_bound,
 	if (srdb->enabled) {
 		struct sr_prefix *srp;
 
-		/* Request new SRGB if SR is enabled. */
+		/* then request new SRGB if SR is enabled. */
 		if (isis_zebra_request_label_range(
 			    srdb->config.srgb_lower_bound,
 			    srdb->config.srgb_upper_bound
 				    - srdb->config.srgb_lower_bound + 1))
 			return -1;
 
-		sr_debug("  |- Got new SRGB %u/%u",
+		sr_debug("  |- Got new SRGB [%u/%u]",
 			 srdb->config.srgb_lower_bound,
 			 srdb->config.srgb_upper_bound);
 
@@ -178,6 +183,54 @@ int isis_sr_cfg_srgb_update(struct isis_area *area, uint32_t lower_bound,
 }
 
 /**
+ * Update Segment Routing Local Block range which is reserved though the
+ * Label Manager. This function trigger the update of local Adjacency-SID
+ * installation.
+ *
+ * @param area		IS-IS area
+ * @param lower_bound	Lower bound of SRLB
+ * @param upper_bound	Upper bound of SRLB
+ *
+ * @return		0 on success, -1 otherwise
+ */
+int isis_sr_cfg_srlb_update(struct isis_area *area, uint32_t lower_bound,
+			    uint32_t upper_bound)
+{
+	struct isis_sr_db *srdb = &area->srdb;
+	struct listnode *node, *nnode;
+	struct sr_adjacency *sra;
+	int rc;
+
+	sr_debug("ISIS-Sr (%s): Update SRLB with new range [%u/%u]",
+		 area->area_tag, lower_bound, upper_bound);
+
+	/* First Delete SRLB */
+	sr_local_block_delete(area);
+
+	srdb->config.srlb_lower_bound = lower_bound;
+	srdb->config.srlb_upper_bound = upper_bound;
+
+	if (!srdb->enabled)
+		return 0;
+
+	/* Initialize new SRLB */
+	rc = sr_local_block_init(area);
+	if (rc !=0)
+		return rc;
+
+	/* Reinstall local Adjacency-SIDs with new labels. */
+	for (ALL_LIST_ELEMENTS(area->srdb.adj_sids, node, nnode, sra))
+		sr_adj_sid_update(sra, &srdb->srlb);
+
+	/* Update Router Capability */
+
+	/* Update and Flood LSP */
+	lsp_regenerate_schedule(area, area->is_type, 0);
+
+	return 0;
+}
+
+/**
  * Add new Prefix-SID configuration to the SRDB.
  *
  * @param area	  IS-IS area
@@ -404,15 +457,13 @@ static struct sr_prefix *sr_prefix_find_by_node(struct sr_node *srn,
  * @return	 New Segment Routing Node structure
  */
 static struct sr_node *sr_node_add(struct isis_area *area, int level,
-				   const uint8_t *sysid,
-				   const struct isis_router_cap *cap)
+				   const uint8_t *sysid)
 {
 	struct sr_node *srn;
 
 	srn = XCALLOC(MTYPE_ISIS_SR_INFO, sizeof(*srn));
 	srn->level = level;
 	memcpy(srn->sysid, sysid, ISIS_SYS_ID_LEN);
-	srn->cap = *cap;
 	srn->area = area;
 	srdb_node_prefix_init(&srn->prefix_sids);
 	srdb_node_add(&area->srdb.sr_nodes[level - 1], srn);
@@ -887,6 +938,26 @@ static inline void sr_prefix_reinstall(struct sr_prefix *srp,
 /* --- IS-IS LSP Parse functions -------------------------------------------- */
 
 /**
+ * Compare Router Capabilities. Only Flags, SRGB and Algorithm are used for the
+ * comparison. MSD and SRLB modification must not trigger and SR-Prefix update.
+ *
+ * @param r1	First Router Capabilities to compare
+ * @param r2	Second Router Capabilities to compare
+ * @return	0 if r1 and r2 are equal or -1 otherwise
+ */
+static int router_cap_cmp(const struct isis_router_cap *r1,
+			  const struct isis_router_cap *r2)
+{
+	if (r1->flags == r2->flags
+	    && r1->srgb.lower_bound == r2->srgb.lower_bound
+	    && r1->srgb.range_size == r2->srgb.range_size
+	    && r1->algo[0] == r2->algo[0])
+		return 0;
+	else
+		return -1;
+}
+
+/**
  * Parse all SR-related information from the given Router Capabilities TLV.
  *
  * @param area		IS-IS area
@@ -909,8 +980,7 @@ parse_router_cap_tlv(struct isis_area *area, int level, const uint8_t *sysid,
 
 	srn = sr_node_find(area, level, sysid);
 	if (srn) {
-		if (memcmp(&srn->cap, router_cap, sizeof(srn->cap)) != 0) {
-			srn->cap = *router_cap;
+		if (router_cap_cmp(&srn->cap, router_cap) != 0) {
 			srn->state = SRDB_STATE_MODIFIED;
 		} else
 			srn->state = SRDB_STATE_UNCHANGED;
@@ -919,10 +989,16 @@ parse_router_cap_tlv(struct isis_area *area, int level, const uint8_t *sysid,
 							   : "Unchanged",
 			 sysid_print(srn->sysid));
 	} else {
-		srn = sr_node_add(area, level, sysid, router_cap);
+		srn = sr_node_add(area, level, sysid);
 		srn->state = SRDB_STATE_NEW;
 	}
 
+	/*
+	 * Update Router Capabilities in any case as SRLB or MSD
+	 * modification are not take into account for comparison.
+	 */
+	srn->cap = *router_cap;
+
 	return srn;
 }
 
@@ -1242,6 +1318,150 @@ static int sr_route_update(struct isis_area *area, struct prefix *prefix,
 	return 0;
 }
 
+/* --- Segment Routing Local Block management functions --------------------- */
+
+/**
+ * Initialize Segment Routing Local Block from SRDB configuration and reserve
+ * block of bits to manage label allocation.
+ *
+ * @param area	IS-IS area
+ */
+static void sr_local_block_init(struct isis_area *area)
+{
+	struct isis_sr_db *srdb = &area->srdb;
+	struct sr_local_block *srlb = &srdb->srlb;
+
+	/*
+	 * Request SRLB to the label manager. If the allocation fails, return
+	 * an error to disable SR until a new SRLB is successfully allocated.
+	 */
+	if (isis_zebra_request_label_range(
+		    srdb->config.srlb_lower_bound,
+		    srdb->config.srlb_upper_bound
+			    - srdb->config.srlb_lower_bound + 1))
+		return;
+
+	sr_debug("ISIS-Sr (%s): Got new SRLB [%u/%u]", area->area_tag,
+		 srdb->config.srlb_lower_bound, srdb->config.srlb_upper_bound);
+
+	/* Initialize the SRLB */
+	srlb->start = srdb->config.srlb_lower_bound;
+	srlb->end = srdb->config.srlb_upper_bound;
+	srlb->current = 0;
+	/* Compute the needed Used Mark number and allocate them */
+	srlb->max_block = (srlb->end - srlb->start + 1) / SRLB_BLOCK_SIZE;
+	if (((srlb->end - srlb->start + 1) % SRLB_BLOCK_SIZE) != 0)
+		srlb->max_block++;
+	srlb->used_mark = XCALLOC(MTYPE_ISIS_SR_INFO,
+				  srlb->max_block * SRLB_BLOCK_SIZE);
+}
+
+/**
+ * Remove Segment Routing Local Block.
+ *
+ * @param area	IS-IS area
+ */
+static void sr_local_block_delete(struct isis_area *area)
+{
+	struct isis_sr_db *srdb = &area->srdb;
+	struct sr_local_block *srlb = &srdb->srlb;
+
+	sr_debug("ISIS-Sr (%s): Remove SRLB [%u/%u]", area->area_tag,
+		 srlb->start, srlb->end);
+
+	/* First release the label block */
+	isis_zebra_release_label_range(srdb->config.srlb_lower_bound,
+				       srdb->config.srlb_upper_bound);
+
+	/* Then reset SRLB structure */
+	if (srlb->used_mark != NULL)
+		XFREE(MTYPE_ISIS_SR_INFO, srlb->used_mark);
+	memset(srlb, 0, sizeof(struct sr_local_block));
+}
+
+/**
+ * Request a label from the Segment Routing Local Block.
+ *
+ * @param srlb	Segment Routing Local Block
+ *
+ * @return	First available label on success or MPLS_INVALID_LABEL if the
+ * 		block of labels is full
+ */
+static mpls_label_t sr_local_block_request_label(struct sr_local_block *srlb)
+{
+
+	mpls_label_t label;
+	uint32_t index;
+	uint32_t pos;
+
+	/* Check if we ran out of available labels */
+	if (srlb->current >= srlb->end)
+		return MPLS_INVALID_LABEL;
+
+	/* Get first available label and mark it used */
+	label = srlb->current + srlb->start;
+	index = srlb->current / SRLB_BLOCK_SIZE;
+	pos = 1ULL << (srlb->current % SRLB_BLOCK_SIZE);
+	srlb->used_mark[index] |= pos;
+
+	/* Jump to the next free position */
+	srlb->current++;
+	pos = srlb->current % SRLB_BLOCK_SIZE;
+	while (srlb->current < srlb->end) {
+		if (pos == 0)
+			index++;
+		if (!((1ULL << pos) & srlb->used_mark[index]))
+			break;
+		else {
+			srlb->current++;
+			pos = srlb->current % SRLB_BLOCK_SIZE;
+		}
+	}
+
+	return label;
+}
+
+/**
+ * Release label in the Segment Routing Local Block.
+ *
+ * @param srlb	Segment Routing Local Block
+ * @param label	Label to be release
+ *
+ * @return	0 on success or -1 if label falls outside SRLB
+ */
+static int sr_local_block_release_label(struct sr_local_block *srlb,
+					mpls_label_t label)
+{
+	uint32_t index;
+	uint32_t pos;
+
+	/* Check that label falls inside the SRLB */
+	if ((label < srlb->start) || (label > srlb->end)) {
+		flog_warn(EC_ISIS_SID_OVERFLOW,
+			"%s: Returning label %u is outside SRLB [%u/%u]",
+			__func__, label, srlb->start, srlb->end);
+		return -1;
+	}
+
+	index = (label - srlb->start) / SRLB_BLOCK_SIZE;
+	pos = 1ULL << ((label - srlb->start) % SRLB_BLOCK_SIZE);
+	srlb->used_mark[index] &= ~pos;
+	/* Reset current to the first available position */
+	for (index = 0; index < srlb->max_block; index++) {
+		if (srlb->used_mark[index] != 0xFFFFFFFFFFFFFFFF) {
+			for (pos = 0; pos < SRLB_BLOCK_SIZE; pos++)
+				if (!((1ULL << pos) & srlb->used_mark[index])) {
+					srlb->current =
+						index * SRLB_BLOCK_SIZE + pos;
+					break;
+				}
+			break;
+		}
+	}
+
+	return 0;
+}
+
 /* --- Segment Routing Adjacency-SID management functions ------------------- */
 
 /**
@@ -1293,7 +1513,11 @@ static void sr_adj_sid_add_single(struct isis_adjacency *adj, int family,
 	if (backup)
 		SET_FLAG(flags, EXT_SUBTLV_LINK_ADJ_SID_BFLG);
 
-	input_label = isis_zebra_request_dynamic_label();
+	/* Get a label from the SRLB for this Adjacency */
+	input_label = sr_local_block_request_label(&area->srdb.srlb);
+	if (input_label == MPLS_INVALID_LABEL)
+		return;
+
 	if (circuit->ext == NULL)
 		circuit->ext = isis_alloc_ext_subtlvs();
 
@@ -1351,6 +1575,36 @@ static void sr_adj_sid_add(struct isis_adjacency *adj, int family)
 	sr_adj_sid_add_single(adj, family, true);
 }
 
+static void sr_adj_sid_update(struct sr_adjacency *sra,
+			      struct sr_local_block *srlb)
+{
+	struct isis_circuit *circuit = sra->adj->circuit;
+
+	/* First remove the old MPLS Label */
+	isis_zebra_send_adjacency_sid(ZEBRA_MPLS_LABELS_DELETE, sra);
+
+	/* Got new label in the new SRLB */
+	sra->nexthop.label = sr_local_block_request_label(srlb);
+	if (sra->nexthop.label == MPLS_INVALID_LABEL)
+		return;
+
+	switch (circuit->circ_type) {
+	case CIRCUIT_T_BROADCAST:
+		sra->u.ladj_sid->sid = sra->nexthop.label;
+		break;
+	case CIRCUIT_T_P2P:
+		sra->u.adj_sid->sid = sra->nexthop.label;
+		break;
+	default:
+		flog_warn(EC_LIB_DEVELOPMENT, "%s: unexpected circuit type: %u",
+			  __func__, circuit->circ_type);
+		break;
+	}
+
+	/* Finally configure the new MPLS Label */
+	isis_zebra_send_adjacency_sid(ZEBRA_MPLS_LABELS_ADD, sra);
+}
+
 /**
  * Delete local Adj-SID.
  *
@@ -1368,11 +1622,13 @@ static void sr_adj_sid_del(struct sr_adjacency *sra)
 	/* Release dynamic label and remove subTLVs */
 	switch (circuit->circ_type) {
 	case CIRCUIT_T_BROADCAST:
-		isis_zebra_release_dynamic_label(sra->u.ladj_sid->sid);
+		sr_local_block_release_label(&area->srdb.srlb,
+					     sra->u.ladj_sid->sid);
 		isis_tlvs_del_lan_adj_sid(circuit->ext, sra->u.ladj_sid);
 		break;
 	case CIRCUIT_T_P2P:
-		isis_zebra_release_dynamic_label(sra->u.adj_sid->sid);
+		sr_local_block_release_label(&area->srdb.srlb,
+					     sra->u.adj_sid->sid);
 		isis_tlvs_del_adj_sid(circuit->ext, sra->u.adj_sid);
 		break;
 	default:
@@ -1730,7 +1986,7 @@ static void show_node(struct vty *vty, struct isis_area *area, int level)
 
 	/* Prepare table. */
 	tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
-	ttable_add_row(tt, "System ID|SRGB|Algorithm|MSD");
+	ttable_add_row(tt, "System ID|SRGB|SRLB|Algorithm|MSD");
 	tt->style.cell.rpad = 2;
 	tt->style.corner = '+';
 	ttable_restyle(tt);
@@ -1738,13 +1994,17 @@ static void show_node(struct vty *vty, struct isis_area *area, int level)
 
 	/* Process all SR-Node from the SRDB */
 	frr_each (srdb_node, &area->srdb.sr_nodes[level - 1], srn) {
-		ttable_add_row(tt, "%s|%u - %u|%s|%u", sysid_print(srn->sysid),
-			       srn->cap.srgb.lower_bound,
-			       srn->cap.srgb.lower_bound
-				       + srn->cap.srgb.range_size - 1,
-			       srn->cap.algo[0] == SR_ALGORITHM_SPF ? "SPF"
-								    : "S-SPF",
-			       srn->cap.msd);
+		ttable_add_row(
+			tt, "%s|%u - %u|%u - %u|%s|%u",
+			sysid_print(srn->sysid),
+			srn->cap.srgb.lower_bound,
+			srn->cap.srgb.lower_bound + srn->cap.srgb.range_size
+				- 1,
+			srn->cap.srlb.lower_bound,
+			srn->cap.srlb.lower_bound + srn->cap.srlb.range_size
+				- 1,
+			srn->cap.algo[0] == SR_ALGORITHM_SPF ? "SPF" : "S-SPF",
+			srn->cap.msd);
 	}
 
 	/* Dump the generated table. */
@@ -1794,6 +2054,10 @@ int isis_sr_start(struct isis_area *area)
 	struct isis_circuit *circuit;
 	struct listnode *node;
 
+	/* Initialize the SRLB */
+	if (sr_local_block_init(area) != 0)
+		return -1;
+
 	/*
 	 * Request SGRB to the label manager. If the allocation fails, return
 	 * an error to disable SR until a new SRGB is successfully allocated.
@@ -1876,6 +2140,9 @@ void isis_sr_stop(struct isis_area *area)
 	isis_zebra_release_label_range(srdb->config.srgb_lower_bound,
 				       srdb->config.srgb_upper_bound);
 
+	/* Delete SRLB */
+	sr_local_block_delete(area);
+
 	/* Regenerate LSPs to advertise that the Node is no more SR enable. */
 	lsp_regenerate_schedule(area, area->is_type, 0);
 }
@@ -1909,10 +2176,16 @@ void isis_sr_area_init(struct isis_area *area)
 		yang_get_default_uint32("%s/srgb/lower-bound", ISIS_SR);
 	srdb->config.srgb_upper_bound =
 		yang_get_default_uint32("%s/srgb/upper-bound", ISIS_SR);
+	srdb->config.srlb_lower_bound =
+		yang_get_default_uint32("%s/srlb/lower-bound", ISIS_SR);
+	srdb->config.srlb_upper_bound =
+		yang_get_default_uint32("%s/srlb/upper-bound", ISIS_SR);
 #else
 	srdb->config.enabled = false;
 	srdb->config.srgb_lower_bound = SRGB_LOWER_BOUND;
 	srdb->config.srgb_upper_bound = SRGB_UPPER_BOUND;
+	srdb->config.srlb_lower_bound = SRLB_LOWER_BOUND;
+	srdb->config.srlb_upper_bound = SRLB_UPPER_BOUND;
 #endif
 	srdb->config.msd = 0;
 	srdb_prefix_cfg_init(&srdb->config.prefix_sids);