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