diff options
Diffstat (limited to 'src/vnet/ip/ip4_mtrie.h')
| -rw-r--r-- | src/vnet/ip/ip4_mtrie.h | 148 |
1 files changed, 90 insertions, 58 deletions
diff --git a/src/vnet/ip/ip4_mtrie.h b/src/vnet/ip/ip4_mtrie.h index 87e2b5892ba..16c524745be 100644 --- a/src/vnet/ip/ip4_mtrie.h +++ b/src/vnet/ip/ip4_mtrie.h @@ -49,9 +49,9 @@ 1 + 2*adj_index for terminal leaves. 0 + 2*next_ply_index for non-terminals, i.e. PLYs 1 => empty (adjacency index of zero is special miss adjacency). */ -typedef u32 ip4_fib_mtrie_leaf_t; +typedef u32 ip4_mtrie_leaf_t; -#define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0) +#define IP4_MTRIE_LEAF_EMPTY (1 + 2 * 0) /** * @brief the 16 way stride that is the top PLY of the mtrie @@ -60,42 +60,29 @@ typedef u32 ip4_fib_mtrie_leaf_t; * the FIB is destroyed. */ #define PLY_16_SIZE (1<<16) -typedef struct ip4_fib_mtrie_16_ply_t_ +typedef struct ip4_mtrie_16_ply_t_ { /** * The leaves/slots/buckets to be filed with leafs */ - union - { - ip4_fib_mtrie_leaf_t leaves[PLY_16_SIZE]; - -#ifdef CLIB_HAVE_VEC128 - u32x4 leaves_as_u32x4[PLY_16_SIZE / 4]; -#endif - }; + ip4_mtrie_leaf_t leaves[PLY_16_SIZE]; /** * Prefix length for terminal leaves. */ u8 dst_address_bits_of_leaves[PLY_16_SIZE]; -} ip4_fib_mtrie_16_ply_t; +} ip4_mtrie_16_ply_t; /** * @brief One ply of the 4 ply mtrie fib. */ -typedef struct ip4_fib_mtrie_8_ply_t_ +typedef struct ip4_mtrie_8_ply_t_ { + CLIB_CACHE_LINE_ALIGN_MARK (cacheline0); /** * The leaves/slots/buckets to be filed with leafs */ - union - { - ip4_fib_mtrie_leaf_t leaves[256]; - -#ifdef CLIB_HAVE_VEC128 - u32x4 leaves_as_u32x4[256 / 4]; -#endif - }; + ip4_mtrie_leaf_t leaves[256]; /** * Prefix length for leaves/ply. @@ -113,17 +100,13 @@ typedef struct ip4_fib_mtrie_8_ply_t_ * 'non-empty'. Otherwise it is the value of the cover. */ i32 dst_address_bits_base; +} ip4_mtrie_8_ply_t; - /* Pad to cache line boundary. */ - u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)]; -} -ip4_fib_mtrie_8_ply_t; - -STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, +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 @@ -133,54 +116,73 @@ typedef struct * 'get me the mtrie' returns the first ply, and not an indirect 'pointer' * to it. therefore no cacheline misses in the data-path. */ - ip4_fib_mtrie_16_ply_t root_ply; -} ip4_fib_mtrie_t; + 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_init (ip4_fib_mtrie_t * m); +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_free (ip4_fib_mtrie_t * m); +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 */ -void ip4_fib_mtrie_route_add (ip4_fib_mtrie_t * m, - const ip4_address_t * dst_address, - u32 dst_address_length, u32 adj_index); +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 */ -void ip4_fib_mtrie_route_del (ip4_fib_mtrie_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_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_fib_mtrie_memory_usage (ip4_fib_mtrie_t * m); +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_fib_mtrie; +format_function_t format_ip4_mtrie_16; +format_function_t format_ip4_mtrie_8; /** * @brief A global pool of 8bit stride plys */ -extern ip4_fib_mtrie_8_ply_t *ip4_ply_pool; +extern ip4_mtrie_8_ply_t *ip4_ply_pool; /** * Is the leaf terminal (i.e. an LB index) or non-terminal (i.e. a PLY index) */ always_inline u32 -ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n) +ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n) { return n & 1; } @@ -189,24 +191,23 @@ ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n) * From the stored slot value extract the LB index value */ always_inline u32 -ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n) +ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n) { - ASSERT (ip4_fib_mtrie_leaf_is_terminal (n)); + ASSERT (ip4_mtrie_leaf_is_terminal (n)); return n >> 1; } /** * @brief Lookup step. Processes 1 byte of 4 byte ip4 address. */ -always_inline ip4_fib_mtrie_leaf_t -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) +always_inline ip4_mtrie_leaf_t +ip4_mtrie_16_lookup_step (ip4_mtrie_leaf_t current_leaf, + const ip4_address_t *dst_address, + u32 dst_address_byte_index) { - ip4_fib_mtrie_8_ply_t *ply; + ip4_mtrie_8_ply_t *ply; - uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf); + uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf); if (!current_is_terminal) { @@ -220,17 +221,48 @@ ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m, /** * @brief Lookup step number 1. Processes 2 bytes 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) +always_inline ip4_mtrie_leaf_t +ip4_mtrie_16_lookup_step_one (const ip4_mtrie_16_t *m, + const ip4_address_t *dst_address) { - ip4_fib_mtrie_leaf_t next_leaf; + ip4_mtrie_leaf_t next_leaf; next_leaf = m->root_ply.leaves[dst_address->as_u16[0]]; 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 */ /* |