1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2015 Intel Corporation
11 #include <sys/queue.h>
13 #include <rte_common.h>
14 #include <rte_malloc.h>
15 #include <rte_cycles.h>
16 #include <rte_random.h>
17 #include <rte_memory.h>
20 #include <rte_string_fns.h>
25 #include <rte_fbk_hash.h>
26 #include <rte_jhash.h>
27 #include <rte_hash_crc.h>
29 /*******************************************************************************
30 * Hash function performance test configuration section. Each performance test
31 * will be performed HASHTEST_ITERATIONS times.
33 * The five arrays below control what tests are performed. Every combination
34 * from the array entries is tested.
36 static rte_hash_function hashtest_funcs
[] = {rte_jhash
, rte_hash_crc
};
37 static uint32_t hashtest_initvals
[] = {0};
38 static uint32_t hashtest_key_lens
[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
39 #define MAX_KEYSIZE 64
40 /******************************************************************************/
41 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
44 * Check condition and return an error if true. Assumes that "handle" is the
45 * name of the hash structure pointer to be freed.
47 #define RETURN_IF_ERROR(cond, str, ...) do { \
49 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
50 if (handle) rte_hash_free(handle); \
55 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
57 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
58 if (handle) rte_fbk_hash_free(handle); \
63 /* 5-tuple key type */
72 int hash_logtype_test
;
75 * Hash function that always returns the same value, to easily test what
76 * happens when a bucket is full.
78 static uint32_t pseudo_hash(__rte_unused
const void *keys
,
79 __rte_unused
uint32_t key_len
,
80 __rte_unused
uint32_t init_val
)
85 RTE_INIT(test_hash_init_log
)
87 hash_logtype_test
= rte_log_register("test.hash");
91 * Print out result of unit test hash operation.
93 static void print_key_info(const char *msg
, const struct flow_key
*key
,
96 const uint8_t *p
= (const uint8_t *)key
;
99 rte_log(RTE_LOG_DEBUG
, hash_logtype_test
, "%s key:0x", msg
);
100 for (i
= 0; i
< sizeof(struct flow_key
); i
++)
101 rte_log(RTE_LOG_DEBUG
, hash_logtype_test
, "%02X", p
[i
]);
102 rte_log(RTE_LOG_DEBUG
, hash_logtype_test
, " @ pos %d\n", pos
);
105 /* Keys used by unit test functions */
106 static struct flow_key keys
[5] = { {
107 .ip_src
= RTE_IPV4(0x03, 0x02, 0x01, 0x00),
108 .ip_dst
= RTE_IPV4(0x07, 0x06, 0x05, 0x04),
113 .ip_src
= RTE_IPV4(0x13, 0x12, 0x11, 0x10),
114 .ip_dst
= RTE_IPV4(0x17, 0x16, 0x15, 0x14),
119 .ip_src
= RTE_IPV4(0x23, 0x22, 0x21, 0x20),
120 .ip_dst
= RTE_IPV4(0x27, 0x26, 0x25, 0x24),
125 .ip_src
= RTE_IPV4(0x33, 0x32, 0x31, 0x30),
126 .ip_dst
= RTE_IPV4(0x37, 0x36, 0x35, 0x34),
131 .ip_src
= RTE_IPV4(0x43, 0x42, 0x41, 0x40),
132 .ip_dst
= RTE_IPV4(0x47, 0x46, 0x45, 0x44),
138 /* Parameters used for hash table in unit test functions. Name set later. */
139 static struct rte_hash_parameters ut_params
= {
141 .key_len
= sizeof(struct flow_key
), /* 13 */
142 .hash_func
= rte_jhash
,
143 .hash_func_init_val
= 0,
147 #define CRC32_ITERATIONS (1U << 10)
148 #define CRC32_DWORDS (1U << 6)
150 * Test if all CRC32 implementations yield the same hash value
153 test_crc32_hash_alg_equiv(void)
157 uint64_t data64
[CRC32_DWORDS
];
161 printf("\n# CRC32 implementations equivalence test\n");
162 for (i
= 0; i
< CRC32_ITERATIONS
; i
++) {
163 /* Randomizing data_len of data set */
164 data_len
= (size_t) ((rte_rand() % sizeof(data64
)) + 1);
165 init_val
= (uint32_t) rte_rand();
167 /* Fill the data set */
168 for (j
= 0; j
< CRC32_DWORDS
; j
++)
169 data64
[j
] = rte_rand();
171 /* Calculate software CRC32 */
172 rte_hash_crc_set_alg(CRC32_SW
);
173 hash_val
= rte_hash_crc(data64
, data_len
, init_val
);
175 /* Check against 4-byte-operand sse4.2 CRC32 if available */
176 rte_hash_crc_set_alg(CRC32_SSE42
);
177 if (hash_val
!= rte_hash_crc(data64
, data_len
, init_val
)) {
178 printf("Failed checking CRC32_SW against CRC32_SSE42\n");
182 /* Check against 8-byte-operand sse4.2 CRC32 if available */
183 rte_hash_crc_set_alg(CRC32_SSE42_x64
);
184 if (hash_val
!= rte_hash_crc(data64
, data_len
, init_val
)) {
185 printf("Failed checking CRC32_SW against CRC32_SSE42_x64\n");
189 /* Check against 8-byte-operand ARM64 CRC32 if available */
190 rte_hash_crc_set_alg(CRC32_ARM64
);
191 if (hash_val
!= rte_hash_crc(data64
, data_len
, init_val
)) {
192 printf("Failed checking CRC32_SW against CRC32_ARM64\n");
197 /* Resetting to best available algorithm */
198 rte_hash_crc_set_alg(CRC32_SSE42_x64
);
200 if (i
== CRC32_ITERATIONS
)
203 printf("Failed test data (hex, %zu bytes total):\n", data_len
);
204 for (j
= 0; j
< data_len
; j
++)
205 printf("%02X%c", ((uint8_t *)data64
)[j
],
206 ((j
+1) % 16 == 0 || j
== data_len
- 1) ? '\n' : ' ');
212 * Test a hash function.
214 static void run_hash_func_test(rte_hash_function f
, uint32_t init_val
,
217 static uint8_t key
[MAX_KEYSIZE
];
221 for (i
= 0; i
< key_len
; i
++)
222 key
[i
] = (uint8_t) rte_rand();
224 /* just to be on the safe side */
228 f(key
, key_len
, init_val
);
232 * Test all hash functions.
234 static void run_hash_func_tests(void)
238 for (i
= 0; i
< RTE_DIM(hashtest_funcs
); i
++) {
239 for (j
= 0; j
< RTE_DIM(hashtest_initvals
); j
++) {
240 for (k
= 0; k
< RTE_DIM(hashtest_key_lens
); k
++) {
241 run_hash_func_test(hashtest_funcs
[i
],
242 hashtest_initvals
[j
],
243 hashtest_key_lens
[k
]);
250 * Basic sequence of operations for a single key:
256 * Repeat the test case when 'free on delete' is disabled.
263 static int test_add_delete(void)
265 struct rte_hash
*handle
;
266 /* test with standard add/lookup/delete functions */
267 int pos0
, expectedPos0
;
269 ut_params
.name
= "test1";
270 handle
= rte_hash_create(&ut_params
);
271 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
273 pos0
= rte_hash_add_key(handle
, &keys
[0]);
274 print_key_info("Add", &keys
[0], pos0
);
275 RETURN_IF_ERROR(pos0
< 0, "failed to add key (pos0=%d)", pos0
);
278 pos0
= rte_hash_lookup(handle
, &keys
[0]);
279 print_key_info("Lkp", &keys
[0], pos0
);
280 RETURN_IF_ERROR(pos0
!= expectedPos0
,
281 "failed to find key (pos0=%d)", pos0
);
283 pos0
= rte_hash_del_key(handle
, &keys
[0]);
284 print_key_info("Del", &keys
[0], pos0
);
285 RETURN_IF_ERROR(pos0
!= expectedPos0
,
286 "failed to delete key (pos0=%d)", pos0
);
288 pos0
= rte_hash_lookup(handle
, &keys
[0]);
289 print_key_info("Lkp", &keys
[0], pos0
);
290 RETURN_IF_ERROR(pos0
!= -ENOENT
,
291 "fail: found key after deleting! (pos0=%d)", pos0
);
293 rte_hash_free(handle
);
295 /* repeat test with precomputed hash functions */
296 hash_sig_t hash_value
;
297 int pos1
, expectedPos1
, delPos1
;
299 ut_params
.extra_flag
= RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL
;
300 handle
= rte_hash_create(&ut_params
);
301 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
302 ut_params
.extra_flag
= 0;
304 hash_value
= rte_hash_hash(handle
, &keys
[0]);
305 pos1
= rte_hash_add_key_with_hash(handle
, &keys
[0], hash_value
);
306 print_key_info("Add", &keys
[0], pos1
);
307 RETURN_IF_ERROR(pos1
< 0, "failed to add key (pos1=%d)", pos1
);
310 pos1
= rte_hash_lookup_with_hash(handle
, &keys
[0], hash_value
);
311 print_key_info("Lkp", &keys
[0], pos1
);
312 RETURN_IF_ERROR(pos1
!= expectedPos1
,
313 "failed to find key (pos1=%d)", pos1
);
315 pos1
= rte_hash_del_key_with_hash(handle
, &keys
[0], hash_value
);
316 print_key_info("Del", &keys
[0], pos1
);
317 RETURN_IF_ERROR(pos1
!= expectedPos1
,
318 "failed to delete key (pos1=%d)", pos1
);
321 pos1
= rte_hash_lookup_with_hash(handle
, &keys
[0], hash_value
);
322 print_key_info("Lkp", &keys
[0], pos1
);
323 RETURN_IF_ERROR(pos1
!= -ENOENT
,
324 "fail: found key after deleting! (pos1=%d)", pos1
);
326 pos1
= rte_hash_free_key_with_position(handle
, delPos1
);
327 print_key_info("Free", &keys
[0], delPos1
);
328 RETURN_IF_ERROR(pos1
!= 0,
329 "failed to free key (pos1=%d)", delPos1
);
331 rte_hash_free(handle
);
337 * Sequence of operations for a single key:
342 * - lookup: hit (updated data)
347 static int test_add_update_delete(void)
349 struct rte_hash
*handle
;
350 int pos0
, expectedPos0
;
352 ut_params
.name
= "test2";
353 handle
= rte_hash_create(&ut_params
);
354 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
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: found non-existent key (pos0=%d)", pos0
);
361 pos0
= rte_hash_add_key(handle
, &keys
[0]);
362 print_key_info("Add", &keys
[0], pos0
);
363 RETURN_IF_ERROR(pos0
< 0, "failed to add key (pos0=%d)", pos0
);
366 pos0
= rte_hash_lookup(handle
, &keys
[0]);
367 print_key_info("Lkp", &keys
[0], pos0
);
368 RETURN_IF_ERROR(pos0
!= expectedPos0
,
369 "failed to find key (pos0=%d)", pos0
);
371 pos0
= rte_hash_add_key(handle
, &keys
[0]);
372 print_key_info("Add", &keys
[0], pos0
);
373 RETURN_IF_ERROR(pos0
!= expectedPos0
,
374 "failed to re-add key (pos0=%d)", pos0
);
376 pos0
= rte_hash_lookup(handle
, &keys
[0]);
377 print_key_info("Lkp", &keys
[0], pos0
);
378 RETURN_IF_ERROR(pos0
!= expectedPos0
,
379 "failed to find key (pos0=%d)", pos0
);
381 pos0
= rte_hash_del_key(handle
, &keys
[0]);
382 print_key_info("Del", &keys
[0], pos0
);
383 RETURN_IF_ERROR(pos0
!= expectedPos0
,
384 "failed to delete key (pos0=%d)", pos0
);
386 pos0
= rte_hash_del_key(handle
, &keys
[0]);
387 print_key_info("Del", &keys
[0], pos0
);
388 RETURN_IF_ERROR(pos0
!= -ENOENT
,
389 "fail: deleted already deleted key (pos0=%d)", pos0
);
391 pos0
= rte_hash_lookup(handle
, &keys
[0]);
392 print_key_info("Lkp", &keys
[0], pos0
);
393 RETURN_IF_ERROR(pos0
!= -ENOENT
,
394 "fail: found key after deleting! (pos0=%d)", pos0
);
396 rte_hash_free(handle
);
401 * Sequence of operations for a single key with 'disable free on del' set:
406 * - lookup: hit (updated data)
413 static int test_add_update_delete_free(void)
415 struct rte_hash
*handle
;
416 int pos0
, expectedPos0
, delPos0
, result
;
418 ut_params
.name
= "test2";
419 ut_params
.extra_flag
= RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL
;
420 handle
= rte_hash_create(&ut_params
);
421 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
422 ut_params
.extra_flag
= 0;
424 pos0
= rte_hash_del_key(handle
, &keys
[0]);
425 print_key_info("Del", &keys
[0], pos0
);
426 RETURN_IF_ERROR(pos0
!= -ENOENT
,
427 "fail: found non-existent key (pos0=%d)", pos0
);
429 pos0
= rte_hash_add_key(handle
, &keys
[0]);
430 print_key_info("Add", &keys
[0], pos0
);
431 RETURN_IF_ERROR(pos0
< 0, "failed to add key (pos0=%d)", pos0
);
434 pos0
= rte_hash_lookup(handle
, &keys
[0]);
435 print_key_info("Lkp", &keys
[0], pos0
);
436 RETURN_IF_ERROR(pos0
!= expectedPos0
,
437 "failed to find key (pos0=%d)", pos0
);
439 pos0
= rte_hash_add_key(handle
, &keys
[0]);
440 print_key_info("Add", &keys
[0], pos0
);
441 RETURN_IF_ERROR(pos0
!= expectedPos0
,
442 "failed to re-add key (pos0=%d)", pos0
);
444 pos0
= rte_hash_lookup(handle
, &keys
[0]);
445 print_key_info("Lkp", &keys
[0], pos0
);
446 RETURN_IF_ERROR(pos0
!= expectedPos0
,
447 "failed to find key (pos0=%d)", pos0
);
449 delPos0
= rte_hash_del_key(handle
, &keys
[0]);
450 print_key_info("Del", &keys
[0], delPos0
);
451 RETURN_IF_ERROR(delPos0
!= expectedPos0
,
452 "failed to delete key (pos0=%d)", delPos0
);
454 pos0
= rte_hash_del_key(handle
, &keys
[0]);
455 print_key_info("Del", &keys
[0], pos0
);
456 RETURN_IF_ERROR(pos0
!= -ENOENT
,
457 "fail: deleted already deleted key (pos0=%d)", pos0
);
459 pos0
= rte_hash_lookup(handle
, &keys
[0]);
460 print_key_info("Lkp", &keys
[0], pos0
);
461 RETURN_IF_ERROR(pos0
!= -ENOENT
,
462 "fail: found key after deleting! (pos0=%d)", pos0
);
464 result
= rte_hash_free_key_with_position(handle
, delPos0
);
465 print_key_info("Free", &keys
[0], delPos0
);
466 RETURN_IF_ERROR(result
!= 0,
467 "failed to free key (pos1=%d)", delPos0
);
469 pos0
= rte_hash_lookup(handle
, &keys
[0]);
470 print_key_info("Lkp", &keys
[0], pos0
);
471 RETURN_IF_ERROR(pos0
!= -ENOENT
,
472 "fail: found key after deleting! (pos0=%d)", pos0
);
474 rte_hash_free(handle
);
479 * Sequence of operations for a single key with 'rw concurrency lock free' set:
483 * Repeat the test case when 'multi writer add' is enabled.
488 static int test_add_delete_free_lf(void)
490 /* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
491 #define LCORE_CACHE_SIZE 64
492 struct rte_hash
*handle
;
493 hash_sig_t hash_value
;
494 int pos
, expectedPos
, delPos
;
498 extra_flag
= ut_params
.extra_flag
;
499 ut_params
.extra_flag
= RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF
;
500 handle
= rte_hash_create(&ut_params
);
501 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
502 ut_params
.extra_flag
= extra_flag
;
505 * The number of iterations is at least the same as the number of slots
506 * rte_hash allocates internally. This is to reveal potential issues of
507 * not freeing keys successfully.
509 for (i
= 0; i
< ut_params
.entries
+ 1; i
++) {
510 hash_value
= rte_hash_hash(handle
, &keys
[0]);
511 pos
= rte_hash_add_key_with_hash(handle
, &keys
[0], hash_value
);
512 print_key_info("Add", &keys
[0], pos
);
513 RETURN_IF_ERROR(pos
< 0, "failed to add key (pos=%d)", pos
);
516 pos
= rte_hash_del_key_with_hash(handle
, &keys
[0], hash_value
);
517 print_key_info("Del", &keys
[0], pos
);
518 RETURN_IF_ERROR(pos
!= expectedPos
,
519 "failed to delete key (pos=%d)", pos
);
522 pos
= rte_hash_free_key_with_position(handle
, delPos
);
523 print_key_info("Free", &keys
[0], delPos
);
524 RETURN_IF_ERROR(pos
!= 0,
525 "failed to free key (pos=%d)", delPos
);
528 rte_hash_free(handle
);
530 extra_flag
= ut_params
.extra_flag
;
531 ut_params
.extra_flag
= RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF
|
532 RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD
;
533 handle
= rte_hash_create(&ut_params
);
534 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
535 ut_params
.extra_flag
= extra_flag
;
537 ip_src
= keys
[0].ip_src
;
539 * The number of iterations is at least the same as the number of slots
540 * rte_hash allocates internally. This is to reveal potential issues of
541 * not freeing keys successfully.
543 for (i
= 0; i
< ut_params
.entries
+ (RTE_MAX_LCORE
- 1) *
544 (LCORE_CACHE_SIZE
- 1) + 1; i
++) {
546 hash_value
= rte_hash_hash(handle
, &keys
[0]);
547 pos
= rte_hash_add_key_with_hash(handle
, &keys
[0], hash_value
);
548 print_key_info("Add", &keys
[0], pos
);
549 RETURN_IF_ERROR(pos
< 0, "failed to add key (pos=%d)", pos
);
552 pos
= rte_hash_del_key_with_hash(handle
, &keys
[0], hash_value
);
553 print_key_info("Del", &keys
[0], pos
);
554 RETURN_IF_ERROR(pos
!= expectedPos
,
555 "failed to delete key (pos=%d)", pos
);
558 pos
= rte_hash_free_key_with_position(handle
, delPos
);
559 print_key_info("Free", &keys
[0], delPos
);
560 RETURN_IF_ERROR(pos
!= 0,
561 "failed to free key (pos=%d)", delPos
);
563 keys
[0].ip_src
= ip_src
;
565 rte_hash_free(handle
);
571 * Sequence of operations for retrieving a key with its position
575 * - get the key with its position: hit
577 * - try to get the deleted key: miss
579 * Repeat the test case when 'free on delete' is disabled.
582 * - get the key with its position: hit
584 * - try to get the deleted key: hit
586 * - try to get the deleted key: miss
589 static int test_hash_get_key_with_position(void)
591 struct rte_hash
*handle
= NULL
;
592 int pos
, expectedPos
, delPos
, result
;
595 ut_params
.name
= "hash_get_key_w_pos";
596 handle
= rte_hash_create(&ut_params
);
597 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
599 pos
= rte_hash_add_key(handle
, &keys
[0]);
600 print_key_info("Add", &keys
[0], pos
);
601 RETURN_IF_ERROR(pos
< 0, "failed to add key (pos0=%d)", pos
);
604 result
= rte_hash_get_key_with_position(handle
, pos
, &key
);
605 RETURN_IF_ERROR(result
!= 0, "error retrieving a key");
607 pos
= rte_hash_del_key(handle
, &keys
[0]);
608 print_key_info("Del", &keys
[0], pos
);
609 RETURN_IF_ERROR(pos
!= expectedPos
,
610 "failed to delete key (pos0=%d)", pos
);
612 result
= rte_hash_get_key_with_position(handle
, pos
, &key
);
613 RETURN_IF_ERROR(result
!= -ENOENT
, "non valid key retrieved");
615 rte_hash_free(handle
);
617 ut_params
.name
= "hash_get_key_w_pos";
618 ut_params
.extra_flag
= RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL
;
619 handle
= rte_hash_create(&ut_params
);
620 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
621 ut_params
.extra_flag
= 0;
623 pos
= rte_hash_add_key(handle
, &keys
[0]);
624 print_key_info("Add", &keys
[0], pos
);
625 RETURN_IF_ERROR(pos
< 0, "failed to add key (pos0=%d)", pos
);
628 result
= rte_hash_get_key_with_position(handle
, pos
, &key
);
629 RETURN_IF_ERROR(result
!= 0, "error retrieving a key");
631 delPos
= rte_hash_del_key(handle
, &keys
[0]);
632 print_key_info("Del", &keys
[0], delPos
);
633 RETURN_IF_ERROR(delPos
!= expectedPos
,
634 "failed to delete key (pos0=%d)", delPos
);
636 result
= rte_hash_get_key_with_position(handle
, delPos
, &key
);
637 RETURN_IF_ERROR(result
!= -ENOENT
, "non valid key retrieved");
639 result
= rte_hash_free_key_with_position(handle
, delPos
);
640 print_key_info("Free", &keys
[0], delPos
);
641 RETURN_IF_ERROR(result
!= 0,
642 "failed to free key (pos1=%d)", delPos
);
644 result
= rte_hash_get_key_with_position(handle
, delPos
, &key
);
645 RETURN_IF_ERROR(result
!= -ENOENT
, "non valid key retrieved");
647 rte_hash_free(handle
);
652 * Sequence of operations for find existing hash table
655 * - find existing table: hit
656 * - find non-existing table: miss
659 static int test_hash_find_existing(void)
661 struct rte_hash
*handle
= NULL
, *result
= NULL
;
663 /* Create hash table. */
664 ut_params
.name
= "hash_find_existing";
665 handle
= rte_hash_create(&ut_params
);
666 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
668 /* Try to find existing hash table */
669 result
= rte_hash_find_existing("hash_find_existing");
670 RETURN_IF_ERROR(result
!= handle
, "could not find existing hash table");
672 /* Try to find non-existing hash table */
673 result
= rte_hash_find_existing("hash_find_non_existing");
674 RETURN_IF_ERROR(!(result
== NULL
), "found table that shouldn't exist");
677 rte_hash_free(handle
);
683 * Sequence of operations for 5 keys
686 * - add keys (update)
687 * - lookup keys: hit (updated data)
688 * - delete keys : hit
689 * - lookup keys: miss
691 static int test_five_keys(void)
693 struct rte_hash
*handle
;
694 const void *key_array
[5] = {0};
700 ut_params
.name
= "test3";
701 handle
= rte_hash_create(&ut_params
);
702 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
705 for (i
= 0; i
< 5; i
++) {
706 pos
[i
] = rte_hash_add_key(handle
, &keys
[i
]);
707 print_key_info("Add", &keys
[i
], pos
[i
]);
708 RETURN_IF_ERROR(pos
[i
] < 0,
709 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
710 expected_pos
[i
] = pos
[i
];
714 for(i
= 0; i
< 5; i
++)
715 key_array
[i
] = &keys
[i
];
717 ret
= rte_hash_lookup_bulk(handle
, &key_array
[0], 5, (int32_t *)pos
);
719 for(i
= 0; i
< 5; i
++) {
720 print_key_info("Lkp", key_array
[i
], pos
[i
]);
721 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
722 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
726 for (i
= 0; i
< 5; i
++) {
727 pos
[i
] = rte_hash_add_key(handle
, &keys
[i
]);
728 print_key_info("Add", &keys
[i
], pos
[i
]);
729 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
730 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
734 for (i
= 0; i
< 5; i
++) {
735 pos
[i
] = rte_hash_lookup(handle
, &keys
[i
]);
736 print_key_info("Lkp", &keys
[i
], pos
[i
]);
737 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
738 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
742 for (i
= 0; i
< 5; i
++) {
743 pos
[i
] = rte_hash_del_key(handle
, &keys
[i
]);
744 print_key_info("Del", &keys
[i
], pos
[i
]);
745 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
746 "failed to delete key (pos[%u]=%d)", i
, pos
[i
]);
750 for (i
= 0; i
< 5; i
++) {
751 pos
[i
] = rte_hash_lookup(handle
, &keys
[i
]);
752 print_key_info("Lkp", &keys
[i
], pos
[i
]);
753 RETURN_IF_ERROR(pos
[i
] != -ENOENT
,
754 "found non-existent key (pos[%u]=%d)", i
, pos
[i
]);
758 ret
= rte_hash_lookup_bulk(handle
, &key_array
[0], 5, (int32_t *)pos
);
760 for (i
= 0; i
< 5; i
++) {
761 print_key_info("Lkp", key_array
[i
], pos
[i
]);
762 RETURN_IF_ERROR(pos
[i
] != -ENOENT
,
763 "found not-existent key (pos[%u]=%d)", i
, pos
[i
]);
766 rte_hash_free(handle
);
772 * Add keys to the same bucket until bucket full.
773 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
774 * first 4 successful, 5th successful, pushing existing item in bucket
775 * - lookup the 5 keys: 5 hits
776 * - add the 5 keys again: 5 OK
777 * - lookup the 5 keys: 5 hits (updated data)
778 * - delete the 5 keys: 5 OK
779 * - lookup the 5 keys: 5 misses
781 static int test_full_bucket(void)
783 struct rte_hash_parameters params_pseudo_hash
= {
786 .key_len
= sizeof(struct flow_key
), /* 13 */
787 .hash_func
= pseudo_hash
,
788 .hash_func_init_val
= 0,
791 struct rte_hash
*handle
;
796 handle
= rte_hash_create(¶ms_pseudo_hash
);
797 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
800 for (i
= 0; i
< 4; i
++) {
801 pos
[i
] = rte_hash_add_key(handle
, &keys
[i
]);
802 print_key_info("Add", &keys
[i
], pos
[i
]);
803 RETURN_IF_ERROR(pos
[i
] < 0,
804 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
805 expected_pos
[i
] = pos
[i
];
808 * This should work and will push one of the items
809 * in the bucket because it is full
811 pos
[4] = rte_hash_add_key(handle
, &keys
[4]);
812 print_key_info("Add", &keys
[4], pos
[4]);
813 RETURN_IF_ERROR(pos
[4] < 0,
814 "failed to add key (pos[4]=%d)", pos
[4]);
815 expected_pos
[4] = pos
[4];
818 for (i
= 0; i
< 5; i
++) {
819 pos
[i
] = rte_hash_lookup(handle
, &keys
[i
]);
820 print_key_info("Lkp", &keys
[i
], pos
[i
]);
821 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
822 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
826 for (i
= 0; i
< 5; i
++) {
827 pos
[i
] = rte_hash_add_key(handle
, &keys
[i
]);
828 print_key_info("Add", &keys
[i
], pos
[i
]);
829 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
830 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
834 for (i
= 0; i
< 5; i
++) {
835 pos
[i
] = rte_hash_lookup(handle
, &keys
[i
]);
836 print_key_info("Lkp", &keys
[i
], pos
[i
]);
837 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
838 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
841 /* Delete 1 key, check other keys are still found */
842 pos
[1] = rte_hash_del_key(handle
, &keys
[1]);
843 print_key_info("Del", &keys
[1], pos
[1]);
844 RETURN_IF_ERROR(pos
[1] != expected_pos
[1],
845 "failed to delete key (pos[1]=%d)", pos
[1]);
846 pos
[3] = rte_hash_lookup(handle
, &keys
[3]);
847 print_key_info("Lkp", &keys
[3], pos
[3]);
848 RETURN_IF_ERROR(pos
[3] != expected_pos
[3],
849 "failed lookup after deleting key from same bucket "
850 "(pos[3]=%d)", pos
[3]);
852 /* Go back to previous state */
853 pos
[1] = rte_hash_add_key(handle
, &keys
[1]);
854 print_key_info("Add", &keys
[1], pos
[1]);
855 expected_pos
[1] = pos
[1];
856 RETURN_IF_ERROR(pos
[1] < 0, "failed to add key (pos[1]=%d)", pos
[1]);
859 for (i
= 0; i
< 5; i
++) {
860 pos
[i
] = rte_hash_del_key(handle
, &keys
[i
]);
861 print_key_info("Del", &keys
[i
], pos
[i
]);
862 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
863 "failed to delete key (pos[%u]=%d)", i
, pos
[i
]);
867 for (i
= 0; i
< 5; i
++) {
868 pos
[i
] = rte_hash_lookup(handle
, &keys
[i
]);
869 print_key_info("Lkp", &keys
[i
], pos
[i
]);
870 RETURN_IF_ERROR(pos
[i
] != -ENOENT
,
871 "fail: found non-existent key (pos[%u]=%d)", i
, pos
[i
]);
874 rte_hash_free(handle
);
876 /* Cover the NULL case. */
882 * Similar to the test above (full bucket test), but for extendable buckets.
884 static int test_extendable_bucket(void)
886 struct rte_hash_parameters params_pseudo_hash
= {
889 .key_len
= sizeof(struct flow_key
), /* 13 */
890 .hash_func
= pseudo_hash
,
891 .hash_func_init_val
= 0,
893 .extra_flag
= RTE_HASH_EXTRA_FLAGS_EXT_TABLE
895 struct rte_hash
*handle
;
897 int expected_pos
[64];
899 struct flow_key rand_keys
[64];
901 for (i
= 0; i
< 64; i
++) {
902 rand_keys
[i
].port_dst
= i
;
903 rand_keys
[i
].port_src
= i
+1;
906 handle
= rte_hash_create(¶ms_pseudo_hash
);
907 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
910 for (i
= 0; i
< 64; i
++) {
911 pos
[i
] = rte_hash_add_key(handle
, &rand_keys
[i
]);
912 print_key_info("Add", &rand_keys
[i
], pos
[i
]);
913 RETURN_IF_ERROR(pos
[i
] < 0,
914 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
915 expected_pos
[i
] = pos
[i
];
919 for (i
= 0; i
< 64; i
++) {
920 pos
[i
] = rte_hash_lookup(handle
, &rand_keys
[i
]);
921 print_key_info("Lkp", &rand_keys
[i
], pos
[i
]);
922 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
923 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
927 for (i
= 0; i
< 64; i
++) {
928 pos
[i
] = rte_hash_add_key(handle
, &rand_keys
[i
]);
929 print_key_info("Add", &rand_keys
[i
], pos
[i
]);
930 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
931 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
935 for (i
= 0; i
< 64; i
++) {
936 pos
[i
] = rte_hash_lookup(handle
, &rand_keys
[i
]);
937 print_key_info("Lkp", &rand_keys
[i
], pos
[i
]);
938 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
939 "failed to find key (pos[%u]=%d)", i
, pos
[i
]);
942 /* Delete 1 key, check other keys are still found */
943 pos
[35] = rte_hash_del_key(handle
, &rand_keys
[35]);
944 print_key_info("Del", &rand_keys
[35], pos
[35]);
945 RETURN_IF_ERROR(pos
[35] != expected_pos
[35],
946 "failed to delete key (pos[1]=%d)", pos
[35]);
947 pos
[20] = rte_hash_lookup(handle
, &rand_keys
[20]);
948 print_key_info("Lkp", &rand_keys
[20], pos
[20]);
949 RETURN_IF_ERROR(pos
[20] != expected_pos
[20],
950 "failed lookup after deleting key from same bucket "
951 "(pos[20]=%d)", pos
[20]);
953 /* Go back to previous state */
954 pos
[35] = rte_hash_add_key(handle
, &rand_keys
[35]);
955 print_key_info("Add", &rand_keys
[35], pos
[35]);
956 expected_pos
[35] = pos
[35];
957 RETURN_IF_ERROR(pos
[35] < 0, "failed to add key (pos[1]=%d)", pos
[35]);
960 for (i
= 0; i
< 64; i
++) {
961 pos
[i
] = rte_hash_del_key(handle
, &rand_keys
[i
]);
962 print_key_info("Del", &rand_keys
[i
], pos
[i
]);
963 RETURN_IF_ERROR(pos
[i
] != expected_pos
[i
],
964 "failed to delete key (pos[%u]=%d)", i
, pos
[i
]);
968 for (i
= 0; i
< 64; i
++) {
969 pos
[i
] = rte_hash_lookup(handle
, &rand_keys
[i
]);
970 print_key_info("Lkp", &rand_keys
[i
], pos
[i
]);
971 RETURN_IF_ERROR(pos
[i
] != -ENOENT
,
972 "fail: found non-existent key (pos[%u]=%d)", i
, pos
[i
]);
976 for (i
= 0; i
< 64; i
++) {
977 pos
[i
] = rte_hash_add_key(handle
, &rand_keys
[i
]);
978 print_key_info("Add", &rand_keys
[i
], pos
[i
]);
979 RETURN_IF_ERROR(pos
[i
] < 0,
980 "failed to add key (pos[%u]=%d)", i
, pos
[i
]);
981 expected_pos
[i
] = pos
[i
];
984 rte_hash_free(handle
);
986 /* Cover the NULL case. */
991 /******************************************************************************/
993 fbk_hash_unit_test(void)
995 struct rte_fbk_hash_params params
= {
996 .name
= "fbk_hash_test",
997 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
998 .entries_per_bucket
= 4,
1002 struct rte_fbk_hash_params invalid_params_1
= {
1003 .name
= "invalid_1",
1004 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
+ 1, /* Not power of 2 */
1005 .entries_per_bucket
= 4,
1009 struct rte_fbk_hash_params invalid_params_2
= {
1010 .name
= "invalid_2",
1012 .entries_per_bucket
= 3, /* Not power of 2 */
1016 struct rte_fbk_hash_params invalid_params_3
= {
1017 .name
= "invalid_3",
1018 .entries
= 0, /* Entries is 0 */
1019 .entries_per_bucket
= 4,
1023 struct rte_fbk_hash_params invalid_params_4
= {
1024 .name
= "invalid_4",
1025 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
1026 .entries_per_bucket
= 0, /* Entries per bucket is 0 */
1030 struct rte_fbk_hash_params invalid_params_5
= {
1031 .name
= "invalid_5",
1033 .entries_per_bucket
= 8, /* Entries per bucket > entries */
1037 struct rte_fbk_hash_params invalid_params_6
= {
1038 .name
= "invalid_6",
1039 .entries
= RTE_FBK_HASH_ENTRIES_MAX
* 2, /* Entries > max allowed */
1040 .entries_per_bucket
= 4,
1044 struct rte_fbk_hash_params invalid_params_7
= {
1045 .name
= "invalid_7",
1046 .entries
= RTE_FBK_HASH_ENTRIES_MAX
,
1047 .entries_per_bucket
= RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX
* 2, /* Entries > max allowed */
1051 struct rte_fbk_hash_params invalid_params_8
= {
1052 .name
= "invalid_7",
1053 .entries
= RTE_FBK_HASH_ENTRIES_MAX
,
1054 .entries_per_bucket
= 4,
1055 .socket_id
= RTE_MAX_NUMA_NODES
+ 1, /* invalid socket */
1058 /* try to create two hashes with identical names
1059 * in this case, trying to create a second one will not
1060 * fail but will simply return pointer to the existing
1061 * hash with that name. sort of like a "find hash by name" :-)
1063 struct rte_fbk_hash_params invalid_params_same_name_1
= {
1064 .name
= "same_name", /* hash with identical name */
1066 .entries_per_bucket
= 2,
1070 /* trying to create this hash should return a pointer to an existing hash */
1071 struct rte_fbk_hash_params invalid_params_same_name_2
= {
1072 .name
= "same_name", /* hash with identical name */
1073 .entries
= RTE_FBK_HASH_ENTRIES_MAX
,
1074 .entries_per_bucket
= 4,
1078 /* this is a sanity check for "same name" test
1079 * creating this hash will check if we are actually able to create
1080 * multiple hashes with different names (instead of having just one).
1082 struct rte_fbk_hash_params different_name
= {
1083 .name
= "different_name", /* different name */
1084 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
1085 .entries_per_bucket
= 4,
1089 struct rte_fbk_hash_params params_jhash
= {
1091 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
1092 .entries_per_bucket
= 4,
1094 .hash_func
= rte_jhash_1word
, /* Tests for different hash_func */
1095 .init_val
= RTE_FBK_HASH_INIT_VAL_DEFAULT
,
1098 struct rte_fbk_hash_params params_nohash
= {
1099 .name
= "valid nohash",
1100 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
1101 .entries_per_bucket
= 4,
1103 .hash_func
= NULL
, /* Tests for null hash_func */
1104 .init_val
= RTE_FBK_HASH_INIT_VAL_DEFAULT
,
1107 struct rte_fbk_hash_table
*handle
, *tmp
;
1109 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1110 uint16_t vals
[5] = {28108, 5699, 38490, 2166, 61571};
1113 double used_entries
;
1115 /* Try creating hashes with invalid parameters */
1116 printf("# Testing hash creation with invalid parameters "
1117 "- expect error msgs\n");
1118 handle
= rte_fbk_hash_create(&invalid_params_1
);
1119 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1121 handle
= rte_fbk_hash_create(&invalid_params_2
);
1122 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1124 handle
= rte_fbk_hash_create(&invalid_params_3
);
1125 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1127 handle
= rte_fbk_hash_create(&invalid_params_4
);
1128 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1130 handle
= rte_fbk_hash_create(&invalid_params_5
);
1131 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1133 handle
= rte_fbk_hash_create(&invalid_params_6
);
1134 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1136 handle
= rte_fbk_hash_create(&invalid_params_7
);
1137 RETURN_IF_ERROR_FBK(handle
!= NULL
, "fbk hash creation should have failed");
1139 if (rte_eal_has_hugepages()) {
1140 handle
= rte_fbk_hash_create(&invalid_params_8
);
1141 RETURN_IF_ERROR_FBK(handle
!= NULL
,
1142 "fbk hash creation should have failed");
1145 handle
= rte_fbk_hash_create(&invalid_params_same_name_1
);
1146 RETURN_IF_ERROR_FBK(handle
== NULL
, "fbk hash creation should have succeeded");
1148 tmp
= rte_fbk_hash_create(&invalid_params_same_name_2
);
1150 rte_fbk_hash_free(tmp
);
1151 RETURN_IF_ERROR_FBK(tmp
!= NULL
, "fbk hash creation should have failed");
1153 /* we are not freeing handle here because we need a hash list
1154 * to be not empty for the next test */
1156 /* create a hash in non-empty list - good for coverage */
1157 tmp
= rte_fbk_hash_create(&different_name
);
1158 RETURN_IF_ERROR_FBK(tmp
== NULL
, "fbk hash creation should have succeeded");
1160 /* free both hashes */
1161 rte_fbk_hash_free(handle
);
1162 rte_fbk_hash_free(tmp
);
1164 /* Create empty jhash hash. */
1165 handle
= rte_fbk_hash_create(¶ms_jhash
);
1166 RETURN_IF_ERROR_FBK(handle
== NULL
, "fbk jhash hash creation failed");
1169 rte_fbk_hash_free(handle
);
1171 /* Create empty jhash hash. */
1172 handle
= rte_fbk_hash_create(¶ms_nohash
);
1173 RETURN_IF_ERROR_FBK(handle
== NULL
, "fbk nohash hash creation failed");
1176 rte_fbk_hash_free(handle
);
1178 /* Create empty hash. */
1179 handle
= rte_fbk_hash_create(¶ms
);
1180 RETURN_IF_ERROR_FBK(handle
== NULL
, "fbk hash creation failed");
1182 used_entries
= rte_fbk_hash_get_load_factor(handle
) * LOCAL_FBK_HASH_ENTRIES_MAX
;
1183 RETURN_IF_ERROR_FBK((unsigned)used_entries
!= 0, \
1184 "load factor right after creation is not zero but it should be");
1186 for (i
= 0; i
< 5; i
++) {
1187 status
= rte_fbk_hash_add_key(handle
, keys
[i
], vals
[i
]);
1188 RETURN_IF_ERROR_FBK(status
!= 0, "fbk hash add failed");
1191 used_entries
= rte_fbk_hash_get_load_factor(handle
) * LOCAL_FBK_HASH_ENTRIES_MAX
;
1192 RETURN_IF_ERROR_FBK((unsigned)used_entries
!= (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX
)*LOCAL_FBK_HASH_ENTRIES_MAX
), \
1193 "load factor now is not as expected");
1194 /* Find value of added keys. */
1195 for (i
= 0; i
< 5; i
++) {
1196 status
= rte_fbk_hash_lookup(handle
, keys
[i
]);
1197 RETURN_IF_ERROR_FBK(status
!= vals
[i
],
1198 "fbk hash lookup failed");
1201 /* Change value of added keys. */
1202 for (i
= 0; i
< 5; i
++) {
1203 status
= rte_fbk_hash_add_key(handle
, keys
[i
], vals
[4 - i
]);
1204 RETURN_IF_ERROR_FBK(status
!= 0, "fbk hash update failed");
1207 /* Find new values. */
1208 for (i
= 0; i
< 5; i
++) {
1209 status
= rte_fbk_hash_lookup(handle
, keys
[i
]);
1210 RETURN_IF_ERROR_FBK(status
!= vals
[4-i
],
1211 "fbk hash lookup failed");
1214 /* Delete keys individually. */
1215 for (i
= 0; i
< 5; i
++) {
1216 status
= rte_fbk_hash_delete_key(handle
, keys
[i
]);
1217 RETURN_IF_ERROR_FBK(status
!= 0, "fbk hash delete failed");
1220 used_entries
= rte_fbk_hash_get_load_factor(handle
) * LOCAL_FBK_HASH_ENTRIES_MAX
;
1221 RETURN_IF_ERROR_FBK((unsigned)used_entries
!= 0, \
1222 "load factor right after deletion is not zero but it should be");
1223 /* Lookup should now fail. */
1224 for (i
= 0; i
< 5; i
++) {
1225 status
= rte_fbk_hash_lookup(handle
, keys
[i
]);
1226 RETURN_IF_ERROR_FBK(status
== 0,
1227 "fbk hash lookup should have failed");
1230 /* Add keys again. */
1231 for (i
= 0; i
< 5; i
++) {
1232 status
= rte_fbk_hash_add_key(handle
, keys
[i
], vals
[i
]);
1233 RETURN_IF_ERROR_FBK(status
!= 0, "fbk hash add failed");
1236 /* Make sure they were added. */
1237 for (i
= 0; i
< 5; i
++) {
1238 status
= rte_fbk_hash_lookup(handle
, keys
[i
]);
1239 RETURN_IF_ERROR_FBK(status
!= vals
[i
],
1240 "fbk hash lookup failed");
1243 /* Clear all entries. */
1244 rte_fbk_hash_clear_all(handle
);
1246 /* Lookup should fail. */
1247 for (i
= 0; i
< 5; i
++) {
1248 status
= rte_fbk_hash_lookup(handle
, keys
[i
]);
1249 RETURN_IF_ERROR_FBK(status
== 0,
1250 "fbk hash lookup should have failed");
1255 /* fill up the hash_table */
1256 for (i
= 0; i
< RTE_FBK_HASH_ENTRIES_MAX
+ 1; i
++)
1257 rte_fbk_hash_add_key(handle
, i
, (uint16_t) i
);
1259 /* Find non-existent key in a full hashtable */
1260 status
= rte_fbk_hash_lookup(handle
, RTE_FBK_HASH_ENTRIES_MAX
+ 1);
1261 RETURN_IF_ERROR_FBK(status
!= -ENOENT
,
1262 "fbk hash lookup succeeded");
1264 /* Delete non-existent key in a full hashtable */
1265 status
= rte_fbk_hash_delete_key(handle
, RTE_FBK_HASH_ENTRIES_MAX
+ 1);
1266 RETURN_IF_ERROR_FBK(status
!= -ENOENT
,
1267 "fbk hash delete succeeded");
1269 /* Delete one key from a full hashtable */
1270 status
= rte_fbk_hash_delete_key(handle
, 1);
1271 RETURN_IF_ERROR_FBK(status
!= 0,
1272 "fbk hash delete failed");
1274 /* Clear all entries. */
1275 rte_fbk_hash_clear_all(handle
);
1278 rte_fbk_hash_free(handle
);
1280 /* Cover the NULL case. */
1281 rte_fbk_hash_free(0);
1287 * Sequence of operations for find existing fbk hash table
1290 * - find existing table: hit
1291 * - find non-existing table: miss
1294 static int test_fbk_hash_find_existing(void)
1296 struct rte_fbk_hash_params params
= {
1297 .name
= "fbk_hash_find_existing",
1298 .entries
= LOCAL_FBK_HASH_ENTRIES_MAX
,
1299 .entries_per_bucket
= 4,
1302 struct rte_fbk_hash_table
*handle
= NULL
, *result
= NULL
;
1304 /* Create hash table. */
1305 handle
= rte_fbk_hash_create(¶ms
);
1306 RETURN_IF_ERROR_FBK(handle
== NULL
, "fbk hash creation failed");
1308 /* Try to find existing fbk hash table */
1309 result
= rte_fbk_hash_find_existing("fbk_hash_find_existing");
1310 RETURN_IF_ERROR_FBK(result
!= handle
, "could not find existing fbk hash table");
1312 /* Try to find non-existing fbk hash table */
1313 result
= rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1314 RETURN_IF_ERROR_FBK(!(result
== NULL
), "found fbk table that shouldn't exist");
1317 rte_fbk_hash_free(handle
);
1322 #define BUCKET_ENTRIES 4
1324 * Do tests for hash creation with bad parameters.
1326 static int test_hash_creation_with_bad_parameters(void)
1328 struct rte_hash
*handle
, *tmp
;
1329 struct rte_hash_parameters params
;
1331 handle
= rte_hash_create(NULL
);
1332 if (handle
!= NULL
) {
1333 rte_hash_free(handle
);
1334 printf("Impossible creating hash successfully without any parameter\n");
1338 memcpy(¶ms
, &ut_params
, sizeof(params
));
1339 params
.name
= "creation_with_bad_parameters_0";
1340 params
.entries
= RTE_HASH_ENTRIES_MAX
+ 1;
1341 handle
= rte_hash_create(¶ms
);
1342 if (handle
!= NULL
) {
1343 rte_hash_free(handle
);
1344 printf("Impossible creating hash successfully with entries in parameter exceeded\n");
1348 memcpy(¶ms
, &ut_params
, sizeof(params
));
1349 params
.name
= "creation_with_bad_parameters_2";
1350 params
.entries
= BUCKET_ENTRIES
- 1;
1351 handle
= rte_hash_create(¶ms
);
1352 if (handle
!= NULL
) {
1353 rte_hash_free(handle
);
1354 printf("Impossible creating hash successfully if entries less than bucket_entries in parameter\n");
1358 memcpy(¶ms
, &ut_params
, sizeof(params
));
1359 params
.name
= "creation_with_bad_parameters_3";
1361 handle
= rte_hash_create(¶ms
);
1362 if (handle
!= NULL
) {
1363 rte_hash_free(handle
);
1364 printf("Impossible creating hash successfully if key_len in parameter is zero\n");
1368 memcpy(¶ms
, &ut_params
, sizeof(params
));
1369 params
.name
= "creation_with_bad_parameters_4";
1370 params
.socket_id
= RTE_MAX_NUMA_NODES
+ 1;
1371 handle
= rte_hash_create(¶ms
);
1372 if (handle
!= NULL
) {
1373 rte_hash_free(handle
);
1374 printf("Impossible creating hash successfully with invalid socket\n");
1378 /* test with same name should fail */
1379 memcpy(¶ms
, &ut_params
, sizeof(params
));
1380 params
.name
= "same_name";
1381 handle
= rte_hash_create(¶ms
);
1382 if (handle
== NULL
) {
1383 printf("Cannot create first hash table with 'same_name'\n");
1386 tmp
= rte_hash_create(¶ms
);
1388 printf("Creation of hash table with same name should fail\n");
1389 rte_hash_free(handle
);
1393 rte_hash_free(handle
);
1395 printf("# Test successful. No more errors expected\n");
1401 * Do tests for hash creation with parameters that look incorrect
1402 * but are actually valid.
1405 test_hash_creation_with_good_parameters(void)
1407 struct rte_hash
*handle
;
1408 struct rte_hash_parameters params
;
1410 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1411 memcpy(¶ms
, &ut_params
, sizeof(params
));
1412 params
.name
= "name";
1413 params
.hash_func
= NULL
;
1414 handle
= rte_hash_create(¶ms
);
1415 if (handle
== NULL
) {
1416 printf("Creating hash with null hash_func failed\n");
1420 rte_hash_free(handle
);
1425 #define ITERATIONS 3
1427 * Test to see the average table utilization (entries added/max entries)
1428 * before hitting a random entry that cannot be added
1430 static int test_average_table_utilization(uint32_t ext_table
)
1432 struct rte_hash
*handle
;
1433 uint8_t simple_key
[MAX_KEYSIZE
];
1435 unsigned added_keys
, average_keys_added
= 0;
1439 printf("\n# Running test to determine average utilization"
1440 "\n before adding elements begins to fail\n");
1442 printf("ext table is enabled\n");
1444 printf("ext table is disabled\n");
1446 printf("Measuring performance, please wait");
1448 ut_params
.entries
= 1 << 16;
1449 ut_params
.name
= "test_average_utilization";
1450 ut_params
.hash_func
= rte_jhash
;
1452 ut_params
.extra_flag
|= RTE_HASH_EXTRA_FLAGS_EXT_TABLE
;
1454 ut_params
.extra_flag
&= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE
;
1456 handle
= rte_hash_create(&ut_params
);
1458 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
1460 for (j
= 0; j
< ITERATIONS
; j
++) {
1462 /* Add random entries until key cannot be added */
1463 for (added_keys
= 0; ret
>= 0; added_keys
++) {
1464 for (i
= 0; i
< ut_params
.key_len
; i
++)
1465 simple_key
[i
] = rte_rand() % 255;
1466 ret
= rte_hash_add_key(handle
, simple_key
);
1471 if (ret
!= -ENOSPC
) {
1472 printf("Unexpected error when adding keys\n");
1473 rte_hash_free(handle
);
1477 cnt
= rte_hash_count(handle
);
1478 if (cnt
!= added_keys
) {
1479 printf("rte_hash_count returned wrong value %u, %u,"
1480 "%u\n", j
, added_keys
, cnt
);
1481 rte_hash_free(handle
);
1485 if (cnt
!= ut_params
.entries
) {
1486 printf("rte_hash_count returned wrong value "
1487 "%u, %u, %u\n", j
, added_keys
, cnt
);
1488 rte_hash_free(handle
);
1493 average_keys_added
+= added_keys
;
1495 /* Reset the table */
1496 rte_hash_reset(handle
);
1498 /* Print a dot to show progress on operations */
1503 average_keys_added
/= ITERATIONS
;
1505 printf("\nAverage table utilization = %.2f%% (%u/%u)\n",
1506 ((double) average_keys_added
/ ut_params
.entries
* 100),
1507 average_keys_added
, ut_params
.entries
);
1508 rte_hash_free(handle
);
1513 #define NUM_ENTRIES 256
1514 static int test_hash_iteration(uint32_t ext_table
)
1516 struct rte_hash
*handle
;
1518 uint8_t keys
[NUM_ENTRIES
][MAX_KEYSIZE
];
1519 const void *next_key
;
1521 void *data
[NUM_ENTRIES
];
1522 unsigned added_keys
;
1526 ut_params
.entries
= NUM_ENTRIES
;
1527 ut_params
.name
= "test_hash_iteration";
1528 ut_params
.hash_func
= rte_jhash
;
1529 ut_params
.key_len
= 16;
1531 ut_params
.extra_flag
|= RTE_HASH_EXTRA_FLAGS_EXT_TABLE
;
1533 ut_params
.extra_flag
&= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE
;
1535 handle
= rte_hash_create(&ut_params
);
1536 RETURN_IF_ERROR(handle
== NULL
, "hash creation failed");
1538 /* Add random entries until key cannot be added */
1539 for (added_keys
= 0; added_keys
< NUM_ENTRIES
; added_keys
++) {
1540 data
[added_keys
] = (void *) ((uintptr_t) rte_rand());
1541 for (i
= 0; i
< ut_params
.key_len
; i
++)
1542 keys
[added_keys
][i
] = rte_rand() % 255;
1543 ret
= rte_hash_add_key_data(handle
, keys
[added_keys
], data
[added_keys
]);
1546 printf("Insertion failed for ext table\n");
1553 /* Iterate through the hash table */
1554 while (rte_hash_iterate(handle
, &next_key
, &next_data
, &iter
) >= 0) {
1555 /* Search for the key in the list of keys added */
1556 for (i
= 0; i
< NUM_ENTRIES
; i
++) {
1557 if (memcmp(next_key
, keys
[i
], ut_params
.key_len
) == 0) {
1558 if (next_data
!= data
[i
]) {
1559 printf("Data found in the hash table is"
1560 "not the data added with the key\n");
1567 if (i
== NUM_ENTRIES
) {
1568 printf("Key found in the hash table was not added\n");
1573 /* Check if all keys have been iterated */
1574 if (added_keys
!= 0) {
1575 printf("There were still %u keys to iterate\n", added_keys
);
1579 rte_hash_free(handle
);
1583 rte_hash_free(handle
);
1587 static uint8_t key
[16] = {0x00, 0x01, 0x02, 0x03,
1588 0x04, 0x05, 0x06, 0x07,
1589 0x08, 0x09, 0x0a, 0x0b,
1590 0x0c, 0x0d, 0x0e, 0x0f};
1591 static struct rte_hash_parameters hash_params_ex
= {
1596 .hash_func_init_val
= 0,
1601 * add/delete key with jhash2
1604 test_hash_add_delete_jhash2(void)
1607 struct rte_hash
*handle
;
1610 hash_params_ex
.name
= "hash_test_jhash2";
1611 hash_params_ex
.key_len
= 4;
1612 hash_params_ex
.hash_func
= (rte_hash_function
)rte_jhash_32b
;
1614 handle
= rte_hash_create(&hash_params_ex
);
1615 if (handle
== NULL
) {
1616 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1619 pos1
= rte_hash_add_key(handle
, (void *)&key
[0]);
1621 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1625 pos2
= rte_hash_del_key(handle
, (void *)&key
[0]);
1626 if (pos2
< 0 || pos1
!= pos2
) {
1627 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1634 rte_hash_free(handle
);
1640 * add/delete (2) key with jhash2
1643 test_hash_add_delete_2_jhash2(void)
1646 struct rte_hash
*handle
;
1649 hash_params_ex
.name
= "hash_test_2_jhash2";
1650 hash_params_ex
.key_len
= 8;
1651 hash_params_ex
.hash_func
= (rte_hash_function
)rte_jhash_32b
;
1653 handle
= rte_hash_create(&hash_params_ex
);
1657 pos1
= rte_hash_add_key(handle
, (void *)&key
[0]);
1661 pos2
= rte_hash_del_key(handle
, (void *)&key
[0]);
1662 if (pos2
< 0 || pos1
!= pos2
)
1669 rte_hash_free(handle
);
1675 test_hash_jhash_1word(const void *key
, uint32_t length
, uint32_t initval
)
1677 const uint32_t *k
= key
;
1679 RTE_SET_USED(length
);
1681 return rte_jhash_1word(k
[0], initval
);
1685 test_hash_jhash_2word(const void *key
, uint32_t length
, uint32_t initval
)
1687 const uint32_t *k
= key
;
1689 RTE_SET_USED(length
);
1691 return rte_jhash_2words(k
[0], k
[1], initval
);
1695 test_hash_jhash_3word(const void *key
, uint32_t length
, uint32_t initval
)
1697 const uint32_t *k
= key
;
1699 RTE_SET_USED(length
);
1701 return rte_jhash_3words(k
[0], k
[1], k
[2], initval
);
1705 * add/delete key with jhash 1word
1708 test_hash_add_delete_jhash_1word(void)
1711 struct rte_hash
*handle
;
1714 hash_params_ex
.name
= "hash_test_jhash_1word";
1715 hash_params_ex
.key_len
= 4;
1716 hash_params_ex
.hash_func
= test_hash_jhash_1word
;
1718 handle
= rte_hash_create(&hash_params_ex
);
1720 goto fail_jhash_1word
;
1722 pos1
= rte_hash_add_key(handle
, (void *)&key
[0]);
1724 goto fail_jhash_1word
;
1726 pos2
= rte_hash_del_key(handle
, (void *)&key
[0]);
1727 if (pos2
< 0 || pos1
!= pos2
)
1728 goto fail_jhash_1word
;
1734 rte_hash_free(handle
);
1740 * add/delete key with jhash 2word
1743 test_hash_add_delete_jhash_2word(void)
1746 struct rte_hash
*handle
;
1749 hash_params_ex
.name
= "hash_test_jhash_2word";
1750 hash_params_ex
.key_len
= 8;
1751 hash_params_ex
.hash_func
= test_hash_jhash_2word
;
1753 handle
= rte_hash_create(&hash_params_ex
);
1755 goto fail_jhash_2word
;
1757 pos1
= rte_hash_add_key(handle
, (void *)&key
[0]);
1759 goto fail_jhash_2word
;
1761 pos2
= rte_hash_del_key(handle
, (void *)&key
[0]);
1762 if (pos2
< 0 || pos1
!= pos2
)
1763 goto fail_jhash_2word
;
1769 rte_hash_free(handle
);
1775 * add/delete key with jhash 3word
1778 test_hash_add_delete_jhash_3word(void)
1781 struct rte_hash
*handle
;
1784 hash_params_ex
.name
= "hash_test_jhash_3word";
1785 hash_params_ex
.key_len
= 12;
1786 hash_params_ex
.hash_func
= test_hash_jhash_3word
;
1788 handle
= rte_hash_create(&hash_params_ex
);
1790 goto fail_jhash_3word
;
1792 pos1
= rte_hash_add_key(handle
, (void *)&key
[0]);
1794 goto fail_jhash_3word
;
1796 pos2
= rte_hash_del_key(handle
, (void *)&key
[0]);
1797 if (pos2
< 0 || pos1
!= pos2
)
1798 goto fail_jhash_3word
;
1804 rte_hash_free(handle
);
1810 * Do all unit and performance tests.
1815 if (test_add_delete() < 0)
1817 if (test_hash_add_delete_jhash2() < 0)
1819 if (test_hash_add_delete_2_jhash2() < 0)
1821 if (test_hash_add_delete_jhash_1word() < 0)
1823 if (test_hash_add_delete_jhash_2word() < 0)
1825 if (test_hash_add_delete_jhash_3word() < 0)
1827 if (test_hash_get_key_with_position() < 0)
1829 if (test_hash_find_existing() < 0)
1831 if (test_add_update_delete() < 0)
1833 if (test_add_update_delete_free() < 0)
1835 if (test_add_delete_free_lf() < 0)
1837 if (test_five_keys() < 0)
1839 if (test_full_bucket() < 0)
1841 if (test_extendable_bucket() < 0)
1844 if (test_fbk_hash_find_existing() < 0)
1846 if (fbk_hash_unit_test() < 0)
1848 if (test_hash_creation_with_bad_parameters() < 0)
1850 if (test_hash_creation_with_good_parameters() < 0)
1853 /* ext table disabled */
1854 if (test_average_table_utilization(0) < 0)
1856 if (test_hash_iteration(0) < 0)
1859 /* ext table enabled */
1860 if (test_average_table_utilization(1) < 0)
1862 if (test_hash_iteration(1) < 0)
1865 run_hash_func_tests();
1867 if (test_crc32_hash_alg_equiv() < 0)
1873 REGISTER_TEST_COMMAND(hash_autotest
, test_hash
);