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