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