4 * Copyright(c) 2010-2012 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 #include <sys/queue.h>
43 #include <rte_common.h>
44 #include <rte_malloc.h>
45 #include <rte_cycles.h>
46 #include <rte_random.h>
47 #include <rte_memory.h>
48 #include <rte_memzone.h>
49 #include <rte_tailq.h>
52 #include <rte_string_fns.h>
55 #include <rte_fbk_hash.h>
56 #include <rte_jhash.h>
58 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
59 #include <rte_hash_crc.h>
61 #include <cmdline_parse.h>
65 #ifdef RTE_LIBRTE_HASH
67 /*******************************************************************************
68 * Hash function performance test configuration section. Each performance test
69 * will be performed HASHTEST_ITERATIONS times.
71 * The five arrays below control what tests are performed. Every combination
72 * from the array entries is tested.
74 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
75 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
77 static rte_hash_function hashtest_funcs[] = {rte_jhash};
79 static uint32_t hashtest_initvals[] = {0};
80 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
81 /******************************************************************************/
82 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
85 * Check condition and return an error if true. Assumes that "handle" is the
86 * name of the hash structure pointer to be freed.
88 #define RETURN_IF_ERROR(cond, str, ...) do { \
90 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
91 if (handle) rte_hash_free(handle); \
96 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
98 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
99 if (handle) rte_fbk_hash_free(handle); \
104 /* 5-tuple key type */
111 } __attribute__((packed));
114 * Hash function that always returns the same value, to easily test what
115 * happens when a bucket is full.
117 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
118 __attribute__((unused)) uint32_t key_len,
119 __attribute__((unused)) uint32_t init_val)
125 * Print out result of unit test hash operation.
127 #if defined(UNIT_TEST_HASH_VERBOSE)
128 static void print_key_info(const char *msg, const struct flow_key *key,
131 uint8_t *p = (uint8_t *)key;
134 printf("%s key:0x", msg);
135 for (i = 0; i < sizeof(struct flow_key); i++) {
136 printf("%02X", p[i]);
138 printf(" @ pos %d\n", pos);
141 static void print_key_info(__attribute__((unused)) const char *msg,
142 __attribute__((unused)) const struct flow_key *key,
143 __attribute__((unused)) int32_t pos)
148 /* Keys used by unit test functions */
149 static struct flow_key keys[5] = { {
150 .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
151 .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
156 .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
157 .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
162 .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
163 .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
168 .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
169 .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
174 .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
175 .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
181 /* Parameters used for hash table in unit test functions. Name set later. */
182 static struct rte_hash_parameters ut_params = {
185 .key_len = sizeof(struct flow_key), /* 13 */
186 .hash_func = rte_jhash,
187 .hash_func_init_val = 0,
192 * Test a hash function.
194 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
197 static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
201 for (i = 0; i < key_len; i++)
202 key[i] = (uint8_t) rte_rand();
204 /* just to be on the safe side */
208 f(key, key_len, init_val);
212 * Test all hash functions.
214 static void run_hash_func_tests(void)
219 i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
222 j < sizeof(hashtest_initvals) / sizeof(uint32_t);
225 k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
227 run_hash_func_test(hashtest_funcs[i],
228 hashtest_initvals[j],
229 hashtest_key_lens[k]);
236 * Basic sequence of operations for a single key:
242 static int test_add_delete(void)
244 struct rte_hash *handle;
245 int pos0, expectedPos0;
247 ut_params.name = "test1";
248 handle = rte_hash_create(&ut_params);
249 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
251 pos0 = rte_hash_add_key(handle, &keys[0]);
252 print_key_info("Add", &keys[0], pos0);
253 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
256 pos0 = rte_hash_lookup(handle, &keys[0]);
257 print_key_info("Lkp", &keys[0], pos0);
258 RETURN_IF_ERROR(pos0 != expectedPos0,
259 "failed to find key (pos0=%d)", pos0);
261 pos0 = rte_hash_del_key(handle, &keys[0]);
262 print_key_info("Del", &keys[0], pos0);
263 RETURN_IF_ERROR(pos0 != expectedPos0,
264 "failed to delete key (pos0=%d)", pos0);
266 pos0 = rte_hash_lookup(handle, &keys[0]);
267 print_key_info("Lkp", &keys[0], pos0);
268 RETURN_IF_ERROR(pos0 != -ENOENT,
269 "fail: found key after deleting! (pos0=%d)", pos0);
271 rte_hash_free(handle);
276 * Sequence of operations for a single key:
281 * - lookup: hit (updated data)
286 static int test_add_update_delete(void)
288 struct rte_hash *handle;
289 int pos0, expectedPos0;
291 ut_params.name = "test2";
292 handle = rte_hash_create(&ut_params);
293 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
295 pos0 = rte_hash_del_key(handle, &keys[0]);
296 print_key_info("Del", &keys[0], pos0);
297 RETURN_IF_ERROR(pos0 != -ENOENT,
298 "fail: found non-existent key (pos0=%d)", pos0);
300 pos0 = rte_hash_add_key(handle, &keys[0]);
301 print_key_info("Add", &keys[0], pos0);
302 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
305 pos0 = rte_hash_lookup(handle, &keys[0]);
306 print_key_info("Lkp", &keys[0], pos0);
307 RETURN_IF_ERROR(pos0 != expectedPos0,
308 "failed to find key (pos0=%d)", pos0);
310 pos0 = rte_hash_add_key(handle, &keys[0]);
311 print_key_info("Add", &keys[0], pos0);
312 RETURN_IF_ERROR(pos0 != expectedPos0,
313 "failed to re-add key (pos0=%d)", pos0);
315 pos0 = rte_hash_lookup(handle, &keys[0]);
316 print_key_info("Lkp", &keys[0], pos0);
317 RETURN_IF_ERROR(pos0 != expectedPos0,
318 "failed to find key (pos0=%d)", pos0);
320 pos0 = rte_hash_del_key(handle, &keys[0]);
321 print_key_info("Del", &keys[0], pos0);
322 RETURN_IF_ERROR(pos0 != expectedPos0,
323 "failed to delete key (pos0=%d)", pos0);
325 pos0 = rte_hash_del_key(handle, &keys[0]);
326 print_key_info("Del", &keys[0], pos0);
327 RETURN_IF_ERROR(pos0 != -ENOENT,
328 "fail: deleted already deleted key (pos0=%d)", pos0);
330 pos0 = rte_hash_lookup(handle, &keys[0]);
331 print_key_info("Lkp", &keys[0], pos0);
332 RETURN_IF_ERROR(pos0 != -ENOENT,
333 "fail: found key after deleting! (pos0=%d)", pos0);
335 rte_hash_free(handle);
340 * Sequence of operations for find existing hash table
343 * - find existing table: hit
344 * - find non-existing table: miss
347 static int test_hash_find_existing(void)
349 struct rte_hash *handle = NULL, *result = NULL;
351 /* Create hash table. */
352 ut_params.name = "hash_find_existing";
353 handle = rte_hash_create(&ut_params);
354 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
356 /* Try to find existing hash table */
357 result = rte_hash_find_existing("hash_find_existing");
358 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
360 /* Try to find non-existing hash table */
361 result = rte_hash_find_existing("hash_find_non_existing");
362 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
365 rte_hash_free(handle);
371 * Sequence of operations for 5 keys
374 * - add keys (update)
375 * - lookup keys: hit (updated data)
376 * - delete keys : hit
377 * - lookup keys: miss
379 static int test_five_keys(void)
381 struct rte_hash *handle;
382 const void *key_array[5] = {0};
388 ut_params.name = "test3";
389 handle = rte_hash_create(&ut_params);
390 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
393 for (i = 0; i < 5; i++) {
394 pos[i] = rte_hash_add_key(handle, &keys[i]);
395 print_key_info("Add", &keys[i], pos[i]);
396 RETURN_IF_ERROR(pos[i] < 0,
397 "failed to add key (pos[%u]=%d)", i, pos[i]);
398 expected_pos[i] = pos[i];
402 for(i = 0; i < 5; i++)
403 key_array[i] = &keys[i];
405 ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
407 for(i = 0; i < 5; i++) {
408 print_key_info("Lkp", key_array[i], pos[i]);
409 RETURN_IF_ERROR(pos[i] != expected_pos[i],
410 "failed to find key (pos[%u]=%d)", i, pos[i]);
414 for (i = 0; i < 5; i++) {
415 pos[i] = rte_hash_add_key(handle, &keys[i]);
416 print_key_info("Add", &keys[i], pos[i]);
417 RETURN_IF_ERROR(pos[i] != expected_pos[i],
418 "failed to add key (pos[%u]=%d)", i, pos[i]);
422 for (i = 0; i < 5; i++) {
423 pos[i] = rte_hash_lookup(handle, &keys[i]);
424 print_key_info("Lkp", &keys[i], pos[i]);
425 RETURN_IF_ERROR(pos[i] != expected_pos[i],
426 "failed to find key (pos[%u]=%d)", i, pos[i]);
430 for (i = 0; i < 5; i++) {
431 pos[i] = rte_hash_del_key(handle, &keys[i]);
432 print_key_info("Del", &keys[i], pos[i]);
433 RETURN_IF_ERROR(pos[i] != expected_pos[i],
434 "failed to delete key (pos[%u]=%d)", i, pos[i]);
438 for (i = 0; i < 5; i++) {
439 pos[i] = rte_hash_lookup(handle, &keys[i]);
440 print_key_info("Lkp", &keys[i], pos[i]);
441 RETURN_IF_ERROR(pos[i] != -ENOENT,
442 "failed to find key (pos[%u]=%d)", i, pos[i]);
445 rte_hash_free(handle);
451 * Add keys to the same bucket until bucket full.
452 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
453 * first 4 successful, 5th unsuccessful
454 * - lookup the 5 keys: 4 hits, 1 miss
455 * - add the 5 keys again: 4 OK, one error as bucket is full
456 * - lookup the 5 keys: 4 hits (updated data), 1 miss
457 * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
458 * - lookup the 5 keys: 5 misses
459 * - add the 5th key: OK
460 * - lookup the 5th key: hit
462 static int test_full_bucket(void)
464 struct rte_hash_parameters params_pseudo_hash = {
468 .key_len = sizeof(struct flow_key), /* 13 */
469 .hash_func = pseudo_hash,
470 .hash_func_init_val = 0,
473 struct rte_hash *handle;
478 handle = rte_hash_create(¶ms_pseudo_hash);
479 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
482 for (i = 0; i < 4; i++) {
483 pos[i] = rte_hash_add_key(handle, &keys[i]);
484 print_key_info("Add", &keys[i], pos[i]);
485 RETURN_IF_ERROR(pos[i] < 0,
486 "failed to add key (pos[%u]=%d)", i, pos[i]);
487 expected_pos[i] = pos[i];
489 /* This shouldn't work because the bucket is full */
490 pos[4] = rte_hash_add_key(handle, &keys[4]);
491 print_key_info("Add", &keys[4], pos[4]);
492 RETURN_IF_ERROR(pos[4] != -ENOSPC,
493 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
496 for (i = 0; i < 4; i++) {
497 pos[i] = rte_hash_lookup(handle, &keys[i]);
498 print_key_info("Lkp", &keys[i], pos[i]);
499 RETURN_IF_ERROR(pos[i] != expected_pos[i],
500 "failed to find key (pos[%u]=%d)", i, pos[i]);
502 pos[4] = rte_hash_lookup(handle, &keys[4]);
503 print_key_info("Lkp", &keys[4], pos[4]);
504 RETURN_IF_ERROR(pos[4] != -ENOENT,
505 "fail: found non-existent key (pos[4]=%d)", pos[4]);
508 for (i = 0; i < 4; i++) {
509 pos[i] = rte_hash_add_key(handle, &keys[i]);
510 print_key_info("Add", &keys[i], pos[i]);
511 RETURN_IF_ERROR(pos[i] != expected_pos[i],
512 "failed to add key (pos[%u]=%d)", i, pos[i]);
514 pos[4] = rte_hash_add_key(handle, &keys[4]);
515 print_key_info("Add", &keys[4], pos[4]);
516 RETURN_IF_ERROR(pos[4] != -ENOSPC,
517 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
520 for (i = 0; i < 4; i++) {
521 pos[i] = rte_hash_lookup(handle, &keys[i]);
522 print_key_info("Lkp", &keys[i], pos[i]);
523 RETURN_IF_ERROR(pos[i] != expected_pos[i],
524 "failed to find key (pos[%u]=%d)", i, pos[i]);
526 pos[4] = rte_hash_lookup(handle, &keys[4]);
527 print_key_info("Lkp", &keys[4], pos[4]);
528 RETURN_IF_ERROR(pos[4] != -ENOENT,
529 "fail: found non-existent key (pos[4]=%d)", pos[4]);
531 /* Delete 1 key, check other keys are still found */
532 pos[1] = rte_hash_del_key(handle, &keys[1]);
533 print_key_info("Del", &keys[1], pos[1]);
534 RETURN_IF_ERROR(pos[1] != expected_pos[1],
535 "failed to delete key (pos[1]=%d)", pos[1]);
536 pos[3] = rte_hash_lookup(handle, &keys[3]);
537 print_key_info("Lkp", &keys[3], pos[3]);
538 RETURN_IF_ERROR(pos[3] != expected_pos[3],
539 "failed lookup after deleting key from same bucket "
540 "(pos[3]=%d)", pos[3]);
542 /* Go back to previous state */
543 pos[1] = rte_hash_add_key(handle, &keys[1]);
544 print_key_info("Add", &keys[1], pos[1]);
545 expected_pos[1] = pos[1];
546 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
549 for (i = 0; i < 4; i++) {
550 pos[i] = rte_hash_del_key(handle, &keys[i]);
551 print_key_info("Del", &keys[i], pos[i]);
552 RETURN_IF_ERROR(pos[i] != expected_pos[i],
553 "failed to delete key (pos[%u]=%d)", i, pos[i]);
555 pos[4] = rte_hash_del_key(handle, &keys[4]);
556 print_key_info("Del", &keys[4], pos[4]);
557 RETURN_IF_ERROR(pos[4] != -ENOENT,
558 "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
561 for (i = 0; i < 4; i++) {
562 pos[i] = rte_hash_lookup(handle, &keys[i]);
563 print_key_info("Lkp", &keys[i], pos[i]);
564 RETURN_IF_ERROR(pos[i] != -ENOENT,
565 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
568 /* Add and lookup the 5th key */
569 pos[4] = rte_hash_add_key(handle, &keys[4]);
570 print_key_info("Add", &keys[4], pos[4]);
571 RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
572 expected_pos[4] = pos[4];
573 pos[4] = rte_hash_lookup(handle, &keys[4]);
574 print_key_info("Lkp", &keys[4], pos[4]);
575 RETURN_IF_ERROR(pos[4] != expected_pos[4],
576 "failed to find key (pos[4]=%d)", pos[4]);
578 rte_hash_free(handle);
580 /* Cover the NULL case. */
585 /******************************************************************************/
587 fbk_hash_unit_test(void)
589 struct rte_fbk_hash_params params = {
590 .name = "fbk_hash_test",
591 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
592 .entries_per_bucket = 4,
596 struct rte_fbk_hash_params invalid_params_1 = {
598 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
599 .entries_per_bucket = 4,
603 struct rte_fbk_hash_params invalid_params_2 = {
606 .entries_per_bucket = 3, /* Not power of 2 */
610 struct rte_fbk_hash_params invalid_params_3 = {
612 .entries = 0, /* Entries is 0 */
613 .entries_per_bucket = 4,
617 struct rte_fbk_hash_params invalid_params_4 = {
619 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
620 .entries_per_bucket = 0, /* Entries per bucket is 0 */
624 struct rte_fbk_hash_params invalid_params_5 = {
627 .entries_per_bucket = 8, /* Entries per bucket > entries */
631 struct rte_fbk_hash_params invalid_params_6 = {
633 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
634 .entries_per_bucket = 4,
638 struct rte_fbk_hash_params invalid_params_7 = {
640 .entries = RTE_FBK_HASH_ENTRIES_MAX,
641 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */
645 struct rte_fbk_hash_params invalid_params_8 = {
647 .entries = RTE_FBK_HASH_ENTRIES_MAX,
648 .entries_per_bucket = 4,
649 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
652 /* try to create two hashes with identical names
653 * in this case, trying to create a second one will not
654 * fail but will simply return pointer to the existing
655 * hash with that name. sort of like a "find hash by name" :-)
657 struct rte_fbk_hash_params invalid_params_same_name_1 = {
658 .name = "same_name", /* hash with identical name */
660 .entries_per_bucket = 2,
664 /* trying to create this hash should return a pointer to an existing hash */
665 struct rte_fbk_hash_params invalid_params_same_name_2 = {
666 .name = "same_name", /* hash with identical name */
667 .entries = RTE_FBK_HASH_ENTRIES_MAX,
668 .entries_per_bucket = 4,
672 /* this is a sanity check for "same name" test
673 * creating this hash will check if we are actually able to create
674 * multiple hashes with different names (instead of having just one).
676 struct rte_fbk_hash_params different_name = {
677 .name = "different_name", /* different name */
678 .entries = RTE_FBK_HASH_ENTRIES_MAX,
679 .entries_per_bucket = 4,
683 struct rte_fbk_hash_params params_jhash = {
685 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
686 .entries_per_bucket = 4,
688 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
689 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
692 struct rte_fbk_hash_params params_nohash = {
693 .name = "valid nohash",
694 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
695 .entries_per_bucket = 4,
697 .hash_func = NULL, /* Tests for null hash_func */
698 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
701 struct rte_fbk_hash_table *handle, *tmp;
703 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
704 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
709 /* Try creating hashes with invalid parameters */
710 handle = rte_fbk_hash_create(&invalid_params_1);
711 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
713 handle = rte_fbk_hash_create(&invalid_params_2);
714 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
716 handle = rte_fbk_hash_create(&invalid_params_3);
717 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
719 handle = rte_fbk_hash_create(&invalid_params_4);
720 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
722 handle = rte_fbk_hash_create(&invalid_params_5);
723 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
725 handle = rte_fbk_hash_create(&invalid_params_6);
726 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
728 handle = rte_fbk_hash_create(&invalid_params_7);
729 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
731 handle = rte_fbk_hash_create(&invalid_params_8);
732 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
734 handle = rte_fbk_hash_create(&invalid_params_same_name_1);
735 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
737 tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
738 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
740 printf("ERROR line %d: hashes should have been the same\n", __LINE__);
741 rte_fbk_hash_free(handle);
742 rte_fbk_hash_free(tmp);
746 /* we are not freeing tmp or handle here because we need a hash list
747 * to be not empty for the next test */
749 /* create a hash in non-empty list - good for coverage */
750 tmp = rte_fbk_hash_create(&different_name);
751 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
753 /* free both hashes */
754 rte_fbk_hash_free(handle);
755 rte_fbk_hash_free(tmp);
757 /* Create empty jhash hash. */
758 handle = rte_fbk_hash_create(¶ms_jhash);
759 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
762 rte_fbk_hash_free(handle);
764 /* Create empty jhash hash. */
765 handle = rte_fbk_hash_create(¶ms_nohash);
766 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
769 rte_fbk_hash_free(handle);
771 /* Create empty hash. */
772 handle = rte_fbk_hash_create(¶ms);
773 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
775 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
776 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
777 "load factor right after creation is not zero but it should be");
779 for (i = 0; i < 5; i++) {
780 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
781 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
784 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
785 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
786 "load factor now is not as expected");
787 /* Find value of added keys. */
788 for (i = 0; i < 5; i++) {
789 status = rte_fbk_hash_lookup(handle, keys[i]);
790 RETURN_IF_ERROR_FBK(status != vals[i],
791 "fbk hash lookup failed");
794 /* Change value of added keys. */
795 for (i = 0; i < 5; i++) {
796 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
797 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
800 /* Find new values. */
801 for (i = 0; i < 5; i++) {
802 status = rte_fbk_hash_lookup(handle, keys[i]);
803 RETURN_IF_ERROR_FBK(status != vals[4-i],
804 "fbk hash lookup failed");
807 /* Delete keys individually. */
808 for (i = 0; i < 5; i++) {
809 status = rte_fbk_hash_delete_key(handle, keys[i]);
810 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
813 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
814 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
815 "load factor right after deletion is not zero but it should be");
816 /* Lookup should now fail. */
817 for (i = 0; i < 5; i++) {
818 status = rte_fbk_hash_lookup(handle, keys[i]);
819 RETURN_IF_ERROR_FBK(status == 0,
820 "fbk hash lookup should have failed");
823 /* Add keys again. */
824 for (i = 0; i < 5; i++) {
825 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
826 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
829 /* Make sure they were added. */
830 for (i = 0; i < 5; i++) {
831 status = rte_fbk_hash_lookup(handle, keys[i]);
832 RETURN_IF_ERROR_FBK(status != vals[i],
833 "fbk hash lookup failed");
836 /* Clear all entries. */
837 rte_fbk_hash_clear_all(handle);
839 /* Lookup should fail. */
840 for (i = 0; i < 5; i++) {
841 status = rte_fbk_hash_lookup(handle, keys[i]);
842 RETURN_IF_ERROR_FBK(status == 0,
843 "fbk hash lookup should have failed");
848 /* fill up the hash_table */
849 for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
850 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
852 /* Find non-existent key in a full hashtable */
853 status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
854 RETURN_IF_ERROR_FBK(status != -ENOENT,
855 "fbk hash lookup succeeded");
857 /* Delete non-existent key in a full hashtable */
858 status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
859 RETURN_IF_ERROR_FBK(status != -ENOENT,
860 "fbk hash delete succeeded");
862 /* Delete one key from a full hashtable */
863 status = rte_fbk_hash_delete_key(handle, 1);
864 RETURN_IF_ERROR_FBK(status != 0,
865 "fbk hash delete failed");
867 /* Clear all entries. */
868 rte_fbk_hash_clear_all(handle);
871 rte_fbk_hash_free(handle);
873 /* Cover the NULL case. */
874 rte_fbk_hash_free(0);
880 * Sequence of operations for find existing fbk hash table
883 * - find existing table: hit
884 * - find non-existing table: miss
887 static int test_fbk_hash_find_existing(void)
889 struct rte_fbk_hash_params params = {
890 .name = "fbk_hash_find_existing",
891 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
892 .entries_per_bucket = 4,
895 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
897 /* Create hash table. */
898 handle = rte_fbk_hash_create(¶ms);
899 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
901 /* Try to find existing fbk hash table */
902 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
903 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
905 /* Try to find non-existing fbk hash table */
906 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
907 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
910 rte_fbk_hash_free(handle);
916 * Do tests for hash creation with bad parameters.
918 static int test_hash_creation_with_bad_parameters(void)
920 struct rte_hash *handle;
921 struct rte_hash_parameters params;
923 handle = rte_hash_create(NULL);
924 if (handle != NULL) {
925 rte_hash_free(handle);
926 printf("Impossible creating hash sucessfully without any parameter\n");
930 memcpy(¶ms, &ut_params, sizeof(params));
931 params.name = "creation_with_bad_parameters_0";
932 params.entries = RTE_HASH_ENTRIES_MAX + 1;
933 handle = rte_hash_create(¶ms);
934 if (handle != NULL) {
935 rte_hash_free(handle);
936 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
940 memcpy(¶ms, &ut_params, sizeof(params));
941 params.name = "creation_with_bad_parameters_1";
942 params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
943 handle = rte_hash_create(¶ms);
944 if (handle != NULL) {
945 rte_hash_free(handle);
946 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
950 memcpy(¶ms, &ut_params, sizeof(params));
951 params.name = "creation_with_bad_parameters_2";
952 params.entries = params.bucket_entries - 1;
953 handle = rte_hash_create(¶ms);
954 if (handle != NULL) {
955 rte_hash_free(handle);
956 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
960 memcpy(¶ms, &ut_params, sizeof(params));
961 params.name = "creation_with_bad_parameters_3";
962 params.entries = params.entries - 1;
963 handle = rte_hash_create(¶ms);
964 if (handle != NULL) {
965 rte_hash_free(handle);
966 printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
970 memcpy(¶ms, &ut_params, sizeof(params));
971 params.name = "creation_with_bad_parameters_4";
972 params.bucket_entries = params.bucket_entries - 1;
973 handle = rte_hash_create(¶ms);
974 if (handle != NULL) {
975 rte_hash_free(handle);
976 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
980 memcpy(¶ms, &ut_params, sizeof(params));
981 params.name = "creation_with_bad_parameters_5";
983 handle = rte_hash_create(¶ms);
984 if (handle != NULL) {
985 rte_hash_free(handle);
986 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
990 memcpy(¶ms, &ut_params, sizeof(params));
991 params.name = "creation_with_bad_parameters_6";
992 params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
993 handle = rte_hash_create(¶ms);
994 if (handle != NULL) {
995 rte_hash_free(handle);
996 printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n");
1000 memcpy(¶ms, &ut_params, sizeof(params));
1001 params.name = "creation_with_bad_parameters_7";
1002 params.socket_id = RTE_MAX_NUMA_NODES + 1;
1003 handle = rte_hash_create(¶ms);
1004 if (handle != NULL) {
1005 rte_hash_free(handle);
1006 printf("Impossible creating hash sucessfully with invalid socket\n");
1010 rte_hash_free(handle);
1016 * Do tests for hash creation with parameters that look incorrect
1017 * but are actually valid.
1020 test_hash_creation_with_good_parameters(void)
1022 struct rte_hash *handle, *tmp;
1023 struct rte_hash_parameters params;
1025 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1026 memcpy(¶ms, &ut_params, sizeof(params));
1027 params.name = "same_name";
1028 params.hash_func = NULL;
1029 handle = rte_hash_create(¶ms);
1030 if (handle == NULL) {
1031 printf("Creating hash with null hash_func failed\n");
1034 if (handle->hash_func == NULL) {
1035 printf("Hash function should have been DEFAULT_HASH_FUNC\n");
1039 /* this test is trying to create a hash with the same name as previous one.
1040 * this should return a pointer to the hash we previously created.
1041 * the previous hash isn't freed exactly for the purpose of it being in
1044 memcpy(¶ms, &ut_params, sizeof(params));
1045 params.name = "same_name";
1046 tmp = rte_hash_create(¶ms);
1048 /* check if the returned handle is actually equal to the previous hash */
1049 if (handle != tmp) {
1050 rte_hash_free(handle);
1052 printf("Creating hash with existing name was successful\n");
1056 /* try creating hash when there already are hashes in the list.
1057 * the previous hash is not freed to have a non-empty hash list.
1058 * the other hash that's in the list is still pointed to by "handle" var.
1060 memcpy(¶ms, &ut_params, sizeof(params));
1061 params.name = "different_name";
1062 tmp = rte_hash_create(¶ms);
1064 rte_hash_free(handle);
1065 printf("Creating hash with valid parameters failed\n");
1070 rte_hash_free(handle);
1075 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1076 0x04, 0x05, 0x06, 0x07,
1077 0x08, 0x09, 0x0a, 0x0b,
1078 0x0c, 0x0d, 0x0e, 0x0f};
1079 static struct rte_hash_parameters hash_params_ex = {
1082 .bucket_entries = 4,
1085 .hash_func_init_val = 0,
1090 * add/delete key with jhash2
1093 test_hash_add_delete_jhash2(void)
1096 struct rte_hash *handle;
1099 hash_params_ex.name = "hash_test_jhash2";
1100 hash_params_ex.key_len = 4;
1101 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1103 handle = rte_hash_create(&hash_params_ex);
1104 if (handle == NULL) {
1105 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1108 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1110 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1114 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1115 if (pos2 < 0 || pos1 != pos2) {
1116 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1123 rte_hash_free(handle);
1129 * add/delete (2) key with jhash2
1132 test_hash_add_delete_2_jhash2(void)
1135 struct rte_hash *handle;
1138 hash_params_ex.name = "hash_test_2_jhash2";
1139 hash_params_ex.key_len = 8;
1140 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1142 handle = rte_hash_create(&hash_params_ex);
1146 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1150 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1151 if (pos2 < 0 || pos1 != pos2)
1158 rte_hash_free(handle);
1164 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1166 const uint32_t *k = key;
1168 RTE_SET_USED(length);
1170 return rte_jhash_1word(k[0], initval);
1174 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1176 const uint32_t *k = key;
1178 RTE_SET_USED(length);
1180 return rte_jhash_2words(k[0], k[1], initval);
1184 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1186 const uint32_t *k = key;
1188 RTE_SET_USED(length);
1190 return rte_jhash_3words(k[0], k[1], k[2], initval);
1194 * add/delete key with jhash 1word
1197 test_hash_add_delete_jhash_1word(void)
1200 struct rte_hash *handle;
1203 hash_params_ex.name = "hash_test_jhash_1word";
1204 hash_params_ex.key_len = 4;
1205 hash_params_ex.hash_func = test_hash_jhash_1word;
1207 handle = rte_hash_create(&hash_params_ex);
1209 goto fail_jhash_1word;
1211 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1213 goto fail_jhash_1word;
1215 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1216 if (pos2 < 0 || pos1 != pos2)
1217 goto fail_jhash_1word;
1223 rte_hash_free(handle);
1229 * add/delete key with jhash 2word
1232 test_hash_add_delete_jhash_2word(void)
1235 struct rte_hash *handle;
1238 hash_params_ex.name = "hash_test_jhash_2word";
1239 hash_params_ex.key_len = 8;
1240 hash_params_ex.hash_func = test_hash_jhash_2word;
1242 handle = rte_hash_create(&hash_params_ex);
1244 goto fail_jhash_2word;
1246 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1248 goto fail_jhash_2word;
1250 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1251 if (pos2 < 0 || pos1 != pos2)
1252 goto fail_jhash_2word;
1258 rte_hash_free(handle);
1264 * add/delete key with jhash 3word
1267 test_hash_add_delete_jhash_3word(void)
1270 struct rte_hash *handle;
1273 hash_params_ex.name = "hash_test_jhash_3word";
1274 hash_params_ex.key_len = 12;
1275 hash_params_ex.hash_func = test_hash_jhash_3word;
1277 handle = rte_hash_create(&hash_params_ex);
1279 goto fail_jhash_3word;
1281 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1283 goto fail_jhash_3word;
1285 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1286 if (pos2 < 0 || pos1 != pos2)
1287 goto fail_jhash_3word;
1293 rte_hash_free(handle);
1299 * Do all unit and performance tests.
1303 if (test_add_delete() < 0)
1305 if (test_hash_add_delete_jhash2() < 0)
1307 if (test_hash_add_delete_2_jhash2() < 0)
1309 if (test_hash_add_delete_jhash_1word() < 0)
1311 if (test_hash_add_delete_jhash_2word() < 0)
1313 if (test_hash_add_delete_jhash_3word() < 0)
1315 if (test_hash_find_existing() < 0)
1317 if (test_add_update_delete() < 0)
1319 if (test_five_keys() < 0)
1321 if (test_full_bucket() < 0)
1324 if (test_fbk_hash_find_existing() < 0)
1326 if (fbk_hash_unit_test() < 0)
1328 if (test_hash_creation_with_bad_parameters() < 0)
1330 if (test_hash_creation_with_good_parameters() < 0)
1333 run_hash_func_tests();
1342 printf("The Hash library is not included in this build\n");