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