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