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