zebra: Add support for SRv6 SID blocks

An SRv6 block is an IPv6 prefix from which SIDs are allocated. This
commit adds support for SRv6 SID blocks. Specifically, it adds a data
structure to store information about an SRv6 block (e.g., its occupancy
status, which SIDs have been allocated and which are available, which
SID format is used for that block, etc.). It also adds some functions to
manage the block (allocate / free / lookup).

These functions will be used in the next commits to support the
allocation of SIDs from a block in the SID Manager.

Signed-off-by: Carmine Scarpitta <cscarpit@cisco.com>

3 files changed, 271 insertions, 2 deletions

diff --git a/zebra/zebra_srv6.c b/zebra/zebra_srv6.c
index 825f0f7fc..2e5c49983 100644
--- a/zebra/zebra_srv6.c
+++ b/zebra/zebra_srv6.c
@@ -33,6 +33,10 @@
 
 DEFINE_MGROUP(SRV6_MGR, "SRv6 Manager");
 DEFINE_MTYPE_STATIC(SRV6_MGR, SRV6M_CHUNK, "SRv6 Manager Chunk");
+DEFINE_MTYPE_STATIC(SRV6_MGR, ZEBRA_SRV6_SID_BLOCK, "SRv6 SID block");
+DEFINE_MTYPE_STATIC(SRV6_MGR, ZEBRA_SRV6_SID_FUNC, "SRv6 SID function");
+DEFINE_MTYPE_STATIC(SRV6_MGR, ZEBRA_SRV6_USID_WLIB,
+		    "SRv6 uSID Wide LIB information");
 
 /* define hooks for the basic API, so that it can be specialized or served
  * externally
@@ -174,6 +178,176 @@ static struct srv6_sid_format *create_srv6_sid_format_uncompressed(void)
 	return format;
 }
 
+/* --- Zebra SRv6 SID function management functions ---------------------------- */
+
+uint32_t *zebra_srv6_sid_func_alloc(uint32_t func)
+{
+	uint32_t *sid_func_ptr;
+
+	sid_func_ptr = XCALLOC(MTYPE_ZEBRA_SRV6_SID_FUNC, sizeof(uint32_t));
+	*sid_func_ptr = func;
+
+	return sid_func_ptr;
+}
+
+void zebra_srv6_sid_func_free(uint32_t *func)
+{
+	XFREE(MTYPE_ZEBRA_SRV6_SID_FUNC, func);
+}
+
+/**
+ * Free an SRv6 SID function.
+ *
+ * @param val SRv6 SID function to be freed
+ */
+void delete_zebra_srv6_sid_func(void *val)
+{
+	zebra_srv6_sid_func_free((uint32_t *)val);
+}
+
+/* --- Zebra SRv6 SID block management functions ---------------------------- */
+
+static struct zebra_srv6_sid_block *zebra_srv6_sid_block_alloc_internal(void)
+{
+	struct zebra_srv6_sid_block *block = NULL;
+
+	block = XCALLOC(MTYPE_ZEBRA_SRV6_SID_BLOCK,
+			sizeof(struct zebra_srv6_sid_block));
+
+	return block;
+}
+
+struct zebra_srv6_sid_block *
+zebra_srv6_sid_block_alloc(struct srv6_sid_format *format,
+			   struct prefix_ipv6 *prefix)
+{
+	struct zebra_srv6_sid_block *block;
+
+	block = zebra_srv6_sid_block_alloc_internal();
+	block->sid_format = format;
+	block->prefix = *prefix;
+
+	if (format) {
+		if (format->type == SRV6_SID_FORMAT_TYPE_USID) {
+			uint32_t wlib_start, wlib_end, func;
+
+			/* Init uSID LIB */
+			block->u.usid.lib.func_allocated = list_new();
+			block->u.usid.lib.func_allocated->del =
+				delete_zebra_srv6_sid_func;
+			block->u.usid.lib.func_released = list_new();
+			block->u.usid.lib.func_released->del =
+				delete_zebra_srv6_sid_func;
+			block->u.usid.lib.first_available_func =
+				format->config.usid.lib_start;
+
+			/* Init uSID Wide LIB */
+			wlib_start = block->sid_format->config.usid.wlib_start;
+			wlib_end = block->sid_format->config.usid.wlib_end;
+			block->u.usid.wide_lib =
+				XCALLOC(MTYPE_ZEBRA_SRV6_USID_WLIB,
+					(wlib_end - wlib_start + 1) *
+						sizeof(struct wide_lib));
+			for (func = 0; func < wlib_end - wlib_start + 1;
+			     func++) {
+				block->u.usid.wide_lib[func].func_allocated =
+					list_new();
+				block->u.usid.wide_lib[func].func_allocated->del =
+					delete_zebra_srv6_sid_func;
+				block->u.usid.wide_lib[func].func_released =
+					list_new();
+				block->u.usid.wide_lib[func].func_released->del =
+					delete_zebra_srv6_sid_func;
+				block->u.usid.wide_lib[func].func = func;
+			}
+		} else if (format->type == SRV6_SID_FORMAT_TYPE_UNCOMPRESSED) {
+			block->u.uncompressed.func_allocated = list_new();
+			block->u.uncompressed.func_allocated->del =
+				delete_zebra_srv6_sid_func;
+			block->u.uncompressed.func_released = list_new();
+			block->u.uncompressed.func_released->del =
+				delete_zebra_srv6_sid_func;
+			block->u.uncompressed.first_available_func =
+				SRV6_SID_FORMAT_UNCOMPRESSED_F4024_FUNC_UNRESERVED_MIN;
+		} else {
+			/* We should never arrive here */
+			assert(0);
+		}
+	} else {
+		block->u.uncompressed.func_allocated = list_new();
+		block->u.uncompressed.func_allocated->del =
+			delete_zebra_srv6_sid_func;
+		block->u.uncompressed.func_released = list_new();
+		block->u.uncompressed.func_released->del =
+			delete_zebra_srv6_sid_func;
+		block->u.uncompressed.first_available_func = 1;
+	}
+
+	return block;
+}
+
+void zebra_srv6_sid_block_free(struct zebra_srv6_sid_block *block)
+{
+	if (block->sid_format) {
+		if (block->sid_format->type == SRV6_SID_FORMAT_TYPE_USID) {
+			uint32_t wlib_start, wlib_end, func;
+
+			/* Free uSID LIB */
+			list_delete(&block->u.usid.lib.func_allocated);
+			list_delete(&block->u.usid.lib.func_released);
+
+			/* Free uSID Wide LIB */
+			wlib_start = block->sid_format->config.usid.wlib_start;
+			wlib_end = block->sid_format->config.usid.wlib_end;
+			for (func = 0; func < wlib_end - wlib_start + 1;
+			     func++) {
+				list_delete(&block->u.usid.wide_lib[func]
+						     .func_allocated);
+				list_delete(&block->u.usid.wide_lib[func]
+						     .func_released);
+			}
+			XFREE(MTYPE_ZEBRA_SRV6_USID_WLIB,
+			      block->u.usid.wide_lib);
+		} else if (block->sid_format->type ==
+			   SRV6_SID_FORMAT_TYPE_UNCOMPRESSED) {
+			list_delete(&block->u.uncompressed.func_allocated);
+			list_delete(&block->u.uncompressed.func_released);
+		} else {
+			/* We should never arrive here */
+			assert(0);
+		}
+	} else {
+		list_delete(&block->u.uncompressed.func_allocated);
+		list_delete(&block->u.uncompressed.func_released);
+	}
+
+	XFREE(MTYPE_ZEBRA_SRV6_SID_BLOCK, block);
+}
+
+/**
+ * Free an SRv6 SID block.
+ *
+ * @param val SRv6 SID block to be freed
+ */
+void delete_zebra_srv6_sid_block(void *val)
+{
+	zebra_srv6_sid_block_free((struct zebra_srv6_sid_block *)val);
+}
+
+struct zebra_srv6_sid_block *
+zebra_srv6_sid_block_lookup(struct prefix_ipv6 *prefix)
+{
+	struct zebra_srv6 *srv6 = zebra_srv6_get_default();
+	struct zebra_srv6_sid_block *block;
+	struct listnode *node;
+
+	for (ALL_LIST_ELEMENTS_RO(srv6->sid_blocks, node, block))
+		if (prefix_match(prefix, &block->prefix))
+			return block;
+
+	return NULL;
+}
+
 void zebra_srv6_locator_add(struct srv6_locator *locator)
 {
 	struct zebra_srv6 *srv6 = zebra_srv6_get_default();
@@ -324,6 +498,10 @@ struct zebra_srv6 *zebra_srv6_get_default(void)
 		/* Create SID format `uncompressed` */
 		format_uncompressed = create_srv6_sid_format_uncompressed();
 		srv6_sid_format_register(format_uncompressed);
+
+		/* Init list to store SRv6 SID blocks */
+		srv6.sid_blocks = list_new();
+		srv6.sid_blocks->del = delete_zebra_srv6_sid_block;
 	}
 	return &srv6;
 }
@@ -529,6 +707,7 @@ void zebra_srv6_terminate(void)
 {
 	struct srv6_locator *locator;
 	struct srv6_sid_format *format;
+	struct zebra_srv6_sid_block *block;
 
 	if (srv6.locators) {
 		while (listcount(srv6.locators)) {
@@ -541,6 +720,18 @@ void zebra_srv6_terminate(void)
 		list_delete(&srv6.locators);
 	}
 
+	/* Free SRv6 SID blocks */
+	if (srv6.sid_blocks) {
+		while (listcount(srv6.sid_blocks)) {
+			block = listnode_head(srv6.sid_blocks);
+
+			listnode_delete(srv6.sid_blocks, block);
+			zebra_srv6_sid_block_free(block);
+		}
+
+		list_delete(&srv6.sid_blocks);
+	}
+
 	/* Free SRv6 SID formats */
 	if (srv6.sid_formats) {
 		while (listcount(srv6.sid_formats)) {
diff --git a/zebra/zebra_srv6.h b/zebra/zebra_srv6.h
index 92e4fcf91..e81d18241 100644
--- a/zebra/zebra_srv6.h
+++ b/zebra/zebra_srv6.h
@@ -38,6 +38,70 @@
 #define SRV6_SID_FORMAT_UNCOMPRESSED_F4024_EXPLICIT_RANGE_START 0xFF00
 #define SRV6_SID_FORMAT_UNCOMPRESSED_F4024_FUNC_UNRESERVED_MIN	0x40
 
+/* uSID Wide LIB */
+struct wide_lib {
+	uint32_t func;
+	uint32_t num_func_allocated;
+	uint32_t first_available_func;
+	struct list *func_allocated;
+	struct list *func_released;
+};
+
+/*
+ * SRv6 SID block.
+ *
+ * A SID block is an IPv6 prefix from which SRv6 SIDs are allocated.
+ * Example:
+ *   SID block = fc00:0::/32
+ *   SID 1 = fc00:0:1:e000::
+ *   SID 2 = fc00:0:1:fe00::
+ *   ...
+ */
+struct zebra_srv6_sid_block {
+	/*  Prefix of this block, e.g. fc00:0::/32 */
+	struct prefix_ipv6 prefix;
+
+	/* Reference counter */
+	unsigned long refcnt;
+
+	/*
+	 * Pointer to the SID format that defines the structure of the SIDs
+	 * allocated from this block
+	 */
+	struct zebra_srv6_sid_format *sid_format;
+
+	/*
+	 * Run-time information/state of this SID block.
+	 *
+	 * This includes stuff like how many SID functions have been allocated
+	 * from this block, which functions are still available to be allocated
+	 * and so on...
+	 */
+	union {
+		/* Information/state for compressed uSID format */
+		struct {
+			/* uSID Local ID Block (LIB) */
+			struct {
+				uint32_t num_func_allocated;
+				uint32_t first_available_func;
+				struct list *func_allocated;
+				struct list *func_released;
+			} lib;
+
+			/* uSID Wide LIB */
+			struct wide_lib *wide_lib;
+		} usid;
+
+		/* Information/state for uncompressed SID format */
+		struct {
+			uint32_t num_func_allocated;
+			uint32_t first_available_func;
+			struct list *func_allocated;
+			struct list *func_released;
+		} uncompressed;
+	} u;
+};
+
 /* SRv6 instance structure. */
 struct zebra_srv6 {
 	struct list *locators;
@@ -47,6 +111,9 @@ struct zebra_srv6 {
 
 	/* SRv6 SID formats */
 	struct list *sid_formats;
+
+	/* SRv6 SID blocks */
+	struct list *sid_blocks;
 };
 
 /* declare hooks for the basic API, so that it can be specialized or served
@@ -103,4 +170,16 @@ void srv6_sid_format_register(struct srv6_sid_format *format);
 void srv6_sid_format_unregister(struct srv6_sid_format *format);
 struct srv6_sid_format *srv6_sid_format_lookup(const char *name);
 
+uint32_t *zebra_srv6_sid_func_alloc(uint32_t func);
+void zebra_srv6_sid_func_free(uint32_t *func);
+void delete_zebra_srv6_sid_func(void *val);
+
+extern struct zebra_srv6_sid_block *
+zebra_srv6_sid_block_alloc(struct zebra_srv6_sid_format *format,
+			   struct prefix_ipv6 *prefix);
+extern void zebra_srv6_sid_block_free(struct zebra_srv6_sid_block *block);
+extern void delete_zebra_srv6_sid_block(void *val);
+extern struct zebra_srv6_sid_block *
+zebra_srv6_sid_block_lookup(struct prefix_ipv6 *prefix);
+
 #endif /* _ZEBRA_SRV6_H */
diff --git a/zebra/zebra_srv6_vty.c b/zebra/zebra_srv6_vty.c
index e5fe0d58a..963b528b8 100644
--- a/zebra/zebra_srv6_vty.c
+++ b/zebra/zebra_srv6_vty.c
@@ -833,8 +833,7 @@ static int zebra_sr_config(struct vty *vty)
 						format->config.uncompressed
 							.explicit_start);
 			}
-			if (format->type ==
-			    SRV6_SID_FORMAT_TYPE_COMPRESSED_USID) {
+			if (format->type == SRV6_SID_FORMAT_TYPE_USID) {
 				vty_out(vty, "   format %s\n", format->name);
 				if (format->config.usid.lib_start !=
 				    SRV6_SID_FORMAT_USID_F3216_LIB_START)