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, 1 insertions, 5 deletions

diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h
index a8dc68b5..243fd77f 100644
--- a/src/vnet/fib/ip4_fib.h
+++ b/src/vnet/fib/ip4_fib.h
@@ -133,15 +133,11 @@ ip4_fib_forwarding_lookup (u32 fib_index,
 
     mtrie = &ip4_fib_get(fib_index)->mtrie;
 
-    leaf = IP4_FIB_MTRIE_LEAF_ROOT;
-    leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 0);
+    leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
     leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 1);
     leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
     leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
 
-    /* Handle default route. */
-    leaf = (leaf == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie->default_leaf : leaf);
-    
     return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
 }