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