From 04a75e3230ab71248fc29a56b9f64bdaee0c17ac Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Thu, 23 Mar 2017 06:46:01 -0700 Subject: 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 --- src/vnet/dpo/lookup_dpo.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-) (limited to 'src/vnet/dpo/lookup_dpo.c') diff --git a/src/vnet/dpo/lookup_dpo.c b/src/vnet/dpo/lookup_dpo.c index 96fedd27ce9..3726c8fe0d4 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); } -- cgit 1.2.3-korg