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];
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 table_index)
111 char name[RTE_HASH_NAMESIZE];
113 sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
114 ut_params.name = name;
115 ut_params.key_len = hashtest_key_lens[table_index];
116 ut_params.socket_id = rte_socket_id();
117 h[table_index] = rte_hash_find_existing(name);
118 if (h[table_index] != NULL)
120 * If table was already created, free it to create it again,
121 * so we force it is empty
123 rte_hash_free(h[table_index]);
124 h[table_index] = rte_hash_create(&ut_params);
125 if (h[table_index] == NULL) {
126 printf("Error creating table\n");
133 /* Shuffle the keys that have been added, so lookups will be totally random */
135 shuffle_input_keys(unsigned table_index)
139 uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];
140 hash_sig_t temp_signature;
141 int32_t temp_position;
143 for (i = KEYS_TO_ADD - 1; i > 0; i--) {
144 swap_idx = rte_rand() % i;
146 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
147 temp_signature = signatures[i];
148 temp_position = positions[i];
150 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
151 signatures[i] = signatures[swap_idx];
152 positions[i] = positions[swap_idx];
154 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
155 signatures[swap_idx] = temp_signature;
156 positions[swap_idx] = temp_position;
161 * Looks for random keys which
162 * ALL can fit in hash table (no errors)
165 get_input_keys(unsigned with_pushes, unsigned table_index)
168 unsigned bucket_idx, incr, success = 1;
171 const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
173 /* Reset all arrays */
174 for (i = 0; i < MAX_ENTRIES; i++)
177 for (i = 0; i < NUM_BUCKETS; i++)
180 for (j = 0; j < hashtest_key_lens[table_index]; j++)
184 * Add only entries that are not duplicated and that fits in the table
185 * (cannot store more than BUCKET_SIZE entries in a bucket).
186 * Regardless a key has been added correctly or not (success),
187 * the next one to try will be increased by 1.
189 for (i = 0; i < KEYS_TO_ADD;) {
193 /* Overflow, need to increment the next byte */
196 for (j = 1; j < hashtest_key_lens[table_index]; j++) {
197 /* Do not increase next byte */
200 keys[i][j] = keys[i - 1][j];
202 keys[i][j] = keys[i][j];
203 /* Increase next byte by one */
206 keys[i][j] = keys[i-1][j] + 1;
208 keys[i][j] = keys[i][j] + 1;
217 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
218 bucket_idx = signatures[i] & bucket_bitmask;
220 * If we are not inserting keys in secondary location,
221 * when bucket is full, do not try to insert the key
223 if (with_pushes == 0)
224 if (buckets[bucket_idx] == BUCKET_SIZE)
227 /* If key can be added, leave in successful key arrays "keys" */
228 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
231 /* If key is already added, ignore the entry and do not store */
235 /* Store the returned position and mark slot as taken */
237 buckets[bucket_idx]++;
244 /* Reset the table, so we can measure the time to add all the entries */
245 rte_hash_free(h[table_index]);
246 h[table_index] = rte_hash_create(&ut_params);
252 timed_adds(unsigned with_hash, unsigned table_index)
255 const uint64_t start_tsc = rte_rdtsc();
258 for (i = 0; i < KEYS_TO_ADD; i++) {
260 ret = rte_hash_add_key_with_hash(h[table_index],
261 (const void *) keys[i],
264 ret = rte_hash_add_key(h[table_index], keys[i]);
269 printf("Failed to add key number %u\n", ret);
274 const uint64_t end_tsc = rte_rdtsc();
275 const uint64_t time_taken = end_tsc - start_tsc;
277 cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD;
282 timed_lookups(unsigned with_hash, unsigned table_index)
285 const uint64_t start_tsc = rte_rdtsc();
288 for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
289 for (j = 0; j < KEYS_TO_ADD; j++) {
291 ret = rte_hash_lookup_with_hash(h[table_index],
292 (const void *) keys[j],
295 ret = rte_hash_lookup(h[table_index], keys[j]);
296 if (ret < 0 || ret != positions[j]) {
297 printf("Key looked up in %d, should be in %d\n",
304 const uint64_t end_tsc = rte_rdtsc();
305 const uint64_t time_taken = end_tsc - start_tsc;
307 cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;
313 timed_lookups_multi(unsigned table_index)
316 int32_t positions_burst[BURST_SIZE];
317 const void *keys_burst[BURST_SIZE];
318 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/BURST_SIZE; j++) {
322 for (k = 0; k < BURST_SIZE; k++)
323 keys_burst[k] = keys[j * BURST_SIZE + k];
325 rte_hash_lookup_bulk(h[table_index],
326 (const void **) keys_burst,
329 for (k = 0; k < BURST_SIZE; k++) {
330 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
331 printf("Key looked up in %d, should be in %d\n",
333 positions[j * BURST_SIZE + k]);
340 const uint64_t end_tsc = rte_rdtsc();
341 const uint64_t time_taken = end_tsc - start_tsc;
343 cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
349 timed_deletes(unsigned with_hash, unsigned table_index)
352 const uint64_t start_tsc = rte_rdtsc();
355 for (i = 0; i < KEYS_TO_ADD; i++) {
357 ret = rte_hash_del_key_with_hash(h[table_index],
358 (const void *) keys[i],
361 ret = rte_hash_del_key(h[table_index],
362 (const void *) keys[i]);
366 printf("Failed to add key number %u\n", ret);
371 const uint64_t end_tsc = rte_rdtsc();
372 const uint64_t time_taken = end_tsc - start_tsc;
374 cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;
380 free_table(unsigned table_index)
382 rte_hash_free(h[table_index]);
386 reset_table(unsigned table_index)
388 free_table(table_index);
389 if (create_table(table_index) != 0)
396 run_all_tbl_perf_tests(unsigned with_pushes)
398 unsigned i, j, with_hash;
400 printf("Measuring performance, please wait");
402 for (i = 0; i < NUM_KEYSIZES; i++) {
403 if (create_table(i) < 0)
406 if (get_input_keys(with_pushes, i) < 0)
408 for (with_hash = 0; with_hash <= 1; with_hash++) {
409 if (timed_adds(with_hash, i) < 0)
412 for (j = 0; j < NUM_SHUFFLES; j++)
413 shuffle_input_keys(i);
415 if (timed_lookups(with_hash, i) < 0)
418 if (timed_lookups_multi(i) < 0)
421 if (timed_deletes(with_hash, i) < 0)
424 if (reset_table(i) < 0)
427 /* Print a dot to show progress on operations */
435 printf("\nResults (in CPU cycles/operation)\n");
436 printf("---------------------------------\n");
437 printf("\nWithout pre-computed hash values\n");
438 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
439 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
440 for (i = 0; i < NUM_KEYSIZES; i++) {
441 printf("%-18d", hashtest_key_lens[i]);
442 for (j = 0; j < NUM_OPERATIONS; j++)
443 printf("%-18"PRIu64, cycles[i][j][0]);
446 printf("\nWith pre-computed hash values\n");
447 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
448 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
449 for (i = 0; i < NUM_KEYSIZES; i++) {
450 printf("%-18d", hashtest_key_lens[i]);
451 for (j = 0; j < NUM_OPERATIONS; j++)
452 printf("%-18"PRIu64, cycles[i][j][1]);
459 /* Control operation of performance testing of fbk hash. */
460 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
461 #define TEST_SIZE 1000000 /* How many operations to time. */
462 #define TEST_ITERATIONS 30 /* How many measurements to take. */
463 #define ENTRIES (1 << 15) /* How many entries. */
466 fbk_hash_perf_test(void)
468 struct rte_fbk_hash_params params = {
469 .name = "fbk_hash_test",
471 .entries_per_bucket = 4,
472 .socket_id = rte_socket_id(),
474 struct rte_fbk_hash_table *handle = NULL;
475 uint32_t *keys = NULL;
476 unsigned indexes[TEST_SIZE];
477 uint64_t lookup_time = 0;
484 handle = rte_fbk_hash_create(¶ms);
485 if (handle == NULL) {
486 printf("Error creating table\n");
490 keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
492 printf("fbk hash: memory allocation for key store failed\n");
496 /* Generate random keys and values. */
497 for (i = 0; i < ENTRIES; i++) {
498 key = (uint32_t)rte_rand();
499 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
500 val = (uint16_t)rte_rand();
502 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
506 if (added > (LOAD_FACTOR * ENTRIES))
510 for (i = 0; i < TEST_ITERATIONS; i++) {
514 /* Generate random indexes into keys[] array. */
515 for (j = 0; j < TEST_SIZE; j++)
516 indexes[j] = rte_rand() % added;
520 for (j = 0; j < TEST_SIZE; j++)
521 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
524 lookup_time += (double)(end - begin);
527 printf("\n\n *** FBK Hash function performance test results ***\n");
529 * The use of the 'value' variable ensures that the hash lookup is not
530 * being optimised out by the compiler.
533 printf("Number of ticks per lookup = %g\n",
534 (double)lookup_time /
535 ((double)TEST_ITERATIONS * (double)TEST_SIZE));
537 rte_fbk_hash_free(handle);
545 unsigned with_pushes;
547 for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
548 if (with_pushes == 0)
549 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
551 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
552 if (run_all_tbl_perf_tests(with_pushes) < 0)
556 if (fbk_hash_perf_test() < 0)
562 static struct test_command hash_perf_cmd = {
563 .command = "hash_perf_autotest",
564 .callback = test_hash_perf,
566 REGISTER_TEST_COMMAND(hash_perf_cmd);