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