From d2ab1e013026b43bd2d822a6aadf624de4d18174 Mon Sep 17 00:00:00 2001 From: Vladimir Medvedkin Date: Tue, 27 Oct 2020 15:11:28 +0000 Subject: [PATCH] fib6: move lookup definition to header MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Move trie table layout and lookup definition into the private header file. This is necessary for implementing a vectorized lookup function in a separate .с file. Signed-off-by: Vladimir Medvedkin Acked-by: Konstantin Ananyev --- lib/librte_fib/trie.c | 121 ------------------------------------------ lib/librte_fib/trie.h | 117 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 117 insertions(+), 121 deletions(-) diff --git a/lib/librte_fib/trie.c b/lib/librte_fib/trie.c index 11a7ca285d..08a03ab772 100644 --- a/lib/librte_fib/trie.c +++ b/lib/librte_fib/trie.c @@ -11,141 +11,20 @@ #include #include -#include #include #include -#include #include #include #include "trie.h" -/* @internal Total number of tbl24 entries. */ -#define TRIE_TBL24_NUM_ENT (1 << 24) - -/* Maximum depth value possible for IPv6 LPM. */ -#define TRIE_MAX_DEPTH 128 - -/* @internal Number of entries in a tbl8 group. */ -#define TRIE_TBL8_GRP_NUM_ENT 256ULL - -/* @internal Total number of tbl8 groups in the tbl8. */ -#define TRIE_TBL8_NUM_GROUPS 65536 - -/* @internal bitmask with valid and valid_group fields set */ -#define TRIE_EXT_ENT 1 - #define TRIE_NAMESIZE 64 -#define BITMAP_SLAB_BIT_SIZE_LOG2 6 -#define BITMAP_SLAB_BIT_SIZE (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2) -#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) - -struct rte_trie_tbl { - uint32_t number_tbl8s; /**< Total number of tbl8s */ - uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ - uint32_t cur_tbl8s; /**< Current cumber of tbl8s */ - uint64_t def_nh; /**< Default next hop */ - enum rte_fib_trie_nh_sz nh_sz; /**< Size of nexthop entry */ - uint64_t *tbl8; /**< tbl8 table. */ - uint32_t *tbl8_pool; /**< bitmap containing free tbl8 idxes*/ - uint32_t tbl8_pool_pos; - /* tbl24 table. */ - __extension__ uint64_t tbl24[0] __rte_cache_aligned; -}; - enum edge { LEDGE, REDGE }; -static inline uint32_t -get_tbl24_idx(const uint8_t *ip) -{ - return ip[0] << 16|ip[1] << 8|ip[2]; -} - -static inline void * -get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz) -{ - uint32_t tbl24_idx; - - tbl24_idx = get_tbl24_idx(ip); - return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz]; -} - -static inline uint8_t -bits_in_nh(uint8_t nh_sz) -{ - return 8 * (1 << nh_sz); -} - -static inline uint64_t -get_max_nh(uint8_t nh_sz) -{ - return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); -} - -static inline uint64_t -lookup_msk(uint8_t nh_sz) -{ - return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; -} - -static inline uint8_t -get_psd_idx(uint32_t val, uint8_t nh_sz) -{ - return val & ((1 << (3 - nh_sz)) - 1); -} - -static inline uint32_t -get_tbl_pos(uint32_t val, uint8_t nh_sz) -{ - return val >> (3 - nh_sz); -} - -static inline uint64_t -get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz) -{ - return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) * - bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); -} - -static inline void * -get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz) -{ - return (uint8_t *)tbl + (idx << nh_sz); -} - -static inline int -is_entry_extended(uint64_t ent) -{ - return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT; -} - -#define LOOKUP_FUNC(suffix, type, nh_sz) \ -static void rte_trie_lookup_bulk_##suffix(void *p, \ - uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], \ - uint64_t *next_hops, const unsigned int n) \ -{ \ - struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; \ - uint64_t tmp; \ - uint32_t i, j; \ - \ - for (i = 0; i < n; i++) { \ - tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])]; \ - j = 3; \ - while (is_entry_extended(tmp)) { \ - tmp = ((type *)dp->tbl8)[ips[i][j++] + \ - ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)]; \ - } \ - next_hops[i] = tmp >> 1; \ - } \ -} -LOOKUP_FUNC(2b, uint16_t, 1) -LOOKUP_FUNC(4b, uint32_t, 2) -LOOKUP_FUNC(8b, uint64_t, 3) - static inline rte_fib6_lookup_fn_t get_scalar_fn(enum rte_fib_trie_nh_sz nh_sz) { diff --git a/lib/librte_fib/trie.h b/lib/librte_fib/trie.h index e328bef046..a4f429ce54 100644 --- a/lib/librte_fib/trie.h +++ b/lib/librte_fib/trie.h @@ -10,11 +10,128 @@ * @file * RTE IPv6 Longest Prefix Match (LPM) */ +#include +#include #ifdef __cplusplus extern "C" { #endif +/* @internal Total number of tbl24 entries. */ +#define TRIE_TBL24_NUM_ENT (1 << 24) +/* Maximum depth value possible for IPv6 LPM. */ +#define TRIE_MAX_DEPTH 128 +/* @internal Number of entries in a tbl8 group. */ +#define TRIE_TBL8_GRP_NUM_ENT 256ULL +/* @internal Total number of tbl8 groups in the tbl8. */ +#define TRIE_TBL8_NUM_GROUPS 65536 +/* @internal bitmask with valid and valid_group fields set */ +#define TRIE_EXT_ENT 1 + +#define BITMAP_SLAB_BIT_SIZE_LOG2 6 +#define BITMAP_SLAB_BIT_SIZE (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2) +#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) + +struct rte_trie_tbl { + uint32_t number_tbl8s; /**< Total number of tbl8s */ + uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ + uint32_t cur_tbl8s; /**< Current cumber of tbl8s */ + uint64_t def_nh; /**< Default next hop */ + enum rte_fib_trie_nh_sz nh_sz; /**< Size of nexthop entry */ + uint64_t *tbl8; /**< tbl8 table. */ + uint32_t *tbl8_pool; /**< bitmap containing free tbl8 idxes*/ + uint32_t tbl8_pool_pos; + /* tbl24 table. */ + __extension__ uint64_t tbl24[0] __rte_cache_aligned; +}; + +static inline uint32_t +get_tbl24_idx(const uint8_t *ip) +{ + return ip[0] << 16|ip[1] << 8|ip[2]; +} + +static inline void * +get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz) +{ + uint32_t tbl24_idx; + + tbl24_idx = get_tbl24_idx(ip); + return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz]; +} + +static inline uint8_t +bits_in_nh(uint8_t nh_sz) +{ + return 8 * (1 << nh_sz); +} + +static inline uint64_t +get_max_nh(uint8_t nh_sz) +{ + return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); +} + +static inline uint64_t +lookup_msk(uint8_t nh_sz) +{ + return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; +} + +static inline uint8_t +get_psd_idx(uint32_t val, uint8_t nh_sz) +{ + return val & ((1 << (3 - nh_sz)) - 1); +} + +static inline uint32_t +get_tbl_pos(uint32_t val, uint8_t nh_sz) +{ + return val >> (3 - nh_sz); +} + +static inline uint64_t +get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz) +{ + return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline void * +get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz) +{ + return (uint8_t *)tbl + (idx << nh_sz); +} + +static inline int +is_entry_extended(uint64_t ent) +{ + return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT; +} + +#define LOOKUP_FUNC(suffix, type, nh_sz) \ +static inline void rte_trie_lookup_bulk_##suffix(void *p, \ + uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], \ + uint64_t *next_hops, const unsigned int n) \ +{ \ + struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; \ + uint64_t tmp; \ + uint32_t i, j; \ + \ + for (i = 0; i < n; i++) { \ + tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])]; \ + j = 3; \ + while (is_entry_extended(tmp)) { \ + tmp = ((type *)dp->tbl8)[ips[i][j++] + \ + ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)]; \ + } \ + next_hops[i] = tmp >> 1; \ + } \ +} +LOOKUP_FUNC(2b, uint16_t, 1) +LOOKUP_FUNC(4b, uint32_t, 2) +LOOKUP_FUNC(8b, uint64_t, 3) + void * trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf); -- 2.20.1