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 <stdalign.h> 10 #include <stdbool.h> 11 12 #include <rte_byteorder.h> 13 #include <rte_prefetch.h> 14 #include <rte_branch_prediction.h> 15 #include <rte_rcu_qsbr.h> 16 17 /** 18 * @file 19 * DIR24_8 algorithm 20 */ 21 22 #define DIR24_8_TBL24_NUM_ENT (1 << 24) 23 #define DIR24_8_TBL8_GRP_NUM_ENT 256U 24 #define DIR24_8_EXT_ENT 1 25 #define DIR24_8_TBL24_MASK 0xffffff00 26 27 #define BITMAP_SLAB_BIT_SIZE_LOG2 6 28 #define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2) 29 #define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) 30 31 struct dir24_8_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 number of tbl8s */ 35 enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */ 36 /* RCU config. */ 37 enum rte_fib_qsbr_mode rcu_mode;/* Blocking, defer queue. */ 38 struct rte_rcu_qsbr *v; /* RCU QSBR variable. */ 39 struct rte_rcu_qsbr_dq *dq; /* RCU QSBR defer queue. */ 40 uint64_t def_nh; /**< Default next hop */ 41 uint64_t *tbl8; /**< tbl8 table. */ 42 uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/ 43 /* tbl24 table. */ 44 alignas(RTE_CACHE_LINE_SIZE) uint64_t tbl24[]; 45 }; 46 47 static inline void * 48 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) 49 { 50 return (void *)&((uint8_t *)dp->tbl24)[(ip & 51 DIR24_8_TBL24_MASK) >> (8 - nh_sz)]; 52 } 53 54 static inline uint8_t 55 bits_in_nh(uint8_t nh_sz) 56 { 57 return 8 * (1 << nh_sz); 58 } 59 60 static inline uint64_t 61 get_max_nh(uint8_t nh_sz) 62 { 63 return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); 64 } 65 66 static inline uint32_t 67 get_tbl24_idx(uint32_t ip) 68 { 69 return ip >> 8; 70 } 71 72 static inline uint32_t 73 get_tbl8_idx(uint32_t res, uint32_t ip) 74 { 75 return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip; 76 } 77 78 static inline uint64_t 79 lookup_msk(uint8_t nh_sz) 80 { 81 return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; 82 } 83 84 static inline uint8_t 85 get_psd_idx(uint32_t val, uint8_t nh_sz) 86 { 87 return val & ((1 << (3 - nh_sz)) - 1); 88 } 89 90 static inline uint32_t 91 get_tbl_idx(uint32_t val, uint8_t nh_sz) 92 { 93 return val >> (3 - nh_sz); 94 } 95 96 static inline uint64_t 97 get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) 98 { 99 return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >> 100 (get_psd_idx(get_tbl24_idx(ip), nh_sz) * 101 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 102 } 103 104 static inline uint64_t 105 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz) 106 { 107 return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >> 108 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) * 109 bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); 110 } 111 112 static inline int 113 is_entry_extended(uint64_t ent) 114 { 115 return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT; 116 } 117 118 #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \ 119 static inline void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \ 120 uint64_t *next_hops, const unsigned int n) \ 121 { \ 122 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \ 123 uint64_t tmp; \ 124 uint32_t i; \ 125 uint32_t prefetch_offset = \ 126 RTE_MIN((unsigned int)bulk_prefetch, n); \ 127 \ 128 for (i = 0; i < prefetch_offset; i++) \ 129 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \ 130 for (i = 0; i < (n - prefetch_offset); i++) { \ 131 rte_prefetch0(get_tbl24_p(dp, \ 132 ips[i + prefetch_offset], nh_sz)); \ 133 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ 134 if (unlikely(is_entry_extended(tmp))) \ 135 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ 136 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ 137 next_hops[i] = tmp >> 1; \ 138 } \ 139 for (; i < n; i++) { \ 140 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ 141 if (unlikely(is_entry_extended(tmp))) \ 142 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ 143 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ 144 next_hops[i] = tmp >> 1; \ 145 } \ 146 } \ 147 148 LOOKUP_FUNC(1b, uint8_t, 5, 0) 149 LOOKUP_FUNC(2b, uint16_t, 6, 1) 150 LOOKUP_FUNC(4b, uint32_t, 15, 2) 151 LOOKUP_FUNC(8b, uint64_t, 12, 3) 152 153 static inline void 154 dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips, 155 uint64_t *next_hops, const unsigned int n, uint8_t nh_sz) 156 { 157 uint64_t tmp; 158 uint32_t i; 159 uint32_t prefetch_offset = RTE_MIN(15U, n); 160 161 for (i = 0; i < prefetch_offset; i++) 162 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 163 for (i = 0; i < (n - prefetch_offset); i++) { 164 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 165 nh_sz)); 166 tmp = get_tbl24(dp, ips[i], nh_sz); 167 if (unlikely(is_entry_extended(tmp))) 168 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 169 170 next_hops[i] = tmp >> 1; 171 } 172 for (; i < n; i++) { 173 tmp = get_tbl24(dp, ips[i], nh_sz); 174 if (unlikely(is_entry_extended(tmp))) 175 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 176 177 next_hops[i] = tmp >> 1; 178 } 179 } 180 181 static inline void 182 dir24_8_lookup_bulk_0(void *p, const uint32_t *ips, 183 uint64_t *next_hops, const unsigned int n) 184 { 185 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 186 187 dir24_8_lookup_bulk(dp, ips, next_hops, n, 0); 188 } 189 190 static inline void 191 dir24_8_lookup_bulk_1(void *p, const uint32_t *ips, 192 uint64_t *next_hops, const unsigned int n) 193 { 194 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 195 196 dir24_8_lookup_bulk(dp, ips, next_hops, n, 1); 197 } 198 199 static inline void 200 dir24_8_lookup_bulk_2(void *p, const uint32_t *ips, 201 uint64_t *next_hops, const unsigned int n) 202 { 203 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 204 205 dir24_8_lookup_bulk(dp, ips, next_hops, n, 2); 206 } 207 208 static inline void 209 dir24_8_lookup_bulk_3(void *p, const uint32_t *ips, 210 uint64_t *next_hops, const unsigned int n) 211 { 212 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 213 214 dir24_8_lookup_bulk(dp, ips, next_hops, n, 3); 215 } 216 217 static inline void 218 dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips, 219 uint64_t *next_hops, const unsigned int n) 220 { 221 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 222 uint64_t tmp; 223 uint32_t i; 224 uint32_t prefetch_offset = RTE_MIN(15U, n); 225 uint8_t nh_sz = dp->nh_sz; 226 227 for (i = 0; i < prefetch_offset; i++) 228 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); 229 for (i = 0; i < (n - prefetch_offset); i++) { 230 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], 231 nh_sz)); 232 tmp = get_tbl24(dp, ips[i], nh_sz); 233 if (unlikely(is_entry_extended(tmp))) 234 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 235 236 next_hops[i] = tmp >> 1; 237 } 238 for (; i < n; i++) { 239 tmp = get_tbl24(dp, ips[i], nh_sz); 240 if (unlikely(is_entry_extended(tmp))) 241 tmp = get_tbl8(dp, tmp, ips[i], nh_sz); 242 243 next_hops[i] = tmp >> 1; 244 } 245 } 246 247 #define BSWAP_MAX_LENGTH 64 248 249 typedef void (*dir24_8_lookup_bulk_be_cb)(void *p, const uint32_t *ips, uint64_t *next_hops, 250 const unsigned int n); 251 252 static inline void 253 dir24_8_lookup_bulk_be(void *p, const uint32_t *ips, uint64_t *next_hops, const unsigned int n, 254 dir24_8_lookup_bulk_be_cb cb) 255 { 256 uint32_t le_ips[BSWAP_MAX_LENGTH]; 257 unsigned int i; 258 259 #if RTE_BYTE_ORDER == RTE_BIG_ENDIAN 260 cb(p, ips, next_hops, n); 261 #else 262 for (i = 0; i < n; i += BSWAP_MAX_LENGTH) { 263 int j; 264 for (j = 0; j < BSWAP_MAX_LENGTH && i + j < n; j++) 265 le_ips[j] = rte_be_to_cpu_32(ips[i + j]); 266 267 cb(p, le_ips, next_hops + i, j); 268 } 269 #endif 270 } 271 272 #define DECLARE_BE_LOOKUP_FN(name) \ 273 static inline void \ 274 name##_be(void *p, const uint32_t *ips, uint64_t *next_hops, const unsigned int n) \ 275 { \ 276 dir24_8_lookup_bulk_be(p, ips, next_hops, n, name); \ 277 } 278 279 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_1b) 280 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_2b) 281 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_4b) 282 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_8b) 283 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_0) 284 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_1) 285 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_2) 286 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_3) 287 DECLARE_BE_LOOKUP_FN(dir24_8_lookup_bulk_uni) 288 289 void * 290 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf); 291 292 void 293 dir24_8_free(void *p); 294 295 rte_fib_lookup_fn_t 296 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type, bool be_addr); 297 298 int 299 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, 300 uint64_t next_hop, int op); 301 302 int 303 dir24_8_rcu_qsbr_add(struct dir24_8_tbl *dp, struct rte_fib_rcu_config *cfg, 304 const char *name); 305 306 #endif /* _DIR24_8_H_ */ 307