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 _DIR24_8_H_ 7 #define _DIR24_8_H_ 8 9 #include <rte_prefetch.h> 10 #include <rte_branch_prediction.h> 11 12 /** 13 * @file 14 * DIR24_8 algorithm 15 */ 16 17 #ifdef __cplusplus 18 extern "C" { 19 #endif 20 21 #define DIR24_8_TBL24_NUM_ENT (1 << 24) 22 #define DIR24_8_TBL8_GRP_NUM_ENT 256U 23 #define DIR24_8_EXT_ENT 1 24 #define DIR24_8_TBL24_MASK 0xffffff00 25 26 #define BITMAP_SLAB_BIT_SIZE_LOG2 6 27 #define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2) 28 #define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) 29 30 struct dir24_8_tbl { 31 uint32_t number_tbl8s; /**< Total number of tbl8s */ 32 uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ 33 uint32_t cur_tbl8s; /**< Current number of tbl8s */ 34 enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */ 35 uint64_t def_nh; /**< Default next hop */ 36 uint64_t *tbl8; /**< tbl8 table. */ 37 uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/ 38 /* tbl24 table. */ 39 __extension__ uint64_t tbl24[0] __rte_cache_aligned; 40 }; 41 42 static inline void * 43 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) 44 { 45 return (void *)&((uint8_t *)dp->tbl24)[(ip & 46 DIR24_8_TBL24_MASK) >> (8 - nh_sz)]; 47 } 48 49 static inline uint8_t 50 bits_in_nh(uint8_t nh_sz) 51 { 52 return 8 * (1 << nh_sz); 53 } 54 55 static inline uint64_t 56 get_max_nh(uint8_t nh_sz) 57 { 58 return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); 59 } 60 61 static inline uint32_t 62 get_tbl24_idx(uint32_t ip) 63 { 64 return ip >> 8; 65 } 66 67 static inline uint32_t 68 get_tbl8_idx(uint32_t res, uint32_t ip) 69 { 70 return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip; 71 } 72 73 static inline uint64_t 74 lookup_msk(uint8_t nh_sz) 75 { 76 return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; 77 } 78 79 static inline uint8_t 80 get_psd_idx(uint32_t val, uint8_t nh_sz) 81 { 82 return val & ((1 << (3 - nh_sz)) - 1); 83 } 84 85 static inline uint32_t 86 get_tbl_idx(uint32_t val, uint8_t nh_sz) 87 { 88 return val >> (3 - nh_sz); 89 } 90 91 static inline uint64_t 92 get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) 93 { 94 return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >> 95 (get_psd_idx(get_tbl24_idx(ip), nh_sz) * 96 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 97 } 98 99 static inline uint64_t 100 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz) 101 { 102 return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >> 103 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) * 104 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 105 } 106 107 static inline int 108 is_entry_extended(uint64_t ent) 109 { 110 return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT; 111 } 112 113 #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \ 114 static inline void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \ 115 uint64_t *next_hops, const unsigned int n) \ 116 { \ 117 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \ 118 uint64_t tmp; \ 119 uint32_t i; \ 120 uint32_t prefetch_offset = \ 121 RTE_MIN((unsigned int)bulk_prefetch, n); \ 122 \ 123 for (i = 0; i < prefetch_offset; i++) \ 124 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \ 125 for (i = 0; i < (n - prefetch_offset); i++) { \ 126 rte_prefetch0(get_tbl24_p(dp, \ 127 ips[i + prefetch_offset], nh_sz)); \ 128 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ 129 if (unlikely(is_entry_extended(tmp))) \ 130 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ 131 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ 132 next_hops[i] = tmp >> 1; \ 133 } \ 134 for (; i < n; i++) { \ 135 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ 136 if (unlikely(is_entry_extended(tmp))) \ 137 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ 138 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ 139 next_hops[i] = tmp >> 1; \ 140 } \ 141 } \ 142 143 LOOKUP_FUNC(1b, uint8_t, 5, 0) 144 LOOKUP_FUNC(2b, uint16_t, 6, 1) 145 LOOKUP_FUNC(4b, uint32_t, 15, 2) 146 LOOKUP_FUNC(8b, uint64_t, 12, 3) 147 148 static inline void 149 dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips, 150 uint64_t *next_hops, const unsigned int n, uint8_t nh_sz) 151 { 152 uint64_t tmp; 153 uint32_t i; 154 uint32_t prefetch_offset = RTE_MIN(15U, n); 155 156 for (i = 0; i < prefetch_offset; i++) 157 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 158 for (i = 0; i < (n - prefetch_offset); i++) { 159 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 160 nh_sz)); 161 tmp = get_tbl24(dp, ips[i], nh_sz); 162 if (unlikely(is_entry_extended(tmp))) 163 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 164 165 next_hops[i] = tmp >> 1; 166 } 167 for (; i < n; i++) { 168 tmp = get_tbl24(dp, ips[i], nh_sz); 169 if (unlikely(is_entry_extended(tmp))) 170 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 171 172 next_hops[i] = tmp >> 1; 173 } 174 } 175 176 static inline void 177 dir24_8_lookup_bulk_0(void *p, const uint32_t *ips, 178 uint64_t *next_hops, const unsigned int n) 179 { 180 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 181 182 dir24_8_lookup_bulk(dp, ips, next_hops, n, 0); 183 } 184 185 static inline void 186 dir24_8_lookup_bulk_1(void *p, const uint32_t *ips, 187 uint64_t *next_hops, const unsigned int n) 188 { 189 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 190 191 dir24_8_lookup_bulk(dp, ips, next_hops, n, 1); 192 } 193 194 static inline void 195 dir24_8_lookup_bulk_2(void *p, const uint32_t *ips, 196 uint64_t *next_hops, const unsigned int n) 197 { 198 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 199 200 dir24_8_lookup_bulk(dp, ips, next_hops, n, 2); 201 } 202 203 static inline void 204 dir24_8_lookup_bulk_3(void *p, const uint32_t *ips, 205 uint64_t *next_hops, const unsigned int n) 206 { 207 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 208 209 dir24_8_lookup_bulk(dp, ips, next_hops, n, 3); 210 } 211 212 static inline void 213 dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips, 214 uint64_t *next_hops, const unsigned int n) 215 { 216 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 217 uint64_t tmp; 218 uint32_t i; 219 uint32_t prefetch_offset = RTE_MIN(15U, n); 220 uint8_t nh_sz = dp->nh_sz; 221 222 for (i = 0; i < prefetch_offset; i++) 223 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 224 for (i = 0; i < (n - prefetch_offset); i++) { 225 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 226 nh_sz)); 227 tmp = get_tbl24(dp, ips[i], nh_sz); 228 if (unlikely(is_entry_extended(tmp))) 229 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 230 231 next_hops[i] = tmp >> 1; 232 } 233 for (; i < n; i++) { 234 tmp = get_tbl24(dp, ips[i], nh_sz); 235 if (unlikely(is_entry_extended(tmp))) 236 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 237 238 next_hops[i] = tmp >> 1; 239 } 240 } 241 242 void * 243 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf); 244 245 void 246 dir24_8_free(void *p); 247 248 rte_fib_lookup_fn_t 249 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type); 250 251 int 252 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, 253 uint64_t next_hop, int op); 254 255 #ifdef __cplusplus 256 } 257 #endif 258 259 #endif /* _DIR24_8_H_ */ 260