bpf: allow self-xor operation
[dpdk.git] / 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);