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>
56 #include <rte_fbk_hash.h>
57 #include <rte_jhash.h>
58 #include <rte_hash_crc.h>
60 /*******************************************************************************
61 * Hash function performance test configuration section. Each performance test
62 * will be performed HASHTEST_ITERATIONS times.
64 * The five arrays below control what tests are performed. Every combination
65 * from the array entries is tested.
67 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
68 static uint32_t hashtest_initvals[] = {0};
69 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
70 /******************************************************************************/
71 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
74 * Check condition and return an error if true. Assumes that "handle" is the
75 * name of the hash structure pointer to be freed.
77 #define RETURN_IF_ERROR(cond, str, ...) do { \
79 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
80 if (handle) rte_hash_free(handle); \
85 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
87 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
88 if (handle) rte_fbk_hash_free(handle); \
93 /* 5-tuple key type */
100 } __attribute__((packed));
103 * Hash function that always returns the same value, to easily test what
104 * happens when a bucket is full.
106 static uint32_t pseudo_hash(__attribute__((unused)) const void *keys,
107 __attribute__((unused)) uint32_t key_len,
108 __attribute__((unused)) uint32_t init_val)
114 * Print out result of unit test hash operation.
116 #if defined(UNIT_TEST_HASH_VERBOSE)
117 static void print_key_info(const char *msg, const struct flow_key *key,
120 uint8_t *p = (uint8_t *)key;
123 printf("%s key:0x", msg);
124 for (i = 0; i < sizeof(struct flow_key); i++) {
125 printf("%02X", p[i]);
127 printf(" @ pos %d\n", pos);
130 static void print_key_info(__attribute__((unused)) const char *msg,
131 __attribute__((unused)) const struct flow_key *key,
132 __attribute__((unused)) int32_t pos)
137 /* Keys used by unit test functions */
138 static struct flow_key keys[5] = { {
139 .ip_src = IPv4(0x03, 0x02, 0x01, 0x00),
140 .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04),
145 .ip_src = IPv4(0x13, 0x12, 0x11, 0x10),
146 .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14),
151 .ip_src = IPv4(0x23, 0x22, 0x21, 0x20),
152 .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24),
157 .ip_src = IPv4(0x33, 0x32, 0x31, 0x30),
158 .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34),
163 .ip_src = IPv4(0x43, 0x42, 0x41, 0x40),
164 .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44),
170 /* Parameters used for hash table in unit test functions. Name set later. */
171 static struct rte_hash_parameters ut_params = {
174 .key_len = sizeof(struct flow_key), /* 13 */
175 .hash_func = rte_jhash,
176 .hash_func_init_val = 0,
181 * Test a hash function.
183 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
186 static uint8_t key[RTE_HASH_KEY_LENGTH_MAX];
190 for (i = 0; i < key_len; i++)
191 key[i] = (uint8_t) rte_rand();
193 /* just to be on the safe side */
197 f(key, key_len, init_val);
201 * Test all hash functions.
203 static void run_hash_func_tests(void)
208 i < sizeof(hashtest_funcs) / sizeof(rte_hash_function);
211 j < sizeof(hashtest_initvals) / sizeof(uint32_t);
214 k < sizeof(hashtest_key_lens) / sizeof(uint32_t);
216 run_hash_func_test(hashtest_funcs[i],
217 hashtest_initvals[j],
218 hashtest_key_lens[k]);
225 * Basic sequence of operations for a single key:
231 static int test_add_delete(void)
233 struct rte_hash *handle;
234 /* test with standard add/lookup/delete functions */
235 int pos0, expectedPos0;
237 ut_params.name = "test1";
238 handle = rte_hash_create(&ut_params);
239 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
241 pos0 = rte_hash_add_key(handle, &keys[0]);
242 print_key_info("Add", &keys[0], pos0);
243 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
246 pos0 = rte_hash_lookup(handle, &keys[0]);
247 print_key_info("Lkp", &keys[0], pos0);
248 RETURN_IF_ERROR(pos0 != expectedPos0,
249 "failed to find key (pos0=%d)", pos0);
251 pos0 = rte_hash_del_key(handle, &keys[0]);
252 print_key_info("Del", &keys[0], pos0);
253 RETURN_IF_ERROR(pos0 != expectedPos0,
254 "failed to delete 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 != -ENOENT,
259 "fail: found key after deleting! (pos0=%d)", pos0);
261 rte_hash_free(handle);
263 /* repeat test with precomputed hash functions */
264 hash_sig_t hash_value;
265 int pos1, expectedPos1;
267 handle = rte_hash_create(&ut_params);
268 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
270 hash_value = rte_hash_hash(handle, &keys[0]);
271 pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
272 print_key_info("Add", &keys[0], pos1);
273 RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
276 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
277 print_key_info("Lkp", &keys[0], pos1);
278 RETURN_IF_ERROR(pos1 != expectedPos1,
279 "failed to find key (pos1=%d)", pos1);
281 pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
282 print_key_info("Del", &keys[0], pos1);
283 RETURN_IF_ERROR(pos1 != expectedPos1,
284 "failed to delete 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 != -ENOENT,
289 "fail: found key after deleting! (pos1=%d)", pos1);
291 rte_hash_free(handle);
297 * Sequence of operations for a single key:
302 * - lookup: hit (updated data)
307 static int test_add_update_delete(void)
309 struct rte_hash *handle;
310 int pos0, expectedPos0;
312 ut_params.name = "test2";
313 handle = rte_hash_create(&ut_params);
314 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
316 pos0 = rte_hash_del_key(handle, &keys[0]);
317 print_key_info("Del", &keys[0], pos0);
318 RETURN_IF_ERROR(pos0 != -ENOENT,
319 "fail: found non-existent key (pos0=%d)", pos0);
321 pos0 = rte_hash_add_key(handle, &keys[0]);
322 print_key_info("Add", &keys[0], pos0);
323 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
326 pos0 = rte_hash_lookup(handle, &keys[0]);
327 print_key_info("Lkp", &keys[0], pos0);
328 RETURN_IF_ERROR(pos0 != expectedPos0,
329 "failed to find 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 != expectedPos0,
334 "failed to re-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_del_key(handle, &keys[0]);
342 print_key_info("Del", &keys[0], pos0);
343 RETURN_IF_ERROR(pos0 != expectedPos0,
344 "failed to delete key (pos0=%d)", pos0);
346 pos0 = rte_hash_del_key(handle, &keys[0]);
347 print_key_info("Del", &keys[0], pos0);
348 RETURN_IF_ERROR(pos0 != -ENOENT,
349 "fail: deleted already deleted key (pos0=%d)", pos0);
351 pos0 = rte_hash_lookup(handle, &keys[0]);
352 print_key_info("Lkp", &keys[0], pos0);
353 RETURN_IF_ERROR(pos0 != -ENOENT,
354 "fail: found key after deleting! (pos0=%d)", pos0);
356 rte_hash_free(handle);
361 * Sequence of operations for find existing hash table
364 * - find existing table: hit
365 * - find non-existing table: miss
368 static int test_hash_find_existing(void)
370 struct rte_hash *handle = NULL, *result = NULL;
372 /* Create hash table. */
373 ut_params.name = "hash_find_existing";
374 handle = rte_hash_create(&ut_params);
375 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
377 /* Try to find existing hash table */
378 result = rte_hash_find_existing("hash_find_existing");
379 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
381 /* Try to find non-existing hash table */
382 result = rte_hash_find_existing("hash_find_non_existing");
383 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
386 rte_hash_free(handle);
392 * Sequence of operations for 5 keys
395 * - add keys (update)
396 * - lookup keys: hit (updated data)
397 * - delete keys : hit
398 * - lookup keys: miss
400 static int test_five_keys(void)
402 struct rte_hash *handle;
403 const void *key_array[5] = {0};
409 ut_params.name = "test3";
410 handle = rte_hash_create(&ut_params);
411 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
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] < 0,
418 "failed to add key (pos[%u]=%d)", i, pos[i]);
419 expected_pos[i] = pos[i];
423 for(i = 0; i < 5; i++)
424 key_array[i] = &keys[i];
426 ret = rte_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos);
428 for(i = 0; i < 5; i++) {
429 print_key_info("Lkp", key_array[i], pos[i]);
430 RETURN_IF_ERROR(pos[i] != expected_pos[i],
431 "failed to find key (pos[%u]=%d)", i, pos[i]);
435 for (i = 0; i < 5; i++) {
436 pos[i] = rte_hash_add_key(handle, &keys[i]);
437 print_key_info("Add", &keys[i], pos[i]);
438 RETURN_IF_ERROR(pos[i] != expected_pos[i],
439 "failed to add key (pos[%u]=%d)", i, pos[i]);
443 for (i = 0; i < 5; i++) {
444 pos[i] = rte_hash_lookup(handle, &keys[i]);
445 print_key_info("Lkp", &keys[i], pos[i]);
446 RETURN_IF_ERROR(pos[i] != expected_pos[i],
447 "failed to find key (pos[%u]=%d)", i, pos[i]);
451 for (i = 0; i < 5; i++) {
452 pos[i] = rte_hash_del_key(handle, &keys[i]);
453 print_key_info("Del", &keys[i], pos[i]);
454 RETURN_IF_ERROR(pos[i] != expected_pos[i],
455 "failed to delete key (pos[%u]=%d)", i, pos[i]);
459 for (i = 0; i < 5; i++) {
460 pos[i] = rte_hash_lookup(handle, &keys[i]);
461 print_key_info("Lkp", &keys[i], pos[i]);
462 RETURN_IF_ERROR(pos[i] != -ENOENT,
463 "failed to find key (pos[%u]=%d)", i, pos[i]);
466 rte_hash_free(handle);
472 * Add keys to the same bucket until bucket full.
473 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
474 * first 4 successful, 5th unsuccessful
475 * - lookup the 5 keys: 4 hits, 1 miss
476 * - add the 5 keys again: 4 OK, one error as bucket is full
477 * - lookup the 5 keys: 4 hits (updated data), 1 miss
478 * - delete the 5 keys: 5 OK (even if the 5th is not in the table)
479 * - lookup the 5 keys: 5 misses
480 * - add the 5th key: OK
481 * - lookup the 5th key: hit
483 static int test_full_bucket(void)
485 struct rte_hash_parameters params_pseudo_hash = {
489 .key_len = sizeof(struct flow_key), /* 13 */
490 .hash_func = pseudo_hash,
491 .hash_func_init_val = 0,
494 struct rte_hash *handle;
499 handle = rte_hash_create(¶ms_pseudo_hash);
500 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
503 for (i = 0; i < 4; i++) {
504 pos[i] = rte_hash_add_key(handle, &keys[i]);
505 print_key_info("Add", &keys[i], pos[i]);
506 RETURN_IF_ERROR(pos[i] < 0,
507 "failed to add key (pos[%u]=%d)", i, pos[i]);
508 expected_pos[i] = pos[i];
510 /* This shouldn't work because the bucket is full */
511 pos[4] = rte_hash_add_key(handle, &keys[4]);
512 print_key_info("Add", &keys[4], pos[4]);
513 RETURN_IF_ERROR(pos[4] != -ENOSPC,
514 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
517 for (i = 0; i < 4; i++) {
518 pos[i] = rte_hash_lookup(handle, &keys[i]);
519 print_key_info("Lkp", &keys[i], pos[i]);
520 RETURN_IF_ERROR(pos[i] != expected_pos[i],
521 "failed to find key (pos[%u]=%d)", i, pos[i]);
523 pos[4] = rte_hash_lookup(handle, &keys[4]);
524 print_key_info("Lkp", &keys[4], pos[4]);
525 RETURN_IF_ERROR(pos[4] != -ENOENT,
526 "fail: found non-existent key (pos[4]=%d)", pos[4]);
529 for (i = 0; i < 4; i++) {
530 pos[i] = rte_hash_add_key(handle, &keys[i]);
531 print_key_info("Add", &keys[i], pos[i]);
532 RETURN_IF_ERROR(pos[i] != expected_pos[i],
533 "failed to add key (pos[%u]=%d)", i, pos[i]);
535 pos[4] = rte_hash_add_key(handle, &keys[4]);
536 print_key_info("Add", &keys[4], pos[4]);
537 RETURN_IF_ERROR(pos[4] != -ENOSPC,
538 "fail: added key to full bucket (pos[4]=%d)", pos[4]);
541 for (i = 0; i < 4; i++) {
542 pos[i] = rte_hash_lookup(handle, &keys[i]);
543 print_key_info("Lkp", &keys[i], pos[i]);
544 RETURN_IF_ERROR(pos[i] != expected_pos[i],
545 "failed to find key (pos[%u]=%d)", i, pos[i]);
547 pos[4] = rte_hash_lookup(handle, &keys[4]);
548 print_key_info("Lkp", &keys[4], pos[4]);
549 RETURN_IF_ERROR(pos[4] != -ENOENT,
550 "fail: found non-existent key (pos[4]=%d)", pos[4]);
552 /* Delete 1 key, check other keys are still found */
553 pos[1] = rte_hash_del_key(handle, &keys[1]);
554 print_key_info("Del", &keys[1], pos[1]);
555 RETURN_IF_ERROR(pos[1] != expected_pos[1],
556 "failed to delete key (pos[1]=%d)", pos[1]);
557 pos[3] = rte_hash_lookup(handle, &keys[3]);
558 print_key_info("Lkp", &keys[3], pos[3]);
559 RETURN_IF_ERROR(pos[3] != expected_pos[3],
560 "failed lookup after deleting key from same bucket "
561 "(pos[3]=%d)", pos[3]);
563 /* Go back to previous state */
564 pos[1] = rte_hash_add_key(handle, &keys[1]);
565 print_key_info("Add", &keys[1], pos[1]);
566 expected_pos[1] = pos[1];
567 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
570 for (i = 0; i < 4; i++) {
571 pos[i] = rte_hash_del_key(handle, &keys[i]);
572 print_key_info("Del", &keys[i], pos[i]);
573 RETURN_IF_ERROR(pos[i] != expected_pos[i],
574 "failed to delete key (pos[%u]=%d)", i, pos[i]);
576 pos[4] = rte_hash_del_key(handle, &keys[4]);
577 print_key_info("Del", &keys[4], pos[4]);
578 RETURN_IF_ERROR(pos[4] != -ENOENT,
579 "fail: deleted non-existent key (pos[4]=%d)", pos[4]);
582 for (i = 0; i < 4; i++) {
583 pos[i] = rte_hash_lookup(handle, &keys[i]);
584 print_key_info("Lkp", &keys[i], pos[i]);
585 RETURN_IF_ERROR(pos[i] != -ENOENT,
586 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
589 /* Add and lookup the 5th key */
590 pos[4] = rte_hash_add_key(handle, &keys[4]);
591 print_key_info("Add", &keys[4], pos[4]);
592 RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]);
593 expected_pos[4] = pos[4];
594 pos[4] = rte_hash_lookup(handle, &keys[4]);
595 print_key_info("Lkp", &keys[4], pos[4]);
596 RETURN_IF_ERROR(pos[4] != expected_pos[4],
597 "failed to find key (pos[4]=%d)", pos[4]);
599 rte_hash_free(handle);
601 /* Cover the NULL case. */
606 /******************************************************************************/
608 fbk_hash_unit_test(void)
610 struct rte_fbk_hash_params params = {
611 .name = "fbk_hash_test",
612 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
613 .entries_per_bucket = 4,
617 struct rte_fbk_hash_params invalid_params_1 = {
619 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
620 .entries_per_bucket = 4,
624 struct rte_fbk_hash_params invalid_params_2 = {
627 .entries_per_bucket = 3, /* Not power of 2 */
631 struct rte_fbk_hash_params invalid_params_3 = {
633 .entries = 0, /* Entries is 0 */
634 .entries_per_bucket = 4,
638 struct rte_fbk_hash_params invalid_params_4 = {
640 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
641 .entries_per_bucket = 0, /* Entries per bucket is 0 */
645 struct rte_fbk_hash_params invalid_params_5 = {
648 .entries_per_bucket = 8, /* Entries per bucket > entries */
652 struct rte_fbk_hash_params invalid_params_6 = {
654 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
655 .entries_per_bucket = 4,
659 struct rte_fbk_hash_params invalid_params_7 = {
661 .entries = RTE_FBK_HASH_ENTRIES_MAX,
662 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */
666 struct rte_fbk_hash_params invalid_params_8 = {
668 .entries = RTE_FBK_HASH_ENTRIES_MAX,
669 .entries_per_bucket = 4,
670 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
673 /* try to create two hashes with identical names
674 * in this case, trying to create a second one will not
675 * fail but will simply return pointer to the existing
676 * hash with that name. sort of like a "find hash by name" :-)
678 struct rte_fbk_hash_params invalid_params_same_name_1 = {
679 .name = "same_name", /* hash with identical name */
681 .entries_per_bucket = 2,
685 /* trying to create this hash should return a pointer to an existing hash */
686 struct rte_fbk_hash_params invalid_params_same_name_2 = {
687 .name = "same_name", /* hash with identical name */
688 .entries = RTE_FBK_HASH_ENTRIES_MAX,
689 .entries_per_bucket = 4,
693 /* this is a sanity check for "same name" test
694 * creating this hash will check if we are actually able to create
695 * multiple hashes with different names (instead of having just one).
697 struct rte_fbk_hash_params different_name = {
698 .name = "different_name", /* different name */
699 .entries = RTE_FBK_HASH_ENTRIES_MAX,
700 .entries_per_bucket = 4,
704 struct rte_fbk_hash_params params_jhash = {
706 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
707 .entries_per_bucket = 4,
709 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
710 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
713 struct rte_fbk_hash_params params_nohash = {
714 .name = "valid nohash",
715 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
716 .entries_per_bucket = 4,
718 .hash_func = NULL, /* Tests for null hash_func */
719 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
722 struct rte_fbk_hash_table *handle, *tmp;
724 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
725 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
730 /* Try creating hashes with invalid parameters */
731 printf("# Testing hash creation with invalid parameters "
732 "- expert error msgs\n");
733 handle = rte_fbk_hash_create(&invalid_params_1);
734 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
736 handle = rte_fbk_hash_create(&invalid_params_2);
737 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
739 handle = rte_fbk_hash_create(&invalid_params_3);
740 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
742 handle = rte_fbk_hash_create(&invalid_params_4);
743 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
745 handle = rte_fbk_hash_create(&invalid_params_5);
746 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
748 handle = rte_fbk_hash_create(&invalid_params_6);
749 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
751 handle = rte_fbk_hash_create(&invalid_params_7);
752 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
754 handle = rte_fbk_hash_create(&invalid_params_8);
755 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
757 handle = rte_fbk_hash_create(&invalid_params_same_name_1);
758 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
760 tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
761 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
763 printf("ERROR line %d: hashes should have been the same\n", __LINE__);
764 rte_fbk_hash_free(handle);
765 rte_fbk_hash_free(tmp);
769 /* we are not freeing tmp or handle here because we need a hash list
770 * to be not empty for the next test */
772 /* create a hash in non-empty list - good for coverage */
773 tmp = rte_fbk_hash_create(&different_name);
774 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
776 /* free both hashes */
777 rte_fbk_hash_free(handle);
778 rte_fbk_hash_free(tmp);
780 /* Create empty jhash hash. */
781 handle = rte_fbk_hash_create(¶ms_jhash);
782 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
785 rte_fbk_hash_free(handle);
787 /* Create empty jhash hash. */
788 handle = rte_fbk_hash_create(¶ms_nohash);
789 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
792 rte_fbk_hash_free(handle);
794 /* Create empty hash. */
795 handle = rte_fbk_hash_create(¶ms);
796 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
798 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
799 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
800 "load factor right after creation is not zero but it should be");
802 for (i = 0; i < 5; i++) {
803 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
804 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
807 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
808 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
809 "load factor now is not as expected");
810 /* Find value of added keys. */
811 for (i = 0; i < 5; i++) {
812 status = rte_fbk_hash_lookup(handle, keys[i]);
813 RETURN_IF_ERROR_FBK(status != vals[i],
814 "fbk hash lookup failed");
817 /* Change value of added keys. */
818 for (i = 0; i < 5; i++) {
819 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
820 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
823 /* Find new values. */
824 for (i = 0; i < 5; i++) {
825 status = rte_fbk_hash_lookup(handle, keys[i]);
826 RETURN_IF_ERROR_FBK(status != vals[4-i],
827 "fbk hash lookup failed");
830 /* Delete keys individually. */
831 for (i = 0; i < 5; i++) {
832 status = rte_fbk_hash_delete_key(handle, keys[i]);
833 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
836 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
837 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
838 "load factor right after deletion is not zero but it should be");
839 /* Lookup should now 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");
846 /* Add keys again. */
847 for (i = 0; i < 5; i++) {
848 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
849 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
852 /* Make sure they were added. */
853 for (i = 0; i < 5; i++) {
854 status = rte_fbk_hash_lookup(handle, keys[i]);
855 RETURN_IF_ERROR_FBK(status != vals[i],
856 "fbk hash lookup failed");
859 /* Clear all entries. */
860 rte_fbk_hash_clear_all(handle);
862 /* Lookup should fail. */
863 for (i = 0; i < 5; i++) {
864 status = rte_fbk_hash_lookup(handle, keys[i]);
865 RETURN_IF_ERROR_FBK(status == 0,
866 "fbk hash lookup should have failed");
871 /* fill up the hash_table */
872 for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
873 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
875 /* Find non-existent key in a full hashtable */
876 status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
877 RETURN_IF_ERROR_FBK(status != -ENOENT,
878 "fbk hash lookup succeeded");
880 /* Delete non-existent key in a full hashtable */
881 status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
882 RETURN_IF_ERROR_FBK(status != -ENOENT,
883 "fbk hash delete succeeded");
885 /* Delete one key from a full hashtable */
886 status = rte_fbk_hash_delete_key(handle, 1);
887 RETURN_IF_ERROR_FBK(status != 0,
888 "fbk hash delete failed");
890 /* Clear all entries. */
891 rte_fbk_hash_clear_all(handle);
894 rte_fbk_hash_free(handle);
896 /* Cover the NULL case. */
897 rte_fbk_hash_free(0);
903 * Sequence of operations for find existing fbk hash table
906 * - find existing table: hit
907 * - find non-existing table: miss
910 static int test_fbk_hash_find_existing(void)
912 struct rte_fbk_hash_params params = {
913 .name = "fbk_hash_find_existing",
914 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
915 .entries_per_bucket = 4,
918 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
920 /* Create hash table. */
921 handle = rte_fbk_hash_create(¶ms);
922 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
924 /* Try to find existing fbk hash table */
925 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
926 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
928 /* Try to find non-existing fbk hash table */
929 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
930 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
933 rte_fbk_hash_free(handle);
939 * Do tests for hash creation with bad parameters.
941 static int test_hash_creation_with_bad_parameters(void)
943 struct rte_hash *handle;
944 struct rte_hash_parameters params;
946 handle = rte_hash_create(NULL);
947 if (handle != NULL) {
948 rte_hash_free(handle);
949 printf("Impossible creating hash sucessfully without any parameter\n");
953 memcpy(¶ms, &ut_params, sizeof(params));
954 params.name = "creation_with_bad_parameters_0";
955 params.entries = RTE_HASH_ENTRIES_MAX + 1;
956 handle = rte_hash_create(¶ms);
957 if (handle != NULL) {
958 rte_hash_free(handle);
959 printf("Impossible creating hash sucessfully with entries in parameter exceeded\n");
963 memcpy(¶ms, &ut_params, sizeof(params));
964 params.name = "creation_with_bad_parameters_1";
965 params.bucket_entries = RTE_HASH_BUCKET_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 bucket_entries in parameter exceeded\n");
973 memcpy(¶ms, &ut_params, sizeof(params));
974 params.name = "creation_with_bad_parameters_2";
975 params.entries = params.bucket_entries - 1;
976 handle = rte_hash_create(¶ms);
977 if (handle != NULL) {
978 rte_hash_free(handle);
979 printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n");
983 memcpy(¶ms, &ut_params, sizeof(params));
984 params.name = "creation_with_bad_parameters_3";
985 params.entries = params.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 in parameter is not power of 2\n");
993 memcpy(¶ms, &ut_params, sizeof(params));
994 params.name = "creation_with_bad_parameters_4";
995 params.bucket_entries = params.bucket_entries - 1;
996 handle = rte_hash_create(¶ms);
997 if (handle != NULL) {
998 rte_hash_free(handle);
999 printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n");
1003 memcpy(¶ms, &ut_params, sizeof(params));
1004 params.name = "creation_with_bad_parameters_5";
1006 handle = rte_hash_create(¶ms);
1007 if (handle != NULL) {
1008 rte_hash_free(handle);
1009 printf("Impossible creating hash sucessfully if key_len in parameter is zero\n");
1013 memcpy(¶ms, &ut_params, sizeof(params));
1014 params.name = "creation_with_bad_parameters_6";
1015 params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1;
1016 handle = rte_hash_create(¶ms);
1017 if (handle != NULL) {
1018 rte_hash_free(handle);
1019 printf("Impossible creating hash sucessfully if key_len is greater than the maximum\n");
1023 memcpy(¶ms, &ut_params, sizeof(params));
1024 params.name = "creation_with_bad_parameters_7";
1025 params.socket_id = RTE_MAX_NUMA_NODES + 1;
1026 handle = rte_hash_create(¶ms);
1027 if (handle != NULL) {
1028 rte_hash_free(handle);
1029 printf("Impossible creating hash sucessfully with invalid socket\n");
1033 rte_hash_free(handle);
1039 * Do tests for hash creation with parameters that look incorrect
1040 * but are actually valid.
1043 test_hash_creation_with_good_parameters(void)
1045 struct rte_hash *handle, *tmp;
1046 struct rte_hash_parameters params;
1048 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1049 memcpy(¶ms, &ut_params, sizeof(params));
1050 params.name = "same_name";
1051 params.hash_func = NULL;
1052 handle = rte_hash_create(¶ms);
1053 if (handle == NULL) {
1054 printf("Creating hash with null hash_func failed\n");
1057 if (handle->hash_func == NULL) {
1058 printf("Hash function should have been DEFAULT_HASH_FUNC\n");
1062 /* this test is trying to create a hash with the same name as previous one.
1063 * this should return a pointer to the hash we previously created.
1064 * the previous hash isn't freed exactly for the purpose of it being in
1067 memcpy(¶ms, &ut_params, sizeof(params));
1068 params.name = "same_name";
1069 tmp = rte_hash_create(¶ms);
1071 /* check if the returned handle is actually equal to the previous hash */
1072 if (handle != tmp) {
1073 rte_hash_free(handle);
1075 printf("Creating hash with existing name was successful\n");
1079 /* try creating hash when there already are hashes in the list.
1080 * the previous hash is not freed to have a non-empty hash list.
1081 * the other hash that's in the list is still pointed to by "handle" var.
1083 memcpy(¶ms, &ut_params, sizeof(params));
1084 params.name = "different_name";
1085 tmp = rte_hash_create(¶ms);
1087 rte_hash_free(handle);
1088 printf("Creating hash with valid parameters failed\n");
1093 rte_hash_free(handle);
1098 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1099 0x04, 0x05, 0x06, 0x07,
1100 0x08, 0x09, 0x0a, 0x0b,
1101 0x0c, 0x0d, 0x0e, 0x0f};
1102 static struct rte_hash_parameters hash_params_ex = {
1105 .bucket_entries = 4,
1108 .hash_func_init_val = 0,
1113 * add/delete key with jhash2
1116 test_hash_add_delete_jhash2(void)
1119 struct rte_hash *handle;
1122 hash_params_ex.name = "hash_test_jhash2";
1123 hash_params_ex.key_len = 4;
1124 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1126 handle = rte_hash_create(&hash_params_ex);
1127 if (handle == NULL) {
1128 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1131 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1133 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1137 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1138 if (pos2 < 0 || pos1 != pos2) {
1139 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1146 rte_hash_free(handle);
1152 * add/delete (2) key with jhash2
1155 test_hash_add_delete_2_jhash2(void)
1158 struct rte_hash *handle;
1161 hash_params_ex.name = "hash_test_2_jhash2";
1162 hash_params_ex.key_len = 8;
1163 hash_params_ex.hash_func = (rte_hash_function)rte_jhash2;
1165 handle = rte_hash_create(&hash_params_ex);
1169 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1173 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1174 if (pos2 < 0 || pos1 != pos2)
1181 rte_hash_free(handle);
1187 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1189 const uint32_t *k = key;
1191 RTE_SET_USED(length);
1193 return rte_jhash_1word(k[0], initval);
1197 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1199 const uint32_t *k = key;
1201 RTE_SET_USED(length);
1203 return rte_jhash_2words(k[0], k[1], initval);
1207 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1209 const uint32_t *k = key;
1211 RTE_SET_USED(length);
1213 return rte_jhash_3words(k[0], k[1], k[2], initval);
1217 * add/delete key with jhash 1word
1220 test_hash_add_delete_jhash_1word(void)
1223 struct rte_hash *handle;
1226 hash_params_ex.name = "hash_test_jhash_1word";
1227 hash_params_ex.key_len = 4;
1228 hash_params_ex.hash_func = test_hash_jhash_1word;
1230 handle = rte_hash_create(&hash_params_ex);
1232 goto fail_jhash_1word;
1234 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1236 goto fail_jhash_1word;
1238 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1239 if (pos2 < 0 || pos1 != pos2)
1240 goto fail_jhash_1word;
1246 rte_hash_free(handle);
1252 * add/delete key with jhash 2word
1255 test_hash_add_delete_jhash_2word(void)
1258 struct rte_hash *handle;
1261 hash_params_ex.name = "hash_test_jhash_2word";
1262 hash_params_ex.key_len = 8;
1263 hash_params_ex.hash_func = test_hash_jhash_2word;
1265 handle = rte_hash_create(&hash_params_ex);
1267 goto fail_jhash_2word;
1269 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1271 goto fail_jhash_2word;
1273 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1274 if (pos2 < 0 || pos1 != pos2)
1275 goto fail_jhash_2word;
1281 rte_hash_free(handle);
1287 * add/delete key with jhash 3word
1290 test_hash_add_delete_jhash_3word(void)
1293 struct rte_hash *handle;
1296 hash_params_ex.name = "hash_test_jhash_3word";
1297 hash_params_ex.key_len = 12;
1298 hash_params_ex.hash_func = test_hash_jhash_3word;
1300 handle = rte_hash_create(&hash_params_ex);
1302 goto fail_jhash_3word;
1304 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1306 goto fail_jhash_3word;
1308 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1309 if (pos2 < 0 || pos1 != pos2)
1310 goto fail_jhash_3word;
1316 rte_hash_free(handle);
1322 * Do all unit and performance tests.
1327 if (test_add_delete() < 0)
1329 if (test_hash_add_delete_jhash2() < 0)
1331 if (test_hash_add_delete_2_jhash2() < 0)
1333 if (test_hash_add_delete_jhash_1word() < 0)
1335 if (test_hash_add_delete_jhash_2word() < 0)
1337 if (test_hash_add_delete_jhash_3word() < 0)
1339 if (test_hash_find_existing() < 0)
1341 if (test_add_update_delete() < 0)
1343 if (test_five_keys() < 0)
1345 if (test_full_bucket() < 0)
1348 if (test_fbk_hash_find_existing() < 0)
1350 if (fbk_hash_unit_test() < 0)
1352 if (test_hash_creation_with_bad_parameters() < 0)
1354 if (test_hash_creation_with_good_parameters() < 0)
1357 run_hash_func_tests();
1362 static struct test_command hash_cmd = {
1363 .command = "hash_autotest",
1364 .callback = test_hash,
1366 REGISTER_TEST_COMMAND(hash_cmd);