4 * Copyright(c) 2010-2015 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.
37 #include <rte_lcore.h>
38 #include <rte_cycles.h>
39 #include <rte_malloc.h>
41 #include <rte_hash_crc.h>
42 #include <rte_jhash.h>
43 #include <rte_fbk_hash.h>
44 #include <rte_random.h>
45 #include <rte_string_fns.h>
49 #define MAX_ENTRIES (1 << 19)
50 #define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */
51 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
53 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
54 #define MAX_KEYSIZE 64
55 #define NUM_KEYSIZES 10
56 #define NUM_SHUFFLES 10
67 static uint32_t hashtest_key_lens[] = {
68 /* standard key sizes */
70 /* IPv4 SRC + DST + protocol, unpadded */
72 /* IPv4 5-tuple, unpadded */
74 /* IPv6 5-tuple, unpadded */
76 /* IPv6 5-tuple, padded to 8-byte boundary */
80 struct rte_hash *h[NUM_KEYSIZES];
82 /* Array that stores if a slot is full */
83 uint8_t slot_taken[MAX_ENTRIES];
85 /* Array to store number of cycles per operation */
86 uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
88 /* Array to store all input keys */
89 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
91 /* Array to store the precomputed hash for 'keys' */
92 hash_sig_t signatures[KEYS_TO_ADD];
94 /* Array to store how many busy entries have each bucket */
95 uint8_t buckets[NUM_BUCKETS];
97 /* Array to store the positions where keys are added */
98 int32_t positions[KEYS_TO_ADD];
100 /* Parameters used for hash table in unit test functions. */
101 static struct rte_hash_parameters ut_params = {
102 .entries = MAX_ENTRIES,
103 .bucket_entries = BUCKET_SIZE,
104 .hash_func = rte_jhash,
105 .hash_func_init_val = 0,
109 create_table(unsigned with_data, unsigned table_index)
111 char name[RTE_HASH_NAMESIZE];
114 /* Table will store 8-byte data */
115 sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]);
117 sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
119 ut_params.name = name;
120 ut_params.key_len = hashtest_key_lens[table_index];
121 ut_params.socket_id = rte_socket_id();
122 h[table_index] = rte_hash_find_existing(name);
123 if (h[table_index] != NULL)
125 * If table was already created, free it to create it again,
126 * so we force it is empty
128 rte_hash_free(h[table_index]);
129 h[table_index] = rte_hash_create(&ut_params);
130 if (h[table_index] == NULL) {
131 printf("Error creating table\n");
138 /* Shuffle the keys that have been added, so lookups will be totally random */
140 shuffle_input_keys(unsigned table_index)
144 uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];
145 hash_sig_t temp_signature;
146 int32_t temp_position;
148 for (i = KEYS_TO_ADD - 1; i > 0; i--) {
149 swap_idx = rte_rand() % i;
151 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
152 temp_signature = signatures[i];
153 temp_position = positions[i];
155 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
156 signatures[i] = signatures[swap_idx];
157 positions[i] = positions[swap_idx];
159 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
160 signatures[swap_idx] = temp_signature;
161 positions[swap_idx] = temp_position;
166 * Looks for random keys which
167 * ALL can fit in hash table (no errors)
170 get_input_keys(unsigned with_pushes, unsigned table_index)
173 unsigned bucket_idx, incr, success = 1;
176 const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
178 /* Reset all arrays */
179 for (i = 0; i < MAX_ENTRIES; i++)
182 for (i = 0; i < NUM_BUCKETS; i++)
185 for (j = 0; j < hashtest_key_lens[table_index]; j++)
189 * Add only entries that are not duplicated and that fits in the table
190 * (cannot store more than BUCKET_SIZE entries in a bucket).
191 * Regardless a key has been added correctly or not (success),
192 * the next one to try will be increased by 1.
194 for (i = 0; i < KEYS_TO_ADD;) {
198 /* Overflow, need to increment the next byte */
201 for (j = 1; j < hashtest_key_lens[table_index]; j++) {
202 /* Do not increase next byte */
205 keys[i][j] = keys[i - 1][j];
207 keys[i][j] = keys[i][j];
208 /* Increase next byte by one */
211 keys[i][j] = keys[i-1][j] + 1;
213 keys[i][j] = keys[i][j] + 1;
222 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
223 bucket_idx = signatures[i] & bucket_bitmask;
225 * If we are not inserting keys in secondary location,
226 * when bucket is full, do not try to insert the key
228 if (with_pushes == 0)
229 if (buckets[bucket_idx] == BUCKET_SIZE)
232 /* If key can be added, leave in successful key arrays "keys" */
233 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
236 /* If key is already added, ignore the entry and do not store */
240 /* Store the returned position and mark slot as taken */
243 buckets[bucket_idx]++;
250 /* Reset the table, so we can measure the time to add all the entries */
251 rte_hash_free(h[table_index]);
252 h[table_index] = rte_hash_create(&ut_params);
258 timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
261 const uint64_t start_tsc = rte_rdtsc();
265 for (i = 0; i < KEYS_TO_ADD; i++) {
266 data = (void *) ((uintptr_t) signatures[i]);
267 if (with_hash && with_data) {
268 ret = rte_hash_add_key_with_hash_data(h[table_index],
269 (const void *) keys[i],
270 signatures[i], data);
272 printf("Failed to add key number %u\n", ret);
275 } else if (with_hash && !with_data) {
276 ret = rte_hash_add_key_with_hash(h[table_index],
277 (const void *) keys[i],
282 printf("Failed to add key number %u\n", ret);
285 } else if (!with_hash && with_data) {
286 ret = rte_hash_add_key_data(h[table_index],
287 (const void *) keys[i],
290 printf("Failed to add key number %u\n", ret);
294 ret = rte_hash_add_key(h[table_index], keys[i]);
298 printf("Failed to add key number %u\n", ret);
304 const uint64_t end_tsc = rte_rdtsc();
305 const uint64_t time_taken = end_tsc - start_tsc;
307 cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD;
313 timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
316 const uint64_t start_tsc = rte_rdtsc();
321 for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
322 for (j = 0; j < KEYS_TO_ADD; j++) {
323 if (with_hash && with_data) {
324 ret = rte_hash_lookup_with_hash_data(h[table_index],
325 (const void *) keys[j],
326 signatures[j], &ret_data);
328 printf("Key number %u was not found\n", j);
331 expected_data = (void *) ((uintptr_t) signatures[j]);
332 if (ret_data != expected_data) {
333 printf("Data returned for key number %u is %p,"
334 " but should be %p\n", j, ret_data,
338 } else if (with_hash && !with_data) {
339 ret = rte_hash_lookup_with_hash(h[table_index],
340 (const void *) keys[j],
342 if (ret < 0 || ret != positions[j]) {
343 printf("Key looked up in %d, should be in %d\n",
347 } else if (!with_hash && with_data) {
348 ret = rte_hash_lookup_data(h[table_index],
349 (const void *) keys[j], &ret_data);
351 printf("Key number %u was not found\n", j);
354 expected_data = (void *) ((uintptr_t) signatures[j]);
355 if (ret_data != expected_data) {
356 printf("Data returned for key number %u is %p,"
357 " but should be %p\n", j, ret_data,
362 ret = rte_hash_lookup(h[table_index], keys[j]);
363 if (ret < 0 || ret != positions[j]) {
364 printf("Key looked up in %d, should be in %d\n",
372 const uint64_t end_tsc = rte_rdtsc();
373 const uint64_t time_taken = end_tsc - start_tsc;
375 cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS;
381 timed_lookups_multi(unsigned with_data, unsigned table_index)
384 int32_t positions_burst[BURST_SIZE];
385 const void *keys_burst[BURST_SIZE];
386 void *expected_data[BURST_SIZE];
387 void *ret_data[BURST_SIZE];
391 const uint64_t start_tsc = rte_rdtsc();
393 for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
394 for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
395 for (k = 0; k < BURST_SIZE; k++)
396 keys_burst[k] = keys[j * BURST_SIZE + k];
398 ret = rte_hash_lookup_bulk_data(h[table_index],
399 (const void **) keys_burst,
403 if (ret != BURST_SIZE) {
404 printf("Expect to find %u keys,"
405 " but found %d\n", BURST_SIZE, ret);
408 for (k = 0; k < BURST_SIZE; k++) {
409 if ((hit_mask & (1ULL << k)) == 0) {
410 printf("Key number %u not found\n",
414 expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]);
415 if (ret_data[k] != expected_data[k]) {
416 printf("Data returned for key number %u is %p,"
417 " but should be %p\n", j * BURST_SIZE + k,
418 ret_data[k], expected_data[k]);
423 rte_hash_lookup_bulk(h[table_index],
424 (const void **) keys_burst,
427 for (k = 0; k < BURST_SIZE; k++) {
428 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
429 printf("Key looked up in %d, should be in %d\n",
431 positions[j * BURST_SIZE + k]);
439 const uint64_t end_tsc = rte_rdtsc();
440 const uint64_t time_taken = end_tsc - start_tsc;
442 cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS;
448 timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
451 const uint64_t start_tsc = rte_rdtsc();
454 for (i = 0; i < KEYS_TO_ADD; i++) {
455 /* There are no delete functions with data, so just call two functions */
457 ret = rte_hash_del_key_with_hash(h[table_index],
458 (const void *) keys[i],
461 ret = rte_hash_del_key(h[table_index],
462 (const void *) keys[i]);
466 printf("Failed to add key number %u\n", ret);
471 const uint64_t end_tsc = rte_rdtsc();
472 const uint64_t time_taken = end_tsc - start_tsc;
474 cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD;
480 free_table(unsigned table_index)
482 rte_hash_free(h[table_index]);
486 reset_table(unsigned table_index)
488 rte_hash_reset(h[table_index]);
492 run_all_tbl_perf_tests(unsigned with_pushes)
494 unsigned i, j, with_data, with_hash;
496 printf("Measuring performance, please wait");
499 for (with_data = 0; with_data <= 1; with_data++) {
500 for (i = 0; i < NUM_KEYSIZES; i++) {
501 if (create_table(with_data, i) < 0)
504 if (get_input_keys(with_pushes, i) < 0)
506 for (with_hash = 0; with_hash <= 1; with_hash++) {
507 if (timed_adds(with_hash, with_data, i) < 0)
510 for (j = 0; j < NUM_SHUFFLES; j++)
511 shuffle_input_keys(i);
513 if (timed_lookups(with_hash, with_data, i) < 0)
516 if (timed_lookups_multi(with_data, i) < 0)
519 if (timed_deletes(with_hash, with_data, i) < 0)
522 /* Print a dot to show progress on operations */
532 printf("\nResults (in CPU cycles/operation)\n");
533 printf("-----------------------------------\n");
534 for (with_data = 0; with_data <= 1; with_data++) {
536 printf("\n Operations with 8-byte data\n");
538 printf("\n Operations without data\n");
539 for (with_hash = 0; with_hash <= 1; with_hash++) {
541 printf("\nWith pre-computed hash values\n");
543 printf("\nWithout pre-computed hash values\n");
545 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
546 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
547 for (i = 0; i < NUM_KEYSIZES; i++) {
548 printf("%-18d", hashtest_key_lens[i]);
549 for (j = 0; j < NUM_OPERATIONS; j++)
550 printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]);
558 /* Control operation of performance testing of fbk hash. */
559 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
560 #define TEST_SIZE 1000000 /* How many operations to time. */
561 #define TEST_ITERATIONS 30 /* How many measurements to take. */
562 #define ENTRIES (1 << 15) /* How many entries. */
565 fbk_hash_perf_test(void)
567 struct rte_fbk_hash_params params = {
568 .name = "fbk_hash_test",
570 .entries_per_bucket = 4,
571 .socket_id = rte_socket_id(),
573 struct rte_fbk_hash_table *handle = NULL;
574 uint32_t *keys = NULL;
575 unsigned indexes[TEST_SIZE];
576 uint64_t lookup_time = 0;
583 handle = rte_fbk_hash_create(¶ms);
584 if (handle == NULL) {
585 printf("Error creating table\n");
589 keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
591 printf("fbk hash: memory allocation for key store failed\n");
595 /* Generate random keys and values. */
596 for (i = 0; i < ENTRIES; i++) {
597 key = (uint32_t)rte_rand();
598 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
599 val = (uint16_t)rte_rand();
601 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
605 if (added > (LOAD_FACTOR * ENTRIES))
609 for (i = 0; i < TEST_ITERATIONS; i++) {
613 /* Generate random indexes into keys[] array. */
614 for (j = 0; j < TEST_SIZE; j++)
615 indexes[j] = rte_rand() % added;
619 for (j = 0; j < TEST_SIZE; j++)
620 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
623 lookup_time += (double)(end - begin);
626 printf("\n\n *** FBK Hash function performance test results ***\n");
628 * The use of the 'value' variable ensures that the hash lookup is not
629 * being optimised out by the compiler.
632 printf("Number of ticks per lookup = %g\n",
633 (double)lookup_time /
634 ((double)TEST_ITERATIONS * (double)TEST_SIZE));
636 rte_fbk_hash_free(handle);
644 unsigned with_pushes;
646 for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
647 if (with_pushes == 0)
648 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
650 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
651 if (run_all_tbl_perf_tests(with_pushes) < 0)
654 if (fbk_hash_perf_test() < 0)
660 static struct test_command hash_perf_cmd = {
661 .command = "hash_perf_autotest",
662 .callback = test_hash_perf,
664 REGISTER_TEST_COMMAND(hash_perf_cmd);