4 * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 #include <rte_common.h>
38 #include <rte_memory.h>
39 #include <rte_malloc.h>
42 #include "rte_table_hash.h"
45 #define RTE_TABLE_HASH_KEY_SIZE 8
47 #ifdef RTE_TABLE_STATS_COLLECT
49 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(table, val) \
50 table->stats.n_pkts_in += val
51 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(table, val) \
52 table->stats.n_pkts_lookup_miss += val
56 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(table, val)
57 #define RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(table, val)
61 struct rte_bucket_4_8 {
65 struct rte_bucket_4_8 *next;
74 struct rte_table_hash {
75 struct rte_table_stats stats;
77 /* Input parameters */
79 uint32_t n_entries_per_bucket;
83 uint32_t signature_offset;
85 rte_table_hash_op_hash f_hash;
88 /* Extendible buckets */
89 uint32_t n_buckets_ext;
94 uint8_t memory[0] __rte_cache_aligned;
98 check_params_create_lru(struct rte_table_hash_key8_lru_params *params) {
100 if (params->n_entries == 0) {
101 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
106 if (params->f_hash == NULL) {
107 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
116 rte_table_hash_create_key8_lru(void *params, int socket_id, uint32_t entry_size)
118 struct rte_table_hash_key8_lru_params *p =
119 (struct rte_table_hash_key8_lru_params *) params;
120 struct rte_table_hash *f;
121 uint32_t n_buckets, n_entries_per_bucket, key_size, bucket_size_cl;
122 uint32_t total_size, i;
124 /* Check input parameters */
125 if ((check_params_create_lru(p) != 0) ||
126 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
127 ((sizeof(struct rte_bucket_4_8) % RTE_CACHE_LINE_SIZE) != 0)) {
130 n_entries_per_bucket = 4;
133 /* Memory allocation */
134 n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
135 n_entries_per_bucket);
136 bucket_size_cl = (sizeof(struct rte_bucket_4_8) + n_entries_per_bucket *
137 entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
138 total_size = sizeof(struct rte_table_hash) + n_buckets *
139 bucket_size_cl * RTE_CACHE_LINE_SIZE;
141 f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
144 "%s: Cannot allocate %u bytes for hash table\n",
145 __func__, total_size);
149 "%s: Hash table memory footprint is %u bytes\n",
150 __func__, total_size);
152 /* Memory initialization */
153 f->n_buckets = n_buckets;
154 f->n_entries_per_bucket = n_entries_per_bucket;
155 f->key_size = key_size;
156 f->entry_size = entry_size;
157 f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
158 f->signature_offset = p->signature_offset;
159 f->key_offset = p->key_offset;
160 f->f_hash = p->f_hash;
163 for (i = 0; i < n_buckets; i++) {
164 struct rte_bucket_4_8 *bucket;
166 bucket = (struct rte_bucket_4_8 *) &f->memory[i *
168 bucket->lru_list = 0x0000000100020003LLU;
175 rte_table_hash_free_key8_lru(void *table)
177 struct rte_table_hash *f = (struct rte_table_hash *) table;
179 /* Check input parameters */
181 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
190 rte_table_hash_entry_add_key8_lru(
197 struct rte_table_hash *f = (struct rte_table_hash *) table;
198 struct rte_bucket_4_8 *bucket;
199 uint64_t signature, mask, pos;
200 uint32_t bucket_index, i;
202 signature = f->f_hash(key, f->key_size, f->seed);
203 bucket_index = signature & (f->n_buckets - 1);
204 bucket = (struct rte_bucket_4_8 *)
205 &f->memory[bucket_index * f->bucket_size];
207 /* Key is present in the bucket */
208 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
209 uint64_t bucket_signature = bucket->signature;
210 uint64_t bucket_key = bucket->key[i];
212 if ((bucket_signature & mask) &&
213 (*((uint64_t *) key) == bucket_key)) {
214 uint8_t *bucket_data = &bucket->data[i * f->entry_size];
216 memcpy(bucket_data, entry, f->entry_size);
217 lru_update(bucket, i);
219 *entry_ptr = (void *) bucket_data;
224 /* Key is not present in the bucket */
225 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
226 uint64_t bucket_signature = bucket->signature;
228 if ((bucket_signature & mask) == 0) {
229 uint8_t *bucket_data = &bucket->data[i * f->entry_size];
231 bucket->signature |= mask;
232 bucket->key[i] = *((uint64_t *) key);
233 memcpy(bucket_data, entry, f->entry_size);
234 lru_update(bucket, i);
236 *entry_ptr = (void *) bucket_data;
242 /* Bucket full: replace LRU entry */
243 pos = lru_pos(bucket);
244 bucket->key[pos] = *((uint64_t *) key);
245 memcpy(&bucket->data[pos * f->entry_size], entry, f->entry_size);
246 lru_update(bucket, pos);
248 *entry_ptr = (void *) &bucket->data[pos * f->entry_size];
254 rte_table_hash_entry_delete_key8_lru(
260 struct rte_table_hash *f = (struct rte_table_hash *) table;
261 struct rte_bucket_4_8 *bucket;
262 uint64_t signature, mask;
263 uint32_t bucket_index, i;
265 signature = f->f_hash(key, f->key_size, f->seed);
266 bucket_index = signature & (f->n_buckets - 1);
267 bucket = (struct rte_bucket_4_8 *)
268 &f->memory[bucket_index * f->bucket_size];
270 /* Key is present in the bucket */
271 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
272 uint64_t bucket_signature = bucket->signature;
273 uint64_t bucket_key = bucket->key[i];
275 if ((bucket_signature & mask) &&
276 (*((uint64_t *) key) == bucket_key)) {
277 uint8_t *bucket_data = &bucket->data[i * f->entry_size];
279 bucket->signature &= ~mask;
282 memcpy(entry, bucket_data, f->entry_size);
288 /* Key is not present in the bucket */
294 check_params_create_ext(struct rte_table_hash_key8_ext_params *params) {
296 if (params->n_entries == 0) {
297 RTE_LOG(ERR, TABLE, "%s: n_entries is zero\n", __func__);
302 if (params->n_entries_ext == 0) {
303 RTE_LOG(ERR, TABLE, "%s: n_entries_ext is zero\n", __func__);
308 if (params->f_hash == NULL) {
309 RTE_LOG(ERR, TABLE, "%s: f_hash function pointer is NULL\n",
318 rte_table_hash_create_key8_ext(void *params, int socket_id, uint32_t entry_size)
320 struct rte_table_hash_key8_ext_params *p =
321 (struct rte_table_hash_key8_ext_params *) params;
322 struct rte_table_hash *f;
323 uint32_t n_buckets, n_buckets_ext, n_entries_per_bucket, key_size;
324 uint32_t bucket_size_cl, stack_size_cl, total_size, i;
326 /* Check input parameters */
327 if ((check_params_create_ext(p) != 0) ||
328 ((sizeof(struct rte_table_hash) % RTE_CACHE_LINE_SIZE) != 0) ||
329 ((sizeof(struct rte_bucket_4_8) % RTE_CACHE_LINE_SIZE) != 0))
332 n_entries_per_bucket = 4;
335 /* Memory allocation */
336 n_buckets = rte_align32pow2((p->n_entries + n_entries_per_bucket - 1) /
337 n_entries_per_bucket);
338 n_buckets_ext = (p->n_entries_ext + n_entries_per_bucket - 1) /
339 n_entries_per_bucket;
340 bucket_size_cl = (sizeof(struct rte_bucket_4_8) + n_entries_per_bucket *
341 entry_size + RTE_CACHE_LINE_SIZE - 1) / RTE_CACHE_LINE_SIZE;
342 stack_size_cl = (n_buckets_ext * sizeof(uint32_t) + RTE_CACHE_LINE_SIZE - 1)
343 / RTE_CACHE_LINE_SIZE;
344 total_size = sizeof(struct rte_table_hash) + ((n_buckets +
345 n_buckets_ext) * bucket_size_cl + stack_size_cl) *
348 f = rte_zmalloc_socket("TABLE", total_size, RTE_CACHE_LINE_SIZE, socket_id);
351 "%s: Cannot allocate %u bytes for hash table\n",
352 __func__, total_size);
356 "%s: Hash table memory footprint is %u bytes\n",
357 __func__, total_size);
359 /* Memory initialization */
360 f->n_buckets = n_buckets;
361 f->n_entries_per_bucket = n_entries_per_bucket;
362 f->key_size = key_size;
363 f->entry_size = entry_size;
364 f->bucket_size = bucket_size_cl * RTE_CACHE_LINE_SIZE;
365 f->signature_offset = p->signature_offset;
366 f->key_offset = p->key_offset;
367 f->f_hash = p->f_hash;
370 f->n_buckets_ext = n_buckets_ext;
371 f->stack_pos = n_buckets_ext;
372 f->stack = (uint32_t *)
373 &f->memory[(n_buckets + n_buckets_ext) * f->bucket_size];
375 for (i = 0; i < n_buckets_ext; i++)
382 rte_table_hash_free_key8_ext(void *table)
384 struct rte_table_hash *f = (struct rte_table_hash *) table;
386 /* Check input parameters */
388 RTE_LOG(ERR, TABLE, "%s: table parameter is NULL\n", __func__);
397 rte_table_hash_entry_add_key8_ext(
404 struct rte_table_hash *f = (struct rte_table_hash *) table;
405 struct rte_bucket_4_8 *bucket0, *bucket, *bucket_prev;
407 uint32_t bucket_index, i;
409 signature = f->f_hash(key, f->key_size, f->seed);
410 bucket_index = signature & (f->n_buckets - 1);
411 bucket0 = (struct rte_bucket_4_8 *)
412 &f->memory[bucket_index * f->bucket_size];
414 /* Key is present in the bucket */
415 for (bucket = bucket0; bucket != NULL; bucket = bucket->next) {
418 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
419 uint64_t bucket_signature = bucket->signature;
420 uint64_t bucket_key = bucket->key[i];
422 if ((bucket_signature & mask) &&
423 (*((uint64_t *) key) == bucket_key)) {
424 uint8_t *bucket_data = &bucket->data[i *
427 memcpy(bucket_data, entry, f->entry_size);
429 *entry_ptr = (void *) bucket_data;
435 /* Key is not present in the bucket */
436 for (bucket_prev = NULL, bucket = bucket0;
437 bucket != NULL; bucket_prev = bucket, bucket = bucket->next) {
440 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
441 uint64_t bucket_signature = bucket->signature;
443 if ((bucket_signature & mask) == 0) {
444 uint8_t *bucket_data = &bucket->data[i *
447 bucket->signature |= mask;
448 bucket->key[i] = *((uint64_t *) key);
449 memcpy(bucket_data, entry, f->entry_size);
451 *entry_ptr = (void *) bucket_data;
458 /* Bucket full: extend bucket */
459 if (f->stack_pos > 0) {
460 bucket_index = f->stack[--f->stack_pos];
462 bucket = (struct rte_bucket_4_8 *) &f->memory[(f->n_buckets +
463 bucket_index) * f->bucket_size];
464 bucket_prev->next = bucket;
465 bucket_prev->next_valid = 1;
467 bucket->signature = 1;
468 bucket->key[0] = *((uint64_t *) key);
469 memcpy(&bucket->data[0], entry, f->entry_size);
471 *entry_ptr = (void *) &bucket->data[0];
479 rte_table_hash_entry_delete_key8_ext(
485 struct rte_table_hash *f = (struct rte_table_hash *) table;
486 struct rte_bucket_4_8 *bucket0, *bucket, *bucket_prev;
488 uint32_t bucket_index, i;
490 signature = f->f_hash(key, f->key_size, f->seed);
491 bucket_index = signature & (f->n_buckets - 1);
492 bucket0 = (struct rte_bucket_4_8 *)
493 &f->memory[bucket_index * f->bucket_size];
495 /* Key is present in the bucket */
496 for (bucket_prev = NULL, bucket = bucket0; bucket != NULL;
497 bucket_prev = bucket, bucket = bucket->next) {
500 for (i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
501 uint64_t bucket_signature = bucket->signature;
502 uint64_t bucket_key = bucket->key[i];
504 if ((bucket_signature & mask) &&
505 (*((uint64_t *) key) == bucket_key)) {
506 uint8_t *bucket_data = &bucket->data[i *
509 bucket->signature &= ~mask;
512 memcpy(entry, bucket_data,
515 if ((bucket->signature == 0) &&
516 (bucket_prev != NULL)) {
517 bucket_prev->next = bucket->next;
518 bucket_prev->next_valid =
522 sizeof(struct rte_bucket_4_8));
523 bucket_index = (((uint8_t *)bucket -
524 (uint8_t *)f->memory)/f->bucket_size) - f->n_buckets;
525 f->stack[f->stack_pos++] = bucket_index;
533 /* Key is not present in the bucket */
538 #define lookup_key8_cmp(key_in, bucket, pos) \
540 uint64_t xor[4], signature; \
542 signature = ~bucket->signature; \
544 xor[0] = (key_in[0] ^ bucket->key[0]) | (signature & 1);\
545 xor[1] = (key_in[0] ^ bucket->key[1]) | (signature & 2);\
546 xor[2] = (key_in[0] ^ bucket->key[2]) | (signature & 4);\
547 xor[3] = (key_in[0] ^ bucket->key[3]) | (signature & 8);\
560 #define lookup1_stage0(pkt0_index, mbuf0, pkts, pkts_mask) \
564 pkt0_index = __builtin_ctzll(pkts_mask); \
565 pkt_mask = 1LLU << pkt0_index; \
566 pkts_mask &= ~pkt_mask; \
568 mbuf0 = pkts[pkt0_index]; \
569 rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf0, 0)); \
572 #define lookup1_stage1(mbuf1, bucket1, f) \
574 uint64_t signature; \
575 uint32_t bucket_index; \
577 signature = RTE_MBUF_METADATA_UINT32(mbuf1, f->signature_offset);\
578 bucket_index = signature & (f->n_buckets - 1); \
579 bucket1 = (struct rte_bucket_4_8 *) \
580 &f->memory[bucket_index * f->bucket_size]; \
581 rte_prefetch0(bucket1); \
584 #define lookup1_stage1_dosig(mbuf1, bucket1, f) \
587 uint64_t signature; \
588 uint32_t bucket_index; \
590 key = RTE_MBUF_METADATA_UINT64_PTR(mbuf1, f->key_offset);\
591 signature = f->f_hash(key, RTE_TABLE_HASH_KEY_SIZE, f->seed);\
592 bucket_index = signature & (f->n_buckets - 1); \
593 bucket1 = (struct rte_bucket_4_8 *) \
594 &f->memory[bucket_index * f->bucket_size]; \
595 rte_prefetch0(bucket1); \
598 #define lookup1_stage2_lru(pkt2_index, mbuf2, bucket2, \
599 pkts_mask_out, entries, f) \
606 key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
608 lookup_key8_cmp(key, bucket2, pos); \
610 pkt_mask = ((bucket2->signature >> pos) & 1LLU) << pkt2_index;\
611 pkts_mask_out |= pkt_mask; \
613 a = (void *) &bucket2->data[pos * f->entry_size]; \
615 entries[pkt2_index] = a; \
616 lru_update(bucket2, pos); \
619 #define lookup1_stage2_ext(pkt2_index, mbuf2, bucket2, pkts_mask_out,\
620 entries, buckets_mask, buckets, keys, f) \
622 struct rte_bucket_4_8 *bucket_next; \
624 uint64_t pkt_mask, bucket_mask; \
628 key = RTE_MBUF_METADATA_UINT64_PTR(mbuf2, f->key_offset);\
630 lookup_key8_cmp(key, bucket2, pos); \
632 pkt_mask = ((bucket2->signature >> pos) & 1LLU) << pkt2_index;\
633 pkts_mask_out |= pkt_mask; \
635 a = (void *) &bucket2->data[pos * f->entry_size]; \
637 entries[pkt2_index] = a; \
639 bucket_mask = (~pkt_mask) & (bucket2->next_valid << pkt2_index);\
640 buckets_mask |= bucket_mask; \
641 bucket_next = bucket2->next; \
642 buckets[pkt2_index] = bucket_next; \
643 keys[pkt2_index] = key; \
646 #define lookup_grinder(pkt_index, buckets, keys, pkts_mask_out, entries,\
649 struct rte_bucket_4_8 *bucket, *bucket_next; \
651 uint64_t pkt_mask, bucket_mask; \
655 bucket = buckets[pkt_index]; \
656 key = keys[pkt_index]; \
658 lookup_key8_cmp(key, bucket, pos); \
660 pkt_mask = ((bucket->signature >> pos) & 1LLU) << pkt_index;\
661 pkts_mask_out |= pkt_mask; \
663 a = (void *) &bucket->data[pos * f->entry_size]; \
665 entries[pkt_index] = a; \
667 bucket_mask = (~pkt_mask) & (bucket->next_valid << pkt_index);\
668 buckets_mask |= bucket_mask; \
669 bucket_next = bucket->next; \
670 rte_prefetch0(bucket_next); \
671 buckets[pkt_index] = bucket_next; \
672 keys[pkt_index] = key; \
675 #define lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01,\
678 uint64_t pkt00_mask, pkt01_mask; \
680 pkt00_index = __builtin_ctzll(pkts_mask); \
681 pkt00_mask = 1LLU << pkt00_index; \
682 pkts_mask &= ~pkt00_mask; \
684 mbuf00 = pkts[pkt00_index]; \
685 rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0)); \
687 pkt01_index = __builtin_ctzll(pkts_mask); \
688 pkt01_mask = 1LLU << pkt01_index; \
689 pkts_mask &= ~pkt01_mask; \
691 mbuf01 = pkts[pkt01_index]; \
692 rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0)); \
695 #define lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,\
696 mbuf00, mbuf01, pkts, pkts_mask) \
698 uint64_t pkt00_mask, pkt01_mask; \
700 pkt00_index = __builtin_ctzll(pkts_mask); \
701 pkt00_mask = 1LLU << pkt00_index; \
702 pkts_mask &= ~pkt00_mask; \
704 mbuf00 = pkts[pkt00_index]; \
705 rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf00, 0)); \
707 pkt01_index = __builtin_ctzll(pkts_mask); \
708 if (pkts_mask == 0) \
709 pkt01_index = pkt00_index; \
711 pkt01_mask = 1LLU << pkt01_index; \
712 pkts_mask &= ~pkt01_mask; \
714 mbuf01 = pkts[pkt01_index]; \
715 rte_prefetch0(RTE_MBUF_METADATA_UINT8_PTR(mbuf01, 0)); \
718 #define lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f) \
720 uint64_t signature10, signature11; \
721 uint32_t bucket10_index, bucket11_index; \
723 signature10 = RTE_MBUF_METADATA_UINT32(mbuf10, f->signature_offset);\
724 bucket10_index = signature10 & (f->n_buckets - 1); \
725 bucket10 = (struct rte_bucket_4_8 *) \
726 &f->memory[bucket10_index * f->bucket_size]; \
727 rte_prefetch0(bucket10); \
729 signature11 = RTE_MBUF_METADATA_UINT32(mbuf11, f->signature_offset);\
730 bucket11_index = signature11 & (f->n_buckets - 1); \
731 bucket11 = (struct rte_bucket_4_8 *) \
732 &f->memory[bucket11_index * f->bucket_size]; \
733 rte_prefetch0(bucket11); \
736 #define lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f)\
738 uint64_t *key10, *key11; \
739 uint64_t signature10, signature11; \
740 uint32_t bucket10_index, bucket11_index; \
741 rte_table_hash_op_hash f_hash = f->f_hash; \
742 uint64_t seed = f->seed; \
743 uint32_t key_offset = f->key_offset; \
745 key10 = RTE_MBUF_METADATA_UINT64_PTR(mbuf10, key_offset);\
746 key11 = RTE_MBUF_METADATA_UINT64_PTR(mbuf11, key_offset);\
748 signature10 = f_hash(key10, RTE_TABLE_HASH_KEY_SIZE, seed);\
749 bucket10_index = signature10 & (f->n_buckets - 1); \
750 bucket10 = (struct rte_bucket_4_8 *) \
751 &f->memory[bucket10_index * f->bucket_size]; \
752 rte_prefetch0(bucket10); \
754 signature11 = f_hash(key11, RTE_TABLE_HASH_KEY_SIZE, seed);\
755 bucket11_index = signature11 & (f->n_buckets - 1); \
756 bucket11 = (struct rte_bucket_4_8 *) \
757 &f->memory[bucket11_index * f->bucket_size]; \
758 rte_prefetch0(bucket11); \
761 #define lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,\
762 bucket20, bucket21, pkts_mask_out, entries, f) \
765 uint64_t pkt20_mask, pkt21_mask; \
766 uint64_t *key20, *key21; \
767 uint32_t pos20, pos21; \
769 key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
770 key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
772 lookup_key8_cmp(key20, bucket20, pos20); \
773 lookup_key8_cmp(key21, bucket21, pos21); \
775 pkt20_mask = ((bucket20->signature >> pos20) & 1LLU) << pkt20_index;\
776 pkt21_mask = ((bucket21->signature >> pos21) & 1LLU) << pkt21_index;\
777 pkts_mask_out |= pkt20_mask | pkt21_mask; \
779 a20 = (void *) &bucket20->data[pos20 * f->entry_size]; \
780 a21 = (void *) &bucket21->data[pos21 * f->entry_size]; \
781 rte_prefetch0(a20); \
782 rte_prefetch0(a21); \
783 entries[pkt20_index] = a20; \
784 entries[pkt21_index] = a21; \
785 lru_update(bucket20, pos20); \
786 lru_update(bucket21, pos21); \
789 #define lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21, bucket20, \
790 bucket21, pkts_mask_out, entries, buckets_mask, buckets, keys, f)\
792 struct rte_bucket_4_8 *bucket20_next, *bucket21_next; \
794 uint64_t pkt20_mask, pkt21_mask, bucket20_mask, bucket21_mask;\
795 uint64_t *key20, *key21; \
796 uint32_t pos20, pos21; \
798 key20 = RTE_MBUF_METADATA_UINT64_PTR(mbuf20, f->key_offset);\
799 key21 = RTE_MBUF_METADATA_UINT64_PTR(mbuf21, f->key_offset);\
801 lookup_key8_cmp(key20, bucket20, pos20); \
802 lookup_key8_cmp(key21, bucket21, pos21); \
804 pkt20_mask = ((bucket20->signature >> pos20) & 1LLU) << pkt20_index;\
805 pkt21_mask = ((bucket21->signature >> pos21) & 1LLU) << pkt21_index;\
806 pkts_mask_out |= pkt20_mask | pkt21_mask; \
808 a20 = (void *) &bucket20->data[pos20 * f->entry_size]; \
809 a21 = (void *) &bucket21->data[pos21 * f->entry_size]; \
810 rte_prefetch0(a20); \
811 rte_prefetch0(a21); \
812 entries[pkt20_index] = a20; \
813 entries[pkt21_index] = a21; \
815 bucket20_mask = (~pkt20_mask) & (bucket20->next_valid << pkt20_index);\
816 bucket21_mask = (~pkt21_mask) & (bucket21->next_valid << pkt21_index);\
817 buckets_mask |= bucket20_mask | bucket21_mask; \
818 bucket20_next = bucket20->next; \
819 bucket21_next = bucket21->next; \
820 buckets[pkt20_index] = bucket20_next; \
821 buckets[pkt21_index] = bucket21_next; \
822 keys[pkt20_index] = key20; \
823 keys[pkt21_index] = key21; \
827 rte_table_hash_lookup_key8_lru(
829 struct rte_mbuf **pkts,
831 uint64_t *lookup_hit_mask,
834 struct rte_table_hash *f = (struct rte_table_hash *) table;
835 struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
836 struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
837 uint32_t pkt00_index, pkt01_index, pkt10_index,
838 pkt11_index, pkt20_index, pkt21_index;
839 uint64_t pkts_mask_out = 0;
841 __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
842 RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
844 /* Cannot run the pipeline with less than 5 packets */
845 if (__builtin_popcountll(pkts_mask) < 5) {
846 for ( ; pkts_mask; ) {
847 struct rte_bucket_4_8 *bucket;
848 struct rte_mbuf *mbuf;
851 lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
852 lookup1_stage1(mbuf, bucket, f);
853 lookup1_stage2_lru(pkt_index, mbuf, bucket,
854 pkts_mask_out, entries, f);
857 *lookup_hit_mask = pkts_mask_out;
858 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
866 /* Pipeline stage 0 */
867 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
873 pkt10_index = pkt00_index;
874 pkt11_index = pkt01_index;
876 /* Pipeline stage 0 */
877 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
880 /* Pipeline stage 1 */
881 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
887 for ( ; pkts_mask; ) {
895 pkt20_index = pkt10_index;
896 pkt21_index = pkt11_index;
897 pkt10_index = pkt00_index;
898 pkt11_index = pkt01_index;
900 /* Pipeline stage 0 */
901 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
902 mbuf00, mbuf01, pkts, pkts_mask);
904 /* Pipeline stage 1 */
905 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
907 /* Pipeline stage 2 */
908 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
909 bucket20, bucket21, pkts_mask_out, entries, f);
923 pkt20_index = pkt10_index;
924 pkt21_index = pkt11_index;
925 pkt10_index = pkt00_index;
926 pkt11_index = pkt01_index;
928 /* Pipeline stage 1 */
929 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
931 /* Pipeline stage 2 */
932 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
933 bucket20, bucket21, pkts_mask_out, entries, f);
940 pkt20_index = pkt10_index;
941 pkt21_index = pkt11_index;
943 /* Pipeline stage 2 */
944 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
945 bucket20, bucket21, pkts_mask_out, entries, f);
947 *lookup_hit_mask = pkts_mask_out;
948 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
950 } /* rte_table_hash_lookup_key8_lru() */
953 rte_table_hash_lookup_key8_lru_dosig(
955 struct rte_mbuf **pkts,
957 uint64_t *lookup_hit_mask,
960 struct rte_table_hash *f = (struct rte_table_hash *) table;
961 struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
962 struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
963 uint32_t pkt00_index, pkt01_index, pkt10_index;
964 uint32_t pkt11_index, pkt20_index, pkt21_index;
965 uint64_t pkts_mask_out = 0;
967 __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
968 RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
970 /* Cannot run the pipeline with less than 5 packets */
971 if (__builtin_popcountll(pkts_mask) < 5) {
972 for ( ; pkts_mask; ) {
973 struct rte_bucket_4_8 *bucket;
974 struct rte_mbuf *mbuf;
977 lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
978 lookup1_stage1_dosig(mbuf, bucket, f);
979 lookup1_stage2_lru(pkt_index, mbuf, bucket,
980 pkts_mask_out, entries, f);
983 *lookup_hit_mask = pkts_mask_out;
984 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
992 /* Pipeline stage 0 */
993 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
999 pkt10_index = pkt00_index;
1000 pkt11_index = pkt01_index;
1002 /* Pipeline stage 0 */
1003 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1006 /* Pipeline stage 1 */
1007 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1013 for ( ; pkts_mask; ) {
1015 bucket20 = bucket10;
1016 bucket21 = bucket11;
1021 pkt20_index = pkt10_index;
1022 pkt21_index = pkt11_index;
1023 pkt10_index = pkt00_index;
1024 pkt11_index = pkt01_index;
1026 /* Pipeline stage 0 */
1027 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1028 mbuf00, mbuf01, pkts, pkts_mask);
1030 /* Pipeline stage 1 */
1031 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1033 /* Pipeline stage 2 */
1034 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1035 bucket20, bucket21, pkts_mask_out, entries, f);
1043 bucket20 = bucket10;
1044 bucket21 = bucket11;
1049 pkt20_index = pkt10_index;
1050 pkt21_index = pkt11_index;
1051 pkt10_index = pkt00_index;
1052 pkt11_index = pkt01_index;
1054 /* Pipeline stage 1 */
1055 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1057 /* Pipeline stage 2 */
1058 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1059 bucket20, bucket21, pkts_mask_out, entries, f);
1062 bucket20 = bucket10;
1063 bucket21 = bucket11;
1066 pkt20_index = pkt10_index;
1067 pkt21_index = pkt11_index;
1069 /* Pipeline stage 2 */
1070 lookup2_stage2_lru(pkt20_index, pkt21_index, mbuf20, mbuf21,
1071 bucket20, bucket21, pkts_mask_out, entries, f);
1073 *lookup_hit_mask = pkts_mask_out;
1074 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1076 } /* rte_table_hash_lookup_key8_lru_dosig() */
1079 rte_table_hash_lookup_key8_ext(
1081 struct rte_mbuf **pkts,
1083 uint64_t *lookup_hit_mask,
1086 struct rte_table_hash *f = (struct rte_table_hash *) table;
1087 struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
1088 struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
1089 uint32_t pkt00_index, pkt01_index, pkt10_index;
1090 uint32_t pkt11_index, pkt20_index, pkt21_index;
1091 uint64_t pkts_mask_out = 0, buckets_mask = 0;
1092 struct rte_bucket_4_8 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
1093 uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
1095 __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
1096 RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
1098 /* Cannot run the pipeline with less than 5 packets */
1099 if (__builtin_popcountll(pkts_mask) < 5) {
1100 for ( ; pkts_mask; ) {
1101 struct rte_bucket_4_8 *bucket;
1102 struct rte_mbuf *mbuf;
1105 lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
1106 lookup1_stage1(mbuf, bucket, f);
1107 lookup1_stage2_ext(pkt_index, mbuf, bucket,
1108 pkts_mask_out, entries, buckets_mask, buckets,
1112 goto grind_next_buckets;
1119 /* Pipeline stage 0 */
1120 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1126 pkt10_index = pkt00_index;
1127 pkt11_index = pkt01_index;
1129 /* Pipeline stage 0 */
1130 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1133 /* Pipeline stage 1 */
1134 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1140 for ( ; pkts_mask; ) {
1142 bucket20 = bucket10;
1143 bucket21 = bucket11;
1148 pkt20_index = pkt10_index;
1149 pkt21_index = pkt11_index;
1150 pkt10_index = pkt00_index;
1151 pkt11_index = pkt01_index;
1153 /* Pipeline stage 0 */
1154 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1155 mbuf00, mbuf01, pkts, pkts_mask);
1157 /* Pipeline stage 1 */
1158 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1160 /* Pipeline stage 2 */
1161 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1162 bucket20, bucket21, pkts_mask_out, entries,
1163 buckets_mask, buckets, keys, f);
1171 bucket20 = bucket10;
1172 bucket21 = bucket11;
1177 pkt20_index = pkt10_index;
1178 pkt21_index = pkt11_index;
1179 pkt10_index = pkt00_index;
1180 pkt11_index = pkt01_index;
1182 /* Pipeline stage 1 */
1183 lookup2_stage1(mbuf10, mbuf11, bucket10, bucket11, f);
1185 /* Pipeline stage 2 */
1186 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1187 bucket20, bucket21, pkts_mask_out, entries,
1188 buckets_mask, buckets, keys, f);
1191 bucket20 = bucket10;
1192 bucket21 = bucket11;
1195 pkt20_index = pkt10_index;
1196 pkt21_index = pkt11_index;
1198 /* Pipeline stage 2 */
1199 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1200 bucket20, bucket21, pkts_mask_out, entries,
1201 buckets_mask, buckets, keys, f);
1204 /* Grind next buckets */
1205 for ( ; buckets_mask; ) {
1206 uint64_t buckets_mask_next = 0;
1208 for ( ; buckets_mask; ) {
1212 pkt_index = __builtin_ctzll(buckets_mask);
1213 pkt_mask = 1LLU << pkt_index;
1214 buckets_mask &= ~pkt_mask;
1216 lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1217 entries, buckets_mask_next, f);
1220 buckets_mask = buckets_mask_next;
1223 *lookup_hit_mask = pkts_mask_out;
1224 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1226 } /* rte_table_hash_lookup_key8_ext() */
1229 rte_table_hash_lookup_key8_ext_dosig(
1231 struct rte_mbuf **pkts,
1233 uint64_t *lookup_hit_mask,
1236 struct rte_table_hash *f = (struct rte_table_hash *) table;
1237 struct rte_bucket_4_8 *bucket10, *bucket11, *bucket20, *bucket21;
1238 struct rte_mbuf *mbuf00, *mbuf01, *mbuf10, *mbuf11, *mbuf20, *mbuf21;
1239 uint32_t pkt00_index, pkt01_index, pkt10_index;
1240 uint32_t pkt11_index, pkt20_index, pkt21_index;
1241 uint64_t pkts_mask_out = 0, buckets_mask = 0;
1242 struct rte_bucket_4_8 *buckets[RTE_PORT_IN_BURST_SIZE_MAX];
1243 uint64_t *keys[RTE_PORT_IN_BURST_SIZE_MAX];
1245 __rte_unused uint32_t n_pkts_in = __builtin_popcountll(pkts_mask);
1246 RTE_TABLE_HASH_KEY8_STATS_PKTS_IN_ADD(f, n_pkts_in);
1248 /* Cannot run the pipeline with less than 5 packets */
1249 if (__builtin_popcountll(pkts_mask) < 5) {
1250 for ( ; pkts_mask; ) {
1251 struct rte_bucket_4_8 *bucket;
1252 struct rte_mbuf *mbuf;
1255 lookup1_stage0(pkt_index, mbuf, pkts, pkts_mask);
1256 lookup1_stage1_dosig(mbuf, bucket, f);
1257 lookup1_stage2_ext(pkt_index, mbuf, bucket,
1258 pkts_mask_out, entries, buckets_mask,
1262 goto grind_next_buckets;
1269 /* Pipeline stage 0 */
1270 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1276 pkt10_index = pkt00_index;
1277 pkt11_index = pkt01_index;
1279 /* Pipeline stage 0 */
1280 lookup2_stage0(pkt00_index, pkt01_index, mbuf00, mbuf01, pkts,
1283 /* Pipeline stage 1 */
1284 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1290 for ( ; pkts_mask; ) {
1292 bucket20 = bucket10;
1293 bucket21 = bucket11;
1298 pkt20_index = pkt10_index;
1299 pkt21_index = pkt11_index;
1300 pkt10_index = pkt00_index;
1301 pkt11_index = pkt01_index;
1303 /* Pipeline stage 0 */
1304 lookup2_stage0_with_odd_support(pkt00_index, pkt01_index,
1305 mbuf00, mbuf01, pkts, pkts_mask);
1307 /* Pipeline stage 1 */
1308 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1310 /* Pipeline stage 2 */
1311 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1312 bucket20, bucket21, pkts_mask_out, entries,
1313 buckets_mask, buckets, keys, f);
1321 bucket20 = bucket10;
1322 bucket21 = bucket11;
1327 pkt20_index = pkt10_index;
1328 pkt21_index = pkt11_index;
1329 pkt10_index = pkt00_index;
1330 pkt11_index = pkt01_index;
1332 /* Pipeline stage 1 */
1333 lookup2_stage1_dosig(mbuf10, mbuf11, bucket10, bucket11, f);
1335 /* Pipeline stage 2 */
1336 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1337 bucket20, bucket21, pkts_mask_out, entries,
1338 buckets_mask, buckets, keys, f);
1341 bucket20 = bucket10;
1342 bucket21 = bucket11;
1345 pkt20_index = pkt10_index;
1346 pkt21_index = pkt11_index;
1348 /* Pipeline stage 2 */
1349 lookup2_stage2_ext(pkt20_index, pkt21_index, mbuf20, mbuf21,
1350 bucket20, bucket21, pkts_mask_out, entries,
1351 buckets_mask, buckets, keys, f);
1354 /* Grind next buckets */
1355 for ( ; buckets_mask; ) {
1356 uint64_t buckets_mask_next = 0;
1358 for ( ; buckets_mask; ) {
1362 pkt_index = __builtin_ctzll(buckets_mask);
1363 pkt_mask = 1LLU << pkt_index;
1364 buckets_mask &= ~pkt_mask;
1366 lookup_grinder(pkt_index, buckets, keys, pkts_mask_out,
1367 entries, buckets_mask_next, f);
1370 buckets_mask = buckets_mask_next;
1373 *lookup_hit_mask = pkts_mask_out;
1374 RTE_TABLE_HASH_KEY8_STATS_PKTS_LOOKUP_MISS(f, n_pkts_in - __builtin_popcountll(pkts_mask_out));
1376 } /* rte_table_hash_lookup_key8_dosig_ext() */
1379 rte_table_hash_key8_stats_read(void *table, struct rte_table_stats *stats, int clear)
1381 struct rte_table_hash *t = (struct rte_table_hash *) table;
1384 memcpy(stats, &t->stats, sizeof(t->stats));
1387 memset(&t->stats, 0, sizeof(t->stats));
1392 struct rte_table_ops rte_table_hash_key8_lru_ops = {
1393 .f_create = rte_table_hash_create_key8_lru,
1394 .f_free = rte_table_hash_free_key8_lru,
1395 .f_add = rte_table_hash_entry_add_key8_lru,
1396 .f_delete = rte_table_hash_entry_delete_key8_lru,
1397 .f_lookup = rte_table_hash_lookup_key8_lru,
1398 .f_stats = rte_table_hash_key8_stats_read,
1401 struct rte_table_ops rte_table_hash_key8_lru_dosig_ops = {
1402 .f_create = rte_table_hash_create_key8_lru,
1403 .f_free = rte_table_hash_free_key8_lru,
1404 .f_add = rte_table_hash_entry_add_key8_lru,
1405 .f_delete = rte_table_hash_entry_delete_key8_lru,
1406 .f_lookup = rte_table_hash_lookup_key8_lru_dosig,
1407 .f_stats = rte_table_hash_key8_stats_read,
1410 struct rte_table_ops rte_table_hash_key8_ext_ops = {
1411 .f_create = rte_table_hash_create_key8_ext,
1412 .f_free = rte_table_hash_free_key8_ext,
1413 .f_add = rte_table_hash_entry_add_key8_ext,
1414 .f_delete = rte_table_hash_entry_delete_key8_ext,
1415 .f_lookup = rte_table_hash_lookup_key8_ext,
1416 .f_stats = rte_table_hash_key8_stats_read,
1419 struct rte_table_ops rte_table_hash_key8_ext_dosig_ops = {
1420 .f_create = rte_table_hash_create_key8_ext,
1421 .f_free = rte_table_hash_free_key8_ext,
1422 .f_add = rte_table_hash_entry_add_key8_ext,
1423 .f_delete = rte_table_hash_entry_delete_key8_ext,
1424 .f_lookup = rte_table_hash_lookup_key8_ext_dosig,
1425 .f_stats = rte_table_hash_key8_stats_read,