From a70b015ceeee158eac0d9b33d12c596e1af409b3 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Tue, 10 Aug 2021 14:37:11 +0000 Subject: fib: Compiile time option to use 8-8-8-8 stride tries for FIB rather than 16-8-8-8 Type: feature the memory trade-off is: for 8-8-8-8 tries DBGvpp# sh ip fib mtrie mem ipv4-VRF:0 mtrie:8068 hash:3499 totals: mtrie:8068 hash:3499 all:11567 for 16-8-8 DBGvpp# sh ip fib mtrie mem ipv4-VRF:0 mtrie:333056 hash:3499 totals: mtrie:333056 hash:3499 all:336555 Signed-off-by: Neale Ranns Change-Id: I5271a4322d786de6e47613cff9bd432762dbed2a --- src/vnet/CMakeLists.txt | 2 + src/vnet/fib/ip4_fib.h | 121 +++++++++++++++++++++++++++++++++++++++++++++++ src/vpp/vnet/config.h.in | 1 + 3 files changed, 124 insertions(+) diff --git a/src/vnet/CMakeLists.txt b/src/vnet/CMakeLists.txt index df23738013d..66a4abc3a41 100644 --- a/src/vnet/CMakeLists.txt +++ b/src/vnet/CMakeLists.txt @@ -16,6 +16,8 @@ unset(VNET_HEADERS) unset(VNET_API_FILES) unset(VNET_MULTIARCH_SOURCES) +option(VPP_IP_FIB_MTRIE_16 "IP FIB's MTRIE Stride is 16-8-8 (if not set it's 8-8-8-8)" ON) + ############################################################################## # Generic stuff ############################################################################## diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h index 0f6911dd3aa..65fc7775cc4 100644 --- a/src/vnet/fib/ip4_fib.h +++ b/src/vnet/fib/ip4_fib.h @@ -37,9 +37,13 @@ #include #include +// for the VPP_IP_FIB_MTRIE_16 definition +#include + /** * the FIB module uses the 16-8-8 stride trie */ +#ifdef VPP_IP_FIB_MTRIE_16 typedef ip4_fib_16_t ip4_fib_t; #define ip4_fibs ip4_fib_16s @@ -57,6 +61,26 @@ typedef ip4_fib_16_t ip4_fib_t; #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 + +#endif + /** * @brief Get the FIB at the given index */ @@ -108,6 +132,7 @@ 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) @@ -192,4 +217,100 @@ ip4_fib_forwarding_lookup_x4 (u32 fib_index0, *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_mtrie_leaf_t leaf; + ip4_mtrie_8_t * mtrie; + + mtrie = &ip4_fib_get(fib_index)->mtrie; + + 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_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_8_t * mtrie[2]; + + mtrie[0] = &ip4_fib_get(fib_index0)->mtrie; + mtrie[1] = &ip4_fib_get(fib_index1)->mtrie; + + 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]; + + 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 diff --git a/src/vpp/vnet/config.h.in b/src/vpp/vnet/config.h.in index 8eee6da4913..5f2749d2c34 100644 --- a/src/vpp/vnet/config.h.in +++ b/src/vpp/vnet/config.h.in @@ -17,5 +17,6 @@ #define included_vpp_vnet_config_h #define VPP_SANITIZE_ADDR_OPTIONS "@VPP_SANITIZE_ADDR_OPTIONS@" +#define VPP_IP_FIB_MTRIE_16 "@VPP_IP_FIB_MTRIE_16@" #endif -- cgit 1.2.3-korg