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