1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2010-2015 Intel Corporation 3 */ 4 5 #include <stdio.h> 6 #include <inttypes.h> 7 8 #include <rte_lcore.h> 9 #include <rte_cycles.h> 10 #include <rte_malloc.h> 11 #include <rte_hash.h> 12 #include <rte_hash_crc.h> 13 #include <rte_jhash.h> 14 #include <rte_fbk_hash.h> 15 #include <rte_random.h> 16 #include <rte_string_fns.h> 17 18 #include "test.h" 19 20 #define MAX_ENTRIES (1 << 19) 21 #define KEYS_TO_ADD (MAX_ENTRIES) 22 #define ADD_PERCENT 0.75 /* 75% table utilization */ 23 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */ 24 /* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */ 25 #define BUCKET_SIZE 8 26 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) 27 #define MAX_KEYSIZE 64 28 #define NUM_KEYSIZES 10 29 #define NUM_SHUFFLES 10 30 #define BURST_SIZE 16 31 32 enum operations { 33 ADD = 0, 34 LOOKUP, 35 LOOKUP_MULTI, 36 DELETE, 37 NUM_OPERATIONS 38 }; 39 40 static uint32_t hashtest_key_lens[] = { 41 /* standard key sizes */ 42 4, 8, 16, 32, 48, 64, 43 /* IPv4 SRC + DST + protocol, unpadded */ 44 9, 45 /* IPv4 5-tuple, unpadded */ 46 13, 47 /* IPv6 5-tuple, unpadded */ 48 37, 49 /* IPv6 5-tuple, padded to 8-byte boundary */ 50 40 51 }; 52 53 struct rte_hash *h[NUM_KEYSIZES]; 54 55 /* Array that stores if a slot is full */ 56 uint8_t slot_taken[MAX_ENTRIES]; 57 58 /* Array to store number of cycles per operation */ 59 uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2]; 60 61 /* Array to store all input keys */ 62 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; 63 64 /* Array to store the precomputed hash for 'keys' */ 65 hash_sig_t signatures[KEYS_TO_ADD]; 66 67 /* Array to store how many busy entries have each bucket */ 68 uint8_t buckets[NUM_BUCKETS]; 69 70 /* Array to store the positions where keys are added */ 71 int32_t positions[KEYS_TO_ADD]; 72 73 /* Parameters used for hash table in unit test functions. */ 74 static struct rte_hash_parameters ut_params = { 75 .entries = MAX_ENTRIES, 76 .hash_func = rte_jhash, 77 .hash_func_init_val = 0, 78 }; 79 80 static int 81 create_table(unsigned int with_data, unsigned int table_index, 82 unsigned int with_locks, unsigned int ext) 83 { 84 char name[RTE_HASH_NAMESIZE]; 85 86 if (with_data) 87 /* Table will store 8-byte data */ 88 snprintf(name, sizeof(name), "test_hash%u_data", 89 hashtest_key_lens[table_index]); 90 else 91 snprintf(name, sizeof(name), "test_hash%u", 92 hashtest_key_lens[table_index]); 93 94 95 if (with_locks) 96 ut_params.extra_flag = 97 RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT 98 | RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY; 99 else 100 ut_params.extra_flag = 0; 101 102 if (ext) 103 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE; 104 105 ut_params.name = name; 106 ut_params.key_len = hashtest_key_lens[table_index]; 107 ut_params.socket_id = rte_socket_id(); 108 h[table_index] = rte_hash_find_existing(name); 109 if (h[table_index] != NULL) 110 /* 111 * If table was already created, free it to create it again, 112 * so we force it is empty 113 */ 114 rte_hash_free(h[table_index]); 115 h[table_index] = rte_hash_create(&ut_params); 116 if (h[table_index] == NULL) { 117 printf("Error creating table\n"); 118 return -1; 119 } 120 return 0; 121 122 } 123 124 /* Shuffle the keys that have been added, so lookups will be totally random */ 125 static void 126 shuffle_input_keys(unsigned int table_index, unsigned int ext) 127 { 128 unsigned i; 129 uint32_t swap_idx; 130 uint8_t temp_key[MAX_KEYSIZE]; 131 hash_sig_t temp_signature; 132 int32_t temp_position; 133 unsigned int keys_to_add; 134 135 if (!ext) 136 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 137 else 138 keys_to_add = KEYS_TO_ADD; 139 140 for (i = keys_to_add - 1; i > 0; i--) { 141 swap_idx = rte_rand() % i; 142 143 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]); 144 temp_signature = signatures[i]; 145 temp_position = positions[i]; 146 147 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]); 148 signatures[i] = signatures[swap_idx]; 149 positions[i] = positions[swap_idx]; 150 151 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]); 152 signatures[swap_idx] = temp_signature; 153 positions[swap_idx] = temp_position; 154 } 155 } 156 157 /* 158 * Looks for random keys which 159 * ALL can fit in hash table (no errors) 160 */ 161 static int 162 get_input_keys(unsigned int with_pushes, unsigned int table_index, 163 unsigned int ext) 164 { 165 unsigned i, j; 166 unsigned bucket_idx, incr, success = 1; 167 uint8_t k = 0; 168 int32_t ret; 169 const uint32_t bucket_bitmask = NUM_BUCKETS - 1; 170 unsigned int keys_to_add; 171 172 if (!ext) 173 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 174 else 175 keys_to_add = KEYS_TO_ADD; 176 /* Reset all arrays */ 177 for (i = 0; i < MAX_ENTRIES; i++) 178 slot_taken[i] = 0; 179 180 for (i = 0; i < NUM_BUCKETS; i++) 181 buckets[i] = 0; 182 183 for (j = 0; j < hashtest_key_lens[table_index]; j++) 184 keys[0][j] = 0; 185 186 /* 187 * Add only entries that are not duplicated and that fits in the table 188 * (cannot store more than BUCKET_SIZE entries in a bucket). 189 * Regardless a key has been added correctly or not (success), 190 * the next one to try will be increased by 1. 191 */ 192 for (i = 0; i < keys_to_add;) { 193 incr = 0; 194 if (i != 0) { 195 keys[i][0] = ++k; 196 /* Overflow, need to increment the next byte */ 197 if (keys[i][0] == 0) 198 incr = 1; 199 for (j = 1; j < hashtest_key_lens[table_index]; j++) { 200 /* Do not increase next byte */ 201 if (incr == 0) 202 if (success == 1) 203 keys[i][j] = keys[i - 1][j]; 204 else 205 keys[i][j] = keys[i][j]; 206 /* Increase next byte by one */ 207 else { 208 if (success == 1) 209 keys[i][j] = keys[i-1][j] + 1; 210 else 211 keys[i][j] = keys[i][j] + 1; 212 if (keys[i][j] == 0) 213 incr = 1; 214 else 215 incr = 0; 216 } 217 } 218 } 219 success = 0; 220 signatures[i] = rte_hash_hash(h[table_index], keys[i]); 221 bucket_idx = signatures[i] & bucket_bitmask; 222 /* 223 * If we are not inserting keys in secondary location, 224 * when bucket is full, do not try to insert the key 225 */ 226 if (with_pushes == 0) 227 if (buckets[bucket_idx] == BUCKET_SIZE) 228 continue; 229 230 /* If key can be added, leave in successful key arrays "keys" */ 231 ret = rte_hash_add_key_with_hash(h[table_index], keys[i], 232 signatures[i]); 233 if (ret >= 0) { 234 /* If key is already added, ignore the entry and do not store */ 235 if (slot_taken[ret]) 236 continue; 237 else { 238 /* Store the returned position and mark slot as taken */ 239 slot_taken[ret] = 1; 240 positions[i] = ret; 241 buckets[bucket_idx]++; 242 success = 1; 243 i++; 244 } 245 } 246 } 247 248 /* Reset the table, so we can measure the time to add all the entries */ 249 rte_hash_free(h[table_index]); 250 h[table_index] = rte_hash_create(&ut_params); 251 252 return 0; 253 } 254 255 static int 256 timed_adds(unsigned int with_hash, unsigned int with_data, 257 unsigned int table_index, unsigned int ext) 258 { 259 unsigned i; 260 const uint64_t start_tsc = rte_rdtsc(); 261 void *data; 262 int32_t ret; 263 unsigned int keys_to_add; 264 if (!ext) 265 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 266 else 267 keys_to_add = KEYS_TO_ADD; 268 269 for (i = 0; i < keys_to_add; i++) { 270 data = (void *) ((uintptr_t) signatures[i]); 271 if (with_hash && with_data) { 272 ret = rte_hash_add_key_with_hash_data(h[table_index], 273 (const void *) keys[i], 274 signatures[i], data); 275 if (ret < 0) { 276 printf("H+D: Failed to add key number %u\n", i); 277 return -1; 278 } 279 } else if (with_hash && !with_data) { 280 ret = rte_hash_add_key_with_hash(h[table_index], 281 (const void *) keys[i], 282 signatures[i]); 283 if (ret >= 0) 284 positions[i] = ret; 285 else { 286 printf("H: Failed to add key number %u\n", i); 287 return -1; 288 } 289 } else if (!with_hash && with_data) { 290 ret = rte_hash_add_key_data(h[table_index], 291 (const void *) keys[i], 292 data); 293 if (ret < 0) { 294 printf("D: Failed to add key number %u\n", i); 295 return -1; 296 } 297 } else { 298 ret = rte_hash_add_key(h[table_index], keys[i]); 299 if (ret >= 0) 300 positions[i] = ret; 301 else { 302 printf("Failed to add key number %u\n", i); 303 return -1; 304 } 305 } 306 } 307 308 const uint64_t end_tsc = rte_rdtsc(); 309 const uint64_t time_taken = end_tsc - start_tsc; 310 311 cycles[table_index][ADD][with_hash][with_data] = time_taken/keys_to_add; 312 313 return 0; 314 } 315 316 static int 317 timed_lookups(unsigned int with_hash, unsigned int with_data, 318 unsigned int table_index, unsigned int ext) 319 { 320 unsigned i, j; 321 const uint64_t start_tsc = rte_rdtsc(); 322 void *ret_data; 323 void *expected_data; 324 int32_t ret; 325 unsigned int keys_to_add, num_lookups; 326 327 if (!ext) { 328 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 329 num_lookups = NUM_LOOKUPS * ADD_PERCENT; 330 } else { 331 keys_to_add = KEYS_TO_ADD; 332 num_lookups = NUM_LOOKUPS; 333 } 334 for (i = 0; i < num_lookups / keys_to_add; i++) { 335 for (j = 0; j < keys_to_add; j++) { 336 if (with_hash && with_data) { 337 ret = rte_hash_lookup_with_hash_data(h[table_index], 338 (const void *) keys[j], 339 signatures[j], &ret_data); 340 if (ret < 0) { 341 printf("Key number %u was not found\n", j); 342 return -1; 343 } 344 expected_data = (void *) ((uintptr_t) signatures[j]); 345 if (ret_data != expected_data) { 346 printf("Data returned for key number %u is %p," 347 " but should be %p\n", j, ret_data, 348 expected_data); 349 return -1; 350 } 351 } else if (with_hash && !with_data) { 352 ret = rte_hash_lookup_with_hash(h[table_index], 353 (const void *) keys[j], 354 signatures[j]); 355 if (ret < 0 || ret != positions[j]) { 356 printf("Key looked up in %d, should be in %d\n", 357 ret, positions[j]); 358 return -1; 359 } 360 } else if (!with_hash && with_data) { 361 ret = rte_hash_lookup_data(h[table_index], 362 (const void *) keys[j], &ret_data); 363 if (ret < 0) { 364 printf("Key number %u was not found\n", j); 365 return -1; 366 } 367 expected_data = (void *) ((uintptr_t) signatures[j]); 368 if (ret_data != expected_data) { 369 printf("Data returned for key number %u is %p," 370 " but should be %p\n", j, ret_data, 371 expected_data); 372 return -1; 373 } 374 } else { 375 ret = rte_hash_lookup(h[table_index], keys[j]); 376 if (ret < 0 || ret != positions[j]) { 377 printf("Key looked up in %d, should be in %d\n", 378 ret, positions[j]); 379 return -1; 380 } 381 } 382 } 383 } 384 385 const uint64_t end_tsc = rte_rdtsc(); 386 const uint64_t time_taken = end_tsc - start_tsc; 387 388 cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/num_lookups; 389 390 return 0; 391 } 392 393 static int 394 timed_lookups_multi(unsigned int with_data, unsigned int table_index, 395 unsigned int ext) 396 { 397 unsigned i, j, k; 398 int32_t positions_burst[BURST_SIZE]; 399 const void *keys_burst[BURST_SIZE]; 400 void *expected_data[BURST_SIZE]; 401 void *ret_data[BURST_SIZE]; 402 uint64_t hit_mask; 403 int ret; 404 unsigned int keys_to_add, num_lookups; 405 406 if (!ext) { 407 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 408 num_lookups = NUM_LOOKUPS * ADD_PERCENT; 409 } else { 410 keys_to_add = KEYS_TO_ADD; 411 num_lookups = NUM_LOOKUPS; 412 } 413 414 const uint64_t start_tsc = rte_rdtsc(); 415 416 for (i = 0; i < num_lookups/keys_to_add; i++) { 417 for (j = 0; j < keys_to_add/BURST_SIZE; j++) { 418 for (k = 0; k < BURST_SIZE; k++) 419 keys_burst[k] = keys[j * BURST_SIZE + k]; 420 if (with_data) { 421 ret = rte_hash_lookup_bulk_data(h[table_index], 422 (const void **) keys_burst, 423 BURST_SIZE, 424 &hit_mask, 425 ret_data); 426 if (ret != BURST_SIZE) { 427 printf("Expect to find %u keys," 428 " but found %d\n", BURST_SIZE, ret); 429 return -1; 430 } 431 for (k = 0; k < BURST_SIZE; k++) { 432 if ((hit_mask & (1ULL << k)) == 0) { 433 printf("Key number %u not found\n", 434 j * BURST_SIZE + k); 435 return -1; 436 } 437 expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]); 438 if (ret_data[k] != expected_data[k]) { 439 printf("Data returned for key number %u is %p," 440 " but should be %p\n", j * BURST_SIZE + k, 441 ret_data[k], expected_data[k]); 442 return -1; 443 } 444 } 445 } else { 446 rte_hash_lookup_bulk(h[table_index], 447 (const void **) keys_burst, 448 BURST_SIZE, 449 positions_burst); 450 for (k = 0; k < BURST_SIZE; k++) { 451 if (positions_burst[k] != positions[j * BURST_SIZE + k]) { 452 printf("Key looked up in %d, should be in %d\n", 453 positions_burst[k], 454 positions[j * BURST_SIZE + k]); 455 return -1; 456 } 457 } 458 } 459 } 460 } 461 462 const uint64_t end_tsc = rte_rdtsc(); 463 const uint64_t time_taken = end_tsc - start_tsc; 464 465 cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/num_lookups; 466 467 return 0; 468 } 469 470 static int 471 timed_deletes(unsigned int with_hash, unsigned int with_data, 472 unsigned int table_index, unsigned int ext) 473 { 474 unsigned i; 475 const uint64_t start_tsc = rte_rdtsc(); 476 int32_t ret; 477 unsigned int keys_to_add; 478 if (!ext) 479 keys_to_add = KEYS_TO_ADD * ADD_PERCENT; 480 else 481 keys_to_add = KEYS_TO_ADD; 482 483 for (i = 0; i < keys_to_add; i++) { 484 /* There are no delete functions with data, so just call two functions */ 485 if (with_hash) 486 ret = rte_hash_del_key_with_hash(h[table_index], 487 (const void *) keys[i], 488 signatures[i]); 489 else 490 ret = rte_hash_del_key(h[table_index], 491 (const void *) keys[i]); 492 if (ret >= 0) 493 positions[i] = ret; 494 else { 495 printf("Failed to delete key number %u\n", i); 496 return -1; 497 } 498 } 499 500 const uint64_t end_tsc = rte_rdtsc(); 501 const uint64_t time_taken = end_tsc - start_tsc; 502 503 cycles[table_index][DELETE][with_hash][with_data] = time_taken/keys_to_add; 504 505 return 0; 506 } 507 508 static void 509 free_table(unsigned table_index) 510 { 511 rte_hash_free(h[table_index]); 512 } 513 514 static void 515 reset_table(unsigned table_index) 516 { 517 rte_hash_reset(h[table_index]); 518 } 519 520 static int 521 run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks, 522 unsigned int ext) 523 { 524 unsigned i, j, with_data, with_hash; 525 526 printf("Measuring performance, please wait"); 527 fflush(stdout); 528 529 for (with_data = 0; with_data <= 1; with_data++) { 530 for (i = 0; i < NUM_KEYSIZES; i++) { 531 if (create_table(with_data, i, with_locks, ext) < 0) 532 return -1; 533 534 if (get_input_keys(with_pushes, i, ext) < 0) 535 return -1; 536 for (with_hash = 0; with_hash <= 1; with_hash++) { 537 if (timed_adds(with_hash, with_data, i, ext) < 0) 538 return -1; 539 540 for (j = 0; j < NUM_SHUFFLES; j++) 541 shuffle_input_keys(i, ext); 542 543 if (timed_lookups(with_hash, with_data, i, ext) < 0) 544 return -1; 545 546 if (timed_lookups_multi(with_data, i, ext) < 0) 547 return -1; 548 549 if (timed_deletes(with_hash, with_data, i, ext) < 0) 550 return -1; 551 552 /* Print a dot to show progress on operations */ 553 printf("."); 554 fflush(stdout); 555 556 reset_table(i); 557 } 558 free_table(i); 559 } 560 } 561 562 printf("\nResults (in CPU cycles/operation)\n"); 563 printf("-----------------------------------\n"); 564 for (with_data = 0; with_data <= 1; with_data++) { 565 if (with_data) 566 printf("\n Operations with 8-byte data\n"); 567 else 568 printf("\n Operations without data\n"); 569 for (with_hash = 0; with_hash <= 1; with_hash++) { 570 if (with_hash) 571 printf("\nWith pre-computed hash values\n"); 572 else 573 printf("\nWithout pre-computed hash values\n"); 574 575 printf("\n%-18s%-18s%-18s%-18s%-18s\n", 576 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); 577 for (i = 0; i < NUM_KEYSIZES; i++) { 578 printf("%-18d", hashtest_key_lens[i]); 579 for (j = 0; j < NUM_OPERATIONS; j++) 580 printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]); 581 printf("\n"); 582 } 583 } 584 } 585 return 0; 586 } 587 588 /* Control operation of performance testing of fbk hash. */ 589 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */ 590 #define TEST_SIZE 1000000 /* How many operations to time. */ 591 #define TEST_ITERATIONS 30 /* How many measurements to take. */ 592 #define ENTRIES (1 << 15) /* How many entries. */ 593 594 static int 595 fbk_hash_perf_test(void) 596 { 597 struct rte_fbk_hash_params params = { 598 .name = "fbk_hash_test", 599 .entries = ENTRIES, 600 .entries_per_bucket = 4, 601 .socket_id = rte_socket_id(), 602 }; 603 struct rte_fbk_hash_table *handle = NULL; 604 uint32_t *keys = NULL; 605 unsigned indexes[TEST_SIZE]; 606 uint64_t lookup_time = 0; 607 unsigned added = 0; 608 unsigned value = 0; 609 uint32_t key; 610 uint16_t val; 611 unsigned i, j; 612 613 handle = rte_fbk_hash_create(¶ms); 614 if (handle == NULL) { 615 printf("Error creating table\n"); 616 return -1; 617 } 618 619 keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0); 620 if (keys == NULL) { 621 printf("fbk hash: memory allocation for key store failed\n"); 622 return -1; 623 } 624 625 /* Generate random keys and values. */ 626 for (i = 0; i < ENTRIES; i++) { 627 key = (uint32_t)rte_rand(); 628 key = ((uint64_t)key << 32) | (uint64_t)rte_rand(); 629 val = (uint16_t)rte_rand(); 630 631 if (rte_fbk_hash_add_key(handle, key, val) == 0) { 632 keys[added] = key; 633 added++; 634 } 635 if (added > (LOAD_FACTOR * ENTRIES)) 636 break; 637 } 638 639 for (i = 0; i < TEST_ITERATIONS; i++) { 640 uint64_t begin; 641 uint64_t end; 642 643 /* Generate random indexes into keys[] array. */ 644 for (j = 0; j < TEST_SIZE; j++) 645 indexes[j] = rte_rand() % added; 646 647 begin = rte_rdtsc(); 648 /* Do lookups */ 649 for (j = 0; j < TEST_SIZE; j++) 650 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]); 651 652 end = rte_rdtsc(); 653 lookup_time += (double)(end - begin); 654 } 655 656 printf("\n\n *** FBK Hash function performance test results ***\n"); 657 /* 658 * The use of the 'value' variable ensures that the hash lookup is not 659 * being optimised out by the compiler. 660 */ 661 if (value != 0) 662 printf("Number of ticks per lookup = %g\n", 663 (double)lookup_time / 664 ((double)TEST_ITERATIONS * (double)TEST_SIZE)); 665 666 rte_fbk_hash_free(handle); 667 668 return 0; 669 } 670 671 static int 672 test_hash_perf(void) 673 { 674 unsigned int with_pushes, with_locks; 675 for (with_locks = 0; with_locks <= 1; with_locks++) { 676 if (with_locks) 677 printf("\nWith locks in the code\n"); 678 else 679 printf("\nWithout locks in the code\n"); 680 for (with_pushes = 0; with_pushes <= 1; with_pushes++) { 681 if (with_pushes == 0) 682 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n"); 683 else 684 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n"); 685 if (run_all_tbl_perf_tests(with_pushes, with_locks, 0) < 0) 686 return -1; 687 } 688 } 689 690 printf("\n EXTENDABLE BUCKETS PERFORMANCE\n"); 691 692 if (run_all_tbl_perf_tests(1, 0, 1) < 0) 693 return -1; 694 695 if (fbk_hash_perf_test() < 0) 696 return -1; 697 698 return 0; 699 } 700 701 REGISTER_TEST_COMMAND(hash_perf_autotest, test_hash_perf); 702