1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2017 Intel Corporation
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>
17 #ifdef RTE_EXEC_ENV_WINDOWS
19 test_member_perf(void)
21 printf("member_perf not supported on Windows, skipping test\n");
27 #include <rte_member.h>
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
37 #define VBF_FALSE_RATE 0.03
39 static unsigned int test_socket_id;
59 struct member_perf_params {
60 struct rte_member_setsum *setsum[NUM_TYPE];
65 static uint32_t hashtest_key_lens[] = {
66 /* standard key sizes */
68 /* IPv4 SRC + DST + protocol, unpadded */
70 /* IPv4 5-tuple, unpadded */
72 /* IPv6 5-tuple, unpadded */
74 /* IPv6 5-tuple, padded to 8-byte boundary */
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];
85 static uint64_t false_hit[NUM_TYPE][NUM_KEYSIZES];
87 static member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD];
89 /* Array to store all input keys */
90 static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
92 /* Shuffle the keys that have been added, so lookups will be totally random */
94 shuffle_input_keys(struct member_perf_params *params)
96 member_set_t temp_data;
99 uint8_t temp_key[MAX_KEYSIZE];
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;
116 static int key_compare(const void *key1, const void *key2)
118 return memcmp(key1, key2, MAX_KEYSIZE);
121 struct rte_member_parameters member_params = {
122 .num_keys = MAX_ENTRIES, /* Total hash table entries. */
123 .key_len = 4, /* Length of hash key. */
125 /* num_set and false_positive_rate only relevant to vBF */
126 .num_set = VBF_SET_CNT,
127 .false_positive_rate = 0.03,
130 .socket_id = 0, /* NUMA Socket ID for memory. */
134 setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
140 params->key_size = hashtest_key_lens[cycle];
141 params->cycle = cycle;
143 /* Reset all arrays */
144 for (i = 0; i < params->key_size; i++)
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;
152 data[HT][i] = data[CACHE][i] = (rte_rand() & 0x7FFE) + 1;
153 data[VBF][i] = rte_rand() % VBF_SET_CNT + 1;
156 /* Remove duplicates from the keys array */
160 /* Sort the list of keys to make it easier to find duplicates */
161 qsort(keys, KEYS_TO_ADD, MAX_KEYSIZE, key_compare);
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 */
170 for (j = 0; j < params->key_size; j++)
171 keys[i][j] = rte_rand() & 0xFF;
174 } while (num_duplicates != 0);
176 /* Shuffle the random values again */
177 shuffle_input_keys(params);
179 /* For testing miss lookup, we insert half and lookup the other half */
180 unsigned int entry_cnt, bf_key_cnt;
182 entry_cnt = MAX_ENTRIES;
183 bf_key_cnt = KEYS_TO_ADD;
185 entry_cnt = MAX_ENTRIES / 2;
186 bf_key_cnt = KEYS_TO_ADD / 2;
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");
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");
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)
220 timed_adds(struct member_perf_params *params, int type)
222 const uint64_t start_tsc = rte_rdtsc();
226 for (i = 0; i < KEYS_TO_ADD; i++) {
227 ret = rte_member_add(params->setsum[type], &keys[i],
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);
239 const uint64_t end_tsc = rte_rdtsc();
240 const uint64_t time_taken = end_tsc - start_tsc;
242 cycles[type][params->cycle][ADD] = time_taken / KEYS_TO_ADD;
247 timed_lookups(struct member_perf_params *params, int type)
251 false_data[type][params->cycle] = 0;
253 const uint64_t start_tsc = rte_rdtsc();
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],
262 printf("lookup wrong internally");
265 if (type == HT && result == RTE_MEMBER_NO_MATCH) {
266 printf("HT mode shouldn't have false negative");
269 if (result != data[type][j])
270 false_data[type][params->cycle]++;
274 const uint64_t end_tsc = rte_rdtsc();
275 const uint64_t time_taken = end_tsc - start_tsc;
277 cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS;
283 timed_lookups_bulk(struct member_perf_params *params, int type)
285 unsigned int i, j, k;
286 member_set_t result[BURST_SIZE] = {0};
287 const void *keys_burst[BURST_SIZE];
290 false_data_bulk[type][params->cycle] = 0;
292 const uint64_t start_tsc = rte_rdtsc();
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];
299 ret = rte_member_lookup_bulk(params->setsum[type],
304 printf("lookup bulk has wrong return value\n");
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 "
315 if (result[k] != data[type][data_idx])
316 false_data_bulk[type][params->cycle]++;
321 const uint64_t end_tsc = rte_rdtsc();
322 const uint64_t time_taken = end_tsc - start_tsc;
324 cycles[type][params->cycle][LOOKUP_BULK] = time_taken / NUM_LOOKUPS;
330 timed_lookups_multimatch(struct member_perf_params *params, int type)
333 member_set_t result[RTE_MEMBER_BUCKET_ENTRIES] = {0};
335 false_data_multi[type][params->cycle] = 0;
337 const uint64_t start_tsc = rte_rdtsc();
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);
347 if (type == HT && ret == 0) {
348 printf("HT mode shouldn't have false negative");
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].
356 if (result[0] != data[type][j])
357 false_data_multi[type][params->cycle]++;
361 const uint64_t end_tsc = rte_rdtsc();
362 const uint64_t time_taken = end_tsc - start_tsc;
364 cycles[type][params->cycle][LOOKUP_MULTI] = time_taken / NUM_LOOKUPS;
370 timed_lookups_multimatch_bulk(struct member_perf_params *params, int type)
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];
378 false_data_multi_bulk[type][params->cycle] = 0;
380 const uint64_t start_tsc = rte_rdtsc();
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];
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);
393 printf("lookup multimatch bulk has wrong return"
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");
403 if (type == HT && match_count[k] == 0) {
404 printf("HT mode shouldn't have "
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]++;
415 const uint64_t end_tsc = rte_rdtsc();
416 const uint64_t time_taken = end_tsc - start_tsc;
418 cycles[type][params->cycle][LOOKUP_MULTI_BULK] = time_taken /
425 timed_deletes(struct member_perf_params *params, int type)
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],
436 if (type != CACHE && ret < 0) {
437 printf("delete error\n");
442 const uint64_t end_tsc = rte_rdtsc();
443 const uint64_t time_taken = end_tsc - start_tsc;
445 cycles[type][params->cycle][DELETE] = time_taken / KEYS_TO_ADD;
451 timed_miss_lookup(struct member_perf_params *params, int type)
456 false_hit[type][params->cycle] = 0;
458 for (i = 0; i < KEYS_TO_ADD / 2; i++) {
459 ret = rte_member_add(params->setsum[type], &keys[i],
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);
472 const uint64_t start_tsc = rte_rdtsc();
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],
480 printf("lookup wrong internally");
483 if (result != RTE_MEMBER_NO_MATCH)
484 false_hit[type][params->cycle]++;
488 const uint64_t end_tsc = rte_rdtsc();
489 const uint64_t time_taken = end_tsc - start_tsc;
491 cycles[type][params->cycle][LOOKUP_MISS] = time_taken / NUM_LOOKUPS;
497 perform_frees(struct member_perf_params *params)
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;
509 exit_with_fail(const char *testname, struct member_perf_params *params,
510 unsigned int i, unsigned int j)
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);
519 run_all_tbl_perf_tests(void)
521 unsigned int i, j, k;
522 struct member_perf_params params;
524 printf("Measuring performance, please wait\n");
527 test_socket_id = rte_socket_id();
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");
534 for (j = 0; j < NUM_TYPE; j++) {
536 if (timed_adds(¶ms, j) < 0)
537 return exit_with_fail("timed_adds", ¶ms,
540 for (k = 0; k < NUM_SHUFFLES; k++)
541 shuffle_input_keys(¶ms);
543 if (timed_lookups(¶ms, j) < 0)
544 return exit_with_fail("timed_lookups", ¶ms,
547 if (timed_lookups_bulk(¶ms, j) < 0)
548 return exit_with_fail("timed_lookups_bulk",
551 if (timed_lookups_multimatch(¶ms, j) < 0)
552 return exit_with_fail("timed_lookups_multi",
555 if (timed_lookups_multimatch_bulk(¶ms, j) < 0)
556 return exit_with_fail("timed_lookups_multi_bulk",
559 if (timed_deletes(¶ms, j) < 0)
560 return exit_with_fail("timed_deletes", ¶ms,
563 /* Print a dot to show progress on operations */
568 perform_frees(¶ms);
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");
577 for (j = 0; j < NUM_TYPE; j++) {
578 if (timed_miss_lookup(¶ms, j) < 0)
579 return exit_with_fail("timed_miss_lookup",
582 perform_frees(¶ms);
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",
591 for (i = 0; i < NUM_KEYSIZES; i++) {
592 for (j = 0; j < NUM_TYPE; j++) {
593 printf("%-18d", hashtest_key_lens[i]);
595 for (k = 0; k < NUM_OPERATIONS; k++)
596 printf("%-18"PRIu64, cycles[j][i][k]);
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]);
611 printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS);
612 printf("%-18f", (float)false_data_bulk[j][i] /
614 printf("%-18f", (float)false_data_multi[j][i] /
616 printf("%-18f", (float)false_data_multi_bulk[j][i] /
618 printf("%-18f", (float)false_hit[j][i] /
627 test_member_perf(void)
630 if (run_all_tbl_perf_tests() < 0)
636 #endif /* !RTE_EXEC_ENV_WINDOWS */
638 REGISTER_TEST_COMMAND(member_perf_autotest, test_member_perf);