A Protocol Independent Hierarchical FIB (VPP-352)

[vpp.git] / vnet / vnet / ip / ip4_mtrie.c

diff --git a/vnet/vnet/ip/ip4_mtrie.c b/vnet/vnet/ip/ip4_mtrie.c
index ed4a0d9..3641824 100644 (file)
--- a/vnet/vnet/ip/ip4_mtrie.c
+++ b/vnet/vnet/ip/ip4_mtrie.c
@@ -38,6 +38,7 @@
  */
 
 #include <vnet/ip/ip.h>
+#include <vnet/fib/fib_entry.h>
 
 static void
 ply_init (ip4_fib_mtrie_ply_t * p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
@@ -191,7 +192,8 @@ set_ply_with_more_specific_leaf (ip4_fib_mtrie_t * m,
       /* Replace less specific terminal leaves with new leaf. */
       else if (new_leaf_dst_address_bits >= ply->dst_address_bits_of_leaves[i])
        {
-         ply->leaves[i] = new_leaf;
+          __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
+          ASSERT(ply->leaves[i] == new_leaf);
          ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
          ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
        }
@@ -240,7 +242,9 @@ set_leaf (ip4_fib_mtrie_t * m,
              if (old_leaf_is_terminal)
                {
                  old_ply->dst_address_bits_of_leaves[i] = a->dst_address_length;
-                 old_ply->leaves[i] = new_leaf;
+                  __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
+                                               new_leaf);
+                  ASSERT(old_ply->leaves[i] == new_leaf);
                  old_ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
                  ASSERT (old_ply->n_non_empty_leafs <= ARRAY_LEN (old_ply->leaves));
                }
@@ -274,7 +278,9 @@ set_leaf (ip4_fib_mtrie_t * m,
          /* Refetch since ply_create may move pool. */
          old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 
-         old_ply->leaves[dst_byte] = new_leaf;
+          __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
+                                       new_leaf);
+          ASSERT(old_ply->leaves[dst_byte] == new_leaf);
          old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
 
          old_ply->n_non_empty_leafs -= ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
@@ -298,7 +304,7 @@ unset_leaf (ip4_fib_mtrie_t * m,
 {
   ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
   i32 n_dst_bits_next_plies;
-  uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
+  i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
   u8 dst_byte;
 
   ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
@@ -396,21 +402,27 @@ ip4_fib_mtrie_add_del_route (ip4_fib_t * fib,
          unset_leaf (m, &a, root_ply, 0);
 
          /* Find next less specific route and insert into mtrie. */
-         for (i = ARRAY_LEN (fib->adj_index_by_dst_address) - 1; i >= 1; i--)
+         for (i = dst_address_length - 1; i >= 1; i--)
            {
              uword * p;
+              index_t lbi;
              ip4_address_t key;
 
-             if (! fib->adj_index_by_dst_address[i])
+             if (! fib->fib_entry_by_dst_address[i])
                continue;
              
              key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
-             p = hash_get (fib->adj_index_by_dst_address[i], key.as_u32);
+             p = hash_get (fib->fib_entry_by_dst_address[i], key.as_u32);
              if (p)
                {
+                 lbi = fib_entry_contribute_ip_forwarding(p[0])->dpoi_index;
+                 if (INDEX_INVALID == lbi)
+                   continue;
+
                  a.dst_address = key;
+                 a.adj_index = lbi;
                  a.dst_address_length = i;
-                 a.adj_index = p[0];
+
                  set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
                  break;
                }
@@ -419,49 +431,6 @@ ip4_fib_mtrie_add_del_route (ip4_fib_t * fib,
     }
 }
 
-always_inline uword
-maybe_remap_leaf (ip_lookup_main_t * lm, ip4_fib_mtrie_leaf_t * p)
-{
-  ip4_fib_mtrie_leaf_t l = p[0];
-  uword was_remapped_to_empty_leaf = 0;
-  if (ip4_fib_mtrie_leaf_is_terminal (l))
-    {
-      u32 adj_index = ip4_fib_mtrie_leaf_get_adj_index (l);
-      u32 m = vec_elt (lm->adjacency_remap_table, adj_index);
-      if (m)
-       {
-         was_remapped_to_empty_leaf = m == ~0;
-         if (was_remapped_to_empty_leaf)
-           p[0] = (was_remapped_to_empty_leaf
-                   ? IP4_FIB_MTRIE_LEAF_EMPTY
-                   : ip4_fib_mtrie_leaf_set_adj_index (m - 1));
-       }
-    }
-  return was_remapped_to_empty_leaf;
-}
-
-static void maybe_remap_ply (ip_lookup_main_t * lm, ip4_fib_mtrie_ply_t * ply)
-{
-  u32 n_remapped_to_empty = 0;
-  u32 i;
-  for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
-    n_remapped_to_empty += maybe_remap_leaf (lm, &ply->leaves[i]);
-  if (n_remapped_to_empty > 0)
-    {
-      ASSERT (n_remapped_to_empty <= ply->n_non_empty_leafs);
-      ply->n_non_empty_leafs -= n_remapped_to_empty;
-      if (ply->n_non_empty_leafs == 0)
-       os_panic ();
-    }
-}
-
-void ip4_mtrie_maybe_remap_adjacencies (ip_lookup_main_t * lm, ip4_fib_mtrie_t * m)
-{
-  ip4_fib_mtrie_ply_t * ply;
-  pool_foreach (ply, m->ply_pool, maybe_remap_ply (lm, ply));
-  maybe_remap_leaf (lm, &m->default_leaf);
-}
-
 /* Returns number of bytes of memory used by mtrie. */
 static uword mtrie_memory_usage (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
 {