From 686afe9f0700b561ea493d2041f5cf16b8d92538 Mon Sep 17 00:00:00 2001 From: Christian Franke Date: Thu, 10 May 2018 20:02:04 +0200 Subject: [PATCH] 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 --- isisd/isis_spf.c | 41 +++++++++++++++++++++++++--- isisd/isis_spf_private.h | 6 ++++ tests/isisd/test_isis_vertex_queue.c | 14 ++++++---- 3 files changed, 52 insertions(+), 9 deletions(-) diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 79b3103237..225ef22ec1 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 3cd6a005be..4478c7a997 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 3e31b83351..96c215dcff 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++; }; -- 2.39.5