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