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