table/rte_swx_table_em.c

   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 };