1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2015 Intel Corporation
3 */
4
5 #include <stdio.h>
6 #include <stdint.h>
7 #include <string.h>
8 #include <stdlib.h>
9 #include <stdarg.h>
10 #include <errno.h>
11 #include <sys/queue.h>
12
13 #include <rte_common.h>
14 #include <rte_malloc.h>
15 #include <rte_cycles.h>
16 #include <rte_random.h>
17 #include <rte_memory.h>
18 #include <rte_eal.h>
19 #include <rte_ip.h>
20 #include <rte_string_fns.h>
21
22 #include "test.h"
23
24 #include <rte_hash.h>
25 #include <rte_fbk_hash.h>
26 #include <rte_jhash.h>
27 #include <rte_hash_crc.h>
28
29 /*******************************************************************************
30 * Hash function performance test configuration section. Each performance test
31 * will be performed HASHTEST_ITERATIONS times.
32 *
33 * The five arrays below control what tests are performed. Every combination
34 * from the array entries is tested.
35 */
36 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
37 static uint32_t hashtest_initvals[] = {0};
38 static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64};
39 #define MAX_KEYSIZE 64
40 /******************************************************************************/
41 #define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)
42
43 /*
44 * Check condition and return an error if true. Assumes that "handle" is the
45 * name of the hash structure pointer to be freed.
46 */
47 #define RETURN_IF_ERROR(cond, str, ...) do { \
48 if (cond) { \
49 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
50 if (handle) rte_hash_free(handle); \
51 return -1; \
52 } \
53 } while(0)
54
55 #define RETURN_IF_ERROR_FBK(cond, str, ...) do { \
56 if (cond) { \
57 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
58 if (handle) rte_fbk_hash_free(handle); \
59 return -1; \
60 } \
61 } while(0)
62
63 #define RETURN_IF_ERROR_RCU_QSBR(cond, str, ...) do { \
64 if (cond) { \
65 printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \
66 if (rcu_cfg.mode == RTE_HASH_QSBR_MODE_SYNC) { \
67 writer_done = 1; \
68 /* Wait until reader exited. */ \
69 rte_eal_mp_wait_lcore(); \
70 } \
71 rte_hash_free(g_handle); \
72 rte_free(g_qsv); \
73 return -1; \
74 } \
75 } while (0)
76
77 /*
78 * 5-tuple key type.
79 * Should be packed to avoid holes with potentially
80 * undefined content in the middle.
81 */
82 struct flow_key {
83 uint32_t ip_src;
84 uint32_t ip_dst;
85 uint16_t port_src;
86 uint16_t port_dst;
87 uint32_t proto;
88 } __rte_packed;
89
90 /*
91 * Hash function that always returns the same value, to easily test what
92 * happens when a bucket is full.
93 */
pseudo_hash(__rte_unused const void * keys,__rte_unused uint32_t key_len,__rte_unused uint32_t init_val)94 static uint32_t pseudo_hash(__rte_unused const void *keys,
95 __rte_unused uint32_t key_len,
96 __rte_unused uint32_t init_val)
97 {
98 return 3;
99 }
100
101 RTE_LOG_REGISTER(hash_logtype_test, test.hash, INFO);
102
103 /*
104 * Print out result of unit test hash operation.
105 */
print_key_info(const char * msg,const struct flow_key * key,int32_t pos)106 static void print_key_info(const char *msg, const struct flow_key *key,
107 int32_t pos)
108 {
109 const uint8_t *p = (const uint8_t *)key;
110 unsigned int i;
111
112 rte_log(RTE_LOG_DEBUG, hash_logtype_test, "%s key:0x", msg);
113 for (i = 0; i < sizeof(struct flow_key); i++)
114 rte_log(RTE_LOG_DEBUG, hash_logtype_test, "%02X", p[i]);
115 rte_log(RTE_LOG_DEBUG, hash_logtype_test, " @ pos %d\n", pos);
116 }
117
118 /* Keys used by unit test functions */
119 static struct flow_key keys[5] = { {
120 .ip_src = RTE_IPV4(0x03, 0x02, 0x01, 0x00),
121 .ip_dst = RTE_IPV4(0x07, 0x06, 0x05, 0x04),
122 .port_src = 0x0908,
123 .port_dst = 0x0b0a,
124 .proto = 0x0c,
125 }, {
126 .ip_src = RTE_IPV4(0x13, 0x12, 0x11, 0x10),
127 .ip_dst = RTE_IPV4(0x17, 0x16, 0x15, 0x14),
128 .port_src = 0x1918,
129 .port_dst = 0x1b1a,
130 .proto = 0x1c,
131 }, {
132 .ip_src = RTE_IPV4(0x23, 0x22, 0x21, 0x20),
133 .ip_dst = RTE_IPV4(0x27, 0x26, 0x25, 0x24),
134 .port_src = 0x2928,
135 .port_dst = 0x2b2a,
136 .proto = 0x2c,
137 }, {
138 .ip_src = RTE_IPV4(0x33, 0x32, 0x31, 0x30),
139 .ip_dst = RTE_IPV4(0x37, 0x36, 0x35, 0x34),
140 .port_src = 0x3938,
141 .port_dst = 0x3b3a,
142 .proto = 0x3c,
143 }, {
144 .ip_src = RTE_IPV4(0x43, 0x42, 0x41, 0x40),
145 .ip_dst = RTE_IPV4(0x47, 0x46, 0x45, 0x44),
146 .port_src = 0x4948,
147 .port_dst = 0x4b4a,
148 .proto = 0x4c,
149 } };
150
151 /* Parameters used for hash table in unit test functions. Name set later. */
152 static struct rte_hash_parameters ut_params = {
153 .entries = 64,
154 .key_len = sizeof(struct flow_key),
155 .hash_func = rte_jhash,
156 .hash_func_init_val = 0,
157 .socket_id = 0,
158 };
159
160 #define CRC32_ITERATIONS (1U << 10)
161 #define CRC32_DWORDS (1U << 6)
162 /*
163 * Test if all CRC32 implementations yield the same hash value
164 */
165 static int
test_crc32_hash_alg_equiv(void)166 test_crc32_hash_alg_equiv(void)
167 {
168 uint32_t hash_val;
169 uint32_t init_val;
170 uint64_t data64[CRC32_DWORDS];
171 unsigned i, j;
172 size_t data_len;
173
174 printf("\n# CRC32 implementations equivalence test\n");
175 for (i = 0; i < CRC32_ITERATIONS; i++) {
176 /* Randomizing data_len of data set */
177 data_len = (size_t) ((rte_rand() % sizeof(data64)) + 1);
178 init_val = (uint32_t) rte_rand();
179
180 /* Fill the data set */
181 for (j = 0; j < CRC32_DWORDS; j++)
182 data64[j] = rte_rand();
183
184 /* Calculate software CRC32 */
185 rte_hash_crc_set_alg(CRC32_SW);
186 hash_val = rte_hash_crc(data64, data_len, init_val);
187
188 /* Check against 4-byte-operand sse4.2 CRC32 if available */
189 rte_hash_crc_set_alg(CRC32_SSE42);
190 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
191 printf("Failed checking CRC32_SW against CRC32_SSE42\n");
192 break;
193 }
194
195 /* Check against 8-byte-operand sse4.2 CRC32 if available */
196 rte_hash_crc_set_alg(CRC32_SSE42_x64);
197 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
198 printf("Failed checking CRC32_SW against CRC32_SSE42_x64\n");
199 break;
200 }
201
202 /* Check against 8-byte-operand ARM64 CRC32 if available */
203 rte_hash_crc_set_alg(CRC32_ARM64);
204 if (hash_val != rte_hash_crc(data64, data_len, init_val)) {
205 printf("Failed checking CRC32_SW against CRC32_ARM64\n");
206 break;
207 }
208 }
209
210 /* Resetting to best available algorithm */
211 rte_hash_crc_set_alg(CRC32_SSE42_x64);
212
213 if (i == CRC32_ITERATIONS)
214 return 0;
215
216 printf("Failed test data (hex, %zu bytes total):\n", data_len);
217 for (j = 0; j < data_len; j++)
218 printf("%02X%c", ((uint8_t *)data64)[j],
219 ((j+1) % 16 == 0 || j == data_len - 1) ? '\n' : ' ');
220
221 return -1;
222 }
223
224 /*
225 * Test a hash function.
226 */
run_hash_func_test(rte_hash_function f,uint32_t init_val,uint32_t key_len)227 static void run_hash_func_test(rte_hash_function f, uint32_t init_val,
228 uint32_t key_len)
229 {
230 static uint8_t key[MAX_KEYSIZE];
231 unsigned i;
232
233
234 for (i = 0; i < key_len; i++)
235 key[i] = (uint8_t) rte_rand();
236
237 /* just to be on the safe side */
238 if (!f)
239 return;
240
241 f(key, key_len, init_val);
242 }
243
244 /*
245 * Test all hash functions.
246 */
run_hash_func_tests(void)247 static void run_hash_func_tests(void)
248 {
249 unsigned i, j, k;
250
251 for (i = 0; i < RTE_DIM(hashtest_funcs); i++) {
252 for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
253 for (k = 0; k < RTE_DIM(hashtest_key_lens); k++) {
254 run_hash_func_test(hashtest_funcs[i],
255 hashtest_initvals[j],
256 hashtest_key_lens[k]);
257 }
258 }
259 }
260 }
261
262 /*
263 * Basic sequence of operations for a single key:
264 * - add
265 * - lookup (hit)
266 * - delete
267 * - lookup (miss)
268 *
269 * Repeat the test case when 'free on delete' is disabled.
270 * - add
271 * - lookup (hit)
272 * - delete
273 * - lookup (miss)
274 * - free
275 */
test_add_delete(void)276 static int test_add_delete(void)
277 {
278 struct rte_hash *handle;
279 /* test with standard add/lookup/delete functions */
280 int pos0, expectedPos0;
281
282 ut_params.name = "test1";
283 handle = rte_hash_create(&ut_params);
284 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
285
286 pos0 = rte_hash_add_key(handle, &keys[0]);
287 print_key_info("Add", &keys[0], pos0);
288 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
289 expectedPos0 = pos0;
290
291 pos0 = rte_hash_lookup(handle, &keys[0]);
292 print_key_info("Lkp", &keys[0], pos0);
293 RETURN_IF_ERROR(pos0 != expectedPos0,
294 "failed to find key (pos0=%d)", pos0);
295
296 pos0 = rte_hash_del_key(handle, &keys[0]);
297 print_key_info("Del", &keys[0], pos0);
298 RETURN_IF_ERROR(pos0 != expectedPos0,
299 "failed to delete key (pos0=%d)", pos0);
300
301 pos0 = rte_hash_lookup(handle, &keys[0]);
302 print_key_info("Lkp", &keys[0], pos0);
303 RETURN_IF_ERROR(pos0 != -ENOENT,
304 "fail: found key after deleting! (pos0=%d)", pos0);
305
306 rte_hash_free(handle);
307
308 /* repeat test with precomputed hash functions */
309 hash_sig_t hash_value;
310 int pos1, expectedPos1, delPos1;
311
312 ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
313 handle = rte_hash_create(&ut_params);
314 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
315 ut_params.extra_flag = 0;
316
317 hash_value = rte_hash_hash(handle, &keys[0]);
318 pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
319 print_key_info("Add", &keys[0], pos1);
320 RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1);
321 expectedPos1 = pos1;
322
323 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
324 print_key_info("Lkp", &keys[0], pos1);
325 RETURN_IF_ERROR(pos1 != expectedPos1,
326 "failed to find key (pos1=%d)", pos1);
327
328 pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
329 print_key_info("Del", &keys[0], pos1);
330 RETURN_IF_ERROR(pos1 != expectedPos1,
331 "failed to delete key (pos1=%d)", pos1);
332 delPos1 = pos1;
333
334 pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value);
335 print_key_info("Lkp", &keys[0], pos1);
336 RETURN_IF_ERROR(pos1 != -ENOENT,
337 "fail: found key after deleting! (pos1=%d)", pos1);
338
339 pos1 = rte_hash_free_key_with_position(handle, delPos1);
340 print_key_info("Free", &keys[0], delPos1);
341 RETURN_IF_ERROR(pos1 != 0,
342 "failed to free key (pos1=%d)", delPos1);
343
344 rte_hash_free(handle);
345
346 return 0;
347 }
348
349 /*
350 * Sequence of operations for a single key:
351 * - delete: miss
352 * - add
353 * - lookup: hit
354 * - add: update
355 * - lookup: hit (updated data)
356 * - delete: hit
357 * - delete: miss
358 * - lookup: miss
359 */
test_add_update_delete(void)360 static int test_add_update_delete(void)
361 {
362 struct rte_hash *handle;
363 int pos0, expectedPos0;
364
365 ut_params.name = "test2";
366 handle = rte_hash_create(&ut_params);
367 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
368
369 pos0 = rte_hash_del_key(handle, &keys[0]);
370 print_key_info("Del", &keys[0], pos0);
371 RETURN_IF_ERROR(pos0 != -ENOENT,
372 "fail: found non-existent key (pos0=%d)", pos0);
373
374 pos0 = rte_hash_add_key(handle, &keys[0]);
375 print_key_info("Add", &keys[0], pos0);
376 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
377 expectedPos0 = pos0;
378
379 pos0 = rte_hash_lookup(handle, &keys[0]);
380 print_key_info("Lkp", &keys[0], pos0);
381 RETURN_IF_ERROR(pos0 != expectedPos0,
382 "failed to find key (pos0=%d)", pos0);
383
384 pos0 = rte_hash_add_key(handle, &keys[0]);
385 print_key_info("Add", &keys[0], pos0);
386 RETURN_IF_ERROR(pos0 != expectedPos0,
387 "failed to re-add key (pos0=%d)", pos0);
388
389 pos0 = rte_hash_lookup(handle, &keys[0]);
390 print_key_info("Lkp", &keys[0], pos0);
391 RETURN_IF_ERROR(pos0 != expectedPos0,
392 "failed to find key (pos0=%d)", pos0);
393
394 pos0 = rte_hash_del_key(handle, &keys[0]);
395 print_key_info("Del", &keys[0], pos0);
396 RETURN_IF_ERROR(pos0 != expectedPos0,
397 "failed to delete key (pos0=%d)", pos0);
398
399 pos0 = rte_hash_del_key(handle, &keys[0]);
400 print_key_info("Del", &keys[0], pos0);
401 RETURN_IF_ERROR(pos0 != -ENOENT,
402 "fail: deleted already deleted key (pos0=%d)", pos0);
403
404 pos0 = rte_hash_lookup(handle, &keys[0]);
405 print_key_info("Lkp", &keys[0], pos0);
406 RETURN_IF_ERROR(pos0 != -ENOENT,
407 "fail: found key after deleting! (pos0=%d)", pos0);
408
409 rte_hash_free(handle);
410 return 0;
411 }
412
413 /*
414 * Sequence of operations for a single key with 'disable free on del' set:
415 * - delete: miss
416 * - add
417 * - lookup: hit
418 * - add: update
419 * - lookup: hit (updated data)
420 * - delete: hit
421 * - delete: miss
422 * - lookup: miss
423 * - free: hit
424 * - lookup: miss
425 */
test_add_update_delete_free(void)426 static int test_add_update_delete_free(void)
427 {
428 struct rte_hash *handle;
429 int pos0, expectedPos0, delPos0, result;
430
431 ut_params.name = "test2";
432 ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
433 handle = rte_hash_create(&ut_params);
434 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
435 ut_params.extra_flag = 0;
436
437 pos0 = rte_hash_del_key(handle, &keys[0]);
438 print_key_info("Del", &keys[0], pos0);
439 RETURN_IF_ERROR(pos0 != -ENOENT,
440 "fail: found non-existent key (pos0=%d)", pos0);
441
442 pos0 = rte_hash_add_key(handle, &keys[0]);
443 print_key_info("Add", &keys[0], pos0);
444 RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
445 expectedPos0 = pos0;
446
447 pos0 = rte_hash_lookup(handle, &keys[0]);
448 print_key_info("Lkp", &keys[0], pos0);
449 RETURN_IF_ERROR(pos0 != expectedPos0,
450 "failed to find key (pos0=%d)", pos0);
451
452 pos0 = rte_hash_add_key(handle, &keys[0]);
453 print_key_info("Add", &keys[0], pos0);
454 RETURN_IF_ERROR(pos0 != expectedPos0,
455 "failed to re-add key (pos0=%d)", pos0);
456
457 pos0 = rte_hash_lookup(handle, &keys[0]);
458 print_key_info("Lkp", &keys[0], pos0);
459 RETURN_IF_ERROR(pos0 != expectedPos0,
460 "failed to find key (pos0=%d)", pos0);
461
462 delPos0 = rte_hash_del_key(handle, &keys[0]);
463 print_key_info("Del", &keys[0], delPos0);
464 RETURN_IF_ERROR(delPos0 != expectedPos0,
465 "failed to delete key (pos0=%d)", delPos0);
466
467 pos0 = rte_hash_del_key(handle, &keys[0]);
468 print_key_info("Del", &keys[0], pos0);
469 RETURN_IF_ERROR(pos0 != -ENOENT,
470 "fail: deleted already deleted key (pos0=%d)", pos0);
471
472 pos0 = rte_hash_lookup(handle, &keys[0]);
473 print_key_info("Lkp", &keys[0], pos0);
474 RETURN_IF_ERROR(pos0 != -ENOENT,
475 "fail: found key after deleting! (pos0=%d)", pos0);
476
477 result = rte_hash_free_key_with_position(handle, delPos0);
478 print_key_info("Free", &keys[0], delPos0);
479 RETURN_IF_ERROR(result != 0,
480 "failed to free key (pos1=%d)", delPos0);
481
482 pos0 = rte_hash_lookup(handle, &keys[0]);
483 print_key_info("Lkp", &keys[0], pos0);
484 RETURN_IF_ERROR(pos0 != -ENOENT,
485 "fail: found key after deleting! (pos0=%d)", pos0);
486
487 rte_hash_free(handle);
488 return 0;
489 }
490
491 /*
492 * Sequence of operations for a single key with 'rw concurrency lock free' set:
493 * - add
494 * - delete: hit
495 * - free: hit
496 * Repeat the test case when 'multi writer add' is enabled.
497 * - add
498 * - delete: hit
499 * - free: hit
500 */
test_add_delete_free_lf(void)501 static int test_add_delete_free_lf(void)
502 {
503 /* Should match the #define LCORE_CACHE_SIZE value in rte_cuckoo_hash.h */
504 #define LCORE_CACHE_SIZE 64
505 struct rte_hash *handle;
506 hash_sig_t hash_value;
507 int pos, expectedPos, delPos;
508 uint8_t extra_flag;
509 uint32_t i, ip_src;
510
511 extra_flag = ut_params.extra_flag;
512 ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
513 handle = rte_hash_create(&ut_params);
514 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
515 ut_params.extra_flag = extra_flag;
516
517 /*
518 * The number of iterations is at least the same as the number of slots
519 * rte_hash allocates internally. This is to reveal potential issues of
520 * not freeing keys successfully.
521 */
522 for (i = 0; i < ut_params.entries + 1; i++) {
523 hash_value = rte_hash_hash(handle, &keys[0]);
524 pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
525 print_key_info("Add", &keys[0], pos);
526 RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
527 expectedPos = pos;
528
529 pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
530 print_key_info("Del", &keys[0], pos);
531 RETURN_IF_ERROR(pos != expectedPos,
532 "failed to delete key (pos=%d)", pos);
533 delPos = pos;
534
535 pos = rte_hash_free_key_with_position(handle, delPos);
536 print_key_info("Free", &keys[0], delPos);
537 RETURN_IF_ERROR(pos != 0,
538 "failed to free key (pos=%d)", delPos);
539 }
540
541 rte_hash_free(handle);
542
543 extra_flag = ut_params.extra_flag;
544 ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
545 RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
546 handle = rte_hash_create(&ut_params);
547 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
548 ut_params.extra_flag = extra_flag;
549
550 ip_src = keys[0].ip_src;
551 /*
552 * The number of iterations is at least the same as the number of slots
553 * rte_hash allocates internally. This is to reveal potential issues of
554 * not freeing keys successfully.
555 */
556 for (i = 0; i < ut_params.entries + (RTE_MAX_LCORE - 1) *
557 (LCORE_CACHE_SIZE - 1) + 1; i++) {
558 keys[0].ip_src++;
559 hash_value = rte_hash_hash(handle, &keys[0]);
560 pos = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
561 print_key_info("Add", &keys[0], pos);
562 RETURN_IF_ERROR(pos < 0, "failed to add key (pos=%d)", pos);
563 expectedPos = pos;
564
565 pos = rte_hash_del_key_with_hash(handle, &keys[0], hash_value);
566 print_key_info("Del", &keys[0], pos);
567 RETURN_IF_ERROR(pos != expectedPos,
568 "failed to delete key (pos=%d)", pos);
569 delPos = pos;
570
571 pos = rte_hash_free_key_with_position(handle, delPos);
572 print_key_info("Free", &keys[0], delPos);
573 RETURN_IF_ERROR(pos != 0,
574 "failed to free key (pos=%d)", delPos);
575 }
576 keys[0].ip_src = ip_src;
577
578 rte_hash_free(handle);
579
580 return 0;
581 }
582
583 /*
584 * Sequence of operations for retrieving a key with its position
585 *
586 * - create table
587 * - add key
588 * - get the key with its position: hit
589 * - delete key
590 * - try to get the deleted key: miss
591 *
592 * Repeat the test case when 'free on delete' is disabled.
593 * - create table
594 * - add key
595 * - get the key with its position: hit
596 * - delete key
597 * - try to get the deleted key: hit
598 * - free key
599 * - try to get the deleted key: miss
600 *
601 */
test_hash_get_key_with_position(void)602 static int test_hash_get_key_with_position(void)
603 {
604 struct rte_hash *handle = NULL;
605 int pos, expectedPos, delPos, result;
606 void *key;
607
608 ut_params.name = "hash_get_key_w_pos";
609 handle = rte_hash_create(&ut_params);
610 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
611
612 pos = rte_hash_add_key(handle, &keys[0]);
613 print_key_info("Add", &keys[0], pos);
614 RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
615 expectedPos = pos;
616
617 result = rte_hash_get_key_with_position(handle, pos, &key);
618 RETURN_IF_ERROR(result != 0, "error retrieving a key");
619
620 pos = rte_hash_del_key(handle, &keys[0]);
621 print_key_info("Del", &keys[0], pos);
622 RETURN_IF_ERROR(pos != expectedPos,
623 "failed to delete key (pos0=%d)", pos);
624
625 result = rte_hash_get_key_with_position(handle, pos, &key);
626 RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
627
628 rte_hash_free(handle);
629
630 ut_params.name = "hash_get_key_w_pos";
631 ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
632 handle = rte_hash_create(&ut_params);
633 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
634 ut_params.extra_flag = 0;
635
636 pos = rte_hash_add_key(handle, &keys[0]);
637 print_key_info("Add", &keys[0], pos);
638 RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
639 expectedPos = pos;
640
641 result = rte_hash_get_key_with_position(handle, pos, &key);
642 RETURN_IF_ERROR(result != 0, "error retrieving a key");
643
644 delPos = rte_hash_del_key(handle, &keys[0]);
645 print_key_info("Del", &keys[0], delPos);
646 RETURN_IF_ERROR(delPos != expectedPos,
647 "failed to delete key (pos0=%d)", delPos);
648
649 result = rte_hash_get_key_with_position(handle, delPos, &key);
650 RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
651
652 result = rte_hash_free_key_with_position(handle, delPos);
653 print_key_info("Free", &keys[0], delPos);
654 RETURN_IF_ERROR(result != 0,
655 "failed to free key (pos1=%d)", delPos);
656
657 result = rte_hash_get_key_with_position(handle, delPos, &key);
658 RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
659
660 rte_hash_free(handle);
661 return 0;
662 }
663
664 /*
665 * Sequence of operations for find existing hash table
666 *
667 * - create table
668 * - find existing table: hit
669 * - find non-existing table: miss
670 *
671 */
test_hash_find_existing(void)672 static int test_hash_find_existing(void)
673 {
674 struct rte_hash *handle = NULL, *result = NULL;
675
676 /* Create hash table. */
677 ut_params.name = "hash_find_existing";
678 handle = rte_hash_create(&ut_params);
679 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
680
681 /* Try to find existing hash table */
682 result = rte_hash_find_existing("hash_find_existing");
683 RETURN_IF_ERROR(result != handle, "could not find existing hash table");
684
685 /* Try to find non-existing hash table */
686 result = rte_hash_find_existing("hash_find_non_existing");
687 RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist");
688
689 /* Cleanup. */
690 rte_hash_free(handle);
691
692 return 0;
693 }
694
695 /*
696 * Sequence of operations for 5 keys
697 * - add keys
698 * - lookup keys: hit
699 * - add keys (update)
700 * - lookup keys: hit (updated data)
701 * - delete keys : hit
702 * - lookup keys: miss
703 */
test_five_keys(void)704 static int test_five_keys(void)
705 {
706 struct rte_hash *handle;
707 const void *key_array[5] = {0};
708 int pos[5];
709 int expected_pos[5];
710 unsigned i;
711 int ret;
712
713 ut_params.name = "test3";
714 handle = rte_hash_create(&ut_params);
715 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
716
717 /* Add */
718 for (i = 0; i < 5; i++) {
719 pos[i] = rte_hash_add_key(handle, &keys[i]);
720 print_key_info("Add", &keys[i], pos[i]);
721 RETURN_IF_ERROR(pos[i] < 0,
722 "failed to add key (pos[%u]=%d)", i, pos[i]);
723 expected_pos[i] = pos[i];
724 }
725
726 /* Lookup */
727 for(i = 0; i < 5; i++)
728 key_array[i] = &keys[i];
729
730 ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
731 if(ret == 0)
732 for(i = 0; i < 5; i++) {
733 print_key_info("Lkp", key_array[i], pos[i]);
734 RETURN_IF_ERROR(pos[i] != expected_pos[i],
735 "failed to find key (pos[%u]=%d)", i, pos[i]);
736 }
737
738 /* Add - update */
739 for (i = 0; i < 5; i++) {
740 pos[i] = rte_hash_add_key(handle, &keys[i]);
741 print_key_info("Add", &keys[i], pos[i]);
742 RETURN_IF_ERROR(pos[i] != expected_pos[i],
743 "failed to add key (pos[%u]=%d)", i, pos[i]);
744 }
745
746 /* Lookup */
747 for (i = 0; i < 5; i++) {
748 pos[i] = rte_hash_lookup(handle, &keys[i]);
749 print_key_info("Lkp", &keys[i], pos[i]);
750 RETURN_IF_ERROR(pos[i] != expected_pos[i],
751 "failed to find key (pos[%u]=%d)", i, pos[i]);
752 }
753
754 /* Delete */
755 for (i = 0; i < 5; i++) {
756 pos[i] = rte_hash_del_key(handle, &keys[i]);
757 print_key_info("Del", &keys[i], pos[i]);
758 RETURN_IF_ERROR(pos[i] != expected_pos[i],
759 "failed to delete key (pos[%u]=%d)", i, pos[i]);
760 }
761
762 /* Lookup */
763 for (i = 0; i < 5; i++) {
764 pos[i] = rte_hash_lookup(handle, &keys[i]);
765 print_key_info("Lkp", &keys[i], pos[i]);
766 RETURN_IF_ERROR(pos[i] != -ENOENT,
767 "found non-existent key (pos[%u]=%d)", i, pos[i]);
768 }
769
770 /* Lookup multi */
771 ret = rte_hash_lookup_bulk(handle, &key_array[0], 5, (int32_t *)pos);
772 if (ret == 0)
773 for (i = 0; i < 5; i++) {
774 print_key_info("Lkp", key_array[i], pos[i]);
775 RETURN_IF_ERROR(pos[i] != -ENOENT,
776 "found not-existent key (pos[%u]=%d)", i, pos[i]);
777 }
778
779 rte_hash_free(handle);
780
781 return 0;
782 }
783
784 /*
785 * Add keys to the same bucket until bucket full.
786 * - add 5 keys to the same bucket (hash created with 4 keys per bucket):
787 * first 4 successful, 5th successful, pushing existing item in bucket
788 * - lookup the 5 keys: 5 hits
789 * - add the 5 keys again: 5 OK
790 * - lookup the 5 keys: 5 hits (updated data)
791 * - delete the 5 keys: 5 OK
792 * - lookup the 5 keys: 5 misses
793 */
test_full_bucket(void)794 static int test_full_bucket(void)
795 {
796 struct rte_hash_parameters params_pseudo_hash = {
797 .name = "test4",
798 .entries = 64,
799 .key_len = sizeof(struct flow_key),
800 .hash_func = pseudo_hash,
801 .hash_func_init_val = 0,
802 .socket_id = 0,
803 };
804 struct rte_hash *handle;
805 int pos[5];
806 int expected_pos[5];
807 unsigned i;
808
809 handle = rte_hash_create(¶ms_pseudo_hash);
810 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
811
812 /* Fill bucket */
813 for (i = 0; i < 4; i++) {
814 pos[i] = rte_hash_add_key(handle, &keys[i]);
815 print_key_info("Add", &keys[i], pos[i]);
816 RETURN_IF_ERROR(pos[i] < 0,
817 "failed to add key (pos[%u]=%d)", i, pos[i]);
818 expected_pos[i] = pos[i];
819 }
820 /*
821 * This should work and will push one of the items
822 * in the bucket because it is full
823 */
824 pos[4] = rte_hash_add_key(handle, &keys[4]);
825 print_key_info("Add", &keys[4], pos[4]);
826 RETURN_IF_ERROR(pos[4] < 0,
827 "failed to add key (pos[4]=%d)", pos[4]);
828 expected_pos[4] = pos[4];
829
830 /* Lookup */
831 for (i = 0; i < 5; i++) {
832 pos[i] = rte_hash_lookup(handle, &keys[i]);
833 print_key_info("Lkp", &keys[i], pos[i]);
834 RETURN_IF_ERROR(pos[i] != expected_pos[i],
835 "failed to find key (pos[%u]=%d)", i, pos[i]);
836 }
837
838 /* Add - update */
839 for (i = 0; i < 5; i++) {
840 pos[i] = rte_hash_add_key(handle, &keys[i]);
841 print_key_info("Add", &keys[i], pos[i]);
842 RETURN_IF_ERROR(pos[i] != expected_pos[i],
843 "failed to add key (pos[%u]=%d)", i, pos[i]);
844 }
845
846 /* Lookup */
847 for (i = 0; i < 5; i++) {
848 pos[i] = rte_hash_lookup(handle, &keys[i]);
849 print_key_info("Lkp", &keys[i], pos[i]);
850 RETURN_IF_ERROR(pos[i] != expected_pos[i],
851 "failed to find key (pos[%u]=%d)", i, pos[i]);
852 }
853
854 /* Delete 1 key, check other keys are still found */
855 pos[1] = rte_hash_del_key(handle, &keys[1]);
856 print_key_info("Del", &keys[1], pos[1]);
857 RETURN_IF_ERROR(pos[1] != expected_pos[1],
858 "failed to delete key (pos[1]=%d)", pos[1]);
859 pos[3] = rte_hash_lookup(handle, &keys[3]);
860 print_key_info("Lkp", &keys[3], pos[3]);
861 RETURN_IF_ERROR(pos[3] != expected_pos[3],
862 "failed lookup after deleting key from same bucket "
863 "(pos[3]=%d)", pos[3]);
864
865 /* Go back to previous state */
866 pos[1] = rte_hash_add_key(handle, &keys[1]);
867 print_key_info("Add", &keys[1], pos[1]);
868 expected_pos[1] = pos[1];
869 RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]);
870
871 /* Delete */
872 for (i = 0; i < 5; i++) {
873 pos[i] = rte_hash_del_key(handle, &keys[i]);
874 print_key_info("Del", &keys[i], pos[i]);
875 RETURN_IF_ERROR(pos[i] != expected_pos[i],
876 "failed to delete key (pos[%u]=%d)", i, pos[i]);
877 }
878
879 /* Lookup */
880 for (i = 0; i < 5; i++) {
881 pos[i] = rte_hash_lookup(handle, &keys[i]);
882 print_key_info("Lkp", &keys[i], pos[i]);
883 RETURN_IF_ERROR(pos[i] != -ENOENT,
884 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
885 }
886
887 rte_hash_free(handle);
888
889 /* Cover the NULL case. */
890 rte_hash_free(0);
891 return 0;
892 }
893
894 /*
895 * Similar to the test above (full bucket test), but for extendable buckets.
896 */
test_extendable_bucket(void)897 static int test_extendable_bucket(void)
898 {
899 struct rte_hash_parameters params_pseudo_hash = {
900 .name = "test5",
901 .entries = 64,
902 .key_len = sizeof(struct flow_key),
903 .hash_func = pseudo_hash,
904 .hash_func_init_val = 0,
905 .socket_id = 0,
906 .extra_flag = RTE_HASH_EXTRA_FLAGS_EXT_TABLE
907 };
908 struct rte_hash *handle;
909 int pos[64];
910 int expected_pos[64];
911 unsigned int i;
912 struct flow_key rand_keys[64];
913
914 for (i = 0; i < 64; i++) {
915 rand_keys[i].port_dst = i;
916 rand_keys[i].port_src = i+1;
917 }
918
919 handle = rte_hash_create(¶ms_pseudo_hash);
920 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
921
922 /* Fill bucket */
923 for (i = 0; i < 64; i++) {
924 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
925 print_key_info("Add", &rand_keys[i], pos[i]);
926 RETURN_IF_ERROR(pos[i] < 0,
927 "failed to add key (pos[%u]=%d)", i, pos[i]);
928 expected_pos[i] = pos[i];
929 }
930
931 /* Lookup */
932 for (i = 0; i < 64; i++) {
933 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
934 print_key_info("Lkp", &rand_keys[i], pos[i]);
935 RETURN_IF_ERROR(pos[i] != expected_pos[i],
936 "failed to find key (pos[%u]=%d)", i, pos[i]);
937 }
938
939 /* Add - update */
940 for (i = 0; i < 64; i++) {
941 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
942 print_key_info("Add", &rand_keys[i], pos[i]);
943 RETURN_IF_ERROR(pos[i] != expected_pos[i],
944 "failed to add key (pos[%u]=%d)", i, pos[i]);
945 }
946
947 /* Lookup */
948 for (i = 0; i < 64; i++) {
949 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
950 print_key_info("Lkp", &rand_keys[i], pos[i]);
951 RETURN_IF_ERROR(pos[i] != expected_pos[i],
952 "failed to find key (pos[%u]=%d)", i, pos[i]);
953 }
954
955 /* Delete 1 key, check other keys are still found */
956 pos[35] = rte_hash_del_key(handle, &rand_keys[35]);
957 print_key_info("Del", &rand_keys[35], pos[35]);
958 RETURN_IF_ERROR(pos[35] != expected_pos[35],
959 "failed to delete key (pos[1]=%d)", pos[35]);
960 pos[20] = rte_hash_lookup(handle, &rand_keys[20]);
961 print_key_info("Lkp", &rand_keys[20], pos[20]);
962 RETURN_IF_ERROR(pos[20] != expected_pos[20],
963 "failed lookup after deleting key from same bucket "
964 "(pos[20]=%d)", pos[20]);
965
966 /* Go back to previous state */
967 pos[35] = rte_hash_add_key(handle, &rand_keys[35]);
968 print_key_info("Add", &rand_keys[35], pos[35]);
969 expected_pos[35] = pos[35];
970 RETURN_IF_ERROR(pos[35] < 0, "failed to add key (pos[1]=%d)", pos[35]);
971
972 /* Delete */
973 for (i = 0; i < 64; i++) {
974 pos[i] = rte_hash_del_key(handle, &rand_keys[i]);
975 print_key_info("Del", &rand_keys[i], pos[i]);
976 RETURN_IF_ERROR(pos[i] != expected_pos[i],
977 "failed to delete key (pos[%u]=%d)", i, pos[i]);
978 }
979
980 /* Lookup */
981 for (i = 0; i < 64; i++) {
982 pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
983 print_key_info("Lkp", &rand_keys[i], pos[i]);
984 RETURN_IF_ERROR(pos[i] != -ENOENT,
985 "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
986 }
987
988 /* Add again */
989 for (i = 0; i < 64; i++) {
990 pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
991 print_key_info("Add", &rand_keys[i], pos[i]);
992 RETURN_IF_ERROR(pos[i] < 0,
993 "failed to add key (pos[%u]=%d)", i, pos[i]);
994 expected_pos[i] = pos[i];
995 }
996
997 rte_hash_free(handle);
998
999 /* Cover the NULL case. */
1000 rte_hash_free(0);
1001 return 0;
1002 }
1003
1004 /******************************************************************************/
1005 static int
fbk_hash_unit_test(void)1006 fbk_hash_unit_test(void)
1007 {
1008 struct rte_fbk_hash_params params = {
1009 .name = "fbk_hash_test",
1010 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1011 .entries_per_bucket = 4,
1012 .socket_id = 0,
1013 };
1014
1015 struct rte_fbk_hash_params invalid_params_1 = {
1016 .name = "invalid_1",
1017 .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */
1018 .entries_per_bucket = 4,
1019 .socket_id = 0,
1020 };
1021
1022 struct rte_fbk_hash_params invalid_params_2 = {
1023 .name = "invalid_2",
1024 .entries = 4,
1025 .entries_per_bucket = 3, /* Not power of 2 */
1026 .socket_id = 0,
1027 };
1028
1029 struct rte_fbk_hash_params invalid_params_3 = {
1030 .name = "invalid_3",
1031 .entries = 0, /* Entries is 0 */
1032 .entries_per_bucket = 4,
1033 .socket_id = 0,
1034 };
1035
1036 struct rte_fbk_hash_params invalid_params_4 = {
1037 .name = "invalid_4",
1038 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1039 .entries_per_bucket = 0, /* Entries per bucket is 0 */
1040 .socket_id = 0,
1041 };
1042
1043 struct rte_fbk_hash_params invalid_params_5 = {
1044 .name = "invalid_5",
1045 .entries = 4,
1046 .entries_per_bucket = 8, /* Entries per bucket > entries */
1047 .socket_id = 0,
1048 };
1049
1050 struct rte_fbk_hash_params invalid_params_6 = {
1051 .name = "invalid_6",
1052 .entries = RTE_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */
1053 .entries_per_bucket = 4,
1054 .socket_id = 0,
1055 };
1056
1057 struct rte_fbk_hash_params invalid_params_7 = {
1058 .name = "invalid_7",
1059 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1060 .entries_per_bucket = RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */
1061 .socket_id = 0,
1062 };
1063
1064 struct rte_fbk_hash_params invalid_params_8 = {
1065 .name = "invalid_7",
1066 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1067 .entries_per_bucket = 4,
1068 .socket_id = RTE_MAX_NUMA_NODES + 1, /* invalid socket */
1069 };
1070
1071 /* try to create two hashes with identical names
1072 * in this case, trying to create a second one will not
1073 * fail but will simply return pointer to the existing
1074 * hash with that name. sort of like a "find hash by name" :-)
1075 */
1076 struct rte_fbk_hash_params invalid_params_same_name_1 = {
1077 .name = "same_name", /* hash with identical name */
1078 .entries = 4,
1079 .entries_per_bucket = 2,
1080 .socket_id = 0,
1081 };
1082
1083 /* trying to create this hash should return a pointer to an existing hash */
1084 struct rte_fbk_hash_params invalid_params_same_name_2 = {
1085 .name = "same_name", /* hash with identical name */
1086 .entries = RTE_FBK_HASH_ENTRIES_MAX,
1087 .entries_per_bucket = 4,
1088 .socket_id = 0,
1089 };
1090
1091 /* this is a sanity check for "same name" test
1092 * creating this hash will check if we are actually able to create
1093 * multiple hashes with different names (instead of having just one).
1094 */
1095 struct rte_fbk_hash_params different_name = {
1096 .name = "different_name", /* different name */
1097 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1098 .entries_per_bucket = 4,
1099 .socket_id = 0,
1100 };
1101
1102 struct rte_fbk_hash_params params_jhash = {
1103 .name = "valid",
1104 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1105 .entries_per_bucket = 4,
1106 .socket_id = 0,
1107 .hash_func = rte_jhash_1word, /* Tests for different hash_func */
1108 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1109 };
1110
1111 struct rte_fbk_hash_params params_nohash = {
1112 .name = "valid nohash",
1113 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1114 .entries_per_bucket = 4,
1115 .socket_id = 0,
1116 .hash_func = NULL, /* Tests for null hash_func */
1117 .init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT,
1118 };
1119
1120 struct rte_fbk_hash_table *handle, *tmp;
1121 uint32_t keys[5] =
1122 {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9};
1123 uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571};
1124 int status;
1125 unsigned i;
1126 double used_entries;
1127
1128 /* Try creating hashes with invalid parameters */
1129 printf("# Testing hash creation with invalid parameters "
1130 "- expect error msgs\n");
1131 handle = rte_fbk_hash_create(&invalid_params_1);
1132 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1133
1134 handle = rte_fbk_hash_create(&invalid_params_2);
1135 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1136
1137 handle = rte_fbk_hash_create(&invalid_params_3);
1138 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1139
1140 handle = rte_fbk_hash_create(&invalid_params_4);
1141 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1142
1143 handle = rte_fbk_hash_create(&invalid_params_5);
1144 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1145
1146 handle = rte_fbk_hash_create(&invalid_params_6);
1147 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1148
1149 handle = rte_fbk_hash_create(&invalid_params_7);
1150 RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed");
1151
1152 if (rte_eal_has_hugepages()) {
1153 handle = rte_fbk_hash_create(&invalid_params_8);
1154 RETURN_IF_ERROR_FBK(handle != NULL,
1155 "fbk hash creation should have failed");
1156 }
1157
1158 handle = rte_fbk_hash_create(&invalid_params_same_name_1);
1159 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded");
1160
1161 tmp = rte_fbk_hash_create(&invalid_params_same_name_2);
1162 if (tmp != NULL)
1163 rte_fbk_hash_free(tmp);
1164 RETURN_IF_ERROR_FBK(tmp != NULL, "fbk hash creation should have failed");
1165
1166 /* we are not freeing handle here because we need a hash list
1167 * to be not empty for the next test */
1168
1169 /* create a hash in non-empty list - good for coverage */
1170 tmp = rte_fbk_hash_create(&different_name);
1171 RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded");
1172
1173 /* free both hashes */
1174 rte_fbk_hash_free(handle);
1175 rte_fbk_hash_free(tmp);
1176
1177 /* Create empty jhash hash. */
1178 handle = rte_fbk_hash_create(¶ms_jhash);
1179 RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed");
1180
1181 /* Cleanup. */
1182 rte_fbk_hash_free(handle);
1183
1184 /* Create empty jhash hash. */
1185 handle = rte_fbk_hash_create(¶ms_nohash);
1186 RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed");
1187
1188 /* Cleanup. */
1189 rte_fbk_hash_free(handle);
1190
1191 /* Create empty hash. */
1192 handle = rte_fbk_hash_create(¶ms);
1193 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1194
1195 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1196 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1197 "load factor right after creation is not zero but it should be");
1198 /* Add keys. */
1199 for (i = 0; i < 5; i++) {
1200 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1201 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1202 }
1203
1204 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1205 RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \
1206 "load factor now is not as expected");
1207 /* Find value of added keys. */
1208 for (i = 0; i < 5; i++) {
1209 status = rte_fbk_hash_lookup(handle, keys[i]);
1210 RETURN_IF_ERROR_FBK(status != vals[i],
1211 "fbk hash lookup failed");
1212 }
1213
1214 /* Change value of added keys. */
1215 for (i = 0; i < 5; i++) {
1216 status = rte_fbk_hash_add_key(handle, keys[i], vals[4 - i]);
1217 RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed");
1218 }
1219
1220 /* Find new values. */
1221 for (i = 0; i < 5; i++) {
1222 status = rte_fbk_hash_lookup(handle, keys[i]);
1223 RETURN_IF_ERROR_FBK(status != vals[4-i],
1224 "fbk hash lookup failed");
1225 }
1226
1227 /* Delete keys individually. */
1228 for (i = 0; i < 5; i++) {
1229 status = rte_fbk_hash_delete_key(handle, keys[i]);
1230 RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed");
1231 }
1232
1233 used_entries = rte_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX;
1234 RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \
1235 "load factor right after deletion is not zero but it should be");
1236 /* Lookup should now fail. */
1237 for (i = 0; i < 5; i++) {
1238 status = rte_fbk_hash_lookup(handle, keys[i]);
1239 RETURN_IF_ERROR_FBK(status == 0,
1240 "fbk hash lookup should have failed");
1241 }
1242
1243 /* Add keys again. */
1244 for (i = 0; i < 5; i++) {
1245 status = rte_fbk_hash_add_key(handle, keys[i], vals[i]);
1246 RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed");
1247 }
1248
1249 /* Make sure they were added. */
1250 for (i = 0; i < 5; i++) {
1251 status = rte_fbk_hash_lookup(handle, keys[i]);
1252 RETURN_IF_ERROR_FBK(status != vals[i],
1253 "fbk hash lookup failed");
1254 }
1255
1256 /* Clear all entries. */
1257 rte_fbk_hash_clear_all(handle);
1258
1259 /* Lookup should fail. */
1260 for (i = 0; i < 5; i++) {
1261 status = rte_fbk_hash_lookup(handle, keys[i]);
1262 RETURN_IF_ERROR_FBK(status == 0,
1263 "fbk hash lookup should have failed");
1264 }
1265
1266 /* coverage */
1267
1268 /* fill up the hash_table */
1269 for (i = 0; i < RTE_FBK_HASH_ENTRIES_MAX + 1; i++)
1270 rte_fbk_hash_add_key(handle, i, (uint16_t) i);
1271
1272 /* Find non-existent key in a full hashtable */
1273 status = rte_fbk_hash_lookup(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
1274 RETURN_IF_ERROR_FBK(status != -ENOENT,
1275 "fbk hash lookup succeeded");
1276
1277 /* Delete non-existent key in a full hashtable */
1278 status = rte_fbk_hash_delete_key(handle, RTE_FBK_HASH_ENTRIES_MAX + 1);
1279 RETURN_IF_ERROR_FBK(status != -ENOENT,
1280 "fbk hash delete succeeded");
1281
1282 /* Delete one key from a full hashtable */
1283 status = rte_fbk_hash_delete_key(handle, 1);
1284 RETURN_IF_ERROR_FBK(status != 0,
1285 "fbk hash delete failed");
1286
1287 /* Clear all entries. */
1288 rte_fbk_hash_clear_all(handle);
1289
1290 /* Cleanup. */
1291 rte_fbk_hash_free(handle);
1292
1293 /* Cover the NULL case. */
1294 rte_fbk_hash_free(0);
1295
1296 return 0;
1297 }
1298
1299 /*
1300 * Sequence of operations for find existing fbk hash table
1301 *
1302 * - create table
1303 * - find existing table: hit
1304 * - find non-existing table: miss
1305 *
1306 */
test_fbk_hash_find_existing(void)1307 static int test_fbk_hash_find_existing(void)
1308 {
1309 struct rte_fbk_hash_params params = {
1310 .name = "fbk_hash_find_existing",
1311 .entries = LOCAL_FBK_HASH_ENTRIES_MAX,
1312 .entries_per_bucket = 4,
1313 .socket_id = 0,
1314 };
1315 struct rte_fbk_hash_table *handle = NULL, *result = NULL;
1316
1317 /* Create hash table. */
1318 handle = rte_fbk_hash_create(¶ms);
1319 RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed");
1320
1321 /* Try to find existing fbk hash table */
1322 result = rte_fbk_hash_find_existing("fbk_hash_find_existing");
1323 RETURN_IF_ERROR_FBK(result != handle, "could not find existing fbk hash table");
1324
1325 /* Try to find non-existing fbk hash table */
1326 result = rte_fbk_hash_find_existing("fbk_hash_find_non_existing");
1327 RETURN_IF_ERROR_FBK(!(result == NULL), "found fbk table that shouldn't exist");
1328
1329 /* Cleanup. */
1330 rte_fbk_hash_free(handle);
1331
1332 return 0;
1333 }
1334
1335 #define BUCKET_ENTRIES 4
1336 /*
1337 * Do tests for hash creation with bad parameters.
1338 */
test_hash_creation_with_bad_parameters(void)1339 static int test_hash_creation_with_bad_parameters(void)
1340 {
1341 struct rte_hash *handle, *tmp;
1342 struct rte_hash_parameters params;
1343
1344 handle = rte_hash_create(NULL);
1345 if (handle != NULL) {
1346 rte_hash_free(handle);
1347 printf("Impossible creating hash successfully without any parameter\n");
1348 return -1;
1349 }
1350
1351 memcpy(¶ms, &ut_params, sizeof(params));
1352 params.name = "creation_with_bad_parameters_0";
1353 params.entries = RTE_HASH_ENTRIES_MAX + 1;
1354 handle = rte_hash_create(¶ms);
1355 if (handle != NULL) {
1356 rte_hash_free(handle);
1357 printf("Impossible creating hash successfully with entries in parameter exceeded\n");
1358 return -1;
1359 }
1360
1361 memcpy(¶ms, &ut_params, sizeof(params));
1362 params.name = "creation_with_bad_parameters_2";
1363 params.entries = BUCKET_ENTRIES - 1;
1364 handle = rte_hash_create(¶ms);
1365 if (handle != NULL) {
1366 rte_hash_free(handle);
1367 printf("Impossible creating hash successfully if entries less than bucket_entries in parameter\n");
1368 return -1;
1369 }
1370
1371 memcpy(¶ms, &ut_params, sizeof(params));
1372 params.name = "creation_with_bad_parameters_3";
1373 params.key_len = 0;
1374 handle = rte_hash_create(¶ms);
1375 if (handle != NULL) {
1376 rte_hash_free(handle);
1377 printf("Impossible creating hash successfully if key_len in parameter is zero\n");
1378 return -1;
1379 }
1380
1381 memcpy(¶ms, &ut_params, sizeof(params));
1382 params.name = "creation_with_bad_parameters_4";
1383 params.socket_id = RTE_MAX_NUMA_NODES + 1;
1384 handle = rte_hash_create(¶ms);
1385 if (handle != NULL) {
1386 rte_hash_free(handle);
1387 printf("Impossible creating hash successfully with invalid socket\n");
1388 return -1;
1389 }
1390
1391 /* test with same name should fail */
1392 memcpy(¶ms, &ut_params, sizeof(params));
1393 params.name = "same_name";
1394 handle = rte_hash_create(¶ms);
1395 if (handle == NULL) {
1396 printf("Cannot create first hash table with 'same_name'\n");
1397 return -1;
1398 }
1399 tmp = rte_hash_create(¶ms);
1400 if (tmp != NULL) {
1401 printf("Creation of hash table with same name should fail\n");
1402 rte_hash_free(handle);
1403 rte_hash_free(tmp);
1404 return -1;
1405 }
1406 rte_hash_free(handle);
1407
1408 printf("# Test successful. No more errors expected\n");
1409
1410 return 0;
1411 }
1412
1413 /*
1414 * Do tests for hash creation with parameters that look incorrect
1415 * but are actually valid.
1416 */
1417 static int
test_hash_creation_with_good_parameters(void)1418 test_hash_creation_with_good_parameters(void)
1419 {
1420 struct rte_hash *handle;
1421 struct rte_hash_parameters params;
1422
1423 /* create with null hash function - should choose DEFAULT_HASH_FUNC */
1424 memcpy(¶ms, &ut_params, sizeof(params));
1425 params.name = "name";
1426 params.hash_func = NULL;
1427 handle = rte_hash_create(¶ms);
1428 if (handle == NULL) {
1429 printf("Creating hash with null hash_func failed\n");
1430 return -1;
1431 }
1432
1433 rte_hash_free(handle);
1434
1435 return 0;
1436 }
1437
1438 #define ITERATIONS 3
1439 /*
1440 * Test to see the average table utilization (entries added/max entries)
1441 * before hitting a random entry that cannot be added
1442 */
test_average_table_utilization(uint32_t ext_table)1443 static int test_average_table_utilization(uint32_t ext_table)
1444 {
1445 struct rte_hash *handle;
1446 uint8_t simple_key[MAX_KEYSIZE];
1447 unsigned i, j;
1448 unsigned added_keys, average_keys_added = 0;
1449 int ret;
1450 unsigned int cnt;
1451
1452 printf("\n# Running test to determine average utilization"
1453 "\n before adding elements begins to fail\n");
1454 if (ext_table)
1455 printf("ext table is enabled\n");
1456 else
1457 printf("ext table is disabled\n");
1458
1459 printf("Measuring performance, please wait");
1460 fflush(stdout);
1461 ut_params.entries = 1 << 16;
1462 ut_params.name = "test_average_utilization";
1463 ut_params.hash_func = rte_jhash;
1464 if (ext_table)
1465 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1466 else
1467 ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1468
1469 handle = rte_hash_create(&ut_params);
1470
1471 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1472
1473 for (j = 0; j < ITERATIONS; j++) {
1474 ret = 0;
1475 /* Add random entries until key cannot be added */
1476 for (added_keys = 0; ret >= 0; added_keys++) {
1477 for (i = 0; i < ut_params.key_len; i++)
1478 simple_key[i] = rte_rand() % 255;
1479 ret = rte_hash_add_key(handle, simple_key);
1480 if (ret < 0)
1481 break;
1482 }
1483
1484 if (ret != -ENOSPC) {
1485 printf("Unexpected error when adding keys\n");
1486 rte_hash_free(handle);
1487 return -1;
1488 }
1489
1490 cnt = rte_hash_count(handle);
1491 if (cnt != added_keys) {
1492 printf("rte_hash_count returned wrong value %u, %u,"
1493 "%u\n", j, added_keys, cnt);
1494 rte_hash_free(handle);
1495 return -1;
1496 }
1497 if (ext_table) {
1498 if (cnt != ut_params.entries) {
1499 printf("rte_hash_count returned wrong value "
1500 "%u, %u, %u\n", j, added_keys, cnt);
1501 rte_hash_free(handle);
1502 return -1;
1503 }
1504 }
1505
1506 average_keys_added += added_keys;
1507
1508 /* Reset the table */
1509 rte_hash_reset(handle);
1510
1511 /* Print a dot to show progress on operations */
1512 printf(".");
1513 fflush(stdout);
1514 }
1515
1516 average_keys_added /= ITERATIONS;
1517
1518 printf("\nAverage table utilization = %.2f%% (%u/%u)\n",
1519 ((double) average_keys_added / ut_params.entries * 100),
1520 average_keys_added, ut_params.entries);
1521 rte_hash_free(handle);
1522
1523 return 0;
1524 }
1525
1526 #define NUM_ENTRIES 256
test_hash_iteration(uint32_t ext_table)1527 static int test_hash_iteration(uint32_t ext_table)
1528 {
1529 struct rte_hash *handle;
1530 unsigned i;
1531 uint8_t keys[NUM_ENTRIES][MAX_KEYSIZE];
1532 const void *next_key;
1533 void *next_data;
1534 void *data[NUM_ENTRIES];
1535 unsigned added_keys;
1536 uint32_t iter = 0;
1537 int ret = 0;
1538
1539 ut_params.entries = NUM_ENTRIES;
1540 ut_params.name = "test_hash_iteration";
1541 ut_params.hash_func = rte_jhash;
1542 ut_params.key_len = 16;
1543 if (ext_table)
1544 ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1545 else
1546 ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1547
1548 handle = rte_hash_create(&ut_params);
1549 RETURN_IF_ERROR(handle == NULL, "hash creation failed");
1550
1551 /* Add random entries until key cannot be added */
1552 for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) {
1553 data[added_keys] = (void *) ((uintptr_t) rte_rand());
1554 for (i = 0; i < ut_params.key_len; i++)
1555 keys[added_keys][i] = rte_rand() % 255;
1556 ret = rte_hash_add_key_data(handle, keys[added_keys], data[added_keys]);
1557 if (ret < 0) {
1558 if (ext_table) {
1559 printf("Insertion failed for ext table\n");
1560 goto err;
1561 }
1562 break;
1563 }
1564 }
1565
1566 /* Iterate through the hash table */
1567 while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) {
1568 /* Search for the key in the list of keys added */
1569 for (i = 0; i < NUM_ENTRIES; i++) {
1570 if (memcmp(next_key, keys[i], ut_params.key_len) == 0) {
1571 if (next_data != data[i]) {
1572 printf("Data found in the hash table is"
1573 "not the data added with the key\n");
1574 goto err;
1575 }
1576 added_keys--;
1577 break;
1578 }
1579 }
1580 if (i == NUM_ENTRIES) {
1581 printf("Key found in the hash table was not added\n");
1582 goto err;
1583 }
1584 }
1585
1586 /* Check if all keys have been iterated */
1587 if (added_keys != 0) {
1588 printf("There were still %u keys to iterate\n", added_keys);
1589 goto err;
1590 }
1591
1592 rte_hash_free(handle);
1593 return 0;
1594
1595 err:
1596 rte_hash_free(handle);
1597 return -1;
1598 }
1599
1600 static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,
1601 0x04, 0x05, 0x06, 0x07,
1602 0x08, 0x09, 0x0a, 0x0b,
1603 0x0c, 0x0d, 0x0e, 0x0f};
1604 static struct rte_hash_parameters hash_params_ex = {
1605 .name = NULL,
1606 .entries = 64,
1607 .key_len = 0,
1608 .hash_func = NULL,
1609 .hash_func_init_val = 0,
1610 .socket_id = 0,
1611 };
1612
1613 /*
1614 * Wrapper function around rte_jhash_32b.
1615 * It is required because rte_jhash_32b() accepts the length
1616 * as size of 4-byte units.
1617 */
1618 static inline uint32_t
test_jhash_32b(const void * k,uint32_t length,uint32_t initval)1619 test_jhash_32b(const void *k, uint32_t length, uint32_t initval)
1620 {
1621 return rte_jhash_32b(k, length >> 2, initval);
1622 }
1623
1624 /*
1625 * add/delete key with jhash2
1626 */
1627 static int
test_hash_add_delete_jhash2(void)1628 test_hash_add_delete_jhash2(void)
1629 {
1630 int ret = -1;
1631 struct rte_hash *handle;
1632 int32_t pos1, pos2;
1633
1634 hash_params_ex.name = "hash_test_jhash2";
1635 hash_params_ex.key_len = 4;
1636 hash_params_ex.hash_func = (rte_hash_function)test_jhash_32b;
1637
1638 handle = rte_hash_create(&hash_params_ex);
1639 if (handle == NULL) {
1640 printf("test_hash_add_delete_jhash2 fail to create hash\n");
1641 goto fail_jhash2;
1642 }
1643 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1644 if (pos1 < 0) {
1645 printf("test_hash_add_delete_jhash2 fail to add hash key\n");
1646 goto fail_jhash2;
1647 }
1648
1649 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1650 if (pos2 < 0 || pos1 != pos2) {
1651 printf("test_hash_add_delete_jhash2 delete different key from being added\n");
1652 goto fail_jhash2;
1653 }
1654 ret = 0;
1655
1656 fail_jhash2:
1657 rte_hash_free(handle);
1658
1659 return ret;
1660 }
1661
1662 /*
1663 * add/delete (2) key with jhash2
1664 */
1665 static int
test_hash_add_delete_2_jhash2(void)1666 test_hash_add_delete_2_jhash2(void)
1667 {
1668 int ret = -1;
1669 struct rte_hash *handle;
1670 int32_t pos1, pos2;
1671
1672 hash_params_ex.name = "hash_test_2_jhash2";
1673 hash_params_ex.key_len = 8;
1674 hash_params_ex.hash_func = (rte_hash_function)test_jhash_32b;
1675
1676 handle = rte_hash_create(&hash_params_ex);
1677 if (handle == NULL)
1678 goto fail_2_jhash2;
1679
1680 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1681 if (pos1 < 0)
1682 goto fail_2_jhash2;
1683
1684 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1685 if (pos2 < 0 || pos1 != pos2)
1686 goto fail_2_jhash2;
1687
1688 ret = 0;
1689
1690 fail_2_jhash2:
1691 rte_hash_free(handle);
1692
1693 return ret;
1694 }
1695
1696 static uint32_t
test_hash_jhash_1word(const void * key,uint32_t length,uint32_t initval)1697 test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval)
1698 {
1699 const uint32_t *k = key;
1700
1701 RTE_SET_USED(length);
1702
1703 return rte_jhash_1word(k[0], initval);
1704 }
1705
1706 static uint32_t
test_hash_jhash_2word(const void * key,uint32_t length,uint32_t initval)1707 test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval)
1708 {
1709 const uint32_t *k = key;
1710
1711 RTE_SET_USED(length);
1712
1713 return rte_jhash_2words(k[0], k[1], initval);
1714 }
1715
1716 static uint32_t
test_hash_jhash_3word(const void * key,uint32_t length,uint32_t initval)1717 test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval)
1718 {
1719 const uint32_t *k = key;
1720
1721 RTE_SET_USED(length);
1722
1723 return rte_jhash_3words(k[0], k[1], k[2], initval);
1724 }
1725
1726 /*
1727 * add/delete key with jhash 1word
1728 */
1729 static int
test_hash_add_delete_jhash_1word(void)1730 test_hash_add_delete_jhash_1word(void)
1731 {
1732 int ret = -1;
1733 struct rte_hash *handle;
1734 int32_t pos1, pos2;
1735
1736 hash_params_ex.name = "hash_test_jhash_1word";
1737 hash_params_ex.key_len = 4;
1738 hash_params_ex.hash_func = test_hash_jhash_1word;
1739
1740 handle = rte_hash_create(&hash_params_ex);
1741 if (handle == NULL)
1742 goto fail_jhash_1word;
1743
1744 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1745 if (pos1 < 0)
1746 goto fail_jhash_1word;
1747
1748 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1749 if (pos2 < 0 || pos1 != pos2)
1750 goto fail_jhash_1word;
1751
1752 ret = 0;
1753
1754 fail_jhash_1word:
1755 rte_hash_free(handle);
1756
1757 return ret;
1758 }
1759
1760 /*
1761 * add/delete key with jhash 2word
1762 */
1763 static int
test_hash_add_delete_jhash_2word(void)1764 test_hash_add_delete_jhash_2word(void)
1765 {
1766 int ret = -1;
1767 struct rte_hash *handle;
1768 int32_t pos1, pos2;
1769
1770 hash_params_ex.name = "hash_test_jhash_2word";
1771 hash_params_ex.key_len = 8;
1772 hash_params_ex.hash_func = test_hash_jhash_2word;
1773
1774 handle = rte_hash_create(&hash_params_ex);
1775 if (handle == NULL)
1776 goto fail_jhash_2word;
1777
1778 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1779 if (pos1 < 0)
1780 goto fail_jhash_2word;
1781
1782 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1783 if (pos2 < 0 || pos1 != pos2)
1784 goto fail_jhash_2word;
1785
1786 ret = 0;
1787
1788 fail_jhash_2word:
1789 rte_hash_free(handle);
1790
1791 return ret;
1792 }
1793
1794 /*
1795 * add/delete key with jhash 3word
1796 */
1797 static int
test_hash_add_delete_jhash_3word(void)1798 test_hash_add_delete_jhash_3word(void)
1799 {
1800 int ret = -1;
1801 struct rte_hash *handle;
1802 int32_t pos1, pos2;
1803
1804 hash_params_ex.name = "hash_test_jhash_3word";
1805 hash_params_ex.key_len = 12;
1806 hash_params_ex.hash_func = test_hash_jhash_3word;
1807
1808 handle = rte_hash_create(&hash_params_ex);
1809 if (handle == NULL)
1810 goto fail_jhash_3word;
1811
1812 pos1 = rte_hash_add_key(handle, (void *)&key[0]);
1813 if (pos1 < 0)
1814 goto fail_jhash_3word;
1815
1816 pos2 = rte_hash_del_key(handle, (void *)&key[0]);
1817 if (pos2 < 0 || pos1 != pos2)
1818 goto fail_jhash_3word;
1819
1820 ret = 0;
1821
1822 fail_jhash_3word:
1823 rte_hash_free(handle);
1824
1825 return ret;
1826 }
1827
1828 static struct rte_hash *g_handle;
1829 static struct rte_rcu_qsbr *g_qsv;
1830 static volatile uint8_t writer_done;
1831 struct flow_key g_rand_keys[9];
1832
1833 /*
1834 * rte_hash_rcu_qsbr_add positive and negative tests.
1835 * - Add RCU QSBR variable to Hash
1836 * - Add another RCU QSBR variable to Hash
1837 * - Check returns
1838 */
1839 static int
test_hash_rcu_qsbr_add(void)1840 test_hash_rcu_qsbr_add(void)
1841 {
1842 size_t sz;
1843 struct rte_rcu_qsbr *qsv2 = NULL;
1844 int32_t status;
1845 struct rte_hash_rcu_config rcu_cfg = {0};
1846 struct rte_hash_parameters params;
1847
1848 printf("\n# Running RCU QSBR add tests\n");
1849 memcpy(¶ms, &ut_params, sizeof(params));
1850 params.name = "test_hash_rcu_qsbr_add";
1851 params.extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF |
1852 RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD;
1853 g_handle = rte_hash_create(¶ms);
1854 RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
1855
1856 /* Create RCU QSBR variable */
1857 sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
1858 g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1859 RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1860 RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
1861 "RCU QSBR variable creation failed");
1862
1863 status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
1864 RETURN_IF_ERROR_RCU_QSBR(status != 0,
1865 "RCU QSBR variable initialization failed");
1866
1867 rcu_cfg.v = g_qsv;
1868 /* Invalid QSBR mode */
1869 rcu_cfg.mode = 0xff;
1870 status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1871 RETURN_IF_ERROR_RCU_QSBR(status == 0, "Invalid QSBR mode test failed");
1872
1873 rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ;
1874 /* Attach RCU QSBR to hash table */
1875 status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1876 RETURN_IF_ERROR_RCU_QSBR(status != 0,
1877 "Attach RCU QSBR to hash table failed");
1878
1879 /* Create and attach another RCU QSBR to hash table */
1880 qsv2 = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1881 RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1882 RETURN_IF_ERROR_RCU_QSBR(qsv2 == NULL,
1883 "RCU QSBR variable creation failed");
1884
1885 rcu_cfg.v = qsv2;
1886 rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC;
1887 status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1888 rte_free(qsv2);
1889 RETURN_IF_ERROR_RCU_QSBR(status == 0,
1890 "Attach RCU QSBR to hash table succeeded where failure"
1891 " is expected");
1892
1893 rte_hash_free(g_handle);
1894 rte_free(g_qsv);
1895
1896 return 0;
1897 }
1898
1899 /*
1900 * rte_hash_rcu_qsbr_add DQ mode functional test.
1901 * Reader and writer are in the same thread in this test.
1902 * - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries
1903 * - Add RCU QSBR variable to hash
1904 * - Add 8 hash entries and fill the bucket
1905 * - If ext bkt is enabled, add 1 extra entry that is available in the ext bkt
1906 * - Register a reader thread (not a real thread)
1907 * - Reader lookup existing entry
1908 * - Writer deletes the entry
1909 * - Reader lookup the entry
1910 * - Writer re-add the entry (no available free index)
1911 * - Reader report quiescent state and unregister
1912 * - Writer re-add the entry
1913 * - Reader lookup the entry
1914 */
1915 static int
test_hash_rcu_qsbr_dq_mode(uint8_t ext_bkt)1916 test_hash_rcu_qsbr_dq_mode(uint8_t ext_bkt)
1917 {
1918 uint32_t total_entries = (ext_bkt == 0) ? 8 : 9;
1919
1920 uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
1921
1922 if (ext_bkt)
1923 hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
1924
1925 struct rte_hash_parameters params_pseudo_hash = {
1926 .name = "test_hash_rcu_qsbr_dq_mode",
1927 .entries = total_entries,
1928 .key_len = sizeof(struct flow_key),
1929 .hash_func = pseudo_hash,
1930 .hash_func_init_val = 0,
1931 .socket_id = 0,
1932 .extra_flag = hash_extra_flag,
1933 };
1934 int pos[total_entries];
1935 int expected_pos[total_entries];
1936 unsigned int i;
1937 size_t sz;
1938 int32_t status;
1939 struct rte_hash_rcu_config rcu_cfg = {0};
1940
1941 g_qsv = NULL;
1942 g_handle = NULL;
1943
1944 for (i = 0; i < total_entries; i++) {
1945 g_rand_keys[i].port_dst = i;
1946 g_rand_keys[i].port_src = i+1;
1947 }
1948
1949 if (ext_bkt)
1950 printf("\n# Running RCU QSBR DQ mode functional test with"
1951 " ext bkt\n");
1952 else
1953 printf("\n# Running RCU QSBR DQ mode functional test\n");
1954
1955 g_handle = rte_hash_create(¶ms_pseudo_hash);
1956 RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
1957
1958 /* Create RCU QSBR variable */
1959 sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
1960 g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
1961 RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
1962 RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
1963 "RCU QSBR variable creation failed");
1964
1965 status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
1966 RETURN_IF_ERROR_RCU_QSBR(status != 0,
1967 "RCU QSBR variable initialization failed");
1968
1969 rcu_cfg.v = g_qsv;
1970 rcu_cfg.mode = RTE_HASH_QSBR_MODE_DQ;
1971 /* Attach RCU QSBR to hash table */
1972 status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
1973 RETURN_IF_ERROR_RCU_QSBR(status != 0,
1974 "Attach RCU QSBR to hash table failed");
1975
1976 /* Fill bucket */
1977 for (i = 0; i < total_entries; i++) {
1978 pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]);
1979 print_key_info("Add", &g_rand_keys[i], pos[i]);
1980 RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0,
1981 "failed to add key (pos[%u]=%d)", i,
1982 pos[i]);
1983 expected_pos[i] = pos[i];
1984 }
1985
1986 /* Register pseudo reader */
1987 status = rte_rcu_qsbr_thread_register(g_qsv, 0);
1988 RETURN_IF_ERROR_RCU_QSBR(status != 0,
1989 "RCU QSBR thread registration failed");
1990 rte_rcu_qsbr_thread_online(g_qsv, 0);
1991
1992 /* Lookup */
1993 pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
1994 print_key_info("Lkp", &g_rand_keys[0], pos[0]);
1995 RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
1996 "failed to find correct key (pos[%u]=%d)", 0,
1997 pos[0]);
1998
1999 /* Writer update */
2000 pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]);
2001 print_key_info("Del", &g_rand_keys[0], pos[0]);
2002 RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2003 "failed to del correct key (pos[%u]=%d)", 0,
2004 pos[0]);
2005
2006 /* Lookup */
2007 pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
2008 print_key_info("Lkp", &g_rand_keys[0], pos[0]);
2009 RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOENT,
2010 "found deleted key (pos[%u]=%d)", 0, pos[0]);
2011
2012 /* Fill bucket */
2013 pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2014 print_key_info("Add", &g_rand_keys[0], pos[0]);
2015 RETURN_IF_ERROR_RCU_QSBR(pos[0] != -ENOSPC,
2016 "Added key successfully (pos[%u]=%d)", 0, pos[0]);
2017
2018 /* Reader quiescent */
2019 rte_rcu_qsbr_quiescent(g_qsv, 0);
2020
2021 /* Fill bucket */
2022 pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2023 print_key_info("Add", &g_rand_keys[0], pos[0]);
2024 RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0,
2025 "failed to add key (pos[%u]=%d)", 0, pos[0]);
2026 expected_pos[0] = pos[0];
2027
2028 rte_rcu_qsbr_thread_offline(g_qsv, 0);
2029 (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0);
2030
2031 /* Lookup */
2032 pos[0] = rte_hash_lookup(g_handle, &g_rand_keys[0]);
2033 print_key_info("Lkp", &g_rand_keys[0], pos[0]);
2034 RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2035 "failed to find correct key (pos[%u]=%d)", 0,
2036 pos[0]);
2037
2038 rte_hash_free(g_handle);
2039 rte_free(g_qsv);
2040 return 0;
2041
2042 }
2043
2044 /* Report quiescent state interval every 1024 lookups. Larger critical
2045 * sections in reader will result in writer polling multiple times.
2046 */
2047 #define QSBR_REPORTING_INTERVAL 1024
2048 #define WRITER_ITERATIONS 512
2049
2050 /*
2051 * Reader thread using rte_hash data structure with RCU.
2052 */
2053 static int
test_hash_rcu_qsbr_reader(void * arg)2054 test_hash_rcu_qsbr_reader(void *arg)
2055 {
2056 int i;
2057
2058 RTE_SET_USED(arg);
2059 /* Register this thread to report quiescent state */
2060 (void)rte_rcu_qsbr_thread_register(g_qsv, 0);
2061 rte_rcu_qsbr_thread_online(g_qsv, 0);
2062
2063 do {
2064 for (i = 0; i < QSBR_REPORTING_INTERVAL; i++)
2065 rte_hash_lookup(g_handle, &g_rand_keys[0]);
2066
2067 /* Update quiescent state */
2068 rte_rcu_qsbr_quiescent(g_qsv, 0);
2069 } while (!writer_done);
2070
2071 rte_rcu_qsbr_thread_offline(g_qsv, 0);
2072 (void)rte_rcu_qsbr_thread_unregister(g_qsv, 0);
2073
2074 return 0;
2075 }
2076
2077 /*
2078 * rte_hash_rcu_qsbr_add sync mode functional test.
2079 * 1 Reader and 1 writer. They cannot be in the same thread in this test.
2080 * - Create hash which supports maximum 8 (9 if ext bkt is enabled) entries
2081 * - Add RCU QSBR variable to hash
2082 * - Register a reader thread. Reader keeps looking up a specific key.
2083 * - Writer keeps adding and deleting a specific key.
2084 */
2085 static int
test_hash_rcu_qsbr_sync_mode(uint8_t ext_bkt)2086 test_hash_rcu_qsbr_sync_mode(uint8_t ext_bkt)
2087 {
2088 uint32_t total_entries = (ext_bkt == 0) ? 8 : 9;
2089
2090 uint8_t hash_extra_flag = RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF;
2091
2092 if (ext_bkt)
2093 hash_extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
2094
2095 struct rte_hash_parameters params_pseudo_hash = {
2096 .name = "test_hash_rcu_qsbr_sync_mode",
2097 .entries = total_entries,
2098 .key_len = sizeof(struct flow_key),
2099 .hash_func = pseudo_hash,
2100 .hash_func_init_val = 0,
2101 .socket_id = 0,
2102 .extra_flag = hash_extra_flag,
2103 };
2104 int pos[total_entries];
2105 int expected_pos[total_entries];
2106 unsigned int i;
2107 size_t sz;
2108 int32_t status;
2109 struct rte_hash_rcu_config rcu_cfg = {0};
2110
2111 g_qsv = NULL;
2112 g_handle = NULL;
2113
2114 for (i = 0; i < total_entries; i++) {
2115 g_rand_keys[i].port_dst = i;
2116 g_rand_keys[i].port_src = i+1;
2117 }
2118
2119 if (ext_bkt)
2120 printf("\n# Running RCU QSBR sync mode functional test with"
2121 " ext bkt\n");
2122 else
2123 printf("\n# Running RCU QSBR sync mode functional test\n");
2124
2125 g_handle = rte_hash_create(¶ms_pseudo_hash);
2126 RETURN_IF_ERROR_RCU_QSBR(g_handle == NULL, "Hash creation failed");
2127
2128 /* Create RCU QSBR variable */
2129 sz = rte_rcu_qsbr_get_memsize(RTE_MAX_LCORE);
2130 g_qsv = (struct rte_rcu_qsbr *)rte_zmalloc_socket(NULL, sz,
2131 RTE_CACHE_LINE_SIZE, SOCKET_ID_ANY);
2132 RETURN_IF_ERROR_RCU_QSBR(g_qsv == NULL,
2133 "RCU QSBR variable creation failed");
2134
2135 status = rte_rcu_qsbr_init(g_qsv, RTE_MAX_LCORE);
2136 RETURN_IF_ERROR_RCU_QSBR(status != 0,
2137 "RCU QSBR variable initialization failed");
2138
2139 rcu_cfg.v = g_qsv;
2140 rcu_cfg.mode = RTE_HASH_QSBR_MODE_SYNC;
2141 /* Attach RCU QSBR to hash table */
2142 status = rte_hash_rcu_qsbr_add(g_handle, &rcu_cfg);
2143 RETURN_IF_ERROR_RCU_QSBR(status != 0,
2144 "Attach RCU QSBR to hash table failed");
2145
2146 /* Launch reader thread */
2147 rte_eal_remote_launch(test_hash_rcu_qsbr_reader, NULL,
2148 rte_get_next_lcore(-1, 1, 0));
2149
2150 /* Fill bucket */
2151 for (i = 0; i < total_entries; i++) {
2152 pos[i] = rte_hash_add_key(g_handle, &g_rand_keys[i]);
2153 print_key_info("Add", &g_rand_keys[i], pos[i]);
2154 RETURN_IF_ERROR_RCU_QSBR(pos[i] < 0,
2155 "failed to add key (pos[%u]=%d)", i, pos[i]);
2156 expected_pos[i] = pos[i];
2157 }
2158 writer_done = 0;
2159
2160 /* Writer Update */
2161 for (i = 0; i < WRITER_ITERATIONS; i++) {
2162 expected_pos[0] = pos[0];
2163 pos[0] = rte_hash_del_key(g_handle, &g_rand_keys[0]);
2164 print_key_info("Del", &g_rand_keys[0], status);
2165 RETURN_IF_ERROR_RCU_QSBR(pos[0] != expected_pos[0],
2166 "failed to del correct key (pos[%u]=%d)"
2167 , 0, pos[0]);
2168
2169 pos[0] = rte_hash_add_key(g_handle, &g_rand_keys[0]);
2170 print_key_info("Add", &g_rand_keys[0], pos[0]);
2171 RETURN_IF_ERROR_RCU_QSBR(pos[0] < 0,
2172 "failed to add key (pos[%u]=%d)", 0,
2173 pos[0]);
2174 }
2175
2176 writer_done = 1;
2177 /* Wait until reader exited. */
2178 rte_eal_mp_wait_lcore();
2179
2180 rte_hash_free(g_handle);
2181 rte_free(g_qsv);
2182
2183 return 0;
2184
2185 }
2186
2187 /*
2188 * Do all unit and performance tests.
2189 */
2190 static int
test_hash(void)2191 test_hash(void)
2192 {
2193 RTE_BUILD_BUG_ON(sizeof(struct flow_key) % sizeof(uint32_t) != 0);
2194
2195 if (test_add_delete() < 0)
2196 return -1;
2197 if (test_hash_add_delete_jhash2() < 0)
2198 return -1;
2199 if (test_hash_add_delete_2_jhash2() < 0)
2200 return -1;
2201 if (test_hash_add_delete_jhash_1word() < 0)
2202 return -1;
2203 if (test_hash_add_delete_jhash_2word() < 0)
2204 return -1;
2205 if (test_hash_add_delete_jhash_3word() < 0)
2206 return -1;
2207 if (test_hash_get_key_with_position() < 0)
2208 return -1;
2209 if (test_hash_find_existing() < 0)
2210 return -1;
2211 if (test_add_update_delete() < 0)
2212 return -1;
2213 if (test_add_update_delete_free() < 0)
2214 return -1;
2215 if (test_add_delete_free_lf() < 0)
2216 return -1;
2217 if (test_five_keys() < 0)
2218 return -1;
2219 if (test_full_bucket() < 0)
2220 return -1;
2221 if (test_extendable_bucket() < 0)
2222 return -1;
2223
2224 if (test_fbk_hash_find_existing() < 0)
2225 return -1;
2226 if (fbk_hash_unit_test() < 0)
2227 return -1;
2228 if (test_hash_creation_with_bad_parameters() < 0)
2229 return -1;
2230 if (test_hash_creation_with_good_parameters() < 0)
2231 return -1;
2232
2233 /* ext table disabled */
2234 if (test_average_table_utilization(0) < 0)
2235 return -1;
2236 if (test_hash_iteration(0) < 0)
2237 return -1;
2238
2239 /* ext table enabled */
2240 if (test_average_table_utilization(1) < 0)
2241 return -1;
2242 if (test_hash_iteration(1) < 0)
2243 return -1;
2244
2245 run_hash_func_tests();
2246
2247 if (test_crc32_hash_alg_equiv() < 0)
2248 return -1;
2249
2250 if (test_hash_rcu_qsbr_add() < 0)
2251 return -1;
2252
2253 if (test_hash_rcu_qsbr_dq_mode(0) < 0)
2254 return -1;
2255
2256 if (test_hash_rcu_qsbr_dq_mode(1) < 0)
2257 return -1;
2258
2259 if (test_hash_rcu_qsbr_sync_mode(0) < 0)
2260 return -1;
2261
2262 if (test_hash_rcu_qsbr_sync_mode(1) < 0)
2263 return -1;
2264
2265 return 0;
2266 }
2267
2268 REGISTER_TEST_COMMAND(hash_autotest, test_hash);
2269