1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
3 * Copyright(c) 2019 Intel Corporation
12 #include <rte_debug.h>
13 #include <rte_malloc.h>
14 #include <rte_prefetch.h>
15 #include <rte_errno.h>
16 #include <rte_memory.h>
17 #include <rte_branch_prediction.h>
23 #define DIR24_8_NAMESIZE 64
25 #define DIR24_8_TBL24_NUM_ENT (1 << 24)
26 #define DIR24_8_TBL8_GRP_NUM_ENT 256U
27 #define DIR24_8_EXT_ENT 1
28 #define DIR24_8_TBL24_MASK 0xffffff00
30 #define BITMAP_SLAB_BIT_SIZE_LOG2 6
31 #define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
32 #define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1)
35 uint32_t number_tbl8s; /**< Total number of tbl8s */
36 uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */
37 uint32_t cur_tbl8s; /**< Current number of tbl8s */
38 enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */
39 uint64_t def_nh; /**< Default next hop */
40 uint64_t *tbl8; /**< tbl8 table. */
41 uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/
43 __extension__ uint64_t tbl24[0] __rte_cache_aligned;
46 #define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y)))
53 enum lookup_type test_lookup = MACRO;
56 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
58 return (void *)&((uint8_t *)dp->tbl24)[(ip &
59 DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
63 bits_in_nh(uint8_t nh_sz)
65 return 8 * (1 << nh_sz);
68 static inline uint64_t
69 get_max_nh(uint8_t nh_sz)
71 return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
74 static inline uint32_t
75 get_tbl24_idx(uint32_t ip)
80 static inline uint32_t
81 get_tbl8_idx(uint32_t res, uint32_t ip)
83 return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
86 static inline uint64_t
87 lookup_msk(uint8_t nh_sz)
89 return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
93 get_psd_idx(uint32_t val, uint8_t nh_sz)
95 return val & ((1 << (3 - nh_sz)) - 1);
98 static inline uint32_t
99 get_tbl_idx(uint32_t val, uint8_t nh_sz)
101 return val >> (3 - nh_sz);
104 static inline uint64_t
105 get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
107 return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
108 (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
109 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
112 static inline uint64_t
113 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
115 return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
116 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
117 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
121 is_entry_extended(uint64_t ent)
123 return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
126 #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \
127 static void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \
128 uint64_t *next_hops, const unsigned int n) \
130 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \
133 uint32_t prefetch_offset = \
134 RTE_MIN((unsigned int)bulk_prefetch, n); \
136 for (i = 0; i < prefetch_offset; i++) \
137 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \
138 for (i = 0; i < (n - prefetch_offset); i++) { \
139 rte_prefetch0(get_tbl24_p(dp, \
140 ips[i + prefetch_offset], nh_sz)); \
141 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \
142 if (unlikely(is_entry_extended(tmp))) \
143 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \
144 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
145 next_hops[i] = tmp >> 1; \
147 for (; i < n; i++) { \
148 tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \
149 if (unlikely(is_entry_extended(tmp))) \
150 tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \
151 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
152 next_hops[i] = tmp >> 1; \
156 LOOKUP_FUNC(1b, uint8_t, 5, 0)
157 LOOKUP_FUNC(2b, uint16_t, 6, 1)
158 LOOKUP_FUNC(4b, uint32_t, 15, 2)
159 LOOKUP_FUNC(8b, uint64_t, 12, 3)
162 dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
163 uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
167 uint32_t prefetch_offset = RTE_MIN(15U, n);
169 for (i = 0; i < prefetch_offset; i++)
170 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
171 for (i = 0; i < (n - prefetch_offset); i++) {
172 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
174 tmp = get_tbl24(dp, ips[i], nh_sz);
175 if (unlikely(is_entry_extended(tmp)))
176 tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
178 next_hops[i] = tmp >> 1;
181 tmp = get_tbl24(dp, ips[i], nh_sz);
182 if (unlikely(is_entry_extended(tmp)))
183 tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
185 next_hops[i] = tmp >> 1;
190 dir24_8_lookup_bulk_0(void *p, const uint32_t *ips,
191 uint64_t *next_hops, const unsigned int n)
193 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
195 dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
199 dir24_8_lookup_bulk_1(void *p, const uint32_t *ips,
200 uint64_t *next_hops, const unsigned int n)
202 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
204 dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
208 dir24_8_lookup_bulk_2(void *p, const uint32_t *ips,
209 uint64_t *next_hops, const unsigned int n)
211 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
213 dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
217 dir24_8_lookup_bulk_3(void *p, const uint32_t *ips,
218 uint64_t *next_hops, const unsigned int n)
220 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
222 dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
226 dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
227 uint64_t *next_hops, const unsigned int n)
229 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
232 uint32_t prefetch_offset = RTE_MIN(15U, n);
233 uint8_t nh_sz = dp->nh_sz;
235 for (i = 0; i < prefetch_offset; i++)
236 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
237 for (i = 0; i < (n - prefetch_offset); i++) {
238 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
240 tmp = get_tbl24(dp, ips[i], nh_sz);
241 if (unlikely(is_entry_extended(tmp)))
242 tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
244 next_hops[i] = tmp >> 1;
247 tmp = get_tbl24(dp, ips[i], nh_sz);
248 if (unlikely(is_entry_extended(tmp)))
249 tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
251 next_hops[i] = tmp >> 1;
256 dir24_8_get_lookup_fn(struct rte_fib_conf *fib_conf)
258 enum rte_fib_dir24_8_nh_sz nh_sz = fib_conf->dir24_8.nh_sz;
260 if (test_lookup == MACRO) {
262 case RTE_FIB_DIR24_8_1B:
263 return dir24_8_lookup_bulk_1b;
264 case RTE_FIB_DIR24_8_2B:
265 return dir24_8_lookup_bulk_2b;
266 case RTE_FIB_DIR24_8_4B:
267 return dir24_8_lookup_bulk_4b;
268 case RTE_FIB_DIR24_8_8B:
269 return dir24_8_lookup_bulk_8b;
271 } else if (test_lookup == INLINE) {
273 case RTE_FIB_DIR24_8_1B:
274 return dir24_8_lookup_bulk_0;
275 case RTE_FIB_DIR24_8_2B:
276 return dir24_8_lookup_bulk_1;
277 case RTE_FIB_DIR24_8_4B:
278 return dir24_8_lookup_bulk_2;
279 case RTE_FIB_DIR24_8_8B:
280 return dir24_8_lookup_bulk_3;
283 return dir24_8_lookup_bulk_uni;
288 write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n)
291 uint8_t *ptr8 = (uint8_t *)ptr;
292 uint16_t *ptr16 = (uint16_t *)ptr;
293 uint32_t *ptr32 = (uint32_t *)ptr;
294 uint64_t *ptr64 = (uint64_t *)ptr;
297 case RTE_FIB_DIR24_8_1B:
298 for (i = 0; i < n; i++)
299 ptr8[i] = (uint8_t)val;
301 case RTE_FIB_DIR24_8_2B:
302 for (i = 0; i < n; i++)
303 ptr16[i] = (uint16_t)val;
305 case RTE_FIB_DIR24_8_4B:
306 for (i = 0; i < n; i++)
307 ptr32[i] = (uint32_t)val;
309 case RTE_FIB_DIR24_8_8B:
310 for (i = 0; i < n; i++)
311 ptr64[i] = (uint64_t)val;
317 tbl8_get_idx(struct dir24_8_tbl *dp)
322 for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
323 (dp->tbl8_idxes[i] == UINT64_MAX); i++)
325 if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
326 bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]);
327 dp->tbl8_idxes[i] |= (1ULL << bit_idx);
328 return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
334 tbl8_free_idx(struct dir24_8_tbl *dp, int idx)
336 dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
337 ~(1ULL << (idx & BITMAP_SLAB_BITMASK));
341 tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh)
346 tbl8_idx = tbl8_get_idx(dp);
349 tbl8_ptr = (uint8_t *)dp->tbl8 +
350 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
352 /*Init tbl8 entries with nexthop from tbl24*/
353 write_to_fib((void *)tbl8_ptr, nh|
354 DIR24_8_EXT_ENT, dp->nh_sz,
355 DIR24_8_TBL8_GRP_NUM_ENT);
361 tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx)
371 case RTE_FIB_DIR24_8_1B:
372 ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx *
373 DIR24_8_TBL8_GRP_NUM_ENT];
375 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
379 ((uint8_t *)dp->tbl24)[ip >> 8] =
380 nh & ~DIR24_8_EXT_ENT;
381 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
384 case RTE_FIB_DIR24_8_2B:
385 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
386 DIR24_8_TBL8_GRP_NUM_ENT];
388 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
392 ((uint16_t *)dp->tbl24)[ip >> 8] =
393 nh & ~DIR24_8_EXT_ENT;
394 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
397 case RTE_FIB_DIR24_8_4B:
398 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
399 DIR24_8_TBL8_GRP_NUM_ENT];
401 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
405 ((uint32_t *)dp->tbl24)[ip >> 8] =
406 nh & ~DIR24_8_EXT_ENT;
407 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
410 case RTE_FIB_DIR24_8_8B:
411 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
412 DIR24_8_TBL8_GRP_NUM_ENT];
414 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
418 ((uint64_t *)dp->tbl24)[ip >> 8] =
419 nh & ~DIR24_8_EXT_ENT;
420 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
424 tbl8_free_idx(dp, tbl8_idx);
429 install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge,
438 len = ((ledge == 0) && (redge == 0)) ? 1 << 24 :
439 ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8;
441 if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) {
442 if ((ROUNDUP(ledge, 24) - ledge) != 0) {
443 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
444 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
447 * Make sure there is space for two TBL8.
448 * This is necessary when installing range that
449 * needs tbl8 for ledge and redge.
451 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
452 tmp_tbl8_idx = tbl8_get_idx(dp);
455 else if (tmp_tbl8_idx < 0) {
456 tbl8_free_idx(dp, tbl8_idx);
459 tbl8_free_idx(dp, tmp_tbl8_idx);
460 /*update dir24 entry with tbl8 index*/
461 write_to_fib(get_tbl24_p(dp, ledge,
462 dp->nh_sz), (tbl8_idx << 1)|
466 tbl8_idx = tbl24_tmp >> 1;
467 tbl8_ptr = (uint8_t *)dp->tbl8 +
468 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
469 (ledge & ~DIR24_8_TBL24_MASK)) <<
471 /*update tbl8 with new next hop*/
472 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
474 dp->nh_sz, ROUNDUP(ledge, 24) - ledge);
475 tbl8_recycle(dp, ledge, tbl8_idx);
477 write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz),
478 next_hop << 1, dp->nh_sz, len);
479 if (redge & ~DIR24_8_TBL24_MASK) {
480 tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz);
481 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
483 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
486 /*update dir24 entry with tbl8 index*/
487 write_to_fib(get_tbl24_p(dp, redge,
488 dp->nh_sz), (tbl8_idx << 1)|
492 tbl8_idx = tbl24_tmp >> 1;
493 tbl8_ptr = (uint8_t *)dp->tbl8 +
494 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
496 /*update tbl8 with new next hop*/
497 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
499 dp->nh_sz, redge & ~DIR24_8_TBL24_MASK);
500 tbl8_recycle(dp, redge, tbl8_idx);
502 } else if ((redge - ledge) != 0) {
503 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
504 if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
506 tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
509 /*update dir24 entry with tbl8 index*/
510 write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz),
515 tbl8_idx = tbl24_tmp >> 1;
516 tbl8_ptr = (uint8_t *)dp->tbl8 +
517 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
518 (ledge & ~DIR24_8_TBL24_MASK)) <<
520 /*update tbl8 with new next hop*/
521 write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
523 dp->nh_sz, redge - ledge);
524 tbl8_recycle(dp, ledge, tbl8_idx);
530 modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
531 uint8_t depth, uint64_t next_hop)
533 struct rte_rib_node *tmp = NULL;
534 uint32_t ledge, redge, tmp_ip;
540 tmp = rte_rib_get_nxt(rib, ip, depth, tmp,
541 RTE_RIB_GET_NXT_COVER);
543 rte_rib_get_depth(tmp, &tmp_depth);
544 if (tmp_depth == depth)
546 rte_rib_get_ip(tmp, &tmp_ip);
547 redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth);
548 if (ledge == redge) {
550 (uint32_t)(1ULL << (32 - tmp_depth));
553 ret = install_to_fib(dp, ledge, redge,
558 (uint32_t)(1ULL << (32 - tmp_depth));
560 redge = ip + (uint32_t)(1ULL << (32 - depth));
563 ret = install_to_fib(dp, ledge, redge,
574 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
575 uint64_t next_hop, int op)
577 struct dir24_8_tbl *dp;
579 struct rte_rib_node *tmp = NULL;
580 struct rte_rib_node *node;
581 struct rte_rib_node *parent;
583 uint64_t par_nh, node_nh;
585 if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
588 dp = rte_fib_get_dp(fib);
589 rib = rte_fib_get_rib(fib);
590 RTE_ASSERT((dp != NULL) && (rib != NULL));
592 if (next_hop > get_max_nh(dp->nh_sz))
595 ip &= rte_rib_depth_to_mask(depth);
597 node = rte_rib_lookup_exact(rib, ip, depth);
601 rte_rib_get_nh(node, &node_nh);
602 if (node_nh == next_hop)
604 ret = modify_fib(dp, rib, ip, depth, next_hop);
606 rte_rib_set_nh(node, next_hop);
610 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
611 RTE_RIB_GET_NXT_COVER);
613 (dp->rsvd_tbl8s >= dp->number_tbl8s))
617 node = rte_rib_insert(rib, ip, depth);
620 rte_rib_set_nh(node, next_hop);
621 parent = rte_rib_lookup_parent(node);
622 if (parent != NULL) {
623 rte_rib_get_nh(parent, &par_nh);
624 if (par_nh == next_hop)
627 ret = modify_fib(dp, rib, ip, depth, next_hop);
629 rte_rib_remove(rib, ip, depth);
632 if ((depth > 24) && (tmp == NULL))
639 parent = rte_rib_lookup_parent(node);
640 if (parent != NULL) {
641 rte_rib_get_nh(parent, &par_nh);
642 rte_rib_get_nh(node, &node_nh);
643 if (par_nh != node_nh)
644 ret = modify_fib(dp, rib, ip, depth, par_nh);
646 ret = modify_fib(dp, rib, ip, depth, dp->def_nh);
648 rte_rib_remove(rib, ip, depth);
650 tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
651 RTE_RIB_GET_NXT_COVER);
664 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
666 char mem_name[DIR24_8_NAMESIZE];
667 struct dir24_8_tbl *dp;
670 enum rte_fib_dir24_8_nh_sz nh_sz;
672 if ((name == NULL) || (fib_conf == NULL) ||
673 (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) ||
674 (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) ||
675 (fib_conf->dir24_8.num_tbl8 >
676 get_max_nh(fib_conf->dir24_8.nh_sz)) ||
677 (fib_conf->dir24_8.num_tbl8 == 0) ||
678 (fib_conf->default_nh >
679 get_max_nh(fib_conf->dir24_8.nh_sz))) {
684 def_nh = fib_conf->default_nh;
685 nh_sz = fib_conf->dir24_8.nh_sz;
686 num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8,
687 BITMAP_SLAB_BIT_SIZE);
689 snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
690 dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) +
691 DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
698 /* Init table with default value */
699 write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
701 snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
702 uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) *
704 dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz,
705 RTE_CACHE_LINE_SIZE, socket_id);
706 if (dp->tbl8 == NULL) {
713 dp->number_tbl8s = num_tbl8;
715 snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
716 dp->tbl8_idxes = rte_zmalloc_socket(mem_name,
717 RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3,
718 RTE_CACHE_LINE_SIZE, socket_id);
719 if (dp->tbl8_idxes == NULL) {
730 dir24_8_free(void *p)
732 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
734 rte_free(dp->tbl8_idxes);