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 (file)
--- 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 7556bc5..b7b350f 100644 (file)
--- 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