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 .hash_func
= rte_jhash
,
104 .hash_func_init_val
= 0,
108 create_table(unsigned with_data
, unsigned table_index
)
110 char name
[RTE_HASH_NAMESIZE
];
113 /* Table will store 8-byte data */
114 sprintf(name
, "test_hash%d_data", hashtest_key_lens
[table_index
]);
116 sprintf(name
, "test_hash%d", hashtest_key_lens
[table_index
]);
118 ut_params
.name
= name
;
119 ut_params
.key_len
= hashtest_key_lens
[table_index
];
120 ut_params
.socket_id
= rte_socket_id();
121 h
[table_index
] = rte_hash_find_existing(name
);
122 if (h
[table_index
] != NULL
)
124 * If table was already created, free it to create it again,
125 * so we force it is empty
127 rte_hash_free(h
[table_index
]);
128 h
[table_index
] = rte_hash_create(&ut_params
);
129 if (h
[table_index
] == NULL
) {
130 printf("Error creating table\n");
137 /* Shuffle the keys that have been added, so lookups will be totally random */
139 shuffle_input_keys(unsigned table_index
)
143 uint8_t temp_key
[MAX_KEYSIZE
];
144 hash_sig_t temp_signature
;
145 int32_t temp_position
;
147 for (i
= KEYS_TO_ADD
- 1; i
> 0; i
--) {
148 swap_idx
= rte_rand() % i
;
150 memcpy(temp_key
, keys
[i
], hashtest_key_lens
[table_index
]);
151 temp_signature
= signatures
[i
];
152 temp_position
= positions
[i
];
154 memcpy(keys
[i
], keys
[swap_idx
], hashtest_key_lens
[table_index
]);
155 signatures
[i
] = signatures
[swap_idx
];
156 positions
[i
] = positions
[swap_idx
];
158 memcpy(keys
[swap_idx
], temp_key
, hashtest_key_lens
[table_index
]);
159 signatures
[swap_idx
] = temp_signature
;
160 positions
[swap_idx
] = temp_position
;
165 * Looks for random keys which
166 * ALL can fit in hash table (no errors)
169 get_input_keys(unsigned with_pushes
, unsigned table_index
)
172 unsigned bucket_idx
, incr
, success
= 1;
175 const uint32_t bucket_bitmask
= NUM_BUCKETS
- 1;
177 /* Reset all arrays */
178 for (i
= 0; i
< MAX_ENTRIES
; i
++)
181 for (i
= 0; i
< NUM_BUCKETS
; i
++)
184 for (j
= 0; j
< hashtest_key_lens
[table_index
]; j
++)
188 * Add only entries that are not duplicated and that fits in the table
189 * (cannot store more than BUCKET_SIZE entries in a bucket).
190 * Regardless a key has been added correctly or not (success),
191 * the next one to try will be increased by 1.
193 for (i
= 0; i
< KEYS_TO_ADD
;) {
197 /* Overflow, need to increment the next byte */
200 for (j
= 1; j
< hashtest_key_lens
[table_index
]; j
++) {
201 /* Do not increase next byte */
204 keys
[i
][j
] = keys
[i
- 1][j
];
206 keys
[i
][j
] = keys
[i
][j
];
207 /* Increase next byte by one */
210 keys
[i
][j
] = keys
[i
-1][j
] + 1;
212 keys
[i
][j
] = keys
[i
][j
] + 1;
221 signatures
[i
] = rte_hash_hash(h
[table_index
], keys
[i
]);
222 bucket_idx
= signatures
[i
] & bucket_bitmask
;
224 * If we are not inserting keys in secondary location,
225 * when bucket is full, do not try to insert the key
227 if (with_pushes
== 0)
228 if (buckets
[bucket_idx
] == BUCKET_SIZE
)
231 /* If key can be added, leave in successful key arrays "keys" */
232 ret
= rte_hash_add_key_with_hash(h
[table_index
], keys
[i
],
235 /* If key is already added, ignore the entry and do not store */
239 /* Store the returned position and mark slot as taken */
242 buckets
[bucket_idx
]++;
249 /* Reset the table, so we can measure the time to add all the entries */
250 rte_hash_free(h
[table_index
]);
251 h
[table_index
] = rte_hash_create(&ut_params
);
257 timed_adds(unsigned with_hash
, unsigned with_data
, unsigned table_index
)
260 const uint64_t start_tsc
= rte_rdtsc();
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("Failed to add key number %u\n", ret
);
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("Failed to add key number %u\n", ret
);
284 } else if (!with_hash
&& with_data
) {
285 ret
= rte_hash_add_key_data(h
[table_index
],
286 (const void *) keys
[i
],
289 printf("Failed to add key number %u\n", ret
);
293 ret
= rte_hash_add_key(h
[table_index
], keys
[i
]);
297 printf("Failed to add key number %u\n", ret
);
303 const uint64_t end_tsc
= rte_rdtsc();
304 const uint64_t time_taken
= end_tsc
- start_tsc
;
306 cycles
[table_index
][ADD
][with_hash
][with_data
] = time_taken
/KEYS_TO_ADD
;
312 timed_lookups(unsigned with_hash
, unsigned with_data
, unsigned table_index
)
315 const uint64_t start_tsc
= rte_rdtsc();
320 for (i
= 0; i
< NUM_LOOKUPS
/KEYS_TO_ADD
; i
++) {
321 for (j
= 0; j
< KEYS_TO_ADD
; j
++) {
322 if (with_hash
&& with_data
) {
323 ret
= rte_hash_lookup_with_hash_data(h
[table_index
],
324 (const void *) keys
[j
],
325 signatures
[j
], &ret_data
);
327 printf("Key number %u was not found\n", j
);
330 expected_data
= (void *) ((uintptr_t) signatures
[j
]);
331 if (ret_data
!= expected_data
) {
332 printf("Data returned for key number %u is %p,"
333 " but should be %p\n", j
, ret_data
,
337 } else if (with_hash
&& !with_data
) {
338 ret
= rte_hash_lookup_with_hash(h
[table_index
],
339 (const void *) keys
[j
],
341 if (ret
< 0 || ret
!= positions
[j
]) {
342 printf("Key looked up in %d, should be in %d\n",
346 } else if (!with_hash
&& with_data
) {
347 ret
= rte_hash_lookup_data(h
[table_index
],
348 (const void *) keys
[j
], &ret_data
);
350 printf("Key number %u was not found\n", j
);
353 expected_data
= (void *) ((uintptr_t) signatures
[j
]);
354 if (ret_data
!= expected_data
) {
355 printf("Data returned for key number %u is %p,"
356 " but should be %p\n", j
, ret_data
,
361 ret
= rte_hash_lookup(h
[table_index
], keys
[j
]);
362 if (ret
< 0 || ret
!= positions
[j
]) {
363 printf("Key looked up in %d, should be in %d\n",
371 const uint64_t end_tsc
= rte_rdtsc();
372 const uint64_t time_taken
= end_tsc
- start_tsc
;
374 cycles
[table_index
][LOOKUP
][with_hash
][with_data
] = time_taken
/NUM_LOOKUPS
;
380 timed_lookups_multi(unsigned with_data
, unsigned table_index
)
383 int32_t positions_burst
[BURST_SIZE
];
384 const void *keys_burst
[BURST_SIZE
];
385 void *expected_data
[BURST_SIZE
];
386 void *ret_data
[BURST_SIZE
];
390 const uint64_t start_tsc
= rte_rdtsc();
392 for (i
= 0; i
< NUM_LOOKUPS
/KEYS_TO_ADD
; i
++) {
393 for (j
= 0; j
< KEYS_TO_ADD
/BURST_SIZE
; j
++) {
394 for (k
= 0; k
< BURST_SIZE
; k
++)
395 keys_burst
[k
] = keys
[j
* BURST_SIZE
+ k
];
397 ret
= rte_hash_lookup_bulk_data(h
[table_index
],
398 (const void **) keys_burst
,
402 if (ret
!= BURST_SIZE
) {
403 printf("Expect to find %u keys,"
404 " but found %d\n", BURST_SIZE
, ret
);
407 for (k
= 0; k
< BURST_SIZE
; k
++) {
408 if ((hit_mask
& (1ULL << k
)) == 0) {
409 printf("Key number %u not found\n",
413 expected_data
[k
] = (void *) ((uintptr_t) signatures
[j
* BURST_SIZE
+ k
]);
414 if (ret_data
[k
] != expected_data
[k
]) {
415 printf("Data returned for key number %u is %p,"
416 " but should be %p\n", j
* BURST_SIZE
+ k
,
417 ret_data
[k
], expected_data
[k
]);
422 rte_hash_lookup_bulk(h
[table_index
],
423 (const void **) keys_burst
,
426 for (k
= 0; k
< BURST_SIZE
; k
++) {
427 if (positions_burst
[k
] != positions
[j
* BURST_SIZE
+ k
]) {
428 printf("Key looked up in %d, should be in %d\n",
430 positions
[j
* BURST_SIZE
+ k
]);
438 const uint64_t end_tsc
= rte_rdtsc();
439 const uint64_t time_taken
= end_tsc
- start_tsc
;
441 cycles
[table_index
][LOOKUP_MULTI
][0][with_data
] = time_taken
/NUM_LOOKUPS
;
447 timed_deletes(unsigned with_hash
, unsigned with_data
, unsigned table_index
)
450 const uint64_t start_tsc
= rte_rdtsc();
453 for (i
= 0; i
< KEYS_TO_ADD
; i
++) {
454 /* There are no delete functions with data, so just call two functions */
456 ret
= rte_hash_del_key_with_hash(h
[table_index
],
457 (const void *) keys
[i
],
460 ret
= rte_hash_del_key(h
[table_index
],
461 (const void *) keys
[i
]);
465 printf("Failed to add key number %u\n", ret
);
470 const uint64_t end_tsc
= rte_rdtsc();
471 const uint64_t time_taken
= end_tsc
- start_tsc
;
473 cycles
[table_index
][DELETE
][with_hash
][with_data
] = time_taken
/KEYS_TO_ADD
;
479 free_table(unsigned table_index
)
481 rte_hash_free(h
[table_index
]);
485 reset_table(unsigned table_index
)
487 rte_hash_reset(h
[table_index
]);
491 run_all_tbl_perf_tests(unsigned with_pushes
)
493 unsigned i
, j
, with_data
, with_hash
;
495 printf("Measuring performance, please wait");
498 for (with_data
= 0; with_data
<= 1; with_data
++) {
499 for (i
= 0; i
< NUM_KEYSIZES
; i
++) {
500 if (create_table(with_data
, i
) < 0)
503 if (get_input_keys(with_pushes
, i
) < 0)
505 for (with_hash
= 0; with_hash
<= 1; with_hash
++) {
506 if (timed_adds(with_hash
, with_data
, i
) < 0)
509 for (j
= 0; j
< NUM_SHUFFLES
; j
++)
510 shuffle_input_keys(i
);
512 if (timed_lookups(with_hash
, with_data
, i
) < 0)
515 if (timed_lookups_multi(with_data
, i
) < 0)
518 if (timed_deletes(with_hash
, with_data
, i
) < 0)
521 /* Print a dot to show progress on operations */
531 printf("\nResults (in CPU cycles/operation)\n");
532 printf("-----------------------------------\n");
533 for (with_data
= 0; with_data
<= 1; with_data
++) {
535 printf("\n Operations with 8-byte data\n");
537 printf("\n Operations without data\n");
538 for (with_hash
= 0; with_hash
<= 1; with_hash
++) {
540 printf("\nWith pre-computed hash values\n");
542 printf("\nWithout pre-computed hash values\n");
544 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
545 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
546 for (i
= 0; i
< NUM_KEYSIZES
; i
++) {
547 printf("%-18d", hashtest_key_lens
[i
]);
548 for (j
= 0; j
< NUM_OPERATIONS
; j
++)
549 printf("%-18"PRIu64
, cycles
[i
][j
][with_hash
][with_data
]);
557 /* Control operation of performance testing of fbk hash. */
558 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
559 #define TEST_SIZE 1000000 /* How many operations to time. */
560 #define TEST_ITERATIONS 30 /* How many measurements to take. */
561 #define ENTRIES (1 << 15) /* How many entries. */
564 fbk_hash_perf_test(void)
566 struct rte_fbk_hash_params params
= {
567 .name
= "fbk_hash_test",
569 .entries_per_bucket
= 4,
570 .socket_id
= rte_socket_id(),
572 struct rte_fbk_hash_table
*handle
= NULL
;
573 uint32_t *keys
= NULL
;
574 unsigned indexes
[TEST_SIZE
];
575 uint64_t lookup_time
= 0;
582 handle
= rte_fbk_hash_create(¶ms
);
583 if (handle
== NULL
) {
584 printf("Error creating table\n");
588 keys
= rte_zmalloc(NULL
, ENTRIES
* sizeof(*keys
), 0);
590 printf("fbk hash: memory allocation for key store failed\n");
594 /* Generate random keys and values. */
595 for (i
= 0; i
< ENTRIES
; i
++) {
596 key
= (uint32_t)rte_rand();
597 key
= ((uint64_t)key
<< 32) | (uint64_t)rte_rand();
598 val
= (uint16_t)rte_rand();
600 if (rte_fbk_hash_add_key(handle
, key
, val
) == 0) {
604 if (added
> (LOAD_FACTOR
* ENTRIES
))
608 for (i
= 0; i
< TEST_ITERATIONS
; i
++) {
612 /* Generate random indexes into keys[] array. */
613 for (j
= 0; j
< TEST_SIZE
; j
++)
614 indexes
[j
] = rte_rand() % added
;
618 for (j
= 0; j
< TEST_SIZE
; j
++)
619 value
+= rte_fbk_hash_lookup(handle
, keys
[indexes
[j
]]);
622 lookup_time
+= (double)(end
- begin
);
625 printf("\n\n *** FBK Hash function performance test results ***\n");
627 * The use of the 'value' variable ensures that the hash lookup is not
628 * being optimised out by the compiler.
631 printf("Number of ticks per lookup = %g\n",
632 (double)lookup_time
/
633 ((double)TEST_ITERATIONS
* (double)TEST_SIZE
));
635 rte_fbk_hash_free(handle
);
643 unsigned with_pushes
;
645 for (with_pushes
= 0; with_pushes
<= 1; with_pushes
++) {
646 if (with_pushes
== 0)
647 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
649 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
650 if (run_all_tbl_perf_tests(with_pushes
) < 0)
653 if (fbk_hash_perf_test() < 0)
659 REGISTER_TEST_COMMAND(hash_perf_autotest
, test_hash_perf
);