Mtrie optimisations

1 - make the default route non-special, i.e. like any other less specific route. Consequently, all buckets have a valid valid index of either a leaf or a ply. Checks for special indeices in the data-path can thus be removed.
2 - since all leaves are now 'real' i.e. they represent a real load-balance object, to tell if a ply slot is 'empty' requeirs chekcing that the prefix length of the leaf occupying the slot is slot than the minium value for that ply.
3 - when removing a leaf find the cover first, then recurse down the ply and replace the old leaf with the cover. This saves us a ply walk.

Change-Id: Idd523019e8bb1b6ef527b1f5279a5e24bcf18332
Signed-off-by: Neale Ranns <nranns@cisco.com>

1 files changed, 53 insertions, 72 deletions

diff --git a/src/vnet/ip/ip4_mtrie.h b/src/vnet/ip/ip4_mtrie.h
index c0afc2cf842..128195d3a52 100644
--- a/src/vnet/ip/ip4_mtrie.h
+++ b/src/vnet/ip/ip4_mtrie.h
@@ -52,67 +52,15 @@
 typedef u32 ip4_fib_mtrie_leaf_t;
 
 #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
-#define IP4_FIB_MTRIE_LEAF_ROOT  (0 + 2*0)
 
-always_inline u32
-ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n)
-{
-  return n == IP4_FIB_MTRIE_LEAF_EMPTY;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n)
-{
-  return n != IP4_FIB_MTRIE_LEAF_EMPTY;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
-{
-  return n & 1;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
-{
-  ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
-  return n >> 1;
-}
-
-always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
-{
-  ip4_fib_mtrie_leaf_t l;
-  l = 1 + 2 * adj_index;
-  ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
-  return l;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
-{
-  return (n & 1) == 0;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
-{
-  ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n));
-  return n >> 1;
-}
-
-always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
-{
-  ip4_fib_mtrie_leaf_t l;
-  l = 0 + 2 * i;
-  ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i);
-  return l;
-}
-
-/* One ply of the 4 ply mtrie fib. */
+/**
+ * @brief One ply of the 4 ply mtrie fib.
+ */
 typedef struct
 {
+  /**
+   * The leaves/slots/buckets to be filed with leafs
+   */
   union
   {
     ip4_fib_mtrie_leaf_t leaves[256];
@@ -122,14 +70,25 @@ typedef struct
 #endif
   };
 
-  /* Prefix length for terminal leaves. */
+  /**
+   * Prefix length for leaves/ply.
+   */
   u8 dst_address_bits_of_leaves[256];
 
-  /* Number of non-empty leafs (whether terminal or not). */
+  /**
+   * Number of non-empty leafs (whether terminal or not).
+   */
   i32 n_non_empty_leafs;
 
+  /**
+   * The length of the ply's coviering prefix. Also a measure of its depth
+   * If a leaf in a slot has a mask length longer than this then it is
+   * 'non-empty'. Otherwise it is the value of the cover.
+   */
+  i32 dst_address_bits_base;
+
   /* Pad to cache line boundary. */
-  u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)];
+  u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
 }
 ip4_fib_mtrie_ply_t;
 
@@ -140,9 +99,6 @@ typedef struct
 {
   /* Pool of plies.  Index zero is root ply. */
   ip4_fib_mtrie_ply_t *ply_pool;
-
-  /* Special case leaf for default route 0.0.0.0/0. */
-  ip4_fib_mtrie_leaf_t default_leaf;
 } ip4_fib_mtrie_t;
 
 void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m);
@@ -154,25 +110,50 @@ void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f,
 				  u32 dst_address_length,
 				  u32 adj_index, u32 is_del);
 
-/* Returns adjacency index. */
-u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst);
-
 format_function_t format_ip4_fib_mtrie;
 
+always_inline u32
+ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
+{
+  return n & 1;
+}
+
+always_inline u32
+ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
+{
+  ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
+  return n >> 1;
+}
+
 /* Lookup step.  Processes 1 byte of 4 byte ip4 address. */
 always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_lookup_step (ip4_fib_mtrie_t * m,
+ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m,
 			   ip4_fib_mtrie_leaf_t current_leaf,
 			   const ip4_address_t * dst_address,
 			   u32 dst_address_byte_index)
 {
-  ip4_fib_mtrie_leaf_t next_leaf;
   ip4_fib_mtrie_ply_t *ply;
   uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
 
-  ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1));
-  next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]];
-  next_leaf = current_is_terminal ? current_leaf : next_leaf;
+  if (!current_is_terminal)
+    {
+      ply = m->ply_pool + (current_leaf >> 1);
+      return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
+    }
+
+  return current_leaf;
+}
+
+/* Lookup step.  Processes 1 byte of 4 byte ip4 address. */
+always_inline ip4_fib_mtrie_leaf_t
+ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t * m,
+			       const ip4_address_t * dst_address)
+{
+  ip4_fib_mtrie_leaf_t next_leaf;
+  ip4_fib_mtrie_ply_t *ply;
+
+  ply = m->ply_pool;
+  next_leaf = ply->leaves[dst_address->as_u8[0]];
 
   return next_leaf;
 }