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 }