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 #include <stdint.h> 7 #include <stdlib.h> 8 #include <stdio.h> 9 #include <string.h> 10 #include <inttypes.h> 11 12 #include <rte_debug.h> 13 #include <rte_malloc.h> 14 #include <rte_errno.h> 15 #include <rte_memory.h> 16 #include <rte_vect.h> 17 18 #include <rte_rib.h> 19 #include <rte_fib.h> 20 #include "dir24_8.h" 21 22 #ifdef CC_DIR24_8_AVX512_SUPPORT 23 24 #include "dir24_8_avx512.h" 25 26 #endif /* CC_DIR24_8_AVX512_SUPPORT */ 27 28 #define DIR24_8_NAMESIZE 64 29 30 #define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y))) 31 32 static inline rte_fib_lookup_fn_t 33 get_scalar_fn(enum rte_fib_dir24_8_nh_sz nh_sz) 34 { 35 switch (nh_sz) { 36 case RTE_FIB_DIR24_8_1B: 37 return dir24_8_lookup_bulk_1b; 38 case RTE_FIB_DIR24_8_2B: 39 return dir24_8_lookup_bulk_2b; 40 case RTE_FIB_DIR24_8_4B: 41 return dir24_8_lookup_bulk_4b; 42 case RTE_FIB_DIR24_8_8B: 43 return dir24_8_lookup_bulk_8b; 44 default: 45 return NULL; 46 } 47 } 48 49 static inline rte_fib_lookup_fn_t 50 get_scalar_fn_inlined(enum rte_fib_dir24_8_nh_sz nh_sz) 51 { 52 switch (nh_sz) { 53 case RTE_FIB_DIR24_8_1B: 54 return dir24_8_lookup_bulk_0; 55 case RTE_FIB_DIR24_8_2B: 56 return dir24_8_lookup_bulk_1; 57 case RTE_FIB_DIR24_8_4B: 58 return dir24_8_lookup_bulk_2; 59 case RTE_FIB_DIR24_8_8B: 60 return dir24_8_lookup_bulk_3; 61 default: 62 return NULL; 63 } 64 } 65 66 static inline rte_fib_lookup_fn_t 67 get_vector_fn(enum rte_fib_dir24_8_nh_sz nh_sz) 68 { 69 #ifdef CC_DIR24_8_AVX512_SUPPORT 70 if ((rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) <= 0) || 71 (rte_vect_get_max_simd_bitwidth() < RTE_VECT_SIMD_512)) 72 return NULL; 73 74 switch (nh_sz) { 75 case RTE_FIB_DIR24_8_1B: 76 return rte_dir24_8_vec_lookup_bulk_1b; 77 case RTE_FIB_DIR24_8_2B: 78 return rte_dir24_8_vec_lookup_bulk_2b; 79 case RTE_FIB_DIR24_8_4B: 80 return rte_dir24_8_vec_lookup_bulk_4b; 81 case RTE_FIB_DIR24_8_8B: 82 return rte_dir24_8_vec_lookup_bulk_8b; 83 default: 84 return NULL; 85 } 86 #else 87 RTE_SET_USED(nh_sz); 88 #endif 89 return NULL; 90 } 91 92 rte_fib_lookup_fn_t 93 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type) 94 { 95 enum rte_fib_dir24_8_nh_sz nh_sz; 96 rte_fib_lookup_fn_t ret_fn; 97 struct dir24_8_tbl *dp = p; 98 99 if (dp == NULL) 100 return NULL; 101 102 nh_sz = dp->nh_sz; 103 104 switch (type) { 105 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_MACRO: 106 return get_scalar_fn(nh_sz); 107 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_INLINE: 108 return get_scalar_fn_inlined(nh_sz); 109 case RTE_FIB_LOOKUP_DIR24_8_SCALAR_UNI: 110 return dir24_8_lookup_bulk_uni; 111 case RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512: 112 return get_vector_fn(nh_sz); 113 case RTE_FIB_LOOKUP_DEFAULT: 114 ret_fn = get_vector_fn(nh_sz); 115 return (ret_fn != NULL) ? ret_fn : get_scalar_fn(nh_sz); 116 default: 117 return NULL; 118 } 119 120 return NULL; 121 } 122 123 static void 124 write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n) 125 { 126 int i; 127 uint8_t *ptr8 = (uint8_t *)ptr; 128 uint16_t *ptr16 = (uint16_t *)ptr; 129 uint32_t *ptr32 = (uint32_t *)ptr; 130 uint64_t *ptr64 = (uint64_t *)ptr; 131 132 switch (size) { 133 case RTE_FIB_DIR24_8_1B: 134 for (i = 0; i < n; i++) 135 ptr8[i] = (uint8_t)val; 136 break; 137 case RTE_FIB_DIR24_8_2B: 138 for (i = 0; i < n; i++) 139 ptr16[i] = (uint16_t)val; 140 break; 141 case RTE_FIB_DIR24_8_4B: 142 for (i = 0; i < n; i++) 143 ptr32[i] = (uint32_t)val; 144 break; 145 case RTE_FIB_DIR24_8_8B: 146 for (i = 0; i < n; i++) 147 ptr64[i] = (uint64_t)val; 148 break; 149 } 150 } 151 152 static int 153 tbl8_get_idx(struct dir24_8_tbl *dp) 154 { 155 uint32_t i; 156 int bit_idx; 157 158 for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) && 159 (dp->tbl8_idxes[i] == UINT64_MAX); i++) 160 ; 161 if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) { 162 bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]); 163 dp->tbl8_idxes[i] |= (1ULL << bit_idx); 164 return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx; 165 } 166 return -ENOSPC; 167 } 168 169 static inline void 170 tbl8_free_idx(struct dir24_8_tbl *dp, int idx) 171 { 172 dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &= 173 ~(1ULL << (idx & BITMAP_SLAB_BITMASK)); 174 } 175 176 static int 177 tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh) 178 { 179 int64_t tbl8_idx; 180 uint8_t *tbl8_ptr; 181 182 tbl8_idx = tbl8_get_idx(dp); 183 if (tbl8_idx < 0) 184 return tbl8_idx; 185 tbl8_ptr = (uint8_t *)dp->tbl8 + 186 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << 187 dp->nh_sz); 188 /*Init tbl8 entries with nexthop from tbl24*/ 189 write_to_fib((void *)tbl8_ptr, nh| 190 DIR24_8_EXT_ENT, dp->nh_sz, 191 DIR24_8_TBL8_GRP_NUM_ENT); 192 dp->cur_tbl8s++; 193 return tbl8_idx; 194 } 195 196 static void 197 tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx) 198 { 199 uint32_t i; 200 uint64_t nh; 201 uint8_t *ptr8; 202 uint16_t *ptr16; 203 uint32_t *ptr32; 204 uint64_t *ptr64; 205 206 switch (dp->nh_sz) { 207 case RTE_FIB_DIR24_8_1B: 208 ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx * 209 DIR24_8_TBL8_GRP_NUM_ENT]; 210 nh = *ptr8; 211 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { 212 if (nh != ptr8[i]) 213 return; 214 } 215 ((uint8_t *)dp->tbl24)[ip >> 8] = 216 nh & ~DIR24_8_EXT_ENT; 217 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) 218 ptr8[i] = 0; 219 break; 220 case RTE_FIB_DIR24_8_2B: 221 ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx * 222 DIR24_8_TBL8_GRP_NUM_ENT]; 223 nh = *ptr16; 224 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { 225 if (nh != ptr16[i]) 226 return; 227 } 228 ((uint16_t *)dp->tbl24)[ip >> 8] = 229 nh & ~DIR24_8_EXT_ENT; 230 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) 231 ptr16[i] = 0; 232 break; 233 case RTE_FIB_DIR24_8_4B: 234 ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx * 235 DIR24_8_TBL8_GRP_NUM_ENT]; 236 nh = *ptr32; 237 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { 238 if (nh != ptr32[i]) 239 return; 240 } 241 ((uint32_t *)dp->tbl24)[ip >> 8] = 242 nh & ~DIR24_8_EXT_ENT; 243 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) 244 ptr32[i] = 0; 245 break; 246 case RTE_FIB_DIR24_8_8B: 247 ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx * 248 DIR24_8_TBL8_GRP_NUM_ENT]; 249 nh = *ptr64; 250 for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { 251 if (nh != ptr64[i]) 252 return; 253 } 254 ((uint64_t *)dp->tbl24)[ip >> 8] = 255 nh & ~DIR24_8_EXT_ENT; 256 for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) 257 ptr64[i] = 0; 258 break; 259 } 260 tbl8_free_idx(dp, tbl8_idx); 261 dp->cur_tbl8s--; 262 } 263 264 static int 265 install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge, 266 uint64_t next_hop) 267 { 268 uint64_t tbl24_tmp; 269 int tbl8_idx; 270 int tmp_tbl8_idx; 271 uint8_t *tbl8_ptr; 272 uint32_t len; 273 274 len = ((ledge == 0) && (redge == 0)) ? 1 << 24 : 275 ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8; 276 277 if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) { 278 if ((ROUNDUP(ledge, 24) - ledge) != 0) { 279 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); 280 if ((tbl24_tmp & DIR24_8_EXT_ENT) != 281 DIR24_8_EXT_ENT) { 282 /** 283 * Make sure there is space for two TBL8. 284 * This is necessary when installing range that 285 * needs tbl8 for ledge and redge. 286 */ 287 tbl8_idx = tbl8_alloc(dp, tbl24_tmp); 288 tmp_tbl8_idx = tbl8_get_idx(dp); 289 if (tbl8_idx < 0) 290 return -ENOSPC; 291 else if (tmp_tbl8_idx < 0) { 292 tbl8_free_idx(dp, tbl8_idx); 293 return -ENOSPC; 294 } 295 tbl8_free_idx(dp, tmp_tbl8_idx); 296 /*update dir24 entry with tbl8 index*/ 297 write_to_fib(get_tbl24_p(dp, ledge, 298 dp->nh_sz), (tbl8_idx << 1)| 299 DIR24_8_EXT_ENT, 300 dp->nh_sz, 1); 301 } else 302 tbl8_idx = tbl24_tmp >> 1; 303 tbl8_ptr = (uint8_t *)dp->tbl8 + 304 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + 305 (ledge & ~DIR24_8_TBL24_MASK)) << 306 dp->nh_sz); 307 /*update tbl8 with new next hop*/ 308 write_to_fib((void *)tbl8_ptr, (next_hop << 1)| 309 DIR24_8_EXT_ENT, 310 dp->nh_sz, ROUNDUP(ledge, 24) - ledge); 311 tbl8_recycle(dp, ledge, tbl8_idx); 312 } 313 write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz), 314 next_hop << 1, dp->nh_sz, len); 315 if (redge & ~DIR24_8_TBL24_MASK) { 316 tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz); 317 if ((tbl24_tmp & DIR24_8_EXT_ENT) != 318 DIR24_8_EXT_ENT) { 319 tbl8_idx = tbl8_alloc(dp, tbl24_tmp); 320 if (tbl8_idx < 0) 321 return -ENOSPC; 322 /*update dir24 entry with tbl8 index*/ 323 write_to_fib(get_tbl24_p(dp, redge, 324 dp->nh_sz), (tbl8_idx << 1)| 325 DIR24_8_EXT_ENT, 326 dp->nh_sz, 1); 327 } else 328 tbl8_idx = tbl24_tmp >> 1; 329 tbl8_ptr = (uint8_t *)dp->tbl8 + 330 ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << 331 dp->nh_sz); 332 /*update tbl8 with new next hop*/ 333 write_to_fib((void *)tbl8_ptr, (next_hop << 1)| 334 DIR24_8_EXT_ENT, 335 dp->nh_sz, redge & ~DIR24_8_TBL24_MASK); 336 tbl8_recycle(dp, redge, tbl8_idx); 337 } 338 } else if ((redge - ledge) != 0) { 339 tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); 340 if ((tbl24_tmp & DIR24_8_EXT_ENT) != 341 DIR24_8_EXT_ENT) { 342 tbl8_idx = tbl8_alloc(dp, tbl24_tmp); 343 if (tbl8_idx < 0) 344 return -ENOSPC; 345 /*update dir24 entry with tbl8 index*/ 346 write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz), 347 (tbl8_idx << 1)| 348 DIR24_8_EXT_ENT, 349 dp->nh_sz, 1); 350 } else 351 tbl8_idx = tbl24_tmp >> 1; 352 tbl8_ptr = (uint8_t *)dp->tbl8 + 353 (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + 354 (ledge & ~DIR24_8_TBL24_MASK)) << 355 dp->nh_sz); 356 /*update tbl8 with new next hop*/ 357 write_to_fib((void *)tbl8_ptr, (next_hop << 1)| 358 DIR24_8_EXT_ENT, 359 dp->nh_sz, redge - ledge); 360 tbl8_recycle(dp, ledge, tbl8_idx); 361 } 362 return 0; 363 } 364 365 static int 366 modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip, 367 uint8_t depth, uint64_t next_hop) 368 { 369 struct rte_rib_node *tmp = NULL; 370 uint32_t ledge, redge, tmp_ip; 371 int ret; 372 uint8_t tmp_depth; 373 374 ledge = ip; 375 do { 376 tmp = rte_rib_get_nxt(rib, ip, depth, tmp, 377 RTE_RIB_GET_NXT_COVER); 378 if (tmp != NULL) { 379 rte_rib_get_depth(tmp, &tmp_depth); 380 if (tmp_depth == depth) 381 continue; 382 rte_rib_get_ip(tmp, &tmp_ip); 383 redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth); 384 if (ledge == redge) { 385 ledge = redge + 386 (uint32_t)(1ULL << (32 - tmp_depth)); 387 continue; 388 } 389 ret = install_to_fib(dp, ledge, redge, 390 next_hop); 391 if (ret != 0) 392 return ret; 393 ledge = redge + 394 (uint32_t)(1ULL << (32 - tmp_depth)); 395 } else { 396 redge = ip + (uint32_t)(1ULL << (32 - depth)); 397 if (ledge == redge) 398 break; 399 ret = install_to_fib(dp, ledge, redge, 400 next_hop); 401 if (ret != 0) 402 return ret; 403 } 404 } while (tmp); 405 406 return 0; 407 } 408 409 int 410 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, 411 uint64_t next_hop, int op) 412 { 413 struct dir24_8_tbl *dp; 414 struct rte_rib *rib; 415 struct rte_rib_node *tmp = NULL; 416 struct rte_rib_node *node; 417 struct rte_rib_node *parent; 418 int ret = 0; 419 uint64_t par_nh, node_nh; 420 421 if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH)) 422 return -EINVAL; 423 424 dp = rte_fib_get_dp(fib); 425 rib = rte_fib_get_rib(fib); 426 RTE_ASSERT((dp != NULL) && (rib != NULL)); 427 428 if (next_hop > get_max_nh(dp->nh_sz)) 429 return -EINVAL; 430 431 ip &= rte_rib_depth_to_mask(depth); 432 433 node = rte_rib_lookup_exact(rib, ip, depth); 434 switch (op) { 435 case RTE_FIB_ADD: 436 if (node != NULL) { 437 rte_rib_get_nh(node, &node_nh); 438 if (node_nh == next_hop) 439 return 0; 440 ret = modify_fib(dp, rib, ip, depth, next_hop); 441 if (ret == 0) 442 rte_rib_set_nh(node, next_hop); 443 return 0; 444 } 445 if (depth > 24) { 446 tmp = rte_rib_get_nxt(rib, ip, 24, NULL, 447 RTE_RIB_GET_NXT_COVER); 448 if ((tmp == NULL) && 449 (dp->rsvd_tbl8s >= dp->number_tbl8s)) 450 return -ENOSPC; 451 452 } 453 node = rte_rib_insert(rib, ip, depth); 454 if (node == NULL) 455 return -rte_errno; 456 rte_rib_set_nh(node, next_hop); 457 parent = rte_rib_lookup_parent(node); 458 if (parent != NULL) { 459 rte_rib_get_nh(parent, &par_nh); 460 if (par_nh == next_hop) 461 return 0; 462 } 463 ret = modify_fib(dp, rib, ip, depth, next_hop); 464 if (ret != 0) { 465 rte_rib_remove(rib, ip, depth); 466 return ret; 467 } 468 if ((depth > 24) && (tmp == NULL)) 469 dp->rsvd_tbl8s++; 470 return 0; 471 case RTE_FIB_DEL: 472 if (node == NULL) 473 return -ENOENT; 474 475 parent = rte_rib_lookup_parent(node); 476 if (parent != NULL) { 477 rte_rib_get_nh(parent, &par_nh); 478 rte_rib_get_nh(node, &node_nh); 479 if (par_nh != node_nh) 480 ret = modify_fib(dp, rib, ip, depth, par_nh); 481 } else 482 ret = modify_fib(dp, rib, ip, depth, dp->def_nh); 483 if (ret == 0) { 484 rte_rib_remove(rib, ip, depth); 485 if (depth > 24) { 486 tmp = rte_rib_get_nxt(rib, ip, 24, NULL, 487 RTE_RIB_GET_NXT_COVER); 488 if (tmp == NULL) 489 dp->rsvd_tbl8s--; 490 } 491 } 492 return ret; 493 default: 494 break; 495 } 496 return -EINVAL; 497 } 498 499 void * 500 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf) 501 { 502 char mem_name[DIR24_8_NAMESIZE]; 503 struct dir24_8_tbl *dp; 504 uint64_t def_nh; 505 uint32_t num_tbl8; 506 enum rte_fib_dir24_8_nh_sz nh_sz; 507 508 if ((name == NULL) || (fib_conf == NULL) || 509 (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) || 510 (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) || 511 (fib_conf->dir24_8.num_tbl8 > 512 get_max_nh(fib_conf->dir24_8.nh_sz)) || 513 (fib_conf->dir24_8.num_tbl8 == 0) || 514 (fib_conf->default_nh > 515 get_max_nh(fib_conf->dir24_8.nh_sz))) { 516 rte_errno = EINVAL; 517 return NULL; 518 } 519 520 def_nh = fib_conf->default_nh; 521 nh_sz = fib_conf->dir24_8.nh_sz; 522 num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8, 523 BITMAP_SLAB_BIT_SIZE); 524 525 snprintf(mem_name, sizeof(mem_name), "DP_%s", name); 526 dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) + 527 DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE, 528 socket_id); 529 if (dp == NULL) { 530 rte_errno = ENOMEM; 531 return NULL; 532 } 533 534 /* Init table with default value */ 535 write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24); 536 537 snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp); 538 uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) * 539 (num_tbl8 + 1); 540 dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz, 541 RTE_CACHE_LINE_SIZE, socket_id); 542 if (dp->tbl8 == NULL) { 543 rte_errno = ENOMEM; 544 rte_free(dp); 545 return NULL; 546 } 547 dp->def_nh = def_nh; 548 dp->nh_sz = nh_sz; 549 dp->number_tbl8s = num_tbl8; 550 551 snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp); 552 dp->tbl8_idxes = rte_zmalloc_socket(mem_name, 553 RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3, 554 RTE_CACHE_LINE_SIZE, socket_id); 555 if (dp->tbl8_idxes == NULL) { 556 rte_errno = ENOMEM; 557 rte_free(dp->tbl8); 558 rte_free(dp); 559 return NULL; 560 } 561 562 return dp; 563 } 564 565 void 566 dir24_8_free(void *p) 567 { 568 struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; 569 570 rte_free(dp->tbl8_idxes); 571 rte_free(dp->tbl8); 572 rte_free(dp); 573 } 574