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>
52 #include <cmdline_parse.h>
56 #ifdef RTE_LIBRTE_HASH
59 #include <rte_fbk_hash.h>
60 #include <rte_jhash.h>
62 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
63 #include <rte_hash_crc.h>
66 /*******************************************************************************
67 * Hash function performance test configuration section. Each performance test
68 * will be performed HASHTEST_ITERATIONS times.
70 * The five arrays below control what tests are performed. Every combination
71 * from the array entries is tested.
73 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
74 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
76 static rte_hash_function hashtest_funcs[] = {rte_jhash};
78 static uint32_t hashtest_initvals[] = {0};
79 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
80 /******************************************************************************/
81 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
84 * Check condition and return an error if true. Assumes that "handle" is the
85 * name of the hash structure pointer to be freed.
87 #define RETURN_IF_ERROR(cond, str, ...) do { \
89 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
90 if (handle) rte_hash_free(handle); \
95 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
97 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
98 if (handle) rte_fbk_hash_free(handle); \
103 /* 5-tuple key type */
110 } __attribute__((packed));
113 * Hash function that always returns the same value, to easily test what
114 * happens when a bucket is full.
116 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
117 __attribute__((unused)) uint32_t key_len,
118 __attribute__((unused)) uint32_t init_val)
124 * Print out result of unit test hash operation.
126 #if defined(UNIT_TEST_HASH_VERBOSE)
127 static void print_key_info(const char *msg, const struct flow_key *key,
130 uint8_t *p = (uint8_t *)key;
133 printf("%s key:0x", msg);
134 for (i = 0; i < sizeof(struct flow_key); i++) {
135 printf("%02X", p[i]);
137 printf(" @ pos %d\n", pos);
140 static void print_key_info(__attribute__((unused)) const char *msg,
141 __attribute__((unused)) const struct flow_key *key,
142 __attribute__((unused)) int32_t pos)
147 /* Keys used by unit test functions */
148 static struct flow_key keys[5] = { {
149 .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
150 .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
155 .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
156 .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
161 .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
162 .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
167 .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
168 .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
173 .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
174 .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
180 /* Parameters used for hash table in unit test functions. Name set later. */
181 static struct rte_hash_parameters ut_params = {
184 .key_len = sizeof(struct flow_key), /* 13 */
185 .hash_func = rte_jhash,
186 .hash_func_init_val = 0,
191 * Test a hash function.
193 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
196 static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
200 for (i = 0; i < key_len; i++)
201 key[i] = (uint8_t) rte_rand();
203 /* just to be on the safe side */
207 f(key, key_len, init_val);
211 * Test all hash functions.
213 static void run_hash_func_tests(void)
218 i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
221 j < sizeof(hashtest_initvals) / sizeof(uint32_t);
224 k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
226 run_hash_func_test(hashtest_funcs[i],
227 hashtest_initvals[j],
228 hashtest_key_lens[k]);
235 * Basic sequence of operations for a single key:
241 static int test_add_delete(void)
243 struct rte_hash *handle;
244 /* test with standard add/lookup/delete functions */
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);
273 /* repeat test with precomputed hash functions */
274 hash_sig_t hash_value;
275 int pos1, expectedPos1;
277 handle = rte_hash_create(&ut_params);
278 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
280 hash_value = rte_hash_hash(handle, &keys[0]);
281 pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
282 print_key_info("Add", &keys[0], pos1);
283 RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
286 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
287 print_key_info("Lkp", &keys[0], pos1);
288 RETURN_IF_ERROR(pos1 != expectedPos1,
289 "failed to find key (pos1=%d)", pos1);
291 pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
292 print_key_info("Del", &keys[0], pos1);
293 RETURN_IF_ERROR(pos1 != expectedPos1,
294 "failed to delete key (pos1=%d)", pos1);
296 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
297 print_key_info("Lkp", &keys[0], pos1);
298 RETURN_IF_ERROR(pos1 != -ENOENT,
299 "fail: found key after deleting! (pos1=%d)", pos1);
301 rte_hash_free(handle);
307 * Sequence of operations for a single key:
312 * - lookup: hit (updated data)
317 static int test_add_update_delete(void)
319 struct rte_hash *handle;
320 int pos0, expectedPos0;
322 ut_params.name = "test2";
323 handle = rte_hash_create(&ut_params);
324 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
326 pos0 = rte_hash_del_key(handle, &keys[0]);
327 print_key_info("Del", &keys[0], pos0);
328 RETURN_IF_ERROR(pos0 != -ENOENT,
329 "fail: found non-existent key (pos0=%d)", pos0);
331 pos0 = rte_hash_add_key(handle, &keys[0]);
332 print_key_info("Add", &keys[0], pos0);
333 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
336 pos0 = rte_hash_lookup(handle, &keys[0]);
337 print_key_info("Lkp", &keys[0], pos0);
338 RETURN_IF_ERROR(pos0 != expectedPos0,
339 "failed to find key (pos0=%d)", pos0);
341 pos0 = rte_hash_add_key(handle, &keys[0]);
342 print_key_info("Add", &keys[0], pos0);
343 RETURN_IF_ERROR(pos0 != expectedPos0,
344 "failed to re-add key (pos0=%d)", pos0);
346 pos0 = rte_hash_lookup(handle, &keys[0]);
347 print_key_info("Lkp", &keys[0], pos0);
348 RETURN_IF_ERROR(pos0 != expectedPos0,
349 "failed to find key (pos0=%d)", pos0);
351 pos0 = rte_hash_del_key(handle, &keys[0]);
352 print_key_info("Del", &keys[0], pos0);
353 RETURN_IF_ERROR(pos0 != expectedPos0,
354 "failed to delete key (pos0=%d)", pos0);
356 pos0 = rte_hash_del_key(handle, &keys[0]);
357 print_key_info("Del", &keys[0], pos0);
358 RETURN_IF_ERROR(pos0 != -ENOENT,
359 "fail: deleted already deleted key (pos0=%d)", pos0);
361 pos0 = rte_hash_lookup(handle, &keys[0]);
362 print_key_info("Lkp", &keys[0], pos0);
363 RETURN_IF_ERROR(pos0 != -ENOENT,
364 "fail: found key after deleting! (pos0=%d)", pos0);
366 rte_hash_free(handle);
371 * Sequence of operations for find existing hash table
374 * - find existing table: hit
375 * - find non-existing table: miss
378 static int test_hash_find_existing(void)
380 struct rte_hash *handle = NULL, *result = NULL;
382 /* Create hash table. */
383 ut_params.name = "hash_find_existing";
384 handle = rte_hash_create(&ut_params);
385 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
387 /* Try to find existing hash table */
388 result = rte_hash_find_existing("hash_find_existing");
389 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
391 /* Try to find non-existing hash table */
392 result = rte_hash_find_existing("hash_find_non_existing");
393 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
396 rte_hash_free(handle);
402 * Sequence of operations for 5 keys
405 * - add keys (update)
406 * - lookup keys: hit (updated data)
407 * - delete keys : hit
408 * - lookup keys: miss
410 static int test_five_keys(void)
412 struct rte_hash *handle;
413 const void *key_array[5] = {0};
419 ut_params.name = "test3";
420 handle = rte_hash_create(&ut_params);
421 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
424 for (i = 0; i < 5; i++) {
425 pos[i] = rte_hash_add_key(handle, &keys[i]);
426 print_key_info("Add", &keys[i], pos[i]);
427 RETURN_IF_ERROR(pos[i] < 0,
428 "failed to add key (pos[%u]=%d)", i, pos[i]);
429 expected_pos[i] = pos[i];
433 for(i = 0; i < 5; i++)
434 key_array[i] = &keys[i];
436 ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
438 for(i = 0; i < 5; i++) {
439 print_key_info("Lkp", key_array[i], pos[i]);
440 RETURN_IF_ERROR(pos[i] != expected_pos[i],
441 "failed to find key (pos[%u]=%d)", i, pos[i]);
445 for (i = 0; i < 5; i++) {
446 pos[i] = rte_hash_add_key(handle, &keys[i]);
447 print_key_info("Add", &keys[i], pos[i]);
448 RETURN_IF_ERROR(pos[i] != expected_pos[i],
449 "failed to add key (pos[%u]=%d)", i, pos[i]);
453 for (i = 0; i < 5; i++) {
454 pos[i] = rte_hash_lookup(handle, &keys[i]);
455 print_key_info("Lkp", &keys[i], pos[i]);
456 RETURN_IF_ERROR(pos[i] != expected_pos[i],
457 "failed to find key (pos[%u]=%d)", i, pos[i]);
461 for (i = 0; i < 5; i++) {
462 pos[i] = rte_hash_del_key(handle, &keys[i]);
463 print_key_info("Del", &keys[i], pos[i]);
464 RETURN_IF_ERROR(pos[i] != expected_pos[i],
465 "failed to delete key (pos[%u]=%d)", i, pos[i]);
469 for (i = 0; i < 5; i++) {
470 pos[i] = rte_hash_lookup(handle, &keys[i]);
471 print_key_info("Lkp", &keys[i], pos[i]);
472 RETURN_IF_ERROR(pos[i] != -ENOENT,
473 "failed to find key (pos[%u]=%d)", i, pos[i]);
476 rte_hash_free(handle);
482 * Add keys to the same bucket until bucket full.
483 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
484 * first 4 successful, 5th unsuccessful
485 * - lookup the 5 keys: 4 hits, 1 miss
486 * - add the 5 keys again: 4 OK, one error as bucket is full
487 * - lookup the 5 keys: 4 hits (updated data), 1 miss
488 * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
489 * - lookup the 5 keys: 5 misses
490 * - add the 5th key: OK
491 * - lookup the 5th key: hit
493 static int test_full_bucket(void)
495 struct rte_hash_parameters params_pseudo_hash = {
499 .key_len = sizeof(struct flow_key), /* 13 */
500 .hash_func = pseudo_hash,
501 .hash_func_init_val = 0,
504 struct rte_hash *handle;
509 handle = rte_hash_create(¶ms_pseudo_hash);
510 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
513 for (i = 0; i < 4; i++) {
514 pos[i] = rte_hash_add_key(handle, &keys[i]);
515 print_key_info("Add", &keys[i], pos[i]);
516 RETURN_IF_ERROR(pos[i] < 0,
517 "failed to add key (pos[%u]=%d)", i, pos[i]);
518 expected_pos[i] = pos[i];
520 /* This shouldn't work because the bucket is full */
521 pos[4] = rte_hash_add_key(handle, &keys[4]);
522 print_key_info("Add", &keys[4], pos[4]);
523 RETURN_IF_ERROR(pos[4] != -ENOSPC,
524 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
527 for (i = 0; i < 4; i++) {
528 pos[i] = rte_hash_lookup(handle, &keys[i]);
529 print_key_info("Lkp", &keys[i], pos[i]);
530 RETURN_IF_ERROR(pos[i] != expected_pos[i],
531 "failed to find key (pos[%u]=%d)", i, pos[i]);
533 pos[4] = rte_hash_lookup(handle, &keys[4]);
534 print_key_info("Lkp", &keys[4], pos[4]);
535 RETURN_IF_ERROR(pos[4] != -ENOENT,
536 "fail: found non-existent key (pos[4]=%d)", pos[4]);
539 for (i = 0; i < 4; i++) {
540 pos[i] = rte_hash_add_key(handle, &keys[i]);
541 print_key_info("Add", &keys[i], pos[i]);
542 RETURN_IF_ERROR(pos[i] != expected_pos[i],
543 "failed to add key (pos[%u]=%d)", i, pos[i]);
545 pos[4] = rte_hash_add_key(handle, &keys[4]);
546 print_key_info("Add", &keys[4], pos[4]);
547 RETURN_IF_ERROR(pos[4] != -ENOSPC,
548 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
551 for (i = 0; i < 4; i++) {
552 pos[i] = rte_hash_lookup(handle, &keys[i]);
553 print_key_info("Lkp", &keys[i], pos[i]);
554 RETURN_IF_ERROR(pos[i] != expected_pos[i],
555 "failed to find key (pos[%u]=%d)", i, pos[i]);
557 pos[4] = rte_hash_lookup(handle, &keys[4]);
558 print_key_info("Lkp", &keys[4], pos[4]);
559 RETURN_IF_ERROR(pos[4] != -ENOENT,
560 "fail: found non-existent key (pos[4]=%d)", pos[4]);
562 /* Delete 1 key, check other keys are still found */
563 pos[1] = rte_hash_del_key(handle, &keys[1]);
564 print_key_info("Del", &keys[1], pos[1]);
565 RETURN_IF_ERROR(pos[1] != expected_pos[1],
566 "failed to delete key (pos[1]=%d)", pos[1]);
567 pos[3] = rte_hash_lookup(handle, &keys[3]);
568 print_key_info("Lkp", &keys[3], pos[3]);
569 RETURN_IF_ERROR(pos[3] != expected_pos[3],
570 "failed lookup after deleting key from same bucket "
571 "(pos[3]=%d)", pos[3]);
573 /* Go back to previous state */
574 pos[1] = rte_hash_add_key(handle, &keys[1]);
575 print_key_info("Add", &keys[1], pos[1]);
576 expected_pos[1] = pos[1];
577 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
580 for (i = 0; i < 4; i++) {
581 pos[i] = rte_hash_del_key(handle, &keys[i]);
582 print_key_info("Del", &keys[i], pos[i]);
583 RETURN_IF_ERROR(pos[i] != expected_pos[i],
584 "failed to delete key (pos[%u]=%d)", i, pos[i]);
586 pos[4] = rte_hash_del_key(handle, &keys[4]);
587 print_key_info("Del", &keys[4], pos[4]);
588 RETURN_IF_ERROR(pos[4] != -ENOENT,
589 "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
592 for (i = 0; i < 4; i++) {
593 pos[i] = rte_hash_lookup(handle, &keys[i]);
594 print_key_info("Lkp", &keys[i], pos[i]);
595 RETURN_IF_ERROR(pos[i] != -ENOENT,
596 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
599 /* Add and lookup the 5th key */
600 pos[4] = rte_hash_add_key(handle, &keys[4]);
601 print_key_info("Add", &keys[4], pos[4]);
602 RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
603 expected_pos[4] = pos[4];
604 pos[4] = rte_hash_lookup(handle, &keys[4]);
605 print_key_info("Lkp", &keys[4], pos[4]);
606 RETURN_IF_ERROR(pos[4] != expected_pos[4],
607 "failed to find key (pos[4]=%d)", pos[4]);
609 rte_hash_free(handle);
611 /* Cover the NULL case. */
616 /******************************************************************************/
618 fbk_hash_unit_test(void)
620 struct rte_fbk_hash_params params = {
621 .name = "fbk_hash_test",
622 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
623 .entries_per_bucket = 4,
627 struct rte_fbk_hash_params invalid_params_1 = {
629 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
630 .entries_per_bucket = 4,
634 struct rte_fbk_hash_params invalid_params_2 = {
637 .entries_per_bucket = 3, /* Not power of 2 */
641 struct rte_fbk_hash_params invalid_params_3 = {
643 .entries = 0, /* Entries is 0 */
644 .entries_per_bucket = 4,
648 struct rte_fbk_hash_params invalid_params_4 = {
650 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
651 .entries_per_bucket = 0, /* Entries per bucket is 0 */
655 struct rte_fbk_hash_params invalid_params_5 = {
658 .entries_per_bucket = 8, /* Entries per bucket > entries */
662 struct rte_fbk_hash_params invalid_params_6 = {
664 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
665 .entries_per_bucket = 4,
669 struct rte_fbk_hash_params invalid_params_7 = {
671 .entries = RTE_FBK_HASH_ENTRIES_MAX,
672 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */
676 struct rte_fbk_hash_params invalid_params_8 = {
678 .entries = RTE_FBK_HASH_ENTRIES_MAX,
679 .entries_per_bucket = 4,
680 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
683 /* try to create two hashes with identical names
684 * in this case, trying to create a second one will not
685 * fail but will simply return pointer to the existing
686 * hash with that name. sort of like a "find hash by name" :-)
688 struct rte_fbk_hash_params invalid_params_same_name_1 = {
689 .name = "same_name", /* hash with identical name */
691 .entries_per_bucket = 2,
695 /* trying to create this hash should return a pointer to an existing hash */
696 struct rte_fbk_hash_params invalid_params_same_name_2 = {
697 .name = "same_name", /* hash with identical name */
698 .entries = RTE_FBK_HASH_ENTRIES_MAX,
699 .entries_per_bucket = 4,
703 /* this is a sanity check for "same name" test
704 * creating this hash will check if we are actually able to create
705 * multiple hashes with different names (instead of having just one).
707 struct rte_fbk_hash_params different_name = {
708 .name = "different_name", /* different name */
709 .entries = RTE_FBK_HASH_ENTRIES_MAX,
710 .entries_per_bucket = 4,
714 struct rte_fbk_hash_params params_jhash = {
716 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
717 .entries_per_bucket = 4,
719 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
720 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
723 struct rte_fbk_hash_params params_nohash = {
724 .name = "valid nohash",
725 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
726 .entries_per_bucket = 4,
728 .hash_func = NULL, /* Tests for null hash_func */
729 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
732 struct rte_fbk_hash_table *handle, *tmp;
734 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
735 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
740 /* Try creating hashes with invalid parameters */
741 printf("# Testing hash creation with invalid parameters "
742 "- expert error msgs\n");
743 handle = rte_fbk_hash_create(&invalid_params_1);
744 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
746 handle = rte_fbk_hash_create(&invalid_params_2);
747 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
749 handle = rte_fbk_hash_create(&invalid_params_3);
750 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
752 handle = rte_fbk_hash_create(&invalid_params_4);
753 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
755 handle = rte_fbk_hash_create(&invalid_params_5);
756 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
758 handle = rte_fbk_hash_create(&invalid_params_6);
759 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
761 handle = rte_fbk_hash_create(&invalid_params_7);
762 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
764 handle = rte_fbk_hash_create(&invalid_params_8);
765 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
767 handle = rte_fbk_hash_create(&invalid_params_same_name_1);
768 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
770 tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
771 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
773 printf("ERROR line %d: hashes should have been the same\n", __LINE__);
774 rte_fbk_hash_free(handle);
775 rte_fbk_hash_free(tmp);
779 /* we are not freeing tmp or handle here because we need a hash list
780 * to be not empty for the next test */
782 /* create a hash in non-empty list - good for coverage */
783 tmp = rte_fbk_hash_create(&different_name);
784 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
786 /* free both hashes */
787 rte_fbk_hash_free(handle);
788 rte_fbk_hash_free(tmp);
790 /* Create empty jhash hash. */
791 handle = rte_fbk_hash_create(¶ms_jhash);
792 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
795 rte_fbk_hash_free(handle);
797 /* Create empty jhash hash. */
798 handle = rte_fbk_hash_create(¶ms_nohash);
799 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
802 rte_fbk_hash_free(handle);
804 /* Create empty hash. */
805 handle = rte_fbk_hash_create(¶ms);
806 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
808 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
809 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
810 "load factor right after creation is not zero but it should be");
812 for (i = 0; i < 5; i++) {
813 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
814 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
817 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
818 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
819 "load factor now is not as expected");
820 /* Find value of added keys. */
821 for (i = 0; i < 5; i++) {
822 status = rte_fbk_hash_lookup(handle, keys[i]);
823 RETURN_IF_ERROR_FBK(status != vals[i],
824 "fbk hash lookup failed");
827 /* Change value of added keys. */
828 for (i = 0; i < 5; i++) {
829 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
830 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
833 /* Find new values. */
834 for (i = 0; i < 5; i++) {
835 status = rte_fbk_hash_lookup(handle, keys[i]);
836 RETURN_IF_ERROR_FBK(status != vals[4-i],
837 "fbk hash lookup failed");
840 /* Delete keys individually. */
841 for (i = 0; i < 5; i++) {
842 status = rte_fbk_hash_delete_key(handle, keys[i]);
843 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
846 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
847 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
848 "load factor right after deletion is not zero but it should be");
849 /* Lookup should now fail. */
850 for (i = 0; i < 5; i++) {
851 status = rte_fbk_hash_lookup(handle, keys[i]);
852 RETURN_IF_ERROR_FBK(status == 0,
853 "fbk hash lookup should have failed");
856 /* Add keys again. */
857 for (i = 0; i < 5; i++) {
858 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
859 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
862 /* Make sure they were added. */
863 for (i = 0; i < 5; i++) {
864 status = rte_fbk_hash_lookup(handle, keys[i]);
865 RETURN_IF_ERROR_FBK(status != vals[i],
866 "fbk hash lookup failed");
869 /* Clear all entries. */
870 rte_fbk_hash_clear_all(handle);
872 /* Lookup should fail. */
873 for (i = 0; i < 5; i++) {
874 status = rte_fbk_hash_lookup(handle, keys[i]);
875 RETURN_IF_ERROR_FBK(status == 0,
876 "fbk hash lookup should have failed");
881 /* fill up the hash_table */
882 for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
883 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
885 /* Find non-existent key in a full hashtable */
886 status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
887 RETURN_IF_ERROR_FBK(status != -ENOENT,
888 "fbk hash lookup succeeded");
890 /* Delete non-existent key in a full hashtable */
891 status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
892 RETURN_IF_ERROR_FBK(status != -ENOENT,
893 "fbk hash delete succeeded");
895 /* Delete one key from a full hashtable */
896 status = rte_fbk_hash_delete_key(handle, 1);
897 RETURN_IF_ERROR_FBK(status != 0,
898 "fbk hash delete failed");
900 /* Clear all entries. */
901 rte_fbk_hash_clear_all(handle);
904 rte_fbk_hash_free(handle);
906 /* Cover the NULL case. */
907 rte_fbk_hash_free(0);
913 * Sequence of operations for find existing fbk hash table
916 * - find existing table: hit
917 * - find non-existing table: miss
920 static int test_fbk_hash_find_existing(void)
922 struct rte_fbk_hash_params params = {
923 .name = "fbk_hash_find_existing",
924 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
925 .entries_per_bucket = 4,
928 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
930 /* Create hash table. */
931 handle = rte_fbk_hash_create(¶ms);
932 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
934 /* Try to find existing fbk hash table */
935 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
936 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
938 /* Try to find non-existing fbk hash table */
939 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
940 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
943 rte_fbk_hash_free(handle);
949 * Do tests for hash creation with bad parameters.
951 static int test_hash_creation_with_bad_parameters(void)
953 struct rte_hash *handle;
954 struct rte_hash_parameters params;
956 handle = rte_hash_create(NULL);
957 if (handle != NULL) {
958 rte_hash_free(handle);
959 printf("Impossible creating hash sucessfully without any parameter\n");
963 memcpy(¶ms, &ut_params, sizeof(params));
964 params.name = "creation_with_bad_parameters_0";
965 params.entries = RTE_HASH_ENTRIES_MAX + 1;
966 handle = rte_hash_create(¶ms);
967 if (handle != NULL) {
968 rte_hash_free(handle);
969 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
973 memcpy(¶ms, &ut_params, sizeof(params));
974 params.name = "creation_with_bad_parameters_1";
975 params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1;
976 handle = rte_hash_create(¶ms);
977 if (handle != NULL) {
978 rte_hash_free(handle);
979 printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n");
983 memcpy(¶ms, &ut_params, sizeof(params));
984 params.name = "creation_with_bad_parameters_2";
985 params.entries = params.bucket_entries - 1;
986 handle = rte_hash_create(¶ms);
987 if (handle != NULL) {
988 rte_hash_free(handle);
989 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
993 memcpy(¶ms, &ut_params, sizeof(params));
994 params.name = "creation_with_bad_parameters_3";
995 params.entries = params.entries - 1;
996 handle = rte_hash_create(¶ms);
997 if (handle != NULL) {
998 rte_hash_free(handle);
999 printf("Impossible creating hash sucessfully if entries in parameter is not power of 2\n");
1003 memcpy(¶ms, &ut_params, sizeof(params));
1004 params.name = "creation_with_bad_parameters_4";
1005 params.bucket_entries = params.bucket_entries - 1;
1006 handle = rte_hash_create(¶ms);
1007 if (handle != NULL) {
1008 rte_hash_free(handle);
1009 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
1013 memcpy(¶ms, &ut_params, sizeof(params));
1014 params.name = "creation_with_bad_parameters_5";
1016 handle = rte_hash_create(¶ms);
1017 if (handle != NULL) {
1018 rte_hash_free(handle);
1019 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1023 memcpy(¶ms, &ut_params, sizeof(params));
1024 params.name = "creation_with_bad_parameters_6";
1025 params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
1026 handle = rte_hash_create(¶ms);
1027 if (handle != NULL) {
1028 rte_hash_free(handle);
1029 printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n");
1033 memcpy(¶ms, &ut_params, sizeof(params));
1034 params.name = "creation_with_bad_parameters_7";
1035 params.socket_id = RTE_MAX_NUMA_NODES + 1;
1036 handle = rte_hash_create(¶ms);
1037 if (handle != NULL) {
1038 rte_hash_free(handle);
1039 printf("Impossible creating hash sucessfully with invalid socket\n");
1043 rte_hash_free(handle);
1049 * Do tests for hash creation with parameters that look incorrect
1050 * but are actually valid.
1053 test_hash_creation_with_good_parameters(void)
1055 struct rte_hash *handle, *tmp;
1056 struct rte_hash_parameters params;
1058 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1059 memcpy(¶ms, &ut_params, sizeof(params));
1060 params.name = "same_name";
1061 params.hash_func = NULL;
1062 handle = rte_hash_create(¶ms);
1063 if (handle == NULL) {
1064 printf("Creating hash with null hash_func failed\n");
1067 if (handle->hash_func == NULL) {
1068 printf("Hash function should have been DEFAULT_HASH_FUNC\n");
1072 /* this test is trying to create a hash with the same name as previous one.
1073 * this should return a pointer to the hash we previously created.
1074 * the previous hash isn't freed exactly for the purpose of it being in
1077 memcpy(¶ms, &ut_params, sizeof(params));
1078 params.name = "same_name";
1079 tmp = rte_hash_create(¶ms);
1081 /* check if the returned handle is actually equal to the previous hash */
1082 if (handle != tmp) {
1083 rte_hash_free(handle);
1085 printf("Creating hash with existing name was successful\n");
1089 /* try creating hash when there already are hashes in the list.
1090 * the previous hash is not freed to have a non-empty hash list.
1091 * the other hash that's in the list is still pointed to by "handle" var.
1093 memcpy(¶ms, &ut_params, sizeof(params));
1094 params.name = "different_name";
1095 tmp = rte_hash_create(¶ms);
1097 rte_hash_free(handle);
1098 printf("Creating hash with valid parameters failed\n");
1103 rte_hash_free(handle);
1108 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1109 0x04, 0x05, 0x06, 0x07,
1110 0x08, 0x09, 0x0a, 0x0b,
1111 0x0c, 0x0d, 0x0e, 0x0f};
1112 static struct rte_hash_parameters hash_params_ex = {
1115 .bucket_entries = 4,
1118 .hash_func_init_val = 0,
1123 * add/delete key with jhash2
1126 test_hash_add_delete_jhash2(void)
1129 struct rte_hash *handle;
1132 hash_params_ex.name = "hash_test_jhash2";
1133 hash_params_ex.key_len = 4;
1134 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1136 handle = rte_hash_create(&hash_params_ex);
1137 if (handle == NULL) {
1138 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1141 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1143 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1147 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1148 if (pos2 < 0 || pos1 != pos2) {
1149 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1156 rte_hash_free(handle);
1162 * add/delete (2) key with jhash2
1165 test_hash_add_delete_2_jhash2(void)
1168 struct rte_hash *handle;
1171 hash_params_ex.name = "hash_test_2_jhash2";
1172 hash_params_ex.key_len = 8;
1173 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1175 handle = rte_hash_create(&hash_params_ex);
1179 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1183 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1184 if (pos2 < 0 || pos1 != pos2)
1191 rte_hash_free(handle);
1197 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1199 const uint32_t *k = key;
1201 RTE_SET_USED(length);
1203 return rte_jhash_1word(k[0], initval);
1207 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1209 const uint32_t *k = key;
1211 RTE_SET_USED(length);
1213 return rte_jhash_2words(k[0], k[1], initval);
1217 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1219 const uint32_t *k = key;
1221 RTE_SET_USED(length);
1223 return rte_jhash_3words(k[0], k[1], k[2], initval);
1227 * add/delete key with jhash 1word
1230 test_hash_add_delete_jhash_1word(void)
1233 struct rte_hash *handle;
1236 hash_params_ex.name = "hash_test_jhash_1word";
1237 hash_params_ex.key_len = 4;
1238 hash_params_ex.hash_func = test_hash_jhash_1word;
1240 handle = rte_hash_create(&hash_params_ex);
1242 goto fail_jhash_1word;
1244 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1246 goto fail_jhash_1word;
1248 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1249 if (pos2 < 0 || pos1 != pos2)
1250 goto fail_jhash_1word;
1256 rte_hash_free(handle);
1262 * add/delete key with jhash 2word
1265 test_hash_add_delete_jhash_2word(void)
1268 struct rte_hash *handle;
1271 hash_params_ex.name = "hash_test_jhash_2word";
1272 hash_params_ex.key_len = 8;
1273 hash_params_ex.hash_func = test_hash_jhash_2word;
1275 handle = rte_hash_create(&hash_params_ex);
1277 goto fail_jhash_2word;
1279 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1281 goto fail_jhash_2word;
1283 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1284 if (pos2 < 0 || pos1 != pos2)
1285 goto fail_jhash_2word;
1291 rte_hash_free(handle);
1297 * add/delete key with jhash 3word
1300 test_hash_add_delete_jhash_3word(void)
1303 struct rte_hash *handle;
1306 hash_params_ex.name = "hash_test_jhash_3word";
1307 hash_params_ex.key_len = 12;
1308 hash_params_ex.hash_func = test_hash_jhash_3word;
1310 handle = rte_hash_create(&hash_params_ex);
1312 goto fail_jhash_3word;
1314 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1316 goto fail_jhash_3word;
1318 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1319 if (pos2 < 0 || pos1 != pos2)
1320 goto fail_jhash_3word;
1326 rte_hash_free(handle);
1332 * Do all unit and performance tests.
1336 if (test_add_delete() < 0)
1338 if (test_hash_add_delete_jhash2() < 0)
1340 if (test_hash_add_delete_2_jhash2() < 0)
1342 if (test_hash_add_delete_jhash_1word() < 0)
1344 if (test_hash_add_delete_jhash_2word() < 0)
1346 if (test_hash_add_delete_jhash_3word() < 0)
1348 if (test_hash_find_existing() < 0)
1350 if (test_add_update_delete() < 0)
1352 if (test_five_keys() < 0)
1354 if (test_full_bucket() < 0)
1357 if (test_fbk_hash_find_existing() < 0)
1359 if (fbk_hash_unit_test() < 0)
1361 if (test_hash_creation_with_bad_parameters() < 0)
1363 if (test_hash_creation_with_good_parameters() < 0)
1366 run_hash_func_tests();
1370 #else /* RTE_LIBRTE_HASH */
1375 printf("The Hash library is not included in this build\n");
1379 #endif /* RTE_LIBRTE_HASH */