Branch data Line data Source code
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)
22 : : #define ADD_PERCENT 0.75 /* 75% table utilization */
23 : : #define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
24 : : /* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */
25 : : #define BUCKET_SIZE 8
26 : : #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
27 : : #define MAX_KEYSIZE 64
28 : : #define NUM_KEYSIZES 10
29 : : #define NUM_SHUFFLES 10
30 : : #define BURST_SIZE 16
31 : :
32 : : enum operations {
33 : : OP_ADD = 0,
34 : : OP_LOOKUP,
35 : : OP_LOOKUP_MULTI,
36 : : OP_DELETE,
37 : : NUM_OPERATIONS
38 : : };
39 : :
40 : : static uint32_t hashtest_key_lens[] = {
41 : : /* standard key sizes */
42 : : 4, 8, 16, 32, 48, 64,
43 : : /* IPv4 SRC + DST + protocol, unpadded */
44 : : 9,
45 : : /* IPv4 5-tuple, unpadded */
46 : : 13,
47 : : /* IPv6 5-tuple, unpadded */
48 : : 37,
49 : : /* IPv6 5-tuple, padded to 8-byte boundary */
50 : : 40
51 : : };
52 : :
53 : : struct rte_hash *h[NUM_KEYSIZES];
54 : :
55 : : /* Array that stores if a slot is full */
56 : : static uint8_t slot_taken[MAX_ENTRIES];
57 : :
58 : : /* Array to store number of cycles per operation */
59 : : static uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
60 : :
61 : : /* Array to store all input keys */
62 : : static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
63 : :
64 : : /* Array to store the precomputed hash for 'keys' */
65 : : static hash_sig_t signatures[KEYS_TO_ADD];
66 : :
67 : : /* Array to store how many busy entries have each bucket */
68 : : static uint8_t buckets[NUM_BUCKETS];
69 : :
70 : : /* Array to store the positions where keys are added */
71 : : static int32_t positions[KEYS_TO_ADD];
72 : :
73 : : /* Parameters used for hash table in unit test functions. */
74 : : static struct rte_hash_parameters ut_params = {
75 : : .entries = MAX_ENTRIES,
76 : : .hash_func = rte_jhash,
77 : : .hash_func_init_val = 0,
78 : : };
79 : :
80 : : static int
81 : 0 : create_table(unsigned int with_data, unsigned int table_index,
82 : : unsigned int with_locks, unsigned int ext)
83 : : {
84 : : char name[RTE_HASH_NAMESIZE];
85 : :
86 [ # # ]: 0 : if (with_data)
87 : : /* Table will store 8-byte data */
88 : 0 : snprintf(name, sizeof(name), "test_hash%u_data",
89 : : hashtest_key_lens[table_index]);
90 : : else
91 : 0 : snprintf(name, sizeof(name), "test_hash%u",
92 : : hashtest_key_lens[table_index]);
93 : :
94 : :
95 [ # # ]: 0 : if (with_locks)
96 : 0 : ut_params.extra_flag =
97 : : RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT
98 : : | RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY;
99 : : else
100 : 0 : ut_params.extra_flag = 0;
101 : :
102 [ # # ]: 0 : if (ext)
103 : 0 : ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
104 : :
105 : 0 : ut_params.name = name;
106 : 0 : ut_params.key_len = hashtest_key_lens[table_index];
107 : 0 : ut_params.socket_id = rte_socket_id();
108 : 0 : h[table_index] = rte_hash_find_existing(name);
109 : 0 : rte_hash_free(h[table_index]);
110 : 0 : h[table_index] = rte_hash_create(&ut_params);
111 [ # # ]: 0 : if (h[table_index] == NULL) {
112 : : printf("Error creating table\n");
113 : 0 : return -1;
114 : : }
115 : : return 0;
116 : :
117 : : }
118 : :
119 : : /* Shuffle the keys that have been added, so lookups will be totally random */
120 : : static void
121 : 0 : shuffle_input_keys(unsigned int table_index, unsigned int ext)
122 : : {
123 : : unsigned i;
124 : : uint32_t swap_idx;
125 : : uint8_t temp_key[MAX_KEYSIZE];
126 : : hash_sig_t temp_signature;
127 : : int32_t temp_position;
128 : : unsigned int keys_to_add;
129 : :
130 [ # # ]: 0 : if (!ext)
131 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
132 : : else
133 : : keys_to_add = KEYS_TO_ADD;
134 : :
135 [ # # ]: 0 : for (i = keys_to_add - 1; i > 0; i--) {
136 : 0 : swap_idx = rte_rand() % i;
137 : :
138 : 0 : memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
139 : 0 : temp_signature = signatures[i];
140 : 0 : temp_position = positions[i];
141 : :
142 : 0 : memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
143 : 0 : signatures[i] = signatures[swap_idx];
144 : 0 : positions[i] = positions[swap_idx];
145 : :
146 : : memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
147 : 0 : signatures[swap_idx] = temp_signature;
148 : 0 : positions[swap_idx] = temp_position;
149 : : }
150 : 0 : }
151 : :
152 : : /*
153 : : * Looks for random keys which
154 : : * ALL can fit in hash table (no errors)
155 : : */
156 : : static int
157 : 0 : get_input_keys(unsigned int with_pushes, unsigned int table_index,
158 : : unsigned int ext)
159 : : {
160 : : unsigned i, j;
161 : : unsigned bucket_idx, incr, success = 1;
162 : : uint8_t k = 0;
163 : : int32_t ret;
164 : : const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
165 : : unsigned int keys_to_add;
166 : :
167 [ # # ]: 0 : if (!ext)
168 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
169 : : else
170 : : keys_to_add = KEYS_TO_ADD;
171 : : /* Reset all arrays */
172 [ # # ]: 0 : for (i = 0; i < MAX_ENTRIES; i++)
173 : 0 : slot_taken[i] = 0;
174 : :
175 [ # # ]: 0 : for (i = 0; i < NUM_BUCKETS; i++)
176 : 0 : buckets[i] = 0;
177 : :
178 [ # # ]: 0 : for (j = 0; j < hashtest_key_lens[table_index]; j++)
179 : 0 : keys[0][j] = 0;
180 : :
181 : : /*
182 : : * Add only entries that are not duplicated and that fits in the table
183 : : * (cannot store more than BUCKET_SIZE entries in a bucket).
184 : : * Regardless a key has been added correctly or not (success),
185 : : * the next one to try will be increased by 1.
186 : : */
187 [ # # ]: 0 : for (i = 0; i < keys_to_add;) {
188 : : incr = 0;
189 [ # # ]: 0 : if (i != 0) {
190 : 0 : keys[i][0] = ++k;
191 : : /* Overflow, need to increment the next byte */
192 [ # # ]: 0 : if (keys[i][0] == 0)
193 : : incr = 1;
194 [ # # ]: 0 : for (j = 1; j < hashtest_key_lens[table_index]; j++) {
195 : : /* Do not increase next byte */
196 [ # # ]: 0 : if (incr == 0)
197 [ # # ]: 0 : if (success == 1)
198 : 0 : keys[i][j] = keys[i - 1][j];
199 : : else
200 : 0 : keys[i][j] = keys[i][j];
201 : : /* Increase next byte by one */
202 : : else {
203 [ # # ]: 0 : if (success == 1)
204 : 0 : keys[i][j] = keys[i-1][j] + 1;
205 : : else
206 : 0 : keys[i][j] = keys[i][j] + 1;
207 [ # # ]: 0 : if (keys[i][j] == 0)
208 : : incr = 1;
209 : : else
210 : : incr = 0;
211 : : }
212 : : }
213 : : }
214 : : success = 0;
215 : 0 : signatures[i] = rte_hash_hash(h[table_index], keys[i]);
216 : 0 : bucket_idx = signatures[i] & bucket_bitmask;
217 : : /*
218 : : * If we are not inserting keys in secondary location,
219 : : * when bucket is full, do not try to insert the key
220 : : */
221 [ # # ]: 0 : if (with_pushes == 0)
222 [ # # ]: 0 : if (buckets[bucket_idx] == BUCKET_SIZE)
223 : 0 : continue;
224 : :
225 : : /* If key can be added, leave in successful key arrays "keys" */
226 : 0 : ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
227 : : signatures[i]);
228 [ # # ]: 0 : if (ret >= 0) {
229 : : /* If key is already added, ignore the entry and do not store */
230 [ # # ]: 0 : if (slot_taken[ret])
231 : 0 : continue;
232 : : else {
233 : : /* Store the returned position and mark slot as taken */
234 : 0 : slot_taken[ret] = 1;
235 : 0 : positions[i] = ret;
236 : 0 : buckets[bucket_idx]++;
237 : : success = 1;
238 : 0 : i++;
239 : : }
240 : : }
241 : : }
242 : :
243 : : /* Reset the table, so we can measure the time to add all the entries */
244 : 0 : rte_hash_free(h[table_index]);
245 : 0 : h[table_index] = rte_hash_create(&ut_params);
246 : :
247 : 0 : return 0;
248 : : }
249 : :
250 : : static int
251 : 0 : timed_adds(unsigned int with_hash, unsigned int with_data,
252 : : unsigned int table_index, unsigned int ext)
253 : : {
254 : : unsigned i;
255 : : const uint64_t start_tsc = rte_rdtsc();
256 : : void *data;
257 : : int32_t ret;
258 : : unsigned int keys_to_add;
259 [ # # ]: 0 : if (!ext)
260 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
261 : : else
262 : : keys_to_add = KEYS_TO_ADD;
263 : :
264 [ # # ]: 0 : for (i = 0; i < keys_to_add; i++) {
265 : 0 : data = (void *) ((uintptr_t) signatures[i]);
266 [ # # ]: 0 : if (with_hash && with_data) {
267 : 0 : ret = rte_hash_add_key_with_hash_data(h[table_index],
268 : 0 : (const void *) keys[i],
269 : : signatures[i], data);
270 [ # # ]: 0 : if (ret < 0) {
271 : : printf("H+D: Failed to add key number %u\n", i);
272 : 0 : return -1;
273 : : }
274 [ # # ]: 0 : } else if (with_hash && !with_data) {
275 : 0 : ret = rte_hash_add_key_with_hash(h[table_index],
276 : 0 : (const void *) keys[i],
277 : : signatures[i]);
278 [ # # ]: 0 : if (ret >= 0)
279 : 0 : positions[i] = ret;
280 : : else {
281 : : printf("H: Failed to add key number %u\n", i);
282 : 0 : return -1;
283 : : }
284 [ # # ]: 0 : } else if (!with_hash && with_data) {
285 : 0 : ret = rte_hash_add_key_data(h[table_index],
286 : 0 : (const void *) keys[i],
287 : : data);
288 [ # # ]: 0 : if (ret < 0) {
289 : : printf("D: Failed to add key number %u\n", i);
290 : 0 : return -1;
291 : : }
292 : : } else {
293 : 0 : ret = rte_hash_add_key(h[table_index], keys[i]);
294 [ # # ]: 0 : if (ret >= 0)
295 : 0 : positions[i] = ret;
296 : : else {
297 : : printf("Failed to add key number %u\n", i);
298 : 0 : return -1;
299 : : }
300 : : }
301 : : }
302 : :
303 : : const uint64_t end_tsc = rte_rdtsc();
304 : 0 : const uint64_t time_taken = end_tsc - start_tsc;
305 : :
306 : 0 : cycles[table_index][OP_ADD][with_hash][with_data] = time_taken/keys_to_add;
307 : :
308 : 0 : return 0;
309 : : }
310 : :
311 : : static int
312 : 0 : timed_lookups(unsigned int with_hash, unsigned int with_data,
313 : : unsigned int table_index, unsigned int ext)
314 : : {
315 : : unsigned i, j;
316 : : const uint64_t start_tsc = rte_rdtsc();
317 : : void *ret_data;
318 : : void *expected_data;
319 : : int32_t ret;
320 : : unsigned int keys_to_add, num_lookups;
321 : :
322 [ # # ]: 0 : if (!ext) {
323 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
324 : : num_lookups = NUM_LOOKUPS * ADD_PERCENT;
325 : : } else {
326 : : keys_to_add = KEYS_TO_ADD;
327 : : num_lookups = NUM_LOOKUPS;
328 : : }
329 [ # # ]: 0 : for (i = 0; i < num_lookups / keys_to_add; i++) {
330 [ # # ]: 0 : for (j = 0; j < keys_to_add; j++) {
331 [ # # ]: 0 : if (with_hash && with_data) {
332 : 0 : ret = rte_hash_lookup_with_hash_data(h[table_index],
333 : 0 : (const void *) keys[j],
334 : : signatures[j], &ret_data);
335 [ # # ]: 0 : if (ret < 0) {
336 : : printf("Key number %u was not found\n", j);
337 : 0 : return -1;
338 : : }
339 : 0 : expected_data = (void *) ((uintptr_t) signatures[j]);
340 [ # # ]: 0 : if (ret_data != expected_data) {
341 : : printf("Data returned for key number %u is %p,"
342 : : " but should be %p\n", j, ret_data,
343 : : expected_data);
344 : 0 : return -1;
345 : : }
346 [ # # ]: 0 : } else if (with_hash && !with_data) {
347 : 0 : ret = rte_hash_lookup_with_hash(h[table_index],
348 : 0 : (const void *) keys[j],
349 : : signatures[j]);
350 [ # # # # ]: 0 : if (ret < 0 || ret != positions[j]) {
351 : 0 : printf("Key looked up in %d, should be in %d\n",
352 : : ret, positions[j]);
353 : 0 : return -1;
354 : : }
355 [ # # ]: 0 : } else if (!with_hash && with_data) {
356 : 0 : ret = rte_hash_lookup_data(h[table_index],
357 : 0 : (const void *) keys[j], &ret_data);
358 [ # # ]: 0 : if (ret < 0) {
359 : : printf("Key number %u was not found\n", j);
360 : 0 : return -1;
361 : : }
362 : 0 : expected_data = (void *) ((uintptr_t) signatures[j]);
363 [ # # ]: 0 : if (ret_data != expected_data) {
364 : : printf("Data returned for key number %u is %p,"
365 : : " but should be %p\n", j, ret_data,
366 : : expected_data);
367 : 0 : return -1;
368 : : }
369 : : } else {
370 : 0 : ret = rte_hash_lookup(h[table_index], keys[j]);
371 [ # # # # ]: 0 : if (ret < 0 || ret != positions[j]) {
372 : 0 : printf("Key looked up in %d, should be in %d\n",
373 : : ret, positions[j]);
374 : 0 : return -1;
375 : : }
376 : : }
377 : : }
378 : : }
379 : :
380 : : const uint64_t end_tsc = rte_rdtsc();
381 : 0 : const uint64_t time_taken = end_tsc - start_tsc;
382 : :
383 : 0 : cycles[table_index][OP_LOOKUP][with_hash][with_data] = time_taken/num_lookups;
384 : :
385 : 0 : return 0;
386 : : }
387 : :
388 : : static int
389 : 0 : timed_lookups_multi(unsigned int with_hash, unsigned int with_data,
390 : : unsigned int table_index, unsigned int ext)
391 : : {
392 : : unsigned i, j, k;
393 : : int32_t positions_burst[BURST_SIZE];
394 : : const void *keys_burst[BURST_SIZE];
395 : : void *expected_data[BURST_SIZE];
396 : : void *ret_data[BURST_SIZE];
397 : : uint64_t hit_mask;
398 : : int ret;
399 : : unsigned int keys_to_add, num_lookups;
400 : :
401 [ # # ]: 0 : if (!ext) {
402 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
403 : : num_lookups = NUM_LOOKUPS * ADD_PERCENT;
404 : : } else {
405 : : keys_to_add = KEYS_TO_ADD;
406 : : num_lookups = NUM_LOOKUPS;
407 : : }
408 : :
409 : : const uint64_t start_tsc = rte_rdtsc();
410 : :
411 [ # # ]: 0 : for (i = 0; i < num_lookups/keys_to_add; i++) {
412 [ # # ]: 0 : for (j = 0; j < keys_to_add/BURST_SIZE; j++) {
413 [ # # ]: 0 : for (k = 0; k < BURST_SIZE; k++)
414 : 0 : keys_burst[k] = keys[j * BURST_SIZE + k];
415 [ # # ]: 0 : if (!with_hash && with_data) {
416 : 0 : ret = rte_hash_lookup_bulk_data(h[table_index],
417 : : (const void **) keys_burst,
418 : : BURST_SIZE,
419 : : &hit_mask,
420 : : ret_data);
421 [ # # ]: 0 : if (ret != BURST_SIZE) {
422 : : printf("Expect to find %u keys,"
423 : : " but found %d\n", BURST_SIZE, ret);
424 : 0 : return -1;
425 : : }
426 [ # # ]: 0 : for (k = 0; k < BURST_SIZE; k++) {
427 [ # # ]: 0 : if ((hit_mask & (1ULL << k)) == 0) {
428 : 0 : printf("Key number %u not found\n",
429 : 0 : j * BURST_SIZE + k);
430 : 0 : return -1;
431 : : }
432 : 0 : expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]);
433 [ # # ]: 0 : if (ret_data[k] != expected_data[k]) {
434 : : printf("Data returned for key number %u is %p,"
435 : : " but should be %p\n", j * BURST_SIZE + k,
436 : : ret_data[k], expected_data[k]);
437 : 0 : return -1;
438 : : }
439 : : }
440 [ # # ]: 0 : } else if (with_hash && with_data) {
441 : 0 : ret = rte_hash_lookup_with_hash_bulk_data(
442 : 0 : h[table_index],
443 : : (const void **)keys_burst,
444 : 0 : &signatures[j * BURST_SIZE],
445 : : BURST_SIZE, &hit_mask, ret_data);
446 [ # # ]: 0 : if (ret != BURST_SIZE) {
447 : : printf("Expect to find %u keys,"
448 : : " but found %d\n",
449 : : BURST_SIZE, ret);
450 : 0 : return -1;
451 : : }
452 [ # # ]: 0 : for (k = 0; k < BURST_SIZE; k++) {
453 [ # # ]: 0 : if ((hit_mask & (1ULL << k)) == 0) {
454 : 0 : printf("Key number %u"
455 : : " not found\n",
456 : : j * BURST_SIZE + k);
457 : 0 : return -1;
458 : : }
459 : : expected_data[k] =
460 : 0 : (void *)((uintptr_t)signatures[
461 : 0 : j * BURST_SIZE + k]);
462 [ # # ]: 0 : if (ret_data[k] != expected_data[k]) {
463 : : printf("Data returned for key"
464 : : " number %u is %p,"
465 : : " but should be %p\n",
466 : : j * BURST_SIZE + k,
467 : : ret_data[k],
468 : : expected_data[k]);
469 : 0 : return -1;
470 : : }
471 : : }
472 [ # # ]: 0 : } else if (with_hash && !with_data) {
473 : 0 : ret = rte_hash_lookup_with_hash_bulk(
474 : 0 : h[table_index],
475 : : (const void **)keys_burst,
476 : 0 : &signatures[j * BURST_SIZE],
477 : : BURST_SIZE, positions_burst);
478 [ # # ]: 0 : if (ret != 0) {
479 : : printf("rte_hash_lookup_with_hash_bulk failed with %d\n",
480 : : ret);
481 : 0 : return -1;
482 : : }
483 [ # # ]: 0 : for (k = 0; k < BURST_SIZE; k++) {
484 : 0 : if (positions_burst[k] !=
485 : 0 : positions[j *
486 [ # # ]: 0 : BURST_SIZE + k]) {
487 : : printf("Key looked up in %d, should be in %d\n",
488 : : positions_burst[k],
489 : : positions[j *
490 : : BURST_SIZE + k]);
491 : 0 : return -1;
492 : : }
493 : : }
494 : : } else {
495 : 0 : ret = rte_hash_lookup_bulk(h[table_index],
496 : : (const void **) keys_burst,
497 : : BURST_SIZE,
498 : : positions_burst);
499 [ # # ]: 0 : if (ret != 0) {
500 : : printf("rte_hash_lookup_bulk failed with %d\n", ret);
501 : 0 : return -1;
502 : : }
503 [ # # ]: 0 : for (k = 0; k < BURST_SIZE; k++) {
504 [ # # ]: 0 : if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
505 : : printf("Key looked up in %d, should be in %d\n",
506 : : positions_burst[k],
507 : : positions[j * BURST_SIZE + k]);
508 : 0 : return -1;
509 : : }
510 : : }
511 : : }
512 : : }
513 : : }
514 : :
515 : : const uint64_t end_tsc = rte_rdtsc();
516 : 0 : const uint64_t time_taken = end_tsc - start_tsc;
517 : :
518 : 0 : cycles[table_index][OP_LOOKUP_MULTI][with_hash][with_data] =
519 : 0 : time_taken/num_lookups;
520 : :
521 : 0 : return 0;
522 : : }
523 : :
524 : : static int
525 : 0 : timed_deletes(unsigned int with_hash, unsigned int with_data,
526 : : unsigned int table_index, unsigned int ext)
527 : : {
528 : : unsigned i;
529 : : const uint64_t start_tsc = rte_rdtsc();
530 : : int32_t ret;
531 : : unsigned int keys_to_add;
532 [ # # ]: 0 : if (!ext)
533 : : keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
534 : : else
535 : : keys_to_add = KEYS_TO_ADD;
536 : :
537 [ # # ]: 0 : for (i = 0; i < keys_to_add; i++) {
538 : : /* There are no delete functions with data, so just call two functions */
539 [ # # ]: 0 : if (with_hash)
540 : 0 : ret = rte_hash_del_key_with_hash(h[table_index],
541 : 0 : (const void *) keys[i],
542 : : signatures[i]);
543 : : else
544 : 0 : ret = rte_hash_del_key(h[table_index],
545 : 0 : (const void *) keys[i]);
546 [ # # ]: 0 : if (ret >= 0)
547 : 0 : positions[i] = ret;
548 : : else {
549 : : printf("Failed to delete key number %u\n", i);
550 : 0 : return -1;
551 : : }
552 : : }
553 : :
554 : : const uint64_t end_tsc = rte_rdtsc();
555 : 0 : const uint64_t time_taken = end_tsc - start_tsc;
556 : :
557 : 0 : cycles[table_index][OP_DELETE][with_hash][with_data] = time_taken/keys_to_add;
558 : :
559 : 0 : return 0;
560 : : }
561 : :
562 : : static void
563 : : free_table(unsigned table_index)
564 : : {
565 : 0 : rte_hash_free(h[table_index]);
566 : : }
567 : :
568 : : static void
569 : : reset_table(unsigned table_index)
570 : : {
571 : 0 : rte_hash_reset(h[table_index]);
572 : : }
573 : :
574 : : static int
575 : 0 : run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks,
576 : : unsigned int ext)
577 : : {
578 : : unsigned i, j, with_data, with_hash;
579 : :
580 : : printf("Measuring performance, please wait");
581 : 0 : fflush(stdout);
582 : :
583 [ # # ]: 0 : for (with_data = 0; with_data <= 1; with_data++) {
584 [ # # ]: 0 : for (i = 0; i < NUM_KEYSIZES; i++) {
585 [ # # ]: 0 : if (create_table(with_data, i, with_locks, ext) < 0)
586 : : return -1;
587 : :
588 [ # # ]: 0 : if (get_input_keys(with_pushes, i, ext) < 0)
589 : : return -1;
590 [ # # ]: 0 : for (with_hash = 0; with_hash <= 1; with_hash++) {
591 [ # # ]: 0 : if (timed_adds(with_hash, with_data, i, ext) < 0)
592 : : return -1;
593 : :
594 [ # # ]: 0 : for (j = 0; j < NUM_SHUFFLES; j++)
595 : 0 : shuffle_input_keys(i, ext);
596 : :
597 [ # # ]: 0 : if (timed_lookups(with_hash, with_data, i, ext) < 0)
598 : : return -1;
599 : :
600 [ # # ]: 0 : if (timed_lookups_multi(with_hash, with_data,
601 : : i, ext) < 0)
602 : : return -1;
603 : :
604 [ # # ]: 0 : if (timed_deletes(with_hash, with_data, i, ext) < 0)
605 : : return -1;
606 : :
607 : : /* Print a dot to show progress on operations */
608 : : printf(".");
609 : 0 : fflush(stdout);
610 : :
611 : : reset_table(i);
612 : : }
613 : : free_table(i);
614 : : }
615 : : }
616 : :
617 : : printf("\nResults (in CPU cycles/operation)\n");
618 : : printf("-----------------------------------\n");
619 [ # # ]: 0 : for (with_data = 0; with_data <= 1; with_data++) {
620 [ # # ]: 0 : if (with_data)
621 : : printf("\n Operations with 8-byte data\n");
622 : : else
623 : : printf("\n Operations without data\n");
624 [ # # ]: 0 : for (with_hash = 0; with_hash <= 1; with_hash++) {
625 [ # # ]: 0 : if (with_hash)
626 : : printf("\nWith pre-computed hash values\n");
627 : : else
628 : : printf("\nWithout pre-computed hash values\n");
629 : :
630 : : printf("\n%-18s%-18s%-18s%-18s%-18s\n",
631 : : "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
632 [ # # ]: 0 : for (i = 0; i < NUM_KEYSIZES; i++) {
633 : 0 : printf("%-18d", hashtest_key_lens[i]);
634 [ # # ]: 0 : for (j = 0; j < NUM_OPERATIONS; j++)
635 : 0 : printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]);
636 : : printf("\n");
637 : : }
638 : : }
639 : : }
640 : : return 0;
641 : : }
642 : :
643 : : /* Control operation of performance testing of fbk hash. */
644 : : #define LOAD_FACTOR 0.667 /* How full to make the hash table. */
645 : : #define TEST_SIZE 1000000 /* How many operations to time. */
646 : : #define TEST_ITERATIONS 30 /* How many measurements to take. */
647 : : #define ENTRIES (1 << 15) /* How many entries. */
648 : :
649 : : static int
650 : 0 : fbk_hash_perf_test(void)
651 : : {
652 : 0 : struct rte_fbk_hash_params params = {
653 : : .name = "fbk_hash_test",
654 : : .entries = ENTRIES,
655 : : .entries_per_bucket = 4,
656 : 0 : .socket_id = rte_socket_id(),
657 : : };
658 : : struct rte_fbk_hash_table *handle = NULL;
659 : : uint32_t *keys = NULL;
660 : : unsigned indexes[TEST_SIZE];
661 : : uint64_t lookup_time = 0;
662 : : unsigned added = 0;
663 : : unsigned value = 0;
664 : : uint32_t key;
665 : : uint16_t val;
666 : : unsigned i, j;
667 : :
668 : 0 : handle = rte_fbk_hash_create(¶ms);
669 [ # # ]: 0 : if (handle == NULL) {
670 : : printf("Error creating table\n");
671 : 0 : return -1;
672 : : }
673 : :
674 : 0 : keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
675 [ # # ]: 0 : if (keys == NULL) {
676 : : printf("fbk hash: memory allocation for key store failed\n");
677 : 0 : return -1;
678 : : }
679 : :
680 : : /* Generate random keys and values. */
681 [ # # ]: 0 : for (i = 0; i < ENTRIES; i++) {
682 : 0 : key = (uint32_t)rte_rand();
683 : 0 : key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
684 : 0 : val = (uint16_t)rte_rand();
685 : :
686 [ # # ]: 0 : if (rte_fbk_hash_add_key(handle, key, val) == 0) {
687 : 0 : keys[added] = key;
688 : 0 : added++;
689 : : }
690 [ # # ]: 0 : if (added > (LOAD_FACTOR * ENTRIES))
691 : : break;
692 : : }
693 : :
694 [ # # ]: 0 : for (i = 0; i < TEST_ITERATIONS; i++) {
695 : : uint64_t begin;
696 : : uint64_t end;
697 : :
698 : : /* Generate random indexes into keys[] array. */
699 [ # # ]: 0 : for (j = 0; j < TEST_SIZE; j++)
700 : 0 : indexes[j] = rte_rand() % added;
701 : :
702 : : begin = rte_rdtsc();
703 : : /* Do lookups */
704 [ # # ]: 0 : for (j = 0; j < TEST_SIZE; j++)
705 : 0 : value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
706 : :
707 : : end = rte_rdtsc();
708 : 0 : lookup_time += (double)(end - begin);
709 : : }
710 : :
711 : : printf("\n\n *** FBK Hash function performance test results ***\n");
712 : : /*
713 : : * The use of the 'value' variable ensures that the hash lookup is not
714 : : * being optimised out by the compiler.
715 : : */
716 [ # # ]: 0 : if (value != 0)
717 : 0 : printf("Number of ticks per lookup = %g\n",
718 : 0 : (double)lookup_time /
719 : : ((double)TEST_ITERATIONS * (double)TEST_SIZE));
720 : :
721 : 0 : rte_fbk_hash_free(handle);
722 : :
723 : 0 : return 0;
724 : : }
725 : :
726 : : static int
727 : 0 : test_hash_perf(void)
728 : : {
729 : : unsigned int with_pushes, with_locks;
730 : :
731 : : if (RTE_EXEC_ENV_IS_WINDOWS)
732 : : return TEST_SKIPPED;
733 : :
734 [ # # ]: 0 : for (with_locks = 0; with_locks <= 1; with_locks++) {
735 [ # # ]: 0 : if (with_locks)
736 : : printf("\nWith locks in the code\n");
737 : : else
738 : : printf("\nWithout locks in the code\n");
739 [ # # ]: 0 : for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
740 [ # # ]: 0 : if (with_pushes == 0)
741 : : printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
742 : : else
743 : : printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
744 [ # # ]: 0 : if (run_all_tbl_perf_tests(with_pushes, with_locks, 0) < 0)
745 : : return -1;
746 : : }
747 : : }
748 : :
749 : : printf("\n EXTENDABLE BUCKETS PERFORMANCE\n");
750 : :
751 [ # # ]: 0 : if (run_all_tbl_perf_tests(1, 0, 1) < 0)
752 : : return -1;
753 : :
754 [ # # ]: 0 : if (fbk_hash_perf_test() < 0)
755 : 0 : return -1;
756 : :
757 : : return 0;
758 : : }
759 : :
760 : 252 : REGISTER_PERF_TEST(hash_perf_autotest, test_hash_perf);
|
