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