1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2020 Intel Corporation 3 */ 4 #include <stdlib.h> 5 #include <string.h> 6 #include <stdio.h> 7 #include <errno.h> 8 9 #include <rte_common.h> 10 #include <rte_prefetch.h> 11 12 #include "rte_swx_table_em.h" 13 14 #define CHECK(condition, err_code) \ 15 do { \ 16 if (!(condition)) \ 17 return -(err_code); \ 18 } while (0) 19 20 #ifndef RTE_SWX_TABLE_EM_USE_HUGE_PAGES 21 #define RTE_SWX_TABLE_EM_USE_HUGE_PAGES 1 22 #endif 23 24 #if RTE_SWX_TABLE_EM_USE_HUGE_PAGES 25 26 #include <rte_malloc.h> 27 28 static void * 29 env_malloc(size_t size, size_t alignment, int numa_node) 30 { 31 return rte_zmalloc_socket(NULL, size, alignment, numa_node); 32 } 33 34 static void 35 env_free(void *start, size_t size __rte_unused) 36 { 37 rte_free(start); 38 } 39 40 #else 41 42 #include <numa.h> 43 44 static void * 45 env_malloc(size_t size, size_t alignment __rte_unused, int numa_node) 46 { 47 return numa_alloc_onnode(size, numa_node); 48 } 49 50 static void 51 env_free(void *start, size_t size) 52 { 53 numa_free(start, size); 54 } 55 56 #endif 57 58 #if defined(RTE_ARCH_X86_64) 59 60 #include <x86intrin.h> 61 62 #define crc32_u64(crc, v) _mm_crc32_u64(crc, v) 63 64 #else 65 66 static inline uint64_t 67 crc32_u64_generic(uint64_t crc, uint64_t value) 68 { 69 int i; 70 71 crc = (crc & 0xFFFFFFFFLLU) ^ value; 72 for (i = 63; i >= 0; i--) { 73 uint64_t mask; 74 75 mask = -(crc & 1LLU); 76 crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask); 77 } 78 79 return crc; 80 } 81 82 #define crc32_u64(crc, v) crc32_u64_generic(crc, v) 83 84 #endif 85 86 /* Key size needs to be one of: 8, 16, 32 or 64. */ 87 static inline uint32_t 88 hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed) 89 { 90 uint64_t *k = key; 91 uint64_t *m = key_mask; 92 uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5; 93 94 switch (key_size) { 95 case 8: 96 crc0 = crc32_u64(seed, k[0] & m[0]); 97 return crc0; 98 99 case 16: 100 k0 = k[0] & m[0]; 101 102 crc0 = crc32_u64(k0, seed); 103 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); 104 105 crc0 ^= crc1; 106 107 return crc0; 108 109 case 32: 110 k0 = k[0] & m[0]; 111 k2 = k[2] & m[2]; 112 113 crc0 = crc32_u64(k0, seed); 114 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); 115 116 crc2 = crc32_u64(k2, k[3] & m[3]); 117 crc3 = k2 >> 32; 118 119 crc0 = crc32_u64(crc0, crc1); 120 crc1 = crc32_u64(crc2, crc3); 121 122 crc0 ^= crc1; 123 124 return crc0; 125 126 case 64: 127 k0 = k[0] & m[0]; 128 k2 = k[2] & m[2]; 129 k5 = k[5] & m[5]; 130 131 crc0 = crc32_u64(k0, seed); 132 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]); 133 134 crc2 = crc32_u64(k2, k[3] & m[3]); 135 crc3 = crc32_u64(k2 >> 32, k[4] & m[4]); 136 137 crc4 = crc32_u64(k5, k[6] & m[6]); 138 crc5 = crc32_u64(k5 >> 32, k[7] & m[7]); 139 140 crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2); 141 crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5); 142 143 crc0 ^= crc1; 144 145 return crc0; 146 147 default: 148 crc0 = 0; 149 return crc0; 150 } 151 } 152 153 /* n_bytes needs to be a multiple of 8 bytes. */ 154 static void 155 keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes) 156 { 157 uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask; 158 uint32_t i; 159 160 for (i = 0; i < n_bytes / sizeof(uint64_t); i++) 161 dst64[i] = src64[i] & src_mask64[i]; 162 } 163 164 /* 165 * Return: 0 = Keys are NOT equal; 1 = Keys are equal. 166 */ 167 static inline uint32_t 168 keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes) 169 { 170 uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask; 171 172 switch (n_bytes) { 173 case 8: { 174 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); 175 uint32_t result = 1; 176 177 if (xor0) 178 result = 0; 179 return result; 180 } 181 182 case 16: { 183 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); 184 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); 185 uint64_t or = xor0 | xor1; 186 uint32_t result = 1; 187 188 if (or) 189 result = 0; 190 return result; 191 } 192 193 case 32: { 194 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); 195 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); 196 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]); 197 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]); 198 uint64_t or = (xor0 | xor1) | (xor2 | xor3); 199 uint32_t result = 1; 200 201 if (or) 202 result = 0; 203 return result; 204 } 205 206 case 64: { 207 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]); 208 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]); 209 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]); 210 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]); 211 uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]); 212 uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]); 213 uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]); 214 uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]); 215 uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) | 216 ((xor4 | xor5) | (xor6 | xor7)); 217 uint32_t result = 1; 218 219 if (or) 220 result = 0; 221 return result; 222 } 223 224 default: { 225 uint32_t i; 226 227 for (i = 0; i < n_bytes / sizeof(uint64_t); i++) 228 if (a64[i] != (b64[i] & b_mask64[i])) 229 return 0; 230 return 1; 231 } 232 } 233 } 234 235 #define KEYS_PER_BUCKET 4 236 237 struct bucket_extension { 238 struct bucket_extension *next; 239 uint16_t sig[KEYS_PER_BUCKET]; 240 uint32_t key_id[KEYS_PER_BUCKET]; 241 }; 242 243 struct table { 244 /* Input parameters */ 245 struct rte_swx_table_params params; 246 247 /* Internal. */ 248 uint32_t key_size; 249 uint32_t data_size; 250 uint32_t key_size_shl; 251 uint32_t data_size_shl; 252 uint32_t n_buckets; 253 uint32_t n_buckets_ext; 254 uint32_t key_stack_tos; 255 uint32_t bkt_ext_stack_tos; 256 uint64_t total_size; 257 258 /* Memory arrays. */ 259 uint8_t *key_mask; 260 struct bucket_extension *buckets; 261 struct bucket_extension *buckets_ext; 262 uint8_t *keys; 263 uint32_t *key_stack; 264 uint32_t *bkt_ext_stack; 265 uint8_t *data; 266 }; 267 268 static inline uint8_t * 269 table_key(struct table *t, uint32_t key_id) 270 { 271 return &t->keys[(uint64_t)key_id << t->key_size_shl]; 272 } 273 274 static inline uint64_t * 275 table_key_data(struct table *t, uint32_t key_id) 276 { 277 return (uint64_t *)&t->data[(uint64_t)key_id << t->data_size_shl]; 278 } 279 280 static inline int 281 bkt_is_empty(struct bucket_extension *bkt) 282 { 283 return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ? 284 1 : 0; 285 } 286 287 /* Return: 288 * 0 = Bucket key position is NOT empty; 289 * 1 = Bucket key position is empty. 290 */ 291 static inline int 292 bkt_key_is_empty(struct bucket_extension *bkt, uint32_t bkt_pos) 293 { 294 return bkt->sig[bkt_pos] ? 0 : 1; 295 } 296 297 /* Return: 0 = Keys are NOT equal; 1 = Keys are equal. */ 298 static inline int 299 bkt_keycmp(struct table *t, 300 struct bucket_extension *bkt, 301 uint8_t *input_key, 302 uint32_t bkt_pos, 303 uint32_t input_sig) 304 { 305 uint32_t bkt_key_id; 306 uint8_t *bkt_key; 307 308 /* Key signature comparison. */ 309 if (input_sig != bkt->sig[bkt_pos]) 310 return 0; 311 312 /* Key comparison. */ 313 bkt_key_id = bkt->key_id[bkt_pos]; 314 bkt_key = table_key(t, bkt_key_id); 315 return keycmp(bkt_key, input_key, t->key_mask, t->key_size); 316 } 317 318 static inline void 319 bkt_key_install(struct table *t, 320 struct bucket_extension *bkt, 321 struct rte_swx_table_entry *input, 322 uint32_t bkt_pos, 323 uint32_t bkt_key_id, 324 uint32_t input_sig) 325 { 326 uint8_t *bkt_key; 327 uint64_t *bkt_data; 328 329 /* Key signature. */ 330 bkt->sig[bkt_pos] = (uint16_t)input_sig; 331 332 /* Key. */ 333 bkt->key_id[bkt_pos] = bkt_key_id; 334 bkt_key = table_key(t, bkt_key_id); 335 keycpy(bkt_key, input->key, t->key_mask, t->key_size); 336 337 /* Key data. */ 338 bkt_data = table_key_data(t, bkt_key_id); 339 bkt_data[0] = input->action_id; 340 if (t->params.action_data_size && input->action_data) 341 memcpy(&bkt_data[1], 342 input->action_data, 343 t->params.action_data_size); 344 } 345 346 static inline void 347 bkt_key_data_update(struct table *t, 348 struct bucket_extension *bkt, 349 struct rte_swx_table_entry *input, 350 uint32_t bkt_pos) 351 { 352 uint32_t bkt_key_id; 353 uint64_t *bkt_data; 354 355 /* Key. */ 356 bkt_key_id = bkt->key_id[bkt_pos]; 357 358 /* Key data. */ 359 bkt_data = table_key_data(t, bkt_key_id); 360 bkt_data[0] = input->action_id; 361 if (t->params.action_data_size && input->action_data) 362 memcpy(&bkt_data[1], 363 input->action_data, 364 t->params.action_data_size); 365 } 366 367 #define CL RTE_CACHE_LINE_ROUNDUP 368 369 static int 370 __table_create(struct table **table, 371 uint64_t *memory_footprint, 372 struct rte_swx_table_params *params, 373 const char *args __rte_unused, 374 int numa_node) 375 { 376 struct table *t; 377 uint8_t *memory; 378 size_t table_meta_sz, key_mask_sz, bucket_sz, bucket_ext_sz, key_sz, 379 key_stack_sz, bkt_ext_stack_sz, data_sz, total_size; 380 size_t key_mask_offset, bucket_offset, bucket_ext_offset, key_offset, 381 key_stack_offset, bkt_ext_stack_offset, data_offset; 382 uint32_t key_size, key_data_size, n_buckets, n_buckets_ext, i; 383 384 /* Check input arguments. */ 385 CHECK(params, EINVAL); 386 CHECK(params->match_type == RTE_SWX_TABLE_MATCH_EXACT, EINVAL); 387 CHECK(params->key_size, EINVAL); 388 CHECK(params->key_size <= 64, EINVAL); 389 CHECK(params->n_keys_max, EINVAL); 390 391 /* Memory allocation. */ 392 key_size = rte_align64pow2(params->key_size); 393 if (key_size < 8) 394 key_size = 8; 395 key_data_size = rte_align64pow2(params->action_data_size + 8); 396 n_buckets = params->n_keys_max / KEYS_PER_BUCKET; 397 n_buckets_ext = params->n_keys_max / KEYS_PER_BUCKET; 398 399 table_meta_sz = CL(sizeof(struct table)); 400 key_mask_sz = CL(key_size); 401 bucket_sz = CL(n_buckets * sizeof(struct bucket_extension)); 402 bucket_ext_sz = CL(n_buckets_ext * sizeof(struct bucket_extension)); 403 key_sz = CL(params->n_keys_max * key_size); 404 key_stack_sz = CL(params->n_keys_max * sizeof(uint32_t)); 405 bkt_ext_stack_sz = CL(n_buckets_ext * sizeof(uint32_t)); 406 data_sz = CL(params->n_keys_max * key_data_size); 407 total_size = table_meta_sz + key_mask_sz + bucket_sz + bucket_ext_sz + 408 key_sz + key_stack_sz + bkt_ext_stack_sz + data_sz; 409 410 key_mask_offset = table_meta_sz; 411 bucket_offset = key_mask_offset + key_mask_sz; 412 bucket_ext_offset = bucket_offset + bucket_sz; 413 key_offset = bucket_ext_offset + bucket_ext_sz; 414 key_stack_offset = key_offset + key_sz; 415 bkt_ext_stack_offset = key_stack_offset + key_stack_sz; 416 data_offset = bkt_ext_stack_offset + bkt_ext_stack_sz; 417 418 if (!table) { 419 if (memory_footprint) 420 *memory_footprint = total_size; 421 return 0; 422 } 423 424 memory = env_malloc(total_size, RTE_CACHE_LINE_SIZE, numa_node); 425 CHECK(memory, ENOMEM); 426 memset(memory, 0, total_size); 427 428 /* Initialization. */ 429 t = (struct table *)memory; 430 memcpy(&t->params, params, sizeof(*params)); 431 432 t->key_size = key_size; 433 t->data_size = key_data_size; 434 t->key_size_shl = __builtin_ctzl(key_size); 435 t->data_size_shl = __builtin_ctzl(key_data_size); 436 t->n_buckets = n_buckets; 437 t->n_buckets_ext = n_buckets_ext; 438 t->total_size = total_size; 439 440 t->key_mask = &memory[key_mask_offset]; 441 t->buckets = (struct bucket_extension *)&memory[bucket_offset]; 442 t->buckets_ext = (struct bucket_extension *)&memory[bucket_ext_offset]; 443 t->keys = &memory[key_offset]; 444 t->key_stack = (uint32_t *)&memory[key_stack_offset]; 445 t->bkt_ext_stack = (uint32_t *)&memory[bkt_ext_stack_offset]; 446 t->data = &memory[data_offset]; 447 448 t->params.key_mask0 = t->key_mask; 449 450 if (!params->key_mask0) 451 memset(t->key_mask, 0xFF, params->key_size); 452 else 453 memcpy(t->key_mask, params->key_mask0, params->key_size); 454 455 for (i = 0; i < t->params.n_keys_max; i++) 456 t->key_stack[i] = t->params.n_keys_max - 1 - i; 457 t->key_stack_tos = t->params.n_keys_max; 458 459 for (i = 0; i < n_buckets_ext; i++) 460 t->bkt_ext_stack[i] = n_buckets_ext - 1 - i; 461 t->bkt_ext_stack_tos = n_buckets_ext; 462 463 *table = t; 464 return 0; 465 } 466 467 static void 468 table_free(void *table) 469 { 470 struct table *t = table; 471 472 if (!t) 473 return; 474 475 env_free(t, t->total_size); 476 } 477 478 static int 479 table_add(void *table, struct rte_swx_table_entry *entry) 480 { 481 struct table *t = table; 482 struct bucket_extension *bkt0, *bkt, *bkt_prev; 483 uint32_t input_sig, bkt_id, i; 484 485 CHECK(t, EINVAL); 486 CHECK(entry, EINVAL); 487 CHECK(entry->key, EINVAL); 488 489 input_sig = hash(entry->key, t->key_mask, t->key_size, 0); 490 bkt_id = input_sig & (t->n_buckets - 1); 491 bkt0 = &t->buckets[bkt_id]; 492 input_sig = (input_sig >> 16) | 1; 493 494 /* Key is present in the bucket. */ 495 for (bkt = bkt0; bkt; bkt = bkt->next) 496 for (i = 0; i < KEYS_PER_BUCKET; i++) 497 if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) { 498 bkt_key_data_update(t, bkt, entry, i); 499 return 0; 500 } 501 502 /* Key is not present in the bucket. Bucket not full. */ 503 for (bkt = bkt0, bkt_prev = NULL; bkt; bkt_prev = bkt, bkt = bkt->next) 504 for (i = 0; i < KEYS_PER_BUCKET; i++) 505 if (bkt_key_is_empty(bkt, i)) { 506 uint32_t new_bkt_key_id; 507 508 /* Allocate new key & install. */ 509 CHECK(t->key_stack_tos, ENOSPC); 510 new_bkt_key_id = 511 t->key_stack[--t->key_stack_tos]; 512 bkt_key_install(t, bkt, entry, i, 513 new_bkt_key_id, input_sig); 514 return 0; 515 } 516 517 /* Bucket full: extend bucket. */ 518 if (t->bkt_ext_stack_tos && t->key_stack_tos) { 519 struct bucket_extension *new_bkt; 520 uint32_t new_bkt_id, new_bkt_key_id; 521 522 /* Allocate new bucket extension & install. */ 523 new_bkt_id = t->bkt_ext_stack[--t->bkt_ext_stack_tos]; 524 new_bkt = &t->buckets_ext[new_bkt_id]; 525 memset(new_bkt, 0, sizeof(*new_bkt)); 526 bkt_prev->next = new_bkt; 527 528 /* Allocate new key & install. */ 529 new_bkt_key_id = t->key_stack[--t->key_stack_tos]; 530 bkt_key_install(t, new_bkt, entry, 0, 531 new_bkt_key_id, input_sig); 532 return 0; 533 } 534 535 CHECK(0, ENOSPC); 536 } 537 538 static int 539 table_del(void *table, struct rte_swx_table_entry *entry) 540 { 541 struct table *t = table; 542 struct bucket_extension *bkt0, *bkt, *bkt_prev; 543 uint32_t input_sig, bkt_id, i; 544 545 CHECK(t, EINVAL); 546 CHECK(entry, EINVAL); 547 CHECK(entry->key, EINVAL); 548 549 input_sig = hash(entry->key, t->key_mask, t->key_size, 0); 550 bkt_id = input_sig & (t->n_buckets - 1); 551 bkt0 = &t->buckets[bkt_id]; 552 input_sig = (input_sig >> 16) | 1; 553 554 /* Key is present in the bucket. */ 555 for (bkt = bkt0, bkt_prev = NULL; bkt; bkt_prev = bkt, bkt = bkt->next) 556 for (i = 0; i < KEYS_PER_BUCKET; i++) 557 if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) { 558 /* Key free. */ 559 bkt->sig[i] = 0; 560 t->key_stack[t->key_stack_tos++] = 561 bkt->key_id[i]; 562 563 /* Bucket extension free if empty and not the 564 * 1st in bucket. 565 */ 566 if (bkt_prev && bkt_is_empty(bkt)) { 567 bkt_prev->next = bkt->next; 568 bkt_id = bkt - t->buckets_ext; 569 t->bkt_ext_stack[t->bkt_ext_stack_tos++] 570 = bkt_id; 571 } 572 573 return 0; 574 } 575 576 return 0; 577 } 578 579 static uint64_t 580 table_mailbox_size_get_unoptimized(void) 581 { 582 return 0; 583 } 584 585 static int 586 table_lookup_unoptimized(void *table, 587 void *mailbox __rte_unused, 588 uint8_t **key, 589 uint64_t *action_id, 590 uint8_t **action_data, 591 int *hit) 592 { 593 struct table *t = table; 594 struct bucket_extension *bkt0, *bkt; 595 uint8_t *input_key; 596 uint32_t input_sig, bkt_id, i; 597 598 input_key = &(*key)[t->params.key_offset]; 599 600 input_sig = hash(input_key, t->key_mask, t->key_size, 0); 601 bkt_id = input_sig & (t->n_buckets - 1); 602 bkt0 = &t->buckets[bkt_id]; 603 input_sig = (input_sig >> 16) | 1; 604 605 /* Key is present in the bucket. */ 606 for (bkt = bkt0; bkt; bkt = bkt->next) 607 for (i = 0; i < KEYS_PER_BUCKET; i++) 608 if (bkt_keycmp(t, bkt, input_key, i, input_sig)) { 609 uint32_t bkt_key_id; 610 uint64_t *bkt_data; 611 612 /* Key. */ 613 bkt_key_id = bkt->key_id[i]; 614 615 /* Key data. */ 616 bkt_data = table_key_data(t, bkt_key_id); 617 *action_id = bkt_data[0]; 618 *action_data = (uint8_t *)&bkt_data[1]; 619 *hit = 1; 620 return 1; 621 } 622 623 *hit = 0; 624 return 1; 625 } 626 627 struct mailbox { 628 struct bucket_extension *bkt; 629 uint32_t input_sig; 630 uint32_t bkt_key_id; 631 uint32_t sig_match; 632 uint32_t sig_match_many; 633 int state; 634 }; 635 636 static uint64_t 637 table_mailbox_size_get(void) 638 { 639 return sizeof(struct mailbox); 640 } 641 642 /* 643 * mask = match bitmask 644 * match = at least one match 645 * match_many = more than one match 646 * match_pos = position of first match 647 * 648 *+------+-------+------------+-----------+ 649 *| mask | match | match_many | match_pos | 650 *+------+-------+------------+-----------+ 651 *| 0000 | 0 | 0 | 00 | 652 *| 0001 | 1 | 0 | 00 | 653 *| 0010 | 1 | 0 | 01 | 654 *| 0011 | 1 | 1 | 00 | 655 *+------+-------+------------+-----------+ 656 *| 0100 | 1 | 0 | 10 | 657 *| 0101 | 1 | 1 | 00 | 658 *| 0110 | 1 | 1 | 01 | 659 *| 0111 | 1 | 1 | 00 | 660 *+------+-------+------------+-----------+ 661 *| 1000 | 1 | 0 | 11 | 662 *| 1001 | 1 | 1 | 00 | 663 *| 1010 | 1 | 1 | 01 | 664 *| 1011 | 1 | 1 | 00 | 665 *+------+-------+------------+-----------+ 666 *| 1100 | 1 | 1 | 10 | 667 *| 1101 | 1 | 1 | 00 | 668 *| 1110 | 1 | 1 | 01 | 669 *| 1111 | 1 | 1 | 00 | 670 *+------+-------+------------+-----------+ 671 * 672 * match = 1111_1111_1111_1110 = 0xFFFE 673 * match_many = 1111_1110_1110_1000 = 0xFEE8 674 * match_pos = 0001_0010_0001_0011__0001_0010_0001_0000 = 0x12131210 675 * 676 */ 677 678 #define LUT_MATCH 0xFFFE 679 #define LUT_MATCH_MANY 0xFEE8 680 #define LUT_MATCH_POS 0x12131210 681 682 static int 683 table_lookup(void *table, 684 void *mailbox, 685 uint8_t **key, 686 uint64_t *action_id, 687 uint8_t **action_data, 688 int *hit) 689 { 690 struct table *t = table; 691 struct mailbox *m = mailbox; 692 693 switch (m->state) { 694 case 0: { 695 uint8_t *input_key = &(*key)[t->params.key_offset]; 696 struct bucket_extension *bkt; 697 uint32_t input_sig, bkt_id; 698 699 input_sig = hash(input_key, t->key_mask, t->key_size, 0); 700 bkt_id = input_sig & (t->n_buckets - 1); 701 bkt = &t->buckets[bkt_id]; 702 rte_prefetch0(bkt); 703 704 m->bkt = bkt; 705 m->input_sig = (input_sig >> 16) | 1; 706 m->state++; 707 return 0; 708 } 709 710 case 1: { 711 struct bucket_extension *bkt = m->bkt; 712 uint32_t input_sig = m->input_sig; 713 uint32_t bkt_sig0, bkt_sig1, bkt_sig2, bkt_sig3; 714 uint32_t mask0 = 0, mask1 = 0, mask2 = 0, mask3 = 0, mask_all; 715 uint32_t sig_match = LUT_MATCH; 716 uint32_t sig_match_many = LUT_MATCH_MANY; 717 uint32_t sig_match_pos = LUT_MATCH_POS; 718 uint32_t bkt_key_id; 719 720 bkt_sig0 = input_sig ^ bkt->sig[0]; 721 if (!bkt_sig0) 722 mask0 = 1 << 0; 723 724 bkt_sig1 = input_sig ^ bkt->sig[1]; 725 if (!bkt_sig1) 726 mask1 = 1 << 1; 727 728 bkt_sig2 = input_sig ^ bkt->sig[2]; 729 if (!bkt_sig2) 730 mask2 = 1 << 2; 731 732 bkt_sig3 = input_sig ^ bkt->sig[3]; 733 if (!bkt_sig3) 734 mask3 = 1 << 3; 735 736 mask_all = (mask0 | mask1) | (mask2 | mask3); 737 sig_match = (sig_match >> mask_all) & 1; 738 sig_match_many = (sig_match_many >> mask_all) & 1; 739 sig_match_pos = (sig_match_pos >> (mask_all << 1)) & 3; 740 741 bkt_key_id = bkt->key_id[sig_match_pos]; 742 rte_prefetch0(table_key(t, bkt_key_id)); 743 rte_prefetch0(table_key_data(t, bkt_key_id)); 744 745 m->bkt_key_id = bkt_key_id; 746 m->sig_match = sig_match; 747 m->sig_match_many = sig_match_many; 748 m->state++; 749 return 0; 750 } 751 752 case 2: { 753 uint8_t *input_key = &(*key)[t->params.key_offset]; 754 struct bucket_extension *bkt = m->bkt; 755 uint32_t bkt_key_id = m->bkt_key_id; 756 uint8_t *bkt_key = table_key(t, bkt_key_id); 757 uint64_t *bkt_data = table_key_data(t, bkt_key_id); 758 uint32_t lkp_hit; 759 760 lkp_hit = keycmp(bkt_key, input_key, t->key_mask, t->key_size); 761 lkp_hit &= m->sig_match; 762 *action_id = bkt_data[0]; 763 *action_data = (uint8_t *)&bkt_data[1]; 764 *hit = lkp_hit; 765 766 m->state = 0; 767 768 if (!lkp_hit && (m->sig_match_many || bkt->next)) 769 return table_lookup_unoptimized(t, 770 m, 771 key, 772 action_id, 773 action_data, 774 hit); 775 776 return 1; 777 } 778 779 default: 780 return 0; 781 } 782 } 783 784 static void * 785 table_create(struct rte_swx_table_params *params, 786 struct rte_swx_table_entry_list *entries, 787 const char *args, 788 int numa_node) 789 { 790 struct table *t; 791 struct rte_swx_table_entry *entry; 792 int status; 793 794 /* Table create. */ 795 status = __table_create(&t, NULL, params, args, numa_node); 796 if (status) 797 return NULL; 798 799 /* Table add entries. */ 800 if (!entries) 801 return t; 802 803 TAILQ_FOREACH(entry, entries, node) { 804 int status; 805 806 status = table_add(t, entry); 807 if (status) { 808 table_free(t); 809 return NULL; 810 } 811 } 812 813 return t; 814 } 815 816 static uint64_t 817 table_footprint(struct rte_swx_table_params *params, 818 struct rte_swx_table_entry_list *entries __rte_unused, 819 const char *args) 820 { 821 uint64_t memory_footprint; 822 int status; 823 824 status = __table_create(NULL, &memory_footprint, params, args, 0); 825 if (status) 826 return 0; 827 828 return memory_footprint; 829 } 830 831 struct rte_swx_table_ops rte_swx_table_exact_match_unoptimized_ops = { 832 .footprint_get = table_footprint, 833 .mailbox_size_get = table_mailbox_size_get_unoptimized, 834 .create = table_create, 835 .add = table_add, 836 .del = table_del, 837 .lkp = table_lookup_unoptimized, 838 .free = table_free, 839 }; 840 841 struct rte_swx_table_ops rte_swx_table_exact_match_ops = { 842 .footprint_get = table_footprint, 843 .mailbox_size_get = table_mailbox_size_get, 844 .create = table_create, 845 .add = table_add, 846 .del = table_del, 847 .lkp = table_lookup, 848 .free = table_free, 849 }; 850