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