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