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