diff options
Diffstat (limited to 'src/vnet/fib/ip4_fib.h')
| -rw-r--r-- | src/vnet/fib/ip4_fib.h | 281 |
1 files changed, 198 insertions, 83 deletions
diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h index 7d17baf2545..65fc7775cc4 100644 --- a/src/vnet/fib/ip4_fib.h +++ b/src/vnet/fib/ip4_fib.h @@ -34,77 +34,52 @@ #include <vnet/ip/ip.h> #include <vnet/fib/fib_entry.h> #include <vnet/fib/fib_table.h> -#include <vnet/ip/ip4_mtrie.h> +#include <vnet/fib/ip4_fib_8.h> +#include <vnet/fib/ip4_fib_16.h> -typedef struct ip4_fib_t_ -{ - /** Required for pool_get_aligned */ - CLIB_CACHE_LINE_ALIGN_MARK(cacheline0); - - /** - * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes. - * First member so it's in the first cacheline. - */ - ip4_fib_mtrie_t mtrie; - - /* Hash table for each prefix length mapping. */ - uword *fib_entry_by_dst_address[33]; - - /* Table ID (hash key) for this FIB. */ - u32 table_id; - - /* Index into FIB vector. */ - u32 index; -} ip4_fib_t; - -extern fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); -extern fib_node_index_t ip4_fib_table_lookup_exact_match(const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); - -extern void ip4_fib_table_entry_remove(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); - -extern void ip4_fib_table_entry_insert(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - fib_node_index_t fib_entry_index); -extern void ip4_fib_table_destroy(u32 fib_index); - -extern void ip4_fib_table_fwding_dpo_update(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo); - -extern void ip4_fib_table_fwding_dpo_remove(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo, - fib_node_index_t cover_index); -extern u32 ip4_fib_table_lookup_lb (ip4_fib_t *fib, - const ip4_address_t * dst); +// for the VPP_IP_FIB_MTRIE_16 definition +#include <vpp/vnet/config.h> /** - * @brief Walk all entries in a FIB table - * N.B: This is NOT safe to deletes. If you need to delete walk the whole - * table and store elements in a vector, then delete the elements + * the FIB module uses the 16-8-8 stride trie */ -extern void ip4_fib_table_walk(ip4_fib_t *fib, - fib_table_walk_fn_t fn, - void *ctx); +#ifdef VPP_IP_FIB_MTRIE_16 +typedef ip4_fib_16_t ip4_fib_t; + +#define ip4_fibs ip4_fib_16s +#define ip4_fib_table_lookup ip4_fib_16_table_lookup +#define ip4_fib_table_lookup_exact_match ip4_fib_16_table_lookup_exact_match +#define ip4_fib_table_entry_remove ip4_fib_16_table_entry_remove +#define ip4_fib_table_entry_insert ip4_fib_16_table_entry_insert +#define ip4_fib_table_fwding_dpo_update ip4_fib_16_table_fwding_dpo_update +#define ip4_fib_table_fwding_dpo_remove ip4_fib_16_table_fwding_dpo_remove +#define ip4_fib_table_lookup_lb ip4_fib_16_table_lookup_lb +#define ip4_fib_table_walk ip4_fib_16_table_walk +#define ip4_fib_table_sub_tree_walk ip4_fib_16_table_sub_tree_walk +#define ip4_fib_table_init ip4_fib_16_table_init +#define ip4_fib_table_free ip4_fib_16_table_free +#define ip4_mtrie_memory_usage ip4_mtrie_16_memory_usage +#define format_ip4_mtrie format_ip4_mtrie_16 + +#else +typedef ip4_fib_8_t ip4_fib_t; + +#define ip4_fibs ip4_fib_8s +#define ip4_fib_table_lookup ip4_fib_8_table_lookup +#define ip4_fib_table_lookup_exact_match ip4_fib_8_table_lookup_exact_match +#define ip4_fib_table_entry_remove ip4_fib_8_table_entry_remove +#define ip4_fib_table_entry_insert ip4_fib_8_table_entry_insert +#define ip4_fib_table_fwding_dpo_update ip4_fib_8_table_fwding_dpo_update +#define ip4_fib_table_fwding_dpo_remove ip4_fib_8_table_fwding_dpo_remove +#define ip4_fib_table_lookup_lb ip4_fib_8_table_lookup_lb +#define ip4_fib_table_walk ip4_fib_8_table_walk +#define ip4_fib_table_sub_tree_walk ip4_fib_8_table_sub_tree_walk +#define ip4_fib_table_init ip4_fib_8_table_init +#define ip4_fib_table_free ip4_fib_8_table_free +#define ip4_mtrie_memory_usage ip4_mtrie_8_memory_usage +#define format_ip4_mtrie format_ip4_mtrie_8 -/** - * @brief Walk all entries in a sub-tree of the FIB table - * N.B: This is NOT safe to deletes. If you need to delete walk the whole - * table and store elements in a vector, then delete the elements - */ -extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, - const fib_prefix_t *root, - fib_table_walk_fn_t fn, - void *ctx); +#endif /** * @brief Get the FIB at the given index @@ -112,7 +87,7 @@ extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, static inline ip4_fib_t * ip4_fib_get (u32 index) { - return (pool_elt_at_index(ip4_main.v4_fibs, index)); + return (pool_elt_at_index(ip4_fibs, index)); } always_inline u32 @@ -138,6 +113,7 @@ ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst) extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id, fib_source_t src); extern u32 ip4_fib_table_create_and_lock(fib_source_t src); +extern void ip4_fib_table_destroy(u32 fib_index); extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args); @@ -156,20 +132,108 @@ u32 ip4_fib_index_from_table_id (u32 table_id) extern u32 ip4_fib_table_get_index_for_sw_if_index(u32 sw_if_index); +#ifdef VPP_IP_FIB_MTRIE_16 +always_inline index_t +ip4_fib_forwarding_lookup (u32 fib_index, + const ip4_address_t * addr) +{ + ip4_mtrie_leaf_t leaf; + ip4_mtrie_16_t * mtrie; + + mtrie = &ip4_fib_get(fib_index)->mtrie; + + leaf = ip4_mtrie_16_lookup_step_one (mtrie, addr); + leaf = ip4_mtrie_16_lookup_step (leaf, addr, 2); + leaf = ip4_mtrie_16_lookup_step (leaf, addr, 3); + + return (ip4_mtrie_leaf_get_adj_index(leaf)); +} + +static_always_inline void +ip4_fib_forwarding_lookup_x2 (u32 fib_index0, + u32 fib_index1, + const ip4_address_t * addr0, + const ip4_address_t * addr1, + index_t *lb0, + index_t *lb1) +{ + ip4_mtrie_leaf_t leaf[2]; + ip4_mtrie_16_t * mtrie[2]; + + mtrie[0] = &ip4_fib_get(fib_index0)->mtrie; + mtrie[1] = &ip4_fib_get(fib_index1)->mtrie; + + leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0); + leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1); + leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2); + leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2); + leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3); + leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3); + + *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]); + *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]); +} + +static_always_inline void +ip4_fib_forwarding_lookup_x4 (u32 fib_index0, + u32 fib_index1, + u32 fib_index2, + u32 fib_index3, + const ip4_address_t * addr0, + const ip4_address_t * addr1, + const ip4_address_t * addr2, + const ip4_address_t * addr3, + index_t *lb0, + index_t *lb1, + index_t *lb2, + index_t *lb3) +{ + ip4_mtrie_leaf_t leaf[4]; + ip4_mtrie_16_t * mtrie[4]; + + mtrie[0] = &ip4_fib_get(fib_index0)->mtrie; + mtrie[1] = &ip4_fib_get(fib_index1)->mtrie; + mtrie[2] = &ip4_fib_get(fib_index2)->mtrie; + mtrie[3] = &ip4_fib_get(fib_index3)->mtrie; + + leaf[0] = ip4_mtrie_16_lookup_step_one (mtrie[0], addr0); + leaf[1] = ip4_mtrie_16_lookup_step_one (mtrie[1], addr1); + leaf[2] = ip4_mtrie_16_lookup_step_one (mtrie[2], addr2); + leaf[3] = ip4_mtrie_16_lookup_step_one (mtrie[3], addr3); + + leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 2); + leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 2); + leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 2); + leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 2); + + leaf[0] = ip4_mtrie_16_lookup_step (leaf[0], addr0, 3); + leaf[1] = ip4_mtrie_16_lookup_step (leaf[1], addr1, 3); + leaf[2] = ip4_mtrie_16_lookup_step (leaf[2], addr2, 3); + leaf[3] = ip4_mtrie_16_lookup_step (leaf[3], addr3, 3); + + *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]); + *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]); + *lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]); + *lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]); +} + +#else + always_inline index_t ip4_fib_forwarding_lookup (u32 fib_index, const ip4_address_t * addr) { - ip4_fib_mtrie_leaf_t leaf; - ip4_fib_mtrie_t * mtrie; + ip4_mtrie_leaf_t leaf; + ip4_mtrie_8_t * mtrie; mtrie = &ip4_fib_get(fib_index)->mtrie; - leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr); - leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2); - leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3); + leaf = ip4_mtrie_8_lookup_step_one (mtrie, addr); + leaf = ip4_mtrie_8_lookup_step (leaf, addr, 1); + leaf = ip4_mtrie_8_lookup_step (leaf, addr, 2); + leaf = ip4_mtrie_8_lookup_step (leaf, addr, 3); - return (ip4_fib_mtrie_leaf_get_adj_index(leaf)); + return (ip4_mtrie_leaf_get_adj_index(leaf)); } static_always_inline void @@ -180,22 +244,73 @@ ip4_fib_forwarding_lookup_x2 (u32 fib_index0, index_t *lb0, index_t *lb1) { - ip4_fib_mtrie_leaf_t leaf[2]; - ip4_fib_mtrie_t * mtrie[2]; + ip4_mtrie_leaf_t leaf[2]; + ip4_mtrie_8_t * mtrie[2]; mtrie[0] = &ip4_fib_get(fib_index0)->mtrie; mtrie[1] = &ip4_fib_get(fib_index1)->mtrie; - leaf[0] = ip4_fib_mtrie_lookup_step_one (mtrie[0], addr0); - leaf[1] = ip4_fib_mtrie_lookup_step_one (mtrie[1], addr1); - leaf[0] = ip4_fib_mtrie_lookup_step (mtrie[0], leaf[0], addr0, 2); - leaf[1] = ip4_fib_mtrie_lookup_step (mtrie[1], leaf[1], addr1, 2); - leaf[0] = ip4_fib_mtrie_lookup_step (mtrie[0], leaf[0], addr0, 3); - leaf[1] = ip4_fib_mtrie_lookup_step (mtrie[1], leaf[1], addr1, 3); + leaf[0] = ip4_mtrie_8_lookup_step_one (mtrie[0], addr0); + leaf[1] = ip4_mtrie_8_lookup_step_one (mtrie[1], addr1); + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 1); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 1); + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 2); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 2); + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 3); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 3); + + *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]); + *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]); +} + +static_always_inline void +ip4_fib_forwarding_lookup_x4 (u32 fib_index0, + u32 fib_index1, + u32 fib_index2, + u32 fib_index3, + const ip4_address_t * addr0, + const ip4_address_t * addr1, + const ip4_address_t * addr2, + const ip4_address_t * addr3, + index_t *lb0, + index_t *lb1, + index_t *lb2, + index_t *lb3) +{ + ip4_mtrie_leaf_t leaf[4]; + ip4_mtrie_8_t * mtrie[4]; - *lb0 = ip4_fib_mtrie_leaf_get_adj_index(leaf[0]); - *lb1 = ip4_fib_mtrie_leaf_get_adj_index(leaf[1]); + mtrie[0] = &ip4_fib_get(fib_index0)->mtrie; + mtrie[1] = &ip4_fib_get(fib_index1)->mtrie; + mtrie[2] = &ip4_fib_get(fib_index2)->mtrie; + mtrie[3] = &ip4_fib_get(fib_index3)->mtrie; + + leaf[0] = ip4_mtrie_8_lookup_step_one (mtrie[0], addr0); + leaf[1] = ip4_mtrie_8_lookup_step_one (mtrie[1], addr1); + leaf[2] = ip4_mtrie_8_lookup_step_one (mtrie[2], addr2); + leaf[3] = ip4_mtrie_8_lookup_step_one (mtrie[3], addr3); + + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 1); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 1); + leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 1); + leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 1); + + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 2); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 2); + leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 2); + leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 2); + + leaf[0] = ip4_mtrie_8_lookup_step (leaf[0], addr0, 3); + leaf[1] = ip4_mtrie_8_lookup_step (leaf[1], addr1, 3); + leaf[2] = ip4_mtrie_8_lookup_step (leaf[2], addr2, 3); + leaf[3] = ip4_mtrie_8_lookup_step (leaf[3], addr3, 3); + + *lb0 = ip4_mtrie_leaf_get_adj_index(leaf[0]); + *lb1 = ip4_mtrie_leaf_get_adj_index(leaf[1]); + *lb2 = ip4_mtrie_leaf_get_adj_index(leaf[2]); + *lb3 = ip4_mtrie_leaf_get_adj_index(leaf[3]); } #endif +#endif |