aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNeale Ranns <nranns@cisco.com>2018-04-23 05:31:19 -0700
committerDamjan Marion <dmarion.lists@gmail.com>2018-04-25 12:31:38 +0000
commit580bba72e55961b1d3f98144244ac1780855f74a (patch)
tree91fc618ab0bb717966e98d3fcb39a1fbdf04d51b
parent260de8684d48c1a69e169112fa053d2df1b4871f (diff)
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 <nranns@cisco.com>
-rw-r--r--src/vnet/adj/adj_nbr.c75
-rw-r--r--src/vnet/interface.h5
2 files changed, 30 insertions, 50 deletions
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
@@ -584,29 +584,6 @@ adj_nbr_walk (u32 sw_if_index,
}
/**
- * @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