fabricd: add field with first and second nexthop to SPF paths

OpenFabric requires knowledge of the first two hops on each path
calculated by spf to implement its flooding optimization. Extend the
hopcount-spf to build such a datastructure.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>

3 files changed, 52 insertions, 9 deletions

diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 79b310323..225ef22ec 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -179,7 +179,8 @@ static const char *vid2string(struct isis_vertex *vertex, char *buff, int size)
 	return "UNKNOWN";
 }
 
-static struct isis_vertex *isis_vertex_new(union isis_N *n,
+static struct isis_vertex *isis_vertex_new(struct isis_spftree *spftree,
+					   union isis_N *n,
 					   enum vertextype vtype)
 {
 	struct isis_vertex *vertex;
@@ -191,6 +192,12 @@ static struct isis_vertex *isis_vertex_new(union isis_N *n,
 	vertex->Adj_N = list_new();
 	vertex->parents = list_new();
 
+	if (spftree->hopcount_metric) {
+		vertex->firsthops = hash_create(isis_vertex_queue_hash_key,
+						isis_vertex_queue_hash_cmp,
+						NULL);
+	}
+
 	return vertex;
 }
 
@@ -334,7 +341,7 @@ static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree,
 		zlog_warn("ISIS-Spf: could not find own l%d LSP!",
 			  spftree->level);
 
-	vertex = isis_vertex_new(&n,
+	vertex = isis_vertex_new(spftree, &n,
 				 spftree->area->oldmetric
 					 ? VTYPE_NONPSEUDO_IS
 					 : VTYPE_NONPSEUDO_TE_IS);
@@ -350,6 +357,26 @@ static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree,
 	return vertex;
 }
 
+static void vertex_add_parent_firsthop(struct hash_backet *backet, void *arg)
+{
+	struct isis_vertex *vertex = arg;
+	struct isis_vertex *hop = backet->data;
+
+	hash_get(vertex->firsthops, hop, hash_alloc_intern);
+}
+
+static void vertex_update_firsthops(struct isis_vertex *vertex,
+				    struct isis_vertex *parent)
+{
+	if (vertex->d_N <= 2)
+		hash_get(vertex->firsthops, vertex, hash_alloc_intern);
+
+	if (vertex->d_N < 2 || !parent)
+		return;
+
+	hash_iterate(parent->firsthops, vertex_add_parent_firsthop, vertex);
+}
+
 /*
  * Add a vertex to TENT sorted by cost and by vertextype on tie break situation
  */
@@ -368,7 +395,7 @@ static struct isis_vertex *isis_spf_add2tent(struct isis_spftree *spftree,
 
 	assert(isis_find_vertex(&spftree->paths, id, vtype) == NULL);
 	assert(isis_find_vertex(&spftree->tents, id, vtype) == NULL);
-	vertex = isis_vertex_new(id, vtype);
+	vertex = isis_vertex_new(spftree, id, vtype);
 	vertex->d_N = cost;
 	vertex->depth = depth;
 
@@ -376,6 +403,9 @@ static struct isis_vertex *isis_spf_add2tent(struct isis_spftree *spftree,
 		listnode_add(vertex->parents, parent);
 	}
 
+	if (spftree->hopcount_metric)
+		vertex_update_firsthops(vertex, parent);
+
 	if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) {
 		for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, parent_adj))
 			listnode_add(vertex->Adj_N, parent_adj);
@@ -497,6 +527,8 @@ static void process_N(struct isis_spftree *spftree, enum vertextype vtype,
 				if (listnode_lookup(vertex->Adj_N, parent_adj)
 				    == NULL)
 					listnode_add(vertex->Adj_N, parent_adj);
+			if (spftree->hopcount_metric)
+				vertex_update_firsthops(vertex, parent);
 			/*      2) */
 			if (listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
 				remove_excess_adjs(vertex->Adj_N);
@@ -1062,7 +1094,8 @@ struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area,
 		isis_spf_preload_tent(spftree, sysid, root);
 	} else {
 		isis_vertex_queue_insert(&spftree->tents, isis_vertex_new(
-					 sysid, VTYPE_NONPSEUDO_TE_IS));
+					 spftree, sysid,
+					 VTYPE_NONPSEUDO_TE_IS));
 	}
 
 	isis_spf_loop(spftree, sysid);
diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h
index 3cd6a005b..4478c7a99 100644
--- a/isisd/isis_spf_private.h
+++ b/isisd/isis_spf_private.h
@@ -64,6 +64,7 @@ struct isis_vertex {
 	uint16_t depth;	/* The depth in the imaginary tree */
 	struct list *Adj_N;    /* {Adj(N)} next hop or neighbor list */
 	struct list *parents;  /* list of parents for ECMP */
+	struct hash *firsthops; /* first two hops to neighbor */
 	uint64_t insert_counter;
 };
 
@@ -170,6 +171,11 @@ static void isis_vertex_del(struct isis_vertex *vertex)
 {
 	list_delete_and_null(&vertex->Adj_N);
 	list_delete_and_null(&vertex->parents);
+	if (vertex->firsthops) {
+		hash_clean(vertex->firsthops, NULL);
+		hash_free(vertex->firsthops);
+		vertex->firsthops = NULL;
+	}
 
 	memset(vertex, 0, sizeof(struct isis_vertex));
 	XFREE(MTYPE_ISIS_VERTEX, vertex);
diff --git a/tests/isisd/test_isis_vertex_queue.c b/tests/isisd/test_isis_vertex_queue.c
index 3e31b8335..96c215dcf 100644
--- a/tests/isisd/test_isis_vertex_queue.c
+++ b/tests/isisd/test_isis_vertex_queue.c
@@ -16,6 +16,8 @@ static size_t vertex_count;
 
 static void setup_test_vertices(void)
 {
+	struct isis_spftree t = {
+	};
 	union isis_N nid, nip = {
 		.ip.dest.family = AF_UNSPEC
 	};
@@ -25,33 +27,35 @@ static void setup_test_vertices(void)
 	nip.ip.dest.family = AF_INET;
 	nip.ip.dest.prefixlen = 24;
 	inet_pton(AF_INET, "192.168.1.0", &nip.ip.dest.u.prefix4);
-	vertices[vertex_count] = isis_vertex_new(&nip, VTYPE_IPREACH_TE);
+	vertices[vertex_count] = isis_vertex_new(&t, &nip, VTYPE_IPREACH_TE);
 	vertices[vertex_count]->d_N = 20;
 	vertex_count++;
 
 	nip.ip.dest.family = AF_INET;
 	nip.ip.dest.prefixlen = 24;
 	inet_pton(AF_INET, "192.168.2.0", &nip.ip.dest.u.prefix4);
-	vertices[vertex_count] = isis_vertex_new(&nip, VTYPE_IPREACH_TE);
+	vertices[vertex_count] = isis_vertex_new(&t, &nip, VTYPE_IPREACH_TE);
 	vertices[vertex_count]->d_N = 20;
 	vertex_count++;
 
 	memset(nid.id, 0, sizeof(nid.id));
 	nid.id[6] = 1;
-	vertices[vertex_count] = isis_vertex_new(&nid, VTYPE_PSEUDO_TE_IS);
+	vertices[vertex_count] = isis_vertex_new(&t, &nid,
+						 VTYPE_PSEUDO_TE_IS);
 	vertices[vertex_count]->d_N = 15;
 	vertex_count++;
 
 	memset(nid.id, 0, sizeof(nid.id));
 	nid.id[5] = 2;
-	vertices[vertex_count] = isis_vertex_new(&nid, VTYPE_NONPSEUDO_TE_IS);
+	vertices[vertex_count] = isis_vertex_new(&t, &nid,
+						 VTYPE_NONPSEUDO_TE_IS);
 	vertices[vertex_count]->d_N = 15;
 	vertex_count++;
 
 	nip.ip.dest.family = AF_INET;
 	nip.ip.dest.prefixlen = 24;
 	inet_pton(AF_INET, "192.168.3.0", &nip.ip.dest.u.prefix4);
-	vertices[vertex_count] = isis_vertex_new(&nip, VTYPE_IPREACH_TE);
+	vertices[vertex_count] = isis_vertex_new(&t, &nip, VTYPE_IPREACH_TE);
 	vertices[vertex_count]->d_N = 20;
 	vertex_count++;
 };