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 */ 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 */ 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 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 */ 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 */ 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 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 */ 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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