crypto/mlx5: add maximum segments configuration
[dpdk.git] / lib / table / rte_table_hash_key32.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2  * Copyright(c) 2010-2017 Intel Corporation
3  */
4 #include <string.h>
5 #include <stdio.h>
6
7 #include <rte_common.h>
8 #include <rte_mbuf.h>
9 #include <rte_memory.h>
10 #include <rte_malloc.h>
11 #include <rte_log.h>
12
13 #include "rte_table_hash.h"
14 #include "rte_lru.h"
15
16 #define KEY_SIZE                                                32
17
18 #define KEYS_PER_BUCKET                                 4
19
20 #define RTE_BUCKET_ENTRY_VALID                                          0x1LLU
21
22 #ifdef RTE_TABLE_STATS_COLLECT
23
24 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(table, val) \
25         table->stats.n_pkts_in += val
26 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(table, val) \
27         table->stats.n_pkts_lookup_miss += val
28
29 #else
30
31 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(table, val)
32 #define RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(table, val)
33
34 #endif
35
36 #ifdef RTE_ARCH_64
37 struct rte_bucket_4_32 {
38         /* Cache line 0 */
39         uint64_t signature[4 + 1];
40         uint64_t lru_list;
41         struct rte_bucket_4_32 *next;
42         uint64_t next_valid;
43
44         /* Cache lines 1 and 2 */
45         uint64_t key[4][4];
46
47         /* Cache line 3 */
48         uint8_t data[0];
49 };
50 #else
51 struct rte_bucket_4_32 {
52         /* Cache line 0 */
53         uint64_t signature[4 + 1];
54         uint64_t lru_list;
55         struct rte_bucket_4_32 *next;
56         uint32_t pad;
57         uint64_t next_valid;
58
59         /* Cache lines 1 and 2 */
60         uint64_t key[4][4];
61
62         /* Cache line 3 */
63         uint8_t data[0];
64 };
65 #endif
66
67 struct rte_table_hash {
68         struct rte_table_stats stats;
69
70         /* Input parameters */
71         uint32_t n_buckets;
72         uint32_t key_size;
73         uint32_t entry_size;
74         uint32_t bucket_size;
75         uint32_t key_offset;
76         uint64_t key_mask[4];
77         rte_table_hash_op_hash f_hash;
78         uint64_t seed;
79
80         /* Extendible buckets */
81         uint32_t n_buckets_ext;
82         uint32_t stack_pos;
83         uint32_t *stack;
84
85         /* Lookup table */
86         uint8_t memory[0] __rte_cache_aligned;
87 };
88
89 static int
90 keycmp(void *a, void *b, void *b_mask)
91 {
92         uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
93
94         return (a64[0] != (b64[0] & b_mask64[0])) ||
95                 (a64[1] != (b64[1] & b_mask64[1])) ||
96                 (a64[2] != (b64[2] & b_mask64[2])) ||
97                 (a64[3] != (b64[3] & b_mask64[3]));
98 }
99
100 static void
101 keycpy(void *dst, void *src, void *src_mask)
102 {
103         uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
104
105         dst64[0] = src64[0] & src_mask64[0];
106         dst64[1] = src64[1] & src_mask64[1];
107         dst64[2] = src64[2] & src_mask64[2];
108         dst64[3] = src64[3] & src_mask64[3];
109 }
110
111 static int
112 check_params_create(struct rte_table_hash_params *params)
113 {
114         /* name */
115         if (params->name == NULL) {
116                 RTE_LOG(ERR, TABLE, "%s: name invalid value\n", __func__);
117                 return -EINVAL;
118         }
119
120         /* key_size */
121         if (params->key_size != KEY_SIZE) {
122                 RTE_LOG(ERR, TABLE, "%s: key_size invalid value\n", __func__);
123                 return -EINVAL;
124         }
125
126         /* n_keys */
127         if (params->n_keys == 0) {
128                 RTE_LOG(ERR, TABLE, "%s: n_keys is zero\n", __func__);
129                 return -EINVAL;
130         }
131
132         /* n_buckets */
133         if ((params->n_buckets == 0) ||
134                 (!rte_is_power_of_2(params->n_buckets))) {
135                 RTE_LOG(ERR, TABLE, "%s: n_buckets invalid value\n", __func__);
136                 return -EINVAL;
137         }
138
139         /* f_hash */
140         if (params->f_hash == NULL) {
141                 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
142                         __func__);
143                 return -EINVAL;
144         }
145
146         return 0;
147 }
148
149 static void *
150 rte_table_hash_create_key32_lru(void *params,
151                 int socket_id,
152                 uint32_t entry_size)
153 {
154         struct rte_table_hash_params *p = params;
155         struct rte_table_hash *f;
156         uint64_t bucket_size, total_size;
157         uint32_t n_buckets, i;
158
159         /* Check input parameters */
160         if ((check_params_create(p) != 0) ||
161                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
162                 ((sizeof(struct rte_bucket_4_32) % 64) != 0))
163                 return NULL;
164
165         /*
166          * Table dimensioning
167          *
168          * Objective: Pick the number of buckets (n_buckets) so that there a chance
169          * to store n_keys keys in the table.
170          *
171          * Note: Since the buckets do not get extended, it is not possible to
172          * guarantee that n_keys keys can be stored in the table at any time. In the
173          * worst case scenario when all the n_keys fall into the same bucket, only
174          * a maximum of KEYS_PER_BUCKET keys will be stored in the table. This case
175          * defeats the purpose of the hash table. It indicates unsuitable f_hash or
176          * n_keys to n_buckets ratio.
177          *
178          * MIN(n_buckets) = (n_keys + KEYS_PER_BUCKET - 1) / KEYS_PER_BUCKET
179          */
180         n_buckets = rte_align32pow2(
181                 (p->n_keys + KEYS_PER_BUCKET - 1) / KEYS_PER_BUCKET);
182         n_buckets = RTE_MAX(n_buckets, p->n_buckets);
183
184         /* Memory allocation */
185         bucket_size = RTE_CACHE_LINE_ROUNDUP(sizeof(struct rte_bucket_4_32) +
186                 KEYS_PER_BUCKET * entry_size);
187         total_size = sizeof(struct rte_table_hash) + n_buckets * bucket_size;
188         if (total_size > SIZE_MAX) {
189                 RTE_LOG(ERR, TABLE, "%s: Cannot allocate %" PRIu64 " bytes "
190                         "for hash table %s\n",
191                         __func__, total_size, p->name);
192                 return NULL;
193         }
194
195         f = rte_zmalloc_socket(p->name,
196                 (size_t)total_size,
197                 RTE_CACHE_LINE_SIZE,
198                 socket_id);
199         if (f == NULL) {
200                 RTE_LOG(ERR, TABLE, "%s: Cannot allocate %" PRIu64 " bytes "
201                         "for hash table %s\n",
202                         __func__, total_size, p->name);
203                 return NULL;
204         }
205         RTE_LOG(INFO, TABLE,
206                 "%s: Hash table %s memory footprint "
207                 "is %" PRIu64 " bytes\n",
208                 __func__, p->name, total_size);
209
210         /* Memory initialization */
211         f->n_buckets = n_buckets;
212         f->key_size = KEY_SIZE;
213         f->entry_size = entry_size;
214         f->bucket_size = bucket_size;
215         f->key_offset = p->key_offset;
216         f->f_hash = p->f_hash;
217         f->seed = p->seed;
218
219         if (p->key_mask != NULL) {
220                 f->key_mask[0] = ((uint64_t *)p->key_mask)[0];
221                 f->key_mask[1] = ((uint64_t *)p->key_mask)[1];
222                 f->key_mask[2] = ((uint64_t *)p->key_mask)[2];
223                 f->key_mask[3] = ((uint64_t *)p->key_mask)[3];
224         } else {
225                 f->key_mask[0] = 0xFFFFFFFFFFFFFFFFLLU;
226                 f->key_mask[1] = 0xFFFFFFFFFFFFFFFFLLU;
227                 f->key_mask[2] = 0xFFFFFFFFFFFFFFFFLLU;
228                 f->key_mask[3] = 0xFFFFFFFFFFFFFFFFLLU;
229         }
230
231         for (i = 0; i < n_buckets; i++) {
232                 struct rte_bucket_4_32 *bucket;
233
234                 bucket = (struct rte_bucket_4_32 *) &f->memory[i *
235                         f->bucket_size];
236                 bucket->lru_list = 0x0000000100020003LLU;
237         }
238
239         return f;
240 }
241
242 static int
243 rte_table_hash_free_key32_lru(void *table)
244 {
245         struct rte_table_hash *f = table;
246
247         /* Check input parameters */
248         if (f == NULL) {
249                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
250                 return -EINVAL;
251         }
252
253         rte_free(f);
254         return 0;
255 }
256
257 static int
258 rte_table_hash_entry_add_key32_lru(
259         void *table,
260         void *key,
261         void *entry,
262         int *key_found,
263         void **entry_ptr)
264 {
265         struct rte_table_hash *f = table;
266         struct rte_bucket_4_32 *bucket;
267         uint64_t signature, pos;
268         uint32_t bucket_index, i;
269
270         signature = f->f_hash(key, f->key_mask, f->key_size, f->seed);
271         bucket_index = signature & (f->n_buckets - 1);
272         bucket = (struct rte_bucket_4_32 *)
273                 &f->memory[bucket_index * f->bucket_size];
274         signature |= RTE_BUCKET_ENTRY_VALID;
275
276         /* Key is present in the bucket */
277         for (i = 0; i < 4; i++) {
278                 uint64_t bucket_signature = bucket->signature[i];
279                 uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
280
281                 if ((bucket_signature == signature) &&
282                         (keycmp(bucket_key, key, f->key_mask) == 0)) {
283                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
284
285                         memcpy(bucket_data, entry, f->entry_size);
286                         lru_update(bucket, i);
287                         *key_found = 1;
288                         *entry_ptr = (void *) bucket_data;
289                         return 0;
290                 }
291         }
292
293         /* Key is not present in the bucket */
294         for (i = 0; i < 4; i++) {
295                 uint64_t bucket_signature = bucket->signature[i];
296                 uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
297
298                 if (bucket_signature == 0) {
299                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
300
301                         bucket->signature[i] = signature;
302                         keycpy(bucket_key, key, f->key_mask);
303                         memcpy(bucket_data, entry, f->entry_size);
304                         lru_update(bucket, i);
305                         *key_found = 0;
306                         *entry_ptr = (void *) bucket_data;
307
308                         return 0;
309                 }
310         }
311
312         /* Bucket full: replace LRU entry */
313         pos = lru_pos(bucket);
314         bucket->signature[pos] = signature;
315         keycpy(&bucket->key[pos], key, f->key_mask);
316         memcpy(&bucket->data[pos * f->entry_size], entry, f->entry_size);
317         lru_update(bucket, pos);
318         *key_found = 0;
319         *entry_ptr = (void *) &bucket->data[pos * f->entry_size];
320
321         return 0;
322 }
323
324 static int
325 rte_table_hash_entry_delete_key32_lru(
326         void *table,
327         void *key,
328         int *key_found,
329         void *entry)
330 {
331         struct rte_table_hash *f = table;
332         struct rte_bucket_4_32 *bucket;
333         uint64_t signature;
334         uint32_t bucket_index, i;
335
336         signature = f->f_hash(key, f->key_mask, f->key_size, f->seed);
337         bucket_index = signature & (f->n_buckets - 1);
338         bucket = (struct rte_bucket_4_32 *)
339                 &f->memory[bucket_index * f->bucket_size];
340         signature |= RTE_BUCKET_ENTRY_VALID;
341
342         /* Key is present in the bucket */
343         for (i = 0; i < 4; i++) {
344                 uint64_t bucket_signature = bucket->signature[i];
345                 uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
346
347                 if ((bucket_signature == signature) &&
348                         (keycmp(bucket_key, key, f->key_mask) == 0)) {
349                         uint8_t *bucket_data = &bucket->data[i * f->entry_size];
350
351                         bucket->signature[i] = 0;
352                         *key_found = 1;
353                         if (entry)
354                                 memcpy(entry, bucket_data, f->entry_size);
355
356                         return 0;
357                 }
358         }
359
360         /* Key is not present in the bucket */
361         *key_found = 0;
362         return 0;
363 }
364
365 static void *
366 rte_table_hash_create_key32_ext(void *params,
367         int socket_id,
368         uint32_t entry_size)
369 {
370         struct rte_table_hash_params *p = params;
371         struct rte_table_hash *f;
372         uint64_t bucket_size, stack_size, total_size;
373         uint32_t n_buckets_ext, i;
374
375         /* Check input parameters */
376         if ((check_params_create(p) != 0) ||
377                 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
378                 ((sizeof(struct rte_bucket_4_32) % 64) != 0))
379                 return NULL;
380
381         /*
382          * Table dimensioning
383          *
384          * Objective: Pick the number of bucket extensions (n_buckets_ext) so that
385          * it is guaranteed that n_keys keys can be stored in the table at any time.
386          *
387          * The worst case scenario takes place when all the n_keys keys fall into
388          * the same bucket. Actually, due to the KEYS_PER_BUCKET scheme, the worst
389          * case takes place when (n_keys - KEYS_PER_BUCKET + 1) keys fall into the
390          * same bucket, while the remaining (KEYS_PER_BUCKET - 1) keys each fall
391          * into a different bucket. This case defeats the purpose of the hash table.
392          * It indicates unsuitable f_hash or n_keys to n_buckets ratio.
393          *
394          * n_buckets_ext = n_keys / KEYS_PER_BUCKET + KEYS_PER_BUCKET - 1
395          */
396         n_buckets_ext = p->n_keys / KEYS_PER_BUCKET + KEYS_PER_BUCKET - 1;
397
398         /* Memory allocation */
399         bucket_size = RTE_CACHE_LINE_ROUNDUP(sizeof(struct rte_bucket_4_32) +
400                 KEYS_PER_BUCKET * entry_size);
401         stack_size = RTE_CACHE_LINE_ROUNDUP(n_buckets_ext * sizeof(uint32_t));
402         total_size = sizeof(struct rte_table_hash) +
403                 (p->n_buckets + n_buckets_ext) * bucket_size + stack_size;
404         if (total_size > SIZE_MAX) {
405                 RTE_LOG(ERR, TABLE, "%s: Cannot allocate %" PRIu64 " bytes "
406                         "for hash table %s\n",
407                         __func__, total_size, p->name);
408                 return NULL;
409         }
410
411         f = rte_zmalloc_socket(p->name,
412                 (size_t)total_size,
413                 RTE_CACHE_LINE_SIZE,
414                 socket_id);
415         if (f == NULL) {
416                 RTE_LOG(ERR, TABLE, "%s: Cannot allocate %" PRIu64 " bytes "
417                         "for hash table %s\n",
418                         __func__, total_size, p->name);
419                 return NULL;
420         }
421         RTE_LOG(INFO, TABLE,
422                 "%s: Hash table %s memory footprint "
423                 "is %" PRIu64" bytes\n",
424                 __func__, p->name, total_size);
425
426         /* Memory initialization */
427         f->n_buckets = p->n_buckets;
428         f->key_size = KEY_SIZE;
429         f->entry_size = entry_size;
430         f->bucket_size = bucket_size;
431         f->key_offset = p->key_offset;
432         f->f_hash = p->f_hash;
433         f->seed = p->seed;
434
435         f->n_buckets_ext = n_buckets_ext;
436         f->stack_pos = n_buckets_ext;
437         f->stack = (uint32_t *)
438                 &f->memory[(p->n_buckets + n_buckets_ext) * f->bucket_size];
439
440         if (p->key_mask != NULL) {
441                 f->key_mask[0] = (((uint64_t *)p->key_mask)[0]);
442                 f->key_mask[1] = (((uint64_t *)p->key_mask)[1]);
443                 f->key_mask[2] = (((uint64_t *)p->key_mask)[2]);
444                 f->key_mask[3] = (((uint64_t *)p->key_mask)[3]);
445         } else {
446                 f->key_mask[0] = 0xFFFFFFFFFFFFFFFFLLU;
447                 f->key_mask[1] = 0xFFFFFFFFFFFFFFFFLLU;
448                 f->key_mask[2] = 0xFFFFFFFFFFFFFFFFLLU;
449                 f->key_mask[3] = 0xFFFFFFFFFFFFFFFFLLU;
450         }
451
452         for (i = 0; i < n_buckets_ext; i++)
453                 f->stack[i] = i;
454
455         return f;
456 }
457
458 static int
459 rte_table_hash_free_key32_ext(void *table)
460 {
461         struct rte_table_hash *f = table;
462
463         /* Check input parameters */
464         if (f == NULL) {
465                 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
466                 return -EINVAL;
467         }
468
469         rte_free(f);
470         return 0;
471 }
472
473 static int
474 rte_table_hash_entry_add_key32_ext(
475         void *table,
476         void *key,
477         void *entry,
478         int *key_found,
479         void **entry_ptr)
480 {
481         struct rte_table_hash *f = table;
482         struct rte_bucket_4_32 *bucket0, *bucket, *bucket_prev;
483         uint64_t signature;
484         uint32_t bucket_index, i;
485
486         signature = f->f_hash(key, f->key_mask, f->key_size, f->seed);
487         bucket_index = signature & (f->n_buckets - 1);
488         bucket0 = (struct rte_bucket_4_32 *)
489                         &f->memory[bucket_index * f->bucket_size];
490         signature |= RTE_BUCKET_ENTRY_VALID;
491
492         /* Key is present in the bucket */
493         for (bucket = bucket0; bucket != NULL; bucket = bucket->next) {
494                 for (i = 0; i < 4; i++) {
495                         uint64_t bucket_signature = bucket->signature[i];
496                         uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
497
498                         if ((bucket_signature == signature) &&
499                                 (keycmp(bucket_key, key, f->key_mask) == 0)) {
500                                 uint8_t *bucket_data = &bucket->data[i *
501                                         f->entry_size];
502
503                                 memcpy(bucket_data, entry, f->entry_size);
504                                 *key_found = 1;
505                                 *entry_ptr = (void *) bucket_data;
506
507                                 return 0;
508                         }
509                 }
510         }
511
512         /* Key is not present in the bucket */
513         for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
514                 bucket_prev = bucket, bucket = bucket->next)
515                 for (i = 0; i < 4; i++) {
516                         uint64_t bucket_signature = bucket->signature[i];
517                         uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
518
519                         if (bucket_signature == 0) {
520                                 uint8_t *bucket_data = &bucket->data[i *
521                                         f->entry_size];
522
523                                 bucket->signature[i] = signature;
524                                 keycpy(bucket_key, key, f->key_mask);
525                                 memcpy(bucket_data, entry, f->entry_size);
526                                 *key_found = 0;
527                                 *entry_ptr = (void *) bucket_data;
528
529                                 return 0;
530                         }
531                 }
532
533         /* Bucket full: extend bucket */
534         if (f->stack_pos > 0) {
535                 bucket_index = f->stack[--f->stack_pos];
536
537                 bucket = (struct rte_bucket_4_32 *)
538                         &f->memory[(f->n_buckets + bucket_index) *
539                         f->bucket_size];
540                 bucket_prev->next = bucket;
541                 bucket_prev->next_valid = 1;
542
543                 bucket->signature[0] = signature;
544                 keycpy(&bucket->key[0], key, f->key_mask);
545                 memcpy(&bucket->data[0], entry, f->entry_size);
546                 *key_found = 0;
547                 *entry_ptr = (void *) &bucket->data[0];
548                 return 0;
549         }
550
551         return -ENOSPC;
552 }
553
554 static int
555 rte_table_hash_entry_delete_key32_ext(
556         void *table,
557         void *key,
558         int *key_found,
559         void *entry)
560 {
561         struct rte_table_hash *f = table;
562         struct rte_bucket_4_32 *bucket0, *bucket, *bucket_prev;
563         uint64_t signature;
564         uint32_t bucket_index, i;
565
566         signature = f->f_hash(key, f->key_mask, f->key_size, f->seed);
567         bucket_index = signature & (f->n_buckets - 1);
568         bucket0 = (struct rte_bucket_4_32 *)
569                 &f->memory[bucket_index * f->bucket_size];
570         signature |= RTE_BUCKET_ENTRY_VALID;
571
572         /* Key is present in the bucket */
573         for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
574                 bucket_prev = bucket, bucket = bucket->next)
575                 for (i = 0; i < 4; i++) {
576                         uint64_t bucket_signature = bucket->signature[i];
577                         uint8_t *bucket_key = (uint8_t *) &bucket->key[i];
578
579                         if ((bucket_signature == signature) &&
580                                 (keycmp(bucket_key, key, f->key_mask) == 0)) {
581                                 uint8_t *bucket_data = &bucket->data[i *
582                                         f->entry_size];
583
584                                 bucket->signature[i] = 0;
585                                 *key_found = 1;
586                                 if (entry)
587                                         memcpy(entry, bucket_data, f->entry_size);
588
589                                 if ((bucket->signature[0] == 0) &&
590                                         (bucket->signature[1] == 0) &&
591                                         (bucket->signature[2] == 0) &&
592                                         (bucket->signature[3] == 0) &&
593                                         (bucket_prev != NULL)) {
594                                         bucket_prev->next = bucket->next;
595                                         bucket_prev->next_valid =
596                                                 bucket->next_valid;
597
598                                         memset(bucket, 0,
599                                                 sizeof(struct rte_bucket_4_32));
600                                         bucket_index = (((uint8_t *)bucket -
601                                                 (uint8_t *)f->memory)/f->bucket_size) - f->n_buckets;
602                                         f->stack[f->stack_pos++] = bucket_index;
603                                 }
604
605                                 return 0;
606                         }
607                 }
608
609         /* Key is not present in the bucket */
610         *key_found = 0;
611         return 0;
612 }
613
614 #define lookup_key32_cmp(key_in, bucket, pos, f)                        \
615 {                                                               \
616         uint64_t xor[4][4], or[4], signature[4], k[4];          \
617                                                                 \
618         k[0] = key_in[0] & f->key_mask[0];                              \
619         k[1] = key_in[1] & f->key_mask[1];                              \
620         k[2] = key_in[2] & f->key_mask[2];                              \
621         k[3] = key_in[3] & f->key_mask[3];                              \
622                                                                 \
623         signature[0] = ((~bucket->signature[0]) & 1);           \
624         signature[1] = ((~bucket->signature[1]) & 1);           \
625         signature[2] = ((~bucket->signature[2]) & 1);           \
626         signature[3] = ((~bucket->signature[3]) & 1);           \
627                                                                 \
628         xor[0][0] = k[0] ^ bucket->key[0][0];                   \
629         xor[0][1] = k[1] ^ bucket->key[0][1];                   \
630         xor[0][2] = k[2] ^ bucket->key[0][2];                   \
631         xor[0][3] = k[3] ^ bucket->key[0][3];                   \
632                                                                 \
633         xor[1][0] = k[0] ^ bucket->key[1][0];                   \
634         xor[1][1] = k[1] ^ bucket->key[1][1];                   \
635         xor[1][2] = k[2] ^ bucket->key[1][2];                   \
636         xor[1][3] = k[3] ^ bucket->key[1][3];                   \
637                                                                 \
638         xor[2][0] = k[0] ^ bucket->key[2][0];                   \
639         xor[2][1] = k[1] ^ bucket->key[2][1];                   \
640         xor[2][2] = k[2] ^ bucket->key[2][2];                   \
641         xor[2][3] = k[3] ^ bucket->key[2][3];                   \
642                                                                 \
643         xor[3][0] = k[0] ^ bucket->key[3][0];                   \
644         xor[3][1] = k[1] ^ bucket->key[3][1];                   \
645         xor[3][2] = k[2] ^ bucket->key[3][2];                   \
646         xor[3][3] = k[3] ^ bucket->key[3][3];                   \
647                                                                 \
648         or[0] = xor[0][0] | xor[0][1] | xor[0][2] | xor[0][3] | signature[0];\
649         or[1] = xor[1][0] | xor[1][1] | xor[1][2] | xor[1][3] | signature[1];\
650         or[2] = xor[2][0] | xor[2][1] | xor[2][2] | xor[2][3] | signature[2];\
651         or[3] = xor[3][0] | xor[3][1] | xor[3][2] | xor[3][3] | signature[3];\
652                                                                 \
653         pos = 4;                                                \
654         if (or[0] == 0)                                         \
655                 pos = 0;                                        \
656         if (or[1] == 0)                                         \
657                 pos = 1;                                        \
658         if (or[2] == 0)                                         \
659                 pos = 2;                                        \
660         if (or[3] == 0)                                         \
661                 pos = 3;                                        \
662 }
663
664 #define lookup1_stage0(pkt0_index, mbuf0, pkts, pkts_mask, f)   \
665 {                                                               \
666         uint64_t pkt_mask;                                      \
667         uint32_t key_offset = f->key_offset;    \
668                                                                 \
669         pkt0_index = __builtin_ctzll(pkts_mask);                \
670         pkt_mask = 1LLU << pkt0_index;                          \
671         pkts_mask &= ~pkt_mask;                                 \
672                                                                 \
673         mbuf0 = pkts[pkt0_index];                               \
674         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf0, key_offset));\
675 }
676
677 #define lookup1_stage1(mbuf1, bucket1, f)                               \
678 {                                                               \
679         uint64_t *key;                                          \
680         uint64_t signature;                                     \
681         uint32_t bucket_index;                                  \
682                                                                 \
683         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf1, f->key_offset);       \
684         signature = f->f_hash(key, f->key_mask, KEY_SIZE, f->seed);     \
685                                                                 \
686         bucket_index = signature & (f->n_buckets - 1);          \
687         bucket1 = (struct rte_bucket_4_32 *)                    \
688                 &f->memory[bucket_index * f->bucket_size];      \
689         rte_prefetch0(bucket1);                                 \
690         rte_prefetch0((void *)(((uintptr_t) bucket1) + RTE_CACHE_LINE_SIZE));\
691         rte_prefetch0((void *)(((uintptr_t) bucket1) + 2 * RTE_CACHE_LINE_SIZE));\
692 }
693
694 #define lookup1_stage2_lru(pkt2_index, mbuf2, bucket2,          \
695         pkts_mask_out, entries, f)                              \
696 {                                                               \
697         void *a;                                                \
698         uint64_t pkt_mask;                                      \
699         uint64_t *key;                                          \
700         uint32_t pos;                                           \
701                                                                 \
702         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
703         lookup_key32_cmp(key, bucket2, pos, f);                 \
704                                                                 \
705         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
706         pkts_mask_out |= pkt_mask;                              \
707                                                                 \
708         a = (void *) &bucket2->data[pos * f->entry_size];       \
709         rte_prefetch0(a);                                       \
710         entries[pkt2_index] = a;                                \
711         lru_update(bucket2, pos);                               \
712 }
713
714 #define lookup1_stage2_ext(pkt2_index, mbuf2, bucket2, pkts_mask_out,\
715         entries, buckets_mask, buckets, keys, f)                \
716 {                                                               \
717         struct rte_bucket_4_32 *bucket_next;                    \
718         void *a;                                                \
719         uint64_t pkt_mask, bucket_mask;                         \
720         uint64_t *key;                                          \
721         uint32_t pos;                                           \
722                                                                 \
723         key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
724         lookup_key32_cmp(key, bucket2, pos, f);                 \
725                                                                 \
726         pkt_mask = (bucket2->signature[pos] & 1LLU) << pkt2_index;\
727         pkts_mask_out |= pkt_mask;                              \
728                                                                 \
729         a = (void *) &bucket2->data[pos * f->entry_size];       \
730         rte_prefetch0(a);                                       \
731         entries[pkt2_index] = a;                                \
732                                                                 \
733         bucket_mask = (~pkt_mask) & (bucket2->next_valid << pkt2_index);\
734         buckets_mask |= bucket_mask;                            \
735         bucket_next = bucket2->next;                            \
736         buckets[pkt2_index] = bucket_next;                      \
737         keys[pkt2_index] = key;                                 \
738 }
739
740 #define lookup_grinder(pkt_index, buckets, keys, pkts_mask_out, \
741         entries, buckets_mask, f)                               \
742 {                                                               \
743         struct rte_bucket_4_32 *bucket, *bucket_next;           \
744         void *a;                                                \
745         uint64_t pkt_mask, bucket_mask;                         \
746         uint64_t *key;                                          \
747         uint32_t pos;                                           \
748                                                                 \
749         bucket = buckets[pkt_index];                            \
750         key = keys[pkt_index];                                  \
751                                                                 \
752         lookup_key32_cmp(key, bucket, pos, f);                  \
753                                                                 \
754         pkt_mask = (bucket->signature[pos] & 1LLU) << pkt_index;\
755         pkts_mask_out |= pkt_mask;                              \
756                                                                 \
757         a = (void *) &bucket->data[pos * f->entry_size];        \
758         rte_prefetch0(a);                                       \
759         entries[pkt_index] = a;                                 \
760                                                                 \
761         bucket_mask = (~pkt_mask) & (bucket->next_valid << pkt_index);\
762         buckets_mask |= bucket_mask;                            \
763         bucket_next = bucket->next;                             \
764         rte_prefetch0(bucket_next);                             \
765         rte_prefetch0((void *)(((uintptr_t) bucket_next) + RTE_CACHE_LINE_SIZE));\
766         rte_prefetch0((void *)(((uintptr_t) bucket_next) +      \
767                 2 * RTE_CACHE_LINE_SIZE));                              \
768         buckets[pkt_index] = bucket_next;                       \
769         keys[pkt_index] = key;                                  \
770 }
771
772 #define lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01,\
773         pkts, pkts_mask, f)                                     \
774 {                                                               \
775         uint64_t pkt00_mask, pkt01_mask;                        \
776         uint32_t key_offset = f->key_offset;            \
777                                                                 \
778         pkt00_index = __builtin_ctzll(pkts_mask);               \
779         pkt00_mask = 1LLU << pkt00_index;                       \
780         pkts_mask &= ~pkt00_mask;                               \
781                                                                 \
782         mbuf00 = pkts[pkt00_index];                             \
783         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset));\
784                                                                 \
785         pkt01_index = __builtin_ctzll(pkts_mask);               \
786         pkt01_mask = 1LLU << pkt01_index;                       \
787         pkts_mask &= ~pkt01_mask;                               \
788                                                                 \
789         mbuf01 = pkts[pkt01_index];                             \
790         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset));\
791 }
792
793 #define lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,\
794         mbuf00, mbuf01, pkts, pkts_mask, f)                     \
795 {                                                               \
796         uint64_t pkt00_mask, pkt01_mask;                        \
797         uint32_t key_offset = f->key_offset;            \
798                                                                 \
799         pkt00_index = __builtin_ctzll(pkts_mask);               \
800         pkt00_mask = 1LLU << pkt00_index;                       \
801         pkts_mask &= ~pkt00_mask;                               \
802                                                                 \
803         mbuf00 = pkts[pkt00_index];                             \
804         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, key_offset)); \
805                                                                 \
806         pkt01_index = __builtin_ctzll(pkts_mask);               \
807         if (pkts_mask == 0)                                     \
808                 pkt01_index = pkt00_index;                      \
809                                                                 \
810         pkt01_mask = 1LLU << pkt01_index;                       \
811         pkts_mask &= ~pkt01_mask;                               \
812                                                                 \
813         mbuf01 = pkts[pkt01_index];                             \
814         rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, key_offset)); \
815 }
816
817 #define lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f)   \
818 {                                                               \
819         uint64_t *key10, *key11;                                        \
820         uint64_t signature10, signature11;                              \
821         uint32_t bucket10_index, bucket11_index;                        \
822                                                                 \
823         key10 = RTE_MBUF_METADATA_UINT64_PTR(mbuf10, f->key_offset);    \
824         signature10 = f->f_hash(key10, f->key_mask,      KEY_SIZE, f->seed); \
825                                                                 \
826         bucket10_index = signature10 & (f->n_buckets - 1);              \
827         bucket10 = (struct rte_bucket_4_32 *)                   \
828                 &f->memory[bucket10_index * f->bucket_size];    \
829         rte_prefetch0(bucket10);                                        \
830         rte_prefetch0((void *)(((uintptr_t) bucket10) + RTE_CACHE_LINE_SIZE));\
831         rte_prefetch0((void *)(((uintptr_t) bucket10) + 2 * RTE_CACHE_LINE_SIZE));\
832                                                                 \
833         key11 = RTE_MBUF_METADATA_UINT64_PTR(mbuf11, f->key_offset);    \
834         signature11 = f->f_hash(key11, f->key_mask, KEY_SIZE, f->seed);\
835                                                                 \
836         bucket11_index = signature11 & (f->n_buckets - 1);              \
837         bucket11 = (struct rte_bucket_4_32 *)                   \
838                 &f->memory[bucket11_index * f->bucket_size];    \
839         rte_prefetch0(bucket11);                                        \
840         rte_prefetch0((void *)(((uintptr_t) bucket11) + RTE_CACHE_LINE_SIZE));\
841         rte_prefetch0((void *)(((uintptr_t) bucket11) + 2 * RTE_CACHE_LINE_SIZE));\
842 }
843
844 #define lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,\
845         bucket20, bucket21, pkts_mask_out, entries, f)          \
846 {                                                               \
847         void *a20, *a21;                                        \
848         uint64_t pkt20_mask, pkt21_mask;                        \
849         uint64_t *key20, *key21;                                \
850         uint32_t pos20, pos21;                                  \
851                                                                 \
852         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
853         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
854                                                                 \
855         lookup_key32_cmp(key20, bucket20, pos20, f);            \
856         lookup_key32_cmp(key21, bucket21, pos21, f);            \
857                                                                 \
858         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
859         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
860         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
861                                                                 \
862         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
863         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
864         rte_prefetch0(a20);                                     \
865         rte_prefetch0(a21);                                     \
866         entries[pkt20_index] = a20;                             \
867         entries[pkt21_index] = a21;                             \
868         lru_update(bucket20, pos20);                            \
869         lru_update(bucket21, pos21);                            \
870 }
871
872 #define lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21, bucket20, \
873         bucket21, pkts_mask_out, entries, buckets_mask, buckets, keys, f)\
874 {                                                               \
875         struct rte_bucket_4_32 *bucket20_next, *bucket21_next;  \
876         void *a20, *a21;                                        \
877         uint64_t pkt20_mask, pkt21_mask, bucket20_mask, bucket21_mask;\
878         uint64_t *key20, *key21;                                \
879         uint32_t pos20, pos21;                                  \
880                                                                 \
881         key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
882         key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
883                                                                 \
884         lookup_key32_cmp(key20, bucket20, pos20, f);            \
885         lookup_key32_cmp(key21, bucket21, pos21, f);            \
886                                                                 \
887         pkt20_mask = (bucket20->signature[pos20] & 1LLU) << pkt20_index;\
888         pkt21_mask = (bucket21->signature[pos21] & 1LLU) << pkt21_index;\
889         pkts_mask_out |= pkt20_mask | pkt21_mask;               \
890                                                                 \
891         a20 = (void *) &bucket20->data[pos20 * f->entry_size];  \
892         a21 = (void *) &bucket21->data[pos21 * f->entry_size];  \
893         rte_prefetch0(a20);                                     \
894         rte_prefetch0(a21);                                     \
895         entries[pkt20_index] = a20;                             \
896         entries[pkt21_index] = a21;                             \
897                                                                 \
898         bucket20_mask = (~pkt20_mask) & (bucket20->next_valid << pkt20_index);\
899         bucket21_mask = (~pkt21_mask) & (bucket21->next_valid << pkt21_index);\
900         buckets_mask |= bucket20_mask | bucket21_mask;          \
901         bucket20_next = bucket20->next;                         \
902         bucket21_next = bucket21->next;                         \
903         buckets[pkt20_index] = bucket20_next;                   \
904         buckets[pkt21_index] = bucket21_next;                   \
905         keys[pkt20_index] = key20;                              \
906         keys[pkt21_index] = key21;                              \
907 }
908
909 static int
910 rte_table_hash_lookup_key32_lru(
911         void *table,
912         struct rte_mbuf **pkts,
913         uint64_t pkts_mask,
914         uint64_t *lookup_hit_mask,
915         void **entries)
916 {
917         struct rte_table_hash *f = (struct rte_table_hash *) table;
918         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
919         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
920         uint32_t pkt00_index, pkt01_index, pkt10_index;
921         uint32_t pkt11_index, pkt20_index, pkt21_index;
922         uint64_t pkts_mask_out = 0;
923
924         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
925         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
926
927         /* Cannot run the pipeline with less than 5 packets */
928         if (__builtin_popcountll(pkts_mask) < 5) {
929                 for ( ; pkts_mask; ) {
930                         struct rte_bucket_4_32 *bucket;
931                         struct rte_mbuf *mbuf;
932                         uint32_t pkt_index;
933
934                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask, f);
935                         lookup1_stage1(mbuf, bucket, f);
936                         lookup1_stage2_lru(pkt_index, mbuf, bucket,
937                                         pkts_mask_out, entries, f);
938                 }
939
940                 *lookup_hit_mask = pkts_mask_out;
941                 RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
942                 return 0;
943         }
944
945         /*
946          * Pipeline fill
947          *
948          */
949         /* Pipeline stage 0 */
950         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
951                 pkts_mask, f);
952
953         /* Pipeline feed */
954         mbuf10 = mbuf00;
955         mbuf11 = mbuf01;
956         pkt10_index = pkt00_index;
957         pkt11_index = pkt01_index;
958
959         /* Pipeline stage 0 */
960         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
961                 pkts_mask, f);
962
963         /* Pipeline stage 1 */
964         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
965
966         /*
967          * Pipeline run
968          *
969          */
970         for ( ; pkts_mask; ) {
971                 /* Pipeline feed */
972                 bucket20 = bucket10;
973                 bucket21 = bucket11;
974                 mbuf20 = mbuf10;
975                 mbuf21 = mbuf11;
976                 mbuf10 = mbuf00;
977                 mbuf11 = mbuf01;
978                 pkt20_index = pkt10_index;
979                 pkt21_index = pkt11_index;
980                 pkt10_index = pkt00_index;
981                 pkt11_index = pkt01_index;
982
983                 /* Pipeline stage 0 */
984                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
985                         mbuf00, mbuf01, pkts, pkts_mask, f);
986
987                 /* Pipeline stage 1 */
988                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
989
990                 /* Pipeline stage 2 */
991                 lookup2_stage2_lru(pkt20_index, pkt21_index,
992                         mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out,
993                         entries, f);
994         }
995
996         /*
997          * Pipeline flush
998          *
999          */
1000         /* Pipeline feed */
1001         bucket20 = bucket10;
1002         bucket21 = bucket11;
1003         mbuf20 = mbuf10;
1004         mbuf21 = mbuf11;
1005         mbuf10 = mbuf00;
1006         mbuf11 = mbuf01;
1007         pkt20_index = pkt10_index;
1008         pkt21_index = pkt11_index;
1009         pkt10_index = pkt00_index;
1010         pkt11_index = pkt01_index;
1011
1012         /* Pipeline stage 1 */
1013         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1014
1015         /* Pipeline stage 2 */
1016         lookup2_stage2_lru(pkt20_index, pkt21_index,
1017                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
1018
1019         /* Pipeline feed */
1020         bucket20 = bucket10;
1021         bucket21 = bucket11;
1022         mbuf20 = mbuf10;
1023         mbuf21 = mbuf11;
1024         pkt20_index = pkt10_index;
1025         pkt21_index = pkt11_index;
1026
1027         /* Pipeline stage 2 */
1028         lookup2_stage2_lru(pkt20_index, pkt21_index,
1029                 mbuf20, mbuf21, bucket20, bucket21, pkts_mask_out, entries, f);
1030
1031         *lookup_hit_mask = pkts_mask_out;
1032         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1033         return 0;
1034 } /* rte_table_hash_lookup_key32_lru() */
1035
1036 static int
1037 rte_table_hash_lookup_key32_ext(
1038         void *table,
1039         struct rte_mbuf **pkts,
1040         uint64_t pkts_mask,
1041         uint64_t *lookup_hit_mask,
1042         void **entries)
1043 {
1044         struct rte_table_hash *f = (struct rte_table_hash *) table;
1045         struct rte_bucket_4_32 *bucket10, *bucket11, *bucket20, *bucket21;
1046         struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
1047         uint32_t pkt00_index, pkt01_index, pkt10_index;
1048         uint32_t pkt11_index, pkt20_index, pkt21_index;
1049         uint64_t pkts_mask_out = 0, buckets_mask = 0;
1050         struct rte_bucket_4_32 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
1051         uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
1052
1053         __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
1054         RTE_TABLE_HASH_KEY32_STATS_PKTS_IN_ADD(f, n_pkts_in);
1055
1056         /* Cannot run the pipeline with less than 5 packets */
1057         if (__builtin_popcountll(pkts_mask) < 5) {
1058                 for ( ; pkts_mask; ) {
1059                         struct rte_bucket_4_32 *bucket;
1060                         struct rte_mbuf *mbuf;
1061                         uint32_t pkt_index;
1062
1063                         lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask, f);
1064                         lookup1_stage1(mbuf, bucket, f);
1065                         lookup1_stage2_ext(pkt_index, mbuf, bucket,
1066                                 pkts_mask_out, entries, buckets_mask, buckets,
1067                                 keys, f);
1068                 }
1069
1070                 goto grind_next_buckets;
1071         }
1072
1073         /*
1074          * Pipeline fill
1075          *
1076          */
1077         /* Pipeline stage 0 */
1078         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1079                 pkts_mask, f);
1080
1081         /* Pipeline feed */
1082         mbuf10 = mbuf00;
1083         mbuf11 = mbuf01;
1084         pkt10_index = pkt00_index;
1085         pkt11_index = pkt01_index;
1086
1087         /* Pipeline stage 0 */
1088         lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1089                 pkts_mask, f);
1090
1091         /* Pipeline stage 1 */
1092         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1093
1094         /*
1095          * Pipeline run
1096          *
1097          */
1098         for ( ; pkts_mask; ) {
1099                 /* Pipeline feed */
1100                 bucket20 = bucket10;
1101                 bucket21 = bucket11;
1102                 mbuf20 = mbuf10;
1103                 mbuf21 = mbuf11;
1104                 mbuf10 = mbuf00;
1105                 mbuf11 = mbuf01;
1106                 pkt20_index = pkt10_index;
1107                 pkt21_index = pkt11_index;
1108                 pkt10_index = pkt00_index;
1109                 pkt11_index = pkt01_index;
1110
1111                 /* Pipeline stage 0 */
1112                 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1113                         mbuf00, mbuf01, pkts, pkts_mask, f);
1114
1115                 /* Pipeline stage 1 */
1116                 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1117
1118                 /* Pipeline stage 2 */
1119                 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1120                         bucket20, bucket21, pkts_mask_out, entries,
1121                         buckets_mask, buckets, keys, f);
1122         }
1123
1124         /*
1125          * Pipeline flush
1126          *
1127          */
1128         /* Pipeline feed */
1129         bucket20 = bucket10;
1130         bucket21 = bucket11;
1131         mbuf20 = mbuf10;
1132         mbuf21 = mbuf11;
1133         mbuf10 = mbuf00;
1134         mbuf11 = mbuf01;
1135         pkt20_index = pkt10_index;
1136         pkt21_index = pkt11_index;
1137         pkt10_index = pkt00_index;
1138         pkt11_index = pkt01_index;
1139
1140         /* Pipeline stage 1 */
1141         lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1142
1143         /* Pipeline stage 2 */
1144         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1145                 bucket20, bucket21, pkts_mask_out, entries,
1146                 buckets_mask, buckets, keys, f);
1147
1148         /* Pipeline feed */
1149         bucket20 = bucket10;
1150         bucket21 = bucket11;
1151         mbuf20 = mbuf10;
1152         mbuf21 = mbuf11;
1153         pkt20_index = pkt10_index;
1154         pkt21_index = pkt11_index;
1155
1156         /* Pipeline stage 2 */
1157         lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1158                 bucket20, bucket21, pkts_mask_out, entries,
1159                 buckets_mask, buckets, keys, f);
1160
1161 grind_next_buckets:
1162         /* Grind next buckets */
1163         for ( ; buckets_mask; ) {
1164                 uint64_t buckets_mask_next = 0;
1165
1166                 for ( ; buckets_mask; ) {
1167                         uint64_t pkt_mask;
1168                         uint32_t pkt_index;
1169
1170                         pkt_index = __builtin_ctzll(buckets_mask);
1171                         pkt_mask = 1LLU << pkt_index;
1172                         buckets_mask &= ~pkt_mask;
1173
1174                         lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1175                                 entries, buckets_mask_next, f);
1176                 }
1177
1178                 buckets_mask = buckets_mask_next;
1179         }
1180
1181         *lookup_hit_mask = pkts_mask_out;
1182         RTE_TABLE_HASH_KEY32_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1183         return 0;
1184 } /* rte_table_hash_lookup_key32_ext() */
1185
1186 static int
1187 rte_table_hash_key32_stats_read(void *table, struct rte_table_stats *stats, int clear)
1188 {
1189         struct rte_table_hash *t = table;
1190
1191         if (stats != NULL)
1192                 memcpy(stats, &t->stats, sizeof(t->stats));
1193
1194         if (clear)
1195                 memset(&t->stats, 0, sizeof(t->stats));
1196
1197         return 0;
1198 }
1199
1200 struct rte_table_ops rte_table_hash_key32_lru_ops = {
1201         .f_create = rte_table_hash_create_key32_lru,
1202         .f_free = rte_table_hash_free_key32_lru,
1203         .f_add = rte_table_hash_entry_add_key32_lru,
1204         .f_delete = rte_table_hash_entry_delete_key32_lru,
1205         .f_add_bulk = NULL,
1206         .f_delete_bulk = NULL,
1207         .f_lookup = rte_table_hash_lookup_key32_lru,
1208         .f_stats = rte_table_hash_key32_stats_read,
1209 };
1210
1211 struct rte_table_ops rte_table_hash_key32_ext_ops = {
1212         .f_create = rte_table_hash_create_key32_ext,
1213         .f_free = rte_table_hash_free_key32_ext,
1214         .f_add = rte_table_hash_entry_add_key32_ext,
1215         .f_delete = rte_table_hash_entry_delete_key32_ext,
1216         .f_add_bulk = NULL,
1217         .f_delete_bulk = NULL,
1218         .f_lookup = rte_table_hash_lookup_key32_ext,
1219         .f_stats = rte_table_hash_key32_stats_read,
1220 };