4 * Copyright(c) 2017 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
37 #include <rte_lcore.h>
38 #include <rte_cycles.h>
39 #include <rte_malloc.h>
40 #include <rte_random.h>
41 #include <rte_memcpy.h>
42 #include <rte_thash.h>
43 #include <rte_member.h>
47 #define NUM_KEYSIZES 10
48 #define NUM_SHUFFLES 10
49 #define MAX_KEYSIZE 64
50 #define MAX_ENTRIES (1 << 19)
51 #define KEYS_TO_ADD (MAX_ENTRIES * 75 / 100) /* 75% table utilization */
52 #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
53 #define VBF_SET_CNT 16
55 #define VBF_FALSE_RATE 0.03
57 static unsigned int test_socket_id;
77 struct member_perf_params {
78 struct rte_member_setsum *setsum[NUM_TYPE];
83 static uint32_t hashtest_key_lens[] = {
84 /* standard key sizes */
86 /* IPv4 SRC + DST + protocol, unpadded */
88 /* IPv4 5-tuple, unpadded */
90 /* IPv6 5-tuple, unpadded */
92 /* IPv6 5-tuple, padded to 8-byte boundary */
96 /* Array to store number of cycles per operation */
97 uint64_t cycles[NUM_TYPE][NUM_KEYSIZES][NUM_OPERATIONS];
98 uint64_t false_data[NUM_TYPE][NUM_KEYSIZES];
99 uint64_t false_data_bulk[NUM_TYPE][NUM_KEYSIZES];
100 uint64_t false_data_multi[NUM_TYPE][NUM_KEYSIZES];
101 uint64_t false_data_multi_bulk[NUM_TYPE][NUM_KEYSIZES];
103 uint64_t false_hit[NUM_TYPE][NUM_KEYSIZES];
105 member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD];
107 /* Array to store all input keys */
108 uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
110 /* Shuffle the keys that have been added, so lookups will be totally random */
112 shuffle_input_keys(struct member_perf_params *params)
114 member_set_t temp_data;
117 uint8_t temp_key[MAX_KEYSIZE];
119 for (i = KEYS_TO_ADD - 1; i > 0; i--) {
120 swap_idx = rte_rand() % i;
121 memcpy(temp_key, keys[i], hashtest_key_lens[params->cycle]);
122 memcpy(keys[i], keys[swap_idx],
123 hashtest_key_lens[params->cycle]);
124 memcpy(keys[swap_idx], temp_key,
125 hashtest_key_lens[params->cycle]);
126 for (j = 0; j < NUM_TYPE; j++) {
127 temp_data = data[j][i];
128 data[j][i] = data[j][swap_idx];
129 data[j][swap_idx] = temp_data;
134 static int key_compare(const void *key1, const void *key2)
136 return memcmp(key1, key2, MAX_KEYSIZE);
139 struct rte_member_parameters member_params = {
140 .num_keys = MAX_ENTRIES, /* Total hash table entries. */
141 .key_len = 4, /* Length of hash key. */
143 /* num_set and false_positive_rate only relevant to vBF */
144 .num_set = VBF_SET_CNT,
145 .false_positive_rate = 0.03,
148 .socket_id = 0, /* NUMA Socket ID for memory. */
152 setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
158 params->key_size = hashtest_key_lens[cycle];
159 params->cycle = cycle;
161 /* Reset all arrays */
162 for (i = 0; i < params->key_size; i++)
165 /* Generate a list of keys, some of which may be duplicates */
166 for (i = 0; i < KEYS_TO_ADD; i++) {
167 for (j = 0; j < params->key_size; j++)
168 keys[i][j] = rte_rand() & 0xFF;
170 data[HT][i] = data[CACHE][i] = (rte_rand() & 0x7FFE) + 1;
171 data[VBF][i] = rte_rand() % VBF_SET_CNT + 1;
174 /* Remove duplicates from the keys array */
178 /* Sort the list of keys to make it easier to find duplicates */
179 qsort(keys, KEYS_TO_ADD, MAX_KEYSIZE, key_compare);
181 /* Sift through the list of keys and look for duplicates */
182 int num_duplicates = 0;
183 for (i = 0; i < KEYS_TO_ADD - 1; i++) {
184 if (memcmp(keys[i], keys[i + 1],
185 params->key_size) == 0) {
186 /* This key already exists, try again */
188 for (j = 0; j < params->key_size; j++)
189 keys[i][j] = rte_rand() & 0xFF;
192 } while (num_duplicates != 0);
194 /* Shuffle the random values again */
195 shuffle_input_keys(params);
197 /* For testing miss lookup, we insert half and lookup the other half */
198 unsigned int entry_cnt, bf_key_cnt;
200 entry_cnt = MAX_ENTRIES;
201 bf_key_cnt = KEYS_TO_ADD;
203 entry_cnt = MAX_ENTRIES / 2;
204 bf_key_cnt = KEYS_TO_ADD / 2;
206 member_params.false_positive_rate = VBF_FALSE_RATE;
207 member_params.key_len = params->key_size;
208 member_params.socket_id = test_socket_id;
209 member_params.num_keys = entry_cnt;
210 member_params.name = "test_member_ht";
211 member_params.is_cache = 0;
212 member_params.type = RTE_MEMBER_TYPE_HT;
213 params->setsum[HT] = rte_member_create(&member_params);
214 if (params->setsum[HT] == NULL)
215 fprintf(stderr, "ht create fail\n");
217 member_params.name = "test_member_cache";
218 member_params.is_cache = 1;
219 params->setsum[CACHE] = rte_member_create(&member_params);
220 if (params->setsum[CACHE] == NULL)
221 fprintf(stderr, "CACHE create fail\n");
223 member_params.name = "test_member_vbf";
224 member_params.type = RTE_MEMBER_TYPE_VBF;
225 member_params.num_keys = bf_key_cnt;
226 params->setsum[VBF] = rte_member_create(&member_params);
227 if (params->setsum[VBF] == NULL)
228 fprintf(stderr, "VBF create fail\n");
229 for (i = 0; i < NUM_TYPE; i++) {
230 if (params->setsum[i] == NULL)
238 timed_adds(struct member_perf_params *params, int type)
240 const uint64_t start_tsc = rte_rdtsc();
244 for (i = 0; i < KEYS_TO_ADD; i++) {
245 ret = rte_member_add(params->setsum[type], &keys[i],
248 printf("Error %d in rte_member_add - key=0x", ret);
249 for (a = 0; a < params->key_size; a++)
250 printf("%02x", keys[i][a]);
251 printf(" value=%d, type: %d\n", data[type][i], type);
257 const uint64_t end_tsc = rte_rdtsc();
258 const uint64_t time_taken = end_tsc - start_tsc;
260 cycles[type][params->cycle][ADD] = time_taken / KEYS_TO_ADD;
265 timed_lookups(struct member_perf_params *params, int type)
269 false_data[type][params->cycle] = 0;
271 const uint64_t start_tsc = rte_rdtsc();
275 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
276 for (j = 0; j < KEYS_TO_ADD; j++) {
277 ret = rte_member_lookup(params->setsum[type], &keys[j],
280 printf("lookup wrong internally");
283 if (type == HT && result == RTE_MEMBER_NO_MATCH) {
284 printf("HT mode shouldn't have false negative");
287 if (result != data[type][j])
288 false_data[type][params->cycle]++;
292 const uint64_t end_tsc = rte_rdtsc();
293 const uint64_t time_taken = end_tsc - start_tsc;
295 cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS;
301 timed_lookups_bulk(struct member_perf_params *params, int type)
303 unsigned int i, j, k;
304 member_set_t result[BURST_SIZE] = {0};
305 const void *keys_burst[BURST_SIZE];
308 false_data_bulk[type][params->cycle] = 0;
310 const uint64_t start_tsc = rte_rdtsc();
312 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
313 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) {
314 for (k = 0; k < BURST_SIZE; k++)
315 keys_burst[k] = keys[j * BURST_SIZE + k];
317 ret = rte_member_lookup_bulk(params->setsum[type],
322 printf("lookup bulk has wrong return value\n");
325 for (k = 0; k < BURST_SIZE; k++) {
326 uint32_t data_idx = j * BURST_SIZE + k;
327 if (type == HT && result[k] ==
328 RTE_MEMBER_NO_MATCH) {
329 printf("HT mode shouldn't have "
333 if (result[k] != data[type][data_idx])
334 false_data_bulk[type][params->cycle]++;
339 const uint64_t end_tsc = rte_rdtsc();
340 const uint64_t time_taken = end_tsc - start_tsc;
342 cycles[type][params->cycle][LOOKUP_BULK] = time_taken / NUM_LOOKUPS;
348 timed_lookups_multimatch(struct member_perf_params *params, int type)
351 member_set_t result[RTE_MEMBER_BUCKET_ENTRIES] = {0};
353 false_data_multi[type][params->cycle] = 0;
355 const uint64_t start_tsc = rte_rdtsc();
357 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
358 for (j = 0; j < KEYS_TO_ADD; j++) {
359 ret = rte_member_lookup_multi(params->setsum[type],
360 &keys[j], RTE_MEMBER_BUCKET_ENTRIES, result);
361 if (type != CACHE && ret <= 0) {
362 printf("lookup multi has wrong return value %d,"
363 "type %d\n", ret, type);
365 if (type == HT && ret == 0) {
366 printf("HT mode shouldn't have false negative");
370 * For performance test purpose, we do not iterate all
371 * results here. We assume most likely each key can only
372 * find one match which is result[0].
374 if (result[0] != data[type][j])
375 false_data_multi[type][params->cycle]++;
379 const uint64_t end_tsc = rte_rdtsc();
380 const uint64_t time_taken = end_tsc - start_tsc;
382 cycles[type][params->cycle][LOOKUP_MULTI] = time_taken / NUM_LOOKUPS;
388 timed_lookups_multimatch_bulk(struct member_perf_params *params, int type)
390 unsigned int i, j, k;
391 member_set_t result[BURST_SIZE][RTE_MEMBER_BUCKET_ENTRIES] = {{0} };
392 const void *keys_burst[BURST_SIZE];
393 uint32_t match_count[BURST_SIZE];
396 false_data_multi_bulk[type][params->cycle] = 0;
398 const uint64_t start_tsc = rte_rdtsc();
400 for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
401 for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) {
402 for (k = 0; k < BURST_SIZE; k++)
403 keys_burst[k] = keys[j * BURST_SIZE + k];
405 ret = rte_member_lookup_multi_bulk(
406 params->setsum[type],
407 keys_burst, BURST_SIZE,
408 RTE_MEMBER_BUCKET_ENTRIES, match_count,
409 (member_set_t *)result);
411 printf("lookup multimatch bulk has wrong return"
415 for (k = 0; k < BURST_SIZE; k++) {
416 if (type != CACHE && match_count[k] == 0) {
417 printf("lookup multimatch bulk get "
418 "wrong match count\n");
421 if (type == HT && match_count[k] == 0) {
422 printf("HT mode shouldn't have "
426 uint32_t data_idx = j * BURST_SIZE + k;
427 if (result[k][0] != data[type][data_idx])
428 false_data_multi_bulk[type][params->cycle]++;
433 const uint64_t end_tsc = rte_rdtsc();
434 const uint64_t time_taken = end_tsc - start_tsc;
436 cycles[type][params->cycle][LOOKUP_MULTI_BULK] = time_taken /
443 timed_deletes(struct member_perf_params *params, int type)
450 const uint64_t start_tsc = rte_rdtsc();
451 for (i = 0; i < KEYS_TO_ADD; i++) {
452 ret = rte_member_delete(params->setsum[type], &keys[i],
454 if (type != CACHE && ret < 0) {
455 printf("delete error\n");
460 const uint64_t end_tsc = rte_rdtsc();
461 const uint64_t time_taken = end_tsc - start_tsc;
463 cycles[type][params->cycle][DELETE] = time_taken / KEYS_TO_ADD;
469 timed_miss_lookup(struct member_perf_params *params, int type)
474 false_hit[type][params->cycle] = 0;
476 for (i = 0; i < KEYS_TO_ADD / 2; i++) {
477 ret = rte_member_add(params->setsum[type], &keys[i],
481 printf("Error %d in rte_member_add - key=0x", ret);
482 for (a = 0; a < params->key_size; a++)
483 printf("%02x", keys[i][a]);
484 printf(" value=%d, type: %d\n", data[type][i], type);
490 const uint64_t start_tsc = rte_rdtsc();
493 for (i = 0; i < 2 * NUM_LOOKUPS / KEYS_TO_ADD; i++) {
494 for (j = KEYS_TO_ADD / 2; j < KEYS_TO_ADD; j++) {
495 ret = rte_member_lookup(params->setsum[type], &keys[j],
498 printf("lookup wrong internally");
501 if (result != RTE_MEMBER_NO_MATCH)
502 false_hit[type][params->cycle]++;
506 const uint64_t end_tsc = rte_rdtsc();
507 const uint64_t time_taken = end_tsc - start_tsc;
509 cycles[type][params->cycle][LOOKUP_MISS] = time_taken / NUM_LOOKUPS;
515 perform_frees(struct member_perf_params *params)
518 for (i = 0; i < NUM_TYPE; i++) {
519 if (params->setsum[i] != NULL) {
520 rte_member_free(params->setsum[i]);
521 params->setsum[i] = NULL;
527 exit_with_fail(const char *testname, struct member_perf_params *params,
528 unsigned int i, unsigned int j)
530 printf("<<<<<Test %s failed at keysize %d iteration %d type %d>>>>>\n",
531 testname, hashtest_key_lens[params->cycle], i, j);
532 perform_frees(params);
537 run_all_tbl_perf_tests(void)
539 unsigned int i, j, k;
540 struct member_perf_params params;
542 printf("Measuring performance, please wait\n");
545 test_socket_id = rte_socket_id();
547 for (i = 0; i < NUM_KEYSIZES; i++) {
548 if (setup_keys_and_data(¶ms, i, 0) < 0) {
549 printf("Could not create keys/data/table\n");
552 for (j = 0; j < NUM_TYPE; j++) {
554 if (timed_adds(¶ms, j) < 0)
555 return exit_with_fail("timed_adds", ¶ms,
558 for (k = 0; k < NUM_SHUFFLES; k++)
559 shuffle_input_keys(¶ms);
561 if (timed_lookups(¶ms, j) < 0)
562 return exit_with_fail("timed_lookups", ¶ms,
565 if (timed_lookups_bulk(¶ms, j) < 0)
566 return exit_with_fail("timed_lookups_bulk",
569 if (timed_lookups_multimatch(¶ms, j) < 0)
570 return exit_with_fail("timed_lookups_multi",
573 if (timed_lookups_multimatch_bulk(¶ms, j) < 0)
574 return exit_with_fail("timed_lookups_multi_bulk",
577 if (timed_deletes(¶ms, j) < 0)
578 return exit_with_fail("timed_deletes", ¶ms,
581 /* Print a dot to show progress on operations */
586 perform_frees(¶ms);
589 /* Test false positive rate using un-inserted keys */
590 for (i = 0; i < NUM_KEYSIZES; i++) {
591 if (setup_keys_and_data(¶ms, i, 1) < 0) {
592 printf("Could not create keys/data/table\n");
595 for (j = 0; j < NUM_TYPE; j++) {
596 if (timed_miss_lookup(¶ms, j) < 0)
597 return exit_with_fail("timed_miss_lookup",
600 perform_frees(¶ms);
603 printf("\nResults (in CPU cycles/operation)\n");
604 printf("-----------------------------------\n");
605 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n",
606 "Keysize", "type", "Add", "Lookup", "Lookup_bulk",
607 "lookup_multi", "lookup_multi_bulk", "Delete",
609 for (i = 0; i < NUM_KEYSIZES; i++) {
610 for (j = 0; j < NUM_TYPE; j++) {
611 printf("%-18d", hashtest_key_lens[i]);
613 for (k = 0; k < NUM_OPERATIONS; k++)
614 printf("%-18"PRIu64, cycles[j][i][k]);
619 printf("\nFalse results rate (and false positive rate)\n");
620 printf("-----------------------------------\n");
621 printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n",
622 "Keysize", "type", "fr_single", "fr_bulk", "fr_multi",
623 "fr_multi_bulk", "false_positive_rate");
624 /* Key size not influence False rate so just print out one key size */
625 for (i = 0; i < 1; i++) {
626 for (j = 0; j < NUM_TYPE; j++) {
627 printf("%-18d", hashtest_key_lens[i]);
629 printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS);
630 printf("%-18f", (float)false_data_bulk[j][i] /
632 printf("%-18f", (float)false_data_multi[j][i] /
634 printf("%-18f", (float)false_data_multi_bulk[j][i] /
636 printf("%-18f", (float)false_hit[j][i] /
645 test_member_perf(void)
648 if (run_all_tbl_perf_tests() < 0)
654 REGISTER_TEST_COMMAND(member_perf_autotest, test_member_perf);