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/ip/ip4_mtrie.h | 125 ++++++++++++++++++++---------------------------- 1 file changed, 53 insertions(+), 72 deletions(-) (limited to 'src/vnet/ip/ip4_mtrie.h') diff --git a/src/vnet/ip/ip4_mtrie.h b/src/vnet/ip/ip4_mtrie.h index c0afc2cf842..128195d3a52 100644 --- a/src/vnet/ip/ip4_mtrie.h +++ b/src/vnet/ip/ip4_mtrie.h @@ -52,67 +52,15 @@ typedef u32 ip4_fib_mtrie_leaf_t; #define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0) -#define IP4_FIB_MTRIE_LEAF_ROOT (0 + 2*0) -always_inline u32 -ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n) -{ - return n == IP4_FIB_MTRIE_LEAF_EMPTY; -} - -always_inline u32 -ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n) -{ - return n != IP4_FIB_MTRIE_LEAF_EMPTY; -} - -always_inline u32 -ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n) -{ - return n & 1; -} - -always_inline u32 -ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n) -{ - ASSERT (ip4_fib_mtrie_leaf_is_terminal (n)); - return n >> 1; -} - -always_inline ip4_fib_mtrie_leaf_t -ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index) -{ - ip4_fib_mtrie_leaf_t l; - l = 1 + 2 * adj_index; - ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index); - return l; -} - -always_inline u32 -ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n) -{ - return (n & 1) == 0; -} - -always_inline u32 -ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n) -{ - ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n)); - return n >> 1; -} - -always_inline ip4_fib_mtrie_leaf_t -ip4_fib_mtrie_leaf_set_next_ply_index (u32 i) -{ - ip4_fib_mtrie_leaf_t l; - l = 0 + 2 * i; - ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i); - return l; -} - -/* One ply of the 4 ply mtrie fib. */ +/** + * @brief One ply of the 4 ply mtrie fib. + */ typedef struct { + /** + * The leaves/slots/buckets to be filed with leafs + */ union { ip4_fib_mtrie_leaf_t leaves[256]; @@ -122,14 +70,25 @@ typedef struct #endif }; - /* Prefix length for terminal leaves. */ + /** + * Prefix length for leaves/ply. + */ u8 dst_address_bits_of_leaves[256]; - /* Number of non-empty leafs (whether terminal or not). */ + /** + * Number of non-empty leafs (whether terminal or not). + */ i32 n_non_empty_leafs; + /** + * The length of the ply's coviering prefix. Also a measure of its depth + * If a leaf in a slot has a mask length longer than this then it is + * 'non-empty'. Otherwise it is the value of the cover. + */ + i32 dst_address_bits_base; + /* Pad to cache line boundary. */ - u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)]; + u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)]; } ip4_fib_mtrie_ply_t; @@ -140,9 +99,6 @@ typedef struct { /* Pool of plies. Index zero is root ply. */ ip4_fib_mtrie_ply_t *ply_pool; - - /* Special case leaf for default route 0.0.0.0/0. */ - ip4_fib_mtrie_leaf_t default_leaf; } ip4_fib_mtrie_t; void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m); @@ -154,25 +110,50 @@ void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f, u32 dst_address_length, u32 adj_index, u32 is_del); -/* Returns adjacency index. */ -u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst); - format_function_t format_ip4_fib_mtrie; +always_inline u32 +ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n) +{ + return n & 1; +} + +always_inline u32 +ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n) +{ + ASSERT (ip4_fib_mtrie_leaf_is_terminal (n)); + return n >> 1; +} + /* Lookup step. Processes 1 byte of 4 byte ip4 address. */ always_inline ip4_fib_mtrie_leaf_t -ip4_fib_mtrie_lookup_step (ip4_fib_mtrie_t * m, +ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t * dst_address, u32 dst_address_byte_index) { - ip4_fib_mtrie_leaf_t next_leaf; ip4_fib_mtrie_ply_t *ply; uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf); - ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1)); - next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]]; - next_leaf = current_is_terminal ? current_leaf : next_leaf; + if (!current_is_terminal) + { + ply = m->ply_pool + (current_leaf >> 1); + return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]); + } + + return current_leaf; +} + +/* Lookup step. Processes 1 byte of 4 byte ip4 address. */ +always_inline ip4_fib_mtrie_leaf_t +ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t * m, + const ip4_address_t * dst_address) +{ + ip4_fib_mtrie_leaf_t next_leaf; + ip4_fib_mtrie_ply_t *ply; + + ply = m->ply_pool; + next_leaf = ply->leaves[dst_address->as_u8[0]]; return next_leaf; } -- cgit 1.2.3-korg