isisd: calculate flex-algo constraint spf

Take into account the flex-algo affinity constraints to compute the SPF
tree.

Signed-off-by: Hiroki Shirokura <hiroki.shirokura@linecorp.com>
Signed-off-by: Louis Scalbert <louis.scalbert@6wind.com>

5 files changed, 290 insertions, 22 deletions

diff --git a/isisd/isis_flex_algo.c b/isisd/isis_flex_algo.c
index 94ad53b22..742a862fc 100644
--- a/isisd/isis_flex_algo.c
+++ b/isisd/isis_flex_algo.c
@@ -237,4 +237,100 @@ bool sr_algorithm_participated(const struct isis_lsp *lsp, uint8_t algorithm)
 	return false;
 }
 
+bool isis_flex_algo_constraint_drop(struct isis_spftree *spftree,
+				    struct isis_lsp *lsp,
+				    struct isis_extended_reach *reach)
+{
+	bool ret;
+	struct isis_ext_subtlvs *subtlvs = reach->subtlvs;
+	uint8_t lspid_orig[ISIS_SYS_ID_LEN + 2];
+	uint8_t lspid_neigh[ISIS_SYS_ID_LEN + 2];
+	struct isis_router_cap_fad *fad;
+	struct isis_asla_subtlvs *asla;
+	struct listnode *node;
+	uint32_t *link_admin_group = NULL;
+	uint32_t link_ext_admin_group_bitmap0;
+	struct admin_group *link_ext_admin_group = NULL;
+
+	fad = isis_flex_algo_elected_supported(spftree->algorithm,
+					       spftree->area);
+	if (!fad)
+		return true;
+
+	for (ALL_LIST_ELEMENTS_RO(subtlvs->aslas, node, asla)) {
+		if (!CHECK_FLAG(asla->standard_apps, ISIS_SABM_FLAG_X))
+			continue;
+		if (asla->legacy) {
+			if (IS_SUBTLV(subtlvs, EXT_ADM_GRP))
+				link_admin_group = &subtlvs->adm_group;
+
+			if (IS_SUBTLV(subtlvs, EXT_EXTEND_ADM_GRP) &&
+			    admin_group_nb_words(&subtlvs->ext_admin_group) !=
+				    0)
+				link_ext_admin_group =
+					&subtlvs->ext_admin_group;
+		} else {
+			if (IS_SUBTLV(asla, EXT_ADM_GRP))
+				link_admin_group = &asla->admin_group;
+			if (IS_SUBTLV(asla, EXT_EXTEND_ADM_GRP) &&
+			    admin_group_nb_words(&asla->ext_admin_group) != 0)
+				link_ext_admin_group = &asla->ext_admin_group;
+		}
+		break;
+	}
+
+	/* RFC7308 section 2.3.1
+	 * A receiving node that notices that the AG differs from the first 32
+	 * bits of the EAG SHOULD report this mismatch to the operator.
+	 */
+	if (link_admin_group && link_ext_admin_group) {
+		link_ext_admin_group_bitmap0 =
+			admin_group_get_offset(link_ext_admin_group, 0);
+		if (*link_admin_group != link_ext_admin_group_bitmap0) {
+			memcpy(lspid_orig, lsp->hdr.lsp_id,
+			       ISIS_SYS_ID_LEN + 2);
+			memcpy(lspid_neigh, reach->id, ISIS_SYS_ID_LEN + 2);
+			zlog_warn(
+				"ISIS-SPF: LSP from %pLS neighbor %pLS. Admin-group 0x%08x differs from ext admin-group 0x%08x.",
+				lspid_orig, lspid_neigh, *link_admin_group,
+				link_ext_admin_group_bitmap0);
+		}
+	}
+
+	/*
+	 * Exclude Any
+	 */
+	if (!admin_group_zero(&fad->fad.admin_group_exclude_any)) {
+		ret = admin_group_match_any(&fad->fad.admin_group_exclude_any,
+					    link_admin_group,
+					    link_ext_admin_group);
+		if (ret)
+			return true;
+	}
+
+	/*
+	 * Include Any
+	 */
+	if (!admin_group_zero(&fad->fad.admin_group_include_any)) {
+		ret = admin_group_match_any(&fad->fad.admin_group_include_any,
+					    link_admin_group,
+					    link_ext_admin_group);
+		if (!ret)
+			return true;
+	}
+
+	/*
+	 * Include All
+	 */
+	if (!admin_group_zero(&fad->fad.admin_group_include_all)) {
+		ret = admin_group_match_all(&fad->fad.admin_group_include_all,
+					    link_admin_group,
+					    link_ext_admin_group);
+		if (!ret)
+			return true;
+	}
+
+	return false;
+}
+
 #endif /* ifndef FABRICD */
diff --git a/isisd/isis_flex_algo.h b/isisd/isis_flex_algo.h
index 0a0e337e0..c47583824 100644
--- a/isisd/isis_flex_algo.h
+++ b/isisd/isis_flex_algo.h
@@ -46,6 +46,10 @@ isis_flex_algo_elected_supported_local_fad(int algorithm,
 struct isis_lsp;
 bool sr_algorithm_participated(const struct isis_lsp *lsp, uint8_t algorithm);
 
+bool isis_flex_algo_constraint_drop(struct isis_spftree *spftree,
+				    struct isis_lsp *lsp,
+				    struct isis_extended_reach *reach);
+
 #endif /* ifndef FABRICD */
 
 #endif /* ISIS_FLEX_ALGO_H */
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 6bfb83c21..cc8c5168e 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -43,6 +43,7 @@
 #include "isis_csm.h"
 #include "isis_mt.h"
 #include "isis_tlvs.h"
+#include "isis_flex_algo.h"
 #include "isis_zebra.h"
 #include "fabricd.h"
 #include "isis_spf_private.h"
@@ -322,29 +323,41 @@ static void isis_spf_adj_free(void *arg)
 	XFREE(MTYPE_ISIS_SPF_ADJ, sadj);
 }
 
-struct isis_spftree *
-isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb,
-		 const uint8_t *sysid, int level, enum spf_tree_id tree_id,
-		 enum spf_type type, uint8_t flags, uint8_t algorithm)
+static void _isis_spftree_init(struct isis_spftree *tree)
 {
-	struct isis_spftree *tree;
-
-	tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree));
-
 	isis_vertex_queue_init(&tree->tents, "IS-IS SPF tents", true);
 	isis_vertex_queue_init(&tree->paths, "IS-IS SPF paths", false);
 	tree->route_table = srcdest_table_init();
 	tree->route_table->cleanup = isis_route_node_cleanup;
-	tree->route_table->info = isis_route_table_info_alloc(algorithm);
+	tree->route_table->info = isis_route_table_info_alloc(tree->algorithm);
 	tree->route_table_backup = srcdest_table_init();
-	tree->route_table_backup->info = isis_route_table_info_alloc(algorithm);
+	tree->route_table_backup->info =
+		isis_route_table_info_alloc(tree->algorithm);
 	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;
+	isis_rlfa_list_init(tree);
+	tree->lfa.remote.pc_spftrees = list_new();
+	tree->lfa.remote.pc_spftrees->del = (void (*)(void *))isis_spftree_del;
+	if (tree->type == SPF_TYPE_RLFA || tree->type == SPF_TYPE_TI_LFA) {
+		isis_spf_node_list_init(&tree->lfa.p_space);
+		isis_spf_node_list_init(&tree->lfa.q_space);
+	}
+}
+
+struct isis_spftree *
+isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb,
+		 const uint8_t *sysid, int level, enum spf_tree_id tree_id,
+		 enum spf_type type, uint8_t flags, uint8_t algorithm)
+{
+	struct isis_spftree *tree;
+
+	tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree));
+
+	tree->area = area;
+	tree->lspdb = lspdb;
 	tree->last_run_timestamp = 0;
 	tree->last_run_monotime = 0;
 	tree->last_run_duration = 0;
@@ -355,19 +368,14 @@ isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb,
 	tree->tree_id = tree_id;
 	tree->family = (tree->tree_id == SPFTREE_IPV4) ? AF_INET : AF_INET6;
 	tree->flags = flags;
-	isis_rlfa_list_init(tree);
-	tree->lfa.remote.pc_spftrees = list_new();
-	tree->lfa.remote.pc_spftrees->del = (void (*)(void *))isis_spftree_del;
-	if (tree->type == SPF_TYPE_RLFA || tree->type == SPF_TYPE_TI_LFA) {
-		isis_spf_node_list_init(&tree->lfa.p_space);
-		isis_spf_node_list_init(&tree->lfa.q_space);
-	}
 	tree->algorithm = algorithm;
 
+	_isis_spftree_init(tree);
+
 	return tree;
 }
 
-void isis_spftree_del(struct isis_spftree *spftree)
+static void _isis_spftree_del(struct isis_spftree *spftree)
 {
 	hash_clean_and_free(&spftree->prefix_sids, NULL);
 	isis_zebra_rlfa_unregister_all(spftree);
@@ -384,6 +392,12 @@ void isis_spftree_del(struct isis_spftree *spftree)
 	isis_vertex_queue_free(&spftree->paths);
 	isis_route_table_info_free(spftree->route_table->info);
 	isis_route_table_info_free(spftree->route_table_backup->info);
+}
+
+void isis_spftree_del(struct isis_spftree *spftree)
+{
+	_isis_spftree_del(spftree);
+
 	route_table_finish(spftree->route_table);
 	route_table_finish(spftree->route_table_backup);
 	spftree->route_table = NULL;
@@ -392,6 +406,14 @@ void isis_spftree_del(struct isis_spftree *spftree)
 	return;
 }
 
+#ifndef FABRICD
+static void isis_spftree_clear(struct isis_spftree *spftree)
+{
+	_isis_spftree_del(spftree);
+	_isis_spftree_init(spftree);
+}
+#endif /* ifndef FABRICD */
+
 static void isis_spftree_adj_del(struct isis_spftree *spftree,
 				 struct isis_adjacency *adj)
 {
@@ -594,6 +616,15 @@ isis_spf_add2tent(struct isis_spftree *spftree, enum vertextype vtype, void *id,
 			if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL)
 				vertex->N.ip.sr.present = true;
 
+#ifndef FABRICD
+			if (flex_algo_id_valid(spftree->algorithm) &&
+			    !isis_flex_algo_elected_supported(
+				    spftree->algorithm, spftree->area)) {
+				vertex->N.ip.sr.present = false;
+				vertex->N.ip.sr.label = MPLS_INVALID_LABEL;
+			}
+#endif /* ifndef FABRICD */
+
 			(void)hash_get(spftree->prefix_sids, vertex,
 				       hash_alloc_intern);
 		}
@@ -895,6 +926,16 @@ lspfragloop:
 				    && !memcmp(er->id, null_sysid,
 					       ISIS_SYS_ID_LEN))
 					continue;
+#ifndef FABRICD
+
+				if (flex_algo_id_valid(spftree->algorithm) &&
+				    (!sr_algorithm_participated(
+					     lsp, spftree->algorithm) ||
+				     isis_flex_algo_constraint_drop(spftree,
+								    lsp, er)))
+					continue;
+#endif /* ifndef FABRICD */
+
 				dist = cost
 				       + (CHECK_FLAG(spftree->flags,
 						     F_SPFTREE_HOPCOUNT_METRIC)
@@ -975,6 +1016,17 @@ lspfragloop:
 					    spftree->algorithm)
 						continue;
 
+#ifndef FABRICD
+					if (flex_algo_id_valid(
+						    spftree->algorithm) &&
+					    (!sr_algorithm_participated(
+						     lsp, spftree->algorithm) ||
+					     !isis_flex_algo_elected_supported(
+						     spftree->algorithm,
+						     spftree->area)))
+						continue;
+#endif /* ifndef FABRICD */
+
 					has_valid_psid = true;
 					process_N(spftree, VTYPE_IPREACH_TE,
 						  &ip_info, dist, depth + 1,
@@ -1044,6 +1096,17 @@ lspfragloop:
 					    spftree->algorithm)
 						continue;
 
+#ifndef FABRICD
+					if (flex_algo_id_valid(
+						    spftree->algorithm) &&
+					    (!sr_algorithm_participated(
+						     lsp, spftree->algorithm) ||
+					     !isis_flex_algo_elected_supported(
+						     spftree->algorithm,
+						     spftree->area)))
+						continue;
+#endif /* ifndef FABRICD */
+
 					has_valid_psid = true;
 					process_N(spftree, vtype, &ip_info,
 						  dist, depth + 1, psid,
@@ -1428,6 +1491,19 @@ static void spf_adj_list_parse_lsp(struct isis_spftree *spftree,
 			for (struct isis_extended_reach *reach =
 				     (struct isis_extended_reach *)head;
 			     reach; reach = reach->next) {
+#ifndef FABRICD
+				/*
+				 * cutting out adjacency by flex-algo link
+				 * affinity attribute
+				 */
+				if (flex_algo_id_valid(spftree->algorithm) &&
+				    (!sr_algorithm_participated(
+					     lsp, spftree->algorithm) ||
+				     isis_flex_algo_constraint_drop(
+					     spftree, lsp, reach)))
+					continue;
+#endif /* ifndef FABRICD */
+
 				spf_adj_list_parse_tlv(
 					spftree, adj_list, reach->id,
 					pseudo_nodeid, pseudo_metric,
@@ -1783,6 +1859,27 @@ void isis_run_spf(struct isis_spftree *spftree)
 		exit(1);
 	}
 
+#ifndef FABRICD
+	/* If a node is configured to participate in a particular Flexible-
+	 * Algorithm, but there is no valid Flex-Algorithm definition available
+	 * for it, or the selected Flex-Algorithm definition includes
+	 * calculation-type, metric-type, constraint, flag, or Sub-TLV that is
+	 * not supported by the node, it MUST stop participating in such
+	 * Flexible-Algorithm.
+	 */
+	if (flex_algo_id_valid(spftree->algorithm) &&
+	    !isis_flex_algo_elected_supported(spftree->algorithm,
+					      spftree->area)) {
+		if (!CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
+			isis_spftree_clear(spftree);
+			SET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
+			lsp_regenerate_schedule(spftree->area,
+						spftree->area->is_type, 0);
+		}
+		goto out;
+	}
+#endif /* ifndef FABRICD */
+
 	/*
 	 * C.2.5 Step 0
 	 */
@@ -1803,6 +1900,18 @@ void isis_run_spf(struct isis_spftree *spftree)
 	}
 
 	isis_spf_loop(spftree, spftree->sysid);
+
+
+#ifndef FABRICD
+	/* flex-algo */
+	if (CHECK_FLAG(spftree->flags, F_SPFTREE_DISABLED)) {
+		UNSET_FLAG(spftree->flags, F_SPFTREE_DISABLED);
+		lsp_regenerate_schedule(spftree->area, spftree->area->is_type,
+					0);
+	}
+
+out:
+#endif /* ifndef FABRICD */
 	spftree->runcount++;
 	spftree->last_run_timestamp = time(NULL);
 	spftree->last_run_monotime = monotime(&time_end);
@@ -1872,6 +1981,12 @@ static void isis_run_spf_cb(struct event *thread)
 	struct isis_area *area = run->area;
 	int level = run->level;
 	int have_run = 0;
+	struct listnode *node;
+	struct isis_circuit *circuit;
+#ifndef FABRICD
+	struct flex_algo *fa;
+	struct isis_flex_algo_data *data;
+#endif /* ifndef FABRICD */
 
 	XFREE(MTYPE_ISIS_SPF_RUN, run);
 
@@ -1892,11 +2007,27 @@ static void isis_run_spf_cb(struct event *thread)
 	if (area->ip_circuits) {
 		isis_run_spf_with_protection(
 			area, area->spftree[SPFTREE_IPV4][level - 1]);
+#ifndef FABRICD
+		for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
+					  fa)) {
+			data = fa->data;
+			isis_run_spf_with_protection(
+				area, data->spftree[SPFTREE_IPV4][level - 1]);
+		}
+#endif /* ifndef FABRICD */
 		have_run = 1;
 	}
 	if (area->ipv6_circuits) {
 		isis_run_spf_with_protection(
 			area, area->spftree[SPFTREE_IPV6][level - 1]);
+#ifndef FABRICD
+		for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
+					  fa)) {
+			data = fa->data;
+			isis_run_spf_with_protection(
+				area, data->spftree[SPFTREE_IPV6][level - 1]);
+		}
+#endif /* ifndef FABRICD */
 		have_run = 1;
 	}
 	if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) {
@@ -1911,8 +2042,6 @@ static void isis_run_spf_cb(struct event *thread)
 	isis_area_verify_routes(area);
 
 	/* walk all circuits and reset any spf specific flags */
-	struct listnode *node;
-	struct isis_circuit *circuit;
 	for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit))
 		UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF);
 
diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h
index 5f926df70..763673063 100644
--- a/isisd/isis_spf_private.h
+++ b/isisd/isis_spf_private.h
@@ -355,6 +355,10 @@ struct isis_spftree {
 #define F_SPFTREE_HOPCOUNT_METRIC 0x01
 #define F_SPFTREE_NO_ROUTES 0x02
 #define F_SPFTREE_NO_ADJACENCIES 0x04
+#ifndef FABRICD
+/* flex-algo */
+#define F_SPFTREE_DISABLED 0x08
+#endif /* ifndef FABRICD */
 
 __attribute__((__unused__))
 static void isis_vertex_id_init(struct isis_vertex *vertex, const void *id,
diff --git a/isisd/isisd.c b/isisd/isisd.c
index 6c4cdfb95..195f9f16f 100644
--- a/isisd/isisd.c
+++ b/isisd/isisd.c
@@ -3069,12 +3069,27 @@ int isis_area_passwd_hmac_md5_set(struct isis_area *area, int level,
 
 void isis_area_invalidate_routes(struct isis_area *area, int levels)
 {
+#ifndef FABRICD
+	struct flex_algo *fa;
+	struct listnode *node;
+	struct isis_flex_algo_data *data;
+#endif /* ifndef FABRICD */
+
 	for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
 		if (!(level & levels))
 			continue;
 		for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
 			isis_spf_invalidate_routes(
 					area->spftree[tree][level - 1]);
+
+#ifndef FABRICD
+			for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos,
+						  node, fa)) {
+				data = fa->data;
+				isis_spf_invalidate_routes(
+					data->spftree[tree][level - 1]);
+			}
+#endif /* ifndef FABRICD */
 		}
 	}
 }
@@ -3106,6 +3121,12 @@ void isis_area_switchover_routes(struct isis_area *area, int family,
 
 static void area_resign_level(struct isis_area *area, int level)
 {
+#ifndef FABRICD
+	struct flex_algo *fa;
+	struct listnode *node;
+	struct isis_flex_algo_data *data;
+#endif /* ifndef FABRICD */
+
 	isis_area_invalidate_routes(area, level);
 	isis_area_verify_routes(area);
 
@@ -3118,6 +3139,20 @@ static void area_resign_level(struct isis_area *area, int level)
 		}
 	}
 
+#ifndef FABRICD
+	for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
+		for (ALL_LIST_ELEMENTS_RO(area->flex_algos->flex_algos, node,
+					  fa)) {
+			data = fa->data;
+			if (data->spftree[level - 1]) {
+				isis_spftree_del(
+					data->spftree[tree][level - 1]);
+				data->spftree[tree][level - 1] = NULL;
+			}
+		}
+	}
+#endif /* ifndef FABRICD */
+
 	if (area->spf_timer[level - 1])
 		isis_spf_timer_free(EVENT_ARG(area->spf_timer[level - 1]));