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