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 } 764