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