1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2017 Intel Corporation 3 */ 4 5 #include "test.h" 6 7 #include <stdio.h> 8 #include <inttypes.h> 9 10 #include <rte_lcore.h> 11 #include <rte_cycles.h> 12 #include <rte_malloc.h> 13 #include <rte_random.h> 14 #include <rte_memcpy.h> 15 #include <rte_thash.h> 16 17 #ifdef RTE_EXEC_ENV_WINDOWS 18 static int 19 test_member_perf(void) 20 { 21 printf("member_perf not supported on Windows, skipping test\n"); 22 return TEST_SKIPPED; 23 } 24 25 #else 26 27 #include <rte_member.h> 28 29 #define NUM_KEYSIZES 10 30 #define NUM_SHUFFLES 10 31 #define MAX_KEYSIZE 64 32 #define MAX_ENTRIES (1 << 19) 33 #define KEYS_TO_ADD (MAX_ENTRIES * 75 / 100) /* 75% table utilization */ 34 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */ 35 #define VBF_SET_CNT 16 36 #define BURST_SIZE 64 37 #define VBF_FALSE_RATE 0.03 38 39 static unsigned int test_socket_id; 40 41 enum sstype { 42 HT = 0, 43 CACHE, 44 VBF, 45 NUM_TYPE 46 }; 47 48 enum operations { 49 ADD = 0, 50 LOOKUP, 51 LOOKUP_BULK, 52 LOOKUP_MULTI, 53 LOOKUP_MULTI_BULK, 54 DELETE, 55 LOOKUP_MISS, 56 NUM_OPERATIONS 57 }; 58 59 struct member_perf_params { 60 struct rte_member_setsum *setsum[NUM_TYPE]; 61 uint32_t key_size; 62 unsigned int cycle; 63 }; 64 65 static uint32_t hashtest_key_lens[] = { 66 /* standard key sizes */ 67 4, 8, 16, 32, 48, 64, 68 /* IPv4 SRC + DST + protocol, unpadded */ 69 9, 70 /* IPv4 5-tuple, unpadded */ 71 13, 72 /* IPv6 5-tuple, unpadded */ 73 37, 74 /* IPv6 5-tuple, padded to 8-byte boundary */ 75 40 76 }; 77 78 /* Array to store number of cycles per operation */ 79 static uint64_t cycles[NUM_TYPE][NUM_KEYSIZES][NUM_OPERATIONS]; 80 static uint64_t false_data[NUM_TYPE][NUM_KEYSIZES]; 81 static uint64_t false_data_bulk[NUM_TYPE][NUM_KEYSIZES]; 82 static uint64_t false_data_multi[NUM_TYPE][NUM_KEYSIZES]; 83 static uint64_t false_data_multi_bulk[NUM_TYPE][NUM_KEYSIZES]; 84 85 static uint64_t false_hit[NUM_TYPE][NUM_KEYSIZES]; 86 87 static member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD]; 88 89 /* Array to store all input keys */ 90 static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; 91 92 /* Shuffle the keys that have been added, so lookups will be totally random */ 93 static void 94 shuffle_input_keys(struct member_perf_params *params) 95 { 96 member_set_t temp_data; 97 unsigned int i, j; 98 uint32_t swap_idx; 99 uint8_t temp_key[MAX_KEYSIZE]; 100 101 for (i = KEYS_TO_ADD - 1; i > 0; i--) { 102 swap_idx = rte_rand() % i; 103 memcpy(temp_key, keys[i], hashtest_key_lens[params->cycle]); 104 memcpy(keys[i], keys[swap_idx], 105 hashtest_key_lens[params->cycle]); 106 memcpy(keys[swap_idx], temp_key, 107 hashtest_key_lens[params->cycle]); 108 for (j = 0; j < NUM_TYPE; j++) { 109 temp_data = data[j][i]; 110 data[j][i] = data[j][swap_idx]; 111 data[j][swap_idx] = temp_data; 112 } 113 } 114 } 115 116 static int key_compare(const void *key1, const void *key2) 117 { 118 return memcmp(key1, key2, MAX_KEYSIZE); 119 } 120 121 struct rte_member_parameters member_params = { 122 .num_keys = MAX_ENTRIES, /* Total hash table entries. */ 123 .key_len = 4, /* Length of hash key. */ 124 125 /* num_set and false_positive_rate only relevant to vBF */ 126 .num_set = VBF_SET_CNT, 127 .false_positive_rate = 0.03, 128 .prim_hash_seed = 0, 129 .sec_hash_seed = 1, 130 .socket_id = 0, /* NUMA Socket ID for memory. */ 131 }; 132 133 static int 134 setup_keys_and_data(struct member_perf_params *params, unsigned int cycle, 135 int miss) 136 { 137 unsigned int i, j; 138 int num_duplicates; 139 140 params->key_size = hashtest_key_lens[cycle]; 141 params->cycle = cycle; 142 143 /* Reset all arrays */ 144 for (i = 0; i < params->key_size; i++) 145 keys[0][i] = 0; 146 147 /* Generate a list of keys, some of which may be duplicates */ 148 for (i = 0; i < KEYS_TO_ADD; i++) { 149 for (j = 0; j < params->key_size; j++) 150 keys[i][j] = rte_rand() & 0xFF; 151 152 data[HT][i] = data[CACHE][i] = (rte_rand() & 0x7FFE) + 1; 153 data[VBF][i] = rte_rand() % VBF_SET_CNT + 1; 154 } 155 156 /* Remove duplicates from the keys array */ 157 do { 158 num_duplicates = 0; 159 160 /* Sort the list of keys to make it easier to find duplicates */ 161 qsort(keys, KEYS_TO_ADD, MAX_KEYSIZE, key_compare); 162 163 /* Sift through the list of keys and look for duplicates */ 164 int num_duplicates = 0; 165 for (i = 0; i < KEYS_TO_ADD - 1; i++) { 166 if (memcmp(keys[i], keys[i + 1], 167 params->key_size) == 0) { 168 /* This key already exists, try again */ 169 num_duplicates++; 170 for (j = 0; j < params->key_size; j++) 171 keys[i][j] = rte_rand() & 0xFF; 172 } 173 } 174 } while (num_duplicates != 0); 175 176 /* Shuffle the random values again */ 177 shuffle_input_keys(params); 178 179 /* For testing miss lookup, we insert half and lookup the other half */ 180 unsigned int entry_cnt, bf_key_cnt; 181 if (!miss) { 182 entry_cnt = MAX_ENTRIES; 183 bf_key_cnt = KEYS_TO_ADD; 184 } else { 185 entry_cnt = MAX_ENTRIES / 2; 186 bf_key_cnt = KEYS_TO_ADD / 2; 187 } 188 member_params.false_positive_rate = VBF_FALSE_RATE; 189 member_params.key_len = params->key_size; 190 member_params.socket_id = test_socket_id; 191 member_params.num_keys = entry_cnt; 192 member_params.name = "test_member_ht"; 193 member_params.is_cache = 0; 194 member_params.type = RTE_MEMBER_TYPE_HT; 195 params->setsum[HT] = rte_member_create(&member_params); 196 if (params->setsum[HT] == NULL) 197 fprintf(stderr, "ht create fail\n"); 198 199 member_params.name = "test_member_cache"; 200 member_params.is_cache = 1; 201 params->setsum[CACHE] = rte_member_create(&member_params); 202 if (params->setsum[CACHE] == NULL) 203 fprintf(stderr, "CACHE create fail\n"); 204 205 member_params.name = "test_member_vbf"; 206 member_params.type = RTE_MEMBER_TYPE_VBF; 207 member_params.num_keys = bf_key_cnt; 208 params->setsum[VBF] = rte_member_create(&member_params); 209 if (params->setsum[VBF] == NULL) 210 fprintf(stderr, "VBF create fail\n"); 211 for (i = 0; i < NUM_TYPE; i++) { 212 if (params->setsum[i] == NULL) 213 return -1; 214 } 215 216 return 0; 217 } 218 219 static int 220 timed_adds(struct member_perf_params *params, int type) 221 { 222 const uint64_t start_tsc = rte_rdtsc(); 223 unsigned int i, a; 224 int32_t ret; 225 226 for (i = 0; i < KEYS_TO_ADD; i++) { 227 ret = rte_member_add(params->setsum[type], &keys[i], 228 data[type][i]); 229 if (ret < 0) { 230 printf("Error %d in rte_member_add - key=0x", ret); 231 for (a = 0; a < params->key_size; a++) 232 printf("%02x", keys[i][a]); 233 printf(" value=%d, type: %d\n", data[type][i], type); 234 235 return -1; 236 } 237 } 238 239 const uint64_t end_tsc = rte_rdtsc(); 240 const uint64_t time_taken = end_tsc - start_tsc; 241 242 cycles[type][params->cycle][ADD] = time_taken / KEYS_TO_ADD; 243 return 0; 244 } 245 246 static int 247 timed_lookups(struct member_perf_params *params, int type) 248 { 249 unsigned int i, j; 250 251 false_data[type][params->cycle] = 0; 252 253 const uint64_t start_tsc = rte_rdtsc(); 254 member_set_t result; 255 int ret; 256 257 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { 258 for (j = 0; j < KEYS_TO_ADD; j++) { 259 ret = rte_member_lookup(params->setsum[type], &keys[j], 260 &result); 261 if (ret < 0) { 262 printf("lookup wrong internally"); 263 return -1; 264 } 265 if (type == HT && result == RTE_MEMBER_NO_MATCH) { 266 printf("HT mode shouldn't have false negative"); 267 return -1; 268 } 269 if (result != data[type][j]) 270 false_data[type][params->cycle]++; 271 } 272 } 273 274 const uint64_t end_tsc = rte_rdtsc(); 275 const uint64_t time_taken = end_tsc - start_tsc; 276 277 cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS; 278 279 return 0; 280 } 281 282 static int 283 timed_lookups_bulk(struct member_perf_params *params, int type) 284 { 285 unsigned int i, j, k; 286 member_set_t result[BURST_SIZE] = {0}; 287 const void *keys_burst[BURST_SIZE]; 288 int ret; 289 290 false_data_bulk[type][params->cycle] = 0; 291 292 const uint64_t start_tsc = rte_rdtsc(); 293 294 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { 295 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) { 296 for (k = 0; k < BURST_SIZE; k++) 297 keys_burst[k] = keys[j * BURST_SIZE + k]; 298 299 ret = rte_member_lookup_bulk(params->setsum[type], 300 keys_burst, 301 BURST_SIZE, 302 result); 303 if (ret <= 0) { 304 printf("lookup bulk has wrong return value\n"); 305 return -1; 306 } 307 for (k = 0; k < BURST_SIZE; k++) { 308 uint32_t data_idx = j * BURST_SIZE + k; 309 if (type == HT && result[k] == 310 RTE_MEMBER_NO_MATCH) { 311 printf("HT mode shouldn't have " 312 "false negative"); 313 return -1; 314 } 315 if (result[k] != data[type][data_idx]) 316 false_data_bulk[type][params->cycle]++; 317 } 318 } 319 } 320 321 const uint64_t end_tsc = rte_rdtsc(); 322 const uint64_t time_taken = end_tsc - start_tsc; 323 324 cycles[type][params->cycle][LOOKUP_BULK] = time_taken / NUM_LOOKUPS; 325 326 return 0; 327 } 328 329 static int 330 timed_lookups_multimatch(struct member_perf_params *params, int type) 331 { 332 unsigned int i, j; 333 member_set_t result[RTE_MEMBER_BUCKET_ENTRIES] = {0}; 334 int ret; 335 false_data_multi[type][params->cycle] = 0; 336 337 const uint64_t start_tsc = rte_rdtsc(); 338 339 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { 340 for (j = 0; j < KEYS_TO_ADD; j++) { 341 ret = rte_member_lookup_multi(params->setsum[type], 342 &keys[j], RTE_MEMBER_BUCKET_ENTRIES, result); 343 if (type != CACHE && ret <= 0) { 344 printf("lookup multi has wrong return value %d," 345 "type %d\n", ret, type); 346 } 347 if (type == HT && ret == 0) { 348 printf("HT mode shouldn't have false negative"); 349 return -1; 350 } 351 /* 352 * For performance test purpose, we do not iterate all 353 * results here. We assume most likely each key can only 354 * find one match which is result[0]. 355 */ 356 if (result[0] != data[type][j]) 357 false_data_multi[type][params->cycle]++; 358 } 359 } 360 361 const uint64_t end_tsc = rte_rdtsc(); 362 const uint64_t time_taken = end_tsc - start_tsc; 363 364 cycles[type][params->cycle][LOOKUP_MULTI] = time_taken / NUM_LOOKUPS; 365 366 return 0; 367 } 368 369 static int 370 timed_lookups_multimatch_bulk(struct member_perf_params *params, int type) 371 { 372 unsigned int i, j, k; 373 member_set_t result[BURST_SIZE][RTE_MEMBER_BUCKET_ENTRIES] = {{0} }; 374 const void *keys_burst[BURST_SIZE]; 375 uint32_t match_count[BURST_SIZE]; 376 int ret; 377 378 false_data_multi_bulk[type][params->cycle] = 0; 379 380 const uint64_t start_tsc = rte_rdtsc(); 381 382 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { 383 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) { 384 for (k = 0; k < BURST_SIZE; k++) 385 keys_burst[k] = keys[j * BURST_SIZE + k]; 386 387 ret = rte_member_lookup_multi_bulk( 388 params->setsum[type], 389 keys_burst, BURST_SIZE, 390 RTE_MEMBER_BUCKET_ENTRIES, match_count, 391 (member_set_t *)result); 392 if (ret < 0) { 393 printf("lookup multimatch bulk has wrong return" 394 " value\n"); 395 return -1; 396 } 397 for (k = 0; k < BURST_SIZE; k++) { 398 if (type != CACHE && match_count[k] == 0) { 399 printf("lookup multimatch bulk get " 400 "wrong match count\n"); 401 return -1; 402 } 403 if (type == HT && match_count[k] == 0) { 404 printf("HT mode shouldn't have " 405 "false negative"); 406 return -1; 407 } 408 uint32_t data_idx = j * BURST_SIZE + k; 409 if (result[k][0] != data[type][data_idx]) 410 false_data_multi_bulk[type][params->cycle]++; 411 } 412 } 413 } 414 415 const uint64_t end_tsc = rte_rdtsc(); 416 const uint64_t time_taken = end_tsc - start_tsc; 417 418 cycles[type][params->cycle][LOOKUP_MULTI_BULK] = time_taken / 419 NUM_LOOKUPS; 420 421 return 0; 422 } 423 424 static int 425 timed_deletes(struct member_perf_params *params, int type) 426 { 427 unsigned int i; 428 int32_t ret; 429 430 if (type == VBF) 431 return 0; 432 const uint64_t start_tsc = rte_rdtsc(); 433 for (i = 0; i < KEYS_TO_ADD; i++) { 434 ret = rte_member_delete(params->setsum[type], &keys[i], 435 data[type][i]); 436 if (type != CACHE && ret < 0) { 437 printf("delete error\n"); 438 return -1; 439 } 440 } 441 442 const uint64_t end_tsc = rte_rdtsc(); 443 const uint64_t time_taken = end_tsc - start_tsc; 444 445 cycles[type][params->cycle][DELETE] = time_taken / KEYS_TO_ADD; 446 447 return 0; 448 } 449 450 static int 451 timed_miss_lookup(struct member_perf_params *params, int type) 452 { 453 unsigned int i, j; 454 int ret; 455 456 false_hit[type][params->cycle] = 0; 457 458 for (i = 0; i < KEYS_TO_ADD / 2; i++) { 459 ret = rte_member_add(params->setsum[type], &keys[i], 460 data[type][i]); 461 if (ret < 0) { 462 unsigned int a; 463 printf("Error %d in rte_member_add - key=0x", ret); 464 for (a = 0; a < params->key_size; a++) 465 printf("%02x", keys[i][a]); 466 printf(" value=%d, type: %d\n", data[type][i], type); 467 468 return -1; 469 } 470 } 471 472 const uint64_t start_tsc = rte_rdtsc(); 473 member_set_t result; 474 475 for (i = 0; i < 2 * NUM_LOOKUPS / KEYS_TO_ADD; i++) { 476 for (j = KEYS_TO_ADD / 2; j < KEYS_TO_ADD; j++) { 477 ret = rte_member_lookup(params->setsum[type], &keys[j], 478 &result); 479 if (ret < 0) { 480 printf("lookup wrong internally"); 481 return -1; 482 } 483 if (result != RTE_MEMBER_NO_MATCH) 484 false_hit[type][params->cycle]++; 485 } 486 } 487 488 const uint64_t end_tsc = rte_rdtsc(); 489 const uint64_t time_taken = end_tsc - start_tsc; 490 491 cycles[type][params->cycle][LOOKUP_MISS] = time_taken / NUM_LOOKUPS; 492 493 return 0; 494 } 495 496 static void 497 perform_frees(struct member_perf_params *params) 498 { 499 int i; 500 for (i = 0; i < NUM_TYPE; i++) { 501 if (params->setsum[i] != NULL) { 502 rte_member_free(params->setsum[i]); 503 params->setsum[i] = NULL; 504 } 505 } 506 } 507 508 static int 509 exit_with_fail(const char *testname, struct member_perf_params *params, 510 unsigned int i, unsigned int j) 511 { 512 printf("<<<<<Test %s failed at keysize %d iteration %d type %d>>>>>\n", 513 testname, hashtest_key_lens[params->cycle], i, j); 514 perform_frees(params); 515 return -1; 516 } 517 518 static int 519 run_all_tbl_perf_tests(void) 520 { 521 unsigned int i, j, k; 522 struct member_perf_params params; 523 524 printf("Measuring performance, please wait\n"); 525 fflush(stdout); 526 527 test_socket_id = rte_socket_id(); 528 529 for (i = 0; i < NUM_KEYSIZES; i++) { 530 if (setup_keys_and_data(¶ms, i, 0) < 0) { 531 printf("Could not create keys/data/table\n"); 532 return -1; 533 } 534 for (j = 0; j < NUM_TYPE; j++) { 535 536 if (timed_adds(¶ms, j) < 0) 537 return exit_with_fail("timed_adds", ¶ms, 538 i, j); 539 540 for (k = 0; k < NUM_SHUFFLES; k++) 541 shuffle_input_keys(¶ms); 542 543 if (timed_lookups(¶ms, j) < 0) 544 return exit_with_fail("timed_lookups", ¶ms, 545 i, j); 546 547 if (timed_lookups_bulk(¶ms, j) < 0) 548 return exit_with_fail("timed_lookups_bulk", 549 ¶ms, i, j); 550 551 if (timed_lookups_multimatch(¶ms, j) < 0) 552 return exit_with_fail("timed_lookups_multi", 553 ¶ms, i, j); 554 555 if (timed_lookups_multimatch_bulk(¶ms, j) < 0) 556 return exit_with_fail("timed_lookups_multi_bulk", 557 ¶ms, i, j); 558 559 if (timed_deletes(¶ms, j) < 0) 560 return exit_with_fail("timed_deletes", ¶ms, 561 i, j); 562 563 /* Print a dot to show progress on operations */ 564 } 565 printf("."); 566 fflush(stdout); 567 568 perform_frees(¶ms); 569 } 570 571 /* Test false positive rate using un-inserted keys */ 572 for (i = 0; i < NUM_KEYSIZES; i++) { 573 if (setup_keys_and_data(¶ms, i, 1) < 0) { 574 printf("Could not create keys/data/table\n"); 575 return -1; 576 } 577 for (j = 0; j < NUM_TYPE; j++) { 578 if (timed_miss_lookup(¶ms, j) < 0) 579 return exit_with_fail("timed_miss_lookup", 580 ¶ms, i, j); 581 } 582 perform_frees(¶ms); 583 } 584 585 printf("\nResults (in CPU cycles/operation)\n"); 586 printf("-----------------------------------\n"); 587 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n", 588 "Keysize", "type", "Add", "Lookup", "Lookup_bulk", 589 "lookup_multi", "lookup_multi_bulk", "Delete", 590 "miss_lookup"); 591 for (i = 0; i < NUM_KEYSIZES; i++) { 592 for (j = 0; j < NUM_TYPE; j++) { 593 printf("%-18d", hashtest_key_lens[i]); 594 printf("%-18d", j); 595 for (k = 0; k < NUM_OPERATIONS; k++) 596 printf("%-18"PRIu64, cycles[j][i][k]); 597 printf("\n"); 598 } 599 } 600 601 printf("\nFalse results rate (and false positive rate)\n"); 602 printf("-----------------------------------\n"); 603 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n", 604 "Keysize", "type", "fr_single", "fr_bulk", "fr_multi", 605 "fr_multi_bulk", "false_positive_rate"); 606 /* Key size not influence False rate so just print out one key size */ 607 for (i = 0; i < 1; i++) { 608 for (j = 0; j < NUM_TYPE; j++) { 609 printf("%-18d", hashtest_key_lens[i]); 610 printf("%-18d", j); 611 printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS); 612 printf("%-18f", (float)false_data_bulk[j][i] / 613 NUM_LOOKUPS); 614 printf("%-18f", (float)false_data_multi[j][i] / 615 NUM_LOOKUPS); 616 printf("%-18f", (float)false_data_multi_bulk[j][i] / 617 NUM_LOOKUPS); 618 printf("%-18f", (float)false_hit[j][i] / 619 NUM_LOOKUPS); 620 printf("\n"); 621 } 622 } 623 return 0; 624 } 625 626 static int 627 test_member_perf(void) 628 { 629 630 if (run_all_tbl_perf_tests() < 0) 631 return -1; 632 633 return 0; 634 } 635 636 #endif /* !RTE_EXEC_ENV_WINDOWS */ 637 638 REGISTER_TEST_COMMAND(member_perf_autotest, test_member_perf); 639