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

diff --git a/src/vnet/fib/ip4_fib.c b/src/vnet/fib/ip4_fib.c
index e8211c80d20..a7915620b37 100644
--- a/src/vnet/fib/ip4_fib.c
+++ b/src/vnet/fib/ip4_fib.c
@@ -158,8 +158,9 @@ ip4_fib_table_destroy (ip4_fib_t *fib)
 
     /*
      * remove all the specials we added when the table was created.
+     * In reverse order so the default route is last.
      */
-    for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
+    for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--)
     {
 	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;