1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2020 Intel Corporation
8 #include <rte_common.h>
9 #include <rte_cycles.h>
10 #include <rte_prefetch.h>
12 #include "rte_swx_table_learner.h"
14 #ifndef RTE_SWX_TABLE_LEARNER_USE_HUGE_PAGES
15 #define RTE_SWX_TABLE_LEARNER_USE_HUGE_PAGES 1
18 #ifndef RTE_SWX_TABLE_SELECTOR_HUGE_PAGES_DISABLE
20 #include <rte_malloc.h>
23 env_calloc(size_t size, size_t alignment, int numa_node)
25 return rte_zmalloc_socket(NULL, size, alignment, numa_node);
29 env_free(void *start, size_t size __rte_unused)
39 env_calloc(size_t size, size_t alignment __rte_unused, int numa_node)
43 if (numa_available() == -1)
46 start = numa_alloc_onnode(size, numa_node);
50 memset(start, 0, size);
55 env_free(void *start, size_t size)
57 if ((numa_available() == -1) || !start)
60 numa_free(start, size);
65 #if defined(RTE_ARCH_X86_64)
67 #include <x86intrin.h>
69 #define crc32_u64(crc, v) _mm_crc32_u64(crc, v)
73 static inline uint64_t
74 crc32_u64_generic(uint64_t crc, uint64_t value)
78 crc = (crc & 0xFFFFFFFFLLU) ^ value;
79 for (i = 63; i >= 0; i--) {
83 crc = (crc >> 1LLU) ^ (0x82F63B78LLU & mask);
89 #define crc32_u64(crc, v) crc32_u64_generic(crc, v)
93 /* Key size needs to be one of: 8, 16, 32 or 64. */
94 static inline uint32_t
95 hash(void *key, void *key_mask, uint32_t key_size, uint32_t seed)
98 uint64_t *m = key_mask;
99 uint64_t k0, k2, k5, crc0, crc1, crc2, crc3, crc4, crc5;
103 crc0 = crc32_u64(seed, k[0] & m[0]);
109 crc0 = crc32_u64(k0, seed);
110 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
120 crc0 = crc32_u64(k0, seed);
121 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
123 crc2 = crc32_u64(k2, k[3] & m[3]);
126 crc0 = crc32_u64(crc0, crc1);
127 crc1 = crc32_u64(crc2, crc3);
138 crc0 = crc32_u64(k0, seed);
139 crc1 = crc32_u64(k0 >> 32, k[1] & m[1]);
141 crc2 = crc32_u64(k2, k[3] & m[3]);
142 crc3 = crc32_u64(k2 >> 32, k[4] & m[4]);
144 crc4 = crc32_u64(k5, k[6] & m[6]);
145 crc5 = crc32_u64(k5 >> 32, k[7] & m[7]);
147 crc0 = crc32_u64(crc0, (crc1 << 32) ^ crc2);
148 crc1 = crc32_u64(crc3, (crc4 << 32) ^ crc5);
160 /* n_bytes needs to be a multiple of 8 bytes. */
162 table_keycpy(void *dst, void *src, void *src_mask, uint32_t n_bytes)
164 uint64_t *dst64 = dst, *src64 = src, *src_mask64 = src_mask;
167 for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
168 dst64[i] = src64[i] & src_mask64[i];
172 * Return: 0 = Keys are NOT equal; 1 = Keys are equal.
174 static inline uint32_t
175 table_keycmp(void *a, void *b, void *b_mask, uint32_t n_bytes)
177 uint64_t *a64 = a, *b64 = b, *b_mask64 = b_mask;
181 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
190 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
191 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
192 uint64_t or = xor0 | xor1;
201 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
202 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
203 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
204 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
205 uint64_t or = (xor0 | xor1) | (xor2 | xor3);
214 uint64_t xor0 = a64[0] ^ (b64[0] & b_mask64[0]);
215 uint64_t xor1 = a64[1] ^ (b64[1] & b_mask64[1]);
216 uint64_t xor2 = a64[2] ^ (b64[2] & b_mask64[2]);
217 uint64_t xor3 = a64[3] ^ (b64[3] & b_mask64[3]);
218 uint64_t xor4 = a64[4] ^ (b64[4] & b_mask64[4]);
219 uint64_t xor5 = a64[5] ^ (b64[5] & b_mask64[5]);
220 uint64_t xor6 = a64[6] ^ (b64[6] & b_mask64[6]);
221 uint64_t xor7 = a64[7] ^ (b64[7] & b_mask64[7]);
222 uint64_t or = ((xor0 | xor1) | (xor2 | xor3)) |
223 ((xor4 | xor5) | (xor6 | xor7));
234 for (i = 0; i < n_bytes / sizeof(uint64_t); i++)
235 if (a64[i] != (b64[i] & b_mask64[i]))
242 #define TABLE_KEYS_PER_BUCKET 4
244 #define TABLE_BUCKET_USEFUL_SIZE \
245 (TABLE_KEYS_PER_BUCKET * (sizeof(uint32_t) + sizeof(uint32_t) + sizeof(uint8_t)))
247 #define TABLE_BUCKET_PAD_SIZE \
248 (RTE_CACHE_LINE_SIZE - TABLE_BUCKET_USEFUL_SIZE)
250 struct table_bucket {
251 uint32_t time[TABLE_KEYS_PER_BUCKET];
252 uint32_t sig[TABLE_KEYS_PER_BUCKET];
253 uint8_t key_timeout_id[TABLE_KEYS_PER_BUCKET];
254 uint8_t pad[TABLE_BUCKET_PAD_SIZE];
258 struct table_params {
259 /* The real key size. Must be non-zero. */
262 /* They key size upgrated to the next power of 2. This used for hash generation (in
263 * increments of 8 bytes, from 8 to 64 bytes) and for run-time key comparison. This is why
264 * key sizes bigger than 64 bytes are not allowed.
266 size_t key_size_pow2;
268 /* log2(key_size_pow2). Purpose: avoid multiplication with non-power-of-2 numbers. */
269 size_t key_size_log2;
271 /* The key offset within the key buffer. */
274 /* The real action data size. */
275 size_t action_data_size;
277 /* The data size, i.e. the 8-byte action_id field plus the action data size, upgraded to the
280 size_t data_size_pow2;
282 /* log2(data_size_pow2). Purpose: avoid multiplication with non-power of 2 numbers. */
283 size_t data_size_log2;
285 /* Number of buckets. Must be a power of 2 to avoid modulo with non-power-of-2 numbers. */
288 /* Bucket mask. Purpose: replace modulo with bitmask and operation. */
291 /* Total number of key bytes in the bucket, including the key padding bytes. There are
292 * (key_size_pow2 - key_size) padding bytes for each key in the bucket.
294 size_t bucket_key_all_size;
296 /* Bucket size. Must be a power of 2 to avoid multiplication with non-power-of-2 number. */
299 /* log2(bucket_size). Purpose: avoid multiplication with non-power of 2 numbers. */
300 size_t bucket_size_log2;
302 /* Set of all possible key timeout values measured in CPU clock cycles. */
303 uint64_t key_timeout[RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX];
305 /* Number of key timeout values. */
306 uint32_t n_key_timeouts;
308 /* Total memory size. */
313 /* Table parameters. */
314 struct table_params params;
316 /* Key mask. Array of *key_size* bytes. */
317 uint8_t key_mask0[RTE_CACHE_LINE_SIZE];
321 } __rte_cache_aligned;
323 /* The timeout (in cycles) is stored in the table as a 32-bit value by truncating its least
324 * significant 32 bits. Therefore, to make sure the time is always advancing when adding the timeout
325 * value on top of the current time, the minimum timeout value is 1^32 cycles, which is 2 seconds on
329 timeout_convert(uint32_t timeout_in_seconds)
331 uint64_t timeout_in_cycles = timeout_in_seconds * rte_get_tsc_hz();
333 if (!(timeout_in_cycles >> 32))
334 timeout_in_cycles = 1LLU << 32;
336 return timeout_in_cycles;
340 table_params_get(struct table_params *p, struct rte_swx_table_learner_params *params)
344 /* Check input parameters. */
347 (params->key_size > 64) ||
348 !params->n_keys_max ||
349 (params->n_keys_max > 1U << 31) ||
350 !params->key_timeout ||
351 !params->n_key_timeouts ||
352 (params->n_key_timeouts > RTE_SWX_TABLE_LEARNER_N_KEY_TIMEOUTS_MAX))
355 for (i = 0; i < params->n_key_timeouts; i++)
356 if (!params->key_timeout[i])
360 p->key_size = params->key_size;
362 p->key_size_pow2 = rte_align64pow2(p->key_size);
363 if (p->key_size_pow2 < 8)
364 p->key_size_pow2 = 8;
366 p->key_size_log2 = __builtin_ctzll(p->key_size_pow2);
368 p->key_offset = params->key_offset;
371 p->action_data_size = params->action_data_size;
373 p->data_size_pow2 = rte_align64pow2(sizeof(uint64_t) + p->action_data_size);
375 p->data_size_log2 = __builtin_ctzll(p->data_size_pow2);
378 p->n_buckets = rte_align32pow2(params->n_keys_max);
380 p->bucket_mask = p->n_buckets - 1;
382 p->bucket_key_all_size = TABLE_KEYS_PER_BUCKET * p->key_size_pow2;
384 p->bucket_size = rte_align64pow2(sizeof(struct table_bucket) +
385 p->bucket_key_all_size +
386 TABLE_KEYS_PER_BUCKET * p->data_size_pow2);
388 p->bucket_size_log2 = __builtin_ctzll(p->bucket_size);
391 for (i = 0; i < params->n_key_timeouts; i++)
392 p->key_timeout[i] = timeout_convert(params->key_timeout[i]);
394 p->n_key_timeouts = rte_align32pow2(params->n_key_timeouts);
396 for ( ; i < p->n_key_timeouts; i++)
397 p->key_timeout[i] = p->key_timeout[0];
400 p->total_size = sizeof(struct table) + p->n_buckets * p->bucket_size;
405 static inline struct table_bucket *
406 table_bucket_get(struct table *t, size_t bucket_id)
408 return (struct table_bucket *)&t->buckets[bucket_id << t->params.bucket_size_log2];
411 static inline uint8_t *
412 table_bucket_key_get(struct table *t, struct table_bucket *b, size_t bucket_key_pos)
414 return &b->key[bucket_key_pos << t->params.key_size_log2];
417 static inline uint64_t *
418 table_bucket_data_get(struct table *t, struct table_bucket *b, size_t bucket_key_pos)
420 return (uint64_t *)&b->key[t->params.bucket_key_all_size +
421 (bucket_key_pos << t->params.data_size_log2)];
425 rte_swx_table_learner_footprint_get(struct rte_swx_table_learner_params *params)
427 struct table_params p;
430 status = table_params_get(&p, params);
432 return status ? 0 : p.total_size;
436 rte_swx_table_learner_create(struct rte_swx_table_learner_params *params, int numa_node)
438 struct table_params p;
442 /* Check and process the input parameters. */
443 status = table_params_get(&p, params);
447 /* Memory allocation. */
448 t = env_calloc(p.total_size, RTE_CACHE_LINE_SIZE, numa_node);
452 /* Memory initialization. */
453 memcpy(&t->params, &p, sizeof(struct table_params));
455 if (params->key_mask0)
456 memcpy(t->key_mask0, params->key_mask0, params->key_size);
458 memset(t->key_mask0, 0xFF, params->key_size);
464 rte_swx_table_learner_free(void *table)
466 struct table *t = table;
471 env_free(t, t->params.total_size);
475 rte_swx_table_learner_timeout_update(void *table,
476 uint32_t key_timeout_id,
477 uint32_t key_timeout)
479 struct table *t = table;
482 (key_timeout_id >= t->params.n_key_timeouts) ||
486 t->params.key_timeout[key_timeout_id] = timeout_convert(key_timeout);
492 /* Writer: lookup state 0. Reader(s): lookup state 1, add(). */
493 struct table_bucket *bucket;
495 /* Writer: lookup state 0. Reader(s): lookup state 1, add(). */
498 /* Writer: lookup state 1. Reader(s): add(). */
501 /* Writer: lookup state 1. Reader(s): add(). Values: 0 = miss; 1 = hit. */
504 /* Writer: lookup state 1. Reader(s): add(). Valid only when hit is non-zero. */
505 size_t bucket_key_pos;
512 rte_swx_table_learner_mailbox_size_get(void)
514 return sizeof(struct mailbox);
518 rte_swx_table_learner_lookup(void *table,
523 uint8_t **action_data,
526 struct table *t = table;
527 struct mailbox *m = mailbox;
532 struct table_bucket *b;
536 input_key = &(*key)[t->params.key_offset];
537 input_sig = hash(input_key, t->key_mask0, t->params.key_size_pow2, 0);
538 bucket_id = input_sig & t->params.bucket_mask;
539 b = table_bucket_get(t, bucket_id);
542 rte_prefetch0(&b->key[0]);
543 rte_prefetch0(&b->key[RTE_CACHE_LINE_SIZE]);
546 m->input_key = input_key;
547 m->input_sig = input_sig | 1;
553 struct table_bucket *b = m->bucket;
556 /* Search the input key through the bucket keys. */
557 for (i = 0; i < TABLE_KEYS_PER_BUCKET; i++) {
558 uint64_t time = b->time[i];
559 uint32_t sig = b->sig[i];
560 uint8_t *key = table_bucket_key_get(t, b, i);
561 uint32_t key_size_pow2 = t->params.key_size_pow2;
565 if ((time > input_time) &&
566 (sig == m->input_sig) &&
567 table_keycmp(key, m->input_key, t->key_mask0, key_size_pow2)) {
568 uint64_t *data = table_bucket_data_get(t, b, i);
574 m->bucket_key_pos = i;
577 *action_id = data[0];
578 *action_data = (uint8_t *)&data[1];
593 /* This state should never be reached. Miss. */
603 rte_swx_table_learner_rearm(void *table,
607 struct table *t = table;
608 struct mailbox *m = mailbox;
609 struct table_bucket *b;
610 size_t bucket_key_pos;
611 uint64_t key_timeout;
612 uint32_t key_timeout_id;
618 bucket_key_pos = m->bucket_key_pos;
620 key_timeout_id = b->key_timeout_id[bucket_key_pos];
621 key_timeout = t->params.key_timeout[key_timeout_id];
622 b->time[bucket_key_pos] = (input_time + key_timeout) >> 32;
626 rte_swx_table_learner_rearm_new(void *table,
629 uint32_t key_timeout_id)
631 struct table *t = table;
632 struct mailbox *m = mailbox;
633 struct table_bucket *b;
634 size_t bucket_key_pos;
635 uint64_t key_timeout;
641 bucket_key_pos = m->bucket_key_pos;
643 key_timeout_id &= t->params.n_key_timeouts - 1;
644 key_timeout = t->params.key_timeout[key_timeout_id];
645 b->time[bucket_key_pos] = (input_time + key_timeout) >> 32;
646 b->key_timeout_id[bucket_key_pos] = (uint8_t)key_timeout_id;
650 rte_swx_table_learner_add(void *table,
654 uint8_t *action_data,
655 uint32_t key_timeout_id)
657 struct table *t = table;
658 struct mailbox *m = mailbox;
659 struct table_bucket *b = m->bucket;
660 uint64_t key_timeout;
663 /* Adjust the key timeout ID to fit the valid range. */
664 key_timeout_id &= t->params.n_key_timeouts - 1;
665 key_timeout = t->params.key_timeout[key_timeout_id];
667 /* Lookup hit: The following bucket fields need to be updated:
668 * - key (key, sig): NO (already correctly set).
669 * - key timeout (key_timeout_id, time): YES.
670 * - key data (data): YES.
673 size_t bucket_key_pos = m->bucket_key_pos;
674 uint64_t *data = table_bucket_data_get(t, b, bucket_key_pos);
676 /* Install the key timeout. */
677 b->time[bucket_key_pos] = (input_time + key_timeout) >> 32;
678 b->key_timeout_id[bucket_key_pos] = (uint8_t)key_timeout_id;
680 /* Install the key data. */
682 if (t->params.action_data_size && action_data)
683 memcpy(&data[1], action_data, t->params.action_data_size);
688 /* Lookup miss: Search for a free position in the current bucket and install the key. */
689 for (i = 0; i < TABLE_KEYS_PER_BUCKET; i++) {
690 uint64_t time = b->time[i];
694 /* Free position: Either there was never a key installed here, so the key time is
695 * set to zero (the init value), which is always less than the current time, or this
696 * position was used before, but the key expired (the key time is in the past).
698 if (time < input_time) {
699 uint8_t *key = table_bucket_key_get(t, b, i);
700 uint64_t *data = table_bucket_data_get(t, b, i);
702 /* Install the key and the key timeout. */
703 b->time[i] = (input_time + key_timeout) >> 32;
704 b->sig[i] = m->input_sig;
705 b->key_timeout_id[i] = (uint8_t)key_timeout_id;
706 table_keycpy(key, m->input_key, t->key_mask0, t->params.key_size_pow2);
708 /* Install the key data. */
710 if (t->params.action_data_size && action_data)
711 memcpy(&data[1], action_data, t->params.action_data_size);
715 m->bucket_key_pos = i;
726 rte_swx_table_learner_delete(void *table __rte_unused,
729 struct mailbox *m = mailbox;
732 struct table_bucket *b = m->bucket;
734 /* Expire the key. */
735 b->time[m->bucket_key_pos] = 0;