1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
3 * Copyright(c) 2019 Intel Corporation
10 #include <rte_malloc.h>
11 #include <rte_errno.h>
18 #ifdef CC_DIR24_8_AVX512_SUPPORT
20 #include "dir24_8_avx512.h"
22 #endif /* CC_DIR24_8_AVX512_SUPPORT */
24 #define DIR24_8_NAMESIZE 64
26 #define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y)))
28 static inline rte_fib_lookup_fn_t
29 get_scalar_fn(enum rte_fib_dir24_8_nh_sz nh_sz)
32 case RTE_FIB_DIR24_8_1B:
33 return dir24_8_lookup_bulk_1b;
34 case RTE_FIB_DIR24_8_2B:
35 return dir24_8_lookup_bulk_2b;
36 case RTE_FIB_DIR24_8_4B:
37 return dir24_8_lookup_bulk_4b;
38 case RTE_FIB_DIR24_8_8B:
39 return dir24_8_lookup_bulk_8b;
45 static inline rte_fib_lookup_fn_t
46 get_scalar_fn_inlined(enum rte_fib_dir24_8_nh_sz nh_sz)
49 case RTE_FIB_DIR24_8_1B:
50 return dir24_8_lookup_bulk_0;
51 case RTE_FIB_DIR24_8_2B:
52 return dir24_8_lookup_bulk_1;
53 case RTE_FIB_DIR24_8_4B:
54 return dir24_8_lookup_bulk_2;
55 case RTE_FIB_DIR24_8_8B:
56 return dir24_8_lookup_bulk_3;
62 static inline rte_fib_lookup_fn_t
63 get_vector_fn(enum rte_fib_dir24_8_nh_sz nh_sz)
65 #ifdef CC_DIR24_8_AVX512_SUPPORT
66 if ((rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) <= 0) ||
67 (rte_vect_get_max_simd_bitwidth() < RTE_VECT_SIMD_512))
71 case RTE_FIB_DIR24_8_1B:
72 return rte_dir24_8_vec_lookup_bulk_1b;
73 case RTE_FIB_DIR24_8_2B:
74 return rte_dir24_8_vec_lookup_bulk_2b;
75 case RTE_FIB_DIR24_8_4B:
76 return rte_dir24_8_vec_lookup_bulk_4b;
77 case RTE_FIB_DIR24_8_8B:
78 return rte_dir24_8_vec_lookup_bulk_8b;
89 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type)
91 enum rte_fib_dir24_8_nh_sz nh_sz;
92 rte_fib_lookup_fn_t ret_fn;
93 struct dir24_8_tbl *dp = p;
101 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_MACRO:
102 return get_scalar_fn(nh_sz);
103 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_INLINE:
104 return get_scalar_fn_inlined(nh_sz);
105 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_UNI:
106 return dir24_8_lookup_bulk_uni;
107 case RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512:
108 return get_vector_fn(nh_sz);
109 case RTE_FIB_LOOKUP_DEFAULT:
110 ret_fn = get_vector_fn(nh_sz);
111 return (ret_fn != NULL) ? ret_fn : get_scalar_fn(nh_sz);
120 write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n)
123 uint8_t *ptr8 = (uint8_t *)ptr;
124 uint16_t *ptr16 = (uint16_t *)ptr;
125 uint32_t *ptr32 = (uint32_t *)ptr;
126 uint64_t *ptr64 = (uint64_t *)ptr;
129 case RTE_FIB_DIR24_8_1B:
130 for (i = 0; i < n; i++)
131 ptr8[i] = (uint8_t)val;
133 case RTE_FIB_DIR24_8_2B:
134 for (i = 0; i < n; i++)
135 ptr16[i] = (uint16_t)val;
137 case RTE_FIB_DIR24_8_4B:
138 for (i = 0; i < n; i++)
139 ptr32[i] = (uint32_t)val;
141 case RTE_FIB_DIR24_8_8B:
142 for (i = 0; i < n; i++)
143 ptr64[i] = (uint64_t)val;
149 tbl8_get_idx(struct dir24_8_tbl *dp)
154 for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
155 (dp->tbl8_idxes[i] == UINT64_MAX); i++)
157 if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
158 bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]);
159 dp->tbl8_idxes[i] |= (1ULL << bit_idx);
160 return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
166 tbl8_free_idx(struct dir24_8_tbl *dp, int idx)
168 dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
169 ~(1ULL << (idx & BITMAP_SLAB_BITMASK));
173 tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh)
178 tbl8_idx = tbl8_get_idx(dp);
181 tbl8_ptr = (uint8_t *)dp->tbl8 +
182 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
184 /*Init tbl8 entries with nexthop from tbl24*/
185 write_to_fib((void *)tbl8_ptr, nh|
186 DIR24_8_EXT_ENT, dp->nh_sz,
187 DIR24_8_TBL8_GRP_NUM_ENT);
193 tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx)
203 case RTE_FIB_DIR24_8_1B:
204 ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx *
205 DIR24_8_TBL8_GRP_NUM_ENT];
207 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
211 ((uint8_t *)dp->tbl24)[ip >> 8] =
212 nh & ~DIR24_8_EXT_ENT;
213 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
216 case RTE_FIB_DIR24_8_2B:
217 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
218 DIR24_8_TBL8_GRP_NUM_ENT];
220 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
224 ((uint16_t *)dp->tbl24)[ip >> 8] =
225 nh & ~DIR24_8_EXT_ENT;
226 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
229 case RTE_FIB_DIR24_8_4B:
230 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
231 DIR24_8_TBL8_GRP_NUM_ENT];
233 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
237 ((uint32_t *)dp->tbl24)[ip >> 8] =
238 nh & ~DIR24_8_EXT_ENT;
239 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
242 case RTE_FIB_DIR24_8_8B:
243 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
244 DIR24_8_TBL8_GRP_NUM_ENT];
246 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
250 ((uint64_t *)dp->tbl24)[ip >> 8] =
251 nh & ~DIR24_8_EXT_ENT;
252 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
256 tbl8_free_idx(dp, tbl8_idx);
261 install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge,
270 len = ((ledge == 0) && (redge == 0)) ? 1 << 24 :
271 ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8;
273 if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) {
274 if ((ROUNDUP(ledge, 24) - ledge) != 0) {
275 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
276 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
279 * Make sure there is space for two TBL8.
280 * This is necessary when installing range that
281 * needs tbl8 for ledge and redge.
283 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
284 tmp_tbl8_idx = tbl8_get_idx(dp);
287 else if (tmp_tbl8_idx < 0) {
288 tbl8_free_idx(dp, tbl8_idx);
291 tbl8_free_idx(dp, tmp_tbl8_idx);
292 /*update dir24 entry with tbl8 index*/
293 write_to_fib(get_tbl24_p(dp, ledge,
294 dp->nh_sz), (tbl8_idx << 1)|
298 tbl8_idx = tbl24_tmp >> 1;
299 tbl8_ptr = (uint8_t *)dp->tbl8 +
300 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
301 (ledge & ~DIR24_8_TBL24_MASK)) <<
303 /*update tbl8 with new next hop*/
304 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
306 dp->nh_sz, ROUNDUP(ledge, 24) - ledge);
307 tbl8_recycle(dp, ledge, tbl8_idx);
309 write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz),
310 next_hop << 1, dp->nh_sz, len);
311 if (redge & ~DIR24_8_TBL24_MASK) {
312 tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz);
313 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
315 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
318 /*update dir24 entry with tbl8 index*/
319 write_to_fib(get_tbl24_p(dp, redge,
320 dp->nh_sz), (tbl8_idx << 1)|
324 tbl8_idx = tbl24_tmp >> 1;
325 tbl8_ptr = (uint8_t *)dp->tbl8 +
326 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
328 /*update tbl8 with new next hop*/
329 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
331 dp->nh_sz, redge & ~DIR24_8_TBL24_MASK);
332 tbl8_recycle(dp, redge, tbl8_idx);
334 } else if ((redge - ledge) != 0) {
335 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
336 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
338 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
341 /*update dir24 entry with tbl8 index*/
342 write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz),
347 tbl8_idx = tbl24_tmp >> 1;
348 tbl8_ptr = (uint8_t *)dp->tbl8 +
349 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
350 (ledge & ~DIR24_8_TBL24_MASK)) <<
352 /*update tbl8 with new next hop*/
353 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
355 dp->nh_sz, redge - ledge);
356 tbl8_recycle(dp, ledge, tbl8_idx);
362 modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
363 uint8_t depth, uint64_t next_hop)
365 struct rte_rib_node *tmp = NULL;
366 uint32_t ledge, redge, tmp_ip;
372 tmp = rte_rib_get_nxt(rib, ip, depth, tmp,
373 RTE_RIB_GET_NXT_COVER);
375 rte_rib_get_depth(tmp, &tmp_depth);
376 if (tmp_depth == depth)
378 rte_rib_get_ip(tmp, &tmp_ip);
379 redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth);
380 if (ledge == redge) {
382 (uint32_t)(1ULL << (32 - tmp_depth));
385 ret = install_to_fib(dp, ledge, redge,
390 (uint32_t)(1ULL << (32 - tmp_depth));
392 redge = ip + (uint32_t)(1ULL << (32 - depth));
395 ret = install_to_fib(dp, ledge, redge,
406 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
407 uint64_t next_hop, int op)
409 struct dir24_8_tbl *dp;
411 struct rte_rib_node *tmp = NULL;
412 struct rte_rib_node *node;
413 struct rte_rib_node *parent;
415 uint64_t par_nh, node_nh;
417 if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
420 dp = rte_fib_get_dp(fib);
421 rib = rte_fib_get_rib(fib);
422 RTE_ASSERT((dp != NULL) && (rib != NULL));
424 if (next_hop > get_max_nh(dp->nh_sz))
427 ip &= rte_rib_depth_to_mask(depth);
429 node = rte_rib_lookup_exact(rib, ip, depth);
433 rte_rib_get_nh(node, &node_nh);
434 if (node_nh == next_hop)
436 ret = modify_fib(dp, rib, ip, depth, next_hop);
438 rte_rib_set_nh(node, next_hop);
442 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
443 RTE_RIB_GET_NXT_COVER);
445 (dp->rsvd_tbl8s >= dp->number_tbl8s))
449 node = rte_rib_insert(rib, ip, depth);
452 rte_rib_set_nh(node, next_hop);
453 parent = rte_rib_lookup_parent(node);
454 if (parent != NULL) {
455 rte_rib_get_nh(parent, &par_nh);
456 if (par_nh == next_hop)
459 ret = modify_fib(dp, rib, ip, depth, next_hop);
461 rte_rib_remove(rib, ip, depth);
464 if ((depth > 24) && (tmp == NULL))
471 parent = rte_rib_lookup_parent(node);
472 if (parent != NULL) {
473 rte_rib_get_nh(parent, &par_nh);
474 rte_rib_get_nh(node, &node_nh);
475 if (par_nh != node_nh)
476 ret = modify_fib(dp, rib, ip, depth, par_nh);
478 ret = modify_fib(dp, rib, ip, depth, dp->def_nh);
480 rte_rib_remove(rib, ip, depth);
482 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
483 RTE_RIB_GET_NXT_COVER);
496 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
498 char mem_name[DIR24_8_NAMESIZE];
499 struct dir24_8_tbl *dp;
502 enum rte_fib_dir24_8_nh_sz nh_sz;
504 if ((name == NULL) || (fib_conf == NULL) ||
505 (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) ||
506 (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) ||
507 (fib_conf->dir24_8.num_tbl8 >
508 get_max_nh(fib_conf->dir24_8.nh_sz)) ||
509 (fib_conf->dir24_8.num_tbl8 == 0) ||
510 (fib_conf->default_nh >
511 get_max_nh(fib_conf->dir24_8.nh_sz))) {
516 def_nh = fib_conf->default_nh;
517 nh_sz = fib_conf->dir24_8.nh_sz;
518 num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8,
519 BITMAP_SLAB_BIT_SIZE);
521 snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
522 dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) +
523 DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
530 /* Init table with default value */
531 write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
533 snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
534 uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) *
536 dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz,
537 RTE_CACHE_LINE_SIZE, socket_id);
538 if (dp->tbl8 == NULL) {
545 dp->number_tbl8s = num_tbl8;
547 snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
548 dp->tbl8_idxes = rte_zmalloc_socket(mem_name,
549 RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3,
550 RTE_CACHE_LINE_SIZE, socket_id);
551 if (dp->tbl8_idxes == NULL) {
562 dir24_8_free(void *p)
564 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
566 rte_free(dp->tbl8_idxes);