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