test/test/test_hash.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 <stdint.h>
  36 #include <string.h>
  37 #include <stdlib.h>
  38 #include <stdarg.h>
  39 #include <errno.h>
  40 #include <sys/queue.h>
  41
  42 #include <rte_common.h>
  43 #include <rte_malloc.h>
  44 #include <rte_cycles.h>
  45 #include <rte_random.h>
  46 #include <rte_memory.h>
  47 #include <rte_memzone.h>
  48 #include <rte_eal.h>
  49 #include <rte_ip.h>
  50 #include <rte_string_fns.h>
  51
  52 #include "test.h"
  53
  54 #include <rte_hash.h>
  55 #include <rte_fbk_hash.h>
  56 #include <rte_jhash.h>
  57 #include <rte_hash_crc.h>
  58
  59 /*******************************************************************************
  60  * Hash function performance test configuration section. Each performance test
  61  * will be performed HASHTEST_ITERATIONS times.
  62  *
  63  * The five arrays below control what tests are performed. Every combination
  64  * from the array entries is tested.
  65  */
  66 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
  67 static uint32_t hashtest_initvals[] = {0};
  68 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
  69 #define MAX_KEYSIZE 64
  70 /******************************************************************************/
  71 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
  72
  73 /*
  74  * Check condition and return an error if true. Assumes that "handle" is the
  75  * name of the hash structure pointer to be freed.
  76  */
  77 #define RETURN_IF_ERROR(cond, str, ...) do {                            \
  78         if (cond) {                                                     \
  79                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
  80                 if (handle) rte_hash_free(handle);                      \
  81                 return -1;                                              \
  82         }                                                               \
  83 } while(0)
  84
  85 #define RETURN_IF_ERROR_FBK(cond, str, ...) do {                                \
  86         if (cond) {                                                     \
  87                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
  88                 if (handle) rte_fbk_hash_free(handle);                  \
  89                 return -1;                                              \
  90         }                                                               \
  91 } while(0)
  92
  93 /* 5-tuple key type */
  94 struct flow_key {
  95         uint32_t ip_src;
  96         uint32_t ip_dst;
  97         uint16_t port_src;
  98         uint16_t port_dst;
  99         uint8_t proto;
 100 } __attribute__((packed));
 101
 102 /*
 103  * Hash function that always returns the same value, to easily test what
 104  * happens when a bucket is full.
 105  */
 106 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
 107                             __attribute__((unused)) uint32_t key_len,
 108                             __attribute__((unused)) uint32_t init_val)
 109 {
 110         return 3;
 111 }
 112
 113 /*
 114  * Print out result of unit test hash operation.
 115  */
 116 #if defined(UNIT_TEST_HASH_VERBOSE)
 117 static void print_key_info(const char *msg, const struct flow_key *key,
 118                                                                 int32_t pos)
 119 {
 120         uint8_t *p = (uint8_t *)key;
 121         unsigned i;
 122
 123         printf("%s key:0x", msg);
 124         for (i = 0; i < sizeof(struct flow_key); i++) {
 125                 printf("%02X", p[i]);
 126         }
 127         printf(" @ pos %d\n", pos);
 128 }
 129 #else
 130 static void print_key_info(__attribute__((unused)) const char *msg,
 131                 __attribute__((unused)) const struct flow_key *key,
 132                 __attribute__((unused)) int32_t pos)
 133 {
 134 }
 135 #endif
 136
 137 /* Keys used by unit test functions */
 138 static struct flow_key keys[5] = { {
 139         .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
 140         .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
 141         .port_src = 0x0908,
 142         .port_dst = 0x0b0a,
 143         .proto = 0x0c,
 144 }, {
 145         .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
 146         .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
 147         .port_src = 0x1918,
 148         .port_dst = 0x1b1a,
 149         .proto = 0x1c,
 150 }, {
 151         .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
 152         .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
 153         .port_src = 0x2928,
 154         .port_dst = 0x2b2a,
 155         .proto = 0x2c,
 156 }, {
 157         .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
 158         .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
 159         .port_src = 0x3938,
 160         .port_dst = 0x3b3a,
 161         .proto = 0x3c,
 162 }, {
 163         .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
 164         .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
 165         .port_src = 0x4948,
 166         .port_dst = 0x4b4a,
 167         .proto = 0x4c,
 168 } };
 169
 170 /* Parameters used for hash table in unit test functions. Name set later. */
 171 static struct rte_hash_parameters ut_params = {
 172         .entries = 64,
 173         .key_len = sizeof(struct flow_key), /* 13 */
 174         .hash_func = rte_jhash,
 175         .hash_func_init_val = 0,
 176         .socket_id = 0,
 177 };
 178
 179 #define CRC32_ITERATIONS (1U << 10)
 180 #define CRC32_DWORDS (1U << 6)
 181 /*
 182  * Test if all CRC32 implementations yield the same hash value
 183  */
 184 static int
 185 test_crc32_hash_alg_equiv(void)
 186 {
 187         uint32_t hash_val;
 188         uint32_t init_val;
 189         uint64_t data64[CRC32_DWORDS];
 190         unsigned i, j;
 191         size_t data_len;
 192
 193         printf("\n# CRC32 implementations equivalence test\n");
 194         for (i = 0; i < CRC32_ITERATIONS; i++) {
 195                 /* Randomizing data_len of data set */
 196                 data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1);
 197                 init_val = (uint32_t) rte_rand();
 198
 199                 /* Fill the data set */
 200                 for (j = 0; j < CRC32_DWORDS; j++)
 201                         data64[j] = rte_rand();
 202
 203                 /* Calculate software CRC32 */
 204                 rte_hash_crc_set_alg(CRC32_SW);
 205                 hash_val = rte_hash_crc(data64, data_len, init_val);
 206
 207                 /* Check against 4-byte-operand sse4.2 CRC32 if available */
 208                 rte_hash_crc_set_alg(CRC32_SSE42);
 209                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 210                         printf("Failed checking CRC32_SW against CRC32_SSE42\n");
 211                         break;
 212                 }
 213
 214                 /* Check against 8-byte-operand sse4.2 CRC32 if available */
 215                 rte_hash_crc_set_alg(CRC32_SSE42_x64);
 216                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 217                         printf("Failed checking CRC32_SW against CRC32_SSE42_x64\n");
 218                         break;
 219                 }
 220
 221                 /* Check against 8-byte-operand ARM64 CRC32 if available */
 222                 rte_hash_crc_set_alg(CRC32_ARM64);
 223                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 224                         printf("Failed checking CRC32_SW against CRC32_ARM64\n");
 225                         break;
 226                 }
 227         }
 228
 229         /* Resetting to best available algorithm */
 230         rte_hash_crc_set_alg(CRC32_SSE42_x64);
 231
 232         if (i == CRC32_ITERATIONS)
 233                 return 0;
 234
 235         printf("Failed test data (hex, %zu bytes total):\n", data_len);
 236         for (j = 0; j < data_len; j++)
 237                 printf("%02X%c", ((uint8_t *)data64)[j],
 238                                 ((j+1) % 16 == 0 || j == data_len - 1) ? '\n' : ' ');
 239
 240         return -1;
 241 }
 242
 243 /*
 244  * Test a hash function.
 245  */
 246 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
 247                 uint32_t key_len)
 248 {
 249         static uint8_t key[MAX_KEYSIZE];
 250         unsigned i;
 251
 252
 253         for (i = 0; i < key_len; i++)
 254                 key[i] = (uint8_t) rte_rand();
 255
 256         /* just to be on the safe side */
 257         if (!f)
 258                 return;
 259
 260         f(key, key_len, init_val);
 261 }
 262
 263 /*
 264  * Test all hash functions.
 265  */
 266 static void run_hash_func_tests(void)
 267 {
 268         unsigned i, j, k;
 269
 270         for (i = 0;
 271              i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
 272              i++) {
 273                 for (j = 0;
 274                      j < sizeof(hashtest_initvals) / sizeof(uint32_t);
 275                      j++) {
 276                         for (k = 0;
 277                              k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
 278                              k++) {
 279                                 run_hash_func_test(hashtest_funcs[i],
 280                                                 hashtest_initvals[j],
 281                                                 hashtest_key_lens[k]);
 282                         }
 283                 }
 284         }
 285 }
 286
 287 /*
 288  * Basic sequence of operations for a single key:
 289  *      - add
 290  *      - lookup (hit)
 291  *      - delete
 292  *      - lookup (miss)
 293  */
 294 static int test_add_delete(void)
 295 {
 296         struct rte_hash *handle;
 297         /* test with standard add/lookup/delete functions */
 298         int pos0, expectedPos0;
 299
 300         ut_params.name = "test1";
 301         handle = rte_hash_create(&ut_params);
 302         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 303
 304         pos0 = rte_hash_add_key(handle, &keys[0]);
 305         print_key_info("Add", &keys[0], pos0);
 306         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 307         expectedPos0 = pos0;
 308
 309         pos0 = rte_hash_lookup(handle, &keys[0]);
 310         print_key_info("Lkp", &keys[0], pos0);
 311         RETURN_IF_ERROR(pos0 != expectedPos0,
 312                         "failed to find key (pos0=%d)", pos0);
 313
 314         pos0 = rte_hash_del_key(handle, &keys[0]);
 315         print_key_info("Del", &keys[0], pos0);
 316         RETURN_IF_ERROR(pos0 != expectedPos0,
 317                         "failed to delete key (pos0=%d)", pos0);
 318
 319         pos0 = rte_hash_lookup(handle, &keys[0]);
 320         print_key_info("Lkp", &keys[0], pos0);
 321         RETURN_IF_ERROR(pos0 != -ENOENT,
 322                         "fail: found key after deleting! (pos0=%d)", pos0);
 323
 324         rte_hash_free(handle);
 325
 326         /* repeat test with precomputed hash functions */
 327         hash_sig_t hash_value;
 328         int pos1, expectedPos1;
 329
 330         handle = rte_hash_create(&ut_params);
 331         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 332
 333         hash_value = rte_hash_hash(handle, &keys[0]);
 334         pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
 335         print_key_info("Add", &keys[0], pos1);
 336         RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
 337         expectedPos1 = pos1;
 338
 339         pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
 340         print_key_info("Lkp", &keys[0], pos1);
 341         RETURN_IF_ERROR(pos1 != expectedPos1,
 342                         "failed to find key (pos1=%d)", pos1);
 343
 344         pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
 345         print_key_info("Del", &keys[0], pos1);
 346         RETURN_IF_ERROR(pos1 != expectedPos1,
 347                         "failed to delete key (pos1=%d)", pos1);
 348
 349         pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
 350         print_key_info("Lkp", &keys[0], pos1);
 351         RETURN_IF_ERROR(pos1 != -ENOENT,
 352                         "fail: found key after deleting! (pos1=%d)", pos1);
 353
 354         rte_hash_free(handle);
 355
 356         return 0;
 357 }
 358
 359 /*
 360  * Sequence of operations for a single key:
 361  *      - delete: miss
 362  *      - add
 363  *      - lookup: hit
 364  *      - add: update
 365  *      - lookup: hit (updated data)
 366  *      - delete: hit
 367  *      - delete: miss
 368  *      - lookup: miss
 369  */
 370 static int test_add_update_delete(void)
 371 {
 372         struct rte_hash *handle;
 373         int pos0, expectedPos0;
 374
 375         ut_params.name = "test2";
 376         handle = rte_hash_create(&ut_params);
 377         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 378
 379         pos0 = rte_hash_del_key(handle, &keys[0]);
 380         print_key_info("Del", &keys[0], pos0);
 381         RETURN_IF_ERROR(pos0 != -ENOENT,
 382                         "fail: found non-existent key (pos0=%d)", pos0);
 383
 384         pos0 = rte_hash_add_key(handle, &keys[0]);
 385         print_key_info("Add", &keys[0], pos0);
 386         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 387         expectedPos0 = pos0;
 388
 389         pos0 = rte_hash_lookup(handle, &keys[0]);
 390         print_key_info("Lkp", &keys[0], pos0);
 391         RETURN_IF_ERROR(pos0 != expectedPos0,
 392                         "failed to find key (pos0=%d)", pos0);
 393
 394         pos0 = rte_hash_add_key(handle, &keys[0]);
 395         print_key_info("Add", &keys[0], pos0);
 396         RETURN_IF_ERROR(pos0 != expectedPos0,
 397                         "failed to re-add key (pos0=%d)", pos0);
 398
 399         pos0 = rte_hash_lookup(handle, &keys[0]);
 400         print_key_info("Lkp", &keys[0], pos0);
 401         RETURN_IF_ERROR(pos0 != expectedPos0,
 402                         "failed to find key (pos0=%d)", pos0);
 403
 404         pos0 = rte_hash_del_key(handle, &keys[0]);
 405         print_key_info("Del", &keys[0], pos0);
 406         RETURN_IF_ERROR(pos0 != expectedPos0,
 407                         "failed to delete key (pos0=%d)", pos0);
 408
 409         pos0 = rte_hash_del_key(handle, &keys[0]);
 410         print_key_info("Del", &keys[0], pos0);
 411         RETURN_IF_ERROR(pos0 != -ENOENT,
 412                         "fail: deleted already deleted key (pos0=%d)", pos0);
 413
 414         pos0 = rte_hash_lookup(handle, &keys[0]);
 415         print_key_info("Lkp", &keys[0], pos0);
 416         RETURN_IF_ERROR(pos0 != -ENOENT,
 417                         "fail: found key after deleting! (pos0=%d)", pos0);
 418
 419         rte_hash_free(handle);
 420         return 0;
 421 }
 422
 423 /*
 424  * Sequence of operations for retrieving a key with its position
 425  *
 426  *  - create table
 427  *  - add key
 428  *  - get the key with its position: hit
 429  *  - delete key
 430  *  - try to get the deleted key: miss
 431  *
 432  */
 433 static int test_hash_get_key_with_position(void)
 434 {
 435         struct rte_hash *handle = NULL;
 436         int pos, expectedPos, result;
 437         void *key;
 438
 439         ut_params.name = "hash_get_key_w_pos";
 440         handle = rte_hash_create(&ut_params);
 441         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 442
 443         pos = rte_hash_add_key(handle, &keys[0]);
 444         print_key_info("Add", &keys[0], pos);
 445         RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
 446         expectedPos = pos;
 447
 448         result = rte_hash_get_key_with_position(handle, pos, &key);
 449         RETURN_IF_ERROR(result != 0, "error retrieving a key");
 450
 451         pos = rte_hash_del_key(handle, &keys[0]);
 452         print_key_info("Del", &keys[0], pos);
 453         RETURN_IF_ERROR(pos != expectedPos,
 454                         "failed to delete key (pos0=%d)", pos);
 455
 456         result = rte_hash_get_key_with_position(handle, pos, &key);
 457         RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
 458
 459         rte_hash_free(handle);
 460         return 0;
 461 }
 462
 463 /*
 464  * Sequence of operations for find existing hash table
 465  *
 466  *  - create table
 467  *  - find existing table: hit
 468  *  - find non-existing table: miss
 469  *
 470  */
 471 static int test_hash_find_existing(void)
 472 {
 473         struct rte_hash *handle = NULL, *result = NULL;
 474
 475         /* Create hash table. */
 476         ut_params.name = "hash_find_existing";
 477         handle = rte_hash_create(&ut_params);
 478         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 479
 480         /* Try to find existing hash table */
 481         result = rte_hash_find_existing("hash_find_existing");
 482         RETURN_IF_ERROR(result != handle, "could not find existing hash table");
 483
 484         /* Try to find non-existing hash table */
 485         result = rte_hash_find_existing("hash_find_non_existing");
 486         RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
 487
 488         /* Cleanup. */
 489         rte_hash_free(handle);
 490
 491         return 0;
 492 }
 493
 494 /*
 495  * Sequence of operations for 5 keys
 496  *      - add keys
 497  *      - lookup keys: hit
 498  *      - add keys (update)
 499  *      - lookup keys: hit (updated data)
 500  *      - delete keys : hit
 501  *      - lookup keys: miss
 502  */
 503 static int test_five_keys(void)
 504 {
 505         struct rte_hash *handle;
 506         const void *key_array[5] = {0};
 507         int pos[5];
 508         int expected_pos[5];
 509         unsigned i;
 510         int ret;
 511
 512         ut_params.name = "test3";
 513         handle = rte_hash_create(&ut_params);
 514         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 515
 516         /* Add */
 517         for (i = 0; i < 5; i++) {
 518                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 519                 print_key_info("Add", &keys[i], pos[i]);
 520                 RETURN_IF_ERROR(pos[i] < 0,
 521                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 522                 expected_pos[i] = pos[i];
 523         }
 524
 525         /* Lookup */
 526         for(i = 0; i < 5; i++)
 527                 key_array[i] = &keys[i];
 528
 529         ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
 530         if(ret == 0)
 531                 for(i = 0; i < 5; i++) {
 532                         print_key_info("Lkp", key_array[i], pos[i]);
 533                         RETURN_IF_ERROR(pos[i] != expected_pos[i],
 534                                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 535                 }
 536
 537         /* Add - update */
 538         for (i = 0; i < 5; i++) {
 539                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 540                 print_key_info("Add", &keys[i], pos[i]);
 541                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 542                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 543         }
 544
 545         /* Lookup */
 546         for (i = 0; i < 5; i++) {
 547                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 548                 print_key_info("Lkp", &keys[i], pos[i]);
 549                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 550                                 "failed to find key (pos[%u]=%d)", i, pos[i]);
 551         }
 552
 553         /* Delete */
 554         for (i = 0; i < 5; i++) {
 555                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 556                 print_key_info("Del", &keys[i], pos[i]);
 557                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 558                                 "failed to delete key (pos[%u]=%d)", i, pos[i]);
 559         }
 560
 561         /* Lookup */
 562         for (i = 0; i < 5; i++) {
 563                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 564                 print_key_info("Lkp", &keys[i], pos[i]);
 565                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 566                                 "found non-existent key (pos[%u]=%d)", i, pos[i]);
 567         }
 568
 569         /* Lookup multi */
 570         ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
 571         if (ret == 0)
 572                 for (i = 0; i < 5; i++) {
 573                         print_key_info("Lkp", key_array[i], pos[i]);
 574                         RETURN_IF_ERROR(pos[i] != -ENOENT,
 575                                         "found not-existent key (pos[%u]=%d)", i, pos[i]);
 576                 }
 577
 578         rte_hash_free(handle);
 579
 580         return 0;
 581 }
 582
 583 /*
 584  * Add keys to the same bucket until bucket full.
 585  *      - add 5 keys to the same bucket (hash created with 4 keys per bucket):
 586  *        first 4 successful, 5th successful, pushing existing item in bucket
 587  *      - lookup the 5 keys: 5 hits
 588  *      - add the 5 keys again: 5 OK
 589  *      - lookup the 5 keys: 5 hits (updated data)
 590  *      - delete the 5 keys: 5 OK
 591  *      - lookup the 5 keys: 5 misses
 592  */
 593 static int test_full_bucket(void)
 594 {
 595         struct rte_hash_parameters params_pseudo_hash = {
 596                 .name = "test4",
 597                 .entries = 64,
 598                 .key_len = sizeof(struct flow_key), /* 13 */
 599                 .hash_func = pseudo_hash,
 600                 .hash_func_init_val = 0,
 601                 .socket_id = 0,
 602         };
 603         struct rte_hash *handle;
 604         int pos[5];
 605         int expected_pos[5];
 606         unsigned i;
 607
 608         handle = rte_hash_create(&params_pseudo_hash);
 609         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 610
 611         /* Fill bucket */
 612         for (i = 0; i < 4; i++) {
 613                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 614                 print_key_info("Add", &keys[i], pos[i]);
 615                 RETURN_IF_ERROR(pos[i] < 0,
 616                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 617                 expected_pos[i] = pos[i];
 618         }
 619         /*
 620          * This should work and will push one of the items
 621          * in the bucket because it is full
 622          */
 623         pos[4] = rte_hash_add_key(handle, &keys[4]);
 624         print_key_info("Add", &keys[4], pos[4]);
 625         RETURN_IF_ERROR(pos[4] < 0,
 626                         "failed to add key (pos[4]=%d)", pos[4]);
 627         expected_pos[4] = pos[4];
 628
 629         /* Lookup */
 630         for (i = 0; i < 5; i++) {
 631                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 632                 print_key_info("Lkp", &keys[i], pos[i]);
 633                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 634                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 635         }
 636
 637         /* Add - update */
 638         for (i = 0; i < 5; i++) {
 639                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 640                 print_key_info("Add", &keys[i], pos[i]);
 641                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 642                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 643         }
 644
 645         /* Lookup */
 646         for (i = 0; i < 5; i++) {
 647                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 648                 print_key_info("Lkp", &keys[i], pos[i]);
 649                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 650                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 651         }
 652
 653         /* Delete 1 key, check other keys are still found */
 654         pos[1] = rte_hash_del_key(handle, &keys[1]);
 655         print_key_info("Del", &keys[1], pos[1]);
 656         RETURN_IF_ERROR(pos[1] != expected_pos[1],
 657                         "failed to delete key (pos[1]=%d)", pos[1]);
 658         pos[3] = rte_hash_lookup(handle, &keys[3]);
 659         print_key_info("Lkp", &keys[3], pos[3]);
 660         RETURN_IF_ERROR(pos[3] != expected_pos[3],
 661                         "failed lookup after deleting key from same bucket "
 662                         "(pos[3]=%d)", pos[3]);
 663
 664         /* Go back to previous state */
 665         pos[1] = rte_hash_add_key(handle, &keys[1]);
 666         print_key_info("Add", &keys[1], pos[1]);
 667         expected_pos[1] = pos[1];
 668         RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
 669
 670         /* Delete */
 671         for (i = 0; i < 5; i++) {
 672                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 673                 print_key_info("Del", &keys[i], pos[i]);
 674                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 675                         "failed to delete key (pos[%u]=%d)", i, pos[i]);
 676         }
 677
 678         /* Lookup */
 679         for (i = 0; i < 5; i++) {
 680                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 681                 print_key_info("Lkp", &keys[i], pos[i]);
 682                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 683                         "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
 684         }
 685
 686         rte_hash_free(handle);
 687
 688         /* Cover the NULL case. */
 689         rte_hash_free(0);
 690         return 0;
 691 }
 692
 693 /******************************************************************************/
 694 static int
 695 fbk_hash_unit_test(void)
 696 {
 697         struct rte_fbk_hash_params params = {
 698                 .name = "fbk_hash_test",
 699                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 700                 .entries_per_bucket = 4,
 701                 .socket_id = 0,
 702         };
 703
 704         struct rte_fbk_hash_params invalid_params_1 = {
 705                 .name = "invalid_1",
 706                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
 707                 .entries_per_bucket = 4,
 708                 .socket_id = 0,
 709         };
 710
 711         struct rte_fbk_hash_params invalid_params_2 = {
 712                 .name = "invalid_2",
 713                 .entries = 4,
 714                 .entries_per_bucket = 3,         /* Not power of 2 */
 715                 .socket_id = 0,
 716         };
 717
 718         struct rte_fbk_hash_params invalid_params_3 = {
 719                 .name = "invalid_3",
 720                 .entries = 0,                    /* Entries is 0 */
 721                 .entries_per_bucket = 4,
 722                 .socket_id = 0,
 723         };
 724
 725         struct rte_fbk_hash_params invalid_params_4 = {
 726                 .name = "invalid_4",
 727                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 728                 .entries_per_bucket = 0,         /* Entries per bucket is 0 */
 729                 .socket_id = 0,
 730         };
 731
 732         struct rte_fbk_hash_params invalid_params_5 = {
 733                 .name = "invalid_5",
 734                 .entries = 4,
 735                 .entries_per_bucket = 8,         /* Entries per bucket > entries */
 736                 .socket_id = 0,
 737         };
 738
 739         struct rte_fbk_hash_params invalid_params_6 = {
 740                 .name = "invalid_6",
 741                 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2,   /* Entries > max allowed */
 742                 .entries_per_bucket = 4,
 743                 .socket_id = 0,
 744         };
 745
 746         struct rte_fbk_hash_params invalid_params_7 = {
 747                 .name = "invalid_7",
 748                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
 749                 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2,  /* Entries > max allowed */
 750                 .socket_id = 0,
 751         };
 752
 753         struct rte_fbk_hash_params invalid_params_8 = {
 754                 .name = "invalid_7",
 755                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
 756                 .entries_per_bucket = 4,
 757                 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
 758         };
 759
 760         /* try to create two hashes with identical names
 761          * in this case, trying to create a second one will not
 762          * fail but will simply return pointer to the existing
 763          * hash with that name. sort of like a "find hash by name" :-)
 764          */
 765         struct rte_fbk_hash_params invalid_params_same_name_1 = {
 766                 .name = "same_name",                            /* hash with identical name */
 767                 .entries = 4,
 768                 .entries_per_bucket = 2,
 769                 .socket_id = 0,
 770         };
 771
 772         /* trying to create this hash should return a pointer to an existing hash */
 773         struct rte_fbk_hash_params invalid_params_same_name_2 = {
 774                 .name = "same_name",                            /* hash with identical name */
 775                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
 776                 .entries_per_bucket = 4,
 777                 .socket_id = 0,
 778         };
 779
 780         /* this is a sanity check for "same name" test
 781          * creating this hash will check if we are actually able to create
 782          * multiple hashes with different names (instead of having just one).
 783          */
 784         struct rte_fbk_hash_params different_name = {
 785                 .name = "different_name",                       /* different name */
 786                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 787                 .entries_per_bucket = 4,
 788                 .socket_id = 0,
 789         };
 790
 791         struct rte_fbk_hash_params params_jhash = {
 792                 .name = "valid",
 793                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 794                 .entries_per_bucket = 4,
 795                 .socket_id = 0,
 796                 .hash_func = rte_jhash_1word,              /* Tests for different hash_func */
 797                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
 798         };
 799
 800         struct rte_fbk_hash_params params_nohash = {
 801                 .name = "valid nohash",
 802                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 803                 .entries_per_bucket = 4,
 804                 .socket_id = 0,
 805                 .hash_func = NULL,                            /* Tests for null hash_func */
 806                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
 807         };
 808
 809         struct rte_fbk_hash_table *handle, *tmp;
 810         uint32_t keys[5] =
 811                 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
 812         uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
 813         int status;
 814         unsigned i;
 815         double used_entries;
 816
 817         /* Try creating hashes with invalid parameters */
 818         printf("# Testing hash creation with invalid parameters "
 819                         "- expect error msgs\n");
 820         handle = rte_fbk_hash_create(&invalid_params_1);
 821         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 822
 823         handle = rte_fbk_hash_create(&invalid_params_2);
 824         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 825
 826         handle = rte_fbk_hash_create(&invalid_params_3);
 827         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 828
 829         handle = rte_fbk_hash_create(&invalid_params_4);
 830         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 831
 832         handle = rte_fbk_hash_create(&invalid_params_5);
 833         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 834
 835         handle = rte_fbk_hash_create(&invalid_params_6);
 836         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 837
 838         handle = rte_fbk_hash_create(&invalid_params_7);
 839         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 840
 841         handle = rte_fbk_hash_create(&invalid_params_8);
 842         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
 843
 844         handle = rte_fbk_hash_create(&invalid_params_same_name_1);
 845         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
 846
 847         tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
 848         if (tmp != NULL)
 849                 rte_fbk_hash_free(tmp);
 850         RETURN_IF_ERROR_FBK(tmp != NULL, "fbk hash creation should have failed");
 851
 852         /* we are not freeing  handle here because we need a hash list
 853          * to be not empty for the next test */
 854
 855         /* create a hash in non-empty list - good for coverage */
 856         tmp = rte_fbk_hash_create(&different_name);
 857         RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
 858
 859         /* free both hashes */
 860         rte_fbk_hash_free(handle);
 861         rte_fbk_hash_free(tmp);
 862
 863         /* Create empty jhash hash. */
 864         handle = rte_fbk_hash_create(&params_jhash);
 865         RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
 866
 867         /* Cleanup. */
 868         rte_fbk_hash_free(handle);
 869
 870         /* Create empty jhash hash. */
 871         handle = rte_fbk_hash_create(&params_nohash);
 872         RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
 873
 874         /* Cleanup. */
 875         rte_fbk_hash_free(handle);
 876
 877         /* Create empty hash. */
 878         handle = rte_fbk_hash_create(&params);
 879         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
 880
 881         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
 882         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
 883                                 "load factor right after creation is not zero but it should be");
 884         /* Add keys. */
 885         for (i = 0; i < 5; i++) {
 886                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
 887                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
 888         }
 889
 890         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
 891         RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
 892                                 "load factor now is not as expected");
 893         /* Find value of added keys. */
 894         for (i = 0; i < 5; i++) {
 895                 status = rte_fbk_hash_lookup(handle, keys[i]);
 896                 RETURN_IF_ERROR_FBK(status != vals[i],
 897                                 "fbk hash lookup failed");
 898         }
 899
 900         /* Change value of added keys. */
 901         for (i = 0; i < 5; i++) {
 902                 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
 903                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
 904         }
 905
 906         /* Find new values. */
 907         for (i = 0; i < 5; i++) {
 908                 status = rte_fbk_hash_lookup(handle, keys[i]);
 909                 RETURN_IF_ERROR_FBK(status != vals[4-i],
 910                                 "fbk hash lookup failed");
 911         }
 912
 913         /* Delete keys individually. */
 914         for (i = 0; i < 5; i++) {
 915                 status = rte_fbk_hash_delete_key(handle, keys[i]);
 916                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
 917         }
 918
 919         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
 920         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
 921                                 "load factor right after deletion is not zero but it should be");
 922         /* Lookup should now fail. */
 923         for (i = 0; i < 5; i++) {
 924                 status = rte_fbk_hash_lookup(handle, keys[i]);
 925                 RETURN_IF_ERROR_FBK(status == 0,
 926                                 "fbk hash lookup should have failed");
 927         }
 928
 929         /* Add keys again. */
 930         for (i = 0; i < 5; i++) {
 931                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
 932                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
 933         }
 934
 935         /* Make sure they were added. */
 936         for (i = 0; i < 5; i++) {
 937                 status = rte_fbk_hash_lookup(handle, keys[i]);
 938                 RETURN_IF_ERROR_FBK(status != vals[i],
 939                                 "fbk hash lookup failed");
 940         }
 941
 942         /* Clear all entries. */
 943         rte_fbk_hash_clear_all(handle);
 944
 945         /* Lookup should fail. */
 946         for (i = 0; i < 5; i++) {
 947                 status = rte_fbk_hash_lookup(handle, keys[i]);
 948                 RETURN_IF_ERROR_FBK(status == 0,
 949                                 "fbk hash lookup should have failed");
 950         }
 951
 952         /* coverage */
 953
 954         /* fill up the hash_table */
 955         for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
 956                 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
 957
 958         /* Find non-existent key in a full hashtable */
 959         status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
 960         RETURN_IF_ERROR_FBK(status != -ENOENT,
 961                         "fbk hash lookup succeeded");
 962
 963         /* Delete non-existent key in a full hashtable */
 964         status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
 965         RETURN_IF_ERROR_FBK(status != -ENOENT,
 966                         "fbk hash delete succeeded");
 967
 968         /* Delete one key from a full hashtable */
 969         status = rte_fbk_hash_delete_key(handle, 1);
 970         RETURN_IF_ERROR_FBK(status != 0,
 971                         "fbk hash delete failed");
 972
 973         /* Clear all entries. */
 974         rte_fbk_hash_clear_all(handle);
 975
 976         /* Cleanup. */
 977         rte_fbk_hash_free(handle);
 978
 979         /* Cover the NULL case. */
 980         rte_fbk_hash_free(0);
 981
 982         return 0;
 983 }
 984
 985 /*
 986  * Sequence of operations for find existing fbk hash table
 987  *
 988  *  - create table
 989  *  - find existing table: hit
 990  *  - find non-existing table: miss
 991  *
 992  */
 993 static int test_fbk_hash_find_existing(void)
 994 {
 995         struct rte_fbk_hash_params params = {
 996                         .name = "fbk_hash_find_existing",
 997                         .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
 998                         .entries_per_bucket = 4,
 999                         .socket_id = 0,
1000         };
1001         struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1002
1003         /* Create hash table. */
1004         handle = rte_fbk_hash_create(&params);
1005         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1006
1007         /* Try to find existing fbk hash table */
1008         result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
1009         RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
1010
1011         /* Try to find non-existing fbk hash table */
1012         result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1013         RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
1014
1015         /* Cleanup. */
1016         rte_fbk_hash_free(handle);
1017
1018         return 0;
1019 }
1020
1021 #define BUCKET_ENTRIES 4
1022 /*
1023  * Do tests for hash creation with bad parameters.
1024  */
1025 static int test_hash_creation_with_bad_parameters(void)
1026 {
1027         struct rte_hash *handle, *tmp;
1028         struct rte_hash_parameters params;
1029
1030         handle = rte_hash_create(NULL);
1031         if (handle != NULL) {
1032                 rte_hash_free(handle);
1033                 printf("Impossible creating hash sucessfully without any parameter\n");
1034                 return -1;
1035         }
1036
1037         memcpy(&params, &ut_params, sizeof(params));
1038         params.name = "creation_with_bad_parameters_0";
1039         params.entries = RTE_HASH_ENTRIES_MAX + 1;
1040         handle = rte_hash_create(&params);
1041         if (handle != NULL) {
1042                 rte_hash_free(handle);
1043                 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
1044                 return -1;
1045         }
1046
1047         memcpy(&params, &ut_params, sizeof(params));
1048         params.name = "creation_with_bad_parameters_2";
1049         params.entries = BUCKET_ENTRIES - 1;
1050         handle = rte_hash_create(&params);
1051         if (handle != NULL) {
1052                 rte_hash_free(handle);
1053                 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
1054                 return -1;
1055         }
1056
1057         memcpy(&params, &ut_params, sizeof(params));
1058         params.name = "creation_with_bad_parameters_3";
1059         params.key_len = 0;
1060         handle = rte_hash_create(&params);
1061         if (handle != NULL) {
1062                 rte_hash_free(handle);
1063                 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1064                 return -1;
1065         }
1066
1067         memcpy(&params, &ut_params, sizeof(params));
1068         params.name = "creation_with_bad_parameters_4";
1069         params.socket_id = RTE_MAX_NUMA_NODES + 1;
1070         handle = rte_hash_create(&params);
1071         if (handle != NULL) {
1072                 rte_hash_free(handle);
1073                 printf("Impossible creating hash sucessfully with invalid socket\n");
1074                 return -1;
1075         }
1076
1077         /* test with same name should fail */
1078         memcpy(&params, &ut_params, sizeof(params));
1079         params.name = "same_name";
1080         handle = rte_hash_create(&params);
1081         if (handle == NULL) {
1082                 printf("Cannot create first hash table with 'same_name'\n");
1083                 return -1;
1084         }
1085         tmp = rte_hash_create(&params);
1086         if (tmp != NULL) {
1087                 printf("Creation of hash table with same name should fail\n");
1088                 rte_hash_free(handle);
1089                 rte_hash_free(tmp);
1090                 return -1;
1091         }
1092         rte_hash_free(handle);
1093
1094         printf("# Test successful. No more errors expected\n");
1095
1096         return 0;
1097 }
1098
1099 /*
1100  * Do tests for hash creation with parameters that look incorrect
1101  * but are actually valid.
1102  */
1103 static int
1104 test_hash_creation_with_good_parameters(void)
1105 {
1106         struct rte_hash *handle;
1107         struct rte_hash_parameters params;
1108
1109         /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1110         memcpy(&params, &ut_params, sizeof(params));
1111         params.name = "name";
1112         params.hash_func = NULL;
1113         handle = rte_hash_create(&params);
1114         if (handle == NULL) {
1115                 printf("Creating hash with null hash_func failed\n");
1116                 return -1;
1117         }
1118
1119         rte_hash_free(handle);
1120
1121         return 0;
1122 }
1123
1124 #define ITERATIONS 3
1125 /*
1126  * Test to see the average table utilization (entries added/max entries)
1127  * before hitting a random entry that cannot be added
1128  */
1129 static int test_average_table_utilization(void)
1130 {
1131         struct rte_hash *handle;
1132         uint8_t simple_key[MAX_KEYSIZE];
1133         unsigned i, j;
1134         unsigned added_keys, average_keys_added = 0;
1135         int ret;
1136
1137         printf("\n# Running test to determine average utilization"
1138                "\n  before adding elements begins to fail\n");
1139         printf("Measuring performance, please wait");
1140         fflush(stdout);
1141         ut_params.entries = 1 << 16;
1142         ut_params.name = "test_average_utilization";
1143         ut_params.hash_func = rte_jhash;
1144         handle = rte_hash_create(&ut_params);
1145         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1146
1147         for (j = 0; j < ITERATIONS; j++) {
1148                 ret = 0;
1149                 /* Add random entries until key cannot be added */
1150                 for (added_keys = 0; ret >= 0; added_keys++) {
1151                         for (i = 0; i < ut_params.key_len; i++)
1152                                 simple_key[i] = rte_rand() % 255;
1153                         ret = rte_hash_add_key(handle, simple_key);
1154                 }
1155                 if (ret != -ENOSPC) {
1156                         printf("Unexpected error when adding keys\n");
1157                         rte_hash_free(handle);
1158                         return -1;
1159                 }
1160
1161                 average_keys_added += added_keys;
1162
1163                 /* Reset the table */
1164                 rte_hash_reset(handle);
1165
1166                 /* Print a dot to show progress on operations */
1167                 printf(".");
1168                 fflush(stdout);
1169         }
1170
1171         average_keys_added /= ITERATIONS;
1172
1173         printf("\nAverage table utilization = %.2f%% (%u/%u)\n",
1174                 ((double) average_keys_added / ut_params.entries * 100),
1175                 average_keys_added, ut_params.entries);
1176         rte_hash_free(handle);
1177
1178         return 0;
1179 }
1180
1181 #define NUM_ENTRIES 256
1182 static int test_hash_iteration(void)
1183 {
1184         struct rte_hash *handle;
1185         unsigned i;
1186         uint8_t keys[NUM_ENTRIES][MAX_KEYSIZE];
1187         const void *next_key;
1188         void *next_data;
1189         void *data[NUM_ENTRIES];
1190         unsigned added_keys;
1191         uint32_t iter = 0;
1192         int ret = 0;
1193
1194         ut_params.entries = NUM_ENTRIES;
1195         ut_params.name = "test_hash_iteration";
1196         ut_params.hash_func = rte_jhash;
1197         ut_params.key_len = 16;
1198         handle = rte_hash_create(&ut_params);
1199         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1200
1201         /* Add random entries until key cannot be added */
1202         for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) {
1203                 data[added_keys] = (void *) ((uintptr_t) rte_rand());
1204                 for (i = 0; i < ut_params.key_len; i++)
1205                         keys[added_keys][i] = rte_rand() % 255;
1206                 ret = rte_hash_add_key_data(handle, keys[added_keys], data[added_keys]);
1207                 if (ret < 0)
1208                         break;
1209         }
1210
1211         /* Iterate through the hash table */
1212         while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) {
1213                 /* Search for the key in the list of keys added */
1214                 for (i = 0; i < NUM_ENTRIES; i++) {
1215                         if (memcmp(next_key, keys[i], ut_params.key_len) == 0) {
1216                                 if (next_data != data[i]) {
1217                                         printf("Data found in the hash table is"
1218                                                "not the data added with the key\n");
1219                                         goto err;
1220                                 }
1221                                 added_keys--;
1222                                 break;
1223                         }
1224                 }
1225                 if (i == NUM_ENTRIES) {
1226                         printf("Key found in the hash table was not added\n");
1227                         goto err;
1228                 }
1229         }
1230
1231         /* Check if all keys have been iterated */
1232         if (added_keys != 0) {
1233                 printf("There were still %u keys to iterate\n", added_keys);
1234                 goto err;
1235         }
1236
1237         rte_hash_free(handle);
1238         return 0;
1239
1240 err:
1241         rte_hash_free(handle);
1242         return -1;
1243 }
1244
1245 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1246                         0x04, 0x05, 0x06, 0x07,
1247                         0x08, 0x09, 0x0a, 0x0b,
1248                         0x0c, 0x0d, 0x0e, 0x0f};
1249 static struct rte_hash_parameters hash_params_ex = {
1250         .name = NULL,
1251         .entries = 64,
1252         .key_len = 0,
1253         .hash_func = NULL,
1254         .hash_func_init_val = 0,
1255         .socket_id = 0,
1256 };
1257
1258 /*
1259  * add/delete key with jhash2
1260  */
1261 static int
1262 test_hash_add_delete_jhash2(void)
1263 {
1264         int ret = -1;
1265         struct rte_hash *handle;
1266         int32_t pos1, pos2;
1267
1268         hash_params_ex.name = "hash_test_jhash2";
1269         hash_params_ex.key_len = 4;
1270         hash_params_ex.hash_func = (rte_hash_function)rte_jhash_32b;
1271
1272         handle = rte_hash_create(&hash_params_ex);
1273         if (handle == NULL) {
1274                 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1275                 goto fail_jhash2;
1276         }
1277         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1278         if (pos1 < 0) {
1279                 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1280                 goto fail_jhash2;
1281         }
1282
1283         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1284         if (pos2 < 0 || pos1 != pos2) {
1285                 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1286                 goto fail_jhash2;
1287         }
1288         ret = 0;
1289
1290 fail_jhash2:
1291         if (handle != NULL)
1292                 rte_hash_free(handle);
1293
1294         return ret;
1295 }
1296
1297 /*
1298  * add/delete (2) key with jhash2
1299  */
1300 static int
1301 test_hash_add_delete_2_jhash2(void)
1302 {
1303         int ret = -1;
1304         struct rte_hash *handle;
1305         int32_t pos1, pos2;
1306
1307         hash_params_ex.name = "hash_test_2_jhash2";
1308         hash_params_ex.key_len = 8;
1309         hash_params_ex.hash_func = (rte_hash_function)rte_jhash_32b;
1310
1311         handle = rte_hash_create(&hash_params_ex);
1312         if (handle == NULL)
1313                 goto fail_2_jhash2;
1314
1315         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1316         if (pos1 < 0)
1317                 goto fail_2_jhash2;
1318
1319         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1320         if (pos2 < 0 || pos1 != pos2)
1321                 goto fail_2_jhash2;
1322
1323         ret = 0;
1324
1325 fail_2_jhash2:
1326         if (handle != NULL)
1327                 rte_hash_free(handle);
1328
1329         return ret;
1330 }
1331
1332 static uint32_t
1333 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1334 {
1335         const uint32_t *k = key;
1336
1337         RTE_SET_USED(length);
1338
1339         return rte_jhash_1word(k[0], initval);
1340 }
1341
1342 static uint32_t
1343 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1344 {
1345         const uint32_t *k = key;
1346
1347         RTE_SET_USED(length);
1348
1349         return rte_jhash_2words(k[0], k[1], initval);
1350 }
1351
1352 static uint32_t
1353 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1354 {
1355         const uint32_t *k = key;
1356
1357         RTE_SET_USED(length);
1358
1359         return rte_jhash_3words(k[0], k[1], k[2], initval);
1360 }
1361
1362 /*
1363  * add/delete key with jhash 1word
1364  */
1365 static int
1366 test_hash_add_delete_jhash_1word(void)
1367 {
1368         int ret = -1;
1369         struct rte_hash *handle;
1370         int32_t pos1, pos2;
1371
1372         hash_params_ex.name = "hash_test_jhash_1word";
1373         hash_params_ex.key_len = 4;
1374         hash_params_ex.hash_func = test_hash_jhash_1word;
1375
1376         handle = rte_hash_create(&hash_params_ex);
1377         if (handle == NULL)
1378                 goto fail_jhash_1word;
1379
1380         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1381         if (pos1 < 0)
1382                 goto fail_jhash_1word;
1383
1384         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1385         if (pos2 < 0 || pos1 != pos2)
1386                 goto fail_jhash_1word;
1387
1388         ret = 0;
1389
1390 fail_jhash_1word:
1391         if (handle != NULL)
1392                 rte_hash_free(handle);
1393
1394         return ret;
1395 }
1396
1397 /*
1398  * add/delete key with jhash 2word
1399  */
1400 static int
1401 test_hash_add_delete_jhash_2word(void)
1402 {
1403         int ret = -1;
1404         struct rte_hash *handle;
1405         int32_t pos1, pos2;
1406
1407         hash_params_ex.name = "hash_test_jhash_2word";
1408         hash_params_ex.key_len = 8;
1409         hash_params_ex.hash_func = test_hash_jhash_2word;
1410
1411         handle = rte_hash_create(&hash_params_ex);
1412         if (handle == NULL)
1413                 goto fail_jhash_2word;
1414
1415         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1416         if (pos1 < 0)
1417                 goto fail_jhash_2word;
1418
1419         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1420         if (pos2 < 0 || pos1 != pos2)
1421                 goto fail_jhash_2word;
1422
1423         ret = 0;
1424
1425 fail_jhash_2word:
1426         if (handle != NULL)
1427                 rte_hash_free(handle);
1428
1429         return ret;
1430 }
1431
1432 /*
1433  * add/delete key with jhash 3word
1434  */
1435 static int
1436 test_hash_add_delete_jhash_3word(void)
1437 {
1438         int ret = -1;
1439         struct rte_hash *handle;
1440         int32_t pos1, pos2;
1441
1442         hash_params_ex.name = "hash_test_jhash_3word";
1443         hash_params_ex.key_len = 12;
1444         hash_params_ex.hash_func = test_hash_jhash_3word;
1445
1446         handle = rte_hash_create(&hash_params_ex);
1447         if (handle == NULL)
1448                 goto fail_jhash_3word;
1449
1450         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1451         if (pos1 < 0)
1452                 goto fail_jhash_3word;
1453
1454         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1455         if (pos2 < 0 || pos1 != pos2)
1456                 goto fail_jhash_3word;
1457
1458         ret = 0;
1459
1460 fail_jhash_3word:
1461         if (handle != NULL)
1462                 rte_hash_free(handle);
1463
1464         return ret;
1465 }
1466
1467 /*
1468  * Do all unit and performance tests.
1469  */
1470 static int
1471 test_hash(void)
1472 {
1473         if (test_add_delete() < 0)
1474                 return -1;
1475         if (test_hash_add_delete_jhash2() < 0)
1476                 return -1;
1477         if (test_hash_add_delete_2_jhash2() < 0)
1478                 return -1;
1479         if (test_hash_add_delete_jhash_1word() < 0)
1480                 return -1;
1481         if (test_hash_add_delete_jhash_2word() < 0)
1482                 return -1;
1483         if (test_hash_add_delete_jhash_3word() < 0)
1484                 return -1;
1485         if (test_hash_get_key_with_position() < 0)
1486                 return -1;
1487         if (test_hash_find_existing() < 0)
1488                 return -1;
1489         if (test_add_update_delete() < 0)
1490                 return -1;
1491         if (test_five_keys() < 0)
1492                 return -1;
1493         if (test_full_bucket() < 0)
1494                 return -1;
1495
1496         if (test_fbk_hash_find_existing() < 0)
1497                 return -1;
1498         if (fbk_hash_unit_test() < 0)
1499                 return -1;
1500         if (test_hash_creation_with_bad_parameters() < 0)
1501                 return -1;
1502         if (test_hash_creation_with_good_parameters() < 0)
1503                 return -1;
1504         if (test_average_table_utilization() < 0)
1505                 return -1;
1506         if (test_hash_iteration() < 0)
1507                 return -1;
1508
1509         run_hash_func_tests();
1510
1511         if (test_crc32_hash_alg_equiv() < 0)
1512                 return -1;
1513
1514         return 0;
1515 }
1516
1517 REGISTER_TEST_COMMAND(hash_autotest, test_hash);