Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause 2 : : * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com> 3 : : * Copyright(c) 2019 Intel Corporation 4 : : */ 5 : : 6 : : #ifndef _TRIE_H_ 7 : : #define _TRIE_H_ 8 : : 9 : : #include <stdalign.h> 10 : : 11 : : /** 12 : : * @file 13 : : * RTE IPv6 Longest Prefix Match (LPM) 14 : : */ 15 : : 16 : : /* @internal Total number of tbl24 entries. */ 17 : : #define TRIE_TBL24_NUM_ENT (1 << 24) 18 : : /* Maximum depth value possible for IPv6 LPM. */ 19 : : #define TRIE_MAX_DEPTH 128 20 : : /* @internal Number of entries in a tbl8 group. */ 21 : : #define TRIE_TBL8_GRP_NUM_ENT 256ULL 22 : : /* @internal Total number of tbl8 groups in the tbl8. */ 23 : : #define TRIE_TBL8_NUM_GROUPS 65536 24 : : /* @internal bitmask with valid and valid_group fields set */ 25 : : #define TRIE_EXT_ENT 1 26 : : 27 : : #define BITMAP_SLAB_BIT_SIZE_LOG2 6 28 : : #define BITMAP_SLAB_BIT_SIZE (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2) 29 : : #define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) 30 : : 31 : : struct rte_trie_tbl { 32 : : uint32_t number_tbl8s; /**< Total number of tbl8s */ 33 : : uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ 34 : : uint32_t cur_tbl8s; /**< Current cumber of tbl8s */ 35 : : uint64_t def_nh; /**< Default next hop */ 36 : : enum rte_fib_trie_nh_sz nh_sz; /**< Size of nexthop entry */ 37 : : uint64_t *tbl8; /**< tbl8 table. */ 38 : : uint32_t *tbl8_pool; /**< bitmap containing free tbl8 idxes*/ 39 : : uint32_t tbl8_pool_pos; 40 : : /* tbl24 table. */ 41 : : __extension__ alignas(RTE_CACHE_LINE_SIZE) uint64_t tbl24[0]; 42 : : }; 43 : : 44 : : static inline uint32_t 45 : : get_tbl24_idx(const uint8_t *ip) 46 : : { 47 : 200067 : return ip[0] << 16|ip[1] << 8|ip[2]; 48 : : } 49 : : 50 : : static inline void * 51 : : get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz) 52 : : { 53 : : uint32_t tbl24_idx; 54 : : 55 : : tbl24_idx = get_tbl24_idx(ip); 56 : 1536 : return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz]; 57 : : } 58 : : 59 : : static inline uint8_t 60 : : bits_in_nh(uint8_t nh_sz) 61 : : { 62 : 10510 : return 8 * (1 << nh_sz); 63 : : } 64 : : 65 : : static inline uint64_t 66 : : get_max_nh(uint8_t nh_sz) 67 : : { 68 [ + - + - ]: 1540 : return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); 69 : : } 70 : : 71 : : static inline uint64_t 72 : : lookup_msk(uint8_t nh_sz) 73 : : { 74 : 8970 : return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; 75 : : } 76 : : 77 : : static inline uint8_t 78 : : get_psd_idx(uint32_t val, uint8_t nh_sz) 79 : : { 80 : 8970 : return val & ((1 << (3 - nh_sz)) - 1); 81 : : } 82 : : 83 : : static inline uint32_t 84 : : get_tbl_pos(uint32_t val, uint8_t nh_sz) 85 : : { 86 : 8970 : return val >> (3 - nh_sz); 87 : : } 88 : : 89 : : static inline uint64_t 90 : : get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz) 91 : : { 92 : 8970 : return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) * 93 [ + + ]: 8970 : bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 94 : : } 95 : : 96 : : static inline void * 97 : : get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz) 98 : : { 99 [ + + ]: 24132 : return (uint8_t *)tbl + (idx << nh_sz); 100 : : } 101 : : 102 : : static inline int 103 : : is_entry_extended(uint64_t ent) 104 : : { 105 : 1082037 : return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT; 106 : : } 107 : : 108 : : #define LOOKUP_FUNC(suffix, type, nh_sz) \ 109 : : static inline void rte_trie_lookup_bulk_##suffix(void *p, \ 110 : : uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], \ 111 : : uint64_t *next_hops, const unsigned int n) \ 112 : : { \ 113 : : struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; \ 114 : : uint64_t tmp; \ 115 : : uint32_t i, j; \ 116 : : \ 117 : : for (i = 0; i < n; i++) { \ 118 : : tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])]; \ 119 : : j = 3; \ 120 : : while (is_entry_extended(tmp)) { \ 121 : : tmp = ((type *)dp->tbl8)[ips[i][j++] + \ 122 : : ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)]; \ 123 : : } \ 124 : : next_hops[i] = tmp >> 1; \ 125 : : } \ 126 : : } 127 [ + + + + ]: 361705 : LOOKUP_FUNC(2b, uint16_t, 1) 128 [ + + + + ]: 361705 : LOOKUP_FUNC(4b, uint32_t, 2) 129 [ + + + + ]: 361705 : LOOKUP_FUNC(8b, uint64_t, 3) 130 : : 131 : : void * 132 : : trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf); 133 : : 134 : : void 135 : : trie_free(void *p); 136 : : 137 : : rte_fib6_lookup_fn_t 138 : : trie_get_lookup_fn(void *p, enum rte_fib6_lookup_type type); 139 : : 140 : : int 141 : : trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], 142 : : uint8_t depth, uint64_t next_hop, int op); 143 : : 144 : : #endif /* _TRIE_H_ */