]> git.proxmox.com Git - ceph.git/blob - ceph/src/spdk/dpdk/test/test/test_hash_perf.c
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
update download target update for octopus release
[ceph.git] / ceph / src / spdk / dpdk / test / test / test_hash_perf.c
1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2015 Intel Corporation
3 */
4
5 #include <stdio.h>
6 #include <inttypes.h>
7
8 #include <rte_lcore.h>
9 #include <rte_cycles.h>
10 #include <rte_malloc.h>
11 #include <rte_hash.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>
17
18 #include "test.h"
19
20 #define MAX_ENTRIES (1 << 19)
21 #define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */
22 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
23 #define BUCKET_SIZE 4
24 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
25 #define MAX_KEYSIZE 64
26 #define NUM_KEYSIZES 10
27 #define NUM_SHUFFLES 10
28 #define BURST_SIZE 16
29
30 enum operations {
31 ADD = 0,
32 LOOKUP,
33 LOOKUP_MULTI,
34 DELETE,
35 NUM_OPERATIONS
36 };
37
38 static uint32_t hashtest_key_lens[] = {
39 /* standard key sizes */
40 4, 8, 16, 32, 48, 64,
41 /* IPv4 SRC + DST + protocol, unpadded */
42 9,
43 /* IPv4 5-tuple, unpadded */
44 13,
45 /* IPv6 5-tuple, unpadded */
46 37,
47 /* IPv6 5-tuple, padded to 8-byte boundary */
48 40
49 };
50
51 struct rte_hash *h[NUM_KEYSIZES];
52
53 /* Array that stores if a slot is full */
54 uint8_t slot_taken[MAX_ENTRIES];
55
56 /* Array to store number of cycles per operation */
57 uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
58
59 /* Array to store all input keys */
60 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
61
62 /* Array to store the precomputed hash for 'keys' */
63 hash_sig_t signatures[KEYS_TO_ADD];
64
65 /* Array to store how many busy entries have each bucket */
66 uint8_t buckets[NUM_BUCKETS];
67
68 /* Array to store the positions where keys are added */
69 int32_t positions[KEYS_TO_ADD];
70
71 /* Parameters used for hash table in unit test functions. */
72 static struct rte_hash_parameters ut_params = {
73 .entries = MAX_ENTRIES,
74 .hash_func = rte_jhash,
75 .hash_func_init_val = 0,
76 };
77
78 static int
79 create_table(unsigned int with_data, unsigned int table_index,
80 unsigned int with_locks)
81 {
82 char name[RTE_HASH_NAMESIZE];
83
84 if (with_data)
85 /* Table will store 8-byte data */
86 sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]);
87 else
88 sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
89
90
91 if (with_locks)
92 ut_params.extra_flag =
93 RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT
94 | RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY;
95 else
96 ut_params.extra_flag = 0;
97
98 ut_params.name = name;
99 ut_params.key_len = hashtest_key_lens[table_index];
100 ut_params.socket_id = rte_socket_id();
101 h[table_index] = rte_hash_find_existing(name);
102 if (h[table_index] != NULL)
103 /*
104 * If table was already created, free it to create it again,
105 * so we force it is empty
106 */
107 rte_hash_free(h[table_index]);
108 h[table_index] = rte_hash_create(&ut_params);
109 if (h[table_index] == NULL) {
110 printf("Error creating table\n");
111 return -1;
112 }
113 return 0;
114
115 }
116
117 /* Shuffle the keys that have been added, so lookups will be totally random */
118 static void
119 shuffle_input_keys(unsigned table_index)
120 {
121 unsigned i;
122 uint32_t swap_idx;
123 uint8_t temp_key[MAX_KEYSIZE];
124 hash_sig_t temp_signature;
125 int32_t temp_position;
126
127 for (i = KEYS_TO_ADD - 1; i > 0; i--) {
128 swap_idx = rte_rand() % i;
129
130 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
131 temp_signature = signatures[i];
132 temp_position = positions[i];
133
134 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
135 signatures[i] = signatures[swap_idx];
136 positions[i] = positions[swap_idx];
137
138 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
139 signatures[swap_idx] = temp_signature;
140 positions[swap_idx] = temp_position;
141 }
142 }
143
144 /*
145 * Looks for random keys which
146 * ALL can fit in hash table (no errors)
147 */
148 static int
149 get_input_keys(unsigned with_pushes, unsigned table_index)
150 {
151 unsigned i, j;
152 unsigned bucket_idx, incr, success = 1;
153 uint8_t k = 0;
154 int32_t ret;
155 const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
156
157 /* Reset all arrays */
158 for (i = 0; i < MAX_ENTRIES; i++)
159 slot_taken[i] = 0;
160
161 for (i = 0; i < NUM_BUCKETS; i++)
162 buckets[i] = 0;
163
164 for (j = 0; j < hashtest_key_lens[table_index]; j++)
165 keys[0][j] = 0;
166
167 /*
168 * Add only entries that are not duplicated and that fits in the table
169 * (cannot store more than BUCKET_SIZE entries in a bucket).
170 * Regardless a key has been added correctly or not (success),
171 * the next one to try will be increased by 1.
172 */
173 for (i = 0; i < KEYS_TO_ADD;) {
174 incr = 0;
175 if (i != 0) {
176 keys[i][0] = ++k;
177 /* Overflow, need to increment the next byte */
178 if (keys[i][0] == 0)
179 incr = 1;
180 for (j = 1; j < hashtest_key_lens[table_index]; j++) {
181 /* Do not increase next byte */
182 if (incr == 0)
183 if (success == 1)
184 keys[i][j] = keys[i - 1][j];
185 else
186 keys[i][j] = keys[i][j];
187 /* Increase next byte by one */
188 else {
189 if (success == 1)
190 keys[i][j] = keys[i-1][j] + 1;
191 else
192 keys[i][j] = keys[i][j] + 1;
193 if (keys[i][j] == 0)
194 incr = 1;
195 else
196 incr = 0;
197 }
198 }
199 }
200 success = 0;
201 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
202 bucket_idx = signatures[i] & bucket_bitmask;
203 /*
204 * If we are not inserting keys in secondary location,
205 * when bucket is full, do not try to insert the key
206 */
207 if (with_pushes == 0)
208 if (buckets[bucket_idx] == BUCKET_SIZE)
209 continue;
210
211 /* If key can be added, leave in successful key arrays "keys" */
212 ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
213 signatures[i]);
214 if (ret >= 0) {
215 /* If key is already added, ignore the entry and do not store */
216 if (slot_taken[ret])
217 continue;
218 else {
219 /* Store the returned position and mark slot as taken */
220 slot_taken[ret] = 1;
221 positions[i] = ret;
222 buckets[bucket_idx]++;
223 success = 1;
224 i++;
225 }
226 }
227 }
228
229 /* Reset the table, so we can measure the time to add all the entries */
230 rte_hash_free(h[table_index]);
231 h[table_index] = rte_hash_create(&ut_params);
232
233 return 0;
234 }
235
236 static int
237 timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
238 {
239 unsigned i;
240 const uint64_t start_tsc = rte_rdtsc();
241 void *data;
242 int32_t ret;
243
244 for (i = 0; i < KEYS_TO_ADD; i++) {
245 data = (void *) ((uintptr_t) signatures[i]);
246 if (with_hash && with_data) {
247 ret = rte_hash_add_key_with_hash_data(h[table_index],
248 (const void *) keys[i],
249 signatures[i], data);
250 if (ret < 0) {
251 printf("Failed to add key number %u\n", ret);
252 return -1;
253 }
254 } else if (with_hash && !with_data) {
255 ret = rte_hash_add_key_with_hash(h[table_index],
256 (const void *) keys[i],
257 signatures[i]);
258 if (ret >= 0)
259 positions[i] = ret;
260 else {
261 printf("Failed to add key number %u\n", ret);
262 return -1;
263 }
264 } else if (!with_hash && with_data) {
265 ret = rte_hash_add_key_data(h[table_index],
266 (const void *) keys[i],
267 data);
268 if (ret < 0) {
269 printf("Failed to add key number %u\n", ret);
270 return -1;
271 }
272 } else {
273 ret = rte_hash_add_key(h[table_index], keys[i]);
274 if (ret >= 0)
275 positions[i] = ret;
276 else {
277 printf("Failed to add key number %u\n", ret);
278 return -1;
279 }
280 }
281 }
282
283 const uint64_t end_tsc = rte_rdtsc();
284 const uint64_t time_taken = end_tsc - start_tsc;
285
286 cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD;
287
288 return 0;
289 }
290
291 static int
292 timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
293 {
294 unsigned i, j;
295 const uint64_t start_tsc = rte_rdtsc();
296 void *ret_data;
297 void *expected_data;
298 int32_t ret;
299
300 for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
301 for (j = 0; j < KEYS_TO_ADD; j++) {
302 if (with_hash && with_data) {
303 ret = rte_hash_lookup_with_hash_data(h[table_index],
304 (const void *) keys[j],
305 signatures[j], &ret_data);
306 if (ret < 0) {
307 printf("Key number %u was not found\n", j);
308 return -1;
309 }
310 expected_data = (void *) ((uintptr_t) signatures[j]);
311 if (ret_data != expected_data) {
312 printf("Data returned for key number %u is %p,"
313 " but should be %p\n", j, ret_data,
314 expected_data);
315 return -1;
316 }
317 } else if (with_hash && !with_data) {
318 ret = rte_hash_lookup_with_hash(h[table_index],
319 (const void *) keys[j],
320 signatures[j]);
321 if (ret < 0 || ret != positions[j]) {
322 printf("Key looked up in %d, should be in %d\n",
323 ret, positions[j]);
324 return -1;
325 }
326 } else if (!with_hash && with_data) {
327 ret = rte_hash_lookup_data(h[table_index],
328 (const void *) keys[j], &ret_data);
329 if (ret < 0) {
330 printf("Key number %u was not found\n", j);
331 return -1;
332 }
333 expected_data = (void *) ((uintptr_t) signatures[j]);
334 if (ret_data != expected_data) {
335 printf("Data returned for key number %u is %p,"
336 " but should be %p\n", j, ret_data,
337 expected_data);
338 return -1;
339 }
340 } else {
341 ret = rte_hash_lookup(h[table_index], keys[j]);
342 if (ret < 0 || ret != positions[j]) {
343 printf("Key looked up in %d, should be in %d\n",
344 ret, positions[j]);
345 return -1;
346 }
347 }
348 }
349 }
350
351 const uint64_t end_tsc = rte_rdtsc();
352 const uint64_t time_taken = end_tsc - start_tsc;
353
354 cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS;
355
356 return 0;
357 }
358
359 static int
360 timed_lookups_multi(unsigned with_data, unsigned table_index)
361 {
362 unsigned i, j, k;
363 int32_t positions_burst[BURST_SIZE];
364 const void *keys_burst[BURST_SIZE];
365 void *expected_data[BURST_SIZE];
366 void *ret_data[BURST_SIZE];
367 uint64_t hit_mask;
368 int ret;
369
370 const uint64_t start_tsc = rte_rdtsc();
371
372 for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
373 for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
374 for (k = 0; k < BURST_SIZE; k++)
375 keys_burst[k] = keys[j * BURST_SIZE + k];
376 if (with_data) {
377 ret = rte_hash_lookup_bulk_data(h[table_index],
378 (const void **) keys_burst,
379 BURST_SIZE,
380 &hit_mask,
381 ret_data);
382 if (ret != BURST_SIZE) {
383 printf("Expect to find %u keys,"
384 " but found %d\n", BURST_SIZE, ret);
385 return -1;
386 }
387 for (k = 0; k < BURST_SIZE; k++) {
388 if ((hit_mask & (1ULL << k)) == 0) {
389 printf("Key number %u not found\n",
390 j * BURST_SIZE + k);
391 return -1;
392 }
393 expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]);
394 if (ret_data[k] != expected_data[k]) {
395 printf("Data returned for key number %u is %p,"
396 " but should be %p\n", j * BURST_SIZE + k,
397 ret_data[k], expected_data[k]);
398 return -1;
399 }
400 }
401 } else {
402 rte_hash_lookup_bulk(h[table_index],
403 (const void **) keys_burst,
404 BURST_SIZE,
405 positions_burst);
406 for (k = 0; k < BURST_SIZE; k++) {
407 if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
408 printf("Key looked up in %d, should be in %d\n",
409 positions_burst[k],
410 positions[j * BURST_SIZE + k]);
411 return -1;
412 }
413 }
414 }
415 }
416 }
417
418 const uint64_t end_tsc = rte_rdtsc();
419 const uint64_t time_taken = end_tsc - start_tsc;
420
421 cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS;
422
423 return 0;
424 }
425
426 static int
427 timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
428 {
429 unsigned i;
430 const uint64_t start_tsc = rte_rdtsc();
431 int32_t ret;
432
433 for (i = 0; i < KEYS_TO_ADD; i++) {
434 /* There are no delete functions with data, so just call two functions */
435 if (with_hash)
436 ret = rte_hash_del_key_with_hash(h[table_index],
437 (const void *) keys[i],
438 signatures[i]);
439 else
440 ret = rte_hash_del_key(h[table_index],
441 (const void *) keys[i]);
442 if (ret >= 0)
443 positions[i] = ret;
444 else {
445 printf("Failed to add key number %u\n", ret);
446 return -1;
447 }
448 }
449
450 const uint64_t end_tsc = rte_rdtsc();
451 const uint64_t time_taken = end_tsc - start_tsc;
452
453 cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD;
454
455 return 0;
456 }
457
458 static void
459 free_table(unsigned table_index)
460 {
461 rte_hash_free(h[table_index]);
462 }
463
464 static void
465 reset_table(unsigned table_index)
466 {
467 rte_hash_reset(h[table_index]);
468 }
469
470 static int
471 run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks)
472 {
473 unsigned i, j, with_data, with_hash;
474
475 printf("Measuring performance, please wait");
476 fflush(stdout);
477
478 for (with_data = 0; with_data <= 1; with_data++) {
479 for (i = 0; i < NUM_KEYSIZES; i++) {
480 if (create_table(with_data, i, with_locks) < 0)
481 return -1;
482
483 if (get_input_keys(with_pushes, i) < 0)
484 return -1;
485 for (with_hash = 0; with_hash <= 1; with_hash++) {
486 if (timed_adds(with_hash, with_data, i) < 0)
487 return -1;
488
489 for (j = 0; j < NUM_SHUFFLES; j++)
490 shuffle_input_keys(i);
491
492 if (timed_lookups(with_hash, with_data, i) < 0)
493 return -1;
494
495 if (timed_lookups_multi(with_data, i) < 0)
496 return -1;
497
498 if (timed_deletes(with_hash, with_data, i) < 0)
499 return -1;
500
501 /* Print a dot to show progress on operations */
502 printf(".");
503 fflush(stdout);
504
505 reset_table(i);
506 }
507 free_table(i);
508 }
509 }
510
511 printf("\nResults (in CPU cycles/operation)\n");
512 printf("-----------------------------------\n");
513 for (with_data = 0; with_data <= 1; with_data++) {
514 if (with_data)
515 printf("\n Operations with 8-byte data\n");
516 else
517 printf("\n Operations without data\n");
518 for (with_hash = 0; with_hash <= 1; with_hash++) {
519 if (with_hash)
520 printf("\nWith pre-computed hash values\n");
521 else
522 printf("\nWithout pre-computed hash values\n");
523
524 printf("\n%-18s%-18s%-18s%-18s%-18s\n",
525 "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
526 for (i = 0; i < NUM_KEYSIZES; i++) {
527 printf("%-18d", hashtest_key_lens[i]);
528 for (j = 0; j < NUM_OPERATIONS; j++)
529 printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]);
530 printf("\n");
531 }
532 }
533 }
534 return 0;
535 }
536
537 /* Control operation of performance testing of fbk hash. */
538 #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
539 #define TEST_SIZE 1000000 /* How many operations to time. */
540 #define TEST_ITERATIONS 30 /* How many measurements to take. */
541 #define ENTRIES (1 << 15) /* How many entries. */
542
543 static int
544 fbk_hash_perf_test(void)
545 {
546 struct rte_fbk_hash_params params = {
547 .name = "fbk_hash_test",
548 .entries = ENTRIES,
549 .entries_per_bucket = 4,
550 .socket_id = rte_socket_id(),
551 };
552 struct rte_fbk_hash_table *handle = NULL;
553 uint32_t *keys = NULL;
554 unsigned indexes[TEST_SIZE];
555 uint64_t lookup_time = 0;
556 unsigned added = 0;
557 unsigned value = 0;
558 uint32_t key;
559 uint16_t val;
560 unsigned i, j;
561
562 handle = rte_fbk_hash_create(&params);
563 if (handle == NULL) {
564 printf("Error creating table\n");
565 return -1;
566 }
567
568 keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
569 if (keys == NULL) {
570 printf("fbk hash: memory allocation for key store failed\n");
571 return -1;
572 }
573
574 /* Generate random keys and values. */
575 for (i = 0; i < ENTRIES; i++) {
576 key = (uint32_t)rte_rand();
577 key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
578 val = (uint16_t)rte_rand();
579
580 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
581 keys[added] = key;
582 added++;
583 }
584 if (added > (LOAD_FACTOR * ENTRIES))
585 break;
586 }
587
588 for (i = 0; i < TEST_ITERATIONS; i++) {
589 uint64_t begin;
590 uint64_t end;
591
592 /* Generate random indexes into keys[] array. */
593 for (j = 0; j < TEST_SIZE; j++)
594 indexes[j] = rte_rand() % added;
595
596 begin = rte_rdtsc();
597 /* Do lookups */
598 for (j = 0; j < TEST_SIZE; j++)
599 value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
600
601 end = rte_rdtsc();
602 lookup_time += (double)(end - begin);
603 }
604
605 printf("\n\n *** FBK Hash function performance test results ***\n");
606 /*
607 * The use of the 'value' variable ensures that the hash lookup is not
608 * being optimised out by the compiler.
609 */
610 if (value != 0)
611 printf("Number of ticks per lookup = %g\n",
612 (double)lookup_time /
613 ((double)TEST_ITERATIONS * (double)TEST_SIZE));
614
615 rte_fbk_hash_free(handle);
616
617 return 0;
618 }
619
620 static int
621 test_hash_perf(void)
622 {
623 unsigned int with_pushes, with_locks;
624 for (with_locks = 0; with_locks <= 1; with_locks++) {
625 if (with_locks)
626 printf("\nWith locks in the code\n");
627 else
628 printf("\nWithout locks in the code\n");
629 for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
630 if (with_pushes == 0)
631 printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
632 else
633 printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
634 if (run_all_tbl_perf_tests(with_pushes, with_locks) < 0)
635 return -1;
636 }
637 }
638 if (fbk_hash_perf_test() < 0)
639 return -1;
640
641 return 0;
642 }
643
644 REGISTER_TEST_COMMAND(hash_perf_autotest, test_hash_perf);
Ceph