test/test/test_hash_perf.c

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