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