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