1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2017 Intel Corporation 3 */ 4 5 /* This test is for membership library's simple feature test */ 6 7 #include <math.h> 8 #include "test.h" 9 10 #include <rte_memcpy.h> 11 #include <rte_malloc.h> 12 13 #ifdef RTE_EXEC_ENV_WINDOWS 14 static int 15 test_member(void) 16 { 17 printf("member not supported on Windows, skipping test\n"); 18 return TEST_SKIPPED; 19 } 20 21 #else 22 23 #include <rte_member.h> 24 #include <rte_byteorder.h> 25 #include <rte_random.h> 26 #include <rte_debug.h> 27 #include <rte_ip.h> 28 29 struct rte_member_setsum *setsum_ht; 30 struct rte_member_setsum *setsum_cache; 31 struct rte_member_setsum *setsum_vbf; 32 struct rte_member_setsum *setsum_sketch; 33 34 /* 5-tuple key type */ 35 struct __rte_packed_begin flow_key { 36 uint32_t ip_src; 37 uint32_t ip_dst; 38 uint16_t port_src; 39 uint16_t port_dst; 40 uint8_t proto; 41 } __rte_packed_end; 42 43 /* Set ID Macros for multimatch test usage */ 44 #define M_MATCH_S 1 /* Not start with 0 since by default 0 means no match */ 45 #define M_MATCH_E 15 46 #define M_MATCH_STEP 2 47 #define M_MATCH_CNT \ 48 (1 + (M_MATCH_E - M_MATCH_S) / M_MATCH_STEP) 49 50 51 #define NUM_SAMPLES 5 52 #define MAX_MATCH 32 53 54 /* Keys used by unit test functions */ 55 static struct flow_key keys[NUM_SAMPLES] = { 56 { 57 .ip_src = RTE_IPV4(0x03, 0x02, 0x01, 0x00), 58 .ip_dst = RTE_IPV4(0x07, 0x06, 0x05, 0x04), 59 .port_src = 0x0908, 60 .port_dst = 0x0b0a, 61 .proto = 0x0c, 62 }, 63 { 64 .ip_src = RTE_IPV4(0x13, 0x12, 0x11, 0x10), 65 .ip_dst = RTE_IPV4(0x17, 0x16, 0x15, 0x14), 66 .port_src = 0x1918, 67 .port_dst = 0x1b1a, 68 .proto = 0x1c, 69 }, 70 { 71 .ip_src = RTE_IPV4(0x23, 0x22, 0x21, 0x20), 72 .ip_dst = RTE_IPV4(0x27, 0x26, 0x25, 0x24), 73 .port_src = 0x2928, 74 .port_dst = 0x2b2a, 75 .proto = 0x2c, 76 }, 77 { 78 .ip_src = RTE_IPV4(0x33, 0x32, 0x31, 0x30), 79 .ip_dst = RTE_IPV4(0x37, 0x36, 0x35, 0x34), 80 .port_src = 0x3938, 81 .port_dst = 0x3b3a, 82 .proto = 0x3c, 83 }, 84 { 85 .ip_src = RTE_IPV4(0x43, 0x42, 0x41, 0x40), 86 .ip_dst = RTE_IPV4(0x47, 0x46, 0x45, 0x44), 87 .port_src = 0x4948, 88 .port_dst = 0x4b4a, 89 .proto = 0x4c, 90 } 91 }; 92 93 uint32_t test_set[NUM_SAMPLES] = {1, 2, 3, 4, 5}; 94 95 #define ITERATIONS 3 96 #define KEY_SIZE 4 97 98 #define MAX_ENTRIES (1 << 16) 99 uint8_t generated_keys[MAX_ENTRIES][KEY_SIZE]; 100 101 static struct rte_member_parameters params = { 102 .num_keys = MAX_ENTRIES, /* Total hash table entries. */ 103 .key_len = KEY_SIZE, /* Length of hash key. */ 104 105 /* num_set and false_positive_rate only relevant to vBF */ 106 .num_set = 16, 107 .false_positive_rate = 0.03, 108 .prim_hash_seed = 1, 109 .sec_hash_seed = 11, 110 .socket_id = 0 /* NUMA Socket ID for memory. */ 111 }; 112 113 /* for sketch definitions */ 114 #define TOP_K 10 115 #define HH_PKT_SIZE 16 116 #define SKETCH_ERROR_RATE 0.05 117 #define SKETCH_SAMPLE_RATE 0.001 118 #define PRINT_OUT_COUNT 20 119 120 #define SKETCH_LARGEST_KEY_SIZE 1000000 121 #define SKETCH_TOTAL_KEY 500 122 #define NUM_OF_KEY(key) {\ 123 (unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \ 124 } 125 126 void *heavy_hitters[TOP_K]; 127 128 /* 129 * Sequence of operations for find existing setsummary 130 * 131 * - create setsum 132 * - find existing setsum: hit 133 * - find non-existing setsum: miss 134 * 135 */ 136 static int 137 test_member_find_existing(void) 138 { 139 struct rte_member_setsum *tmp_setsum = NULL, *result = NULL; 140 struct rte_member_parameters tmp_params = { 141 .name = "member_find_existing", 142 .num_keys = MAX_ENTRIES, /* Total hash table entries. */ 143 .key_len = KEY_SIZE, /* Length of hash key. */ 144 .type = RTE_MEMBER_TYPE_HT, 145 .num_set = 32, 146 .false_positive_rate = 0.03, 147 .prim_hash_seed = 1, 148 .sec_hash_seed = 11, 149 .socket_id = 0 /* NUMA Socket ID for memory. */ 150 }; 151 152 /* Create */ 153 tmp_setsum = rte_member_create(&tmp_params); 154 TEST_ASSERT(tmp_setsum != NULL, "setsum creation failed"); 155 156 /* Try to find existing hash table */ 157 result = rte_member_find_existing("member_find_existing"); 158 TEST_ASSERT(result == tmp_setsum, "could not find existing setsum"); 159 160 /* Try to find non-existing hash table */ 161 result = rte_member_find_existing("member_find_non_existing"); 162 TEST_ASSERT(result == NULL, "found setsum that shouldn't exist"); 163 164 /* Cleanup. */ 165 rte_member_free(tmp_setsum); 166 167 return 0; 168 } 169 170 /* 171 * Test for bad creating parameters 172 */ 173 static int 174 test_member_create_bad_param(void) 175 { 176 struct rte_member_setsum *bad_setsum = NULL; 177 struct rte_member_parameters bad_params = { 178 .num_keys = MAX_ENTRIES, /* Total hash table entries. */ 179 .key_len = KEY_SIZE, /* Length of hash key. */ 180 .type = RTE_MEMBER_TYPE_HT, 181 .num_set = 32, 182 .false_positive_rate = 0.03, 183 .prim_hash_seed = 1, 184 .sec_hash_seed = 11, 185 .socket_id = 0 /* NUMA Socket ID for memory. */ 186 }; 187 188 printf("Expected error section begin...\n"); 189 bad_params.name = "bad_param1"; 190 bad_params.num_set = 0; 191 bad_params.type = RTE_MEMBER_TYPE_VBF; 192 /* Test with 0 set for vBF should fail */ 193 bad_setsum = rte_member_create(&bad_params); 194 if (bad_setsum != NULL) { 195 rte_member_free(bad_setsum); 196 printf("Impossible creating setsum successfully with invalid " 197 "number of set for vBF\n"); 198 return -1; 199 } 200 201 bad_params.name = "bad_param2"; 202 bad_params.false_positive_rate = 0; 203 bad_params.num_set = 32; 204 /* Test with 0 false positive for vBF should fail */ 205 bad_setsum = rte_member_create(&bad_params); 206 if (bad_setsum != NULL) { 207 rte_member_free(bad_setsum); 208 printf("Impossible creating setsum successfully with invalid " 209 "false positive rate for vBF\n"); 210 return -1; 211 } 212 213 bad_params.name = "bad_param3"; 214 bad_params.false_positive_rate = 0.03; 215 bad_params.num_keys = 0; 216 /* Test with 0 key per BF for vBF should fail */ 217 bad_setsum = rte_member_create(&bad_params); 218 if (bad_setsum != NULL) { 219 rte_member_free(bad_setsum); 220 printf("Impossible creating setsum successfully with invalid " 221 "num_keys for vBF\n"); 222 return -1; 223 } 224 225 bad_params.name = "bad_param4"; 226 bad_params.type = RTE_MEMBER_TYPE_HT; 227 bad_params.num_keys = RTE_MEMBER_BUCKET_ENTRIES / 2; 228 /* Test with less than 1 bucket for HTSS should fail */ 229 bad_setsum = rte_member_create(&bad_params); 230 if (bad_setsum != NULL) { 231 rte_member_free(bad_setsum); 232 printf("Impossible creating setsum successfully with too few " 233 "number of keys(entries) for HT\n"); 234 return -1; 235 } 236 237 bad_params.name = "bad_param5"; 238 bad_params.num_keys = RTE_MEMBER_ENTRIES_MAX + 1; 239 /* Test with more than maximum entries for HTSS should fail */ 240 bad_setsum = rte_member_create(&bad_params); 241 if (bad_setsum != NULL) { 242 rte_member_free(bad_setsum); 243 printf("Impossible creating setsum successfully with to many " 244 "number of keys(entries) for HT\n"); 245 return -1; 246 } 247 248 bad_params.name = "bad_param5"; 249 /* Test with same name should fail */ 250 bad_setsum = rte_member_create(&bad_params); 251 if (bad_setsum != NULL) { 252 rte_member_free(bad_setsum); 253 printf("Impossible creating setsum successfully with existed " 254 "name\n"); 255 return -1; 256 } 257 printf("Expected error section end...\n"); 258 rte_member_free(bad_setsum); 259 return 0; 260 } 261 262 /* Create test setsummaries. */ 263 static int test_member_create(void) 264 { 265 params.key_len = sizeof(struct flow_key); 266 267 params.name = "test_member_ht"; 268 params.is_cache = 0; 269 params.type = RTE_MEMBER_TYPE_HT; 270 setsum_ht = rte_member_create(¶ms); 271 272 params.name = "test_member_cache"; 273 params.is_cache = 1; 274 setsum_cache = rte_member_create(¶ms); 275 276 params.name = "test_member_vbf"; 277 params.type = RTE_MEMBER_TYPE_VBF; 278 setsum_vbf = rte_member_create(¶ms); 279 280 if (setsum_ht == NULL || setsum_cache == NULL || setsum_vbf == NULL) { 281 printf("Creation of setsums fail\n"); 282 return -1; 283 } 284 printf("Creation of setsums success\n"); 285 return 0; 286 } 287 288 static int test_member_insert(void) 289 { 290 int ret_ht, ret_cache, ret_vbf, i; 291 292 for (i = 0; i < NUM_SAMPLES; i++) { 293 ret_ht = rte_member_add(setsum_ht, &keys[i], test_set[i]); 294 ret_cache = rte_member_add(setsum_cache, &keys[i], 295 test_set[i]); 296 ret_vbf = rte_member_add(setsum_vbf, &keys[i], test_set[i]); 297 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, 298 "insert error"); 299 } 300 printf("insert key success\n"); 301 return 0; 302 } 303 304 static int test_member_lookup(void) 305 { 306 int ret_ht, ret_cache, ret_vbf, i; 307 uint16_t set_ht, set_cache, set_vbf; 308 member_set_t set_ids_ht[NUM_SAMPLES] = {0}; 309 member_set_t set_ids_cache[NUM_SAMPLES] = {0}; 310 member_set_t set_ids_vbf[NUM_SAMPLES] = {0}; 311 312 uint32_t num_key_ht = NUM_SAMPLES; 313 uint32_t num_key_cache = NUM_SAMPLES; 314 uint32_t num_key_vbf = NUM_SAMPLES; 315 316 const void *key_array[NUM_SAMPLES]; 317 318 /* Single lookup test */ 319 for (i = 0; i < NUM_SAMPLES; i++) { 320 ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht); 321 ret_cache = rte_member_lookup(setsum_cache, &keys[i], 322 &set_cache); 323 ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf); 324 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, 325 "single lookup function error"); 326 327 TEST_ASSERT(set_ht == test_set[i] && 328 set_cache == test_set[i] && 329 set_vbf == test_set[i], 330 "single lookup set value error"); 331 } 332 printf("lookup single key success\n"); 333 334 /* Bulk lookup test */ 335 for (i = 0; i < NUM_SAMPLES; i++) 336 key_array[i] = &keys[i]; 337 338 ret_ht = rte_member_lookup_bulk(setsum_ht, key_array, 339 num_key_ht, set_ids_ht); 340 341 ret_cache = rte_member_lookup_bulk(setsum_cache, key_array, 342 num_key_cache, set_ids_cache); 343 344 ret_vbf = rte_member_lookup_bulk(setsum_vbf, key_array, 345 num_key_vbf, set_ids_vbf); 346 347 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, 348 "bulk lookup function error"); 349 350 for (i = 0; i < NUM_SAMPLES; i++) { 351 TEST_ASSERT((set_ids_ht[i] == test_set[i]) && 352 (set_ids_cache[i] == test_set[i]) && 353 (set_ids_vbf[i] == test_set[i]), 354 "bulk lookup result error"); 355 } 356 357 return 0; 358 } 359 360 static int test_member_delete(void) 361 { 362 int ret_ht, ret_cache, ret_vbf, i; 363 uint16_t set_ht, set_cache, set_vbf; 364 const void *key_array[NUM_SAMPLES]; 365 member_set_t set_ids_ht[NUM_SAMPLES] = {0}; 366 member_set_t set_ids_cache[NUM_SAMPLES] = {0}; 367 member_set_t set_ids_vbf[NUM_SAMPLES] = {0}; 368 uint32_t num_key_ht = NUM_SAMPLES; 369 uint32_t num_key_cache = NUM_SAMPLES; 370 uint32_t num_key_vbf = NUM_SAMPLES; 371 372 /* Delete part of all inserted keys */ 373 for (i = 0; i < NUM_SAMPLES / 2; i++) { 374 ret_ht = rte_member_delete(setsum_ht, &keys[i], test_set[i]); 375 ret_cache = rte_member_delete(setsum_cache, &keys[i], 376 test_set[i]); 377 ret_vbf = rte_member_delete(setsum_vbf, &keys[i], test_set[i]); 378 /* VBF does not support delete yet, so return error code */ 379 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0, 380 "key deletion function error"); 381 TEST_ASSERT(ret_vbf < 0, 382 "vbf does not support deletion, error"); 383 } 384 385 for (i = 0; i < NUM_SAMPLES; i++) 386 key_array[i] = &keys[i]; 387 388 ret_ht = rte_member_lookup_bulk(setsum_ht, key_array, 389 num_key_ht, set_ids_ht); 390 391 ret_cache = rte_member_lookup_bulk(setsum_cache, key_array, 392 num_key_cache, set_ids_cache); 393 394 ret_vbf = rte_member_lookup_bulk(setsum_vbf, key_array, 395 num_key_vbf, set_ids_vbf); 396 397 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, 398 "bulk lookup function error"); 399 400 for (i = 0; i < NUM_SAMPLES / 2; i++) { 401 TEST_ASSERT((set_ids_ht[i] == RTE_MEMBER_NO_MATCH) && 402 (set_ids_cache[i] == RTE_MEMBER_NO_MATCH), 403 "bulk lookup result error"); 404 } 405 406 for (i = NUM_SAMPLES / 2; i < NUM_SAMPLES; i++) { 407 TEST_ASSERT((set_ids_ht[i] == test_set[i]) && 408 (set_ids_cache[i] == test_set[i]) && 409 (set_ids_vbf[i] == test_set[i]), 410 "bulk lookup result error"); 411 } 412 413 /* Delete the left of inserted keys */ 414 for (i = NUM_SAMPLES / 2; i < NUM_SAMPLES; i++) { 415 ret_ht = rte_member_delete(setsum_ht, &keys[i], test_set[i]); 416 ret_cache = rte_member_delete(setsum_cache, &keys[i], 417 test_set[i]); 418 ret_vbf = rte_member_delete(setsum_vbf, &keys[i], test_set[i]); 419 /* VBF does not support delete yet, so return error code */ 420 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0, 421 "key deletion function error"); 422 TEST_ASSERT(ret_vbf < 0, 423 "vbf does not support deletion, error"); 424 } 425 426 for (i = 0; i < NUM_SAMPLES; i++) { 427 ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht); 428 ret_cache = rte_member_lookup(setsum_cache, &keys[i], 429 &set_cache); 430 ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf); 431 TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0, 432 "key lookup function error"); 433 TEST_ASSERT(set_ht == RTE_MEMBER_NO_MATCH && 434 ret_cache == RTE_MEMBER_NO_MATCH, 435 "key deletion failed"); 436 } 437 /* Reset vbf for other following tests */ 438 rte_member_reset(setsum_vbf); 439 440 printf("delete success\n"); 441 return 0; 442 } 443 444 static int test_member_multimatch(void) 445 { 446 int ret_ht, ret_vbf, ret_cache; 447 member_set_t set_ids_ht[MAX_MATCH] = {0}; 448 member_set_t set_ids_vbf[MAX_MATCH] = {0}; 449 member_set_t set_ids_cache[MAX_MATCH] = {0}; 450 451 member_set_t set_ids_ht_m[NUM_SAMPLES][MAX_MATCH] = {{0} }; 452 member_set_t set_ids_vbf_m[NUM_SAMPLES][MAX_MATCH] = {{0} }; 453 member_set_t set_ids_cache_m[NUM_SAMPLES][MAX_MATCH] = {{0} }; 454 455 uint32_t match_count_ht[NUM_SAMPLES]; 456 uint32_t match_count_vbf[NUM_SAMPLES]; 457 uint32_t match_count_cache[NUM_SAMPLES]; 458 459 uint32_t num_key_ht = NUM_SAMPLES; 460 uint32_t num_key_vbf = NUM_SAMPLES; 461 uint32_t num_key_cache = NUM_SAMPLES; 462 463 const void *key_array[NUM_SAMPLES]; 464 465 uint32_t i, j; 466 467 /* Same key at most inserted 2*entry_per_bucket times for HT mode */ 468 for (i = M_MATCH_S; i <= M_MATCH_E; i += M_MATCH_STEP) { 469 for (j = 0; j < NUM_SAMPLES; j++) { 470 ret_ht = rte_member_add(setsum_ht, &keys[j], i); 471 ret_vbf = rte_member_add(setsum_vbf, &keys[j], i); 472 ret_cache = rte_member_add(setsum_cache, &keys[j], i); 473 474 TEST_ASSERT(ret_ht >= 0 && ret_vbf >= 0 && 475 ret_cache >= 0, 476 "insert function error"); 477 } 478 } 479 480 /* Single multimatch test */ 481 for (i = 0; i < NUM_SAMPLES; i++) { 482 ret_vbf = rte_member_lookup_multi(setsum_vbf, &keys[i], 483 MAX_MATCH, set_ids_vbf); 484 ret_ht = rte_member_lookup_multi(setsum_ht, &keys[i], 485 MAX_MATCH, set_ids_ht); 486 ret_cache = rte_member_lookup_multi(setsum_cache, &keys[i], 487 MAX_MATCH, set_ids_cache); 488 /* 489 * For cache mode, keys overwrite when signature same. 490 * the multimatch should work like single match. 491 */ 492 TEST_ASSERT(ret_ht == M_MATCH_CNT && ret_vbf == M_MATCH_CNT && 493 ret_cache == 1, 494 "single lookup_multi error"); 495 TEST_ASSERT(set_ids_cache[0] == M_MATCH_E, 496 "single lookup_multi cache error"); 497 498 for (j = 1; j <= M_MATCH_CNT; j++) { 499 TEST_ASSERT(set_ids_ht[j-1] == j * M_MATCH_STEP - 1 && 500 set_ids_vbf[j-1] == 501 j * M_MATCH_STEP - 1, 502 "single multimatch lookup error"); 503 } 504 } 505 printf("lookup single key for multimatch success\n"); 506 507 /* Bulk multimatch test */ 508 for (i = 0; i < NUM_SAMPLES; i++) 509 key_array[i] = &keys[i]; 510 ret_vbf = rte_member_lookup_multi_bulk(setsum_vbf, 511 &key_array[0], num_key_ht, MAX_MATCH, match_count_vbf, 512 (member_set_t *)set_ids_vbf_m); 513 514 ret_ht = rte_member_lookup_multi_bulk(setsum_ht, 515 &key_array[0], num_key_vbf, MAX_MATCH, match_count_ht, 516 (member_set_t *)set_ids_ht_m); 517 518 ret_cache = rte_member_lookup_multi_bulk(setsum_cache, 519 &key_array[0], num_key_cache, MAX_MATCH, 520 match_count_cache, (member_set_t *)set_ids_cache_m); 521 522 523 for (j = 0; j < NUM_SAMPLES; j++) { 524 TEST_ASSERT(match_count_ht[j] == M_MATCH_CNT, 525 "bulk multimatch lookup HT match count error"); 526 TEST_ASSERT(match_count_vbf[j] == M_MATCH_CNT, 527 "bulk multimatch lookup vBF match count error"); 528 TEST_ASSERT(match_count_cache[j] == 1, 529 "bulk multimatch lookup CACHE match count error"); 530 TEST_ASSERT(set_ids_cache_m[j][0] == M_MATCH_E, 531 "bulk multimatch lookup CACHE set value error"); 532 533 for (i = 1; i <= M_MATCH_CNT; i++) { 534 TEST_ASSERT(set_ids_ht_m[j][i-1] == 535 i * M_MATCH_STEP - 1, 536 "bulk multimatch lookup HT set value error"); 537 TEST_ASSERT(set_ids_vbf_m[j][i-1] == 538 i * M_MATCH_STEP - 1, 539 "bulk multimatch lookup vBF set value error"); 540 } 541 } 542 543 printf("lookup for bulk multimatch success\n"); 544 545 return 0; 546 } 547 548 static int key_compare(const void *key1, const void *key2) 549 { 550 return memcmp(key1, key2, KEY_SIZE); 551 } 552 553 static void 554 setup_keys_and_data(void) 555 { 556 unsigned int i, j; 557 int num_duplicates; 558 559 /* Reset all arrays */ 560 for (i = 0; i < KEY_SIZE; i++) 561 generated_keys[0][i] = 0; 562 563 /* Generate a list of keys, some of which may be duplicates */ 564 for (i = 0; i < MAX_ENTRIES; i++) { 565 for (j = 0; j < KEY_SIZE; j++) 566 generated_keys[i][j] = rte_rand() & 0xFF; 567 } 568 569 /* Remove duplicates from the keys array */ 570 do { 571 num_duplicates = 0; 572 /* Sort the list of keys to make it easier to find duplicates */ 573 qsort(generated_keys, MAX_ENTRIES, KEY_SIZE, key_compare); 574 575 /* Sift through the list of keys and look for duplicates */ 576 for (i = 0; i < MAX_ENTRIES - 1; i++) { 577 if (memcmp(generated_keys[i], generated_keys[i + 1], 578 KEY_SIZE) == 0) { 579 /* This key already exists, try again */ 580 num_duplicates++; 581 for (j = 0; j < KEY_SIZE; j++) 582 generated_keys[i][j] = 583 rte_rand() & 0xFF; 584 } 585 } 586 } while (num_duplicates != 0); 587 } 588 589 static inline int 590 add_generated_keys(struct rte_member_setsum *setsum, unsigned int *added_keys) 591 { 592 int ret = 0; 593 594 for (*added_keys = 0; ret >= 0 && *added_keys < MAX_ENTRIES; 595 (*added_keys)++) { 596 uint16_t set = (rte_rand() & 0xf) + 1; 597 ret = rte_member_add(setsum, &generated_keys[*added_keys], set); 598 } 599 return ret; 600 } 601 602 static inline int 603 add_generated_keys_cache(struct rte_member_setsum *setsum, 604 unsigned int *added_keys) 605 { 606 int ret = 0; 607 608 for (*added_keys = 0; ret == 0 && *added_keys < MAX_ENTRIES; 609 (*added_keys)++) { 610 uint16_t set = (rte_rand() & 0xf) + 1; 611 ret = rte_member_add(setsum, &generated_keys[*added_keys], set); 612 } 613 return ret; 614 } 615 616 static int 617 test_member_loadfactor(void) 618 { 619 unsigned int j; 620 unsigned int added_keys, average_keys_added = 0; 621 int ret; 622 623 setup_keys_and_data(); 624 625 rte_member_free(setsum_ht); 626 rte_member_free(setsum_cache); 627 rte_member_free(setsum_vbf); 628 629 params.key_len = KEY_SIZE; 630 params.name = "test_member_ht"; 631 params.is_cache = 0; 632 params.type = RTE_MEMBER_TYPE_HT; 633 setsum_ht = rte_member_create(¶ms); 634 635 params.name = "test_member_cache"; 636 params.is_cache = 1; 637 setsum_cache = rte_member_create(¶ms); 638 639 640 if (setsum_ht == NULL || setsum_cache == NULL) { 641 printf("Creation of setsums fail\n"); 642 return -1; 643 } 644 /* Test HT non-cache mode */ 645 for (j = 0; j < ITERATIONS; j++) { 646 /* Add random entries until key cannot be added */ 647 ret = add_generated_keys(setsum_ht, &added_keys); 648 if (ret != -ENOSPC) { 649 printf("Unexpected error when adding keys\n"); 650 return -1; 651 } 652 average_keys_added += added_keys; 653 654 /* Reset the table */ 655 rte_member_reset(setsum_ht); 656 657 /* Print a dot to show progress on operations */ 658 printf("."); 659 fflush(stdout); 660 } 661 662 average_keys_added /= ITERATIONS; 663 664 printf("\nKeys inserted when no space(non-cache) = %.2f%% (%u/%u)\n", 665 ((double) average_keys_added / params.num_keys * 100), 666 average_keys_added, params.num_keys); 667 668 /* Test cache mode */ 669 added_keys = average_keys_added = 0; 670 for (j = 0; j < ITERATIONS; j++) { 671 /* Add random entries until key cannot be added */ 672 ret = add_generated_keys_cache(setsum_cache, &added_keys); 673 if (ret != 1) { 674 printf("Unexpected error when adding keys\n"); 675 return -1; 676 } 677 average_keys_added += added_keys; 678 679 /* Reset the table */ 680 rte_member_reset(setsum_cache); 681 682 /* Print a dot to show progress on operations */ 683 printf("."); 684 fflush(stdout); 685 } 686 687 average_keys_added /= ITERATIONS; 688 689 printf("\nKeys inserted when eviction happens(cache)= %.2f%% (%u/%u)\n", 690 ((double) average_keys_added / params.num_keys * 100), 691 average_keys_added, params.num_keys); 692 return 0; 693 } 694 695 static void 696 perform_free(void) 697 { 698 rte_member_free(setsum_ht); 699 rte_member_free(setsum_cache); 700 rte_member_free(setsum_vbf); 701 } 702 703 static void 704 print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set, 705 uint32_t print_num, bool count_byte) 706 { 707 uint32_t i; 708 709 for (i = 0; i < print_num; i++) { 710 if (count_byte) 711 printf("key %2u, count %8"PRIu64", real count %8u, " 712 "heavy_set %u, deviation rate [%.04f]\n", 713 i, count_result[i], 714 (unsigned int)ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)) * 715 HH_PKT_SIZE, 716 heavy_set[i], 717 fabs((double)count_result[i] - (double)NUM_OF_KEY(i) * HH_PKT_SIZE) / 718 ((double)NUM_OF_KEY(i) * HH_PKT_SIZE)); 719 else 720 printf("key %2u, count %8"PRIu64", real count %8u, " 721 "heavy_set %u, deviation rate [%.04f]\n", 722 i, count_result[i], 723 (unsigned int)ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)), 724 heavy_set[i], 725 fabs((double)count_result[i] - (double)NUM_OF_KEY(i)) / 726 (double)NUM_OF_KEY(i)); 727 } 728 } 729 730 static int 731 sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int reset_test) 732 { 733 uint32_t i; 734 uint64_t result_count[SKETCH_TOTAL_KEY]; 735 member_set_t heavy_set[SKETCH_TOTAL_KEY]; 736 uint64_t count[TOP_K]; 737 int ret; 738 int hh_cnt; 739 740 setsum_sketch = rte_member_create(¶ms); 741 if (setsum_sketch == NULL) { 742 printf("Creation of setsums fail\n"); 743 return -1; 744 } 745 746 for (i = 0; i < total_pkt; i++) { 747 if (count_byte) 748 ret = rte_member_add_byte_count(setsum_sketch, &keys[i], HH_PKT_SIZE); 749 else 750 ret = rte_member_add(setsum_sketch, &keys[i], 1); 751 752 if (ret < 0) { 753 printf("rte_member_add Failed! Error [%d]\n", ret); 754 rte_member_free(setsum_sketch); 755 756 return -1; 757 } 758 } 759 760 for (i = 0; i < SKETCH_TOTAL_KEY; i++) { 761 uint32_t tmp_key = i; 762 763 rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); 764 rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); 765 } 766 767 print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); 768 769 hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); 770 if (hh_cnt < 0) { 771 printf("sketch report heavy hitter error!"); 772 rte_member_free(setsum_sketch); 773 774 return -1; 775 } 776 777 printf("Report heavy hitters:"); 778 for (i = 0; i < (unsigned int)hh_cnt; i++) { 779 printf("%u: %"PRIu64"\t", 780 *((uint32_t *)heavy_hitters[i]), count[i]); 781 } 782 printf("\n"); 783 784 if (reset_test) { 785 printf("\nEntering Sketch Reset Test Process!\n"); 786 rte_member_reset(setsum_sketch); 787 788 /* after reset, check some key's count */ 789 for (i = 0; i < SKETCH_TOTAL_KEY; i++) { 790 uint32_t tmp_key = i; 791 792 rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); 793 rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); 794 } 795 796 print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); 797 798 printf("\nReinsert keys after Sketch Reset!\n"); 799 for (i = 0; i < total_pkt; i++) { 800 if (count_byte) 801 ret = rte_member_add_byte_count 802 (setsum_sketch, &keys[i], HH_PKT_SIZE); 803 else 804 ret = rte_member_add(setsum_sketch, &keys[i], 1); 805 806 if (ret < 0) { 807 printf("rte_member_add Failed! Error [%d]\n", ret); 808 rte_member_free(setsum_sketch); 809 810 return -1; 811 } 812 } 813 814 for (i = 0; i < SKETCH_TOTAL_KEY; i++) { 815 uint32_t tmp_key = i; 816 817 rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); 818 rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); 819 } 820 821 print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); 822 823 hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); 824 if (hh_cnt < 0) { 825 printf("sketch report heavy hitter error!"); 826 rte_member_free(setsum_sketch); 827 828 return -1; 829 } 830 printf("Report heavy hitters:"); 831 for (i = 0; i < (unsigned int)hh_cnt; i++) { 832 printf("%u: %"PRIu64"\t", 833 *((uint32_t *)heavy_hitters[i]), count[i]); 834 } 835 printf("\n"); 836 837 printf("\nDelete some keys!\n"); 838 uint32_t tmp_key = 0; 839 840 rte_member_delete(setsum_sketch, (void *)&tmp_key, 0); 841 tmp_key = 1; 842 rte_member_delete(setsum_sketch, (void *)&tmp_key, 0); 843 844 for (i = 0; i < SKETCH_TOTAL_KEY; i++) { 845 uint32_t tmp_key = i; 846 847 rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]); 848 rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]); 849 } 850 851 print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte); 852 853 hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count); 854 if (hh_cnt < 0) { 855 printf("sketch report heavy hitter error!"); 856 rte_member_free(setsum_sketch); 857 858 return -1; 859 } 860 printf("Report heavy hitters:"); 861 for (i = 0; i < (unsigned int)hh_cnt; i++) { 862 printf("%u: %"PRIu64"\t", 863 *((uint32_t *)heavy_hitters[i]), count[i]); 864 } 865 printf("\n"); 866 } 867 868 rte_member_free(setsum_sketch); 869 return 0; 870 } 871 872 static int 873 test_member_sketch(void) 874 { 875 unsigned int i, j, index; 876 uint32_t total_pkt = 0; 877 uint32_t *keys; 878 int count_byte = 0; 879 880 for (i = 0; i < SKETCH_TOTAL_KEY; i++) 881 total_pkt += ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)); 882 883 printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt); 884 885 keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0); 886 887 if (keys == NULL) { 888 printf("RTE_ZMALLOC failed\n"); 889 return -1; 890 } 891 892 index = 0; 893 for (i = 0; i < SKETCH_TOTAL_KEY; i++) { 894 for (j = 0; j < ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++) 895 keys[index++] = i; 896 } 897 898 /* shuffle the keys */ 899 for (i = index - 1; i > 0; i--) { 900 uint32_t swap_idx = rte_rand() % i; 901 uint32_t tmp_key = keys[i]; 902 903 keys[i] = keys[swap_idx]; 904 keys[swap_idx] = tmp_key; 905 } 906 907 params.key_len = 4; 908 params.name = "test_member_sketch"; 909 params.type = RTE_MEMBER_TYPE_SKETCH; 910 params.error_rate = SKETCH_ERROR_RATE; 911 params.sample_rate = SKETCH_SAMPLE_RATE; 912 params.extra_flag = 0; 913 params.top_k = TOP_K; 914 params.prim_hash_seed = rte_rdtsc(); 915 int reset_test = 0; 916 917 printf("Default sketching params: Error Rate: [%f]\tSample Rate: [%f]\tTopK: [%d]\n", 918 SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K); 919 920 printf("\n[Sketch with Fixed Sampling Rate Mode]\n"); 921 if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { 922 rte_free(keys); 923 return -1; 924 } 925 926 params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED; 927 printf("\n[Sketch with Always Bounded Mode]\n"); 928 if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { 929 rte_free(keys); 930 return -1; 931 } 932 933 count_byte = 1; 934 params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE; 935 printf("\n[Sketch with Packet Size Mode]\n"); 936 if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { 937 rte_free(keys); 938 return -1; 939 } 940 941 count_byte = 0; 942 params.extra_flag = 0; 943 reset_test = 1; 944 printf("\nreset sketch test\n"); 945 if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) { 946 rte_free(keys); 947 return -1; 948 } 949 950 rte_free(keys); 951 return 0; 952 } 953 954 static int 955 test_member(void) 956 { 957 if (test_member_create_bad_param() < 0) 958 return -1; 959 960 if (test_member_find_existing() < 0) 961 return -1; 962 963 if (test_member_create() < 0) { 964 perform_free(); 965 return -1; 966 } 967 if (test_member_insert() < 0) { 968 perform_free(); 969 return -1; 970 } 971 if (test_member_lookup() < 0) { 972 perform_free(); 973 return -1; 974 } 975 if (test_member_delete() < 0) { 976 perform_free(); 977 return -1; 978 } 979 if (test_member_multimatch() < 0) { 980 perform_free(); 981 return -1; 982 } 983 if (test_member_loadfactor() < 0) { 984 rte_member_free(setsum_ht); 985 rte_member_free(setsum_cache); 986 return -1; 987 } 988 989 if (test_member_sketch() < 0) { 990 perform_free(); 991 return -1; 992 } 993 perform_free(); 994 return 0; 995 } 996 997 #endif /* !RTE_EXEC_ENV_WINDOWS */ 998 999 REGISTER_FAST_TEST(member_autotest, true, true, test_member); 1000