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