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