lib/hash/rte_thash.c

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