Mtrie optimisations 46/5846/5
authorNeale Ranns <nranns@cisco.com>
Thu, 23 Mar 2017 13:46:01 +0000 (06:46 -0700)
committerDamjan Marion <dmarion.lists@gmail.com>
Wed, 29 Mar 2017 13:00:52 +0000 (13:00 +0000)
commit04a75e3230ab71248fc29a56b9f64bdaee0c17ac
tree85977ecfdf1c4002451cbbcf075694ae1ba1173c
parent9a69a6095f67b8979a02f128f44e449889454273
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>
13 files changed:
src/vnet/adj/adj.c
src/vnet/adj/adj_l2.c
src/vnet/cop/ip4_whitelist.c
src/vnet/dpo/load_balance.c
src/vnet/dpo/lookup_dpo.c
src/vnet/fib/ip4_fib.c
src/vnet/fib/ip4_fib.h
src/vnet/ip/ip4_forward.c
src/vnet/ip/ip4_mtrie.c
src/vnet/ip/ip4_mtrie.h
src/vnet/ip/ip4_source_check.c
src/vnet/ip/ip6_forward.c
src/vnet/mpls/mpls_output.c