app/test/test_member_perf.c

   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(&params, 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(&params, j) < 0)
 526                                 return exit_with_fail("timed_adds", &params,
 527                                                         i, j);
 528
 529                         for (k = 0; k < NUM_SHUFFLES; k++)
 530                                 shuffle_input_keys(&params);
 531
 532                         if (timed_lookups(&params, j) < 0)
 533                                 return exit_with_fail("timed_lookups", &params,
 534                                                         i, j);
 535
 536                         if (timed_lookups_bulk(&params, j) < 0)
 537                                 return exit_with_fail("timed_lookups_bulk",
 538                                                 &params, i, j);
 539
 540                         if (timed_lookups_multimatch(&params, j) < 0)
 541                                 return exit_with_fail("timed_lookups_multi",
 542                                                 &params, i, j);
 543
 544                         if (timed_lookups_multimatch_bulk(&params, j) < 0)
 545                                 return exit_with_fail("timed_lookups_multi_bulk",
 546                                                         &params, i, j);
 547
 548                         if (timed_deletes(&params, j) < 0)
 549                                 return exit_with_fail("timed_deletes", &params,
 550                                                         i, j);
 551
 552                         /* Print a dot to show progress on operations */
 553                 }
 554                 printf(".");
 555                 fflush(stdout);
 556
 557                 perform_frees(&params);
 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(&params, 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(&params, j) < 0)
 568                                 return exit_with_fail("timed_miss_lookup",
 569                                                 &params, i, j);
 570                 }
 571                 perform_frees(&params);
 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);