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