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