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