Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2021 Intel Corporation
3 : : */
4 : :
5 : : #include <stdalign.h>
6 : : #include <sys/queue.h>
7 : :
8 : : #include <eal_export.h>
9 : : #include <rte_thash.h>
10 : : #include <rte_tailq.h>
11 : : #include <rte_random.h>
12 : : #include <rte_memcpy.h>
13 : : #include <rte_errno.h>
14 : : #include <rte_eal_memconfig.h>
15 : : #include <rte_log.h>
16 : : #include <rte_malloc.h>
17 : : #include <rte_cpuflags.h>
18 : :
19 [ - + ]: 253 : RTE_LOG_REGISTER_SUFFIX(thash_logtype, thash, INFO);
20 : : #define RTE_LOGTYPE_HASH thash_logtype
21 : : #define HASH_LOG(level, ...) \
22 : : RTE_LOG_LINE(level, HASH, "" __VA_ARGS__)
23 : :
24 : : #define THASH_NAME_LEN 64
25 : : #define TOEPLITZ_HASH_LEN 32
26 : :
27 : : #define RETA_SZ_IN_RANGE(reta_sz) ((reta_sz >= RTE_THASH_RETA_SZ_MIN) &&\
28 : : (reta_sz <= RTE_THASH_RETA_SZ_MAX))
29 : :
30 : : TAILQ_HEAD(rte_thash_list, rte_tailq_entry);
31 : : static struct rte_tailq_elem rte_thash_tailq = {
32 : : .name = "RTE_THASH",
33 : : };
34 [ - + ]: 253 : EAL_REGISTER_TAILQ(rte_thash_tailq)
35 : :
36 : : struct thash_lfsr {
37 : : uint32_t ref_cnt;
38 : : uint32_t poly;
39 : : /**< polynomial associated with the lfsr */
40 : : uint32_t rev_poly;
41 : : /**< polynomial to generate the sequence in reverse direction */
42 : : uint32_t state;
43 : : /**< current state of the lfsr */
44 : : uint32_t rev_state;
45 : : /**< current state of the lfsr for reverse direction */
46 : : uint32_t deg; /**< polynomial degree*/
47 : : uint32_t bits_cnt; /**< number of bits generated by lfsr*/
48 : : };
49 : :
50 : : struct rte_thash_subtuple_helper {
51 : : char name[THASH_NAME_LEN]; /** < Name of subtuple configuration */
52 : : LIST_ENTRY(rte_thash_subtuple_helper) next;
53 : : struct thash_lfsr *lfsr;
54 : : uint32_t offset; /** < Offset of the m-sequence */
55 : : uint32_t len; /** < Length of the m-sequence */
56 : : uint32_t tuple_offset; /** < Offset in bits of the subtuple */
57 : : uint32_t tuple_len; /** < Length in bits of the subtuple */
58 : : uint32_t lsb_msk; /** < (1 << reta_sz_log) - 1 */
59 : : alignas(RTE_CACHE_LINE_SIZE) uint32_t compl_table[];
60 : : /** < Complementary table */
61 : : };
62 : :
63 : : struct rte_thash_ctx {
64 : : char name[THASH_NAME_LEN];
65 : : LIST_HEAD(, rte_thash_subtuple_helper) head;
66 : : uint32_t key_len; /** < Length of the NIC RSS hash key */
67 : : uint32_t reta_sz_log; /** < size of the RSS ReTa in bits */
68 : : uint32_t subtuples_nb; /** < number of subtuples */
69 : : uint32_t flags;
70 : : uint64_t *matrices;
71 : : /**< matrices used with rte_thash_gfni implementation */
72 : : uint8_t hash_key[];
73 : : };
74 : :
75 : : RTE_EXPORT_SYMBOL(rte_thash_gfni_supported)
76 : : int
77 : 173 : rte_thash_gfni_supported(void)
78 : : {
79 : : #ifdef RTE_THASH_GFNI_DEFINED
80 : : if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_GFNI) &&
81 : : (rte_vect_get_max_simd_bitwidth() >=
82 : : RTE_VECT_SIMD_512))
83 : : return 1;
84 : : #endif
85 : :
86 : 173 : return 0;
87 : : };
88 : :
89 : : RTE_EXPORT_SYMBOL(rte_thash_complete_matrix)
90 : : void
91 : 0 : rte_thash_complete_matrix(uint64_t *matrixes, const uint8_t *rss_key, int size)
92 : : {
93 : : int i, j;
94 : : uint8_t *m = (uint8_t *)matrixes;
95 : : uint8_t left_part, right_part;
96 : :
97 [ # # ]: 0 : for (i = 0; i < size; i++) {
98 [ # # ]: 0 : for (j = 0; j < 8; j++) {
99 : 0 : left_part = rss_key[i] << j;
100 : 0 : right_part = (uint16_t)(rss_key[(i + 1) % size]) >>
101 : 0 : (8 - j);
102 : 0 : m[i * 8 + j] = left_part|right_part;
103 : : }
104 : : }
105 : 0 : }
106 : :
107 : : static inline uint32_t
108 : : get_bit_lfsr(struct thash_lfsr *lfsr)
109 : : {
110 : : uint32_t bit, ret;
111 : :
112 : : /*
113 : : * masking the TAP bits defined by the polynomial and
114 : : * calculating parity
115 : : */
116 : 3254 : bit = rte_popcount32(lfsr->state & lfsr->poly) & 0x1;
117 : 3464 : ret = lfsr->state & 0x1;
118 : 3464 : lfsr->state = ((lfsr->state >> 1) | (bit << (lfsr->deg - 1))) &
119 : 3464 : ((1 << lfsr->deg) - 1);
120 : :
121 : 3464 : lfsr->bits_cnt++;
122 : : return ret;
123 : : }
124 : :
125 : : static inline uint32_t
126 : : get_rev_bit_lfsr(struct thash_lfsr *lfsr)
127 : : {
128 : : uint32_t bit, ret;
129 : :
130 : 844 : bit = rte_popcount32(lfsr->rev_state & lfsr->rev_poly) & 0x1;
131 : 0 : ret = lfsr->rev_state & (1 << (lfsr->deg - 1));
132 : 844 : lfsr->rev_state = ((lfsr->rev_state << 1) | bit) &
133 : 0 : ((1 << lfsr->deg) - 1);
134 : :
135 : 844 : lfsr->bits_cnt++;
136 : : return ret;
137 : : }
138 : :
139 : : static inline uint32_t
140 : : get_rev_poly(uint32_t poly, int degree)
141 : : {
142 : : int i;
143 : : /*
144 : : * The implicit highest coefficient of the polynomial
145 : : * becomes the lowest after reversal.
146 : : */
147 : : uint32_t rev_poly = 1;
148 : 81 : uint32_t mask = (1 << degree) - 1;
149 : :
150 : : /*
151 : : * Here we assume "poly" argument is an irreducible polynomial,
152 : : * thus the lowest coefficient of the "poly" must always be equal to "1".
153 : : * After the reversal, this the lowest coefficient becomes the highest and
154 : : * it is omitted since the highest coefficient is implicitly determined by
155 : : * degree of the polynomial.
156 : : */
157 [ + + ]: 763 : for (i = 1; i < degree; i++)
158 : 682 : rev_poly |= ((poly >> i) & 0x1) << (degree - i);
159 : :
160 : 81 : return rev_poly & mask;
161 : : }
162 : :
163 : : static struct thash_lfsr *
164 : 81 : alloc_lfsr(uint32_t poly_degree)
165 : : {
166 : : struct thash_lfsr *lfsr;
167 : : uint32_t i;
168 : :
169 [ + - ]: 81 : if ((poly_degree > 32) || (poly_degree == 0))
170 : : return NULL;
171 : :
172 : 81 : lfsr = rte_zmalloc(NULL, sizeof(struct thash_lfsr), 0);
173 [ + - ]: 81 : if (lfsr == NULL)
174 : : return NULL;
175 : :
176 : 81 : lfsr->deg = poly_degree;
177 : 81 : lfsr->poly = thash_get_rand_poly(lfsr->deg);
178 : : do {
179 : 81 : lfsr->state = rte_rand() & ((1 << lfsr->deg) - 1);
180 [ - + ]: 81 : } while (lfsr->state == 0);
181 : : /* init reverse order polynomial */
182 : 81 : lfsr->rev_poly = get_rev_poly(lfsr->poly, lfsr->deg);
183 : : /* init proper rev_state*/
184 : 81 : lfsr->rev_state = lfsr->state;
185 [ + + ]: 925 : for (i = 0; i <= lfsr->deg; i++)
186 : : get_rev_bit_lfsr(lfsr);
187 : :
188 : : /* clear bits_cnt after rev_state was inited */
189 : 81 : lfsr->bits_cnt = 0;
190 : 81 : lfsr->ref_cnt = 1;
191 : :
192 : 81 : return lfsr;
193 : : }
194 : :
195 : : static void
196 : : attach_lfsr(struct rte_thash_subtuple_helper *h, struct thash_lfsr *lfsr)
197 : : {
198 : 5 : lfsr->ref_cnt++;
199 : 5 : h->lfsr = lfsr;
200 : : }
201 : :
202 : : static void
203 : : free_lfsr(struct thash_lfsr *lfsr)
204 : : {
205 : 85 : lfsr->ref_cnt--;
206 [ + - ]: 10 : if (lfsr->ref_cnt == 0)
207 : 80 : rte_free(lfsr);
208 : : }
209 : :
210 : : RTE_EXPORT_SYMBOL(rte_thash_init_ctx)
211 : : struct rte_thash_ctx *
212 : 173 : rte_thash_init_ctx(const char *name, uint32_t key_len, uint32_t reta_sz,
213 : : uint8_t *key, uint32_t flags)
214 : : {
215 : : struct rte_thash_ctx *ctx;
216 : : struct rte_tailq_entry *te;
217 : : struct rte_thash_list *thash_list;
218 : : uint32_t i;
219 : :
220 [ + + - + ]: 173 : if ((name == NULL) || (key_len == 0) || !RETA_SZ_IN_RANGE(reta_sz)) {
221 : 4 : rte_errno = EINVAL;
222 : 4 : return NULL;
223 : : }
224 : :
225 : 169 : thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
226 : :
227 : 169 : rte_mcfg_tailq_write_lock();
228 : :
229 : : /* guarantee there's no existing */
230 [ - + ]: 169 : TAILQ_FOREACH(te, thash_list, next) {
231 : 0 : ctx = (struct rte_thash_ctx *)te->data;
232 [ # # ]: 0 : if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
233 : : break;
234 : : }
235 : : ctx = NULL;
236 [ - + ]: 169 : if (te != NULL) {
237 : 0 : rte_errno = EEXIST;
238 : 0 : goto exit;
239 : : }
240 : :
241 : : /* allocate tailq entry */
242 : 169 : te = rte_zmalloc("THASH_TAILQ_ENTRY", sizeof(*te), 0);
243 [ - + ]: 169 : if (te == NULL) {
244 : 0 : HASH_LOG(ERR,
245 : : "Can not allocate tailq entry for thash context %s",
246 : : name);
247 : 0 : rte_errno = ENOMEM;
248 : 0 : goto exit;
249 : : }
250 : :
251 : 169 : ctx = rte_zmalloc(NULL, sizeof(struct rte_thash_ctx) + key_len, 0);
252 [ - + ]: 169 : if (ctx == NULL) {
253 : 0 : HASH_LOG(ERR, "thash ctx %s memory allocation failed",
254 : : name);
255 : 0 : rte_errno = ENOMEM;
256 : 0 : goto free_te;
257 : : }
258 : :
259 [ + + ]: 169 : rte_strlcpy(ctx->name, name, sizeof(ctx->name));
260 : 169 : ctx->key_len = key_len;
261 : 169 : ctx->reta_sz_log = reta_sz;
262 : 169 : LIST_INIT(&ctx->head);
263 : 169 : ctx->flags = flags;
264 : :
265 [ + + ]: 169 : if (key)
266 [ - + ]: 1 : rte_memcpy(ctx->hash_key, key, key_len);
267 : : else {
268 [ + + ]: 6888 : for (i = 0; i < key_len; i++)
269 : 6720 : ctx->hash_key[i] = rte_rand();
270 : : }
271 : :
272 [ - + ]: 169 : if (rte_thash_gfni_supported()) {
273 : 0 : ctx->matrices = rte_zmalloc(NULL, key_len * sizeof(uint64_t),
274 : : RTE_CACHE_LINE_SIZE);
275 [ # # ]: 0 : if (ctx->matrices == NULL) {
276 : 0 : HASH_LOG(ERR, "Cannot allocate matrices");
277 : 0 : rte_errno = ENOMEM;
278 : 0 : goto free_ctx;
279 : : }
280 : :
281 : 0 : rte_thash_complete_matrix(ctx->matrices, ctx->hash_key,
282 : : key_len);
283 : : }
284 : :
285 : 169 : te->data = (void *)ctx;
286 : 169 : TAILQ_INSERT_TAIL(thash_list, te, next);
287 : :
288 : 169 : rte_mcfg_tailq_write_unlock();
289 : :
290 : 169 : return ctx;
291 : :
292 : : free_ctx:
293 : 0 : rte_free(ctx);
294 : 0 : free_te:
295 : 0 : rte_free(te);
296 : 0 : exit:
297 : 0 : rte_mcfg_tailq_write_unlock();
298 : 0 : return NULL;
299 : : }
300 : :
301 : : RTE_EXPORT_SYMBOL(rte_thash_find_existing)
302 : : struct rte_thash_ctx *
303 : 1 : rte_thash_find_existing(const char *name)
304 : : {
305 : : struct rte_thash_ctx *ctx;
306 : : struct rte_tailq_entry *te;
307 : : struct rte_thash_list *thash_list;
308 : :
309 : 1 : thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
310 : :
311 : 1 : rte_mcfg_tailq_read_lock();
312 [ + - ]: 1 : TAILQ_FOREACH(te, thash_list, next) {
313 : 1 : ctx = (struct rte_thash_ctx *)te->data;
314 [ - + ]: 1 : if (strncmp(name, ctx->name, sizeof(ctx->name)) == 0)
315 : : break;
316 : : }
317 : :
318 : 1 : rte_mcfg_tailq_read_unlock();
319 : :
320 [ - + ]: 1 : if (te == NULL) {
321 : 0 : rte_errno = ENOENT;
322 : 0 : return NULL;
323 : : }
324 : :
325 : : return ctx;
326 : : }
327 : :
328 : : RTE_EXPORT_SYMBOL(rte_thash_free_ctx)
329 : : void
330 : 170 : rte_thash_free_ctx(struct rte_thash_ctx *ctx)
331 : : {
332 : : struct rte_tailq_entry *te;
333 : : struct rte_thash_list *thash_list;
334 : : struct rte_thash_subtuple_helper *ent, *tmp;
335 : :
336 [ + + ]: 170 : if (ctx == NULL)
337 : : return;
338 : :
339 : 169 : thash_list = RTE_TAILQ_CAST(rte_thash_tailq.head, rte_thash_list);
340 : 169 : rte_mcfg_tailq_write_lock();
341 [ + - ]: 169 : TAILQ_FOREACH(te, thash_list, next) {
342 [ - + ]: 169 : if (te->data == (void *)ctx)
343 : : break;
344 : : }
345 : :
346 [ + - ]: 169 : if (te != NULL)
347 [ - + ]: 169 : TAILQ_REMOVE(thash_list, te, next);
348 : :
349 : 169 : rte_mcfg_tailq_write_unlock();
350 : 169 : ent = LIST_FIRST(&(ctx->head));
351 [ + + ]: 243 : while (ent) {
352 [ + + ]: 74 : free_lfsr(ent->lfsr);
353 : : tmp = ent;
354 : 74 : ent = LIST_NEXT(ent, next);
355 [ + + ]: 74 : LIST_REMOVE(tmp, next);
356 : 74 : rte_free(tmp);
357 : : }
358 : :
359 : 169 : rte_free(ctx);
360 : 169 : rte_free(te);
361 : : }
362 : :
363 : : static inline void
364 : : set_bit(uint8_t *ptr, uint32_t bit, uint32_t pos)
365 : : {
366 : 3464 : uint32_t byte_idx = pos / CHAR_BIT;
367 : : /* index of the bit int byte, indexing starts from MSB */
368 : 3464 : uint32_t bit_idx = (CHAR_BIT - 1) - (pos & (CHAR_BIT - 1));
369 : : uint8_t tmp;
370 : :
371 : 3464 : tmp = ptr[byte_idx];
372 : 3464 : tmp &= ~(1 << bit_idx);
373 : 3464 : tmp |= bit << bit_idx;
374 : 3464 : ptr[byte_idx] = tmp;
375 : : }
376 : :
377 : : /**
378 : : * writes m-sequence to the hash_key for range [start, end]
379 : : * (i.e. including start and end positions)
380 : : */
381 : : static int
382 : 76 : generate_subkey(struct rte_thash_ctx *ctx, struct thash_lfsr *lfsr,
383 : : uint32_t start, uint32_t end)
384 : : {
385 : : uint32_t i;
386 [ + + ]: 76 : uint32_t req_bits = (start < end) ? (end - start) : (start - end);
387 : 76 : req_bits++; /* due to including end */
388 : :
389 : : /* check if lfsr overflow period of the m-sequence */
390 [ + + ]: 76 : if (((lfsr->bits_cnt + req_bits) > (1ULL << lfsr->deg) - 1) &&
391 [ + + ]: 2 : ((ctx->flags & RTE_THASH_IGNORE_PERIOD_OVERFLOW) !=
392 : : RTE_THASH_IGNORE_PERIOD_OVERFLOW)) {
393 : 1 : HASH_LOG(ERR,
394 : : "Can't generate m-sequence due to period overflow");
395 : 1 : return -ENOSPC;
396 : : }
397 : :
398 [ + + ]: 75 : if (start < end) {
399 : : /* original direction (from left to right)*/
400 [ + + ]: 3326 : for (i = start; i <= end; i++)
401 : 3254 : set_bit(ctx->hash_key, get_bit_lfsr(lfsr), i);
402 : :
403 : : } else {
404 : : /* reverse direction (from right to left) */
405 [ - + ]: 3 : for (i = end; i >= start; i--)
406 : 0 : set_bit(ctx->hash_key, get_rev_bit_lfsr(lfsr), i);
407 : : }
408 : :
409 [ - + ]: 75 : if (ctx->matrices != NULL)
410 : 0 : rte_thash_complete_matrix(ctx->matrices, ctx->hash_key,
411 : 0 : ctx->key_len);
412 : :
413 : : return 0;
414 : : }
415 : :
416 : : static inline uint32_t
417 : 1837504 : get_subvalue(struct rte_thash_ctx *ctx, uint32_t offset)
418 : : {
419 : : uint32_t tmp, val;
420 : :
421 : 1837504 : tmp = *(unaligned_uint32_t *)&ctx->hash_key[offset >> 3];
422 [ - + ]: 1837504 : val = rte_be_to_cpu_32(tmp);
423 : 1837504 : val >>= (TOEPLITZ_HASH_LEN - ((offset & (CHAR_BIT - 1)) +
424 : 1837504 : ctx->reta_sz_log));
425 : :
426 : 1837504 : return val & ((1 << ctx->reta_sz_log) - 1);
427 : : }
428 : :
429 : : static inline void
430 : 74 : generate_complement_table(struct rte_thash_ctx *ctx,
431 : : struct rte_thash_subtuple_helper *h)
432 : : {
433 : : int i, j, k;
434 : : uint32_t val;
435 : : uint32_t start;
436 : :
437 : 74 : start = h->offset + h->len - (2 * ctx->reta_sz_log - 1);
438 : :
439 [ + + ]: 262464 : for (i = 1; i < (1 << ctx->reta_sz_log); i++) {
440 : : val = 0;
441 [ + + ]: 2099894 : for (j = i; j; j &= (j - 1)) {
442 : 1837504 : k = rte_bsf32(j);
443 : 1837504 : val ^= get_subvalue(ctx, start - k +
444 : : ctx->reta_sz_log - 1);
445 : : }
446 : 262390 : h->compl_table[val] = i;
447 : : }
448 : 74 : }
449 : :
450 : : static inline int
451 : 3 : insert_before(struct rte_thash_ctx *ctx,
452 : : struct rte_thash_subtuple_helper *ent,
453 : : struct rte_thash_subtuple_helper *cur_ent,
454 : : struct rte_thash_subtuple_helper *next_ent,
455 : : uint32_t start, uint32_t end, uint32_t range_end)
456 : : {
457 : : int ret;
458 : :
459 [ + + ]: 3 : if (end < cur_ent->offset) {
460 : 1 : ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
461 [ - + ]: 1 : if (ent->lfsr == NULL) {
462 : 0 : rte_free(ent);
463 : 0 : return -ENOMEM;
464 : : }
465 : : /* generate nonoverlapping range [start, end) */
466 : 1 : ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
467 [ - + ]: 1 : if (ret != 0) {
468 [ # # ]: 0 : free_lfsr(ent->lfsr);
469 : 0 : rte_free(ent);
470 : 0 : return ret;
471 : : }
472 [ + - - + ]: 2 : } else if ((next_ent != NULL) && (end > next_ent->offset)) {
473 : 0 : HASH_LOG(ERR,
474 : : "Can't add helper %s due to conflict with existing"
475 : : " helper %s", ent->name, next_ent->name);
476 : 0 : rte_free(ent);
477 : 0 : return -ENOSPC;
478 : : }
479 : 3 : attach_lfsr(ent, cur_ent->lfsr);
480 : :
481 : : /**
482 : : * generate partially overlapping range
483 : : * [start, cur_ent->start) in reverse order
484 : : */
485 : 3 : ret = generate_subkey(ctx, ent->lfsr, cur_ent->offset - 1, start);
486 [ - + ]: 3 : if (ret != 0) {
487 [ # # ]: 0 : free_lfsr(ent->lfsr);
488 : 0 : rte_free(ent);
489 : 0 : return ret;
490 : : }
491 : :
492 [ + + ]: 3 : if (end > range_end) {
493 : : /**
494 : : * generate partially overlapping range
495 : : * (range_end, end)
496 : : */
497 : 1 : ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
498 [ - + ]: 1 : if (ret != 0) {
499 [ # # ]: 0 : free_lfsr(ent->lfsr);
500 : 0 : rte_free(ent);
501 : 0 : return ret;
502 : : }
503 : : }
504 : :
505 : 3 : LIST_INSERT_BEFORE(cur_ent, ent, next);
506 : 3 : generate_complement_table(ctx, ent);
507 : 3 : ctx->subtuples_nb++;
508 : 3 : return 0;
509 : : }
510 : :
511 : : static inline int
512 : 3 : insert_after(struct rte_thash_ctx *ctx,
513 : : struct rte_thash_subtuple_helper *ent,
514 : : struct rte_thash_subtuple_helper *cur_ent,
515 : : struct rte_thash_subtuple_helper *next_ent,
516 : : struct rte_thash_subtuple_helper *prev_ent,
517 : : uint32_t end, uint32_t range_end)
518 : : {
519 : : int ret;
520 : :
521 [ + + + + ]: 3 : if ((next_ent != NULL) && (end > next_ent->offset)) {
522 : 1 : HASH_LOG(ERR,
523 : : "Can't add helper %s due to conflict with existing"
524 : : " helper %s", ent->name, next_ent->name);
525 : 1 : rte_free(ent);
526 : 1 : return -EEXIST;
527 : : }
528 : :
529 : 2 : attach_lfsr(ent, cur_ent->lfsr);
530 [ + + ]: 2 : if (end > range_end) {
531 : : /**
532 : : * generate partially overlapping range
533 : : * (range_end, end)
534 : : */
535 : 1 : ret = generate_subkey(ctx, ent->lfsr, range_end, end - 1);
536 [ - + ]: 1 : if (ret != 0) {
537 [ # # ]: 0 : free_lfsr(ent->lfsr);
538 : 0 : rte_free(ent);
539 : 0 : return ret;
540 : : }
541 : : }
542 : :
543 [ + + ]: 2 : LIST_INSERT_AFTER(prev_ent, ent, next);
544 : 2 : generate_complement_table(ctx, ent);
545 : 2 : ctx->subtuples_nb++;
546 : :
547 : 2 : return 0;
548 : : }
549 : :
550 : : RTE_EXPORT_SYMBOL(rte_thash_add_helper)
551 : : int
552 : 81 : rte_thash_add_helper(struct rte_thash_ctx *ctx, const char *name, uint32_t len,
553 : : uint32_t offset)
554 : : {
555 : : struct rte_thash_subtuple_helper *ent, *cur_ent, *prev_ent, *next_ent;
556 : : uint32_t start, end;
557 : : int ret;
558 : :
559 [ + + + + ]: 81 : if ((ctx == NULL) || (name == NULL) || (len < ctx->reta_sz_log) ||
560 : 78 : ((offset + len + TOEPLITZ_HASH_LEN - 1) >
561 [ + + ]: 78 : ctx->key_len * CHAR_BIT))
562 : : return -EINVAL;
563 : :
564 : : /* Check for existing name*/
565 [ + + ]: 101 : LIST_FOREACH(cur_ent, &ctx->head, next) {
566 [ + + ]: 25 : if (strncmp(name, cur_ent->name, sizeof(cur_ent->name)) == 0)
567 : : return -EEXIST;
568 : : }
569 : :
570 : : end = offset + len + TOEPLITZ_HASH_LEN - 1;
571 : 76 : start = ((ctx->flags & RTE_THASH_MINIMAL_SEQ) ==
572 [ + + ]: 76 : RTE_THASH_MINIMAL_SEQ) ? (end - (2 * ctx->reta_sz_log - 1)) :
573 : : offset;
574 : :
575 : 76 : ent = rte_zmalloc(NULL, sizeof(struct rte_thash_subtuple_helper) +
576 : 76 : (sizeof(uint32_t) << ctx->reta_sz_log),
577 : : RTE_CACHE_LINE_SIZE);
578 [ + - ]: 76 : if (ent == NULL)
579 : : return -ENOMEM;
580 : :
581 : 76 : rte_strlcpy(ent->name, name, sizeof(ent->name));
582 : 76 : ent->offset = start;
583 : 76 : ent->len = end - start;
584 : 76 : ent->tuple_offset = offset;
585 : 76 : ent->tuple_len = len;
586 : 76 : ent->lsb_msk = (1 << ctx->reta_sz_log) - 1;
587 : :
588 : 76 : cur_ent = LIST_FIRST(&ctx->head);
589 [ + + ]: 78 : while (cur_ent) {
590 : 8 : uint32_t range_end = cur_ent->offset + cur_ent->len;
591 : 8 : next_ent = LIST_NEXT(cur_ent, next);
592 : : prev_ent = cur_ent;
593 : : /* Iterate through overlapping ranges */
594 [ + + + + ]: 19 : while ((next_ent != NULL) && (next_ent->offset < range_end)) {
595 : 11 : range_end = RTE_MAX(next_ent->offset + next_ent->len,
596 : : range_end);
597 [ + + ]: 11 : if (start > next_ent->offset)
598 : : prev_ent = next_ent;
599 : :
600 : 11 : next_ent = LIST_NEXT(next_ent, next);
601 : : }
602 : :
603 [ + + ]: 8 : if (start < cur_ent->offset)
604 : 3 : return insert_before(ctx, ent, cur_ent, next_ent,
605 : : start, end, range_end);
606 [ + + ]: 5 : else if (start < range_end)
607 : 3 : return insert_after(ctx, ent, cur_ent, next_ent,
608 : : prev_ent, end, range_end);
609 : :
610 : : cur_ent = next_ent;
611 : 2 : continue;
612 : : }
613 : :
614 : 70 : ent->lfsr = alloc_lfsr(ctx->reta_sz_log);
615 [ - + ]: 70 : if (ent->lfsr == NULL) {
616 : 0 : rte_free(ent);
617 : 0 : return -ENOMEM;
618 : : }
619 : :
620 : : /* generate nonoverlapping range [start, end) */
621 : 70 : ret = generate_subkey(ctx, ent->lfsr, start, end - 1);
622 [ + + ]: 70 : if (ret != 0) {
623 [ + - ]: 1 : free_lfsr(ent->lfsr);
624 : 1 : rte_free(ent);
625 : 1 : return ret;
626 : : }
627 [ + + ]: 69 : if (LIST_EMPTY(&ctx->head)) {
628 : 67 : LIST_INSERT_HEAD(&ctx->head, ent, next);
629 : : } else {
630 [ + + ]: 5 : LIST_FOREACH(next_ent, &ctx->head, next)
631 : : prev_ent = next_ent;
632 : :
633 [ - + ]: 2 : LIST_INSERT_AFTER(prev_ent, ent, next);
634 : : }
635 : 69 : generate_complement_table(ctx, ent);
636 : 69 : ctx->subtuples_nb++;
637 : :
638 : 69 : return 0;
639 : : }
640 : :
641 : : RTE_EXPORT_SYMBOL(rte_thash_get_helper)
642 : : struct rte_thash_subtuple_helper *
643 : 72 : rte_thash_get_helper(struct rte_thash_ctx *ctx, const char *name)
644 : : {
645 : : struct rte_thash_subtuple_helper *ent;
646 : :
647 [ + + ]: 72 : if ((ctx == NULL) || (name == NULL))
648 : : return NULL;
649 : :
650 [ + - ]: 76 : LIST_FOREACH(ent, &ctx->head, next) {
651 [ + + ]: 76 : if (strncmp(name, ent->name, sizeof(ent->name)) == 0)
652 : 70 : return ent;
653 : : }
654 : :
655 : : return NULL;
656 : : }
657 : :
658 : : RTE_EXPORT_SYMBOL(rte_thash_get_complement)
659 : : uint32_t
660 : 825 : rte_thash_get_complement(struct rte_thash_subtuple_helper *h,
661 : : uint32_t hash, uint32_t desired_hash)
662 : : {
663 : 825 : return h->compl_table[(hash ^ desired_hash) & h->lsb_msk];
664 : : }
665 : :
666 : : RTE_EXPORT_SYMBOL(rte_thash_get_key)
667 : : const uint8_t *
668 : 126 : rte_thash_get_key(struct rte_thash_ctx *ctx)
669 : : {
670 : 126 : return ctx->hash_key;
671 : : }
672 : :
673 : : RTE_EXPORT_SYMBOL(rte_thash_get_gfni_matrices)
674 : : const uint64_t *
675 : 0 : rte_thash_get_gfni_matrices(struct rte_thash_ctx *ctx)
676 : : {
677 : 0 : return ctx->matrices;
678 : : }
679 : :
680 : : static inline uint8_t
681 : : read_unaligned_byte(uint8_t *ptr, unsigned int offset)
682 : : {
683 : : uint8_t ret = 0;
684 : :
685 : 101 : ret = ptr[offset / CHAR_BIT];
686 : 101 : if (offset % CHAR_BIT) {
687 : 82 : ret <<= (offset % CHAR_BIT);
688 : 82 : ret |= ptr[(offset / CHAR_BIT) + 1] >>
689 : 82 : (CHAR_BIT - (offset % CHAR_BIT));
690 : : }
691 : :
692 : : return ret;
693 : : }
694 : :
695 : : static inline uint32_t
696 : 65 : read_unaligned_bits(uint8_t *ptr, int len, int offset)
697 : : {
698 : : uint32_t ret = 0;
699 : : int shift;
700 : :
701 : 65 : len = RTE_MAX(len, 0);
702 : 65 : len = RTE_MIN(len, (int)(sizeof(uint32_t) * CHAR_BIT));
703 : :
704 [ + + ]: 166 : while (len > 0) {
705 : 101 : ret <<= CHAR_BIT;
706 : :
707 [ + + ]: 101 : ret |= read_unaligned_byte(ptr, offset);
708 : 101 : offset += CHAR_BIT;
709 : 101 : len -= CHAR_BIT;
710 : : }
711 : :
712 [ + + ]: 65 : shift = (len == 0) ? 0 :
713 : 51 : (CHAR_BIT - ((len + CHAR_BIT) % CHAR_BIT));
714 : 65 : return ret >> shift;
715 : : }
716 : :
717 : : /* returns mask for len bits with given offset inside byte */
718 : : static inline uint8_t
719 : : get_bits_mask(unsigned int len, unsigned int offset)
720 : : {
721 : : unsigned int last_bit;
722 : :
723 : 101 : offset %= CHAR_BIT;
724 : : /* last bit within byte */
725 : 171 : last_bit = RTE_MIN((unsigned int)CHAR_BIT, offset + len);
726 : :
727 : 101 : return ((1 << (CHAR_BIT - offset)) - 1) ^
728 : 171 : ((1 << (CHAR_BIT - last_bit)) - 1);
729 : : }
730 : :
731 : : static inline void
732 : 101 : write_unaligned_byte(uint8_t *ptr, unsigned int len,
733 : : unsigned int offset, uint8_t val)
734 : : {
735 : : uint8_t tmp;
736 : :
737 : 101 : tmp = ptr[offset / CHAR_BIT];
738 : 101 : tmp &= ~get_bits_mask(len, offset);
739 : 101 : tmp |= ((val << (CHAR_BIT - len)) >> (offset % CHAR_BIT));
740 : 101 : ptr[offset / CHAR_BIT] = tmp;
741 [ + + ]: 101 : if (((offset + len) / CHAR_BIT) != (offset / CHAR_BIT)) {
742 : 70 : int rest_len = (offset + len) % CHAR_BIT;
743 : 70 : tmp = ptr[(offset + len) / CHAR_BIT];
744 : 70 : tmp &= ~get_bits_mask(rest_len, 0);
745 : 70 : tmp |= val << (CHAR_BIT - rest_len);
746 : 70 : ptr[(offset + len) / CHAR_BIT] = tmp;
747 : : }
748 : 101 : }
749 : :
750 : : static inline void
751 : 65 : write_unaligned_bits(uint8_t *ptr, int len, int offset, uint32_t val)
752 : : {
753 : : uint8_t tmp;
754 : : unsigned int part_len;
755 : :
756 : 65 : len = RTE_MAX(len, 0);
757 : 65 : len = RTE_MIN(len, (int)(sizeof(uint32_t) * CHAR_BIT));
758 : :
759 [ + + ]: 166 : while (len > 0) {
760 : 101 : part_len = RTE_MIN(CHAR_BIT, len);
761 : 101 : tmp = (uint8_t)val & ((1 << part_len) - 1);
762 : 101 : write_unaligned_byte(ptr, part_len,
763 : 101 : offset + len - part_len, tmp);
764 : 101 : len -= CHAR_BIT;
765 : 101 : val >>= CHAR_BIT;
766 : : }
767 : 65 : }
768 : :
769 : : RTE_EXPORT_SYMBOL(rte_thash_adjust_tuple)
770 : : int
771 : 63 : rte_thash_adjust_tuple(struct rte_thash_ctx *ctx,
772 : : struct rte_thash_subtuple_helper *h,
773 : : uint8_t *tuple, unsigned int tuple_len,
774 : : uint32_t desired_value, unsigned int attempts,
775 : : rte_thash_check_tuple_t fn, void *userdata)
776 : : {
777 : : uint32_t tmp_tuple[RTE_THASH_TUPLE_LEN_MAX];
778 : : unsigned int i, j, ret = 0;
779 : : uint32_t hash, adj_bits;
780 : : const uint8_t *hash_key;
781 : : uint32_t tmp;
782 : : int offset;
783 : : int tmp_len;
784 : :
785 [ + - + - ]: 63 : if ((ctx == NULL) || (h == NULL) || (tuple == NULL) ||
786 [ + - + - ]: 63 : (tuple_len % sizeof(uint32_t) != 0) || (attempts <= 0))
787 : : return -EINVAL;
788 : :
789 : 63 : hash_key = rte_thash_get_key(ctx);
790 : :
791 : 63 : attempts = RTE_MIN(attempts, 1U << (h->tuple_len - ctx->reta_sz_log));
792 : :
793 [ + + ]: 65 : for (i = 0; i < attempts; i++) {
794 [ - + ]: 64 : if (ctx->matrices != NULL)
795 : 0 : hash = rte_thash_gfni(ctx->matrices, tuple, tuple_len);
796 : : else {
797 [ + + ]: 256 : for (j = 0; j < (tuple_len / 4); j++)
798 : 192 : tmp_tuple[j] =
799 [ - + ]: 192 : rte_be_to_cpu_32(
800 : : *(uint32_t *)&tuple[j * 4]);
801 : :
802 : 64 : hash = rte_softrss(tmp_tuple, tuple_len / 4, hash_key);
803 : : }
804 : :
805 : 64 : adj_bits = rte_thash_get_complement(h, hash, desired_value);
806 : :
807 : : /*
808 : : * Hint: LSB of adj_bits corresponds to
809 : : * offset + len bit of the subtuple
810 : : */
811 : 64 : offset = h->tuple_offset + h->tuple_len - ctx->reta_sz_log;
812 : 64 : tmp = read_unaligned_bits(tuple, ctx->reta_sz_log, offset);
813 : 64 : tmp ^= adj_bits;
814 : 64 : write_unaligned_bits(tuple, ctx->reta_sz_log, offset, tmp);
815 : :
816 [ + + ]: 64 : if (fn != NULL) {
817 [ + + ]: 3 : ret = (fn(userdata, tuple)) ? 0 : -EEXIST;
818 : : if (ret == 0)
819 : : return 0;
820 [ + + ]: 2 : else if (i < (attempts - 1)) {
821 : : /* increment subtuple part by 1 */
822 : 1 : tmp_len = RTE_MIN(sizeof(uint32_t) * CHAR_BIT,
823 : : h->tuple_len - ctx->reta_sz_log);
824 : 1 : offset -= tmp_len;
825 : 1 : tmp = read_unaligned_bits(tuple, tmp_len,
826 : : offset);
827 : 1 : tmp++;
828 : 1 : tmp &= (1 << tmp_len) - 1;
829 : 1 : write_unaligned_bits(tuple, tmp_len, offset,
830 : : tmp);
831 : : }
832 : : } else
833 : : return 0;
834 : : }
835 : :
836 : 1 : return ret;
837 : : }
838 : :
839 : : RTE_EXPORT_EXPERIMENTAL_SYMBOL(rte_thash_gen_key, 24.11)
840 : : int
841 : 10 : rte_thash_gen_key(uint8_t *key, size_t key_len, size_t reta_sz_log,
842 : : uint32_t entropy_start, size_t entropy_sz)
843 : : {
844 : : size_t i, end, start;
845 : :
846 : : /* define lfsr sequence range*/
847 : 10 : end = entropy_start + entropy_sz + TOEPLITZ_HASH_LEN - 1;
848 : 10 : start = end - (entropy_sz + reta_sz_log - 1);
849 : :
850 [ + - + - ]: 10 : if ((key == NULL) || (key_len * CHAR_BIT < entropy_start + entropy_sz) ||
851 [ + - ]: 10 : (entropy_sz < reta_sz_log) || (reta_sz_log > TOEPLITZ_HASH_LEN))
852 : : return -EINVAL;
853 : :
854 : 10 : struct thash_lfsr *lfsr = alloc_lfsr(reta_sz_log);
855 [ + - ]: 10 : if (lfsr == NULL)
856 : : return -ENOMEM;
857 : :
858 [ + + ]: 220 : for (i = start; i < end; i++)
859 : 210 : set_bit(key, get_bit_lfsr(lfsr), i);
860 : :
861 : : free_lfsr(lfsr);
862 : :
863 : : return 0;
864 : : }
|
