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