test/test/test_hash.c

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