1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2015 Intel Corporation
9 #include <rte_cycles.h>
10 #include <rte_malloc.h>
12 #include <rte_hash_crc.h>
13 #include <rte_jhash.h>
14 #include <rte_fbk_hash.h>
15 #include <rte_random.h>
16 #include <rte_string_fns.h>
20 #define MAX_ENTRIES (1 << 19)
21 #define KEYS_TO_ADD (MAX_ENTRIES)
22 #define ADD_PERCENT 0.75 /* 75% table utilization */
23 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
24 /* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */
26 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
27 #define MAX_KEYSIZE 64
28 #define NUM_KEYSIZES 10
29 #define NUM_SHUFFLES 10
40 static uint32_t hashtest_key_lens[] = {
41 /* standard key sizes */
43 /* IPv4 SRC + DST + protocol, unpadded */
45 /* IPv4 5-tuple, unpadded */
47 /* IPv6 5-tuple, unpadded */
49 /* IPv6 5-tuple, padded to 8-byte boundary */
53 struct rte_hash *h[NUM_KEYSIZES];
55 /* Array that stores if a slot is full */
56 static uint8_t slot_taken[MAX_ENTRIES];
58 /* Array to store number of cycles per operation */
59 static uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
61 /* Array to store all input keys */
62 static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
64 /* Array to store the precomputed hash for 'keys' */
65 static hash_sig_t signatures[KEYS_TO_ADD];
67 /* Array to store how many busy entries have each bucket */
68 static uint8_t buckets[NUM_BUCKETS];
70 /* Array to store the positions where keys are added */
71 static int32_t positions[KEYS_TO_ADD];
73 /* Parameters used for hash table in unit test functions. */
74 static struct rte_hash_parameters ut_params = {
75 .entries = MAX_ENTRIES,
76 .hash_func = rte_jhash,
77 .hash_func_init_val = 0,
81 create_table(unsigned int with_data, unsigned int table_index,
82 unsigned int with_locks, unsigned int ext)
84 char name[RTE_HASH_NAMESIZE];
87 /* Table will store 8-byte data */
88 snprintf(name, sizeof(name), "test_hash%u_data",
89 hashtest_key_lens[table_index]);
91 snprintf(name, sizeof(name), "test_hash%u",
92 hashtest_key_lens[table_index]);
96 ut_params.extra_flag =
97 RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT
98 | RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY;
100 ut_params.extra_flag = 0;
103 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
105 ut_params.name = name;
106 ut_params.key_len = hashtest_key_lens[table_index];
107 ut_params.socket_id = rte_socket_id();
108 h[table_index] = rte_hash_find_existing(name);
109 rte_hash_free(h[table_index]);
110 h[table_index] = rte_hash_create(&ut_params);
111 if (h[table_index] == NULL) {
112 printf("Error creating table\n");
119 /* Shuffle the keys that have been added, so lookups will be totally random */
121 shuffle_input_keys(unsigned int table_index, unsigned int ext)
125 uint8_t temp_key[MAX_KEYSIZE];
126 hash_sig_t temp_signature;
127 int32_t temp_position;
128 unsigned int keys_to_add;
131 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
133 keys_to_add = KEYS_TO_ADD;
135 for (i = keys_to_add - 1; i > 0; i--) {
136 swap_idx = rte_rand() % i;
138 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
139 temp_signature = signatures[i];
140 temp_position = positions[i];
142 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
143 signatures[i] = signatures[swap_idx];
144 positions[i] = positions[swap_idx];
146 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
147 signatures[swap_idx] = temp_signature;
148 positions[swap_idx] = temp_position;
153 * Looks for random keys which
154 * ALL can fit in hash table (no errors)
157 get_input_keys(unsigned int with_pushes, unsigned int table_index,
161 unsigned bucket_idx, incr, success = 1;
164 const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
165 unsigned int keys_to_add;
168 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
170 keys_to_add = KEYS_TO_ADD;
171 /* Reset all arrays */
172 for (i = 0; i < MAX_ENTRIES; i++)
175 for (i = 0; i < NUM_BUCKETS; i++)
178 for (j = 0; j < hashtest_key_lens[table_index]; j++)
182 * Add only entries that are not duplicated and that fits in the table
183 * (cannot store more than BUCKET_SIZE entries in a bucket).
184 * Regardless a key has been added correctly or not (success),
185 * the next one to try will be increased by 1.
187 for (i = 0; i < keys_to_add;) {
191 /* Overflow, need to increment the next byte */
194 for (j = 1; j < hashtest_key_lens[table_index]; j++) {
195 /* Do not increase next byte */
198 keys[i][j] = keys[i - 1][j];
200 keys[i][j] = keys[i][j];
201 /* Increase next byte by one */
204 keys[i][j] = keys[i-1][j] + 1;
206 keys[i][j] = keys[i][j] + 1;
215 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
216 bucket_idx = signatures[i] & bucket_bitmask;
218 * If we are not inserting keys in secondary location,
219 * when bucket is full, do not try to insert the key
221 if (with_pushes == 0)
222 if (buckets[bucket_idx] == BUCKET_SIZE)
225 /* If key can be added, leave in successful key arrays "keys" */
226 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
229 /* If key is already added, ignore the entry and do not store */
233 /* Store the returned position and mark slot as taken */
236 buckets[bucket_idx]++;
243 /* Reset the table, so we can measure the time to add all the entries */
244 rte_hash_free(h[table_index]);
245 h[table_index] = rte_hash_create(&ut_params);
251 timed_adds(unsigned int with_hash, unsigned int with_data,
252 unsigned int table_index, unsigned int ext)
255 const uint64_t start_tsc = rte_rdtsc();
258 unsigned int keys_to_add;
260 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
262 keys_to_add = KEYS_TO_ADD;
264 for (i = 0; i < keys_to_add; i++) {
265 data = (void *) ((uintptr_t) signatures[i]);
266 if (with_hash && with_data) {
267 ret = rte_hash_add_key_with_hash_data(h[table_index],
268 (const void *) keys[i],
269 signatures[i], data);
271 printf("H+D: Failed to add key number %u\n", i);
274 } else if (with_hash && !with_data) {
275 ret = rte_hash_add_key_with_hash(h[table_index],
276 (const void *) keys[i],
281 printf("H: Failed to add key number %u\n", i);
284 } else if (!with_hash && with_data) {
285 ret = rte_hash_add_key_data(h[table_index],
286 (const void *) keys[i],
289 printf("D: Failed to add key number %u\n", i);
293 ret = rte_hash_add_key(h[table_index], keys[i]);
297 printf("Failed to add key number %u\n", i);
303 const uint64_t end_tsc = rte_rdtsc();
304 const uint64_t time_taken = end_tsc - start_tsc;
306 cycles[table_index][OP_ADD][with_hash][with_data] = time_taken/keys_to_add;
312 timed_lookups(unsigned int with_hash, unsigned int with_data,
313 unsigned int table_index, unsigned int ext)
316 const uint64_t start_tsc = rte_rdtsc();
320 unsigned int keys_to_add, num_lookups;
323 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
324 num_lookups = NUM_LOOKUPS * ADD_PERCENT;
326 keys_to_add = KEYS_TO_ADD;
327 num_lookups = NUM_LOOKUPS;
329 for (i = 0; i < num_lookups / keys_to_add; i++) {
330 for (j = 0; j < keys_to_add; j++) {
331 if (with_hash && with_data) {
332 ret = rte_hash_lookup_with_hash_data(h[table_index],
333 (const void *) keys[j],
334 signatures[j], &ret_data);
336 printf("Key number %u was not found\n", j);
339 expected_data = (void *) ((uintptr_t) signatures[j]);
340 if (ret_data != expected_data) {
341 printf("Data returned for key number %u is %p,"
342 " but should be %p\n", j, ret_data,
346 } else if (with_hash && !with_data) {
347 ret = rte_hash_lookup_with_hash(h[table_index],
348 (const void *) keys[j],
350 if (ret < 0 || ret != positions[j]) {
351 printf("Key looked up in %d, should be in %d\n",
355 } else if (!with_hash && with_data) {
356 ret = rte_hash_lookup_data(h[table_index],
357 (const void *) keys[j], &ret_data);
359 printf("Key number %u was not found\n", j);
362 expected_data = (void *) ((uintptr_t) signatures[j]);
363 if (ret_data != expected_data) {
364 printf("Data returned for key number %u is %p,"
365 " but should be %p\n", j, ret_data,
370 ret = rte_hash_lookup(h[table_index], keys[j]);
371 if (ret < 0 || ret != positions[j]) {
372 printf("Key looked up in %d, should be in %d\n",
380 const uint64_t end_tsc = rte_rdtsc();
381 const uint64_t time_taken = end_tsc - start_tsc;
383 cycles[table_index][OP_LOOKUP][with_hash][with_data] = time_taken/num_lookups;
389 timed_lookups_multi(unsigned int with_hash, unsigned int with_data,
390 unsigned int table_index, unsigned int ext)
393 int32_t positions_burst[BURST_SIZE];
394 const void *keys_burst[BURST_SIZE];
395 void *expected_data[BURST_SIZE];
396 void *ret_data[BURST_SIZE];
399 unsigned int keys_to_add, num_lookups;
402 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
403 num_lookups = NUM_LOOKUPS * ADD_PERCENT;
405 keys_to_add = KEYS_TO_ADD;
406 num_lookups = NUM_LOOKUPS;
409 const uint64_t start_tsc = rte_rdtsc();
411 for (i = 0; i < num_lookups/keys_to_add; i++) {
412 for (j = 0; j < keys_to_add/BURST_SIZE; j++) {
413 for (k = 0; k < BURST_SIZE; k++)
414 keys_burst[k] = keys[j * BURST_SIZE + k];
415 if (!with_hash && with_data) {
416 ret = rte_hash_lookup_bulk_data(h[table_index],
417 (const void **) keys_burst,
421 if (ret != BURST_SIZE) {
422 printf("Expect to find %u keys,"
423 " but found %d\n", BURST_SIZE, ret);
426 for (k = 0; k < BURST_SIZE; k++) {
427 if ((hit_mask & (1ULL << k)) == 0) {
428 printf("Key number %u not found\n",
432 expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]);
433 if (ret_data[k] != expected_data[k]) {
434 printf("Data returned for key number %u is %p,"
435 " but should be %p\n", j * BURST_SIZE + k,
436 ret_data[k], expected_data[k]);
440 } else if (with_hash && with_data) {
441 ret = rte_hash_lookup_with_hash_bulk_data(
443 (const void **)keys_burst,
444 &signatures[j * BURST_SIZE],
445 BURST_SIZE, &hit_mask, ret_data);
446 if (ret != BURST_SIZE) {
447 printf("Expect to find %u keys,"
452 for (k = 0; k < BURST_SIZE; k++) {
453 if ((hit_mask & (1ULL << k)) == 0) {
454 printf("Key number %u"
460 (void *)((uintptr_t)signatures[
461 j * BURST_SIZE + k]);
462 if (ret_data[k] != expected_data[k]) {
463 printf("Data returned for key"
465 " but should be %p\n",
472 } else if (with_hash && !with_data) {
473 ret = rte_hash_lookup_with_hash_bulk(
475 (const void **)keys_burst,
476 &signatures[j * BURST_SIZE],
477 BURST_SIZE, positions_burst);
478 for (k = 0; k < BURST_SIZE; k++) {
479 if (positions_burst[k] !=
482 printf("Key looked up in %d, should be in %d\n",
490 rte_hash_lookup_bulk(h[table_index],
491 (const void **) keys_burst,
494 for (k = 0; k < BURST_SIZE; k++) {
495 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
496 printf("Key looked up in %d, should be in %d\n",
498 positions[j * BURST_SIZE + k]);
506 const uint64_t end_tsc = rte_rdtsc();
507 const uint64_t time_taken = end_tsc - start_tsc;
509 cycles[table_index][OP_LOOKUP_MULTI][with_hash][with_data] =
510 time_taken/num_lookups;
516 timed_deletes(unsigned int with_hash, unsigned int with_data,
517 unsigned int table_index, unsigned int ext)
520 const uint64_t start_tsc = rte_rdtsc();
522 unsigned int keys_to_add;
524 keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
526 keys_to_add = KEYS_TO_ADD;
528 for (i = 0; i < keys_to_add; i++) {
529 /* There are no delete functions with data, so just call two functions */
531 ret = rte_hash_del_key_with_hash(h[table_index],
532 (const void *) keys[i],
535 ret = rte_hash_del_key(h[table_index],
536 (const void *) keys[i]);
540 printf("Failed to delete key number %u\n", i);
545 const uint64_t end_tsc = rte_rdtsc();
546 const uint64_t time_taken = end_tsc - start_tsc;
548 cycles[table_index][OP_DELETE][with_hash][with_data] = time_taken/keys_to_add;
554 free_table(unsigned table_index)
556 rte_hash_free(h[table_index]);
560 reset_table(unsigned table_index)
562 rte_hash_reset(h[table_index]);
566 run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks,
569 unsigned i, j, with_data, with_hash;
571 printf("Measuring performance, please wait");
574 for (with_data = 0; with_data <= 1; with_data++) {
575 for (i = 0; i < NUM_KEYSIZES; i++) {
576 if (create_table(with_data, i, with_locks, ext) < 0)
579 if (get_input_keys(with_pushes, i, ext) < 0)
581 for (with_hash = 0; with_hash <= 1; with_hash++) {
582 if (timed_adds(with_hash, with_data, i, ext) < 0)
585 for (j = 0; j < NUM_SHUFFLES; j++)
586 shuffle_input_keys(i, ext);
588 if (timed_lookups(with_hash, with_data, i, ext) < 0)
591 if (timed_lookups_multi(with_hash, with_data,
595 if (timed_deletes(with_hash, with_data, i, ext) < 0)
598 /* Print a dot to show progress on operations */
608 printf("\nResults (in CPU cycles/operation)\n");
609 printf("-----------------------------------\n");
610 for (with_data = 0; with_data <= 1; with_data++) {
612 printf("\n Operations with 8-byte data\n");
614 printf("\n Operations without data\n");
615 for (with_hash = 0; with_hash <= 1; with_hash++) {
617 printf("\nWith pre-computed hash values\n");
619 printf("\nWithout pre-computed hash values\n");
621 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
622 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
623 for (i = 0; i < NUM_KEYSIZES; i++) {
624 printf("%-18d", hashtest_key_lens[i]);
625 for (j = 0; j < NUM_OPERATIONS; j++)
626 printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]);
634 /* Control operation of performance testing of fbk hash. */
635 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
636 #define TEST_SIZE 1000000 /* How many operations to time. */
637 #define TEST_ITERATIONS 30 /* How many measurements to take. */
638 #define ENTRIES (1 << 15) /* How many entries. */
641 fbk_hash_perf_test(void)
643 struct rte_fbk_hash_params params = {
644 .name = "fbk_hash_test",
646 .entries_per_bucket = 4,
647 .socket_id = rte_socket_id(),
649 struct rte_fbk_hash_table *handle = NULL;
650 uint32_t *keys = NULL;
651 unsigned indexes[TEST_SIZE];
652 uint64_t lookup_time = 0;
659 handle = rte_fbk_hash_create(¶ms);
660 if (handle == NULL) {
661 printf("Error creating table\n");
665 keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
667 printf("fbk hash: memory allocation for key store failed\n");
671 /* Generate random keys and values. */
672 for (i = 0; i < ENTRIES; i++) {
673 key = (uint32_t)rte_rand();
674 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
675 val = (uint16_t)rte_rand();
677 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
681 if (added > (LOAD_FACTOR * ENTRIES))
685 for (i = 0; i < TEST_ITERATIONS; i++) {
689 /* Generate random indexes into keys[] array. */
690 for (j = 0; j < TEST_SIZE; j++)
691 indexes[j] = rte_rand() % added;
695 for (j = 0; j < TEST_SIZE; j++)
696 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
699 lookup_time += (double)(end - begin);
702 printf("\n\n *** FBK Hash function performance test results ***\n");
704 * The use of the 'value' variable ensures that the hash lookup is not
705 * being optimised out by the compiler.
708 printf("Number of ticks per lookup = %g\n",
709 (double)lookup_time /
710 ((double)TEST_ITERATIONS * (double)TEST_SIZE));
712 rte_fbk_hash_free(handle);
720 unsigned int with_pushes, with_locks;
722 if (RTE_EXEC_ENV_IS_WINDOWS)
725 for (with_locks = 0; with_locks <= 1; with_locks++) {
727 printf("\nWith locks in the code\n");
729 printf("\nWithout locks in the code\n");
730 for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
731 if (with_pushes == 0)
732 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
734 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
735 if (run_all_tbl_perf_tests(with_pushes, with_locks, 0) < 0)
740 printf("\n EXTENDABLE BUCKETS PERFORMANCE\n");
742 if (run_all_tbl_perf_tests(1, 0, 1) < 0)
745 if (fbk_hash_perf_test() < 0)
751 REGISTER_TEST_COMMAND(hash_perf_autotest, test_hash_perf);