X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvnet%2Fip%2Fip4_mtrie.h;h=16c524745be07348d5e8b0f7b30c000d3b0a601b;hb=e22a7041626cf1ebee7534d84068d48e8671a6ab;hp=c0afc2cf8422e4c2316c091e6f555c24318952fc;hpb=7cd468a3d7dee7d6c92f69a0bb7061ae208ec727;p=vpp.git diff --git a/src/vnet/ip/ip4_mtrie.h b/src/vnet/ip/ip4_mtrie.h index c0afc2cf842..16c524745be 100644 --- a/src/vnet/ip/ip4_mtrie.h +++ b/src/vnet/ip/ip4_mtrie.h @@ -47,132 +47,218 @@ /* ip4 fib leafs: 4 ply 8-8-8-8 mtrie. 1 + 2*adj_index for terminal leaves. - 0 + 2*next_ply_index for non-terminals. + 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_FIB_MTRIE_LEAF_ROOT (0 + 2*0) +#define IP4_MTRIE_LEAF_EMPTY (1 + 2 * 0) -always_inline u32 -ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n) +/** + * @brief the 16 way stride that is the top PLY of the mtrie + * We do not maintain the count of 'real' leaves in this PLY, since + * it is never removed. The FIB will destroy the mtrie and the ply once + * the FIB is destroyed. + */ +#define PLY_16_SIZE (1<<16) +typedef struct ip4_mtrie_16_ply_t_ { - return n == IP4_FIB_MTRIE_LEAF_EMPTY; -} + /** + * The leaves/slots/buckets to be filed with leafs + */ + ip4_mtrie_leaf_t leaves[PLY_16_SIZE]; -always_inline u32 -ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n) -{ - return n != IP4_FIB_MTRIE_LEAF_EMPTY; -} + /** + * Prefix length for terminal leaves. + */ + u8 dst_address_bits_of_leaves[PLY_16_SIZE]; +} ip4_mtrie_16_ply_t; -always_inline u32 -ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n) +/** + * @brief One ply of the 4 ply mtrie fib. + */ +typedef struct ip4_mtrie_8_ply_t_ { - return n & 1; -} + CLIB_CACHE_LINE_ALIGN_MARK (cacheline0); + /** + * The leaves/slots/buckets to be filed with leafs + */ + ip4_mtrie_leaf_t leaves[256]; -always_inline u32 -ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n) + /** + * Prefix length for leaves/ply. + */ + u8 dst_address_bits_of_leaves[256]; + + /** + * Number of non-empty leafs (whether terminal or not). + */ + i32 n_non_empty_leafs; + + /** + * The length of the ply's covering 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; +} ip4_mtrie_8_ply_t; + +STATIC_ASSERT (0 == sizeof (ip4_mtrie_8_ply_t) % CLIB_CACHE_LINE_BYTES, + "IP4 Mtrie ply cache line"); + +/** + * @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 { - ASSERT (ip4_fib_mtrie_leaf_is_terminal (n)); - return n >> 1; -} + /** + * Embed the PLY with the mtrie struct. This means that the Data-plane + * 'get me the mtrie' returns the first ply, and not an indirect 'pointer' + * to it. therefore no cacheline misses in the data-path. + */ + ip4_mtrie_16_ply_t root_ply; +} ip4_mtrie_16_t; -always_inline ip4_fib_mtrie_leaf_t -ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index) +/** + * @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 { - ip4_fib_mtrie_leaf_t l; - l = 1 + 2 * adj_index; - ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index); - return l; -} + /* 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 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 + */ +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_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 + */ +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_next_ply (ip4_fib_mtrie_leaf_t n) +ip4_mtrie_leaf_is_terminal (ip4_mtrie_leaf_t n) { - return (n & 1) == 0; + return n & 1; } +/** + * From the stored slot value extract the LB index value + */ always_inline u32 -ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n) +ip4_mtrie_leaf_get_adj_index (ip4_mtrie_leaf_t n) { - ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n)); + ASSERT (ip4_mtrie_leaf_is_terminal (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. */ -typedef struct +/** + * @brief Lookup step. Processes 1 byte of 4 byte ip4 address. + */ +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) { - union - { - ip4_fib_mtrie_leaf_t leaves[256]; + ip4_mtrie_8_ply_t *ply; -#ifdef CLIB_HAVE_VEC128 - u32x4 leaves_as_u32x4[256 / 4]; -#endif - }; + uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf); - /* Prefix length for terminal leaves. */ - u8 dst_address_bits_of_leaves[256]; + if (!current_is_terminal) + { + ply = ip4_ply_pool + (current_leaf >> 1); + return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]); + } - /* Number of non-empty leafs (whether terminal or not). */ - i32 n_non_empty_leafs; - - /* Pad to cache line boundary. */ - u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)]; + return current_leaf; } -ip4_fib_mtrie_ply_t; - -STATIC_ASSERT (0 == sizeof (ip4_fib_mtrie_ply_t) % CLIB_CACHE_LINE_BYTES, - "IP4 Mtrie ply cache line"); -typedef struct +/** + * @brief Lookup step number 1. Processes 2 bytes of 4 byte ip4 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) { - /* Pool of plies. Index zero is root ply. */ - ip4_fib_mtrie_ply_t *ply_pool; + ip4_mtrie_leaf_t next_leaf; - /* Special case leaf for default route 0.0.0.0/0. */ - ip4_fib_mtrie_leaf_t default_leaf; -} ip4_fib_mtrie_t; + next_leaf = m->root_ply.leaves[dst_address->as_u16[0]]; -void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m); + return next_leaf; +} -struct ip4_fib_t; +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; -void ip4_fib_mtrie_add_del_route (struct ip4_fib_t *f, - ip4_address_t dst_address, - u32 dst_address_length, - u32 adj_index, u32 is_del); + uword current_is_terminal = ip4_mtrie_leaf_is_terminal (current_leaf); -/* Returns adjacency index. */ -u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst); + if (!current_is_terminal) + { + ply = ip4_ply_pool + (current_leaf >> 1); + return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]); + } -format_function_t format_ip4_fib_mtrie; + 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 (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_8_lookup_step_one (const ip4_mtrie_8_t *m, + const ip4_address_t *dst_address) { - 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); + ip4_mtrie_leaf_t next_leaf; + ip4_mtrie_8_ply_t *ply; - 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; + ply = pool_elt_at_index (ip4_ply_pool, m->root_ply); + next_leaf = ply->leaves[dst_address->as_u8[0]]; return next_leaf; }