1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2020 Intel Corporation
3 */
4 #include <string.h>
5 #include <stdio.h>
6 #include <errno.h>
7
8 #include <rte_common.h>
9 #include <rte_prefetch.h>
10
11 #include "rte_swx_table_em.h"
12
13 #define CHECK(condition, err_code) \
14 do { \
15 if (!(condition)) \
16 return -(err_code); \
17 } while (0)
18
19 #ifndef RTE_SWX_TABLE_EM_USE_HUGE_PAGES
20 #define RTE_SWX_TABLE_EM_USE_HUGE_PAGES 1
21 #endif
22
23 #if RTE_SWX_TABLE_EM_USE_HUGE_PAGES
24
25 #include <rte_malloc.h>
26
27 static void *
env_malloc(size_t size,size_t alignment,int numa_node)28 env_malloc(size_t size, size_t alignment, int numa_node)
29 {
30 return rte_zmalloc_socket(NULL, size, alignment, numa_node);
31 }
32
33 static void
env_free(void * start,size_t size __rte_unused)34 env_free(void *start, size_t size __rte_unused)
35 {
36 rte_free(start);
37 }
38
39 #else
40
41 #include <numa.h>
42
43 static void *
env_malloc(size_t size,size_t alignment __rte_unused,int numa_node)44 env_malloc(size_t size, size_t alignment __rte_unused, int numa_node)
45 {
46 return numa_alloc_onnode(size, numa_node);
47 }
48
49 static void
env_free(void * start,size_t size)50 env_free(void *start, size_t size)
51 {
52 numa_free(start, size);
53 }
54
55 #endif
56
57 #if defined(RTE_ARCH_X86_64)
58
59 #include <x86intrin.h>
60
61 #define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
62
63 #else
64
65 static inline uint64_t
crc32_u64_generic(uint64_t crc,uint64_t value)66 crc32_u64_generic(uint64_t crc, uint64_t value)
67 {
68 int i;
69
70 crc = (crc & 0xFFFFFFFFLLU) ^ value;
71 for (i = 63; i >= 0; i--) {
72 uint64_t mask;
73
74 mask = -(crc & 1LLU);
75 crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
76 }
77
78 return crc;
79 }
80
81 #define crc32_u64(crc, v) crc32_u64_generic(crc, v)
82
83 #endif
84
85 /* Key size needs to be one of: 8, 16, 32 or 64. */
86 static inline uint32_t
hash(void * key,void * key_mask,uint32_t key_size,uint32_t seed)87 hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
88 {
89 uint64_t *k = key;
90 uint64_t *m = key_mask;
91 uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
92
93 switch (key_size) {
94 case 8:
95 crc0 = crc32_u64(seed, k[0] & m[0]);
96 return crc0;
97
98 case 16:
99 k0 = k[0] & m[0];
100
101 crc0 = crc32_u64(k0, seed);
102 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
103
104 crc0 ^= crc1;
105
106 return crc0;
107
108 case 32:
109 k0 = k[0] & m[0];
110 k2 = k[2] & m[2];
111
112 crc0 = crc32_u64(k0, seed);
113 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
114
115 crc2 = crc32_u64(k2, k[3] & m[3]);
116 crc3 = k2 >> 32;
117
118 crc0 = crc32_u64(crc0, crc1);
119 crc1 = crc32_u64(crc2, crc3);
120
121 crc0 ^= crc1;
122
123 return crc0;
124
125 case 64:
126 k0 = k[0] & m[0];
127 k2 = k[2] & m[2];
128 k5 = k[5] & m[5];
129
130 crc0 = crc32_u64(k0, seed);
131 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
132
133 crc2 = crc32_u64(k2, k[3] & m[3]);
134 crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
135
136 crc4 = crc32_u64(k5, k[6] & m[6]);
137 crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
138
139 crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
140 crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
141
142 crc0 ^= crc1;
143
144 return crc0;
145
146 default:
147 crc0 = 0;
148 return crc0;
149 }
150 }
151
152 /* n_bytes needs to be a multiple of 8 bytes. */
153 static void
keycpy(void * dst,void * src,void * src_mask,uint32_t n_bytes)154 keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
155 {
156 uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
157 uint32_t i;
158
159 for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
160 dst64[i] = src64[i] & src_mask64[i];
161 }
162
163 /*
164 * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
165 */
166 static inline uint32_t
keycmp(void * a,void * b,void * b_mask,uint32_t n_bytes)167 keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
168 {
169 uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
170
171 switch (n_bytes) {
172 case 8: {
173 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
174 uint32_t result = 1;
175
176 if (xor0)
177 result = 0;
178 return result;
179 }
180
181 case 16: {
182 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
183 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
184 uint64_t or = xor0 | xor1;
185 uint32_t result = 1;
186
187 if (or)
188 result = 0;
189 return result;
190 }
191
192 case 32: {
193 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
194 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
195 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
196 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
197 uint64_t or = (xor0 | xor1) | (xor2 | xor3);
198 uint32_t result = 1;
199
200 if (or)
201 result = 0;
202 return result;
203 }
204
205 case 64: {
206 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
207 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
208 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
209 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
210 uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
211 uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
212 uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
213 uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
214 uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
215 ((xor4 | xor5) | (xor6 | xor7));
216 uint32_t result = 1;
217
218 if (or)
219 result = 0;
220 return result;
221 }
222
223 default: {
224 uint32_t i;
225
226 for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
227 if (a64[i] != (b64[i] & b_mask64[i]))
228 return 0;
229 return 1;
230 }
231 }
232 }
233
234 #define KEYS_PER_BUCKET 4
235
236 struct bucket_extension {
237 struct bucket_extension *next;
238 uint16_t sig[KEYS_PER_BUCKET];
239 uint32_t key_id[KEYS_PER_BUCKET];
240 };
241
242 struct table {
243 /* Input parameters */
244 struct rte_swx_table_params params;
245
246 /* Internal. */
247 uint32_t key_size;
248 uint32_t data_size;
249 uint32_t key_size_shl;
250 uint32_t data_size_shl;
251 uint32_t n_buckets;
252 uint32_t n_buckets_ext;
253 uint32_t key_stack_tos;
254 uint32_t bkt_ext_stack_tos;
255 uint64_t total_size;
256
257 /* Memory arrays. */
258 uint8_t *key_mask;
259 struct bucket_extension *buckets;
260 struct bucket_extension *buckets_ext;
261 uint8_t *keys;
262 uint32_t *key_stack;
263 uint32_t *bkt_ext_stack;
264 uint8_t *data;
265 };
266
267 static inline uint8_t *
table_key(struct table * t,uint32_t key_id)268 table_key(struct table *t, uint32_t key_id)
269 {
270 return &t->keys[(uint64_t)key_id << t->key_size_shl];
271 }
272
273 static inline uint64_t *
table_key_data(struct table * t,uint32_t key_id)274 table_key_data(struct table *t, uint32_t key_id)
275 {
276 return (uint64_t *)&t->data[(uint64_t)key_id << t->data_size_shl];
277 }
278
279 static inline int
bkt_is_empty(struct bucket_extension * bkt)280 bkt_is_empty(struct bucket_extension *bkt)
281 {
282 return (!bkt->sig[0] && !bkt->sig[1] && !bkt->sig[2] && !bkt->sig[3]) ?
283 1 : 0;
284 }
285
286 /* Return:
287 * 0 = Bucket key position is NOT empty;
288 * 1 = Bucket key position is empty.
289 */
290 static inline int
bkt_key_is_empty(struct bucket_extension * bkt,uint32_t bkt_pos)291 bkt_key_is_empty(struct bucket_extension *bkt, uint32_t bkt_pos)
292 {
293 return bkt->sig[bkt_pos] ? 0 : 1;
294 }
295
296 /* Return: 0 = Keys are NOT equal; 1 = Keys are equal. */
297 static inline int
bkt_keycmp(struct table * t,struct bucket_extension * bkt,uint8_t * input_key,uint32_t bkt_pos,uint32_t input_sig)298 bkt_keycmp(struct table *t,
299 struct bucket_extension *bkt,
300 uint8_t *input_key,
301 uint32_t bkt_pos,
302 uint32_t input_sig)
303 {
304 uint32_t bkt_key_id;
305 uint8_t *bkt_key;
306
307 /* Key signature comparison. */
308 if (input_sig != bkt->sig[bkt_pos])
309 return 0;
310
311 /* Key comparison. */
312 bkt_key_id = bkt->key_id[bkt_pos];
313 bkt_key = table_key(t, bkt_key_id);
314 return keycmp(bkt_key, input_key, t->key_mask, t->key_size);
315 }
316
317 static inline void
bkt_key_install(struct table * t,struct bucket_extension * bkt,struct rte_swx_table_entry * input,uint32_t bkt_pos,uint32_t bkt_key_id,uint32_t input_sig)318 bkt_key_install(struct table *t,
319 struct bucket_extension *bkt,
320 struct rte_swx_table_entry *input,
321 uint32_t bkt_pos,
322 uint32_t bkt_key_id,
323 uint32_t input_sig)
324 {
325 uint8_t *bkt_key;
326 uint64_t *bkt_data;
327
328 /* Key signature. */
329 bkt->sig[bkt_pos] = (uint16_t)input_sig;
330
331 /* Key. */
332 bkt->key_id[bkt_pos] = bkt_key_id;
333 bkt_key = table_key(t, bkt_key_id);
334 keycpy(bkt_key, input->key, t->key_mask, t->key_size);
335
336 /* Key data. */
337 bkt_data = table_key_data(t, bkt_key_id);
338 bkt_data[0] = input->action_id;
339 if (t->params.action_data_size && input->action_data)
340 memcpy(&bkt_data[1],
341 input->action_data,
342 t->params.action_data_size);
343 }
344
345 static inline void
bkt_key_data_update(struct table * t,struct bucket_extension * bkt,struct rte_swx_table_entry * input,uint32_t bkt_pos)346 bkt_key_data_update(struct table *t,
347 struct bucket_extension *bkt,
348 struct rte_swx_table_entry *input,
349 uint32_t bkt_pos)
350 {
351 uint32_t bkt_key_id;
352 uint64_t *bkt_data;
353
354 /* Key. */
355 bkt_key_id = bkt->key_id[bkt_pos];
356
357 /* Key data. */
358 bkt_data = table_key_data(t, bkt_key_id);
359 bkt_data[0] = input->action_id;
360 if (t->params.action_data_size && input->action_data)
361 memcpy(&bkt_data[1],
362 input->action_data,
363 t->params.action_data_size);
364 }
365
366 #define CL RTE_CACHE_LINE_ROUNDUP
367
368 static int
__table_create(struct table ** table,uint64_t * memory_footprint,struct rte_swx_table_params * params,const char * args __rte_unused,int numa_node)369 __table_create(struct table **table,
370 uint64_t *memory_footprint,
371 struct rte_swx_table_params *params,
372 const char *args __rte_unused,
373 int numa_node)
374 {
375 struct table *t;
376 uint8_t *memory;
377 size_t table_meta_sz, key_mask_sz, bucket_sz, bucket_ext_sz, key_sz,
378 key_stack_sz, bkt_ext_stack_sz, data_sz, total_size;
379 size_t key_mask_offset, bucket_offset, bucket_ext_offset, key_offset,
380 key_stack_offset, bkt_ext_stack_offset, data_offset;
381 uint32_t key_size, key_data_size, n_buckets, n_buckets_ext, i;
382
383 /* Check input arguments. */
384 CHECK(params, EINVAL);
385 CHECK(params->match_type == RTE_SWX_TABLE_MATCH_EXACT, EINVAL);
386 CHECK(params->key_size, EINVAL);
387 CHECK(params->key_size <= 64, EINVAL);
388 CHECK(params->n_keys_max, EINVAL);
389
390 /* Memory allocation. */
391 key_size = rte_align64pow2(params->key_size);
392 if (key_size < 8)
393 key_size = 8;
394 key_data_size = rte_align64pow2(params->action_data_size + 8);
395 n_buckets = params->n_keys_max / KEYS_PER_BUCKET;
396 n_buckets_ext = params->n_keys_max / KEYS_PER_BUCKET;
397
398 table_meta_sz = CL(sizeof(struct table));
399 key_mask_sz = CL(key_size);
400 bucket_sz = CL(n_buckets * sizeof(struct bucket_extension));
401 bucket_ext_sz = CL(n_buckets_ext * sizeof(struct bucket_extension));
402 key_sz = CL(params->n_keys_max * key_size);
403 key_stack_sz = CL(params->n_keys_max * sizeof(uint32_t));
404 bkt_ext_stack_sz = CL(n_buckets_ext * sizeof(uint32_t));
405 data_sz = CL(params->n_keys_max * key_data_size);
406 total_size = table_meta_sz + key_mask_sz + bucket_sz + bucket_ext_sz +
407 key_sz + key_stack_sz + bkt_ext_stack_sz + data_sz;
408
409 key_mask_offset = table_meta_sz;
410 bucket_offset = key_mask_offset + key_mask_sz;
411 bucket_ext_offset = bucket_offset + bucket_sz;
412 key_offset = bucket_ext_offset + bucket_ext_sz;
413 key_stack_offset = key_offset + key_sz;
414 bkt_ext_stack_offset = key_stack_offset + key_stack_sz;
415 data_offset = bkt_ext_stack_offset + bkt_ext_stack_sz;
416
417 if (!table) {
418 if (memory_footprint)
419 *memory_footprint = total_size;
420 return 0;
421 }
422
423 memory = env_malloc(total_size, RTE_CACHE_LINE_SIZE, numa_node);
424 CHECK(memory, ENOMEM);
425 memset(memory, 0, total_size);
426
427 /* Initialization. */
428 t = (struct table *)memory;
429 memcpy(&t->params, params, sizeof(*params));
430
431 t->key_size = key_size;
432 t->data_size = key_data_size;
433 t->key_size_shl = __builtin_ctzl(key_size);
434 t->data_size_shl = __builtin_ctzl(key_data_size);
435 t->n_buckets = n_buckets;
436 t->n_buckets_ext = n_buckets_ext;
437 t->total_size = total_size;
438
439 t->key_mask = &memory[key_mask_offset];
440 t->buckets = (struct bucket_extension *)&memory[bucket_offset];
441 t->buckets_ext = (struct bucket_extension *)&memory[bucket_ext_offset];
442 t->keys = &memory[key_offset];
443 t->key_stack = (uint32_t *)&memory[key_stack_offset];
444 t->bkt_ext_stack = (uint32_t *)&memory[bkt_ext_stack_offset];
445 t->data = &memory[data_offset];
446
447 t->params.key_mask0 = t->key_mask;
448
449 if (!params->key_mask0)
450 memset(t->key_mask, 0xFF, params->key_size);
451 else
452 memcpy(t->key_mask, params->key_mask0, params->key_size);
453
454 for (i = 0; i < t->params.n_keys_max; i++)
455 t->key_stack[i] = t->params.n_keys_max - 1 - i;
456 t->key_stack_tos = t->params.n_keys_max;
457
458 for (i = 0; i < n_buckets_ext; i++)
459 t->bkt_ext_stack[i] = n_buckets_ext - 1 - i;
460 t->bkt_ext_stack_tos = n_buckets_ext;
461
462 *table = t;
463 return 0;
464 }
465
466 static void
table_free(void * table)467 table_free(void *table)
468 {
469 struct table *t = table;
470
471 if (!t)
472 return;
473
474 env_free(t, t->total_size);
475 }
476
477 static int
table_add(void * table,struct rte_swx_table_entry * entry)478 table_add(void *table, struct rte_swx_table_entry *entry)
479 {
480 struct table *t = table;
481 struct bucket_extension *bkt0, *bkt, *bkt_prev;
482 uint32_t input_sig, bkt_id, i;
483
484 CHECK(t, EINVAL);
485 CHECK(entry, EINVAL);
486 CHECK(entry->key, EINVAL);
487
488 input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
489 bkt_id = input_sig & (t->n_buckets - 1);
490 bkt0 = &t->buckets[bkt_id];
491 input_sig = (input_sig >> 16) | 1;
492
493 /* Key is present in the bucket. */
494 for (bkt = bkt0; bkt; bkt = bkt->next)
495 for (i = 0; i < KEYS_PER_BUCKET; i++)
496 if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) {
497 bkt_key_data_update(t, bkt, entry, i);
498 return 0;
499 }
500
501 /* Key is not present in the bucket. Bucket not full. */
502 for (bkt = bkt0, bkt_prev = NULL; bkt; bkt_prev = bkt, bkt = bkt->next)
503 for (i = 0; i < KEYS_PER_BUCKET; i++)
504 if (bkt_key_is_empty(bkt, i)) {
505 uint32_t new_bkt_key_id;
506
507 /* Allocate new key & install. */
508 CHECK(t->key_stack_tos, ENOSPC);
509 new_bkt_key_id =
510 t->key_stack[--t->key_stack_tos];
511 bkt_key_install(t, bkt, entry, i,
512 new_bkt_key_id, input_sig);
513 return 0;
514 }
515
516 /* Bucket full: extend bucket. */
517 if (t->bkt_ext_stack_tos && t->key_stack_tos) {
518 struct bucket_extension *new_bkt;
519 uint32_t new_bkt_id, new_bkt_key_id;
520
521 /* Allocate new bucket extension & install. */
522 new_bkt_id = t->bkt_ext_stack[--t->bkt_ext_stack_tos];
523 new_bkt = &t->buckets_ext[new_bkt_id];
524 memset(new_bkt, 0, sizeof(*new_bkt));
525 bkt_prev->next = new_bkt;
526
527 /* Allocate new key & install. */
528 new_bkt_key_id = t->key_stack[--t->key_stack_tos];
529 bkt_key_install(t, new_bkt, entry, 0,
530 new_bkt_key_id, input_sig);
531 return 0;
532 }
533
534 CHECK(0, ENOSPC);
535 }
536
537 static int
table_del(void * table,struct rte_swx_table_entry * entry)538 table_del(void *table, struct rte_swx_table_entry *entry)
539 {
540 struct table *t = table;
541 struct bucket_extension *bkt0, *bkt, *bkt_prev;
542 uint32_t input_sig, bkt_id, i;
543
544 CHECK(t, EINVAL);
545 CHECK(entry, EINVAL);
546 CHECK(entry->key, EINVAL);
547
548 input_sig = hash(entry->key, t->key_mask, t->key_size, 0);
549 bkt_id = input_sig & (t->n_buckets - 1);
550 bkt0 = &t->buckets[bkt_id];
551 input_sig = (input_sig >> 16) | 1;
552
553 /* Key is present in the bucket. */
554 for (bkt = bkt0, bkt_prev = NULL; bkt; bkt_prev = bkt, bkt = bkt->next)
555 for (i = 0; i < KEYS_PER_BUCKET; i++)
556 if (bkt_keycmp(t, bkt, entry->key, i, input_sig)) {
557 /* Key free. */
558 bkt->sig[i] = 0;
559 t->key_stack[t->key_stack_tos++] =
560 bkt->key_id[i];
561
562 /* Bucket extension free if empty and not the
563 * 1st in bucket.
564 */
565 if (bkt_prev && bkt_is_empty(bkt)) {
566 bkt_prev->next = bkt->next;
567 bkt_id = bkt - t->buckets_ext;
568 t->bkt_ext_stack[t->bkt_ext_stack_tos++]
569 = bkt_id;
570 }
571
572 return 0;
573 }
574
575 return 0;
576 }
577
578 static uint64_t
table_mailbox_size_get_unoptimized(void)579 table_mailbox_size_get_unoptimized(void)
580 {
581 return 0;
582 }
583
584 static int
table_lookup_unoptimized(void * table,void * mailbox __rte_unused,uint8_t ** key,uint64_t * action_id,uint8_t ** action_data,int * hit)585 table_lookup_unoptimized(void *table,
586 void *mailbox __rte_unused,
587 uint8_t **key,
588 uint64_t *action_id,
589 uint8_t **action_data,
590 int *hit)
591 {
592 struct table *t = table;
593 struct bucket_extension *bkt0, *bkt;
594 uint8_t *input_key;
595 uint32_t input_sig, bkt_id, i;
596
597 input_key = &(*key)[t->params.key_offset];
598
599 input_sig = hash(input_key, t->key_mask, t->key_size, 0);
600 bkt_id = input_sig & (t->n_buckets - 1);
601 bkt0 = &t->buckets[bkt_id];
602 input_sig = (input_sig >> 16) | 1;
603
604 /* Key is present in the bucket. */
605 for (bkt = bkt0; bkt; bkt = bkt->next)
606 for (i = 0; i < KEYS_PER_BUCKET; i++)
607 if (bkt_keycmp(t, bkt, input_key, i, input_sig)) {
608 uint32_t bkt_key_id;
609 uint64_t *bkt_data;
610
611 /* Key. */
612 bkt_key_id = bkt->key_id[i];
613
614 /* Key data. */
615 bkt_data = table_key_data(t, bkt_key_id);
616 *action_id = bkt_data[0];
617 *action_data = (uint8_t *)&bkt_data[1];
618 *hit = 1;
619 return 1;
620 }
621
622 *hit = 0;
623 return 1;
624 }
625
626 struct mailbox {
627 struct bucket_extension *bkt;
628 uint32_t input_sig;
629 uint32_t bkt_key_id;
630 uint32_t sig_match;
631 uint32_t sig_match_many;
632 int state;
633 };
634
635 static uint64_t
table_mailbox_size_get(void)636 table_mailbox_size_get(void)
637 {
638 return sizeof(struct mailbox);
639 }
640
641 /*
642 * mask = match bitmask
643 * match = at least one match
644 * match_many = more than one match
645 * match_pos = position of first match
646 *
647 *+------+-------+------------+-----------+
648 *| mask | match | match_many | match_pos |
649 *+------+-------+------------+-----------+
650 *| 0000 | 0 | 0 | 00 |
651 *| 0001 | 1 | 0 | 00 |
652 *| 0010 | 1 | 0 | 01 |
653 *| 0011 | 1 | 1 | 00 |
654 *+------+-------+------------+-----------+
655 *| 0100 | 1 | 0 | 10 |
656 *| 0101 | 1 | 1 | 00 |
657 *| 0110 | 1 | 1 | 01 |
658 *| 0111 | 1 | 1 | 00 |
659 *+------+-------+------------+-----------+
660 *| 1000 | 1 | 0 | 11 |
661 *| 1001 | 1 | 1 | 00 |
662 *| 1010 | 1 | 1 | 01 |
663 *| 1011 | 1 | 1 | 00 |
664 *+------+-------+------------+-----------+
665 *| 1100 | 1 | 1 | 10 |
666 *| 1101 | 1 | 1 | 00 |
667 *| 1110 | 1 | 1 | 01 |
668 *| 1111 | 1 | 1 | 00 |
669 *+------+-------+------------+-----------+
670 *
671 * match = 1111_1111_1111_1110 = 0xFFFE
672 * match_many = 1111_1110_1110_1000 = 0xFEE8
673 * match_pos = 0001_0010_0001_0011__0001_0010_0001_0000 = 0x12131210
674 *
675 */
676
677 #define LUT_MATCH 0xFFFE
678 #define LUT_MATCH_MANY 0xFEE8
679 #define LUT_MATCH_POS 0x12131210
680
681 static int
table_lookup(void * table,void * mailbox,uint8_t ** key,uint64_t * action_id,uint8_t ** action_data,int * hit)682 table_lookup(void *table,
683 void *mailbox,
684 uint8_t **key,
685 uint64_t *action_id,
686 uint8_t **action_data,
687 int *hit)
688 {
689 struct table *t = table;
690 struct mailbox *m = mailbox;
691
692 switch (m->state) {
693 case 0: {
694 uint8_t *input_key = &(*key)[t->params.key_offset];
695 struct bucket_extension *bkt;
696 uint32_t input_sig, bkt_id;
697
698 input_sig = hash(input_key, t->key_mask, t->key_size, 0);
699 bkt_id = input_sig & (t->n_buckets - 1);
700 bkt = &t->buckets[bkt_id];
701 rte_prefetch0(bkt);
702
703 m->bkt = bkt;
704 m->input_sig = (input_sig >> 16) | 1;
705 m->state++;
706 return 0;
707 }
708
709 case 1: {
710 struct bucket_extension *bkt = m->bkt;
711 uint32_t input_sig = m->input_sig;
712 uint32_t bkt_sig0, bkt_sig1, bkt_sig2, bkt_sig3;
713 uint32_t mask0 = 0, mask1 = 0, mask2 = 0, mask3 = 0, mask_all;
714 uint32_t sig_match = LUT_MATCH;
715 uint32_t sig_match_many = LUT_MATCH_MANY;
716 uint32_t sig_match_pos = LUT_MATCH_POS;
717 uint32_t bkt_key_id;
718
719 bkt_sig0 = input_sig ^ bkt->sig[0];
720 if (!bkt_sig0)
721 mask0 = 1 << 0;
722
723 bkt_sig1 = input_sig ^ bkt->sig[1];
724 if (!bkt_sig1)
725 mask1 = 1 << 1;
726
727 bkt_sig2 = input_sig ^ bkt->sig[2];
728 if (!bkt_sig2)
729 mask2 = 1 << 2;
730
731 bkt_sig3 = input_sig ^ bkt->sig[3];
732 if (!bkt_sig3)
733 mask3 = 1 << 3;
734
735 mask_all = (mask0 | mask1) | (mask2 | mask3);
736 sig_match = (sig_match >> mask_all) & 1;
737 sig_match_many = (sig_match_many >> mask_all) & 1;
738 sig_match_pos = (sig_match_pos >> (mask_all << 1)) & 3;
739
740 bkt_key_id = bkt->key_id[sig_match_pos];
741 rte_prefetch0(table_key(t, bkt_key_id));
742 rte_prefetch0(table_key_data(t, bkt_key_id));
743
744 m->bkt_key_id = bkt_key_id;
745 m->sig_match = sig_match;
746 m->sig_match_many = sig_match_many;
747 m->state++;
748 return 0;
749 }
750
751 case 2: {
752 uint8_t *input_key = &(*key)[t->params.key_offset];
753 struct bucket_extension *bkt = m->bkt;
754 uint32_t bkt_key_id = m->bkt_key_id;
755 uint8_t *bkt_key = table_key(t, bkt_key_id);
756 uint64_t *bkt_data = table_key_data(t, bkt_key_id);
757 uint32_t lkp_hit;
758
759 lkp_hit = keycmp(bkt_key, input_key, t->key_mask, t->key_size);
760 lkp_hit &= m->sig_match;
761 *action_id = bkt_data[0];
762 *action_data = (uint8_t *)&bkt_data[1];
763 *hit = lkp_hit;
764
765 m->state = 0;
766
767 if (!lkp_hit && (m->sig_match_many || bkt->next))
768 return table_lookup_unoptimized(t,
769 m,
770 key,
771 action_id,
772 action_data,
773 hit);
774
775 return 1;
776 }
777
778 default:
779 return 0;
780 }
781 }
782
783 static void *
table_create(struct rte_swx_table_params * params,struct rte_swx_table_entry_list * entries,const char * args,int numa_node)784 table_create(struct rte_swx_table_params *params,
785 struct rte_swx_table_entry_list *entries,
786 const char *args,
787 int numa_node)
788 {
789 struct table *t;
790 struct rte_swx_table_entry *entry;
791 int status;
792
793 /* Table create. */
794 status = __table_create(&t, NULL, params, args, numa_node);
795 if (status)
796 return NULL;
797
798 /* Table add entries. */
799 if (!entries)
800 return t;
801
802 TAILQ_FOREACH(entry, entries, node) {
803 int status;
804
805 status = table_add(t, entry);
806 if (status) {
807 table_free(t);
808 return NULL;
809 }
810 }
811
812 return t;
813 }
814
815 static uint64_t
table_footprint(struct rte_swx_table_params * params,struct rte_swx_table_entry_list * entries __rte_unused,const char * args)816 table_footprint(struct rte_swx_table_params *params,
817 struct rte_swx_table_entry_list *entries __rte_unused,
818 const char *args)
819 {
820 uint64_t memory_footprint;
821 int status;
822
823 status = __table_create(NULL, &memory_footprint, params, args, 0);
824 if (status)
825 return 0;
826
827 return memory_footprint;
828 }
829
830 struct rte_swx_table_ops rte_swx_table_exact_match_unoptimized_ops = {
831 .footprint_get = table_footprint,
832 .mailbox_size_get = table_mailbox_size_get_unoptimized,
833 .create = table_create,
834 .add = table_add,
835 .del = table_del,
836 .lkp = table_lookup_unoptimized,
837 .free = table_free,
838 };
839
840 struct rte_swx_table_ops rte_swx_table_exact_match_ops = {
841 .footprint_get = table_footprint,
842 .mailbox_size_get = table_mailbox_size_get,
843 .create = table_create,
844 .add = table_add,
845 .del = table_del,
846 .lkp = table_lookup,
847 .free = table_free,
848 };
849