app/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 #define RETURN_IF_ERROR_RCU_QSBR(cond, str, ...) do {                   \
  64         if (cond) {                                                     \
  65                 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
  66                 if (rcu_cfg.mode == RTE_HASH_QSBR_MODE_SYNC) {          \
  67                         writer_done = 1;                                \
  68                         /* Wait until reader exited. */                 \
  69                         rte_eal_mp_wait_lcore();                        \
  70                 }                                                       \
  71                 rte_hash_free(g_handle);                                \
  72                 rte_free(g_qsv);                                        \
  73                 return -1;                                              \
  74         }                                                               \
  75 } while (0)
  76
  77 /*
  78  * 5-tuple key type.
  79  * Should be packed to avoid holes with potentially
  80  * undefined content in the middle.
  81  */
  82 struct flow_key {
  83         uint32_t ip_src;
  84         uint32_t ip_dst;
  85         uint16_t port_src;
  86         uint16_t port_dst;
  87         uint32_t proto;
  88 } __rte_packed;
  89
  90 /*
  91  * Hash function that always returns the same value, to easily test what
  92  * happens when a bucket is full.
  93  */
  94 static uint32_t pseudo_hash(__rte_unused const void *keys,
  95                             __rte_unused uint32_t key_len,
  96                             __rte_unused uint32_t init_val)
  97 {
  98         return 3;
  99 }
 100
 101 RTE_LOG_REGISTER(hash_logtype_test, test.hash, INFO);
 102
 103 /*
 104  * Print out result of unit test hash operation.
 105  */
 106 static void print_key_info(const char *msg, const struct flow_key *key,
 107                                                                 int32_t pos)
 108 {
 109         const uint8_t *p = (const uint8_t *)key;
 110         unsigned int i;
 111
 112         rte_log(RTE_LOG_DEBUG, hash_logtype_test, "%s key:0x", msg);
 113         for (i = 0; i < sizeof(struct flow_key); i++)
 114                 rte_log(RTE_LOG_DEBUG, hash_logtype_test, "%02X", p[i]);
 115         rte_log(RTE_LOG_DEBUG, hash_logtype_test, " @ pos %d\n", pos);
 116 }
 117
 118 /* Keys used by unit test functions */
 119 static struct flow_key keys[5] = { {
 120         .ip_src = RTE_IPV4(0x03, 0x02, 0x01, 0x00),
 121         .ip_dst = RTE_IPV4(0x07, 0x06, 0x05, 0x04),
 122         .port_src = 0x0908,
 123         .port_dst = 0x0b0a,
 124         .proto = 0x0c,
 125 }, {
 126         .ip_src = RTE_IPV4(0x13, 0x12, 0x11, 0x10),
 127         .ip_dst = RTE_IPV4(0x17, 0x16, 0x15, 0x14),
 128         .port_src = 0x1918,
 129         .port_dst = 0x1b1a,
 130         .proto = 0x1c,
 131 }, {
 132         .ip_src = RTE_IPV4(0x23, 0x22, 0x21, 0x20),
 133         .ip_dst = RTE_IPV4(0x27, 0x26, 0x25, 0x24),
 134         .port_src = 0x2928,
 135         .port_dst = 0x2b2a,
 136         .proto = 0x2c,
 137 }, {
 138         .ip_src = RTE_IPV4(0x33, 0x32, 0x31, 0x30),
 139         .ip_dst = RTE_IPV4(0x37, 0x36, 0x35, 0x34),
 140         .port_src = 0x3938,
 141         .port_dst = 0x3b3a,
 142         .proto = 0x3c,
 143 }, {
 144         .ip_src = RTE_IPV4(0x43, 0x42, 0x41, 0x40),
 145         .ip_dst = RTE_IPV4(0x47, 0x46, 0x45, 0x44),
 146         .port_src = 0x4948,
 147         .port_dst = 0x4b4a,
 148         .proto = 0x4c,
 149 } };
 150
 151 /* Parameters used for hash table in unit test functions. Name set later. */
 152 static struct rte_hash_parameters ut_params = {
 153         .entries = 64,
 154         .key_len = sizeof(struct flow_key),
 155         .hash_func = rte_jhash,
 156         .hash_func_init_val = 0,
 157         .socket_id = 0,
 158 };
 159
 160 #define CRC32_ITERATIONS (1U << 10)
 161 #define CRC32_DWORDS (1U << 6)
 162 /*
 163  * Test if all CRC32 implementations yield the same hash value
 164  */
 165 static int
 166 test_crc32_hash_alg_equiv(void)
 167 {
 168         uint32_t hash_val;
 169         uint32_t init_val;
 170         uint64_t data64[CRC32_DWORDS];
 171         unsigned i, j;
 172         size_t data_len;
 173
 174         printf("\n# CRC32 implementations equivalence test\n");
 175         for (i = 0; i < CRC32_ITERATIONS; i++) {
 176                 /* Randomizing data_len of data set */
 177                 data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1);
 178                 init_val = (uint32_t) rte_rand();
 179
 180                 /* Fill the data set */
 181                 for (j = 0; j < CRC32_DWORDS; j++)
 182                         data64[j] = rte_rand();
 183
 184                 /* Calculate software CRC32 */
 185                 rte_hash_crc_set_alg(CRC32_SW);
 186                 hash_val = rte_hash_crc(data64, data_len, init_val);
 187
 188                 /* Check against 4-byte-operand sse4.2 CRC32 if available */
 189                 rte_hash_crc_set_alg(CRC32_SSE42);
 190                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 191                         printf("Failed checking CRC32_SW against CRC32_SSE42\n");
 192                         break;
 193                 }
 194
 195                 /* Check against 8-byte-operand sse4.2 CRC32 if available */
 196                 rte_hash_crc_set_alg(CRC32_SSE42_x64);
 197                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 198                         printf("Failed checking CRC32_SW against CRC32_SSE42_x64\n");
 199                         break;
 200                 }
 201
 202                 /* Check against 8-byte-operand ARM64 CRC32 if available */
 203                 rte_hash_crc_set_alg(CRC32_ARM64);
 204                 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
 205                         printf("Failed checking CRC32_SW against CRC32_ARM64\n");
 206                         break;
 207                 }
 208         }
 209
 210         /* Resetting to best available algorithm */
 211         rte_hash_crc_set_alg(CRC32_SSE42_x64);
 212
 213         if (i == CRC32_ITERATIONS)
 214                 return 0;
 215
 216         printf("Failed test data (hex, %zu bytes total):\n", data_len);
 217         for (j = 0; j < data_len; j++)
 218                 printf("%02X%c", ((uint8_t *)data64)[j],
 219                                 ((j+1) % 16 == 0 || j == data_len - 1) ? '\n' : ' ');
 220
 221         return -1;
 222 }
 223
 224 /*
 225  * Test a hash function.
 226  */
 227 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
 228                 uint32_t key_len)
 229 {
 230         static uint8_t key[MAX_KEYSIZE];
 231         unsigned i;
 232
 233
 234         for (i = 0; i < key_len; i++)
 235                 key[i] = (uint8_t) rte_rand();
 236
 237         /* just to be on the safe side */
 238         if (!f)
 239                 return;
 240
 241         f(key, key_len, init_val);
 242 }
 243
 244 /*
 245  * Test all hash functions.
 246  */
 247 static void run_hash_func_tests(void)
 248 {
 249         unsigned i, j, k;
 250
 251         for (i = 0; i < RTE_DIM(hashtest_funcs); i++) {
 252                 for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
 253                         for (k = 0; k < RTE_DIM(hashtest_key_lens); k++) {
 254                                 run_hash_func_test(hashtest_funcs[i],
 255                                                 hashtest_initvals[j],
 256                                                 hashtest_key_lens[k]);
 257                         }
 258                 }
 259         }
 260 }
 261
 262 /*
 263  * Basic sequence of operations for a single key:
 264  *      - add
 265  *      - lookup (hit)
 266  *      - delete
 267  *      - lookup (miss)
 268  *
 269  * Repeat the test case when 'free on delete' is disabled.
 270  *      - add
 271  *      - lookup (hit)
 272  *      - delete
 273  *      - lookup (miss)
 274  *      - free
 275  */
 276 static int test_add_delete(void)
 277 {
 278         struct rte_hash *handle;
 279         /* test with standard add/lookup/delete functions */
 280         int pos0, expectedPos0;
 281
 282         ut_params.name = "test1";
 283         handle = rte_hash_create(&ut_params);
 284         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 285
 286         pos0 = rte_hash_add_key(handle, &keys[0]);
 287         print_key_info("Add", &keys[0], pos0);
 288         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 289         expectedPos0 = pos0;
 290
 291         pos0 = rte_hash_lookup(handle, &keys[0]);
 292         print_key_info("Lkp", &keys[0], pos0);
 293         RETURN_IF_ERROR(pos0 != expectedPos0,
 294                         "failed to find key (pos0=%d)", pos0);
 295
 296         pos0 = rte_hash_del_key(handle, &keys[0]);
 297         print_key_info("Del", &keys[0], pos0);
 298         RETURN_IF_ERROR(pos0 != expectedPos0,
 299                         "failed to delete key (pos0=%d)", pos0);
 300
 301         pos0 = rte_hash_lookup(handle, &keys[0]);
 302         print_key_info("Lkp", &keys[0], pos0);
 303         RETURN_IF_ERROR(pos0 != -ENOENT,
 304                         "fail: found key after deleting! (pos0=%d)", pos0);
 305
 306         rte_hash_free(handle);
 307
 308         /* repeat test with precomputed hash functions */
 309         hash_sig_t hash_value;
 310         int pos1, expectedPos1, delPos1;
 311
 312         ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
 313         handle = rte_hash_create(&ut_params);
 314         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 315         ut_params.extra_flag = 0;
 316
 317         hash_value = rte_hash_hash(handle, &keys[0]);
 318         pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
 319         print_key_info("Add", &keys[0], pos1);
 320         RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
 321         expectedPos1 = 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 != expectedPos1,
 326                         "failed to find key (pos1=%d)", pos1);
 327
 328         pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
 329         print_key_info("Del", &keys[0], pos1);
 330         RETURN_IF_ERROR(pos1 != expectedPos1,
 331                         "failed to delete key (pos1=%d)", pos1);
 332         delPos1 = pos1;
 333
 334         pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
 335         print_key_info("Lkp", &keys[0], pos1);
 336         RETURN_IF_ERROR(pos1 != -ENOENT,
 337                         "fail: found key after deleting! (pos1=%d)", pos1);
 338
 339         pos1 = rte_hash_free_key_with_position(handle, delPos1);
 340         print_key_info("Free", &keys[0], delPos1);
 341         RETURN_IF_ERROR(pos1 != 0,
 342                         "failed to free key (pos1=%d)", delPos1);
 343
 344         rte_hash_free(handle);
 345
 346         return 0;
 347 }
 348
 349 /*
 350  * Sequence of operations for a single key:
 351  *      - delete: miss
 352  *      - add
 353  *      - lookup: hit
 354  *      - add: update
 355  *      - lookup: hit (updated data)
 356  *      - delete: hit
 357  *      - delete: miss
 358  *      - lookup: miss
 359  */
 360 static int test_add_update_delete(void)
 361 {
 362         struct rte_hash *handle;
 363         int pos0, expectedPos0;
 364
 365         ut_params.name = "test2";
 366         handle = rte_hash_create(&ut_params);
 367         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 368
 369         pos0 = rte_hash_del_key(handle, &keys[0]);
 370         print_key_info("Del", &keys[0], pos0);
 371         RETURN_IF_ERROR(pos0 != -ENOENT,
 372                         "fail: found non-existent key (pos0=%d)", pos0);
 373
 374         pos0 = rte_hash_add_key(handle, &keys[0]);
 375         print_key_info("Add", &keys[0], pos0);
 376         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 377         expectedPos0 = pos0;
 378
 379         pos0 = rte_hash_lookup(handle, &keys[0]);
 380         print_key_info("Lkp", &keys[0], pos0);
 381         RETURN_IF_ERROR(pos0 != expectedPos0,
 382                         "failed to find key (pos0=%d)", pos0);
 383
 384         pos0 = rte_hash_add_key(handle, &keys[0]);
 385         print_key_info("Add", &keys[0], pos0);
 386         RETURN_IF_ERROR(pos0 != expectedPos0,
 387                         "failed to re-add key (pos0=%d)", pos0);
 388
 389         pos0 = rte_hash_lookup(handle, &keys[0]);
 390         print_key_info("Lkp", &keys[0], pos0);
 391         RETURN_IF_ERROR(pos0 != expectedPos0,
 392                         "failed to find key (pos0=%d)", pos0);
 393
 394         pos0 = rte_hash_del_key(handle, &keys[0]);
 395         print_key_info("Del", &keys[0], pos0);
 396         RETURN_IF_ERROR(pos0 != expectedPos0,
 397                         "failed to delete key (pos0=%d)", pos0);
 398
 399         pos0 = rte_hash_del_key(handle, &keys[0]);
 400         print_key_info("Del", &keys[0], pos0);
 401         RETURN_IF_ERROR(pos0 != -ENOENT,
 402                         "fail: deleted already deleted key (pos0=%d)", pos0);
 403
 404         pos0 = rte_hash_lookup(handle, &keys[0]);
 405         print_key_info("Lkp", &keys[0], pos0);
 406         RETURN_IF_ERROR(pos0 != -ENOENT,
 407                         "fail: found key after deleting! (pos0=%d)", pos0);
 408
 409         rte_hash_free(handle);
 410         return 0;
 411 }
 412
 413 /*
 414  * Sequence of operations for a single key with 'disable free on del' set:
 415  *      - delete: miss
 416  *      - add
 417  *      - lookup: hit
 418  *      - add: update
 419  *      - lookup: hit (updated data)
 420  *      - delete: hit
 421  *      - delete: miss
 422  *      - lookup: miss
 423  *      - free: hit
 424  *      - lookup: miss
 425  */
 426 static int test_add_update_delete_free(void)
 427 {
 428         struct rte_hash *handle;
 429         int pos0, expectedPos0, delPos0, result;
 430
 431         ut_params.name = "test2";
 432         ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
 433         handle = rte_hash_create(&ut_params);
 434         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 435         ut_params.extra_flag = 0;
 436
 437         pos0 = rte_hash_del_key(handle, &keys[0]);
 438         print_key_info("Del", &keys[0], pos0);
 439         RETURN_IF_ERROR(pos0 != -ENOENT,
 440                         "fail: found non-existent key (pos0=%d)", pos0);
 441
 442         pos0 = rte_hash_add_key(handle, &keys[0]);
 443         print_key_info("Add", &keys[0], pos0);
 444         RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
 445         expectedPos0 = pos0;
 446
 447         pos0 = rte_hash_lookup(handle, &keys[0]);
 448         print_key_info("Lkp", &keys[0], pos0);
 449         RETURN_IF_ERROR(pos0 != expectedPos0,
 450                         "failed to find key (pos0=%d)", pos0);
 451
 452         pos0 = rte_hash_add_key(handle, &keys[0]);
 453         print_key_info("Add", &keys[0], pos0);
 454         RETURN_IF_ERROR(pos0 != expectedPos0,
 455                         "failed to re-add key (pos0=%d)", pos0);
 456
 457         pos0 = rte_hash_lookup(handle, &keys[0]);
 458         print_key_info("Lkp", &keys[0], pos0);
 459         RETURN_IF_ERROR(pos0 != expectedPos0,
 460                         "failed to find key (pos0=%d)", pos0);
 461
 462         delPos0 = rte_hash_del_key(handle, &keys[0]);
 463         print_key_info("Del", &keys[0], delPos0);
 464         RETURN_IF_ERROR(delPos0 != expectedPos0,
 465                         "failed to delete key (pos0=%d)", delPos0);
 466
 467         pos0 = rte_hash_del_key(handle, &keys[0]);
 468         print_key_info("Del", &keys[0], pos0);
 469         RETURN_IF_ERROR(pos0 != -ENOENT,
 470                         "fail: deleted already deleted key (pos0=%d)", pos0);
 471
 472         pos0 = rte_hash_lookup(handle, &keys[0]);
 473         print_key_info("Lkp", &keys[0], pos0);
 474         RETURN_IF_ERROR(pos0 != -ENOENT,
 475                         "fail: found key after deleting! (pos0=%d)", pos0);
 476
 477         result = rte_hash_free_key_with_position(handle, delPos0);
 478         print_key_info("Free", &keys[0], delPos0);
 479         RETURN_IF_ERROR(result != 0,
 480                         "failed to free key (pos1=%d)", delPos0);
 481
 482         pos0 = rte_hash_lookup(handle, &keys[0]);
 483         print_key_info("Lkp", &keys[0], pos0);
 484         RETURN_IF_ERROR(pos0 != -ENOENT,
 485                         "fail: found key after deleting! (pos0=%d)", pos0);
 486
 487         rte_hash_free(handle);
 488         return 0;
 489 }
 490
 491 /*
 492  * Sequence of operations for a single key with 'rw concurrency lock free' set:
 493  *      - add
 494  *      - delete: hit
 495  *      - free: hit
 496  * Repeat the test case when 'multi writer add' is enabled.
 497  *      - add
 498  *      - delete: hit
 499  *      - free: hit
 500  */
 501 static int test_add_delete_free_lf(void)
 502 {
 503 /* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
 504 #define LCORE_CACHE_SIZE        64
 505         struct rte_hash *handle;
 506         hash_sig_t hash_value;
 507         int pos, expectedPos, delPos;
 508         uint8_t extra_flag;
 509         uint32_t i, ip_src;
 510
 511         extra_flag = ut_params.extra_flag;
 512         ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
 513         handle = rte_hash_create(&ut_params);
 514         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 515         ut_params.extra_flag = extra_flag;
 516
 517         /*
 518          * The number of iterations is at least the same as the number of slots
 519          * rte_hash allocates internally. This is to reveal potential issues of
 520          * not freeing keys successfully.
 521          */
 522         for (i = 0; i < ut_params.entries + 1; i++) {
 523                 hash_value = rte_hash_hash(handle, &keys[0]);
 524                 pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
 525                 print_key_info("Add", &keys[0], pos);
 526                 RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
 527                 expectedPos = pos;
 528
 529                 pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
 530                 print_key_info("Del", &keys[0], pos);
 531                 RETURN_IF_ERROR(pos != expectedPos,
 532                                 "failed to delete key (pos=%d)", pos);
 533                 delPos = pos;
 534
 535                 pos = rte_hash_free_key_with_position(handle, delPos);
 536                 print_key_info("Free", &keys[0], delPos);
 537                 RETURN_IF_ERROR(pos != 0,
 538                                 "failed to free key (pos=%d)", delPos);
 539         }
 540
 541         rte_hash_free(handle);
 542
 543         extra_flag = ut_params.extra_flag;
 544         ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
 545                                 RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
 546         handle = rte_hash_create(&ut_params);
 547         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 548         ut_params.extra_flag = extra_flag;
 549
 550         ip_src = keys[0].ip_src;
 551         /*
 552          * The number of iterations is at least the same as the number of slots
 553          * rte_hash allocates internally. This is to reveal potential issues of
 554          * not freeing keys successfully.
 555          */
 556         for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
 557                                         (LCORE_CACHE_SIZE - 1) + 1; i++) {
 558                 keys[0].ip_src++;
 559                 hash_value = rte_hash_hash(handle, &keys[0]);
 560                 pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
 561                 print_key_info("Add", &keys[0], pos);
 562                 RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
 563                 expectedPos = pos;
 564
 565                 pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
 566                 print_key_info("Del", &keys[0], pos);
 567                 RETURN_IF_ERROR(pos != expectedPos,
 568                         "failed to delete key (pos=%d)", pos);
 569                 delPos = pos;
 570
 571                 pos = rte_hash_free_key_with_position(handle, delPos);
 572                 print_key_info("Free", &keys[0], delPos);
 573                 RETURN_IF_ERROR(pos != 0,
 574                         "failed to free key (pos=%d)", delPos);
 575         }
 576         keys[0].ip_src = ip_src;
 577
 578         rte_hash_free(handle);
 579
 580         return 0;
 581 }
 582
 583 /*
 584  * Sequence of operations for retrieving a key with its position
 585  *
 586  *  - create table
 587  *  - add key
 588  *  - get the key with its position: hit
 589  *  - delete key
 590  *  - try to get the deleted key: miss
 591  *
 592  * Repeat the test case when 'free on delete' is disabled.
 593  *  - create table
 594  *  - add key
 595  *  - get the key with its position: hit
 596  *  - delete key
 597  *  - try to get the deleted key: hit
 598  *  - free key
 599  *  - try to get the deleted key: miss
 600  *
 601  */
 602 static int test_hash_get_key_with_position(void)
 603 {
 604         struct rte_hash *handle = NULL;
 605         int pos, expectedPos, delPos, result;
 606         void *key;
 607
 608         ut_params.name = "hash_get_key_w_pos";
 609         handle = rte_hash_create(&ut_params);
 610         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 611
 612         pos = rte_hash_add_key(handle, &keys[0]);
 613         print_key_info("Add", &keys[0], pos);
 614         RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
 615         expectedPos = pos;
 616
 617         result = rte_hash_get_key_with_position(handle, pos, &key);
 618         RETURN_IF_ERROR(result != 0, "error retrieving a key");
 619
 620         pos = rte_hash_del_key(handle, &keys[0]);
 621         print_key_info("Del", &keys[0], pos);
 622         RETURN_IF_ERROR(pos != expectedPos,
 623                         "failed to delete key (pos0=%d)", pos);
 624
 625         result = rte_hash_get_key_with_position(handle, pos, &key);
 626         RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
 627
 628         rte_hash_free(handle);
 629
 630         ut_params.name = "hash_get_key_w_pos";
 631         ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
 632         handle = rte_hash_create(&ut_params);
 633         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 634         ut_params.extra_flag = 0;
 635
 636         pos = rte_hash_add_key(handle, &keys[0]);
 637         print_key_info("Add", &keys[0], pos);
 638         RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
 639         expectedPos = pos;
 640
 641         result = rte_hash_get_key_with_position(handle, pos, &key);
 642         RETURN_IF_ERROR(result != 0, "error retrieving a key");
 643
 644         delPos = rte_hash_del_key(handle, &keys[0]);
 645         print_key_info("Del", &keys[0], delPos);
 646         RETURN_IF_ERROR(delPos != expectedPos,
 647                         "failed to delete key (pos0=%d)", delPos);
 648
 649         result = rte_hash_get_key_with_position(handle, delPos, &key);
 650         RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
 651
 652         result = rte_hash_free_key_with_position(handle, delPos);
 653         print_key_info("Free", &keys[0], delPos);
 654         RETURN_IF_ERROR(result != 0,
 655                         "failed to free key (pos1=%d)", delPos);
 656
 657         result = rte_hash_get_key_with_position(handle, delPos, &key);
 658         RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
 659
 660         rte_hash_free(handle);
 661         return 0;
 662 }
 663
 664 /*
 665  * Sequence of operations for find existing hash table
 666  *
 667  *  - create table
 668  *  - find existing table: hit
 669  *  - find non-existing table: miss
 670  *
 671  */
 672 static int test_hash_find_existing(void)
 673 {
 674         struct rte_hash *handle = NULL, *result = NULL;
 675
 676         /* Create hash table. */
 677         ut_params.name = "hash_find_existing";
 678         handle = rte_hash_create(&ut_params);
 679         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 680
 681         /* Try to find existing hash table */
 682         result = rte_hash_find_existing("hash_find_existing");
 683         RETURN_IF_ERROR(result != handle, "could not find existing hash table");
 684
 685         /* Try to find non-existing hash table */
 686         result = rte_hash_find_existing("hash_find_non_existing");
 687         RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
 688
 689         /* Cleanup. */
 690         rte_hash_free(handle);
 691
 692         return 0;
 693 }
 694
 695 /*
 696  * Sequence of operations for 5 keys
 697  *      - add keys
 698  *      - lookup keys: hit
 699  *      - add keys (update)
 700  *      - lookup keys: hit (updated data)
 701  *      - delete keys : hit
 702  *      - lookup keys: miss
 703  */
 704 static int test_five_keys(void)
 705 {
 706         struct rte_hash *handle;
 707         const void *key_array[5] = {0};
 708         int pos[5];
 709         int expected_pos[5];
 710         unsigned i;
 711         int ret;
 712
 713         ut_params.name = "test3";
 714         handle = rte_hash_create(&ut_params);
 715         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 716
 717         /* Add */
 718         for (i = 0; i < 5; i++) {
 719                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 720                 print_key_info("Add", &keys[i], pos[i]);
 721                 RETURN_IF_ERROR(pos[i] < 0,
 722                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 723                 expected_pos[i] = pos[i];
 724         }
 725
 726         /* Lookup */
 727         for(i = 0; i < 5; i++)
 728                 key_array[i] = &keys[i];
 729
 730         ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
 731         if(ret == 0)
 732                 for(i = 0; i < 5; i++) {
 733                         print_key_info("Lkp", key_array[i], pos[i]);
 734                         RETURN_IF_ERROR(pos[i] != expected_pos[i],
 735                                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 736                 }
 737
 738         /* Add - update */
 739         for (i = 0; i < 5; i++) {
 740                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 741                 print_key_info("Add", &keys[i], pos[i]);
 742                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 743                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
 744         }
 745
 746         /* Lookup */
 747         for (i = 0; i < 5; i++) {
 748                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 749                 print_key_info("Lkp", &keys[i], pos[i]);
 750                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 751                                 "failed to find key (pos[%u]=%d)", i, pos[i]);
 752         }
 753
 754         /* Delete */
 755         for (i = 0; i < 5; i++) {
 756                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 757                 print_key_info("Del", &keys[i], pos[i]);
 758                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 759                                 "failed to delete key (pos[%u]=%d)", i, pos[i]);
 760         }
 761
 762         /* Lookup */
 763         for (i = 0; i < 5; i++) {
 764                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 765                 print_key_info("Lkp", &keys[i], pos[i]);
 766                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 767                                 "found non-existent key (pos[%u]=%d)", i, pos[i]);
 768         }
 769
 770         /* Lookup multi */
 771         ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
 772         if (ret == 0)
 773                 for (i = 0; i < 5; i++) {
 774                         print_key_info("Lkp", key_array[i], pos[i]);
 775                         RETURN_IF_ERROR(pos[i] != -ENOENT,
 776                                         "found not-existent key (pos[%u]=%d)", i, pos[i]);
 777                 }
 778
 779         rte_hash_free(handle);
 780
 781         return 0;
 782 }
 783
 784 /*
 785  * Add keys to the same bucket until bucket full.
 786  *      - add 5 keys to the same bucket (hash created with 4 keys per bucket):
 787  *        first 4 successful, 5th successful, pushing existing item in bucket
 788  *      - lookup the 5 keys: 5 hits
 789  *      - add the 5 keys again: 5 OK
 790  *      - lookup the 5 keys: 5 hits (updated data)
 791  *      - delete the 5 keys: 5 OK
 792  *      - lookup the 5 keys: 5 misses
 793  */
 794 static int test_full_bucket(void)
 795 {
 796         struct rte_hash_parameters params_pseudo_hash = {
 797                 .name = "test4",
 798                 .entries = 64,
 799                 .key_len = sizeof(struct flow_key),
 800                 .hash_func = pseudo_hash,
 801                 .hash_func_init_val = 0,
 802                 .socket_id = 0,
 803         };
 804         struct rte_hash *handle;
 805         int pos[5];
 806         int expected_pos[5];
 807         unsigned i;
 808
 809         handle = rte_hash_create(&params_pseudo_hash);
 810         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 811
 812         /* Fill bucket */
 813         for (i = 0; i < 4; i++) {
 814                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 815                 print_key_info("Add", &keys[i], pos[i]);
 816                 RETURN_IF_ERROR(pos[i] < 0,
 817                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 818                 expected_pos[i] = pos[i];
 819         }
 820         /*
 821          * This should work and will push one of the items
 822          * in the bucket because it is full
 823          */
 824         pos[4] = rte_hash_add_key(handle, &keys[4]);
 825         print_key_info("Add", &keys[4], pos[4]);
 826         RETURN_IF_ERROR(pos[4] < 0,
 827                         "failed to add key (pos[4]=%d)", pos[4]);
 828         expected_pos[4] = pos[4];
 829
 830         /* Lookup */
 831         for (i = 0; i < 5; i++) {
 832                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 833                 print_key_info("Lkp", &keys[i], pos[i]);
 834                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 835                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 836         }
 837
 838         /* Add - update */
 839         for (i = 0; i < 5; i++) {
 840                 pos[i] = rte_hash_add_key(handle, &keys[i]);
 841                 print_key_info("Add", &keys[i], pos[i]);
 842                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 843                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 844         }
 845
 846         /* Lookup */
 847         for (i = 0; i < 5; i++) {
 848                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 849                 print_key_info("Lkp", &keys[i], pos[i]);
 850                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 851                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 852         }
 853
 854         /* Delete 1 key, check other keys are still found */
 855         pos[1] = rte_hash_del_key(handle, &keys[1]);
 856         print_key_info("Del", &keys[1], pos[1]);
 857         RETURN_IF_ERROR(pos[1] != expected_pos[1],
 858                         "failed to delete key (pos[1]=%d)", pos[1]);
 859         pos[3] = rte_hash_lookup(handle, &keys[3]);
 860         print_key_info("Lkp", &keys[3], pos[3]);
 861         RETURN_IF_ERROR(pos[3] != expected_pos[3],
 862                         "failed lookup after deleting key from same bucket "
 863                         "(pos[3]=%d)", pos[3]);
 864
 865         /* Go back to previous state */
 866         pos[1] = rte_hash_add_key(handle, &keys[1]);
 867         print_key_info("Add", &keys[1], pos[1]);
 868         expected_pos[1] = pos[1];
 869         RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
 870
 871         /* Delete */
 872         for (i = 0; i < 5; i++) {
 873                 pos[i] = rte_hash_del_key(handle, &keys[i]);
 874                 print_key_info("Del", &keys[i], pos[i]);
 875                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 876                         "failed to delete key (pos[%u]=%d)", i, pos[i]);
 877         }
 878
 879         /* Lookup */
 880         for (i = 0; i < 5; i++) {
 881                 pos[i] = rte_hash_lookup(handle, &keys[i]);
 882                 print_key_info("Lkp", &keys[i], pos[i]);
 883                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 884                         "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
 885         }
 886
 887         rte_hash_free(handle);
 888
 889         /* Cover the NULL case. */
 890         rte_hash_free(0);
 891         return 0;
 892 }
 893
 894 /*
 895  * Similar to the test above (full bucket test), but for extendable buckets.
 896  */
 897 static int test_extendable_bucket(void)
 898 {
 899         struct rte_hash_parameters params_pseudo_hash = {
 900                 .name = "test5",
 901                 .entries = 64,
 902                 .key_len = sizeof(struct flow_key),
 903                 .hash_func = pseudo_hash,
 904                 .hash_func_init_val = 0,
 905                 .socket_id = 0,
 906                 .extra_flag = RTE_HASH_EXTRA_FLAGS_EXT_TABLE
 907         };
 908         struct rte_hash *handle;
 909         int pos[64];
 910         int expected_pos[64];
 911         unsigned int i;
 912         struct flow_key rand_keys[64];
 913
 914         for (i = 0; i < 64; i++) {
 915                 rand_keys[i].port_dst = i;
 916                 rand_keys[i].port_src = i+1;
 917         }
 918
 919         handle = rte_hash_create(&params_pseudo_hash);
 920         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
 921
 922         /* Fill bucket */
 923         for (i = 0; i < 64; i++) {
 924                 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
 925                 print_key_info("Add", &rand_keys[i], pos[i]);
 926                 RETURN_IF_ERROR(pos[i] < 0,
 927                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 928                 expected_pos[i] = pos[i];
 929         }
 930
 931         /* Lookup */
 932         for (i = 0; i < 64; i++) {
 933                 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
 934                 print_key_info("Lkp", &rand_keys[i], pos[i]);
 935                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 936                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 937         }
 938
 939         /* Add - update */
 940         for (i = 0; i < 64; i++) {
 941                 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
 942                 print_key_info("Add", &rand_keys[i], pos[i]);
 943                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 944                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 945         }
 946
 947         /* Lookup */
 948         for (i = 0; i < 64; i++) {
 949                 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
 950                 print_key_info("Lkp", &rand_keys[i], pos[i]);
 951                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 952                         "failed to find key (pos[%u]=%d)", i, pos[i]);
 953         }
 954
 955         /* Delete 1 key, check other keys are still found */
 956         pos[35] = rte_hash_del_key(handle, &rand_keys[35]);
 957         print_key_info("Del", &rand_keys[35], pos[35]);
 958         RETURN_IF_ERROR(pos[35] != expected_pos[35],
 959                         "failed to delete key (pos[1]=%d)", pos[35]);
 960         pos[20] = rte_hash_lookup(handle, &rand_keys[20]);
 961         print_key_info("Lkp", &rand_keys[20], pos[20]);
 962         RETURN_IF_ERROR(pos[20] != expected_pos[20],
 963                         "failed lookup after deleting key from same bucket "
 964                         "(pos[20]=%d)", pos[20]);
 965
 966         /* Go back to previous state */
 967         pos[35] = rte_hash_add_key(handle, &rand_keys[35]);
 968         print_key_info("Add", &rand_keys[35], pos[35]);
 969         expected_pos[35] = pos[35];
 970         RETURN_IF_ERROR(pos[35] < 0, "failed to add key (pos[1]=%d)", pos[35]);
 971
 972         /* Delete */
 973         for (i = 0; i < 64; i++) {
 974                 pos[i] = rte_hash_del_key(handle, &rand_keys[i]);
 975                 print_key_info("Del", &rand_keys[i], pos[i]);
 976                 RETURN_IF_ERROR(pos[i] != expected_pos[i],
 977                         "failed to delete key (pos[%u]=%d)", i, pos[i]);
 978         }
 979
 980         /* Lookup */
 981         for (i = 0; i < 64; i++) {
 982                 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
 983                 print_key_info("Lkp", &rand_keys[i], pos[i]);
 984                 RETURN_IF_ERROR(pos[i] != -ENOENT,
 985                         "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
 986         }
 987
 988         /* Add again */
 989         for (i = 0; i < 64; i++) {
 990                 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
 991                 print_key_info("Add", &rand_keys[i], pos[i]);
 992                 RETURN_IF_ERROR(pos[i] < 0,
 993                         "failed to add key (pos[%u]=%d)", i, pos[i]);
 994                 expected_pos[i] = pos[i];
 995         }
 996
 997         rte_hash_free(handle);
 998
 999         /* Cover the NULL case. */
1000         rte_hash_free(0);
1001         return 0;
1002 }
1003
1004 /******************************************************************************/
1005 static int
1006 fbk_hash_unit_test(void)
1007 {
1008         struct rte_fbk_hash_params params = {
1009                 .name = "fbk_hash_test",
1010                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1011                 .entries_per_bucket = 4,
1012                 .socket_id = 0,
1013         };
1014
1015         struct rte_fbk_hash_params invalid_params_1 = {
1016                 .name = "invalid_1",
1017                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
1018                 .entries_per_bucket = 4,
1019                 .socket_id = 0,
1020         };
1021
1022         struct rte_fbk_hash_params invalid_params_2 = {
1023                 .name = "invalid_2",
1024                 .entries = 4,
1025                 .entries_per_bucket = 3,         /* Not power of 2 */
1026                 .socket_id = 0,
1027         };
1028
1029         struct rte_fbk_hash_params invalid_params_3 = {
1030                 .name = "invalid_3",
1031                 .entries = 0,                    /* Entries is 0 */
1032                 .entries_per_bucket = 4,
1033                 .socket_id = 0,
1034         };
1035
1036         struct rte_fbk_hash_params invalid_params_4 = {
1037                 .name = "invalid_4",
1038                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1039                 .entries_per_bucket = 0,         /* Entries per bucket is 0 */
1040                 .socket_id = 0,
1041         };
1042
1043         struct rte_fbk_hash_params invalid_params_5 = {
1044                 .name = "invalid_5",
1045                 .entries = 4,
1046                 .entries_per_bucket = 8,         /* Entries per bucket > entries */
1047                 .socket_id = 0,
1048         };
1049
1050         struct rte_fbk_hash_params invalid_params_6 = {
1051                 .name = "invalid_6",
1052                 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2,   /* Entries > max allowed */
1053                 .entries_per_bucket = 4,
1054                 .socket_id = 0,
1055         };
1056
1057         struct rte_fbk_hash_params invalid_params_7 = {
1058                 .name = "invalid_7",
1059                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1060                 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2,  /* Entries > max allowed */
1061                 .socket_id = 0,
1062         };
1063
1064         struct rte_fbk_hash_params invalid_params_8 = {
1065                 .name = "invalid_7",
1066                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1067                 .entries_per_bucket = 4,
1068                 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
1069         };
1070
1071         /* try to create two hashes with identical names
1072          * in this case, trying to create a second one will not
1073          * fail but will simply return pointer to the existing
1074          * hash with that name. sort of like a "find hash by name" :-)
1075          */
1076         struct rte_fbk_hash_params invalid_params_same_name_1 = {
1077                 .name = "same_name",                            /* hash with identical name */
1078                 .entries = 4,
1079                 .entries_per_bucket = 2,
1080                 .socket_id = 0,
1081         };
1082
1083         /* trying to create this hash should return a pointer to an existing hash */
1084         struct rte_fbk_hash_params invalid_params_same_name_2 = {
1085                 .name = "same_name",                            /* hash with identical name */
1086                 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1087                 .entries_per_bucket = 4,
1088                 .socket_id = 0,
1089         };
1090
1091         /* this is a sanity check for "same name" test
1092          * creating this hash will check if we are actually able to create
1093          * multiple hashes with different names (instead of having just one).
1094          */
1095         struct rte_fbk_hash_params different_name = {
1096                 .name = "different_name",                       /* different name */
1097                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1098                 .entries_per_bucket = 4,
1099                 .socket_id = 0,
1100         };
1101
1102         struct rte_fbk_hash_params params_jhash = {
1103                 .name = "valid",
1104                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1105                 .entries_per_bucket = 4,
1106                 .socket_id = 0,
1107                 .hash_func = rte_jhash_1word,              /* Tests for different hash_func */
1108                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1109         };
1110
1111         struct rte_fbk_hash_params params_nohash = {
1112                 .name = "valid nohash",
1113                 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1114                 .entries_per_bucket = 4,
1115                 .socket_id = 0,
1116                 .hash_func = NULL,                            /* Tests for null hash_func */
1117                 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1118         };
1119
1120         struct rte_fbk_hash_table *handle, *tmp;
1121         uint32_t keys[5] =
1122                 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1123         uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
1124         int status;
1125         unsigned i;
1126         double used_entries;
1127
1128         /* Try creating hashes with invalid parameters */
1129         printf("# Testing hash creation with invalid parameters "
1130                         "- expect error msgs\n");
1131         handle = rte_fbk_hash_create(&invalid_params_1);
1132         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1133
1134         handle = rte_fbk_hash_create(&invalid_params_2);
1135         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1136
1137         handle = rte_fbk_hash_create(&invalid_params_3);
1138         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1139
1140         handle = rte_fbk_hash_create(&invalid_params_4);
1141         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1142
1143         handle = rte_fbk_hash_create(&invalid_params_5);
1144         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1145
1146         handle = rte_fbk_hash_create(&invalid_params_6);
1147         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1148
1149         handle = rte_fbk_hash_create(&invalid_params_7);
1150         RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1151
1152         if (rte_eal_has_hugepages()) {
1153                 handle = rte_fbk_hash_create(&invalid_params_8);
1154                 RETURN_IF_ERROR_FBK(handle != NULL,
1155                                         "fbk hash creation should have failed");
1156         }
1157
1158         handle = rte_fbk_hash_create(&invalid_params_same_name_1);
1159         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
1160
1161         tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
1162         if (tmp != NULL)
1163                 rte_fbk_hash_free(tmp);
1164         RETURN_IF_ERROR_FBK(tmp != NULL, "fbk hash creation should have failed");
1165
1166         /* we are not freeing  handle here because we need a hash list
1167          * to be not empty for the next test */
1168
1169         /* create a hash in non-empty list - good for coverage */
1170         tmp = rte_fbk_hash_create(&different_name);
1171         RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
1172
1173         /* free both hashes */
1174         rte_fbk_hash_free(handle);
1175         rte_fbk_hash_free(tmp);
1176
1177         /* Create empty jhash hash. */
1178         handle = rte_fbk_hash_create(&params_jhash);
1179         RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
1180
1181         /* Cleanup. */
1182         rte_fbk_hash_free(handle);
1183
1184         /* Create empty jhash hash. */
1185         handle = rte_fbk_hash_create(&params_nohash);
1186         RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
1187
1188         /* Cleanup. */
1189         rte_fbk_hash_free(handle);
1190
1191         /* Create empty hash. */
1192         handle = rte_fbk_hash_create(&params);
1193         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1194
1195         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1196         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1197                                 "load factor right after creation is not zero but it should be");
1198         /* Add keys. */
1199         for (i = 0; i < 5; i++) {
1200                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1201                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1202         }
1203
1204         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1205         RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
1206                                 "load factor now is not as expected");
1207         /* Find value of added keys. */
1208         for (i = 0; i < 5; i++) {
1209                 status = rte_fbk_hash_lookup(handle, keys[i]);
1210                 RETURN_IF_ERROR_FBK(status != vals[i],
1211                                 "fbk hash lookup failed");
1212         }
1213
1214         /* Change value of added keys. */
1215         for (i = 0; i < 5; i++) {
1216                 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
1217                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
1218         }
1219
1220         /* Find new values. */
1221         for (i = 0; i < 5; i++) {
1222                 status = rte_fbk_hash_lookup(handle, keys[i]);
1223                 RETURN_IF_ERROR_FBK(status != vals[4-i],
1224                                 "fbk hash lookup failed");
1225         }
1226
1227         /* Delete keys individually. */
1228         for (i = 0; i < 5; i++) {
1229                 status = rte_fbk_hash_delete_key(handle, keys[i]);
1230                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
1231         }
1232
1233         used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1234         RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1235                                 "load factor right after deletion is not zero but it should be");
1236         /* Lookup should now fail. */
1237         for (i = 0; i < 5; i++) {
1238                 status = rte_fbk_hash_lookup(handle, keys[i]);
1239                 RETURN_IF_ERROR_FBK(status == 0,
1240                                 "fbk hash lookup should have failed");
1241         }
1242
1243         /* Add keys again. */
1244         for (i = 0; i < 5; i++) {
1245                 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1246                 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1247         }
1248
1249         /* Make sure they were added. */
1250         for (i = 0; i < 5; i++) {
1251                 status = rte_fbk_hash_lookup(handle, keys[i]);
1252                 RETURN_IF_ERROR_FBK(status != vals[i],
1253                                 "fbk hash lookup failed");
1254         }
1255
1256         /* Clear all entries. */
1257         rte_fbk_hash_clear_all(handle);
1258
1259         /* Lookup should fail. */
1260         for (i = 0; i < 5; i++) {
1261                 status = rte_fbk_hash_lookup(handle, keys[i]);
1262                 RETURN_IF_ERROR_FBK(status == 0,
1263                                 "fbk hash lookup should have failed");
1264         }
1265
1266         /* coverage */
1267
1268         /* fill up the hash_table */
1269         for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
1270                 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
1271
1272         /* Find non-existent key in a full hashtable */
1273         status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
1274         RETURN_IF_ERROR_FBK(status != -ENOENT,
1275                         "fbk hash lookup succeeded");
1276
1277         /* Delete non-existent key in a full hashtable */
1278         status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
1279         RETURN_IF_ERROR_FBK(status != -ENOENT,
1280                         "fbk hash delete succeeded");
1281
1282         /* Delete one key from a full hashtable */
1283         status = rte_fbk_hash_delete_key(handle, 1);
1284         RETURN_IF_ERROR_FBK(status != 0,
1285                         "fbk hash delete failed");
1286
1287         /* Clear all entries. */
1288         rte_fbk_hash_clear_all(handle);
1289
1290         /* Cleanup. */
1291         rte_fbk_hash_free(handle);
1292
1293         /* Cover the NULL case. */
1294         rte_fbk_hash_free(0);
1295
1296         return 0;
1297 }
1298
1299 /*
1300  * Sequence of operations for find existing fbk hash table
1301  *
1302  *  - create table
1303  *  - find existing table: hit
1304  *  - find non-existing table: miss
1305  *
1306  */
1307 static int test_fbk_hash_find_existing(void)
1308 {
1309         struct rte_fbk_hash_params params = {
1310                         .name = "fbk_hash_find_existing",
1311                         .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1312                         .entries_per_bucket = 4,
1313                         .socket_id = 0,
1314         };
1315         struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1316
1317         /* Create hash table. */
1318         handle = rte_fbk_hash_create(&params);
1319         RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1320
1321         /* Try to find existing fbk hash table */
1322         result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
1323         RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
1324
1325         /* Try to find non-existing fbk hash table */
1326         result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1327         RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
1328
1329         /* Cleanup. */
1330         rte_fbk_hash_free(handle);
1331
1332         return 0;
1333 }
1334
1335 #define BUCKET_ENTRIES 4
1336 /*
1337  * Do tests for hash creation with bad parameters.
1338  */
1339 static int test_hash_creation_with_bad_parameters(void)
1340 {
1341         struct rte_hash *handle, *tmp;
1342         struct rte_hash_parameters params;
1343
1344         handle = rte_hash_create(NULL);
1345         if (handle != NULL) {
1346                 rte_hash_free(handle);
1347                 printf("Impossible creating hash successfully without any parameter\n");
1348                 return -1;
1349         }
1350
1351         memcpy(&params, &ut_params, sizeof(params));
1352         params.name = "creation_with_bad_parameters_0";
1353         params.entries = RTE_HASH_ENTRIES_MAX + 1;
1354         handle = rte_hash_create(&params);
1355         if (handle != NULL) {
1356                 rte_hash_free(handle);
1357                 printf("Impossible creating hash successfully with entries in parameter exceeded\n");
1358                 return -1;
1359         }
1360
1361         memcpy(&params, &ut_params, sizeof(params));
1362         params.name = "creation_with_bad_parameters_2";
1363         params.entries = BUCKET_ENTRIES - 1;
1364         handle = rte_hash_create(&params);
1365         if (handle != NULL) {
1366                 rte_hash_free(handle);
1367                 printf("Impossible creating hash successfully if entries less than bucket_entries in parameter\n");
1368                 return -1;
1369         }
1370
1371         memcpy(&params, &ut_params, sizeof(params));
1372         params.name = "creation_with_bad_parameters_3";
1373         params.key_len = 0;
1374         handle = rte_hash_create(&params);
1375         if (handle != NULL) {
1376                 rte_hash_free(handle);
1377                 printf("Impossible creating hash successfully if key_len in parameter is zero\n");
1378                 return -1;
1379         }
1380
1381         memcpy(&params, &ut_params, sizeof(params));
1382         params.name = "creation_with_bad_parameters_4";
1383         params.socket_id = RTE_MAX_NUMA_NODES + 1;
1384         handle = rte_hash_create(&params);
1385         if (handle != NULL) {
1386                 rte_hash_free(handle);
1387                 printf("Impossible creating hash successfully with invalid socket\n");
1388                 return -1;
1389         }
1390
1391         /* test with same name should fail */
1392         memcpy(&params, &ut_params, sizeof(params));
1393         params.name = "same_name";
1394         handle = rte_hash_create(&params);
1395         if (handle == NULL) {
1396                 printf("Cannot create first hash table with 'same_name'\n");
1397                 return -1;
1398         }
1399         tmp = rte_hash_create(&params);
1400         if (tmp != NULL) {
1401                 printf("Creation of hash table with same name should fail\n");
1402                 rte_hash_free(handle);
1403                 rte_hash_free(tmp);
1404                 return -1;
1405         }
1406         rte_hash_free(handle);
1407
1408         printf("# Test successful. No more errors expected\n");
1409
1410         return 0;
1411 }
1412
1413 /*
1414  * Do tests for hash creation with parameters that look incorrect
1415  * but are actually valid.
1416  */
1417 static int
1418 test_hash_creation_with_good_parameters(void)
1419 {
1420         struct rte_hash *handle;
1421         struct rte_hash_parameters params;
1422
1423         /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1424         memcpy(&params, &ut_params, sizeof(params));
1425         params.name = "name";
1426         params.hash_func = NULL;
1427         handle = rte_hash_create(&params);
1428         if (handle == NULL) {
1429                 printf("Creating hash with null hash_func failed\n");
1430                 return -1;
1431         }
1432
1433         rte_hash_free(handle);
1434
1435         return 0;
1436 }
1437
1438 #define ITERATIONS 3
1439 /*
1440  * Test to see the average table utilization (entries added/max entries)
1441  * before hitting a random entry that cannot be added
1442  */
1443 static int test_average_table_utilization(uint32_t ext_table)
1444 {
1445         struct rte_hash *handle;
1446         uint8_t simple_key[MAX_KEYSIZE];
1447         unsigned i, j;
1448         unsigned added_keys, average_keys_added = 0;
1449         int ret;
1450         unsigned int cnt;
1451
1452         printf("\n# Running test to determine average utilization"
1453                "\n  before adding elements begins to fail\n");
1454         if (ext_table)
1455                 printf("ext table is enabled\n");
1456         else
1457                 printf("ext table is disabled\n");
1458
1459         printf("Measuring performance, please wait");
1460         fflush(stdout);
1461         ut_params.entries = 1 << 16;
1462         ut_params.name = "test_average_utilization";
1463         ut_params.hash_func = rte_jhash;
1464         if (ext_table)
1465                 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1466         else
1467                 ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1468
1469         handle = rte_hash_create(&ut_params);
1470
1471         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1472
1473         for (j = 0; j < ITERATIONS; j++) {
1474                 ret = 0;
1475                 /* Add random entries until key cannot be added */
1476                 for (added_keys = 0; ret >= 0; added_keys++) {
1477                         for (i = 0; i < ut_params.key_len; i++)
1478                                 simple_key[i] = rte_rand() % 255;
1479                         ret = rte_hash_add_key(handle, simple_key);
1480                         if (ret < 0)
1481                                 break;
1482                 }
1483
1484                 if (ret != -ENOSPC) {
1485                         printf("Unexpected error when adding keys\n");
1486                         rte_hash_free(handle);
1487                         return -1;
1488                 }
1489
1490                 cnt = rte_hash_count(handle);
1491                 if (cnt != added_keys) {
1492                         printf("rte_hash_count returned wrong value %u, %u,"
1493                                         "%u\n", j, added_keys, cnt);
1494                         rte_hash_free(handle);
1495                         return -1;
1496                 }
1497                 if (ext_table) {
1498                         if (cnt != ut_params.entries) {
1499                                 printf("rte_hash_count returned wrong value "
1500                                         "%u, %u, %u\n", j, added_keys, cnt);
1501                                 rte_hash_free(handle);
1502                                 return -1;
1503                         }
1504                 }
1505
1506                 average_keys_added += added_keys;
1507
1508                 /* Reset the table */
1509                 rte_hash_reset(handle);
1510
1511                 /* Print a dot to show progress on operations */
1512                 printf(".");
1513                 fflush(stdout);
1514         }
1515
1516         average_keys_added /= ITERATIONS;
1517
1518         printf("\nAverage table utilization = %.2f%% (%u/%u)\n",
1519                 ((double) average_keys_added / ut_params.entries * 100),
1520                 average_keys_added, ut_params.entries);
1521         rte_hash_free(handle);
1522
1523         return 0;
1524 }
1525
1526 #define NUM_ENTRIES 256
1527 static int test_hash_iteration(uint32_t ext_table)
1528 {
1529         struct rte_hash *handle;
1530         unsigned i;
1531         uint8_t keys[NUM_ENTRIES][MAX_KEYSIZE];
1532         const void *next_key;
1533         void *next_data;
1534         void *data[NUM_ENTRIES];
1535         unsigned added_keys;
1536         uint32_t iter = 0;
1537         int ret = 0;
1538
1539         ut_params.entries = NUM_ENTRIES;
1540         ut_params.name = "test_hash_iteration";
1541         ut_params.hash_func = rte_jhash;
1542         ut_params.key_len = 16;
1543         if (ext_table)
1544                 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1545         else
1546                 ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1547
1548         handle = rte_hash_create(&ut_params);
1549         RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1550
1551         /* Add random entries until key cannot be added */
1552         for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) {
1553                 data[added_keys] = (void *) ((uintptr_t) rte_rand());
1554                 for (i = 0; i < ut_params.key_len; i++)
1555                         keys[added_keys][i] = rte_rand() % 255;
1556                 ret = rte_hash_add_key_data(handle, keys[added_keys], data[added_keys]);
1557                 if (ret < 0) {
1558                         if (ext_table) {
1559                                 printf("Insertion failed for ext table\n");
1560                                 goto err;
1561                         }
1562                         break;
1563                 }
1564         }
1565
1566         /* Iterate through the hash table */
1567         while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) {
1568                 /* Search for the key in the list of keys added */
1569                 for (i = 0; i < NUM_ENTRIES; i++) {
1570                         if (memcmp(next_key, keys[i], ut_params.key_len) == 0) {
1571                                 if (next_data != data[i]) {
1572                                         printf("Data found in the hash table is"
1573                                                "not the data added with the key\n");
1574                                         goto err;
1575                                 }
1576                                 added_keys--;
1577                                 break;
1578                         }
1579                 }
1580                 if (i == NUM_ENTRIES) {
1581                         printf("Key found in the hash table was not added\n");
1582                         goto err;
1583                 }
1584         }
1585
1586         /* Check if all keys have been iterated */
1587         if (added_keys != 0) {
1588                 printf("There were still %u keys to iterate\n", added_keys);
1589                 goto err;
1590         }
1591
1592         rte_hash_free(handle);
1593         return 0;
1594
1595 err:
1596         rte_hash_free(handle);
1597         return -1;
1598 }
1599
1600 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1601                         0x04, 0x05, 0x06, 0x07,
1602                         0x08, 0x09, 0x0a, 0x0b,
1603                         0x0c, 0x0d, 0x0e, 0x0f};
1604 static struct rte_hash_parameters hash_params_ex = {
1605         .name = NULL,
1606         .entries = 64,
1607         .key_len = 0,
1608         .hash_func = NULL,
1609         .hash_func_init_val = 0,
1610         .socket_id = 0,
1611 };
1612
1613 /*
1614  * Wrapper function around rte_jhash_32b.
1615  * It is required because rte_jhash_32b() accepts the length
1616  * as size of 4-byte units.
1617  */
1618 static inline uint32_t
1619 test_jhash_32b(const void *k, uint32_t length, uint32_t initval)
1620 {
1621         return rte_jhash_32b(k, length >> 2, initval);
1622 }
1623
1624 /*
1625  * add/delete key with jhash2
1626  */
1627 static int
1628 test_hash_add_delete_jhash2(void)
1629 {
1630         int ret = -1;
1631         struct rte_hash *handle;
1632         int32_t pos1, pos2;
1633
1634         hash_params_ex.name = "hash_test_jhash2";
1635         hash_params_ex.key_len = 4;
1636         hash_params_ex.hash_func = (rte_hash_function)test_jhash_32b;
1637
1638         handle = rte_hash_create(&hash_params_ex);
1639         if (handle == NULL) {
1640                 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1641                 goto fail_jhash2;
1642         }
1643         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1644         if (pos1 < 0) {
1645                 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1646                 goto fail_jhash2;
1647         }
1648
1649         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1650         if (pos2 < 0 || pos1 != pos2) {
1651                 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1652                 goto fail_jhash2;
1653         }
1654         ret = 0;
1655
1656 fail_jhash2:
1657         if (handle != NULL)
1658                 rte_hash_free(handle);
1659
1660         return ret;
1661 }
1662
1663 /*
1664  * add/delete (2) key with jhash2
1665  */
1666 static int
1667 test_hash_add_delete_2_jhash2(void)
1668 {
1669         int ret = -1;
1670         struct rte_hash *handle;
1671         int32_t pos1, pos2;
1672
1673         hash_params_ex.name = "hash_test_2_jhash2";
1674         hash_params_ex.key_len = 8;
1675         hash_params_ex.hash_func = (rte_hash_function)test_jhash_32b;
1676
1677         handle = rte_hash_create(&hash_params_ex);
1678         if (handle == NULL)
1679                 goto fail_2_jhash2;
1680
1681         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1682         if (pos1 < 0)
1683                 goto fail_2_jhash2;
1684
1685         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1686         if (pos2 < 0 || pos1 != pos2)
1687                 goto fail_2_jhash2;
1688
1689         ret = 0;
1690
1691 fail_2_jhash2:
1692         if (handle != NULL)
1693                 rte_hash_free(handle);
1694
1695         return ret;
1696 }
1697
1698 static uint32_t
1699 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1700 {
1701         const uint32_t *k = key;
1702
1703         RTE_SET_USED(length);
1704
1705         return rte_jhash_1word(k[0], initval);
1706 }
1707
1708 static uint32_t
1709 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1710 {
1711         const uint32_t *k = key;
1712
1713         RTE_SET_USED(length);
1714
1715         return rte_jhash_2words(k[0], k[1], initval);
1716 }
1717
1718 static uint32_t
1719 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1720 {
1721         const uint32_t *k = key;
1722
1723         RTE_SET_USED(length);
1724
1725         return rte_jhash_3words(k[0], k[1], k[2], initval);
1726 }
1727
1728 /*
1729  * add/delete key with jhash 1word
1730  */
1731 static int
1732 test_hash_add_delete_jhash_1word(void)
1733 {
1734         int ret = -1;
1735         struct rte_hash *handle;
1736         int32_t pos1, pos2;
1737
1738         hash_params_ex.name = "hash_test_jhash_1word";
1739         hash_params_ex.key_len = 4;
1740         hash_params_ex.hash_func = test_hash_jhash_1word;
1741
1742         handle = rte_hash_create(&hash_params_ex);
1743         if (handle == NULL)
1744                 goto fail_jhash_1word;
1745
1746         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1747         if (pos1 < 0)
1748                 goto fail_jhash_1word;
1749
1750         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1751         if (pos2 < 0 || pos1 != pos2)
1752                 goto fail_jhash_1word;
1753
1754         ret = 0;
1755
1756 fail_jhash_1word:
1757         if (handle != NULL)
1758                 rte_hash_free(handle);
1759
1760         return ret;
1761 }
1762
1763 /*
1764  * add/delete key with jhash 2word
1765  */
1766 static int
1767 test_hash_add_delete_jhash_2word(void)
1768 {
1769         int ret = -1;
1770         struct rte_hash *handle;
1771         int32_t pos1, pos2;
1772
1773         hash_params_ex.name = "hash_test_jhash_2word";
1774         hash_params_ex.key_len = 8;
1775         hash_params_ex.hash_func = test_hash_jhash_2word;
1776
1777         handle = rte_hash_create(&hash_params_ex);
1778         if (handle == NULL)
1779                 goto fail_jhash_2word;
1780
1781         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1782         if (pos1 < 0)
1783                 goto fail_jhash_2word;
1784
1785         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1786         if (pos2 < 0 || pos1 != pos2)
1787                 goto fail_jhash_2word;
1788
1789         ret = 0;
1790
1791 fail_jhash_2word:
1792         if (handle != NULL)
1793                 rte_hash_free(handle);
1794
1795         return ret;
1796 }
1797
1798 /*
1799  * add/delete key with jhash 3word
1800  */
1801 static int
1802 test_hash_add_delete_jhash_3word(void)
1803 {
1804         int ret = -1;
1805         struct rte_hash *handle;
1806         int32_t pos1, pos2;
1807
1808         hash_params_ex.name = "hash_test_jhash_3word";
1809         hash_params_ex.key_len = 12;
1810         hash_params_ex.hash_func = test_hash_jhash_3word;
1811
1812         handle = rte_hash_create(&hash_params_ex);
1813         if (handle == NULL)
1814                 goto fail_jhash_3word;
1815
1816         pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1817         if (pos1 < 0)
1818                 goto fail_jhash_3word;
1819
1820         pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1821         if (pos2 < 0 || pos1 != pos2)
1822                 goto fail_jhash_3word;
1823
1824         ret = 0;
1825
1826 fail_jhash_3word:
1827         if (handle != NULL)
1828                 rte_hash_free(handle);
1829
1830         return ret;
1831 }
1832
1833 static struct rte_hash *g_handle;
1834 static struct rte_rcu_qsbr *g_qsv;
1835 static volatile uint8_t writer_done;
1836 struct flow_key g_rand_keys[9];
1837
1838 /*
1839  * rte_hash_rcu_qsbr_add positive and negative tests.
1840  *  - Add RCU QSBR variable to Hash
1841  *  - Add another RCU QSBR variable to Hash
1842  *  - Check returns
1843  */
1844 static int
1845 test_hash_rcu_qsbr_add(void)
1846 {
1847         size_t sz;
1848         struct rte_rcu_qsbr *qsv2 = NULL;
1849         int32_t status;
1850         struct rte_hash_rcu_config rcu_cfg = {0};
1851         struct rte_hash_parameters params;
1852
1853         printf("\n# Running RCU QSBR add tests\n");
1854         memcpy(&params, &ut_params, sizeof(params));
1855         params.name = "test_hash_rcu_qsbr_add";
1856         params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
1857                                 RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
1858         g_handle = rte_hash_create(&params);
1859         RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
1860
1861         /* Create RCU QSBR variable */
1862         sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
1863         g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1864                                         RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1865         RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
1866                                  "RCU QSBR variable creation failed");
1867
1868         status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
1869         RETURN_IF_ERROR_RCU_QSBR(status != 0,
1870                                  "RCU QSBR variable initialization failed");
1871
1872         rcu_cfg.v = g_qsv;
1873         /* Invalid QSBR mode */
1874         rcu_cfg.mode = 0xff;
1875         status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1876         RETURN_IF_ERROR_RCU_QSBR(status == 0, "Invalid QSBR mode test failed");
1877
1878         rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ;
1879         /* Attach RCU QSBR to hash table */
1880         status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1881         RETURN_IF_ERROR_RCU_QSBR(status != 0,
1882                                  "Attach RCU QSBR to hash table failed");
1883
1884         /* Create and attach another RCU QSBR to hash table */
1885         qsv2 = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1886                                         RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1887         RETURN_IF_ERROR_RCU_QSBR(qsv2 == NULL,
1888                                  "RCU QSBR variable creation failed");
1889
1890         rcu_cfg.v = qsv2;
1891         rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC;
1892         status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1893         rte_free(qsv2);
1894         RETURN_IF_ERROR_RCU_QSBR(status == 0,
1895                         "Attach RCU QSBR to hash table succeeded where failure"
1896                         " is expected");
1897
1898         rte_hash_free(g_handle);
1899         rte_free(g_qsv);
1900
1901         return 0;
1902 }
1903
1904 /*
1905  * rte_hash_rcu_qsbr_add DQ mode functional test.
1906  * Reader and writer are in the same thread in this test.
1907  *  - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries
1908  *  - Add RCU QSBR variable to hash
1909  *  - Add 8 hash entries and fill the bucket
1910  *  - If ext bkt is enabled, add 1 extra entry that is available in the ext bkt
1911  *  - Register a reader thread (not a real thread)
1912  *  - Reader lookup existing entry
1913  *  - Writer deletes the entry
1914  *  - Reader lookup the entry
1915  *  - Writer re-add the entry (no available free index)
1916  *  - Reader report quiescent state and unregister
1917  *  - Writer re-add the entry
1918  *  - Reader lookup the entry
1919  */
1920 static int
1921 test_hash_rcu_qsbr_dq_mode(uint8_t ext_bkt)
1922 {
1923         uint32_t total_entries = (ext_bkt == 0) ? 8 : 9;
1924
1925         uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
1926
1927         if (ext_bkt)
1928                 hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1929
1930         struct rte_hash_parameters params_pseudo_hash = {
1931                 .name = "test_hash_rcu_qsbr_dq_mode",
1932                 .entries = total_entries,
1933                 .key_len = sizeof(struct flow_key),
1934                 .hash_func = pseudo_hash,
1935                 .hash_func_init_val = 0,
1936                 .socket_id = 0,
1937                 .extra_flag = hash_extra_flag,
1938         };
1939         int pos[total_entries];
1940         int expected_pos[total_entries];
1941         unsigned int i;
1942         size_t sz;
1943         int32_t status;
1944         struct rte_hash_rcu_config rcu_cfg = {0};
1945
1946         g_qsv = NULL;
1947         g_handle = NULL;
1948
1949         for (i = 0; i < total_entries; i++) {
1950                 g_rand_keys[i].port_dst = i;
1951                 g_rand_keys[i].port_src = i+1;
1952         }
1953
1954         if (ext_bkt)
1955                 printf("\n# Running RCU QSBR DQ mode functional test with"
1956                        " ext bkt\n");
1957         else
1958                 printf("\n# Running RCU QSBR DQ mode functional test\n");
1959
1960         g_handle = rte_hash_create(&params_pseudo_hash);
1961         RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
1962
1963         /* Create RCU QSBR variable */
1964         sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
1965         g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1966                                         RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1967         RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
1968                                  "RCU QSBR variable creation failed");
1969
1970         status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
1971         RETURN_IF_ERROR_RCU_QSBR(status != 0,
1972                                  "RCU QSBR variable initialization failed");
1973
1974         rcu_cfg.v = g_qsv;
1975         rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ;
1976         /* Attach RCU QSBR to hash table */
1977         status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1978         RETURN_IF_ERROR_RCU_QSBR(status != 0,
1979                                  "Attach RCU QSBR to hash table failed");
1980
1981         /* Fill bucket */
1982         for (i = 0; i < total_entries; i++) {
1983                 pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]);
1984                 print_key_info("Add", &g_rand_keys[i], pos[i]);
1985                 RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0,
1986                                          "failed to add key (pos[%u]=%d)", i,
1987                                          pos[i]);
1988                 expected_pos[i] = pos[i];
1989         }
1990
1991         /* Register pseudo reader */
1992         status = rte_rcu_qsbr_thread_register(g_qsv, 0);
1993         RETURN_IF_ERROR_RCU_QSBR(status != 0,
1994                                  "RCU QSBR thread registration failed");
1995         rte_rcu_qsbr_thread_online(g_qsv, 0);
1996
1997         /* Lookup */
1998         pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
1999         print_key_info("Lkp", &g_rand_keys[0], pos[0]);
2000         RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2001                                  "failed to find correct key (pos[%u]=%d)", 0,
2002                                  pos[0]);
2003
2004         /* Writer update */
2005         pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]);
2006         print_key_info("Del", &g_rand_keys[0], pos[0]);
2007         RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2008                                  "failed to del correct key (pos[%u]=%d)", 0,
2009                                  pos[0]);
2010
2011         /* Lookup */
2012         pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
2013         print_key_info("Lkp", &g_rand_keys[0], pos[0]);
2014         RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOENT,
2015                                  "found deleted key (pos[%u]=%d)", 0, pos[0]);
2016
2017         /* Fill bucket */
2018         pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2019         print_key_info("Add", &g_rand_keys[0], pos[0]);
2020         RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOSPC,
2021                                  "Added key successfully (pos[%u]=%d)", 0, pos[0]);
2022
2023         /* Reader quiescent */
2024         rte_rcu_qsbr_quiescent(g_qsv, 0);
2025
2026         /* Fill bucket */
2027         pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2028         print_key_info("Add", &g_rand_keys[0], pos[0]);
2029         RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0,
2030                                  "failed to add key (pos[%u]=%d)", 0, pos[0]);
2031         expected_pos[0] = pos[0];
2032
2033         rte_rcu_qsbr_thread_offline(g_qsv, 0);
2034         (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0);
2035
2036         /* Lookup */
2037         pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
2038         print_key_info("Lkp", &g_rand_keys[0], pos[0]);
2039         RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2040                                  "failed to find correct key (pos[%u]=%d)", 0,
2041                                  pos[0]);
2042
2043         rte_hash_free(g_handle);
2044         rte_free(g_qsv);
2045         return 0;
2046
2047 }
2048
2049 /* Report quiescent state interval every 1024 lookups. Larger critical
2050  * sections in reader will result in writer polling multiple times.
2051  */
2052 #define QSBR_REPORTING_INTERVAL 1024
2053 #define WRITER_ITERATIONS       512
2054
2055 /*
2056  * Reader thread using rte_hash data structure with RCU.
2057  */
2058 static int
2059 test_hash_rcu_qsbr_reader(void *arg)
2060 {
2061         int i;
2062
2063         RTE_SET_USED(arg);
2064         /* Register this thread to report quiescent state */
2065         (void)rte_rcu_qsbr_thread_register(g_qsv, 0);
2066         rte_rcu_qsbr_thread_online(g_qsv, 0);
2067
2068         do {
2069                 for (i = 0; i < QSBR_REPORTING_INTERVAL; i++)
2070                         rte_hash_lookup(g_handle, &g_rand_keys[0]);
2071
2072                 /* Update quiescent state */
2073                 rte_rcu_qsbr_quiescent(g_qsv, 0);
2074         } while (!writer_done);
2075
2076         rte_rcu_qsbr_thread_offline(g_qsv, 0);
2077         (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0);
2078
2079         return 0;
2080 }
2081
2082 /*
2083  * rte_hash_rcu_qsbr_add sync mode functional test.
2084  * 1 Reader and 1 writer. They cannot be in the same thread in this test.
2085  *  - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries
2086  *  - Add RCU QSBR variable to hash
2087  *  - Register a reader thread. Reader keeps looking up a specific key.
2088  *  - Writer keeps adding and deleting a specific key.
2089  */
2090 static int
2091 test_hash_rcu_qsbr_sync_mode(uint8_t ext_bkt)
2092 {
2093         uint32_t total_entries = (ext_bkt == 0) ? 8 : 9;
2094
2095         uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
2096
2097         if (ext_bkt)
2098                 hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
2099
2100         struct rte_hash_parameters params_pseudo_hash = {
2101                 .name = "test_hash_rcu_qsbr_sync_mode",
2102                 .entries = total_entries,
2103                 .key_len = sizeof(struct flow_key),
2104                 .hash_func = pseudo_hash,
2105                 .hash_func_init_val = 0,
2106                 .socket_id = 0,
2107                 .extra_flag = hash_extra_flag,
2108         };
2109         int pos[total_entries];
2110         int expected_pos[total_entries];
2111         unsigned int i;
2112         size_t sz;
2113         int32_t status;
2114         struct rte_hash_rcu_config rcu_cfg = {0};
2115
2116         g_qsv = NULL;
2117         g_handle = NULL;
2118
2119         for (i = 0; i < total_entries; i++) {
2120                 g_rand_keys[i].port_dst = i;
2121                 g_rand_keys[i].port_src = i+1;
2122         }
2123
2124         if (ext_bkt)
2125                 printf("\n# Running RCU QSBR sync mode functional test with"
2126                        " ext bkt\n");
2127         else
2128                 printf("\n# Running RCU QSBR sync mode functional test\n");
2129
2130         g_handle = rte_hash_create(&params_pseudo_hash);
2131         RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
2132
2133         /* Create RCU QSBR variable */
2134         sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
2135         g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
2136                                         RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
2137         RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
2138                                  "RCU QSBR variable creation failed");
2139
2140         status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
2141         RETURN_IF_ERROR_RCU_QSBR(status != 0,
2142                                  "RCU QSBR variable initialization failed");
2143
2144         rcu_cfg.v = g_qsv;
2145         rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC;
2146         /* Attach RCU QSBR to hash table */
2147         status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
2148         RETURN_IF_ERROR_RCU_QSBR(status != 0,
2149                                  "Attach RCU QSBR to hash table failed");
2150
2151         /* Launch reader thread */
2152         rte_eal_remote_launch(test_hash_rcu_qsbr_reader, NULL,
2153                                 rte_get_next_lcore(-1, 1, 0));
2154
2155         /* Fill bucket */
2156         for (i = 0; i < total_entries; i++) {
2157                 pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]);
2158                 print_key_info("Add", &g_rand_keys[i], pos[i]);
2159                 RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0,
2160                                 "failed to add key (pos[%u]=%d)", i, pos[i]);
2161                 expected_pos[i] = pos[i];
2162         }
2163         writer_done = 0;
2164
2165         /* Writer Update */
2166         for (i = 0; i < WRITER_ITERATIONS; i++) {
2167                 expected_pos[0] = pos[0];
2168                 pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]);
2169                 print_key_info("Del", &g_rand_keys[0], status);
2170                 RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2171                                          "failed to del correct key (pos[%u]=%d)"
2172                                          , 0, pos[0]);
2173
2174                 pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2175                 print_key_info("Add", &g_rand_keys[0], pos[0]);
2176                 RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0,
2177                                          "failed to add key (pos[%u]=%d)", 0,
2178                                          pos[0]);
2179         }
2180
2181         writer_done = 1;
2182         /* Wait until reader exited. */
2183         rte_eal_mp_wait_lcore();
2184
2185         rte_hash_free(g_handle);
2186         rte_free(g_qsv);
2187
2188         return  0;
2189
2190 }
2191
2192 /*
2193  * Do all unit and performance tests.
2194  */
2195 static int
2196 test_hash(void)
2197 {
2198         RTE_BUILD_BUG_ON(sizeof(struct flow_key) % sizeof(uint32_t) != 0);
2199
2200         if (test_add_delete() < 0)
2201                 return -1;
2202         if (test_hash_add_delete_jhash2() < 0)
2203                 return -1;
2204         if (test_hash_add_delete_2_jhash2() < 0)
2205                 return -1;
2206         if (test_hash_add_delete_jhash_1word() < 0)
2207                 return -1;
2208         if (test_hash_add_delete_jhash_2word() < 0)
2209                 return -1;
2210         if (test_hash_add_delete_jhash_3word() < 0)
2211                 return -1;
2212         if (test_hash_get_key_with_position() < 0)
2213                 return -1;
2214         if (test_hash_find_existing() < 0)
2215                 return -1;
2216         if (test_add_update_delete() < 0)
2217                 return -1;
2218         if (test_add_update_delete_free() < 0)
2219                 return -1;
2220         if (test_add_delete_free_lf() < 0)
2221                 return -1;
2222         if (test_five_keys() < 0)
2223                 return -1;
2224         if (test_full_bucket() < 0)
2225                 return -1;
2226         if (test_extendable_bucket() < 0)
2227                 return -1;
2228
2229         if (test_fbk_hash_find_existing() < 0)
2230                 return -1;
2231         if (fbk_hash_unit_test() < 0)
2232                 return -1;
2233         if (test_hash_creation_with_bad_parameters() < 0)
2234                 return -1;
2235         if (test_hash_creation_with_good_parameters() < 0)
2236                 return -1;
2237
2238         /* ext table disabled */
2239         if (test_average_table_utilization(0) < 0)
2240                 return -1;
2241         if (test_hash_iteration(0) < 0)
2242                 return -1;
2243
2244         /* ext table enabled */
2245         if (test_average_table_utilization(1) < 0)
2246                 return -1;
2247         if (test_hash_iteration(1) < 0)
2248                 return -1;
2249
2250         run_hash_func_tests();
2251
2252         if (test_crc32_hash_alg_equiv() < 0)
2253                 return -1;
2254
2255         if (test_hash_rcu_qsbr_add() < 0)
2256                 return -1;
2257
2258         if (test_hash_rcu_qsbr_dq_mode(0) < 0)
2259                 return -1;
2260
2261         if (test_hash_rcu_qsbr_dq_mode(1) < 0)
2262                 return -1;
2263
2264         if (test_hash_rcu_qsbr_sync_mode(0) < 0)
2265                 return -1;
2266
2267         if (test_hash_rcu_qsbr_sync_mode(1) < 0)
2268                 return -1;
2269
2270         return 0;
2271 }
2272
2273 REGISTER_TEST_COMMAND(hash_autotest, test_hash);