mk: optimize directory dependencies
[dpdk.git] / test / test / test_hash_perf.c
1 /*-
2  *   BSD LICENSE
3  *
4  *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  *
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  *
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
16  *       distribution.
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.
20  *
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.
32  */
33
34 #include <stdio.h>
35 #include <inttypes.h>
36
37 #include <rte_lcore.h>
38 #include <rte_cycles.h>
39 #include <rte_malloc.h>
40 #include <rte_hash.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>
46
47 #include "test.h"
48
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 */
52 #define BUCKET_SIZE 4
53 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
54 #define MAX_KEYSIZE 64
55 #define NUM_KEYSIZES 10
56 #define NUM_SHUFFLES 10
57 #define BURST_SIZE 16
58
59 enum operations {
60         ADD = 0,
61         LOOKUP,
62         LOOKUP_MULTI,
63         DELETE,
64         NUM_OPERATIONS
65 };
66
67 static uint32_t hashtest_key_lens[] = {
68         /* standard key sizes */
69         4, 8, 16, 32, 48, 64,
70         /* IPv4 SRC + DST + protocol, unpadded */
71         9,
72         /* IPv4 5-tuple, unpadded */
73         13,
74         /* IPv6 5-tuple, unpadded */
75         37,
76         /* IPv6 5-tuple, padded to 8-byte boundary */
77         40
78 };
79
80 struct rte_hash *h[NUM_KEYSIZES];
81
82 /* Array that stores if a slot is full */
83 uint8_t slot_taken[MAX_ENTRIES];
84
85 /* Array to store number of cycles per operation */
86 uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
87
88 /* Array to store all input keys */
89 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
90
91 /* Array to store the precomputed hash for 'keys' */
92 hash_sig_t signatures[KEYS_TO_ADD];
93
94 /* Array to store how many busy entries have each bucket */
95 uint8_t buckets[NUM_BUCKETS];
96
97 /* Array to store the positions where keys are added */
98 int32_t positions[KEYS_TO_ADD];
99
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,
105 };
106
107 static int
108 create_table(unsigned with_data, unsigned table_index)
109 {
110         char name[RTE_HASH_NAMESIZE];
111
112         if (with_data)
113                 /* Table will store 8-byte data */
114                 sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]);
115         else
116                 sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
117
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)
123                 /*
124                  * If table was already created, free it to create it again,
125                  * so we force it is empty
126                  */
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");
131                 return -1;
132         }
133         return 0;
134
135 }
136
137 /* Shuffle the keys that have been added, so lookups will be totally random */
138 static void
139 shuffle_input_keys(unsigned table_index)
140 {
141         unsigned i;
142         uint32_t swap_idx;
143         uint8_t temp_key[MAX_KEYSIZE];
144         hash_sig_t temp_signature;
145         int32_t temp_position;
146
147         for (i = KEYS_TO_ADD - 1; i > 0; i--) {
148                 swap_idx = rte_rand() % i;
149
150                 memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
151                 temp_signature = signatures[i];
152                 temp_position = positions[i];
153
154                 memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
155                 signatures[i] = signatures[swap_idx];
156                 positions[i] = positions[swap_idx];
157
158                 memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
159                 signatures[swap_idx] = temp_signature;
160                 positions[swap_idx] = temp_position;
161         }
162 }
163
164 /*
165  * Looks for random keys which
166  * ALL can fit in hash table (no errors)
167  */
168 static int
169 get_input_keys(unsigned with_pushes, unsigned table_index)
170 {
171         unsigned i, j;
172         unsigned bucket_idx, incr, success = 1;
173         uint8_t k = 0;
174         int32_t ret;
175         const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
176
177         /* Reset all arrays */
178         for (i = 0; i < MAX_ENTRIES; i++)
179                 slot_taken[i] = 0;
180
181         for (i = 0; i < NUM_BUCKETS; i++)
182                 buckets[i] = 0;
183
184         for (j = 0; j < hashtest_key_lens[table_index]; j++)
185                 keys[0][j] = 0;
186
187         /*
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.
192          */
193         for (i = 0; i < KEYS_TO_ADD;) {
194                 incr = 0;
195                 if (i != 0) {
196                         keys[i][0] = ++k;
197                         /* Overflow, need to increment the next byte */
198                         if (keys[i][0] == 0)
199                                 incr = 1;
200                         for (j = 1; j < hashtest_key_lens[table_index]; j++) {
201                                 /* Do not increase next byte */
202                                 if (incr == 0)
203                                         if (success == 1)
204                                                 keys[i][j] = keys[i - 1][j];
205                                         else
206                                                 keys[i][j] = keys[i][j];
207                                 /* Increase next byte by one */
208                                 else {
209                                         if (success == 1)
210                                                 keys[i][j] = keys[i-1][j] + 1;
211                                         else
212                                                 keys[i][j] = keys[i][j] + 1;
213                                         if (keys[i][j] == 0)
214                                                 incr = 1;
215                                         else
216                                                 incr = 0;
217                                 }
218                         }
219                 }
220                 success = 0;
221                 signatures[i] = rte_hash_hash(h[table_index], keys[i]);
222                 bucket_idx = signatures[i] & bucket_bitmask;
223                 /*
224                  * If we are not inserting keys in secondary location,
225                  * when bucket is full, do not try to insert the key
226                  */
227                 if (with_pushes == 0)
228                         if (buckets[bucket_idx] == BUCKET_SIZE)
229                                 continue;
230
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],
233                                                 signatures[i]);
234                 if (ret >= 0) {
235                         /* If key is already added, ignore the entry and do not store */
236                         if (slot_taken[ret])
237                                 continue;
238                         else {
239                                 /* Store the returned position and mark slot as taken */
240                                 slot_taken[ret] = 1;
241                                 positions[i] = ret;
242                                 buckets[bucket_idx]++;
243                                 success = 1;
244                                 i++;
245                         }
246                 }
247         }
248
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);
252
253         return 0;
254 }
255
256 static int
257 timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
258 {
259         unsigned i;
260         const uint64_t start_tsc = rte_rdtsc();
261         void *data;
262         int32_t ret;
263
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);
270                         if (ret < 0) {
271                                 printf("Failed to add key number %u\n", ret);
272                                 return -1;
273                         }
274                 } else if (with_hash && !with_data) {
275                         ret = rte_hash_add_key_with_hash(h[table_index],
276                                                 (const void *) keys[i],
277                                                 signatures[i]);
278                         if (ret >= 0)
279                                 positions[i] = ret;
280                         else {
281                                 printf("Failed to add key number %u\n", ret);
282                                 return -1;
283                         }
284                 } else if (!with_hash && with_data) {
285                         ret = rte_hash_add_key_data(h[table_index],
286                                                 (const void *) keys[i],
287                                                 data);
288                         if (ret < 0) {
289                                 printf("Failed to add key number %u\n", ret);
290                                 return -1;
291                         }
292                 } else {
293                         ret = rte_hash_add_key(h[table_index], keys[i]);
294                         if (ret >= 0)
295                                 positions[i] = ret;
296                         else {
297                                 printf("Failed to add key number %u\n", ret);
298                                 return -1;
299                         }
300                 }
301         }
302
303         const uint64_t end_tsc = rte_rdtsc();
304         const uint64_t time_taken = end_tsc - start_tsc;
305
306         cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD;
307
308         return 0;
309 }
310
311 static int
312 timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
313 {
314         unsigned i, j;
315         const uint64_t start_tsc = rte_rdtsc();
316         void *ret_data;
317         void *expected_data;
318         int32_t ret;
319
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);
326                                 if (ret < 0) {
327                                         printf("Key number %u was not found\n", j);
328                                         return -1;
329                                 }
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,
334                                                 expected_data);
335                                         return -1;
336                                 }
337                         } else if (with_hash && !with_data) {
338                                 ret = rte_hash_lookup_with_hash(h[table_index],
339                                                         (const void *) keys[j],
340                                                         signatures[j]);
341                                 if (ret < 0 || ret != positions[j]) {
342                                         printf("Key looked up in %d, should be in %d\n",
343                                                 ret, positions[j]);
344                                         return -1;
345                                 }
346                         } else if (!with_hash && with_data) {
347                                 ret = rte_hash_lookup_data(h[table_index],
348                                                         (const void *) keys[j], &ret_data);
349                                 if (ret < 0) {
350                                         printf("Key number %u was not found\n", j);
351                                         return -1;
352                                 }
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,
357                                                 expected_data);
358                                         return -1;
359                                 }
360                         } else {
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",
364                                                 ret, positions[j]);
365                                         return -1;
366                                 }
367                         }
368                 }
369         }
370
371         const uint64_t end_tsc = rte_rdtsc();
372         const uint64_t time_taken = end_tsc - start_tsc;
373
374         cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS;
375
376         return 0;
377 }
378
379 static int
380 timed_lookups_multi(unsigned with_data, unsigned table_index)
381 {
382         unsigned i, j, k;
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];
387         uint64_t hit_mask;
388         int ret;
389
390         const uint64_t start_tsc = rte_rdtsc();
391
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];
396                         if (with_data) {
397                                 ret = rte_hash_lookup_bulk_data(h[table_index],
398                                         (const void **) keys_burst,
399                                         BURST_SIZE,
400                                         &hit_mask,
401                                         ret_data);
402                                 if (ret != BURST_SIZE) {
403                                         printf("Expect to find %u keys,"
404                                                " but found %d\n", BURST_SIZE, ret);
405                                         return -1;
406                                 }
407                                 for (k = 0; k < BURST_SIZE; k++) {
408                                         if ((hit_mask & (1ULL << k))  == 0) {
409                                                 printf("Key number %u not found\n",
410                                                         j * BURST_SIZE + k);
411                                                 return -1;
412                                         }
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]);
418                                                 return -1;
419                                         }
420                                 }
421                         } else {
422                                 rte_hash_lookup_bulk(h[table_index],
423                                                 (const void **) keys_burst,
424                                                 BURST_SIZE,
425                                                 positions_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",
429                                                         positions_burst[k],
430                                                         positions[j * BURST_SIZE + k]);
431                                                 return -1;
432                                         }
433                                 }
434                         }
435                 }
436         }
437
438         const uint64_t end_tsc = rte_rdtsc();
439         const uint64_t time_taken = end_tsc - start_tsc;
440
441         cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS;
442
443         return 0;
444 }
445
446 static int
447 timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
448 {
449         unsigned i;
450         const uint64_t start_tsc = rte_rdtsc();
451         int32_t ret;
452
453         for (i = 0; i < KEYS_TO_ADD; i++) {
454                 /* There are no delete functions with data, so just call two functions */
455                 if (with_hash)
456                         ret = rte_hash_del_key_with_hash(h[table_index],
457                                                         (const void *) keys[i],
458                                                         signatures[i]);
459                 else
460                         ret = rte_hash_del_key(h[table_index],
461                                                         (const void *) keys[i]);
462                 if (ret >= 0)
463                         positions[i] = ret;
464                 else {
465                         printf("Failed to add key number %u\n", ret);
466                         return -1;
467                 }
468         }
469
470         const uint64_t end_tsc = rte_rdtsc();
471         const uint64_t time_taken = end_tsc - start_tsc;
472
473         cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD;
474
475         return 0;
476 }
477
478 static void
479 free_table(unsigned table_index)
480 {
481         rte_hash_free(h[table_index]);
482 }
483
484 static void
485 reset_table(unsigned table_index)
486 {
487         rte_hash_reset(h[table_index]);
488 }
489
490 static int
491 run_all_tbl_perf_tests(unsigned with_pushes)
492 {
493         unsigned i, j, with_data, with_hash;
494
495         printf("Measuring performance, please wait");
496         fflush(stdout);
497
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)
501                                 return -1;
502
503                         if (get_input_keys(with_pushes, i) < 0)
504                                 return -1;
505                         for (with_hash = 0; with_hash <= 1; with_hash++) {
506                                 if (timed_adds(with_hash, with_data, i) < 0)
507                                         return -1;
508
509                                 for (j = 0; j < NUM_SHUFFLES; j++)
510                                         shuffle_input_keys(i);
511
512                                 if (timed_lookups(with_hash, with_data, i) < 0)
513                                         return -1;
514
515                                 if (timed_lookups_multi(with_data, i) < 0)
516                                         return -1;
517
518                                 if (timed_deletes(with_hash, with_data, i) < 0)
519                                         return -1;
520
521                                 /* Print a dot to show progress on operations */
522                                 printf(".");
523                                 fflush(stdout);
524
525                                 reset_table(i);
526                         }
527                         free_table(i);
528                 }
529         }
530
531         printf("\nResults (in CPU cycles/operation)\n");
532         printf("-----------------------------------\n");
533         for (with_data = 0; with_data <= 1; with_data++) {
534                 if (with_data)
535                         printf("\n Operations with 8-byte data\n");
536                 else
537                         printf("\n Operations without data\n");
538                 for (with_hash = 0; with_hash <= 1; with_hash++) {
539                         if (with_hash)
540                                 printf("\nWith pre-computed hash values\n");
541                         else
542                                 printf("\nWithout pre-computed hash values\n");
543
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]);
550                                 printf("\n");
551                         }
552                 }
553         }
554         return 0;
555 }
556
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. */
562
563 static int
564 fbk_hash_perf_test(void)
565 {
566         struct rte_fbk_hash_params params = {
567                 .name = "fbk_hash_test",
568                 .entries = ENTRIES,
569                 .entries_per_bucket = 4,
570                 .socket_id = rte_socket_id(),
571         };
572         struct rte_fbk_hash_table *handle = NULL;
573         uint32_t *keys = NULL;
574         unsigned indexes[TEST_SIZE];
575         uint64_t lookup_time = 0;
576         unsigned added = 0;
577         unsigned value = 0;
578         uint32_t key;
579         uint16_t val;
580         unsigned i, j;
581
582         handle = rte_fbk_hash_create(&params);
583         if (handle == NULL) {
584                 printf("Error creating table\n");
585                 return -1;
586         }
587
588         keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
589         if (keys == NULL) {
590                 printf("fbk hash: memory allocation for key store failed\n");
591                 return -1;
592         }
593
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();
599
600                 if (rte_fbk_hash_add_key(handle, key, val) == 0) {
601                         keys[added] = key;
602                         added++;
603                 }
604                 if (added > (LOAD_FACTOR * ENTRIES))
605                         break;
606         }
607
608         for (i = 0; i < TEST_ITERATIONS; i++) {
609                 uint64_t begin;
610                 uint64_t end;
611
612                 /* Generate random indexes into keys[] array. */
613                 for (j = 0; j < TEST_SIZE; j++)
614                         indexes[j] = rte_rand() % added;
615
616                 begin = rte_rdtsc();
617                 /* Do lookups */
618                 for (j = 0; j < TEST_SIZE; j++)
619                         value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
620
621                 end = rte_rdtsc();
622                 lookup_time += (double)(end - begin);
623         }
624
625         printf("\n\n *** FBK Hash function performance test results ***\n");
626         /*
627          * The use of the 'value' variable ensures that the hash lookup is not
628          * being optimised out by the compiler.
629          */
630         if (value != 0)
631                 printf("Number of ticks per lookup = %g\n",
632                         (double)lookup_time /
633                         ((double)TEST_ITERATIONS * (double)TEST_SIZE));
634
635         rte_fbk_hash_free(handle);
636
637         return 0;
638 }
639
640 static int
641 test_hash_perf(void)
642 {
643         unsigned with_pushes;
644
645         for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
646                 if (with_pushes == 0)
647                         printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
648                 else
649                         printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
650                 if (run_all_tbl_perf_tests(with_pushes) < 0)
651                         return -1;
652         }
653         if (fbk_hash_perf_test() < 0)
654                 return -1;
655
656         return 0;
657 }
658
659 REGISTER_TEST_COMMAND(hash_perf_autotest, test_hash_perf);