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