From 7244a706430746facf20a5f047666b74d440cef8 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Fri, 6 Aug 2021 13:12:00 +0000 Subject: ip: [re]introduce the 8-8-8-8 stride MTRIE Type: improvement there's a time-space trade-off between the 16-8-8 and 8-8-8-8 stride. FIB continues to use the 16-8-8. Other features are now free to make the choice. Signed-off-by: Neale Ranns Change-Id: I6691a163486ce62e75e629f6ef0c990f253df8e5 --- src/vnet/ip/ip4_mtrie.h | 58 +++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 54 insertions(+), 4 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 332e34a75ca..ec417c9a9f7 100644 --- a/src/vnet/ip/ip4_mtrie.h +++ b/src/vnet/ip/ip4_mtrie.h @@ -122,7 +122,7 @@ STATIC_ASSERT (0 == sizeof (ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, "IP4 Mtrie ply cache line"); /** - * @brief The mutiway-TRIE. + * @brief The mutiway-TRIE with a 16-8-8 stride. * There is no data associated with the mtrie apart from the top PLY */ typedef struct @@ -135,15 +135,27 @@ typedef struct ip4_mtrie_16_ply_t root_ply; } ip4_mtrie_16_t; +/** + * @brief The mutiway-TRIE with a 8-8-8-8 stride. + * There is no data associated with the mtrie apart from the top PLY + */ +typedef struct +{ + /* pool index of the root ply */ + u32 root_ply; +} ip4_mtrie_8_t; + /** * @brief Initialise an mtrie */ void ip4_mtrie_16_init (ip4_mtrie_16_t *m); +void ip4_mtrie_8_init (ip4_mtrie_8_t *m); /** - * @brief Free an mtrie, It must be emty when free'd + * @brief Free an mtrie, It must be empty when free'd */ void ip4_mtrie_16_free (ip4_mtrie_16_t *m); +void ip4_mtrie_8_free (ip4_mtrie_8_t *m); /** * @brief Add a route/entry to the mtrie @@ -151,6 +163,9 @@ void ip4_mtrie_16_free (ip4_mtrie_16_t *m); void ip4_mtrie_16_route_add (ip4_mtrie_16_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index); +void ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, + u32 dst_address_length, u32 adj_index); + /** * @brief remove a route/entry to the mtrie */ @@ -158,16 +173,21 @@ void ip4_mtrie_16_route_del (ip4_mtrie_16_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index); +void ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, + u32 dst_address_length, u32 adj_index, + u32 cover_address_length, u32 cover_adj_index); /** * @brief return the memory used by the table */ uword ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m); +uword ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m); /** * @brief Format/display the contents of the mtrie */ format_function_t format_ip4_mtrie_16; +format_function_t format_ip4_mtrie_8; /** * @brief A global pool of 8bit stride plys @@ -197,8 +217,7 @@ ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n) * @brief Lookup step. Processes 1 byte of 4 byte ip4 address. */ always_inline ip4_mtrie_leaf_t -ip4_mtrie_16_lookup_step (const ip4_mtrie_16_t *m, - ip4_mtrie_leaf_t current_leaf, +ip4_mtrie_16_lookup_step (ip4_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index) { @@ -229,6 +248,37 @@ ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m, return next_leaf; } +always_inline ip4_mtrie_leaf_t +ip4_mtrie_8_lookup_step (ip4_mtrie_leaf_t current_leaf, + const ip4_address_t *dst_address, + u32 dst_address_byte_index) +{ + ip4_mtrie_8_ply_t *ply; + + uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf); + + if (!current_is_terminal) + { + ply = ip4_ply_pool + (current_leaf >> 1); + return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]); + } + + return current_leaf; +} + +always_inline ip4_mtrie_leaf_t +ip4_mtrie_8_lookup_step_one (const ip4_mtrie_8_t *m, + const ip4_address_t *dst_address) +{ + ip4_mtrie_leaf_t next_leaf; + ip4_mtrie_8_ply_t *ply; + + ply = pool_elt_at_index (ip4_ply_pool, m->root_ply); + next_leaf = ply->leaves[dst_address->as_u8[0]]; + + return next_leaf; +} + #endif /* included_ip_ip4_fib_h */ /* -- cgit 1.2.3-korg