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>

2 files changed, 11 insertions, 12 deletions

diff --git a/src/vnet/dpo/load_balance.c b/src/vnet/dpo/load_balance.c
index e9fb5d9d..d5e98e4e 100644
--- a/src/vnet/dpo/load_balance.c
+++ b/src/vnet/dpo/load_balance.c
@@ -829,6 +829,13 @@ load_balance_module_init (void)
 {
     dpo_register(DPO_LOAD_BALANCE, &lb_vft, load_balance_nodes);
 
+    /*
+     * Special LB with index zero. we need to define this since the v4 mtrie
+     * assumes an index of 0 implies the ply is empty. therefore all 'real'
+     * adjs need a non-zero index.
+     */
+    load_balance_create(0, DPO_PROTO_IP4, 0);
+
     load_balance_map_module_init();
 }
 
diff --git a/src/vnet/dpo/lookup_dpo.c b/src/vnet/dpo/lookup_dpo.c
index 96fedd27..3726c8fe 100644
--- a/src/vnet/dpo/lookup_dpo.c
+++ b/src/vnet/dpo/lookup_dpo.c
@@ -205,19 +205,16 @@ ip4_src_fib_lookup_one (u32 src_fib_index0,
                         const ip4_address_t * addr0,
                         u32 * src_adj_index0)
 {
-    ip4_fib_mtrie_leaf_t leaf0, leaf1;
+    ip4_fib_mtrie_leaf_t leaf0;
     ip4_fib_mtrie_t * mtrie0;
 
     mtrie0 = &ip4_fib_get (src_fib_index0)->mtrie;
 
-    leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-    leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
+    leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, addr0);
     leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
     leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 2);
     leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
 
-    /* Handle default route. */
-    leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
     src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
 }
 
@@ -235,10 +232,8 @@ ip4_src_fib_lookup_two (u32 src_fib_index0,
     mtrie0 = &ip4_fib_get (src_fib_index0)->mtrie;
     mtrie1 = &ip4_fib_get (src_fib_index1)->mtrie;
 
-    leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-
-    leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
-    leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 0);
+    leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, addr0);
+    leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, addr1);
 
     leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
     leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 1);
@@ -249,9 +244,6 @@ ip4_src_fib_lookup_two (u32 src_fib_index0,
     leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
     leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 3);
 
-    /* Handle default route. */
-    leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
-    leaf1 = (leaf1 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie1->default_leaf : leaf1);
     src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
     src_adj_index1[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf1);
 }