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>
diff --git a/src/vnet/adj/adj_nbr.c b/src/vnet/adj/adj_nbr.c
index dcf3cb1..29cd812 100644
--- a/src/vnet/adj/adj_nbr.c
+++ b/src/vnet/adj/adj_nbr.c
@@ -584,29 +584,6 @@
}
/**
- * @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 @@
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 @@
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 @@
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 7556bc5..b7b350f 100644
--- a/src/vnet/interface.h
+++ b/src/vnet/interface.h
@@ -296,6 +296,11 @@
[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