net/virtio: fix incorrect cast of void *
[dpdk.git] / 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 };