4 * Copyright(c) 2010-2014 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.
40 #include <sys/queue.h>
42 #include <rte_common.h>
43 #include <rte_malloc.h>
44 #include <rte_cycles.h>
45 #include <rte_random.h>
46 #include <rte_memory.h>
47 #include <rte_memzone.h>
48 #include <rte_tailq.h>
51 #include <rte_string_fns.h>
55 #ifdef RTE_LIBRTE_HASH
58 #include <rte_fbk_hash.h>
59 #include <rte_jhash.h>
61 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
62 #include <rte_hash_crc.h>
65 /*******************************************************************************
66 * Hash function performance test configuration section. Each performance test
67 * will be performed HASHTEST_ITERATIONS times.
69 * The five arrays below control what tests are performed. Every combination
70 * from the array entries is tested.
72 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
73 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
75 static rte_hash_function hashtest_funcs[] = {rte_jhash};
77 static uint32_t hashtest_initvals[] = {0};
78 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
79 /******************************************************************************/
80 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
83 * Check condition and return an error if true. Assumes that "handle" is the
84 * name of the hash structure pointer to be freed.
86 #define RETURN_IF_ERROR(cond, str, ...) do { \
88 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
89 if (handle) rte_hash_free(handle); \
94 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
96 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
97 if (handle) rte_fbk_hash_free(handle); \
102 /* 5-tuple key type */
109 } __attribute__((packed));
112 * Hash function that always returns the same value, to easily test what
113 * happens when a bucket is full.
115 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
116 __attribute__((unused)) uint32_t key_len,
117 __attribute__((unused)) uint32_t init_val)
123 * Print out result of unit test hash operation.
125 #if defined(UNIT_TEST_HASH_VERBOSE)
126 static void print_key_info(const char *msg, const struct flow_key *key,
129 uint8_t *p = (uint8_t *)key;
132 printf("%s key:0x", msg);
133 for (i = 0; i < sizeof(struct flow_key); i++) {
134 printf("%02X", p[i]);
136 printf(" @ pos %d\n", pos);
139 static void print_key_info(__attribute__((unused)) const char *msg,
140 __attribute__((unused)) const struct flow_key *key,
141 __attribute__((unused)) int32_t pos)
146 /* Keys used by unit test functions */
147 static struct flow_key keys[5] = { {
148 .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
149 .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
154 .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
155 .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
160 .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
161 .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
166 .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
167 .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
172 .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
173 .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
179 /* Parameters used for hash table in unit test functions. Name set later. */
180 static struct rte_hash_parameters ut_params = {
183 .key_len = sizeof(struct flow_key), /* 13 */
184 .hash_func = rte_jhash,
185 .hash_func_init_val = 0,
190 * Test a hash function.
192 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
195 static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
199 for (i = 0; i < key_len; i++)
200 key[i] = (uint8_t) rte_rand();
202 /* just to be on the safe side */
206 f(key, key_len, init_val);
210 * Test all hash functions.
212 static void run_hash_func_tests(void)
217 i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
220 j < sizeof(hashtest_initvals) / sizeof(uint32_t);
223 k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
225 run_hash_func_test(hashtest_funcs[i],
226 hashtest_initvals[j],
227 hashtest_key_lens[k]);
234 * Basic sequence of operations for a single key:
240 static int test_add_delete(void)
242 struct rte_hash *handle;
243 /* test with standard add/lookup/delete functions */
244 int pos0, expectedPos0;
246 ut_params.name = "test1";
247 handle = rte_hash_create(&ut_params);
248 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
250 pos0 = rte_hash_add_key(handle, &keys[0]);
251 print_key_info("Add", &keys[0], pos0);
252 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
255 pos0 = rte_hash_lookup(handle, &keys[0]);
256 print_key_info("Lkp", &keys[0], pos0);
257 RETURN_IF_ERROR(pos0 != expectedPos0,
258 "failed to find key (pos0=%d)", pos0);
260 pos0 = rte_hash_del_key(handle, &keys[0]);
261 print_key_info("Del", &keys[0], pos0);
262 RETURN_IF_ERROR(pos0 != expectedPos0,
263 "failed to delete key (pos0=%d)", pos0);
265 pos0 = rte_hash_lookup(handle, &keys[0]);
266 print_key_info("Lkp", &keys[0], pos0);
267 RETURN_IF_ERROR(pos0 != -ENOENT,
268 "fail: found key after deleting! (pos0=%d)", pos0);
270 rte_hash_free(handle);
272 /* repeat test with precomputed hash functions */
273 hash_sig_t hash_value;
274 int pos1, expectedPos1;
276 handle = rte_hash_create(&ut_params);
277 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
279 hash_value = rte_hash_hash(handle, &keys[0]);
280 pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
281 print_key_info("Add", &keys[0], pos1);
282 RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
285 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
286 print_key_info("Lkp", &keys[0], pos1);
287 RETURN_IF_ERROR(pos1 != expectedPos1,
288 "failed to find key (pos1=%d)", pos1);
290 pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
291 print_key_info("Del", &keys[0], pos1);
292 RETURN_IF_ERROR(pos1 != expectedPos1,
293 "failed to delete key (pos1=%d)", pos1);
295 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
296 print_key_info("Lkp", &keys[0], pos1);
297 RETURN_IF_ERROR(pos1 != -ENOENT,
298 "fail: found key after deleting! (pos1=%d)", pos1);
300 rte_hash_free(handle);
306 * Sequence of operations for a single key:
311 * - lookup: hit (updated data)
316 static int test_add_update_delete(void)
318 struct rte_hash *handle;
319 int pos0, expectedPos0;
321 ut_params.name = "test2";
322 handle = rte_hash_create(&ut_params);
323 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
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: found non-existent key (pos0=%d)", pos0);
330 pos0 = rte_hash_add_key(handle, &keys[0]);
331 print_key_info("Add", &keys[0], pos0);
332 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
335 pos0 = rte_hash_lookup(handle, &keys[0]);
336 print_key_info("Lkp", &keys[0], pos0);
337 RETURN_IF_ERROR(pos0 != expectedPos0,
338 "failed to find key (pos0=%d)", pos0);
340 pos0 = rte_hash_add_key(handle, &keys[0]);
341 print_key_info("Add", &keys[0], pos0);
342 RETURN_IF_ERROR(pos0 != expectedPos0,
343 "failed to re-add key (pos0=%d)", pos0);
345 pos0 = rte_hash_lookup(handle, &keys[0]);
346 print_key_info("Lkp", &keys[0], pos0);
347 RETURN_IF_ERROR(pos0 != expectedPos0,
348 "failed to find key (pos0=%d)", pos0);
350 pos0 = rte_hash_del_key(handle, &keys[0]);
351 print_key_info("Del", &keys[0], pos0);
352 RETURN_IF_ERROR(pos0 != expectedPos0,
353 "failed to delete key (pos0=%d)", pos0);
355 pos0 = rte_hash_del_key(handle, &keys[0]);
356 print_key_info("Del", &keys[0], pos0);
357 RETURN_IF_ERROR(pos0 != -ENOENT,
358 "fail: deleted already deleted key (pos0=%d)", pos0);
360 pos0 = rte_hash_lookup(handle, &keys[0]);
361 print_key_info("Lkp", &keys[0], pos0);
362 RETURN_IF_ERROR(pos0 != -ENOENT,
363 "fail: found key after deleting! (pos0=%d)", pos0);
365 rte_hash_free(handle);
370 * Sequence of operations for find existing hash table
373 * - find existing table: hit
374 * - find non-existing table: miss
377 static int test_hash_find_existing(void)
379 struct rte_hash *handle = NULL, *result = NULL;
381 /* Create hash table. */
382 ut_params.name = "hash_find_existing";
383 handle = rte_hash_create(&ut_params);
384 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
386 /* Try to find existing hash table */
387 result = rte_hash_find_existing("hash_find_existing");
388 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
390 /* Try to find non-existing hash table */
391 result = rte_hash_find_existing("hash_find_non_existing");
392 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
395 rte_hash_free(handle);
401 * Sequence of operations for 5 keys
404 * - add keys (update)
405 * - lookup keys: hit (updated data)
406 * - delete keys : hit
407 * - lookup keys: miss
409 static int test_five_keys(void)
411 struct rte_hash *handle;
412 const void *key_array[5] = {0};
418 ut_params.name = "test3";
419 handle = rte_hash_create(&ut_params);
420 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
423 for (i = 0; i < 5; i++) {
424 pos[i] = rte_hash_add_key(handle, &keys[i]);
425 print_key_info("Add", &keys[i], pos[i]);
426 RETURN_IF_ERROR(pos[i] < 0,
427 "failed to add key (pos[%u]=%d)", i, pos[i]);
428 expected_pos[i] = pos[i];
432 for(i = 0; i < 5; i++)
433 key_array[i] = &keys[i];
435 ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
437 for(i = 0; i < 5; i++) {
438 print_key_info("Lkp", key_array[i], pos[i]);
439 RETURN_IF_ERROR(pos[i] != expected_pos[i],
440 "failed to find key (pos[%u]=%d)", i, pos[i]);
444 for (i = 0; i < 5; i++) {
445 pos[i] = rte_hash_add_key(handle, &keys[i]);
446 print_key_info("Add", &keys[i], pos[i]);
447 RETURN_IF_ERROR(pos[i] != expected_pos[i],
448 "failed to add key (pos[%u]=%d)", i, pos[i]);
452 for (i = 0; i < 5; i++) {
453 pos[i] = rte_hash_lookup(handle, &keys[i]);
454 print_key_info("Lkp", &keys[i], pos[i]);
455 RETURN_IF_ERROR(pos[i] != expected_pos[i],
456 "failed to find key (pos[%u]=%d)", i, pos[i]);
460 for (i = 0; i < 5; i++) {
461 pos[i] = rte_hash_del_key(handle, &keys[i]);
462 print_key_info("Del", &keys[i], pos[i]);
463 RETURN_IF_ERROR(pos[i] != expected_pos[i],
464 "failed to delete key (pos[%u]=%d)", i, pos[i]);
468 for (i = 0; i < 5; i++) {
469 pos[i] = rte_hash_lookup(handle, &keys[i]);
470 print_key_info("Lkp", &keys[i], pos[i]);
471 RETURN_IF_ERROR(pos[i] != -ENOENT,
472 "failed to find key (pos[%u]=%d)", i, pos[i]);
475 rte_hash_free(handle);
481 * Add keys to the same bucket until bucket full.
482 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
483 * first 4 successful, 5th unsuccessful
484 * - lookup the 5 keys: 4 hits, 1 miss
485 * - add the 5 keys again: 4 OK, one error as bucket is full
486 * - lookup the 5 keys: 4 hits (updated data), 1 miss
487 * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
488 * - lookup the 5 keys: 5 misses
489 * - add the 5th key: OK
490 * - lookup the 5th key: hit
492 static int test_full_bucket(void)
494 struct rte_hash_parameters params_pseudo_hash = {
498 .key_len = sizeof(struct flow_key), /* 13 */
499 .hash_func = pseudo_hash,
500 .hash_func_init_val = 0,
503 struct rte_hash *handle;
508 handle = rte_hash_create(¶ms_pseudo_hash);
509 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
512 for (i = 0; i < 4; i++) {
513 pos[i] = rte_hash_add_key(handle, &keys[i]);
514 print_key_info("Add", &keys[i], pos[i]);
515 RETURN_IF_ERROR(pos[i] < 0,
516 "failed to add key (pos[%u]=%d)", i, pos[i]);
517 expected_pos[i] = pos[i];
519 /* This shouldn't work because the bucket is full */
520 pos[4] = rte_hash_add_key(handle, &keys[4]);
521 print_key_info("Add", &keys[4], pos[4]);
522 RETURN_IF_ERROR(pos[4] != -ENOSPC,
523 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
526 for (i = 0; i < 4; i++) {
527 pos[i] = rte_hash_lookup(handle, &keys[i]);
528 print_key_info("Lkp", &keys[i], pos[i]);
529 RETURN_IF_ERROR(pos[i] != expected_pos[i],
530 "failed to find key (pos[%u]=%d)", i, pos[i]);
532 pos[4] = rte_hash_lookup(handle, &keys[4]);
533 print_key_info("Lkp", &keys[4], pos[4]);
534 RETURN_IF_ERROR(pos[4] != -ENOENT,
535 "fail: found non-existent key (pos[4]=%d)", pos[4]);
538 for (i = 0; i < 4; i++) {
539 pos[i] = rte_hash_add_key(handle, &keys[i]);
540 print_key_info("Add", &keys[i], pos[i]);
541 RETURN_IF_ERROR(pos[i] != expected_pos[i],
542 "failed to add key (pos[%u]=%d)", i, pos[i]);
544 pos[4] = rte_hash_add_key(handle, &keys[4]);
545 print_key_info("Add", &keys[4], pos[4]);
546 RETURN_IF_ERROR(pos[4] != -ENOSPC,
547 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
550 for (i = 0; i < 4; i++) {
551 pos[i] = rte_hash_lookup(handle, &keys[i]);
552 print_key_info("Lkp", &keys[i], pos[i]);
553 RETURN_IF_ERROR(pos[i] != expected_pos[i],
554 "failed to find key (pos[%u]=%d)", i, pos[i]);
556 pos[4] = rte_hash_lookup(handle, &keys[4]);
557 print_key_info("Lkp", &keys[4], pos[4]);
558 RETURN_IF_ERROR(pos[4] != -ENOENT,
559 "fail: found non-existent key (pos[4]=%d)", pos[4]);
561 /* Delete 1 key, check other keys are still found */
562 pos[1] = rte_hash_del_key(handle, &keys[1]);
563 print_key_info("Del", &keys[1], pos[1]);
564 RETURN_IF_ERROR(pos[1] != expected_pos[1],
565 "failed to delete key (pos[1]=%d)", pos[1]);
566 pos[3] = rte_hash_lookup(handle, &keys[3]);
567 print_key_info("Lkp", &keys[3], pos[3]);
568 RETURN_IF_ERROR(pos[3] != expected_pos[3],
569 "failed lookup after deleting key from same bucket "
570 "(pos[3]=%d)", pos[3]);
572 /* Go back to previous state */
573 pos[1] = rte_hash_add_key(handle, &keys[1]);
574 print_key_info("Add", &keys[1], pos[1]);
575 expected_pos[1] = pos[1];
576 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
579 for (i = 0; i < 4; i++) {
580 pos[i] = rte_hash_del_key(handle, &keys[i]);
581 print_key_info("Del", &keys[i], pos[i]);
582 RETURN_IF_ERROR(pos[i] != expected_pos[i],
583 "failed to delete key (pos[%u]=%d)", i, pos[i]);
585 pos[4] = rte_hash_del_key(handle, &keys[4]);
586 print_key_info("Del", &keys[4], pos[4]);
587 RETURN_IF_ERROR(pos[4] != -ENOENT,
588 "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
591 for (i = 0; i < 4; i++) {
592 pos[i] = rte_hash_lookup(handle, &keys[i]);
593 print_key_info("Lkp", &keys[i], pos[i]);
594 RETURN_IF_ERROR(pos[i] != -ENOENT,
595 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
598 /* Add and lookup the 5th key */
599 pos[4] = rte_hash_add_key(handle, &keys[4]);
600 print_key_info("Add", &keys[4], pos[4]);
601 RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
602 expected_pos[4] = pos[4];
603 pos[4] = rte_hash_lookup(handle, &keys[4]);
604 print_key_info("Lkp", &keys[4], pos[4]);
605 RETURN_IF_ERROR(pos[4] != expected_pos[4],
606 "failed to find key (pos[4]=%d)", pos[4]);
608 rte_hash_free(handle);
610 /* Cover the NULL case. */
615 /******************************************************************************/
617 fbk_hash_unit_test(void)
619 struct rte_fbk_hash_params params = {
620 .name = "fbk_hash_test",
621 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
622 .entries_per_bucket = 4,
626 struct rte_fbk_hash_params invalid_params_1 = {
628 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
629 .entries_per_bucket = 4,
633 struct rte_fbk_hash_params invalid_params_2 = {
636 .entries_per_bucket = 3, /* Not power of 2 */
640 struct rte_fbk_hash_params invalid_params_3 = {
642 .entries = 0, /* Entries is 0 */
643 .entries_per_bucket = 4,
647 struct rte_fbk_hash_params invalid_params_4 = {
649 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
650 .entries_per_bucket = 0, /* Entries per bucket is 0 */
654 struct rte_fbk_hash_params invalid_params_5 = {
657 .entries_per_bucket = 8, /* Entries per bucket > entries */
661 struct rte_fbk_hash_params invalid_params_6 = {
663 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
664 .entries_per_bucket = 4,
668 struct rte_fbk_hash_params invalid_params_7 = {
670 .entries = RTE_FBK_HASH_ENTRIES_MAX,
671 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */
675 struct rte_fbk_hash_params invalid_params_8 = {
677 .entries = RTE_FBK_HASH_ENTRIES_MAX,
678 .entries_per_bucket = 4,
679 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
682 /* try to create two hashes with identical names
683 * in this case, trying to create a second one will not
684 * fail but will simply return pointer to the existing
685 * hash with that name. sort of like a "find hash by name" :-)
687 struct rte_fbk_hash_params invalid_params_same_name_1 = {
688 .name = "same_name", /* hash with identical name */
690 .entries_per_bucket = 2,
694 /* trying to create this hash should return a pointer to an existing hash */
695 struct rte_fbk_hash_params invalid_params_same_name_2 = {
696 .name = "same_name", /* hash with identical name */
697 .entries = RTE_FBK_HASH_ENTRIES_MAX,
698 .entries_per_bucket = 4,
702 /* this is a sanity check for "same name" test
703 * creating this hash will check if we are actually able to create
704 * multiple hashes with different names (instead of having just one).
706 struct rte_fbk_hash_params different_name = {
707 .name = "different_name", /* different name */
708 .entries = RTE_FBK_HASH_ENTRIES_MAX,
709 .entries_per_bucket = 4,
713 struct rte_fbk_hash_params params_jhash = {
715 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
716 .entries_per_bucket = 4,
718 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
719 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
722 struct rte_fbk_hash_params params_nohash = {
723 .name = "valid nohash",
724 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
725 .entries_per_bucket = 4,
727 .hash_func = NULL, /* Tests for null hash_func */
728 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
731 struct rte_fbk_hash_table *handle, *tmp;
733 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
734 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
739 /* Try creating hashes with invalid parameters */
740 printf("# Testing hash creation with invalid parameters "
741 "- expert error msgs\n");
742 handle = rte_fbk_hash_create(&invalid_params_1);
743 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
745 handle = rte_fbk_hash_create(&invalid_params_2);
746 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
748 handle = rte_fbk_hash_create(&invalid_params_3);
749 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
751 handle = rte_fbk_hash_create(&invalid_params_4);
752 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
754 handle = rte_fbk_hash_create(&invalid_params_5);
755 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
757 handle = rte_fbk_hash_create(&invalid_params_6);
758 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
760 handle = rte_fbk_hash_create(&invalid_params_7);
761 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
763 handle = rte_fbk_hash_create(&invalid_params_8);
764 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
766 handle = rte_fbk_hash_create(&invalid_params_same_name_1);
767 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
769 tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
770 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
772 printf("ERROR line %d: hashes should have been the same\n", __LINE__);
773 rte_fbk_hash_free(handle);
774 rte_fbk_hash_free(tmp);
778 /* we are not freeing tmp or handle here because we need a hash list
779 * to be not empty for the next test */
781 /* create a hash in non-empty list - good for coverage */
782 tmp = rte_fbk_hash_create(&different_name);
783 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
785 /* free both hashes */
786 rte_fbk_hash_free(handle);
787 rte_fbk_hash_free(tmp);
789 /* Create empty jhash hash. */
790 handle = rte_fbk_hash_create(¶ms_jhash);
791 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
794 rte_fbk_hash_free(handle);
796 /* Create empty jhash hash. */
797 handle = rte_fbk_hash_create(¶ms_nohash);
798 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
801 rte_fbk_hash_free(handle);
803 /* Create empty hash. */
804 handle = rte_fbk_hash_create(¶ms);
805 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
807 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
808 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
809 "load factor right after creation is not zero but it should be");
811 for (i = 0; i < 5; i++) {
812 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
813 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
816 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
817 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
818 "load factor now is not as expected");
819 /* Find value of added keys. */
820 for (i = 0; i < 5; i++) {
821 status = rte_fbk_hash_lookup(handle, keys[i]);
822 RETURN_IF_ERROR_FBK(status != vals[i],
823 "fbk hash lookup failed");
826 /* Change value of added keys. */
827 for (i = 0; i < 5; i++) {
828 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
829 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
832 /* Find new values. */
833 for (i = 0; i < 5; i++) {
834 status = rte_fbk_hash_lookup(handle, keys[i]);
835 RETURN_IF_ERROR_FBK(status != vals[4-i],
836 "fbk hash lookup failed");
839 /* Delete keys individually. */
840 for (i = 0; i < 5; i++) {
841 status = rte_fbk_hash_delete_key(handle, keys[i]);
842 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
845 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
846 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
847 "load factor right after deletion is not zero but it should be");
848 /* Lookup should now fail. */
849 for (i = 0; i < 5; i++) {
850 status = rte_fbk_hash_lookup(handle, keys[i]);
851 RETURN_IF_ERROR_FBK(status == 0,
852 "fbk hash lookup should have failed");
855 /* Add keys again. */
856 for (i = 0; i < 5; i++) {
857 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
858 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
861 /* Make sure they were added. */
862 for (i = 0; i < 5; i++) {
863 status = rte_fbk_hash_lookup(handle, keys[i]);
864 RETURN_IF_ERROR_FBK(status != vals[i],
865 "fbk hash lookup failed");
868 /* Clear all entries. */
869 rte_fbk_hash_clear_all(handle);
871 /* Lookup should fail. */
872 for (i = 0; i < 5; i++) {
873 status = rte_fbk_hash_lookup(handle, keys[i]);
874 RETURN_IF_ERROR_FBK(status == 0,
875 "fbk hash lookup should have failed");
880 /* fill up the hash_table */
881 for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
882 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
884 /* Find non-existent key in a full hashtable */
885 status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
886 RETURN_IF_ERROR_FBK(status != -ENOENT,
887 "fbk hash lookup succeeded");
889 /* Delete non-existent key in a full hashtable */
890 status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
891 RETURN_IF_ERROR_FBK(status != -ENOENT,
892 "fbk hash delete succeeded");
894 /* Delete one key from a full hashtable */
895 status = rte_fbk_hash_delete_key(handle, 1);
896 RETURN_IF_ERROR_FBK(status != 0,
897 "fbk hash delete failed");
899 /* Clear all entries. */
900 rte_fbk_hash_clear_all(handle);
903 rte_fbk_hash_free(handle);
905 /* Cover the NULL case. */
906 rte_fbk_hash_free(0);
912 * Sequence of operations for find existing fbk hash table
915 * - find existing table: hit
916 * - find non-existing table: miss
919 static int test_fbk_hash_find_existing(void)
921 struct rte_fbk_hash_params params = {
922 .name = "fbk_hash_find_existing",
923 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
924 .entries_per_bucket = 4,
927 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
929 /* Create hash table. */
930 handle = rte_fbk_hash_create(¶ms);
931 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
933 /* Try to find existing fbk hash table */
934 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
935 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
937 /* Try to find non-existing fbk hash table */
938 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
939 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
942 rte_fbk_hash_free(handle);
948 * Do tests for hash creation with bad parameters.
950 static int test_hash_creation_with_bad_parameters(void)
952 struct rte_hash *handle;
953 struct rte_hash_parameters params;
955 handle = rte_hash_create(NULL);
956 if (handle != NULL) {
957 rte_hash_free(handle);
958 printf("Impossible creating hash sucessfully without any parameter\n");
962 memcpy(¶ms, &ut_params, sizeof(params));
963 params.name = "creation_with_bad_parameters_0";
964 params.entries = RTE_HASH_ENTRIES_MAX + 1;
965 handle = rte_hash_create(¶ms);
966 if (handle != NULL) {
967 rte_hash_free(handle);
968 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
972 memcpy(¶ms, &ut_params, sizeof(params));
973 params.name = "creation_with_bad_parameters_1";
974 params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
975 handle = rte_hash_create(¶ms);
976 if (handle != NULL) {
977 rte_hash_free(handle);
978 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
982 memcpy(¶ms, &ut_params, sizeof(params));
983 params.name = "creation_with_bad_parameters_2";
984 params.entries = params.bucket_entries - 1;
985 handle = rte_hash_create(¶ms);
986 if (handle != NULL) {
987 rte_hash_free(handle);
988 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
992 memcpy(¶ms, &ut_params, sizeof(params));
993 params.name = "creation_with_bad_parameters_3";
994 params.entries = params.entries - 1;
995 handle = rte_hash_create(¶ms);
996 if (handle != NULL) {
997 rte_hash_free(handle);
998 printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
1002 memcpy(¶ms, &ut_params, sizeof(params));
1003 params.name = "creation_with_bad_parameters_4";
1004 params.bucket_entries = params.bucket_entries - 1;
1005 handle = rte_hash_create(¶ms);
1006 if (handle != NULL) {
1007 rte_hash_free(handle);
1008 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
1012 memcpy(¶ms, &ut_params, sizeof(params));
1013 params.name = "creation_with_bad_parameters_5";
1015 handle = rte_hash_create(¶ms);
1016 if (handle != NULL) {
1017 rte_hash_free(handle);
1018 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1022 memcpy(¶ms, &ut_params, sizeof(params));
1023 params.name = "creation_with_bad_parameters_6";
1024 params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
1025 handle = rte_hash_create(¶ms);
1026 if (handle != NULL) {
1027 rte_hash_free(handle);
1028 printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n");
1032 memcpy(¶ms, &ut_params, sizeof(params));
1033 params.name = "creation_with_bad_parameters_7";
1034 params.socket_id = RTE_MAX_NUMA_NODES + 1;
1035 handle = rte_hash_create(¶ms);
1036 if (handle != NULL) {
1037 rte_hash_free(handle);
1038 printf("Impossible creating hash sucessfully with invalid socket\n");
1042 rte_hash_free(handle);
1048 * Do tests for hash creation with parameters that look incorrect
1049 * but are actually valid.
1052 test_hash_creation_with_good_parameters(void)
1054 struct rte_hash *handle, *tmp;
1055 struct rte_hash_parameters params;
1057 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1058 memcpy(¶ms, &ut_params, sizeof(params));
1059 params.name = "same_name";
1060 params.hash_func = NULL;
1061 handle = rte_hash_create(¶ms);
1062 if (handle == NULL) {
1063 printf("Creating hash with null hash_func failed\n");
1066 if (handle->hash_func == NULL) {
1067 printf("Hash function should have been DEFAULT_HASH_FUNC\n");
1071 /* this test is trying to create a hash with the same name as previous one.
1072 * this should return a pointer to the hash we previously created.
1073 * the previous hash isn't freed exactly for the purpose of it being in
1076 memcpy(¶ms, &ut_params, sizeof(params));
1077 params.name = "same_name";
1078 tmp = rte_hash_create(¶ms);
1080 /* check if the returned handle is actually equal to the previous hash */
1081 if (handle != tmp) {
1082 rte_hash_free(handle);
1084 printf("Creating hash with existing name was successful\n");
1088 /* try creating hash when there already are hashes in the list.
1089 * the previous hash is not freed to have a non-empty hash list.
1090 * the other hash that's in the list is still pointed to by "handle" var.
1092 memcpy(¶ms, &ut_params, sizeof(params));
1093 params.name = "different_name";
1094 tmp = rte_hash_create(¶ms);
1096 rte_hash_free(handle);
1097 printf("Creating hash with valid parameters failed\n");
1102 rte_hash_free(handle);
1107 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1108 0x04, 0x05, 0x06, 0x07,
1109 0x08, 0x09, 0x0a, 0x0b,
1110 0x0c, 0x0d, 0x0e, 0x0f};
1111 static struct rte_hash_parameters hash_params_ex = {
1114 .bucket_entries = 4,
1117 .hash_func_init_val = 0,
1122 * add/delete key with jhash2
1125 test_hash_add_delete_jhash2(void)
1128 struct rte_hash *handle;
1131 hash_params_ex.name = "hash_test_jhash2";
1132 hash_params_ex.key_len = 4;
1133 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1135 handle = rte_hash_create(&hash_params_ex);
1136 if (handle == NULL) {
1137 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1140 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1142 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1146 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1147 if (pos2 < 0 || pos1 != pos2) {
1148 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1155 rte_hash_free(handle);
1161 * add/delete (2) key with jhash2
1164 test_hash_add_delete_2_jhash2(void)
1167 struct rte_hash *handle;
1170 hash_params_ex.name = "hash_test_2_jhash2";
1171 hash_params_ex.key_len = 8;
1172 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1174 handle = rte_hash_create(&hash_params_ex);
1178 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1182 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1183 if (pos2 < 0 || pos1 != pos2)
1190 rte_hash_free(handle);
1196 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1198 const uint32_t *k = key;
1200 RTE_SET_USED(length);
1202 return rte_jhash_1word(k[0], initval);
1206 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1208 const uint32_t *k = key;
1210 RTE_SET_USED(length);
1212 return rte_jhash_2words(k[0], k[1], initval);
1216 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1218 const uint32_t *k = key;
1220 RTE_SET_USED(length);
1222 return rte_jhash_3words(k[0], k[1], k[2], initval);
1226 * add/delete key with jhash 1word
1229 test_hash_add_delete_jhash_1word(void)
1232 struct rte_hash *handle;
1235 hash_params_ex.name = "hash_test_jhash_1word";
1236 hash_params_ex.key_len = 4;
1237 hash_params_ex.hash_func = test_hash_jhash_1word;
1239 handle = rte_hash_create(&hash_params_ex);
1241 goto fail_jhash_1word;
1243 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1245 goto fail_jhash_1word;
1247 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1248 if (pos2 < 0 || pos1 != pos2)
1249 goto fail_jhash_1word;
1255 rte_hash_free(handle);
1261 * add/delete key with jhash 2word
1264 test_hash_add_delete_jhash_2word(void)
1267 struct rte_hash *handle;
1270 hash_params_ex.name = "hash_test_jhash_2word";
1271 hash_params_ex.key_len = 8;
1272 hash_params_ex.hash_func = test_hash_jhash_2word;
1274 handle = rte_hash_create(&hash_params_ex);
1276 goto fail_jhash_2word;
1278 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1280 goto fail_jhash_2word;
1282 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1283 if (pos2 < 0 || pos1 != pos2)
1284 goto fail_jhash_2word;
1290 rte_hash_free(handle);
1296 * add/delete key with jhash 3word
1299 test_hash_add_delete_jhash_3word(void)
1302 struct rte_hash *handle;
1305 hash_params_ex.name = "hash_test_jhash_3word";
1306 hash_params_ex.key_len = 12;
1307 hash_params_ex.hash_func = test_hash_jhash_3word;
1309 handle = rte_hash_create(&hash_params_ex);
1311 goto fail_jhash_3word;
1313 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1315 goto fail_jhash_3word;
1317 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1318 if (pos2 < 0 || pos1 != pos2)
1319 goto fail_jhash_3word;
1325 rte_hash_free(handle);
1331 * Do all unit and performance tests.
1335 if (test_add_delete() < 0)
1337 if (test_hash_add_delete_jhash2() < 0)
1339 if (test_hash_add_delete_2_jhash2() < 0)
1341 if (test_hash_add_delete_jhash_1word() < 0)
1343 if (test_hash_add_delete_jhash_2word() < 0)
1345 if (test_hash_add_delete_jhash_3word() < 0)
1347 if (test_hash_find_existing() < 0)
1349 if (test_add_update_delete() < 0)
1351 if (test_five_keys() < 0)
1353 if (test_full_bucket() < 0)
1356 if (test_fbk_hash_find_existing() < 0)
1358 if (fbk_hash_unit_test() < 0)
1360 if (test_hash_creation_with_bad_parameters() < 0)
1362 if (test_hash_creation_with_good_parameters() < 0)
1365 run_hash_func_tests();
1369 #else /* RTE_LIBRTE_HASH */
1374 printf("The Hash library is not included in this build\n");
1378 #endif /* RTE_LIBRTE_HASH */