1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017 Intel Corporation
3 */
4
5 #include "test.h"
6
7 #include <stdio.h>
8 #include <inttypes.h>
9
10 #include <rte_lcore.h>
11 #include <rte_cycles.h>
12 #include <rte_malloc.h>
13 #include <rte_random.h>
14 #include <rte_memcpy.h>
15 #include <rte_thash.h>
16
17 #ifdef RTE_EXEC_ENV_WINDOWS
18 static int
test_member_perf(void)19 test_member_perf(void)
20 {
21 printf("member_perf not supported on Windows, skipping test\n");
22 return TEST_SKIPPED;
23 }
24
25 #else
26
27 #include <rte_member.h>
28
29 #define NUM_KEYSIZES 10
30 #define NUM_SHUFFLES 10
31 #define MAX_KEYSIZE 64
32 #define MAX_ENTRIES (1 << 19)
33 #define KEYS_TO_ADD (MAX_ENTRIES * 75 / 100) /* 75% table utilization */
34 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
35 #define VBF_SET_CNT 16
36 #define BURST_SIZE 64
37 #define VBF_FALSE_RATE 0.03
38
39 static unsigned int test_socket_id;
40
41 enum sstype {
42 HT = 0,
43 CACHE,
44 VBF,
45 NUM_TYPE
46 };
47
48 enum operations {
49 ADD = 0,
50 LOOKUP,
51 LOOKUP_BULK,
52 LOOKUP_MULTI,
53 LOOKUP_MULTI_BULK,
54 DELETE,
55 LOOKUP_MISS,
56 NUM_OPERATIONS
57 };
58
59 struct member_perf_params {
60 struct rte_member_setsum *setsum[NUM_TYPE];
61 uint32_t key_size;
62 unsigned int cycle;
63 };
64
65 static uint32_t hashtest_key_lens[] = {
66 /* standard key sizes */
67 4, 8, 16, 32, 48, 64,
68 /* IPv4 SRC + DST + protocol, unpadded */
69 9,
70 /* IPv4 5-tuple, unpadded */
71 13,
72 /* IPv6 5-tuple, unpadded */
73 37,
74 /* IPv6 5-tuple, padded to 8-byte boundary */
75 40
76 };
77
78 /* Array to store number of cycles per operation */
79 static uint64_t cycles[NUM_TYPE][NUM_KEYSIZES][NUM_OPERATIONS];
80 static uint64_t false_data[NUM_TYPE][NUM_KEYSIZES];
81 static uint64_t false_data_bulk[NUM_TYPE][NUM_KEYSIZES];
82 static uint64_t false_data_multi[NUM_TYPE][NUM_KEYSIZES];
83 static uint64_t false_data_multi_bulk[NUM_TYPE][NUM_KEYSIZES];
84
85 static uint64_t false_hit[NUM_TYPE][NUM_KEYSIZES];
86
87 static member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD];
88
89 /* Array to store all input keys */
90 static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
91
92 /* Shuffle the keys that have been added, so lookups will be totally random */
93 static void
shuffle_input_keys(struct member_perf_params * params)94 shuffle_input_keys(struct member_perf_params *params)
95 {
96 member_set_t temp_data;
97 unsigned int i, j;
98 uint32_t swap_idx;
99 uint8_t temp_key[MAX_KEYSIZE];
100
101 for (i = KEYS_TO_ADD - 1; i > 0; i--) {
102 swap_idx = rte_rand() % i;
103 memcpy(temp_key, keys[i], hashtest_key_lens[params->cycle]);
104 memcpy(keys[i], keys[swap_idx],
105 hashtest_key_lens[params->cycle]);
106 memcpy(keys[swap_idx], temp_key,
107 hashtest_key_lens[params->cycle]);
108 for (j = 0; j < NUM_TYPE; j++) {
109 temp_data = data[j][i];
110 data[j][i] = data[j][swap_idx];
111 data[j][swap_idx] = temp_data;
112 }
113 }
114 }
115
key_compare(const void * key1,const void * key2)116 static int key_compare(const void *key1, const void *key2)
117 {
118 return memcmp(key1, key2, MAX_KEYSIZE);
119 }
120
121 struct rte_member_parameters member_params = {
122 .num_keys = MAX_ENTRIES, /* Total hash table entries. */
123 .key_len = 4, /* Length of hash key. */
124
125 /* num_set and false_positive_rate only relevant to vBF */
126 .num_set = VBF_SET_CNT,
127 .false_positive_rate = 0.03,
128 .prim_hash_seed = 0,
129 .sec_hash_seed = 1,
130 .socket_id = 0, /* NUMA Socket ID for memory. */
131 };
132
133 static int
setup_keys_and_data(struct member_perf_params * params,unsigned int cycle,int miss)134 setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
135 int miss)
136 {
137 unsigned int i, j;
138 int num_duplicates;
139
140 params->key_size = hashtest_key_lens[cycle];
141 params->cycle = cycle;
142
143 /* Reset all arrays */
144 for (i = 0; i < params->key_size; i++)
145 keys[0][i] = 0;
146
147 /* Generate a list of keys, some of which may be duplicates */
148 for (i = 0; i < KEYS_TO_ADD; i++) {
149 for (j = 0; j < params->key_size; j++)
150 keys[i][j] = rte_rand() & 0xFF;
151
152 data[HT][i] = data[CACHE][i] = (rte_rand() & 0x7FFE) + 1;
153 data[VBF][i] = rte_rand() % VBF_SET_CNT + 1;
154 }
155
156 /* Remove duplicates from the keys array */
157 do {
158 num_duplicates = 0;
159
160 /* Sort the list of keys to make it easier to find duplicates */
161 qsort(keys, KEYS_TO_ADD, MAX_KEYSIZE, key_compare);
162
163 /* Sift through the list of keys and look for duplicates */
164 int num_duplicates = 0;
165 for (i = 0; i < KEYS_TO_ADD - 1; i++) {
166 if (memcmp(keys[i], keys[i + 1],
167 params->key_size) == 0) {
168 /* This key already exists, try again */
169 num_duplicates++;
170 for (j = 0; j < params->key_size; j++)
171 keys[i][j] = rte_rand() & 0xFF;
172 }
173 }
174 } while (num_duplicates != 0);
175
176 /* Shuffle the random values again */
177 shuffle_input_keys(params);
178
179 /* For testing miss lookup, we insert half and lookup the other half */
180 unsigned int entry_cnt, bf_key_cnt;
181 if (!miss) {
182 entry_cnt = MAX_ENTRIES;
183 bf_key_cnt = KEYS_TO_ADD;
184 } else {
185 entry_cnt = MAX_ENTRIES / 2;
186 bf_key_cnt = KEYS_TO_ADD / 2;
187 }
188 member_params.false_positive_rate = VBF_FALSE_RATE;
189 member_params.key_len = params->key_size;
190 member_params.socket_id = test_socket_id;
191 member_params.num_keys = entry_cnt;
192 member_params.name = "test_member_ht";
193 member_params.is_cache = 0;
194 member_params.type = RTE_MEMBER_TYPE_HT;
195 params->setsum[HT] = rte_member_create(&member_params);
196 if (params->setsum[HT] == NULL)
197 fprintf(stderr, "ht create fail\n");
198
199 member_params.name = "test_member_cache";
200 member_params.is_cache = 1;
201 params->setsum[CACHE] = rte_member_create(&member_params);
202 if (params->setsum[CACHE] == NULL)
203 fprintf(stderr, "CACHE create fail\n");
204
205 member_params.name = "test_member_vbf";
206 member_params.type = RTE_MEMBER_TYPE_VBF;
207 member_params.num_keys = bf_key_cnt;
208 params->setsum[VBF] = rte_member_create(&member_params);
209 if (params->setsum[VBF] == NULL)
210 fprintf(stderr, "VBF create fail\n");
211 for (i = 0; i < NUM_TYPE; i++) {
212 if (params->setsum[i] == NULL)
213 return -1;
214 }
215
216 return 0;
217 }
218
219 static int
timed_adds(struct member_perf_params * params,int type)220 timed_adds(struct member_perf_params *params, int type)
221 {
222 const uint64_t start_tsc = rte_rdtsc();
223 unsigned int i, a;
224 int32_t ret;
225
226 for (i = 0; i < KEYS_TO_ADD; i++) {
227 ret = rte_member_add(params->setsum[type], &keys[i],
228 data[type][i]);
229 if (ret < 0) {
230 printf("Error %d in rte_member_add - key=0x", ret);
231 for (a = 0; a < params->key_size; a++)
232 printf("%02x", keys[i][a]);
233 printf(" value=%d, type: %d\n", data[type][i], type);
234
235 return -1;
236 }
237 }
238
239 const uint64_t end_tsc = rte_rdtsc();
240 const uint64_t time_taken = end_tsc - start_tsc;
241
242 cycles[type][params->cycle][ADD] = time_taken / KEYS_TO_ADD;
243 return 0;
244 }
245
246 static int
timed_lookups(struct member_perf_params * params,int type)247 timed_lookups(struct member_perf_params *params, int type)
248 {
249 unsigned int i, j;
250
251 false_data[type][params->cycle] = 0;
252
253 const uint64_t start_tsc = rte_rdtsc();
254 member_set_t result;
255 int ret;
256
257 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
258 for (j = 0; j < KEYS_TO_ADD; j++) {
259 ret = rte_member_lookup(params->setsum[type], &keys[j],
260 &result);
261 if (ret < 0) {
262 printf("lookup wrong internally");
263 return -1;
264 }
265 if (type == HT && result == RTE_MEMBER_NO_MATCH) {
266 printf("HT mode shouldn't have false negative");
267 return -1;
268 }
269 if (result != data[type][j])
270 false_data[type][params->cycle]++;
271 }
272 }
273
274 const uint64_t end_tsc = rte_rdtsc();
275 const uint64_t time_taken = end_tsc - start_tsc;
276
277 cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS;
278
279 return 0;
280 }
281
282 static int
timed_lookups_bulk(struct member_perf_params * params,int type)283 timed_lookups_bulk(struct member_perf_params *params, int type)
284 {
285 unsigned int i, j, k;
286 member_set_t result[BURST_SIZE] = {0};
287 const void *keys_burst[BURST_SIZE];
288 int ret;
289
290 false_data_bulk[type][params->cycle] = 0;
291
292 const uint64_t start_tsc = rte_rdtsc();
293
294 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
295 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) {
296 for (k = 0; k < BURST_SIZE; k++)
297 keys_burst[k] = keys[j * BURST_SIZE + k];
298
299 ret = rte_member_lookup_bulk(params->setsum[type],
300 keys_burst,
301 BURST_SIZE,
302 result);
303 if (ret <= 0) {
304 printf("lookup bulk has wrong return value\n");
305 return -1;
306 }
307 for (k = 0; k < BURST_SIZE; k++) {
308 uint32_t data_idx = j * BURST_SIZE + k;
309 if (type == HT && result[k] ==
310 RTE_MEMBER_NO_MATCH) {
311 printf("HT mode shouldn't have "
312 "false negative");
313 return -1;
314 }
315 if (result[k] != data[type][data_idx])
316 false_data_bulk[type][params->cycle]++;
317 }
318 }
319 }
320
321 const uint64_t end_tsc = rte_rdtsc();
322 const uint64_t time_taken = end_tsc - start_tsc;
323
324 cycles[type][params->cycle][LOOKUP_BULK] = time_taken / NUM_LOOKUPS;
325
326 return 0;
327 }
328
329 static int
timed_lookups_multimatch(struct member_perf_params * params,int type)330 timed_lookups_multimatch(struct member_perf_params *params, int type)
331 {
332 unsigned int i, j;
333 member_set_t result[RTE_MEMBER_BUCKET_ENTRIES] = {0};
334 int ret;
335 false_data_multi[type][params->cycle] = 0;
336
337 const uint64_t start_tsc = rte_rdtsc();
338
339 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
340 for (j = 0; j < KEYS_TO_ADD; j++) {
341 ret = rte_member_lookup_multi(params->setsum[type],
342 &keys[j], RTE_MEMBER_BUCKET_ENTRIES, result);
343 if (type != CACHE && ret <= 0) {
344 printf("lookup multi has wrong return value %d,"
345 "type %d\n", ret, type);
346 }
347 if (type == HT && ret == 0) {
348 printf("HT mode shouldn't have false negative");
349 return -1;
350 }
351 /*
352 * For performance test purpose, we do not iterate all
353 * results here. We assume most likely each key can only
354 * find one match which is result[0].
355 */
356 if (result[0] != data[type][j])
357 false_data_multi[type][params->cycle]++;
358 }
359 }
360
361 const uint64_t end_tsc = rte_rdtsc();
362 const uint64_t time_taken = end_tsc - start_tsc;
363
364 cycles[type][params->cycle][LOOKUP_MULTI] = time_taken / NUM_LOOKUPS;
365
366 return 0;
367 }
368
369 static int
timed_lookups_multimatch_bulk(struct member_perf_params * params,int type)370 timed_lookups_multimatch_bulk(struct member_perf_params *params, int type)
371 {
372 unsigned int i, j, k;
373 member_set_t result[BURST_SIZE][RTE_MEMBER_BUCKET_ENTRIES] = {{0} };
374 const void *keys_burst[BURST_SIZE];
375 uint32_t match_count[BURST_SIZE];
376 int ret;
377
378 false_data_multi_bulk[type][params->cycle] = 0;
379
380 const uint64_t start_tsc = rte_rdtsc();
381
382 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
383 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) {
384 for (k = 0; k < BURST_SIZE; k++)
385 keys_burst[k] = keys[j * BURST_SIZE + k];
386
387 ret = rte_member_lookup_multi_bulk(
388 params->setsum[type],
389 keys_burst, BURST_SIZE,
390 RTE_MEMBER_BUCKET_ENTRIES, match_count,
391 (member_set_t *)result);
392 if (ret < 0) {
393 printf("lookup multimatch bulk has wrong return"
394 " value\n");
395 return -1;
396 }
397 for (k = 0; k < BURST_SIZE; k++) {
398 if (type != CACHE && match_count[k] == 0) {
399 printf("lookup multimatch bulk get "
400 "wrong match count\n");
401 return -1;
402 }
403 if (type == HT && match_count[k] == 0) {
404 printf("HT mode shouldn't have "
405 "false negative");
406 return -1;
407 }
408 uint32_t data_idx = j * BURST_SIZE + k;
409 if (result[k][0] != data[type][data_idx])
410 false_data_multi_bulk[type][params->cycle]++;
411 }
412 }
413 }
414
415 const uint64_t end_tsc = rte_rdtsc();
416 const uint64_t time_taken = end_tsc - start_tsc;
417
418 cycles[type][params->cycle][LOOKUP_MULTI_BULK] = time_taken /
419 NUM_LOOKUPS;
420
421 return 0;
422 }
423
424 static int
timed_deletes(struct member_perf_params * params,int type)425 timed_deletes(struct member_perf_params *params, int type)
426 {
427 unsigned int i;
428 int32_t ret;
429
430 if (type == VBF)
431 return 0;
432 const uint64_t start_tsc = rte_rdtsc();
433 for (i = 0; i < KEYS_TO_ADD; i++) {
434 ret = rte_member_delete(params->setsum[type], &keys[i],
435 data[type][i]);
436 if (type != CACHE && ret < 0) {
437 printf("delete error\n");
438 return -1;
439 }
440 }
441
442 const uint64_t end_tsc = rte_rdtsc();
443 const uint64_t time_taken = end_tsc - start_tsc;
444
445 cycles[type][params->cycle][DELETE] = time_taken / KEYS_TO_ADD;
446
447 return 0;
448 }
449
450 static int
timed_miss_lookup(struct member_perf_params * params,int type)451 timed_miss_lookup(struct member_perf_params *params, int type)
452 {
453 unsigned int i, j;
454 int ret;
455
456 false_hit[type][params->cycle] = 0;
457
458 for (i = 0; i < KEYS_TO_ADD / 2; i++) {
459 ret = rte_member_add(params->setsum[type], &keys[i],
460 data[type][i]);
461 if (ret < 0) {
462 unsigned int a;
463 printf("Error %d in rte_member_add - key=0x", ret);
464 for (a = 0; a < params->key_size; a++)
465 printf("%02x", keys[i][a]);
466 printf(" value=%d, type: %d\n", data[type][i], type);
467
468 return -1;
469 }
470 }
471
472 const uint64_t start_tsc = rte_rdtsc();
473 member_set_t result;
474
475 for (i = 0; i < 2 * NUM_LOOKUPS / KEYS_TO_ADD; i++) {
476 for (j = KEYS_TO_ADD / 2; j < KEYS_TO_ADD; j++) {
477 ret = rte_member_lookup(params->setsum[type], &keys[j],
478 &result);
479 if (ret < 0) {
480 printf("lookup wrong internally");
481 return -1;
482 }
483 if (result != RTE_MEMBER_NO_MATCH)
484 false_hit[type][params->cycle]++;
485 }
486 }
487
488 const uint64_t end_tsc = rte_rdtsc();
489 const uint64_t time_taken = end_tsc - start_tsc;
490
491 cycles[type][params->cycle][LOOKUP_MISS] = time_taken / NUM_LOOKUPS;
492
493 return 0;
494 }
495
496 static void
perform_frees(struct member_perf_params * params)497 perform_frees(struct member_perf_params *params)
498 {
499 int i;
500 for (i = 0; i < NUM_TYPE; i++) {
501 if (params->setsum[i] != NULL) {
502 rte_member_free(params->setsum[i]);
503 params->setsum[i] = NULL;
504 }
505 }
506 }
507
508 static int
exit_with_fail(const char * testname,struct member_perf_params * params,unsigned int i,unsigned int j)509 exit_with_fail(const char *testname, struct member_perf_params *params,
510 unsigned int i, unsigned int j)
511 {
512 printf("<<<<<Test %s failed at keysize %d iteration %d type %d>>>>>\n",
513 testname, hashtest_key_lens[params->cycle], i, j);
514 perform_frees(params);
515 return -1;
516 }
517
518 static int
run_all_tbl_perf_tests(void)519 run_all_tbl_perf_tests(void)
520 {
521 unsigned int i, j, k;
522 struct member_perf_params params;
523
524 printf("Measuring performance, please wait\n");
525 fflush(stdout);
526
527 test_socket_id = rte_socket_id();
528
529 for (i = 0; i < NUM_KEYSIZES; i++) {
530 if (setup_keys_and_data(¶ms, i, 0) < 0) {
531 printf("Could not create keys/data/table\n");
532 return -1;
533 }
534 for (j = 0; j < NUM_TYPE; j++) {
535
536 if (timed_adds(¶ms, j) < 0)
537 return exit_with_fail("timed_adds", ¶ms,
538 i, j);
539
540 for (k = 0; k < NUM_SHUFFLES; k++)
541 shuffle_input_keys(¶ms);
542
543 if (timed_lookups(¶ms, j) < 0)
544 return exit_with_fail("timed_lookups", ¶ms,
545 i, j);
546
547 if (timed_lookups_bulk(¶ms, j) < 0)
548 return exit_with_fail("timed_lookups_bulk",
549 ¶ms, i, j);
550
551 if (timed_lookups_multimatch(¶ms, j) < 0)
552 return exit_with_fail("timed_lookups_multi",
553 ¶ms, i, j);
554
555 if (timed_lookups_multimatch_bulk(¶ms, j) < 0)
556 return exit_with_fail("timed_lookups_multi_bulk",
557 ¶ms, i, j);
558
559 if (timed_deletes(¶ms, j) < 0)
560 return exit_with_fail("timed_deletes", ¶ms,
561 i, j);
562
563 /* Print a dot to show progress on operations */
564 }
565 printf(".");
566 fflush(stdout);
567
568 perform_frees(¶ms);
569 }
570
571 /* Test false positive rate using un-inserted keys */
572 for (i = 0; i < NUM_KEYSIZES; i++) {
573 if (setup_keys_and_data(¶ms, i, 1) < 0) {
574 printf("Could not create keys/data/table\n");
575 return -1;
576 }
577 for (j = 0; j < NUM_TYPE; j++) {
578 if (timed_miss_lookup(¶ms, j) < 0)
579 return exit_with_fail("timed_miss_lookup",
580 ¶ms, i, j);
581 }
582 perform_frees(¶ms);
583 }
584
585 printf("\nResults (in CPU cycles/operation)\n");
586 printf("-----------------------------------\n");
587 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n",
588 "Keysize", "type", "Add", "Lookup", "Lookup_bulk",
589 "lookup_multi", "lookup_multi_bulk", "Delete",
590 "miss_lookup");
591 for (i = 0; i < NUM_KEYSIZES; i++) {
592 for (j = 0; j < NUM_TYPE; j++) {
593 printf("%-18d", hashtest_key_lens[i]);
594 printf("%-18d", j);
595 for (k = 0; k < NUM_OPERATIONS; k++)
596 printf("%-18"PRIu64, cycles[j][i][k]);
597 printf("\n");
598 }
599 }
600
601 printf("\nFalse results rate (and false positive rate)\n");
602 printf("-----------------------------------\n");
603 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n",
604 "Keysize", "type", "fr_single", "fr_bulk", "fr_multi",
605 "fr_multi_bulk", "false_positive_rate");
606 /* Key size not influence False rate so just print out one key size */
607 for (i = 0; i < 1; i++) {
608 for (j = 0; j < NUM_TYPE; j++) {
609 printf("%-18d", hashtest_key_lens[i]);
610 printf("%-18d", j);
611 printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS);
612 printf("%-18f", (float)false_data_bulk[j][i] /
613 NUM_LOOKUPS);
614 printf("%-18f", (float)false_data_multi[j][i] /
615 NUM_LOOKUPS);
616 printf("%-18f", (float)false_data_multi_bulk[j][i] /
617 NUM_LOOKUPS);
618 printf("%-18f", (float)false_hit[j][i] /
619 NUM_LOOKUPS);
620 printf("\n");
621 }
622 }
623 return 0;
624 }
625
626 static int
test_member_perf(void)627 test_member_perf(void)
628 {
629
630 if (run_all_tbl_perf_tests() < 0)
631 return -1;
632
633 return 0;
634 }
635
636 #endif /* !RTE_EXEC_ENV_WINDOWS */
637
638 REGISTER_TEST_COMMAND(member_perf_autotest, test_member_perf);
639