1
2
3
4#include <stdio.h>
5#include <string.h>
6#include <stdint.h>
7#include <inttypes.h>
8#include <errno.h>
9#include <stdarg.h>
10#include <sys/queue.h>
11
12#include <rte_string_fns.h>
13#include <rte_log.h>
14#include <rte_eal_memconfig.h>
15#include <rte_errno.h>
16#include <rte_malloc.h>
17#include <rte_prefetch.h>
18#include <rte_branch_prediction.h>
19#include <rte_memcpy.h>
20#include <rte_ring.h>
21#include <rte_jhash.h>
22#include <rte_hash_crc.h>
23#include <rte_tailq.h>
24#include <rte_vect.h>
25
26#include "rte_efd.h"
27#if defined(RTE_ARCH_X86)
28#include "rte_efd_x86.h"
29#elif defined(RTE_ARCH_ARM64)
30#include "rte_efd_arm64.h"
31#endif
32
33#define EFD_KEY(key_idx, table) (table->keys + ((key_idx) * table->key_len))
34
35#define EFD_HASH(key, table) \
36 (uint32_t)(rte_jhash(key, table->key_len, 0xbc9f1d34))
37
38#define EFD_HASHFUNCA(key, table) \
39 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d35))
40
41#define EFD_HASHFUNCB(key, table) \
42 (uint32_t)(rte_hash_crc(key, table->key_len, 0xbc9f1d36))
43
44
45
46
47
48
49#define EFD_CHUNK_NUM_GROUPS (64)
50#define EFD_CHUNK_NUM_BINS (256)
51#define EFD_CHUNK_NUM_BIN_TO_GROUP_SETS \
52 (EFD_CHUNK_NUM_BINS / EFD_CHUNK_NUM_GROUPS)
53
54
55
56
57
58#define EFD_TARGET_CHUNK_NUM_RULES \
59 (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)
60
61
62
63
64#define EFD_TARGET_CHUNK_MAX_NUM_RULES \
65 (EFD_CHUNK_NUM_GROUPS * EFD_MAX_GROUP_NUM_RULES)
66
67
68#define EFD_MAX_GROUP_NUM_BINS (16)
69
70
71
72
73
74
75#define EFD_NUM_CHUNK_PADDING_BYTES (256)
76
77
78enum efd_lookup_internal_function {
79 EFD_LOOKUP_SCALAR = 0,
80 EFD_LOOKUP_AVX2,
81 EFD_LOOKUP_NEON,
82 EFD_LOOKUP_NUM
83};
84
85TAILQ_HEAD(rte_efd_list, rte_tailq_entry);
86
87static struct rte_tailq_elem rte_efd_tailq = {
88 .name = "RTE_EFD",
89};
90EAL_REGISTER_TAILQ(rte_efd_tailq);
91
92
93const uint32_t efd_bin_to_group[EFD_CHUNK_NUM_BIN_TO_GROUP_SETS][EFD_CHUNK_NUM_BINS] = {
94 {
95 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
96 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
97 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
98 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
99 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
100 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
101 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
102 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
103 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
104 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
105 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
106 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
107 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
108 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
109 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
110 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63
111 },
112 {
113 34, 33, 48, 59, 0, 21, 36, 18, 9, 49, 54, 38, 51, 23, 31, 5,
114 44, 23, 37, 52, 11, 4, 58, 20, 38, 40, 38, 22, 26, 28, 42, 6,
115 46, 16, 31, 28, 46, 14, 60, 0, 35, 53, 16, 58, 16, 29, 39, 7,
116 1, 54, 15, 11, 48, 3, 62, 9, 58, 5, 30, 43, 17, 7, 36, 34,
117 6, 36, 2, 14, 10, 1, 47, 47, 20, 45, 62, 56, 34, 25, 39, 18,
118 51, 41, 61, 25, 56, 40, 41, 37, 52, 35, 30, 57, 11, 42, 37, 27,
119 54, 19, 26, 13, 48, 31, 46, 15, 12, 10, 16, 20, 43, 17, 12, 55,
120 45, 18, 8, 41, 7, 31, 42, 63, 12, 14, 21, 57, 24, 40, 5, 41,
121 13, 44, 23, 59, 25, 57, 52, 50, 62, 1, 2, 49, 32, 57, 26, 43,
122 56, 60, 55, 5, 49, 6, 3, 50, 46, 39, 27, 33, 17, 4, 53, 13,
123 2, 19, 36, 51, 63, 0, 22, 33, 59, 28, 29, 23, 45, 33, 53, 27,
124 22, 21, 40, 56, 4, 18, 44, 47, 28, 17, 4, 50, 21, 62, 8, 39,
125 0, 8, 15, 24, 29, 24, 9, 11, 48, 61, 35, 55, 43, 1, 54, 42,
126 53, 60, 22, 3, 32, 52, 25, 8, 15, 60, 7, 55, 27, 63, 19, 10,
127 63, 24, 61, 19, 12, 38, 6, 29, 13, 37, 10, 3, 45, 32, 32, 30,
128 49, 61, 44, 14, 20, 58, 35, 30, 2, 26, 34, 51, 9, 59, 47, 50
129 },
130 {
131 32, 35, 32, 34, 55, 5, 6, 23, 49, 11, 6, 23, 52, 37, 29, 54,
132 55, 40, 63, 50, 29, 52, 61, 25, 12, 56, 39, 38, 29, 11, 46, 1,
133 40, 11, 19, 56, 7, 28, 51, 16, 15, 48, 21, 51, 60, 31, 14, 22,
134 41, 47, 59, 56, 53, 28, 58, 26, 43, 27, 41, 33, 24, 52, 44, 38,
135 13, 59, 48, 51, 60, 15, 3, 30, 15, 0, 10, 62, 44, 14, 28, 51,
136 38, 2, 41, 26, 25, 49, 10, 12, 55, 57, 27, 35, 19, 33, 0, 30,
137 5, 36, 47, 53, 5, 53, 20, 43, 34, 37, 52, 41, 21, 63, 59, 9,
138 24, 1, 45, 24, 39, 44, 45, 16, 9, 17, 7, 50, 57, 22, 18, 28,
139 25, 45, 2, 40, 58, 15, 17, 3, 1, 27, 61, 39, 19, 0, 19, 21,
140 57, 62, 54, 60, 54, 40, 48, 33, 36, 37, 4, 42, 1, 43, 58, 8,
141 13, 42, 10, 56, 35, 22, 48, 61, 63, 10, 49, 9, 24, 9, 25, 57,
142 33, 18, 13, 31, 42, 36, 36, 55, 30, 37, 53, 34, 59, 4, 4, 23,
143 8, 16, 58, 14, 30, 11, 12, 63, 49, 62, 2, 39, 47, 22, 2, 60,
144 18, 8, 46, 31, 6, 20, 32, 29, 46, 42, 20, 31, 32, 61, 34, 4,
145 47, 26, 20, 43, 26, 21, 7, 3, 16, 35, 18, 44, 27, 62, 13, 23,
146 6, 50, 12, 8, 45, 17, 3, 46, 50, 7, 14, 5, 17, 54, 38, 0
147 },
148 {
149 29, 56, 5, 7, 54, 48, 23, 37, 35, 44, 52, 40, 33, 49, 60, 0,
150 59, 51, 28, 12, 41, 26, 2, 23, 34, 5, 59, 40, 3, 19, 6, 26,
151 35, 53, 45, 49, 29, 57, 28, 62, 58, 59, 19, 53, 59, 62, 6, 54,
152 13, 15, 48, 50, 45, 21, 41, 12, 34, 40, 24, 56, 19, 21, 35, 18,
153 55, 45, 9, 61, 47, 61, 19, 15, 16, 39, 17, 31, 3, 51, 21, 50,
154 17, 25, 25, 11, 44, 16, 18, 28, 14, 2, 37, 61, 58, 27, 62, 4,
155 14, 17, 1, 9, 46, 28, 37, 0, 53, 43, 57, 7, 57, 46, 21, 41,
156 39, 14, 52, 60, 44, 53, 49, 60, 49, 63, 13, 11, 29, 1, 55, 47,
157 55, 12, 60, 43, 54, 37, 13, 6, 42, 10, 36, 13, 9, 8, 34, 51,
158 31, 32, 12, 7, 57, 2, 26, 14, 3, 30, 63, 3, 32, 1, 5, 11,
159 27, 24, 26, 44, 31, 23, 56, 38, 62, 0, 40, 30, 6, 23, 38, 2,
160 47, 5, 15, 27, 16, 10, 31, 25, 22, 63, 30, 25, 20, 33, 32, 50,
161 29, 43, 55, 10, 50, 45, 56, 20, 4, 7, 27, 46, 11, 16, 22, 52,
162 35, 20, 41, 54, 46, 33, 42, 18, 63, 8, 22, 58, 36, 4, 51, 42,
163 38, 32, 38, 22, 17, 0, 47, 8, 48, 8, 48, 1, 61, 36, 33, 20,
164 24, 39, 39, 18, 30, 36, 9, 43, 42, 24, 10, 58, 4, 15, 34, 52
165 },
166};
167
168
169
170
171
172
173
174
175struct efd_offline_group_rules {
176 uint32_t num_rules;
177
178
179 uint32_t key_idx[EFD_MAX_GROUP_NUM_RULES];
180
181 efd_value_t value[EFD_MAX_GROUP_NUM_RULES];
182
183
184 uint8_t bin_id[EFD_MAX_GROUP_NUM_RULES];
185
186
187
188};
189
190
191
192
193struct efd_offline_chunk_rules {
194 uint16_t num_rules;
195
196
197
198
199 struct efd_offline_group_rules group_rules[EFD_CHUNK_NUM_GROUPS];
200
201};
202
203
204
205
206
207
208struct efd_online_group_entry {
209 efd_hashfunc_t hash_idx[RTE_EFD_VALUE_NUM_BITS];
210 efd_lookuptbl_t lookup_table[RTE_EFD_VALUE_NUM_BITS];
211} __rte_packed;
212
213
214
215
216
217struct efd_online_chunk {
218 uint8_t bin_choice_list[(EFD_CHUNK_NUM_BINS * 2 + 7) / 8];
219
220
221
222
223
224
225 struct efd_online_group_entry groups[EFD_CHUNK_NUM_GROUPS];
226
227} __rte_packed;
228
229
230
231
232struct rte_efd_table {
233 char name[RTE_EFD_NAMESIZE];
234
235 uint32_t key_len;
236
237 uint32_t max_num_rules;
238
239
240 uint32_t num_rules;
241
242
243 uint32_t num_chunks;
244
245
246 uint32_t num_chunks_shift;
247
248
249 enum efd_lookup_internal_function lookup_fn;
250
251
252 struct efd_online_chunk *chunks[RTE_MAX_NUMA_NODES];
253
254
255 struct efd_offline_chunk_rules *offline_chunks;
256
257
258 struct rte_ring *free_slots;
259
260
261 uint8_t *keys;
262};
263
264
265
266
267
268
269
270
271
272
273
274
275static inline uint32_t
276efd_get_chunk_id(const struct rte_efd_table * const table,
277 const uint32_t hashed_key)
278{
279 return hashed_key & (table->num_chunks - 1);
280}
281
282
283
284
285
286
287
288
289
290
291
292static inline uint32_t
293efd_get_bin_id(const struct rte_efd_table * const table,
294 const uint32_t hashed_key)
295{
296 return (hashed_key >> table->num_chunks_shift) & (EFD_CHUNK_NUM_BINS - 1);
297}
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314static inline uint8_t
315efd_get_choice(const struct rte_efd_table * const table,
316 const unsigned int socket_id, const uint32_t chunk_id,
317 const uint32_t bin_id)
318{
319 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
320
321
322
323
324
325 uint8_t choice_chunk =
326 chunk->bin_choice_list[bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS];
327
328
329
330
331
332 int offset = (bin_id & 0x3) * 2;
333
334
335 return (uint8_t) ((choice_chunk >> offset) & 0x3);
336}
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351static inline void
352efd_compute_ids(const struct rte_efd_table * const table,
353 const void *key, uint32_t * const chunk_id, uint32_t * const bin_id)
354{
355
356 uint32_t h = EFD_HASH(key, table);
357
358
359 *chunk_id = efd_get_chunk_id(table, h);
360
361
362
363
364
365 *bin_id = efd_get_bin_id(table, h);
366}
367
368
369
370
371static inline int
372efd_search_hash(struct rte_efd_table * const table,
373 const struct efd_offline_group_rules * const off_group,
374 struct efd_online_group_entry * const on_group)
375{
376 efd_hashfunc_t hash_idx;
377 efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
378 efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
379
380 uint32_t i, j, rule_id;
381 uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
382 uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
383 uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
384
385
386 rte_prefetch0(off_group->value);
387
388
389
390
391
392 for (i = 0; i < off_group->num_rules; i++) {
393 void *key_stored = EFD_KEY(off_group->key_idx[i], table);
394 hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
395 hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
396 }
397
398 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
399 hash_idx = on_group->hash_idx[i];
400 start_hash_idx[i] = hash_idx;
401 start_lookup_table[i] = on_group->lookup_table[i];
402
403 do {
404 efd_lookuptbl_t lookup_table = 0;
405 efd_lookuptbl_t lookup_table_complement = 0;
406
407 for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
408 hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
409 hash_val_b[rule_id]);
410
411
412
413
414
415
416
417
418
419 for (rule_id = 0; rule_id < off_group->num_rules;
420 rule_id++) {
421
422
423
424
425
426 uint32_t bucket_idx = hash_val[rule_id] >>
427 EFD_LOOKUPTBL_SHIFT;
428
429
430
431
432
433
434 efd_lookuptbl_t expected =
435 (off_group->value[rule_id] >> i) & 0x1;
436
437
438
439
440
441
442 lookup_table |= expected << bucket_idx;
443 lookup_table_complement |= (1 - expected)
444 << bucket_idx;
445
446
447
448
449
450
451
452 if (lookup_table & lookup_table_complement)
453 break;
454 }
455
456
457
458
459
460 if (rule_id == off_group->num_rules) {
461
462
463
464
465 on_group->hash_idx[i] = hash_idx;
466 on_group->lookup_table[i] = lookup_table;
467
468
469
470
471
472 hash_idx = start_hash_idx[i] + 1;
473 break;
474 }
475 hash_idx++;
476
477 } while (hash_idx != start_hash_idx[i]);
478
479
480 if (hash_idx == start_hash_idx[i]) {
481
482
483
484
485 for (j = 0; j < i; j++) {
486 on_group->hash_idx[j] = start_hash_idx[j];
487 on_group->lookup_table[j] = start_lookup_table[j];
488 }
489 return 1;
490 }
491 }
492
493 return 0;
494}
495
496struct rte_efd_table *
497rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len,
498 uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket)
499{
500 struct rte_efd_table *table = NULL;
501 uint8_t *key_array = NULL;
502 uint32_t num_chunks, num_chunks_shift;
503 uint8_t socket_id;
504 struct rte_efd_list *efd_list = NULL;
505 struct rte_tailq_entry *te;
506 uint64_t offline_table_size;
507 char ring_name[RTE_RING_NAMESIZE];
508 struct rte_ring *r = NULL;
509 unsigned int i;
510
511 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
512
513 if (online_cpu_socket_bitmask == 0) {
514 RTE_LOG(ERR, EFD, "At least one CPU socket must be enabled "
515 "in the bitmask\n");
516 return NULL;
517 }
518
519 if (max_num_rules == 0) {
520 RTE_LOG(ERR, EFD, "Max num rules must be higher than 0\n");
521 return NULL;
522 }
523
524
525
526
527
528 if (max_num_rules % EFD_TARGET_CHUNK_NUM_RULES == 0)
529 num_chunks = rte_align32pow2(max_num_rules /
530 EFD_TARGET_CHUNK_NUM_RULES);
531 else
532 num_chunks = rte_align32pow2((max_num_rules /
533 EFD_TARGET_CHUNK_NUM_RULES) + 1);
534
535 num_chunks_shift = rte_bsf32(num_chunks);
536
537 rte_mcfg_tailq_write_lock();
538
539
540
541
542
543 TAILQ_FOREACH(te, efd_list, next)
544 {
545 table = (struct rte_efd_table *) te->data;
546 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
547 break;
548 }
549
550 table = NULL;
551 if (te != NULL) {
552 rte_errno = EEXIST;
553 te = NULL;
554 goto error_unlock_exit;
555 }
556
557 te = rte_zmalloc("EFD_TAILQ_ENTRY", sizeof(*te), 0);
558 if (te == NULL) {
559 RTE_LOG(ERR, EFD, "tailq entry allocation failed\n");
560 goto error_unlock_exit;
561 }
562
563
564 table = rte_zmalloc_socket(NULL,
565 sizeof(struct rte_efd_table),
566 RTE_CACHE_LINE_SIZE,
567 offline_cpu_socket);
568 if (table == NULL) {
569 RTE_LOG(ERR, EFD, "Allocating EFD table management structure"
570 " on socket %u failed\n",
571 offline_cpu_socket);
572 goto error_unlock_exit;
573 }
574
575
576 RTE_LOG(DEBUG, EFD, "Allocated EFD table management structure "
577 "on socket %u\n", offline_cpu_socket);
578
579 table->max_num_rules = num_chunks * EFD_TARGET_CHUNK_MAX_NUM_RULES;
580 table->num_rules = 0;
581 table->num_chunks = num_chunks;
582 table->num_chunks_shift = num_chunks_shift;
583 table->key_len = key_len;
584
585
586 key_array = rte_zmalloc_socket(NULL,
587 table->max_num_rules * table->key_len,
588 RTE_CACHE_LINE_SIZE,
589 offline_cpu_socket);
590 if (key_array == NULL) {
591 RTE_LOG(ERR, EFD, "Allocating key array"
592 " on socket %u failed\n",
593 offline_cpu_socket);
594 goto error_unlock_exit;
595 }
596 table->keys = key_array;
597 strlcpy(table->name, name, sizeof(table->name));
598
599 RTE_LOG(DEBUG, EFD, "Creating an EFD table with %u chunks,"
600 " which potentially supports %u entries\n",
601 num_chunks, table->max_num_rules);
602
603
604 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
605 table->chunks[socket_id] = NULL;
606 table->offline_chunks = NULL;
607
608
609
610
611
612 uint64_t online_table_size = num_chunks * sizeof(struct efd_online_chunk) +
613 EFD_NUM_CHUNK_PADDING_BYTES;
614
615 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++) {
616 if ((online_cpu_socket_bitmask >> socket_id) & 0x01) {
617
618
619
620
621 table->chunks[socket_id] =
622 rte_zmalloc_socket(
623 NULL,
624 online_table_size,
625 RTE_CACHE_LINE_SIZE,
626 socket_id);
627 if (table->chunks[socket_id] == NULL) {
628 RTE_LOG(ERR, EFD,
629 "Allocating EFD online table on "
630 "socket %u failed\n",
631 socket_id);
632 goto error_unlock_exit;
633 }
634 RTE_LOG(DEBUG, EFD,
635 "Allocated EFD online table of size "
636 "%"PRIu64" bytes (%.2f MB) on socket %u\n",
637 online_table_size,
638 (float) online_table_size /
639 (1024.0F * 1024.0F),
640 socket_id);
641 }
642 }
643
644#if defined(RTE_ARCH_X86)
645
646
647
648
649 if (RTE_EFD_VALUE_NUM_BITS > 3
650 && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2)
651 && rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_256)
652 table->lookup_fn = EFD_LOOKUP_AVX2;
653 else
654#endif
655#if defined(RTE_ARCH_ARM64)
656
657
658
659
660 if (RTE_EFD_VALUE_NUM_BITS > 16 &&
661 rte_cpu_get_flag_enabled(RTE_CPUFLAG_NEON) &&
662 rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_128)
663 table->lookup_fn = EFD_LOOKUP_NEON;
664 else
665#endif
666 table->lookup_fn = EFD_LOOKUP_SCALAR;
667
668
669
670
671
672
673 offline_table_size = num_chunks * sizeof(struct efd_offline_chunk_rules);
674 table->offline_chunks =
675 rte_zmalloc_socket(NULL,
676 offline_table_size,
677 RTE_CACHE_LINE_SIZE,
678 offline_cpu_socket);
679 if (table->offline_chunks == NULL) {
680 RTE_LOG(ERR, EFD, "Allocating EFD offline table on socket %u "
681 "failed\n", offline_cpu_socket);
682 goto error_unlock_exit;
683 }
684
685 RTE_LOG(DEBUG, EFD,
686 "Allocated EFD offline table of size %"PRIu64" bytes "
687 " (%.2f MB) on socket %u\n", offline_table_size,
688 (float) offline_table_size / (1024.0F * 1024.0F),
689 offline_cpu_socket);
690
691 te->data = (void *) table;
692 TAILQ_INSERT_TAIL(efd_list, te, next);
693 rte_mcfg_tailq_write_unlock();
694
695 snprintf(ring_name, sizeof(ring_name), "HT_%s", table->name);
696
697 r = rte_ring_create(ring_name, rte_align32pow2(table->max_num_rules),
698 offline_cpu_socket, 0);
699 if (r == NULL) {
700 RTE_LOG(ERR, EFD, "memory allocation failed\n");
701 rte_efd_free(table);
702 return NULL;
703 }
704
705
706 for (i = 0; i < table->max_num_rules; i++)
707 rte_ring_sp_enqueue(r, (void *) ((uintptr_t) i));
708
709 table->free_slots = r;
710 return table;
711
712error_unlock_exit:
713 rte_mcfg_tailq_write_unlock();
714 rte_free(te);
715 rte_efd_free(table);
716
717 return NULL;
718}
719
720struct rte_efd_table *
721rte_efd_find_existing(const char *name)
722{
723 struct rte_efd_table *table = NULL;
724 struct rte_tailq_entry *te;
725 struct rte_efd_list *efd_list;
726
727 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
728
729 rte_mcfg_tailq_read_lock();
730
731 TAILQ_FOREACH(te, efd_list, next)
732 {
733 table = (struct rte_efd_table *) te->data;
734 if (strncmp(name, table->name, RTE_EFD_NAMESIZE) == 0)
735 break;
736 }
737 rte_mcfg_tailq_read_unlock();
738
739 if (te == NULL) {
740 rte_errno = ENOENT;
741 return NULL;
742 }
743 return table;
744}
745
746void
747rte_efd_free(struct rte_efd_table *table)
748{
749 uint8_t socket_id;
750 struct rte_efd_list *efd_list;
751 struct rte_tailq_entry *te, *temp;
752
753 if (table == NULL)
754 return;
755
756 for (socket_id = 0; socket_id < RTE_MAX_NUMA_NODES; socket_id++)
757 rte_free(table->chunks[socket_id]);
758
759 efd_list = RTE_TAILQ_CAST(rte_efd_tailq.head, rte_efd_list);
760 rte_mcfg_tailq_write_lock();
761
762 TAILQ_FOREACH_SAFE(te, efd_list, next, temp) {
763 if (te->data == (void *) table) {
764 TAILQ_REMOVE(efd_list, te, next);
765 rte_free(te);
766 break;
767 }
768 }
769
770 rte_mcfg_tailq_write_unlock();
771 rte_ring_free(table->free_slots);
772 rte_free(table->offline_chunks);
773 rte_free(table->keys);
774 rte_free(table);
775}
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798static inline void
799efd_apply_update(struct rte_efd_table * const table, const unsigned int socket_id,
800 const uint32_t chunk_id, const uint32_t group_id,
801 const uint32_t bin_id, const uint8_t new_bin_choice,
802 const struct efd_online_group_entry * const new_group_entry)
803{
804 int i;
805 struct efd_online_chunk *chunk = &table->chunks[socket_id][chunk_id];
806 uint8_t bin_index = bin_id / EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
807
808
809
810
811
812 uint8_t choice_chunk =
813 chunk->bin_choice_list[bin_index];
814
815
816
817 int offset = (bin_id & 0x3) * 2;
818
819
820 choice_chunk = (choice_chunk & (~(0x03 << offset)))
821 | ((new_bin_choice & 0x03) << offset);
822
823
824 for (i = 0; i < RTE_MAX_NUMA_NODES; i++) {
825 if (table->chunks[i] != NULL) {
826 memcpy(&(table->chunks[i][chunk_id].groups[group_id]),
827 new_group_entry,
828 sizeof(struct efd_online_group_entry));
829 table->chunks[i][chunk_id].bin_choice_list[bin_index] =
830 choice_chunk;
831 }
832 }
833}
834
835
836
837
838static inline void
839move_groups(uint32_t bin_id, uint8_t bin_size,
840 struct efd_offline_group_rules *new_group,
841 struct efd_offline_group_rules * const current_group)
842{
843
844 uint8_t empty_idx = 0;
845 unsigned int i;
846
847 if (new_group == current_group)
848 return;
849
850 for (i = 0; i < current_group->num_rules; i++) {
851
852
853
854
855 if (current_group->bin_id[i] == bin_id) {
856 new_group->key_idx[new_group->num_rules] =
857 current_group->key_idx[i];
858 new_group->value[new_group->num_rules] =
859 current_group->value[i];
860 new_group->bin_id[new_group->num_rules] =
861 current_group->bin_id[i];
862 new_group->num_rules++;
863 } else {
864 if (i != empty_idx) {
865
866
867
868
869 current_group->key_idx[empty_idx] =
870 current_group->key_idx[i];
871 current_group->value[empty_idx] =
872 current_group->value[i];
873 current_group->bin_id[empty_idx] =
874 current_group->bin_id[i];
875 }
876 empty_idx++;
877 }
878
879 }
880 current_group->num_rules -= bin_size;
881}
882
883
884
885
886
887static inline void
888revert_groups(struct efd_offline_group_rules *previous_group,
889 struct efd_offline_group_rules *current_group, uint8_t bin_size)
890{
891 unsigned int i;
892
893 if (current_group == previous_group)
894 return;
895
896
897 for (i = current_group->num_rules - bin_size;
898 i < current_group->num_rules; i++) {
899 previous_group->key_idx[previous_group->num_rules] =
900 current_group->key_idx[i];
901 previous_group->value[previous_group->num_rules] =
902 current_group->value[i];
903 previous_group->bin_id[previous_group->num_rules] =
904 current_group->bin_id[i];
905 previous_group->num_rules++;
906 }
907
908
909
910
911
912 current_group->num_rules -= bin_size;
913}
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959static inline int
960efd_compute_update(struct rte_efd_table * const table,
961 const unsigned int socket_id, const void *key,
962 const efd_value_t value, uint32_t * const chunk_id,
963 uint32_t * const group_id, uint32_t * const bin_id,
964 uint8_t * const new_bin_choice,
965 struct efd_online_group_entry * const entry)
966{
967 unsigned int i;
968 int ret;
969 uint32_t new_idx;
970 void *new_k, *slot_id = NULL;
971 int status = EXIT_SUCCESS;
972 unsigned int found = 0;
973
974 efd_compute_ids(table, key, chunk_id, bin_id);
975
976 struct efd_offline_chunk_rules * const chunk =
977 &table->offline_chunks[*chunk_id];
978 struct efd_offline_group_rules *new_group;
979
980 uint8_t current_choice = efd_get_choice(table, socket_id,
981 *chunk_id, *bin_id);
982 uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
983 struct efd_offline_group_rules * const current_group =
984 &chunk->group_rules[current_group_id];
985 uint8_t bin_size = 0;
986 uint8_t key_changed_index = 0;
987 efd_value_t key_changed_previous_value = 0;
988 uint32_t key_idx_previous = 0;
989
990
991 for (i = 0; i < current_group->num_rules; i++) {
992 if (current_group->bin_id[i] == *bin_id)
993 bin_size++;
994 else
995 continue;
996
997 void *key_stored = EFD_KEY(current_group->key_idx[i], table);
998 if (found == 0 && unlikely(memcmp(key_stored, key,
999 table->key_len) == 0)) {
1000
1001
1002
1003
1004
1005
1006 if (current_group->value[i] == value)
1007 return RTE_EFD_UPDATE_NO_CHANGE;
1008
1009 key_idx_previous = current_group->key_idx[i];
1010 key_changed_previous_value = current_group->value[i];
1011 key_changed_index = i;
1012 current_group->value[i] = value;
1013 found = 1;
1014 }
1015 }
1016
1017 if (found == 0) {
1018
1019 if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
1020 RTE_LOG(ERR, EFD,
1021 "Fatal: No room remaining for insert into "
1022 "chunk %u group %u bin %u\n",
1023 *chunk_id,
1024 current_group_id, *bin_id);
1025 return RTE_EFD_UPDATE_FAILED;
1026 }
1027
1028 if (unlikely(current_group->num_rules ==
1029 (EFD_MAX_GROUP_NUM_RULES - 1))) {
1030 RTE_LOG(INFO, EFD, "Warn: Insert into last "
1031 "available slot in chunk %u "
1032 "group %u bin %u\n", *chunk_id,
1033 current_group_id, *bin_id);
1034 status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
1035 }
1036
1037 if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
1038 return RTE_EFD_UPDATE_FAILED;
1039
1040 new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
1041 table->key_len);
1042 rte_prefetch0(new_k);
1043 new_idx = (uint32_t) ((uintptr_t) slot_id);
1044
1045 rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
1046 current_group->key_idx[current_group->num_rules] = new_idx;
1047 current_group->value[current_group->num_rules] = value;
1048 current_group->bin_id[current_group->num_rules] = *bin_id;
1049 current_group->num_rules++;
1050 table->num_rules++;
1051 bin_size++;
1052 } else {
1053 uint32_t last = current_group->num_rules - 1;
1054
1055 current_group->key_idx[key_changed_index] =
1056 current_group->key_idx[last];
1057 current_group->value[key_changed_index] =
1058 current_group->value[last];
1059 current_group->bin_id[key_changed_index] =
1060 current_group->bin_id[last];
1061
1062
1063
1064
1065
1066 current_group->key_idx[last] = key_idx_previous;
1067 current_group->value[last] = value;
1068 current_group->bin_id[last] = *bin_id;
1069 }
1070
1071 *new_bin_choice = current_choice;
1072 *group_id = current_group_id;
1073 new_group = current_group;
1074
1075
1076 if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
1077
1078
1079
1080
1081
1082 current_group->num_rules -= bin_size;
1083
1084
1085
1086
1087
1088
1089 uint8_t smallest_choice = current_choice;
1090 uint8_t smallest_size = current_group->num_rules;
1091 uint32_t smallest_group_id = current_group_id;
1092 unsigned char choice;
1093
1094 for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
1095 choice++) {
1096 uint32_t test_group_id =
1097 efd_bin_to_group[choice][*bin_id];
1098 uint32_t num_rules =
1099 chunk->group_rules[test_group_id].num_rules;
1100 if (num_rules < smallest_size) {
1101 smallest_choice = choice;
1102 smallest_size = num_rules;
1103 smallest_group_id = test_group_id;
1104 }
1105 }
1106
1107 *new_bin_choice = smallest_choice;
1108 *group_id = smallest_group_id;
1109 new_group = &chunk->group_rules[smallest_group_id];
1110 current_group->num_rules += bin_size;
1111
1112 }
1113
1114 uint8_t choice = 0;
1115 for (;;) {
1116 if (current_group != new_group &&
1117 new_group->num_rules + bin_size >
1118 EFD_MAX_GROUP_NUM_RULES) {
1119 RTE_LOG(DEBUG, EFD,
1120 "Unable to move_groups to dest group "
1121 "containing %u entries."
1122 "bin_size:%u choice:%02x\n",
1123 new_group->num_rules, bin_size,
1124 choice - 1);
1125 goto next_choice;
1126 }
1127 move_groups(*bin_id, bin_size, new_group, current_group);
1128
1129
1130
1131
1132 ret = efd_search_hash(table, new_group, entry);
1133
1134 if (!ret)
1135 return status;
1136
1137 RTE_LOG(DEBUG, EFD,
1138 "Failed to find perfect hash for group "
1139 "containing %u entries. bin_size:%u choice:%02x\n",
1140 new_group->num_rules, bin_size, choice - 1);
1141
1142 revert_groups(current_group, new_group, bin_size);
1143
1144next_choice:
1145 if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
1146 break;
1147 *new_bin_choice = choice;
1148 *group_id = efd_bin_to_group[choice][*bin_id];
1149 new_group = &chunk->group_rules[*group_id];
1150 choice++;
1151 }
1152
1153 if (!found) {
1154 current_group->num_rules--;
1155 table->num_rules--;
1156 } else
1157 current_group->value[current_group->num_rules - 1] =
1158 key_changed_previous_value;
1159 return RTE_EFD_UPDATE_FAILED;
1160}
1161
1162int
1163rte_efd_update(struct rte_efd_table * const table, const unsigned int socket_id,
1164 const void *key, const efd_value_t value)
1165{
1166 uint32_t chunk_id = 0, group_id = 0, bin_id = 0;
1167 uint8_t new_bin_choice = 0;
1168 struct efd_online_group_entry entry;
1169
1170 int status = efd_compute_update(table, socket_id, key, value,
1171 &chunk_id, &group_id, &bin_id,
1172 &new_bin_choice, &entry);
1173
1174 if (status == RTE_EFD_UPDATE_NO_CHANGE)
1175 return EXIT_SUCCESS;
1176
1177 if (status == RTE_EFD_UPDATE_FAILED)
1178 return status;
1179
1180 efd_apply_update(table, socket_id, chunk_id, group_id, bin_id,
1181 new_bin_choice, &entry);
1182 return status;
1183}
1184
1185int
1186rte_efd_delete(struct rte_efd_table * const table, const unsigned int socket_id,
1187 const void *key, efd_value_t * const prev_value)
1188{
1189 unsigned int i;
1190 uint32_t chunk_id, bin_id;
1191 uint8_t not_found = 1;
1192
1193 efd_compute_ids(table, key, &chunk_id, &bin_id);
1194
1195 struct efd_offline_chunk_rules * const chunk =
1196 &table->offline_chunks[chunk_id];
1197
1198 uint8_t current_choice = efd_get_choice(table, socket_id,
1199 chunk_id, bin_id);
1200 uint32_t current_group_id = efd_bin_to_group[current_choice][bin_id];
1201 struct efd_offline_group_rules * const current_group =
1202 &chunk->group_rules[current_group_id];
1203
1204
1205
1206
1207
1208 for (i = 0; i < current_group->num_rules; i++) {
1209 if (not_found) {
1210
1211 if (memcmp(EFD_KEY(current_group->key_idx[i], table),
1212 key, table->key_len) == 0) {
1213
1214 if (prev_value != NULL)
1215 *prev_value = current_group->value[i];
1216
1217 not_found = 0;
1218 rte_ring_sp_enqueue(table->free_slots,
1219 (void *)((uintptr_t)current_group->key_idx[i]));
1220 }
1221 } else {
1222
1223
1224
1225
1226
1227
1228 current_group->key_idx[i - 1] = current_group->key_idx[i];
1229 current_group->value[i - 1] = current_group->value[i];
1230 current_group->bin_id[i - 1] = current_group->bin_id[i];
1231 }
1232 }
1233
1234 if (not_found == 0) {
1235 table->num_rules--;
1236 current_group->num_rules--;
1237 }
1238
1239 return not_found;
1240}
1241
1242static inline efd_value_t
1243efd_lookup_internal_scalar(const efd_hashfunc_t *group_hash_idx,
1244 const efd_lookuptbl_t *group_lookup_table,
1245 const uint32_t hash_val_a, const uint32_t hash_val_b)
1246{
1247 efd_value_t value = 0;
1248 uint32_t i;
1249
1250 for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
1251 value <<= 1;
1252 uint32_t h = hash_val_a + (hash_val_b *
1253 group_hash_idx[RTE_EFD_VALUE_NUM_BITS - i - 1]);
1254 uint16_t bucket_idx = h >> EFD_LOOKUPTBL_SHIFT;
1255 value |= (group_lookup_table[
1256 RTE_EFD_VALUE_NUM_BITS - i - 1] >>
1257 bucket_idx) & 0x1;
1258 }
1259
1260 return value;
1261}
1262
1263
1264static inline efd_value_t
1265efd_lookup_internal(const struct efd_online_group_entry * const group,
1266 const uint32_t hash_val_a, const uint32_t hash_val_b,
1267 enum efd_lookup_internal_function lookup_fn)
1268{
1269 efd_value_t value = 0;
1270
1271 switch (lookup_fn) {
1272
1273#if defined(RTE_ARCH_X86) && defined(CC_SUPPORT_AVX2)
1274 case EFD_LOOKUP_AVX2:
1275 return efd_lookup_internal_avx2(group->hash_idx,
1276 group->lookup_table,
1277 hash_val_a,
1278 hash_val_b);
1279 break;
1280#endif
1281#if defined(RTE_ARCH_ARM64)
1282 case EFD_LOOKUP_NEON:
1283 return efd_lookup_internal_neon(group->hash_idx,
1284 group->lookup_table,
1285 hash_val_a,
1286 hash_val_b);
1287 break;
1288#endif
1289 case EFD_LOOKUP_SCALAR:
1290
1291 default:
1292 return efd_lookup_internal_scalar(group->hash_idx,
1293 group->lookup_table,
1294 hash_val_a,
1295 hash_val_b);
1296 }
1297
1298 return value;
1299}
1300
1301efd_value_t
1302rte_efd_lookup(const struct rte_efd_table * const table,
1303 const unsigned int socket_id, const void *key)
1304{
1305 uint32_t chunk_id, group_id, bin_id;
1306 uint8_t bin_choice;
1307 const struct efd_online_group_entry *group;
1308 const struct efd_online_chunk * const chunks = table->chunks[socket_id];
1309
1310
1311 efd_compute_ids(table, key, &chunk_id, &bin_id);
1312 bin_choice = efd_get_choice(table, socket_id, chunk_id, bin_id);
1313 group_id = efd_bin_to_group[bin_choice][bin_id];
1314 group = &chunks[chunk_id].groups[group_id];
1315
1316 return efd_lookup_internal(group,
1317 EFD_HASHFUNCA(key, table),
1318 EFD_HASHFUNCB(key, table),
1319 table->lookup_fn);
1320}
1321
1322void rte_efd_lookup_bulk(const struct rte_efd_table * const table,
1323 const unsigned int socket_id, const int num_keys,
1324 const void **key_list, efd_value_t * const value_list)
1325{
1326 int i;
1327 uint32_t chunk_id_list[RTE_EFD_BURST_MAX];
1328 uint32_t bin_id_list[RTE_EFD_BURST_MAX];
1329 uint8_t bin_choice_list[RTE_EFD_BURST_MAX];
1330 uint32_t group_id_list[RTE_EFD_BURST_MAX];
1331 struct efd_online_group_entry *group;
1332
1333 struct efd_online_chunk *chunks = table->chunks[socket_id];
1334
1335 for (i = 0; i < num_keys; i++) {
1336 efd_compute_ids(table, key_list[i], &chunk_id_list[i],
1337 &bin_id_list[i]);
1338 rte_prefetch0(&chunks[chunk_id_list[i]].bin_choice_list);
1339 }
1340
1341 for (i = 0; i < num_keys; i++) {
1342 bin_choice_list[i] = efd_get_choice(table, socket_id,
1343 chunk_id_list[i], bin_id_list[i]);
1344 group_id_list[i] =
1345 efd_bin_to_group[bin_choice_list[i]][bin_id_list[i]];
1346 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1347 rte_prefetch0(group);
1348 }
1349
1350 for (i = 0; i < num_keys; i++) {
1351 group = &chunks[chunk_id_list[i]].groups[group_id_list[i]];
1352 value_list[i] = efd_lookup_internal(group,
1353 EFD_HASHFUNCA(key_list[i], table),
1354 EFD_HASHFUNCB(key_list[i], table),
1355 table->lookup_fn);
1356 }
1357}
1358