app/test/test_hash_perf.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <stdio.h>
  35 #include <inttypes.h>
  36
  37 #include <rte_lcore.h>
  38 #include <rte_cycles.h>
  39 #include <rte_malloc.h>
  40 #include <rte_hash.h>
  41 #include <rte_hash_crc.h>
  42 #include <rte_jhash.h>
  43 #include <rte_fbk_hash.h>
  44 #include <rte_random.h>
  45 #include <rte_string_fns.h>
  46
  47 #include "test.h"
  48
  49 #define MAX_ENTRIES (1 << 19)
  50 #define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */
  51 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
  52 #define BUCKET_SIZE 4
  53 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
  54 #define MAX_KEYSIZE 64
  55 #define NUM_KEYSIZES 10
  56 #define NUM_SHUFFLES 10
  57 #define BURST_SIZE 16
  58
  59 enum operations {
  60         ADD = 0,
  61         LOOKUP,
  62         LOOKUP_MULTI,
  63         DELETE,
  64         NUM_OPERATIONS
  65 };
  66
  67 static uint32_t hashtest_key_lens[] = {
  68         /* standard key sizes */
  69         4, 8, 16, 32, 48, 64,
  70         /* IPv4 SRC + DST + protocol, unpadded */
  71         9,
  72         /* IPv4 5-tuple, unpadded */
  73         13,
  74         /* IPv6 5-tuple, unpadded */
  75         37,
  76         /* IPv6 5-tuple, padded to 8-byte boundary */
  77         40
  78 };
  79
  80 struct rte_hash *h[NUM_KEYSIZES];
  81
  82 /* Array that stores if a slot is full */
  83 uint8_t slot_taken[MAX_ENTRIES];
  84
  85 /* Array to store number of cycles per operation */
  86 uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2];
  87
  88 /* Array to store all input keys */
  89 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
  90
  91 /* Array to store the precomputed hash for 'keys' */
  92 hash_sig_t signatures[KEYS_TO_ADD];
  93
  94 /* Array to store how many busy entries have each bucket */
  95 uint8_t buckets[NUM_BUCKETS];
  96
  97 /* Array to store the positions where keys are added */
  98 int32_t positions[KEYS_TO_ADD];
  99
 100 /* Parameters used for hash table in unit test functions. */
 101 static struct rte_hash_parameters ut_params = {
 102         .entries = MAX_ENTRIES,
 103         .bucket_entries = BUCKET_SIZE,
 104         .hash_func = rte_jhash,
 105         .hash_func_init_val = 0,
 106 };
 107
 108 static int
 109 create_table(unsigned table_index)
 110 {
 111         char name[RTE_HASH_NAMESIZE];
 112
 113         sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
 114         ut_params.name = name;
 115         ut_params.key_len = hashtest_key_lens[table_index];
 116         ut_params.socket_id = rte_socket_id();
 117         h[table_index] = rte_hash_find_existing(name);
 118         if (h[table_index] != NULL)
 119                 /*
 120                  * If table was already created, free it to create it again,
 121                  * so we force it is empty
 122                  */
 123                 rte_hash_free(h[table_index]);
 124         h[table_index] = rte_hash_create(&ut_params);
 125         if (h[table_index] == NULL) {
 126                 printf("Error creating table\n");
 127                 return -1;
 128         }
 129         return 0;
 130
 131 }
 132
 133 /* Shuffle the keys that have been added, so lookups will be totally random */
 134 static void
 135 shuffle_input_keys(unsigned table_index)
 136 {
 137         unsigned i;
 138         uint32_t swap_idx;
 139         uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];
 140         hash_sig_t temp_signature;
 141         int32_t temp_position;
 142
 143         for (i = KEYS_TO_ADD - 1; i > 0; i--) {
 144                 swap_idx = rte_rand() % i;
 145
 146                 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
 147                 temp_signature = signatures[i];
 148                 temp_position = positions[i];
 149
 150                 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
 151                 signatures[i] = signatures[swap_idx];
 152                 positions[i] = positions[swap_idx];
 153
 154                 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
 155                 signatures[swap_idx] = temp_signature;
 156                 positions[swap_idx] = temp_position;
 157         }
 158 }
 159
 160 /*
 161  * Looks for random keys which
 162  * ALL can fit in hash table (no errors)
 163  */
 164 static int
 165 get_input_keys(unsigned with_pushes, unsigned table_index)
 166 {
 167         unsigned i, j;
 168         unsigned bucket_idx, incr, success = 1;
 169         uint8_t k = 0;
 170         int32_t ret;
 171         const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
 172
 173         /* Reset all arrays */
 174         for (i = 0; i < MAX_ENTRIES; i++)
 175                 slot_taken[i] = 0;
 176
 177         for (i = 0; i < NUM_BUCKETS; i++)
 178                 buckets[i] = 0;
 179
 180         for (j = 0; j < hashtest_key_lens[table_index]; j++)
 181                 keys[0][j] = 0;
 182
 183         /*
 184          * Add only entries that are not duplicated and that fits in the table
 185          * (cannot store more than BUCKET_SIZE entries in a bucket).
 186          * Regardless a key has been added correctly or not (success),
 187          * the next one to try will be increased by 1.
 188          */
 189         for (i = 0; i < KEYS_TO_ADD;) {
 190                 incr = 0;
 191                 if (i != 0) {
 192                         keys[i][0] = ++k;
 193                         /* Overflow, need to increment the next byte */
 194                         if (keys[i][0] == 0)
 195                                 incr = 1;
 196                         for (j = 1; j < hashtest_key_lens[table_index]; j++) {
 197                                 /* Do not increase next byte */
 198                                 if (incr == 0)
 199                                         if (success == 1)
 200                                                 keys[i][j] = keys[i - 1][j];
 201                                         else
 202                                                 keys[i][j] = keys[i][j];
 203                                 /* Increase next byte by one */
 204                                 else {
 205                                         if (success == 1)
 206                                                 keys[i][j] = keys[i-1][j] + 1;
 207                                         else
 208                                                 keys[i][j] = keys[i][j] + 1;
 209                                         if (keys[i][j] == 0)
 210                                                 incr = 1;
 211                                         else
 212                                                 incr = 0;
 213                                 }
 214                         }
 215                 }
 216                 success = 0;
 217                 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
 218                 bucket_idx = signatures[i] & bucket_bitmask;
 219                 /*
 220                  * If we are not inserting keys in secondary location,
 221                  * when bucket is full, do not try to insert the key
 222                  */
 223                 if (with_pushes == 0)
 224                         if (buckets[bucket_idx] == BUCKET_SIZE)
 225                                 continue;
 226
 227                 /* If key can be added, leave in successful key arrays "keys" */
 228                 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
 229                                                 signatures[i]);
 230                 if (ret >= 0) {
 231                         /* If key is already added, ignore the entry and do not store */
 232                         if (slot_taken[ret])
 233                                 continue;
 234                         else {
 235                                 /* Store the returned position and mark slot as taken */
 236                                 slot_taken[ret] = 1;
 237                                 buckets[bucket_idx]++;
 238                                 success = 1;
 239                                 i++;
 240                         }
 241                 }
 242         }
 243
 244         /* Reset the table, so we can measure the time to add all the entries */
 245         rte_hash_free(h[table_index]);
 246         h[table_index] = rte_hash_create(&ut_params);
 247
 248         return 0;
 249 }
 250
 251 static int
 252 timed_adds(unsigned with_hash, unsigned table_index)
 253 {
 254         unsigned i;
 255         const uint64_t start_tsc = rte_rdtsc();
 256         int32_t ret;
 257
 258         for (i = 0; i < KEYS_TO_ADD; i++) {
 259                 if (with_hash)
 260                         ret = rte_hash_add_key_with_hash(h[table_index],
 261                                                 (const void *) keys[i],
 262                                                 signatures[i]);
 263                 else
 264                         ret = rte_hash_add_key(h[table_index], keys[i]);
 265
 266                 if (ret >= 0)
 267                         positions[i] = ret;
 268                 else {
 269                         printf("Failed to add key number %u\n", ret);
 270                         return -1;
 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] = time_taken/KEYS_TO_ADD;
 278         return 0;
 279 }
 280
 281 static int
 282 timed_lookups(unsigned with_hash, unsigned table_index)
 283 {
 284         unsigned i, j;
 285         const uint64_t start_tsc = rte_rdtsc();
 286         int32_t ret;
 287
 288         for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
 289                 for (j = 0; j < KEYS_TO_ADD; j++) {
 290                         if (with_hash)
 291                                 ret = rte_hash_lookup_with_hash(h[table_index],
 292                                                         (const void *) keys[j],
 293                                                         signatures[j]);
 294                         else
 295                                 ret = rte_hash_lookup(h[table_index], keys[j]);
 296                         if (ret < 0 || ret != positions[j]) {
 297                                 printf("Key looked up in %d, should be in %d\n",
 298                                         ret, positions[j]);
 299                                 return -1;
 300                         }
 301                 }
 302         }
 303
 304         const uint64_t end_tsc = rte_rdtsc();
 305         const uint64_t time_taken = end_tsc - start_tsc;
 306
 307         cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;
 308
 309         return 0;
 310 }
 311
 312 static int
 313 timed_lookups_multi(unsigned table_index)
 314 {
 315         unsigned i, j, k;
 316         int32_t positions_burst[BURST_SIZE];
 317         const void *keys_burst[BURST_SIZE];
 318         const uint64_t start_tsc = rte_rdtsc();
 319
 320         for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
 321                 for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
 322                         for (k = 0; k < BURST_SIZE; k++)
 323                                 keys_burst[k] = keys[j * BURST_SIZE + k];
 324
 325                         rte_hash_lookup_bulk(h[table_index],
 326                                                 (const void **) keys_burst,
 327                                                 BURST_SIZE,
 328                                                 positions_burst);
 329                         for (k = 0; k < BURST_SIZE; k++) {
 330                                 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
 331                                         printf("Key looked up in %d, should be in %d\n",
 332                                                 positions_burst[k],
 333                                                 positions[j * BURST_SIZE + k]);
 334                                         return -1;
 335                                 }
 336                         }
 337                 }
 338         }
 339
 340         const uint64_t end_tsc = rte_rdtsc();
 341         const uint64_t time_taken = end_tsc - start_tsc;
 342
 343         cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
 344
 345         return 0;
 346 }
 347
 348 static int
 349 timed_deletes(unsigned with_hash, unsigned table_index)
 350 {
 351         unsigned i;
 352         const uint64_t start_tsc = rte_rdtsc();
 353         int32_t ret;
 354
 355         for (i = 0; i < KEYS_TO_ADD; i++) {
 356                 if (with_hash)
 357                         ret = rte_hash_del_key_with_hash(h[table_index],
 358                                                         (const void *) keys[i],
 359                                                         signatures[i]);
 360                 else
 361                         ret = rte_hash_del_key(h[table_index],
 362                                                         (const void *) keys[i]);
 363                 if (ret >= 0)
 364                         positions[i] = ret;
 365                 else {
 366                         printf("Failed to add key number %u\n", ret);
 367                         return -1;
 368                 }
 369         }
 370
 371         const uint64_t end_tsc = rte_rdtsc();
 372         const uint64_t time_taken = end_tsc - start_tsc;
 373
 374         cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;
 375
 376         return 0;
 377 }
 378
 379 static void
 380 free_table(unsigned table_index)
 381 {
 382         rte_hash_free(h[table_index]);
 383 }
 384
 385 static int
 386 reset_table(unsigned table_index)
 387 {
 388         free_table(table_index);
 389         if (create_table(table_index) != 0)
 390                 return -1;
 391
 392         return 0;
 393 }
 394
 395 static int
 396 run_all_tbl_perf_tests(unsigned with_pushes)
 397 {
 398         unsigned i, j, with_hash;
 399
 400         printf("Measuring performance, please wait");
 401         fflush(stdout);
 402         for (i = 0; i < NUM_KEYSIZES; i++) {
 403                 if (create_table(i) < 0)
 404                         return -1;
 405
 406                 if (get_input_keys(with_pushes, i) < 0)
 407                         return -1;
 408                 for (with_hash = 0; with_hash <= 1; with_hash++) {
 409                         if (timed_adds(with_hash, i) < 0)
 410                                 return -1;
 411
 412                         for (j = 0; j < NUM_SHUFFLES; j++)
 413                                 shuffle_input_keys(i);
 414
 415                         if (timed_lookups(with_hash, i) < 0)
 416                                 return -1;
 417
 418                         if (timed_lookups_multi(i) < 0)
 419                                 return -1;
 420
 421                         if (timed_deletes(with_hash, i) < 0)
 422                                 return -1;
 423
 424                         if (reset_table(i) < 0)
 425                                 return -1;
 426
 427                         /* Print a dot to show progress on operations */
 428                         printf(".");
 429                         fflush(stdout);
 430
 431                 }
 432
 433                 free_table(i);
 434         }
 435         printf("\nResults (in CPU cycles/operation)\n");
 436         printf("---------------------------------\n");
 437         printf("\nWithout pre-computed hash values\n");
 438         printf("\n%-18s%-18s%-18s%-18s%-18s\n",
 439                         "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
 440         for (i = 0; i < NUM_KEYSIZES; i++) {
 441                 printf("%-18d", hashtest_key_lens[i]);
 442                 for (j = 0; j < NUM_OPERATIONS; j++)
 443                         printf("%-18"PRIu64, cycles[i][j][0]);
 444                 printf("\n");
 445         }
 446         printf("\nWith pre-computed hash values\n");
 447         printf("\n%-18s%-18s%-18s%-18s%-18s\n",
 448                         "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
 449         for (i = 0; i < NUM_KEYSIZES; i++) {
 450                 printf("%-18d", hashtest_key_lens[i]);
 451                 for (j = 0; j < NUM_OPERATIONS; j++)
 452                         printf("%-18"PRIu64, cycles[i][j][1]);
 453                 printf("\n");
 454         }
 455
 456         return 0;
 457 }
 458
 459 /* Control operation of performance testing of fbk hash. */
 460 #define LOAD_FACTOR 0.667       /* How full to make the hash table. */
 461 #define TEST_SIZE 1000000       /* How many operations to time. */
 462 #define TEST_ITERATIONS 30      /* How many measurements to take. */
 463 #define ENTRIES (1 << 15)       /* How many entries. */
 464
 465 static int
 466 fbk_hash_perf_test(void)
 467 {
 468         struct rte_fbk_hash_params params = {
 469                 .name = "fbk_hash_test",
 470                 .entries = ENTRIES,
 471                 .entries_per_bucket = 4,
 472                 .socket_id = rte_socket_id(),
 473         };
 474         struct rte_fbk_hash_table *handle = NULL;
 475         uint32_t *keys = NULL;
 476         unsigned indexes[TEST_SIZE];
 477         uint64_t lookup_time = 0;
 478         unsigned added = 0;
 479         unsigned value = 0;
 480         uint32_t key;
 481         uint16_t val;
 482         unsigned i, j;
 483
 484         handle = rte_fbk_hash_create(&params);
 485         if (handle == NULL) {
 486                 printf("Error creating table\n");
 487                 return -1;
 488         }
 489
 490         keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
 491         if (keys == NULL) {
 492                 printf("fbk hash: memory allocation for key store failed\n");
 493                 return -1;
 494         }
 495
 496         /* Generate random keys and values. */
 497         for (i = 0; i < ENTRIES; i++) {
 498                 key = (uint32_t)rte_rand();
 499                 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
 500                 val = (uint16_t)rte_rand();
 501
 502                 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
 503                         keys[added] = key;
 504                         added++;
 505                 }
 506                 if (added > (LOAD_FACTOR * ENTRIES))
 507                         break;
 508         }
 509
 510         for (i = 0; i < TEST_ITERATIONS; i++) {
 511                 uint64_t begin;
 512                 uint64_t end;
 513
 514                 /* Generate random indexes into keys[] array. */
 515                 for (j = 0; j < TEST_SIZE; j++)
 516                         indexes[j] = rte_rand() % added;
 517
 518                 begin = rte_rdtsc();
 519                 /* Do lookups */
 520                 for (j = 0; j < TEST_SIZE; j++)
 521                         value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
 522
 523                 end = rte_rdtsc();
 524                 lookup_time += (double)(end - begin);
 525         }
 526
 527         printf("\n\n *** FBK Hash function performance test results ***\n");
 528         /*
 529          * The use of the 'value' variable ensures that the hash lookup is not
 530          * being optimised out by the compiler.
 531          */
 532         if (value != 0)
 533                 printf("Number of ticks per lookup = %g\n",
 534                         (double)lookup_time /
 535                         ((double)TEST_ITERATIONS * (double)TEST_SIZE));
 536
 537         rte_fbk_hash_free(handle);
 538
 539         return 0;
 540 }
 541
 542 static int
 543 test_hash_perf(void)
 544 {
 545         unsigned with_pushes;
 546
 547         for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
 548                 if (with_pushes == 0)
 549                         printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
 550                 else
 551                         printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
 552                 if (run_all_tbl_perf_tests(with_pushes) < 0)
 553                         return -1;
 554         }
 555
 556         if (fbk_hash_perf_test() < 0)
 557                 return -1;
 558
 559         return 0;
 560 }
 561
 562 static struct test_command hash_perf_cmd = {
 563                 .command = "hash_perf_autotest",
 564                 .callback = test_hash_perf,
 565 };
 566 REGISTER_TEST_COMMAND(hash_perf_cmd);