From 580bba72e55961b1d3f98144244ac1780855f74a Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Mon, 23 Apr 2018 05:31:19 -0700 Subject: Adjacency walk more scalable When walking all adjacencies for a given {next-hop,interface} instead of walking all the adjacencies on that interface and matching the next-hop (which is O(n) in the number of adjacencies on that link, find all instances of an adjacency with any link-type and wtih that {next-hop,interfacE} pair: this is O(1). Change-Id: Ic80399fc9e93c8df111379c039e592d8cafbab18 Signed-off-by: Neale Ranns --- src/vnet/adj/adj_nbr.c | 75 +++++++++++++++++--------------------------------- src/vnet/interface.h | 5 ++++ 2 files changed, 30 insertions(+), 50 deletions(-) (limited to 'src') diff --git a/src/vnet/adj/adj_nbr.c b/src/vnet/adj/adj_nbr.c index dcf3cb149a6..29cd8123414 100644 --- a/src/vnet/adj/adj_nbr.c +++ b/src/vnet/adj/adj_nbr.c @@ -583,29 +583,6 @@ adj_nbr_walk (u32 sw_if_index, &awc); } -/** - * @brief Context for a walk of the adjacency neighbour DB - */ -typedef struct adj_walk_nh_ctx_t_ -{ - adj_walk_cb_t awc_cb; - void *awc_ctx; - const ip46_address_t *awc_nh; -} adj_walk_nh_ctx_t; - -static void -adj_nbr_walk_nh_cb (BVT(clib_bihash_kv) * kvp, - void *arg) -{ - ip_adjacency_t *adj; - adj_walk_nh_ctx_t *ctx = arg; - - adj = adj_get(kvp->value); - - if (!ip46_address_cmp(&adj->sub_type.nbr.next_hop, ctx->awc_nh)) - ctx->awc_cb(kvp->value, ctx->awc_ctx); -} - /** * @brief Walk adjacencies on a link with a given v4 next-hop. * that is visit the adjacencies with different link types. @@ -622,17 +599,16 @@ adj_nbr_walk_nh4 (u32 sw_if_index, ip46_address_t nh = { .ip4 = *addr, }; + vnet_link_t linkt; + adj_index_t ai; - adj_walk_nh_ctx_t awc = { - .awc_ctx = ctx, - .awc_cb = cb, - .awc_nh = &nh, - }; + FOR_EACH_VNET_LINK(linkt) + { + ai = adj_nbr_find (FIB_PROTOCOL_IP4, linkt, &nh, sw_if_index); - BV(clib_bihash_foreach_key_value_pair) ( - adj_nbr_tables[FIB_PROTOCOL_IP4][sw_if_index], - adj_nbr_walk_nh_cb, - &awc); + if (INDEX_INVALID != ai) + cb(ai, ctx); + } } /** @@ -651,17 +627,16 @@ adj_nbr_walk_nh6 (u32 sw_if_index, ip46_address_t nh = { .ip6 = *addr, }; + vnet_link_t linkt; + adj_index_t ai; - adj_walk_nh_ctx_t awc = { - .awc_ctx = ctx, - .awc_cb = cb, - .awc_nh = &nh, - }; + FOR_EACH_VNET_LINK(linkt) + { + ai = adj_nbr_find (FIB_PROTOCOL_IP6, linkt, &nh, sw_if_index); - BV(clib_bihash_foreach_key_value_pair) ( - adj_nbr_tables[FIB_PROTOCOL_IP6][sw_if_index], - adj_nbr_walk_nh_cb, - &awc); + if (INDEX_INVALID != ai) + cb(ai, ctx); + } } /** @@ -678,16 +653,16 @@ adj_nbr_walk_nh (u32 sw_if_index, if (!ADJ_NBR_ITF_OK(adj_nh_proto, sw_if_index)) return; - adj_walk_nh_ctx_t awc = { - .awc_ctx = ctx, - .awc_cb = cb, - .awc_nh = nh, - }; + vnet_link_t linkt; + adj_index_t ai; - BV(clib_bihash_foreach_key_value_pair) ( - adj_nbr_tables[adj_nh_proto][sw_if_index], - adj_nbr_walk_nh_cb, - &awc); + FOR_EACH_VNET_LINK(linkt) + { + ai = adj_nbr_find (FIB_PROTOCOL_IP4, linkt, nh, sw_if_index); + + if (INDEX_INVALID != ai) + cb(ai, ctx); + } } /** diff --git a/src/vnet/interface.h b/src/vnet/interface.h index 7556bc5544e..b7b350f68fe 100644 --- a/src/vnet/interface.h +++ b/src/vnet/interface.h @@ -296,6 +296,11 @@ typedef enum vnet_link_t_ [VNET_LINK_NSH] = "nsh", \ } +#define FOR_EACH_VNET_LINK(_link) \ + for (_link = VNET_LINK_IP4; \ + _link <= VNET_LINK_NSH; \ + _link++) + /** * @brief Number of link types. Not part of the enum so it does not have to be included in * switch statements -- cgit 1.2.3-korg