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 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                 /* If bucket is full, do not try to insert the key */
 220                 if (buckets[bucket_idx] == BUCKET_SIZE)
 221                         continue;
 222                 /* If key can be added, leave in successful key arrays "keys" */
 223                 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
 224                                                 signatures[i]);
 225                 if (ret >= 0) {
 226                         /* If key is already added, ignore the entry and do not store */
 227                         if (slot_taken[ret])
 228                                 continue;
 229                         else {
 230                                 /* Store the returned position and mark slot as taken */
 231                                 slot_taken[ret] = 1;
 232                                 buckets[bucket_idx]++;
 233                                 success = 1;
 234                                 i++;
 235                         }
 236                 }
 237         }
 238
 239         /* Reset the table, so we can measure the time to add all the entries */
 240         rte_hash_free(h[table_index]);
 241         h[table_index] = rte_hash_create(&ut_params);
 242
 243         return 0;
 244 }
 245
 246 static int
 247 timed_adds(unsigned with_hash, unsigned table_index)
 248 {
 249         unsigned i;
 250         const uint64_t start_tsc = rte_rdtsc();
 251         int32_t ret;
 252
 253         for (i = 0; i < KEYS_TO_ADD; i++) {
 254                 if (with_hash)
 255                         ret = rte_hash_add_key_with_hash(h[table_index],
 256                                                 (const void *) keys[i],
 257                                                 signatures[i]);
 258                 else
 259                         ret = rte_hash_add_key(h[table_index], keys[i]);
 260
 261                 if (ret >= 0)
 262                         positions[i] = ret;
 263                 else {
 264                         printf("Failed to add key number %u\n", ret);
 265                         return -1;
 266                 }
 267         }
 268
 269         const uint64_t end_tsc = rte_rdtsc();
 270         const uint64_t time_taken = end_tsc - start_tsc;
 271
 272         cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD;
 273         return 0;
 274 }
 275
 276 static int
 277 timed_lookups(unsigned with_hash, unsigned table_index)
 278 {
 279         unsigned i, j;
 280         const uint64_t start_tsc = rte_rdtsc();
 281         int32_t ret;
 282
 283         for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
 284                 for (j = 0; j < KEYS_TO_ADD; j++) {
 285                         if (with_hash)
 286                                 ret = rte_hash_lookup_with_hash(h[table_index],
 287                                                         (const void *) keys[j],
 288                                                         signatures[j]);
 289                         else
 290                                 ret = rte_hash_lookup(h[table_index], keys[j]);
 291                         if (ret < 0 || ret != positions[j]) {
 292                                 printf("Key looked up in %d, should be in %d\n",
 293                                         ret, positions[j]);
 294                                 return -1;
 295                         }
 296                 }
 297         }
 298
 299         const uint64_t end_tsc = rte_rdtsc();
 300         const uint64_t time_taken = end_tsc - start_tsc;
 301
 302         cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;
 303
 304         return 0;
 305 }
 306
 307 static int
 308 timed_lookups_multi(unsigned table_index)
 309 {
 310         unsigned i, j, k;
 311         int32_t positions_burst[BURST_SIZE];
 312         const void *keys_burst[BURST_SIZE];
 313         const uint64_t start_tsc = rte_rdtsc();
 314
 315         for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
 316                 for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
 317                         for (k = 0; k < BURST_SIZE; k++)
 318                                 keys_burst[k] = keys[j * BURST_SIZE + k];
 319
 320                         rte_hash_lookup_bulk(h[table_index],
 321                                                 (const void **) keys_burst,
 322                                                 BURST_SIZE,
 323                                                 positions_burst);
 324                         for (k = 0; k < BURST_SIZE; k++) {
 325                                 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
 326                                         printf("Key looked up in %d, should be in %d\n",
 327                                                 positions_burst[k],
 328                                                 positions[j * BURST_SIZE + k]);
 329                                         return -1;
 330                                 }
 331                         }
 332                 }
 333         }
 334
 335         const uint64_t end_tsc = rte_rdtsc();
 336         const uint64_t time_taken = end_tsc - start_tsc;
 337
 338         cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
 339
 340         return 0;
 341 }
 342
 343 static int
 344 timed_deletes(unsigned with_hash, unsigned table_index)
 345 {
 346         unsigned i;
 347         const uint64_t start_tsc = rte_rdtsc();
 348         int32_t ret;
 349
 350         for (i = 0; i < KEYS_TO_ADD; i++) {
 351                 if (with_hash)
 352                         ret = rte_hash_del_key_with_hash(h[table_index],
 353                                                         (const void *) keys[i],
 354                                                         signatures[i]);
 355                 else
 356                         ret = rte_hash_del_key(h[table_index],
 357                                                         (const void *) keys[i]);
 358                 if (ret >= 0)
 359                         positions[i] = ret;
 360                 else {
 361                         printf("Failed to add key number %u\n", ret);
 362                         return -1;
 363                 }
 364         }
 365
 366         const uint64_t end_tsc = rte_rdtsc();
 367         const uint64_t time_taken = end_tsc - start_tsc;
 368
 369         cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;
 370
 371         return 0;
 372 }
 373
 374 static void
 375 free_table(unsigned table_index)
 376 {
 377         rte_hash_free(h[table_index]);
 378 }
 379
 380 static int
 381 reset_table(unsigned table_index)
 382 {
 383         free_table(table_index);
 384         if (create_table(table_index) != 0)
 385                 return -1;
 386
 387         return 0;
 388 }
 389
 390 static int
 391 run_all_tbl_perf_tests(void)
 392 {
 393         unsigned i, j;
 394
 395         printf("Measuring performance, please wait");
 396         fflush(stdout);
 397         for (i = 0; i < NUM_KEYSIZES; i++) {
 398                 if (create_table(i) < 0)
 399                         return -1;
 400
 401                 if (get_input_keys(i) < 0)
 402                         return -1;
 403
 404                 if (timed_adds(0, i) < 0)
 405                         return -1;
 406
 407                 for (j = 0; j < NUM_SHUFFLES; j++)
 408                         shuffle_input_keys(i);
 409
 410                 if (timed_lookups(0, i) < 0)
 411                         return -1;
 412
 413                 if (timed_lookups_multi(i) < 0)
 414                         return -1;
 415
 416                 if (timed_deletes(0, i) < 0)
 417                         return -1;
 418
 419                 /* Print a dot to show progress on operations */
 420                 printf(".");
 421                 fflush(stdout);
 422
 423                 if (reset_table(i) < 0)
 424                         return -1;
 425
 426                 if (timed_adds(1, i) < 0)
 427                         return -1;
 428
 429                 for (j = 0; j < NUM_SHUFFLES; j++)
 430                         shuffle_input_keys(i);
 431
 432                 if (timed_lookups(1, i) < 0)
 433                         return -1;
 434
 435                 if (timed_deletes(1, i) < 0)
 436                         return -1;
 437
 438                 /* Print a dot to show progress on operations */
 439                 printf(".");
 440                 fflush(stdout);
 441
 442                 free_table(i);
 443         }
 444         printf("\nResults (in CPU cycles/operation)\n");
 445         printf("---------------------------------\n");
 446         printf("\nWithout 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][0]);
 453                 printf("\n");
 454         }
 455         printf("\nWith pre-computed hash values\n");
 456         printf("\n%-18s%-18s%-18s%-18s%-18s\n",
 457                         "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
 458         for (i = 0; i < NUM_KEYSIZES; i++) {
 459                 printf("%-18d", hashtest_key_lens[i]);
 460                 for (j = 0; j < NUM_OPERATIONS; j++)
 461                         printf("%-18"PRIu64, cycles[i][j][1]);
 462                 printf("\n");
 463         }
 464
 465         return 0;
 466 }
 467
 468 /* Control operation of performance testing of fbk hash. */
 469 #define LOAD_FACTOR 0.667       /* How full to make the hash table. */
 470 #define TEST_SIZE 1000000       /* How many operations to time. */
 471 #define TEST_ITERATIONS 30      /* How many measurements to take. */
 472 #define ENTRIES (1 << 15)       /* How many entries. */
 473
 474 static int
 475 fbk_hash_perf_test(void)
 476 {
 477         struct rte_fbk_hash_params params = {
 478                 .name = "fbk_hash_test",
 479                 .entries = ENTRIES,
 480                 .entries_per_bucket = 4,
 481                 .socket_id = rte_socket_id(),
 482         };
 483         struct rte_fbk_hash_table *handle = NULL;
 484         uint32_t *keys = NULL;
 485         unsigned indexes[TEST_SIZE];
 486         uint64_t lookup_time = 0;
 487         unsigned added = 0;
 488         unsigned value = 0;
 489         uint32_t key;
 490         uint16_t val;
 491         unsigned i, j;
 492
 493         handle = rte_fbk_hash_create(&params);
 494         if (handle == NULL) {
 495                 printf("Error creating table\n");
 496                 return -1;
 497         }
 498
 499         keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
 500         if (keys == NULL) {
 501                 printf("fbk hash: memory allocation for key store failed\n");
 502                 return -1;
 503         }
 504
 505         /* Generate random keys and values. */
 506         for (i = 0; i < ENTRIES; i++) {
 507                 key = (uint32_t)rte_rand();
 508                 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
 509                 val = (uint16_t)rte_rand();
 510
 511                 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
 512                         keys[added] = key;
 513                         added++;
 514                 }
 515                 if (added > (LOAD_FACTOR * ENTRIES))
 516                         break;
 517         }
 518
 519         for (i = 0; i < TEST_ITERATIONS; i++) {
 520                 uint64_t begin;
 521                 uint64_t end;
 522
 523                 /* Generate random indexes into keys[] array. */
 524                 for (j = 0; j < TEST_SIZE; j++)
 525                         indexes[j] = rte_rand() % added;
 526
 527                 begin = rte_rdtsc();
 528                 /* Do lookups */
 529                 for (j = 0; j < TEST_SIZE; j++)
 530                         value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
 531
 532                 end = rte_rdtsc();
 533                 lookup_time += (double)(end - begin);
 534         }
 535
 536         printf("\n\n *** FBK Hash function performance test results ***\n");
 537         /*
 538          * The use of the 'value' variable ensures that the hash lookup is not
 539          * being optimised out by the compiler.
 540          */
 541         if (value != 0)
 542                 printf("Number of ticks per lookup = %g\n",
 543                         (double)lookup_time /
 544                         ((double)TEST_ITERATIONS * (double)TEST_SIZE));
 545
 546         rte_fbk_hash_free(handle);
 547
 548         return 0;
 549 }
 550
 551 static int
 552 test_hash_perf(void)
 553 {
 554         if (run_all_tbl_perf_tests() < 0)
 555                 return -1;
 556
 557         if (fbk_hash_perf_test() < 0)
 558                 return -1;
 559
 560         return 0;
 561 }
 562
 563 static struct test_command hash_perf_cmd = {
 564                 .command = "hash_perf_autotest",
 565                 .callback = test_hash_perf,
 566 };
 567 REGISTER_TEST_COMMAND(hash_perf_cmd);