1 /* $NetBSD: rbt_test.c,v 1.3 2025/01/26 16:25:47 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 #include <ctype.h> 17 #include <fcntl.h> 18 #include <inttypes.h> 19 #include <sched.h> /* IWYU pragma: keep */ 20 #include <setjmp.h> 21 #include <stdarg.h> 22 #include <stdbool.h> 23 #include <stddef.h> 24 #include <stdlib.h> 25 #include <string.h> 26 #include <time.h> 27 #include <unistd.h> 28 29 #define UNIT_TESTING 30 #include <cmocka.h> 31 32 #include <isc/buffer.h> 33 #include <isc/file.h> 34 #include <isc/hash.h> 35 #include <isc/mem.h> 36 #include <isc/os.h> 37 #include <isc/random.h> 38 #include <isc/result.h> 39 #include <isc/stdio.h> 40 #include <isc/string.h> 41 #include <isc/thread.h> 42 #include <isc/time.h> 43 #include <isc/timer.h> 44 #include <isc/util.h> 45 46 #include <dns/compress.h> 47 #include <dns/fixedname.h> 48 #include <dns/log.h> 49 #include <dns/name.h> 50 #include <dns/rbt.h> 51 52 #include <dst/dst.h> 53 54 #include <tests/dns.h> 55 56 typedef struct { 57 dns_rbt_t *rbt; 58 dns_rbt_t *rbt_distances; 59 } test_context_t; 60 61 /* The initial structure of domain tree will be as follows: 62 * 63 * . 64 * | 65 * b 66 * / \ 67 * a d.e.f 68 * / | \ 69 * c | g.h 70 * | | 71 * w.y i 72 * / | \ \ 73 * x | z k 74 * | | 75 * p j 76 * / \ 77 * o q 78 */ 79 80 /* The full absolute names of the nodes in the tree (the tree also 81 * contains "." which is not included in this list). 82 */ 83 static const char *const domain_names[] = { 84 "c.", "b.", "a.", "x.d.e.f.", 85 "z.d.e.f.", "g.h.", "i.g.h.", "o.w.y.d.e.f.", 86 "j.z.d.e.f.", "p.w.y.d.e.f.", "q.w.y.d.e.f.", "k.g.h." 87 }; 88 89 static const size_t domain_names_count = 90 (sizeof(domain_names) / sizeof(domain_names[0])); 91 92 /* These are set as the node data for the tree used in distances check 93 * (for the names in domain_names[] above). 94 */ 95 static const int node_distances[] = { 3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2 }; 96 97 /* 98 * The domain order should be: 99 * ., a, b, c, d.e.f, x.d.e.f, w.y.d.e.f, o.w.y.d.e.f, p.w.y.d.e.f, 100 * q.w.y.d.e.f, z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h 101 * . (no data, can't be found) 102 * | 103 * b 104 * / \ 105 * a d.e.f 106 * / | \ 107 * c | g.h 108 * | | 109 * w.y i 110 * / | \ \ 111 * x | z k 112 * | | 113 * p j 114 * / \ 115 * o q 116 */ 117 118 static const char *const ordered_names[] = { 119 "a.", "b.", "c.", "d.e.f.", 120 "x.d.e.f.", "w.y.d.e.f.", "o.w.y.d.e.f.", "p.w.y.d.e.f.", 121 "q.w.y.d.e.f.", "z.d.e.f.", "j.z.d.e.f.", "g.h.", 122 "i.g.h.", "k.g.h." 123 }; 124 125 static const size_t ordered_names_count = 126 (sizeof(ordered_names) / sizeof(*ordered_names)); 127 128 static void 129 delete_data(void *data, void *arg) { 130 UNUSED(arg); 131 132 isc_mem_put(mctx, data, sizeof(size_t)); 133 } 134 135 static test_context_t * 136 test_context_setup(void) { 137 test_context_t *ctx; 138 isc_result_t result; 139 size_t i; 140 141 ctx = isc_mem_get(mctx, sizeof(*ctx)); 142 assert_non_null(ctx); 143 144 ctx->rbt = NULL; 145 result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt); 146 assert_int_equal(result, ISC_R_SUCCESS); 147 148 ctx->rbt_distances = NULL; 149 result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt_distances); 150 assert_int_equal(result, ISC_R_SUCCESS); 151 152 for (i = 0; i < domain_names_count; i++) { 153 size_t *n; 154 dns_fixedname_t fname; 155 dns_name_t *name = NULL; 156 dns_rbtnode_t *node = NULL; 157 158 dns_test_namefromstring(domain_names[i], &fname); 159 160 name = dns_fixedname_name(&fname); 161 162 n = isc_mem_get(mctx, sizeof(size_t)); 163 assert_non_null(n); 164 *n = i + 1; 165 result = dns_rbt_addnode(ctx->rbt, name, &node); 166 assert_int_equal(result, ISC_R_SUCCESS); 167 node->data = n; 168 169 node = NULL; 170 n = isc_mem_get(mctx, sizeof(size_t)); 171 assert_non_null(n); 172 *n = node_distances[i]; 173 result = dns_rbt_addnode(ctx->rbt_distances, name, &node); 174 node->data = n; 175 assert_int_equal(result, ISC_R_SUCCESS); 176 } 177 178 return ctx; 179 } 180 181 static void 182 test_context_teardown(test_context_t *ctx) { 183 dns_rbt_destroy(&ctx->rbt, 0); 184 dns_rbt_destroy(&ctx->rbt_distances, 0); 185 186 isc_mem_put(mctx, ctx, sizeof(*ctx)); 187 } 188 189 /* 190 * Walk the tree and ensure that all the test nodes are present. 191 */ 192 static void 193 check_test_data(dns_rbt_t *rbt) { 194 dns_fixedname_t fixed; 195 isc_result_t result; 196 dns_name_t *foundname; 197 size_t i; 198 199 foundname = dns_fixedname_initname(&fixed); 200 201 for (i = 0; i < domain_names_count; i++) { 202 dns_fixedname_t fname; 203 dns_rbtnode_t *node = NULL; 204 dns_name_t *name = NULL; 205 size_t *n = NULL; 206 207 dns_test_namefromstring(domain_names[i], &fname); 208 209 name = dns_fixedname_name(&fname); 210 n = NULL; 211 result = dns_rbt_findnode(rbt, name, foundname, &node, NULL, 0, 212 NULL, NULL); 213 assert_int_equal(result, ISC_R_SUCCESS); 214 n = node->data; 215 assert_int_equal(*n, i + 1); 216 } 217 } 218 219 /* Test the creation of an rbt */ 220 ISC_RUN_TEST_IMPL(rbt_create) { 221 test_context_t *ctx; 222 bool tree_ok; 223 224 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 225 226 ctx = test_context_setup(); 227 228 check_test_data(ctx->rbt); 229 230 tree_ok = dns__rbt_checkproperties(ctx->rbt); 231 assert_true(tree_ok); 232 233 test_context_teardown(ctx); 234 } 235 236 /* Test dns_rbt_nodecount() on a tree */ 237 ISC_RUN_TEST_IMPL(rbt_nodecount) { 238 test_context_t *ctx; 239 240 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 241 242 ctx = test_context_setup(); 243 244 assert_int_equal(15, dns_rbt_nodecount(ctx->rbt)); 245 246 test_context_teardown(ctx); 247 } 248 249 /* Test dns_rbtnode_get_distance() on a tree */ 250 ISC_RUN_TEST_IMPL(rbtnode_get_distance) { 251 isc_result_t result; 252 test_context_t *ctx; 253 const char *name_str = "a."; 254 dns_fixedname_t fname; 255 dns_name_t *name; 256 dns_rbtnode_t *node = NULL; 257 dns_rbtnodechain_t chain; 258 259 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 260 261 ctx = test_context_setup(); 262 263 dns_test_namefromstring(name_str, &fname); 264 name = dns_fixedname_name(&fname); 265 266 dns_rbtnodechain_init(&chain); 267 268 result = dns_rbt_findnode(ctx->rbt_distances, name, NULL, &node, &chain, 269 0, NULL, NULL); 270 assert_int_equal(result, ISC_R_SUCCESS); 271 272 while (node != NULL) { 273 const size_t *distance = (const size_t *)node->data; 274 if (distance != NULL) { 275 assert_int_equal(*distance, 276 dns__rbtnode_getdistance(node)); 277 } 278 result = dns_rbtnodechain_next(&chain, NULL, NULL); 279 if (result == ISC_R_NOMORE) { 280 break; 281 } 282 dns_rbtnodechain_current(&chain, NULL, NULL, &node); 283 } 284 285 assert_int_equal(result, ISC_R_NOMORE); 286 287 dns_rbtnodechain_invalidate(&chain); 288 289 test_context_teardown(ctx); 290 } 291 292 /* 293 * Test tree balance, inserting names in random order. 294 * 295 * This test checks an important performance-related property of 296 * the red-black tree, which is important for us: the longest 297 * path from a sub-tree's root to a node is no more than 298 * 2log(n). This check verifies that the tree is balanced. 299 */ 300 ISC_RUN_TEST_IMPL(rbt_check_distance_random) { 301 dns_rbt_t *mytree = NULL; 302 const unsigned int log_num_nodes = 16; 303 isc_result_t result; 304 bool tree_ok; 305 int i; 306 307 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 308 309 result = dns_rbt_create(mctx, delete_data, NULL, &mytree); 310 assert_int_equal(result, ISC_R_SUCCESS); 311 312 /* Names are inserted in random order. */ 313 314 /* Make a large 65536 node top-level domain tree, i.e., the 315 * following code inserts names such as: 316 * 317 * savoucnsrkrqzpkqypbygwoiliawpbmz. 318 * wkadamcbbpjtundbxcmuayuycposvngx. 319 * wzbpznemtooxdpjecdxynsfztvnuyfao. 320 * yueojmhyffslpvfmgyfwioxegfhepnqq. 321 */ 322 for (i = 0; i < (1 << log_num_nodes); i++) { 323 size_t *n = NULL; 324 char namebuf[34]; 325 326 n = isc_mem_get(mctx, sizeof(size_t)); 327 assert_non_null(n); 328 *n = i + 1; 329 330 while (1) { 331 int j; 332 dns_fixedname_t fname; 333 dns_rbtnode_t *node = NULL; 334 dns_name_t *name = NULL; 335 336 for (j = 0; j < 32; j++) { 337 uint32_t v = isc_random_uniform(26); 338 namebuf[j] = 'a' + v; 339 } 340 namebuf[32] = '.'; 341 namebuf[33] = 0; 342 343 dns_test_namefromstring(namebuf, &fname); 344 name = dns_fixedname_name(&fname); 345 346 result = dns_rbt_addnode(mytree, name, &node); 347 node->data = n; 348 if (result == ISC_R_SUCCESS) { 349 break; 350 } 351 } 352 } 353 354 /* 1 (root . node) + (1 << log_num_nodes) */ 355 assert_int_equal(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree)); 356 357 /* The distance from each node to its sub-tree root must be less 358 * than 2 * log(n). 359 */ 360 assert_true((2U * log_num_nodes) >= dns__rbt_getheight(mytree)); 361 362 /* Also check RB tree properties */ 363 tree_ok = dns__rbt_checkproperties(mytree); 364 assert_true(tree_ok); 365 366 dns_rbt_destroy(&mytree, 0); 367 } 368 369 /* 370 * Test tree balance, inserting names in sorted order. 371 * 372 * This test checks an important performance-related property of 373 * the red-black tree, which is important for us: the longest 374 * path from a sub-tree's root to a node is no more than 375 * 2log(n). This check verifies that the tree is balanced. 376 */ 377 ISC_RUN_TEST_IMPL(rbt_check_distance_ordered) { 378 dns_rbt_t *mytree = NULL; 379 const unsigned int log_num_nodes = 16; 380 isc_result_t result; 381 bool tree_ok; 382 int i; 383 384 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 385 386 result = dns_rbt_create(mctx, delete_data, NULL, &mytree); 387 assert_int_equal(result, ISC_R_SUCCESS); 388 389 /* Names are inserted in sorted order. */ 390 391 /* Make a large 65536 node top-level domain tree, i.e., the 392 * following code inserts names such as: 393 * 394 * name00000000. 395 * name00000001. 396 * name00000002. 397 * name00000003. 398 */ 399 for (i = 0; i < (1 << log_num_nodes); i++) { 400 size_t *n; 401 char namebuf[14]; 402 dns_fixedname_t fname; 403 dns_name_t *name = NULL; 404 dns_rbtnode_t *node = NULL; 405 406 n = isc_mem_get(mctx, sizeof(size_t)); 407 assert_non_null(n); 408 *n = i + 1; 409 410 snprintf(namebuf, sizeof(namebuf), "name%08x.", i); 411 dns_test_namefromstring(namebuf, &fname); 412 name = dns_fixedname_name(&fname); 413 414 result = dns_rbt_addnode(mytree, name, &node); 415 assert_int_equal(result, ISC_R_SUCCESS); 416 node->data = n; 417 } 418 419 /* 1 (root . node) + (1 << log_num_nodes) */ 420 assert_int_equal(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree)); 421 422 /* The distance from each node to its sub-tree root must be less 423 * than 2 * log(n). 424 */ 425 assert_true((2U * log_num_nodes) >= dns__rbt_getheight(mytree)); 426 427 /* Also check RB tree properties */ 428 tree_ok = dns__rbt_checkproperties(mytree); 429 assert_true(tree_ok); 430 431 dns_rbt_destroy(&mytree, 0); 432 } 433 434 static isc_result_t 435 insert_helper(dns_rbt_t *rbt, const char *namestr, dns_rbtnode_t **node) { 436 dns_fixedname_t fname; 437 dns_name_t *name; 438 439 dns_test_namefromstring(namestr, &fname); 440 name = dns_fixedname_name(&fname); 441 442 return dns_rbt_addnode(rbt, name, node); 443 } 444 445 static bool 446 compare_labelsequences(dns_rbtnode_t *node, const char *labelstr) { 447 dns_name_t name; 448 isc_result_t result; 449 char *nodestr = NULL; 450 bool is_equal; 451 452 dns_name_init(&name, NULL); 453 dns_rbt_namefromnode(node, &name); 454 455 result = dns_name_tostring(&name, &nodestr, mctx); 456 assert_int_equal(result, ISC_R_SUCCESS); 457 458 is_equal = strcmp(labelstr, nodestr) == 0 ? true : false; 459 460 isc_mem_free(mctx, nodestr); 461 462 return is_equal; 463 } 464 465 /* Test insertion into a tree */ 466 ISC_RUN_TEST_IMPL(rbt_insert) { 467 isc_result_t result; 468 test_context_t *ctx; 469 dns_rbtnode_t *node; 470 471 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 472 473 ctx = test_context_setup(); 474 475 /* Check node count before beginning. */ 476 assert_int_equal(15, dns_rbt_nodecount(ctx->rbt)); 477 478 /* Try to insert a node that already exists. */ 479 node = NULL; 480 result = insert_helper(ctx->rbt, "d.e.f.", &node); 481 assert_int_equal(result, ISC_R_EXISTS); 482 483 /* Node count must not have changed. */ 484 assert_int_equal(15, dns_rbt_nodecount(ctx->rbt)); 485 486 /* Try to insert a node that doesn't exist. */ 487 node = NULL; 488 result = insert_helper(ctx->rbt, "0.", &node); 489 assert_int_equal(result, ISC_R_SUCCESS); 490 assert_true(compare_labelsequences(node, "0")); 491 492 /* Node count must have increased. */ 493 assert_int_equal(16, dns_rbt_nodecount(ctx->rbt)); 494 495 /* Another. */ 496 node = NULL; 497 result = insert_helper(ctx->rbt, "example.com.", &node); 498 assert_int_equal(result, ISC_R_SUCCESS); 499 assert_non_null(node); 500 assert_null(node->data); 501 502 /* Node count must have increased. */ 503 assert_int_equal(17, dns_rbt_nodecount(ctx->rbt)); 504 505 /* Re-adding it should return EXISTS */ 506 node = NULL; 507 result = insert_helper(ctx->rbt, "example.com.", &node); 508 assert_int_equal(result, ISC_R_EXISTS); 509 510 /* Node count must not have changed. */ 511 assert_int_equal(17, dns_rbt_nodecount(ctx->rbt)); 512 513 /* Fission the node d.e.f */ 514 node = NULL; 515 result = insert_helper(ctx->rbt, "k.e.f.", &node); 516 assert_int_equal(result, ISC_R_SUCCESS); 517 assert_true(compare_labelsequences(node, "k")); 518 519 /* Node count must have incremented twice ("d.e.f" fissioned to 520 * "d" and "e.f", and the newly added "k"). 521 */ 522 assert_int_equal(19, dns_rbt_nodecount(ctx->rbt)); 523 524 /* Fission the node "g.h" */ 525 node = NULL; 526 result = insert_helper(ctx->rbt, "h.", &node); 527 assert_int_equal(result, ISC_R_SUCCESS); 528 assert_true(compare_labelsequences(node, "h")); 529 530 /* Node count must have incremented ("g.h" fissioned to "g" and 531 * "h"). 532 */ 533 assert_int_equal(20, dns_rbt_nodecount(ctx->rbt)); 534 535 /* Add child domains */ 536 537 node = NULL; 538 result = insert_helper(ctx->rbt, "m.p.w.y.d.e.f.", &node); 539 assert_int_equal(result, ISC_R_SUCCESS); 540 assert_true(compare_labelsequences(node, "m")); 541 assert_int_equal(21, dns_rbt_nodecount(ctx->rbt)); 542 543 node = NULL; 544 result = insert_helper(ctx->rbt, "n.p.w.y.d.e.f.", &node); 545 assert_int_equal(result, ISC_R_SUCCESS); 546 assert_true(compare_labelsequences(node, "n")); 547 assert_int_equal(22, dns_rbt_nodecount(ctx->rbt)); 548 549 node = NULL; 550 result = insert_helper(ctx->rbt, "l.a.", &node); 551 assert_int_equal(result, ISC_R_SUCCESS); 552 assert_true(compare_labelsequences(node, "l")); 553 assert_int_equal(23, dns_rbt_nodecount(ctx->rbt)); 554 555 node = NULL; 556 result = insert_helper(ctx->rbt, "r.d.e.f.", &node); 557 assert_int_equal(result, ISC_R_SUCCESS); 558 node = NULL; 559 result = insert_helper(ctx->rbt, "s.d.e.f.", &node); 560 assert_int_equal(result, ISC_R_SUCCESS); 561 assert_int_equal(25, dns_rbt_nodecount(ctx->rbt)); 562 563 node = NULL; 564 result = insert_helper(ctx->rbt, "h.w.y.d.e.f.", &node); 565 assert_int_equal(result, ISC_R_SUCCESS); 566 567 /* Add more nodes one by one to cover left and right rotation 568 * functions. 569 */ 570 node = NULL; 571 result = insert_helper(ctx->rbt, "f.", &node); 572 assert_int_equal(result, ISC_R_SUCCESS); 573 574 node = NULL; 575 result = insert_helper(ctx->rbt, "m.", &node); 576 assert_int_equal(result, ISC_R_SUCCESS); 577 578 node = NULL; 579 result = insert_helper(ctx->rbt, "nm.", &node); 580 assert_int_equal(result, ISC_R_SUCCESS); 581 582 node = NULL; 583 result = insert_helper(ctx->rbt, "om.", &node); 584 assert_int_equal(result, ISC_R_SUCCESS); 585 586 node = NULL; 587 result = insert_helper(ctx->rbt, "k.", &node); 588 assert_int_equal(result, ISC_R_SUCCESS); 589 590 node = NULL; 591 result = insert_helper(ctx->rbt, "l.", &node); 592 assert_int_equal(result, ISC_R_SUCCESS); 593 594 node = NULL; 595 result = insert_helper(ctx->rbt, "fe.", &node); 596 assert_int_equal(result, ISC_R_SUCCESS); 597 598 node = NULL; 599 result = insert_helper(ctx->rbt, "ge.", &node); 600 assert_int_equal(result, ISC_R_SUCCESS); 601 602 node = NULL; 603 result = insert_helper(ctx->rbt, "i.", &node); 604 assert_int_equal(result, ISC_R_SUCCESS); 605 606 node = NULL; 607 result = insert_helper(ctx->rbt, "ae.", &node); 608 assert_int_equal(result, ISC_R_SUCCESS); 609 610 node = NULL; 611 result = insert_helper(ctx->rbt, "n.", &node); 612 assert_int_equal(result, ISC_R_SUCCESS); 613 614 test_context_teardown(ctx); 615 } 616 617 /* 618 * Test removal from a tree 619 * 620 * This testcase checks that after node removal, the binary-search tree is 621 * valid and all nodes that are supposed to exist are present in the 622 * correct order. It mainly tests DomainTree as a BST, and not particularly 623 * as a red-black tree. This test checks node deletion when upper nodes 624 * have data. 625 */ 626 static isc_result_t 627 deletename(dns_rbt_t *mytree, const dns_name_t *name) { 628 isc_result_t result; 629 dns_rbtnode_t *node = NULL; 630 631 result = dns_rbt_findnode(mytree, name, NULL, &node, NULL, 0, NULL, 632 NULL); 633 if (result == ISC_R_SUCCESS) { 634 if (node->data != NULL) { 635 result = dns_rbt_deletenode(mytree, node, false); 636 } else { 637 result = ISC_R_NOTFOUND; 638 } 639 } else if (result == DNS_R_PARTIALMATCH) { 640 result = ISC_R_NOTFOUND; 641 } 642 643 return result; 644 } 645 646 ISC_RUN_TEST_IMPL(rbt_remove) { 647 isc_result_t result; 648 size_t j; 649 650 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 651 652 /* 653 * Delete single nodes and check if the rest of the nodes exist. 654 */ 655 for (j = 0; j < ordered_names_count; j++) { 656 dns_rbt_t *mytree = NULL; 657 dns_rbtnode_t *node; 658 size_t i; 659 size_t *n; 660 bool tree_ok; 661 dns_rbtnodechain_t chain; 662 size_t start_node; 663 664 /* Create a tree. */ 665 result = dns_rbt_create(mctx, delete_data, NULL, &mytree); 666 assert_int_equal(result, ISC_R_SUCCESS); 667 668 /* Insert test data into the tree. */ 669 for (i = 0; i < domain_names_count; i++) { 670 node = NULL; 671 result = insert_helper(mytree, domain_names[i], &node); 672 assert_int_equal(result, ISC_R_SUCCESS); 673 } 674 675 /* Check that all names exist in order. */ 676 for (i = 0; i < ordered_names_count; i++) { 677 dns_fixedname_t fname; 678 dns_name_t *name; 679 680 dns_test_namefromstring(ordered_names[i], &fname); 681 682 name = dns_fixedname_name(&fname); 683 node = NULL; 684 result = dns_rbt_findnode(mytree, name, NULL, &node, 685 NULL, DNS_RBTFIND_EMPTYDATA, 686 NULL, NULL); 687 assert_int_equal(result, ISC_R_SUCCESS); 688 689 /* Add node data */ 690 assert_non_null(node); 691 assert_null(node->data); 692 693 n = isc_mem_get(mctx, sizeof(size_t)); 694 assert_non_null(n); 695 *n = i; 696 697 node->data = n; 698 } 699 700 /* Now, delete the j'th node from the tree. */ 701 { 702 dns_fixedname_t fname; 703 dns_name_t *name; 704 705 dns_test_namefromstring(ordered_names[j], &fname); 706 707 name = dns_fixedname_name(&fname); 708 709 result = deletename(mytree, name); 710 assert_int_equal(result, ISC_R_SUCCESS); 711 } 712 713 /* Check RB tree properties. */ 714 tree_ok = dns__rbt_checkproperties(mytree); 715 assert_true(tree_ok); 716 717 dns_rbtnodechain_init(&chain); 718 719 /* Now, walk through nodes in order. */ 720 if (j == 0) { 721 /* 722 * Node for ordered_names[0] was already deleted 723 * above. We start from node 1. 724 */ 725 dns_fixedname_t fname; 726 dns_name_t *name; 727 728 dns_test_namefromstring(ordered_names[0], &fname); 729 name = dns_fixedname_name(&fname); 730 node = NULL; 731 result = dns_rbt_findnode(mytree, name, NULL, &node, 732 NULL, 0, NULL, NULL); 733 assert_int_equal(result, ISC_R_NOTFOUND); 734 735 dns_test_namefromstring(ordered_names[1], &fname); 736 name = dns_fixedname_name(&fname); 737 node = NULL; 738 result = dns_rbt_findnode(mytree, name, NULL, &node, 739 &chain, 0, NULL, NULL); 740 assert_int_equal(result, ISC_R_SUCCESS); 741 start_node = 1; 742 } else { 743 /* Start from node 0. */ 744 dns_fixedname_t fname; 745 dns_name_t *name; 746 747 dns_test_namefromstring(ordered_names[0], &fname); 748 name = dns_fixedname_name(&fname); 749 node = NULL; 750 result = dns_rbt_findnode(mytree, name, NULL, &node, 751 &chain, 0, NULL, NULL); 752 assert_int_equal(result, ISC_R_SUCCESS); 753 start_node = 0; 754 } 755 756 /* 757 * node and chain have been set by the code above at 758 * this point. 759 */ 760 for (i = start_node; i < ordered_names_count; i++) { 761 dns_fixedname_t fname_j, fname_i; 762 dns_name_t *name_j, *name_i; 763 764 dns_test_namefromstring(ordered_names[j], &fname_j); 765 name_j = dns_fixedname_name(&fname_j); 766 dns_test_namefromstring(ordered_names[i], &fname_i); 767 name_i = dns_fixedname_name(&fname_i); 768 769 if (dns_name_equal(name_i, name_j)) { 770 /* 771 * This may be true for the last node if 772 * we seek ahead in the loop using 773 * dns_rbtnodechain_next() below. 774 */ 775 if (node == NULL) { 776 break; 777 } 778 779 /* All ordered nodes have data 780 * initially. If any node is empty, it 781 * means it was removed, but an empty 782 * node exists because it is a 783 * super-domain. Just skip it. 784 */ 785 if (node->data == NULL) { 786 result = dns_rbtnodechain_next( 787 &chain, NULL, NULL); 788 if (result == ISC_R_NOMORE) { 789 node = NULL; 790 } else { 791 dns_rbtnodechain_current( 792 &chain, NULL, NULL, 793 &node); 794 } 795 } 796 continue; 797 } 798 799 assert_non_null(node); 800 801 n = (size_t *)node->data; 802 if (n != NULL) { 803 /* printf("n=%zu, i=%zu\n", *n, i); */ 804 assert_int_equal(*n, i); 805 } 806 807 result = dns_rbtnodechain_next(&chain, NULL, NULL); 808 if (result == ISC_R_NOMORE) { 809 node = NULL; 810 } else { 811 dns_rbtnodechain_current(&chain, NULL, NULL, 812 &node); 813 } 814 } 815 816 /* We should have reached the end of the tree. */ 817 assert_null(node); 818 819 dns_rbt_destroy(&mytree, 0); 820 } 821 } 822 823 static void 824 insert_nodes(dns_rbt_t *mytree, char **names, size_t *names_count, 825 uint32_t num_names) { 826 uint32_t i; 827 dns_rbtnode_t *node; 828 829 for (i = 0; i < num_names; i++) { 830 size_t *n; 831 char namebuf[34]; 832 833 n = isc_mem_get(mctx, sizeof(size_t)); 834 assert_non_null(n); 835 836 *n = i; /* Unused value */ 837 838 while (1) { 839 int j; 840 dns_fixedname_t fname; 841 dns_name_t *name; 842 isc_result_t result; 843 844 for (j = 0; j < 32; j++) { 845 uint32_t v = isc_random_uniform(26); 846 namebuf[j] = 'a' + v; 847 } 848 namebuf[32] = '.'; 849 namebuf[33] = 0; 850 851 dns_test_namefromstring(namebuf, &fname); 852 name = dns_fixedname_name(&fname); 853 854 node = NULL; 855 result = dns_rbt_addnode(mytree, name, &node); 856 if (result == ISC_R_SUCCESS) { 857 node->data = n; 858 names[*names_count] = isc_mem_strdup(mctx, 859 namebuf); 860 assert_non_null(names[*names_count]); 861 *names_count += 1; 862 break; 863 } 864 } 865 } 866 } 867 868 static void 869 remove_nodes(dns_rbt_t *mytree, char **names, size_t *names_count, 870 uint32_t num_names) { 871 uint32_t i; 872 873 UNUSED(mytree); 874 875 for (i = 0; i < num_names; i++) { 876 isc_result_t result; 877 dns_fixedname_t fname; 878 dns_name_t *name = NULL; 879 uint32_t num; 880 881 num = isc_random_uniform(*names_count); 882 883 dns_test_namefromstring(names[num], &fname); 884 name = dns_fixedname_name(&fname); 885 886 result = deletename(mytree, name); 887 assert_int_equal(result, ISC_R_SUCCESS); 888 889 isc_mem_free(mctx, names[num]); 890 if (*names_count > 0) { 891 names[num] = names[*names_count - 1]; 892 names[*names_count - 1] = NULL; 893 *names_count -= 1; 894 } 895 } 896 } 897 898 static void 899 check_tree(dns_rbt_t *mytree, char **names, size_t names_count) { 900 bool tree_ok; 901 902 UNUSED(names); 903 904 assert_int_equal(names_count + 1, dns_rbt_nodecount(mytree)); 905 906 /* 907 * The distance from each node to its sub-tree root must be less 908 * than 2 * log_2(1024). 909 */ 910 assert_true((2 * 10) >= dns__rbt_getheight(mytree)); 911 912 /* Also check RB tree properties */ 913 tree_ok = dns__rbt_checkproperties(mytree); 914 assert_true(tree_ok); 915 } 916 917 /* 918 * Test insert and remove in a loop. 919 * 920 * What is the best way to test our red-black tree code? It is 921 * not a good method to test every case handled in the actual 922 * code itself. This is because our approach itself may be 923 * incorrect. 924 * 925 * We test our code at the interface level here by exercising the 926 * tree randomly multiple times, checking that red-black tree 927 * properties are valid, and all the nodes that are supposed to be 928 * in the tree exist and are in order. 929 * 930 * NOTE: These tests are run within a single tree level in the 931 * forest. The number of nodes in the tree level doesn't grow 932 * over 1024. 933 */ 934 ISC_RUN_TEST_IMPL(rbt_insert_and_remove) { 935 isc_result_t result; 936 dns_rbt_t *mytree = NULL; 937 size_t *n = NULL; 938 dns_rbtnode_t *node = NULL; 939 char *names[1024]; 940 size_t names_count; 941 int i; 942 943 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 944 945 result = dns_rbt_create(mctx, delete_data, NULL, &mytree); 946 assert_int_equal(result, ISC_R_SUCCESS); 947 948 n = isc_mem_get(mctx, sizeof(size_t)); 949 assert_non_null(n); 950 result = dns_rbt_addnode(mytree, dns_rootname, &node); 951 assert_int_equal(result, ISC_R_SUCCESS); 952 node->data = n; 953 954 memset(names, 0, sizeof(names)); 955 names_count = 0; 956 957 /* Repeat the insert/remove test some 4096 times */ 958 for (i = 0; i < 4096; i++) { 959 uint32_t num_names; 960 961 if (names_count < 1024) { 962 num_names = isc_random_uniform(1024 - names_count); 963 num_names++; 964 } else { 965 num_names = 0; 966 } 967 968 insert_nodes(mytree, names, &names_count, num_names); 969 check_tree(mytree, names, names_count); 970 971 if (names_count > 0) { 972 num_names = isc_random_uniform(names_count); 973 num_names++; 974 } else { 975 num_names = 0; 976 } 977 978 remove_nodes(mytree, names, &names_count, num_names); 979 check_tree(mytree, names, names_count); 980 } 981 982 /* Remove the rest of the nodes */ 983 remove_nodes(mytree, names, &names_count, names_count); 984 check_tree(mytree, names, names_count); 985 986 for (i = 0; i < 1024; i++) { 987 if (names[i] != NULL) { 988 isc_mem_free(mctx, names[i]); 989 } 990 } 991 992 result = deletename(mytree, dns_rootname); 993 assert_int_equal(result, ISC_R_SUCCESS); 994 assert_int_equal(dns_rbt_nodecount(mytree), 0); 995 996 dns_rbt_destroy(&mytree, 0); 997 } 998 999 /* Test nodechain */ 1000 ISC_RUN_TEST_IMPL(rbt_nodechain) { 1001 isc_result_t result; 1002 test_context_t *ctx; 1003 dns_fixedname_t fname, found, expect; 1004 dns_name_t *name, *foundname, *expected; 1005 dns_rbtnode_t *node = NULL; 1006 dns_rbtnodechain_t chain; 1007 1008 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 1009 1010 ctx = test_context_setup(); 1011 1012 dns_rbtnodechain_init(&chain); 1013 1014 dns_test_namefromstring("a.", &fname); 1015 name = dns_fixedname_name(&fname); 1016 1017 result = dns_rbt_findnode(ctx->rbt, name, NULL, &node, &chain, 0, NULL, 1018 NULL); 1019 assert_int_equal(result, ISC_R_SUCCESS); 1020 1021 foundname = dns_fixedname_initname(&found); 1022 1023 dns_test_namefromstring("a.", &expect); 1024 expected = dns_fixedname_name(&expect); 1025 UNUSED(expected); 1026 1027 result = dns_rbtnodechain_first(&chain, ctx->rbt, foundname, NULL); 1028 assert_int_equal(result, DNS_R_NEWORIGIN); 1029 assert_int_equal(dns_name_countlabels(foundname), 0); 1030 1031 result = dns_rbtnodechain_prev(&chain, NULL, NULL); 1032 assert_int_equal(result, ISC_R_NOMORE); 1033 1034 result = dns_rbtnodechain_next(&chain, NULL, NULL); 1035 assert_int_equal(result, ISC_R_SUCCESS); 1036 1037 result = dns_rbtnodechain_next(&chain, NULL, NULL); 1038 assert_int_equal(result, ISC_R_SUCCESS); 1039 1040 result = dns_rbtnodechain_last(&chain, ctx->rbt, NULL, NULL); 1041 assert_int_equal(result, DNS_R_NEWORIGIN); 1042 1043 result = dns_rbtnodechain_next(&chain, NULL, NULL); 1044 assert_int_equal(result, ISC_R_NOMORE); 1045 1046 result = dns_rbtnodechain_last(&chain, ctx->rbt, NULL, NULL); 1047 assert_int_equal(result, DNS_R_NEWORIGIN); 1048 1049 result = dns_rbtnodechain_prev(&chain, NULL, NULL); 1050 assert_int_equal(result, ISC_R_SUCCESS); 1051 1052 dns_rbtnodechain_invalidate(&chain); 1053 1054 test_context_teardown(ctx); 1055 } 1056 1057 /* Test name lengths */ 1058 ISC_RUN_TEST_IMPL(rbtnode_namelen) { 1059 isc_result_t result; 1060 test_context_t *ctx = NULL; 1061 dns_rbtnode_t *node; 1062 unsigned int len; 1063 1064 isc_mem_debugging = ISC_MEM_DEBUGRECORD; 1065 1066 ctx = test_context_setup(); 1067 1068 node = NULL; 1069 result = insert_helper(ctx->rbt, ".", &node); 1070 len = dns__rbtnode_namelen(node); 1071 assert_int_equal(result, ISC_R_EXISTS); 1072 assert_int_equal(len, 1); 1073 node = NULL; 1074 1075 result = insert_helper(ctx->rbt, "a.b.c.d.e.f.g.h.i.j.k.l.m.", &node); 1076 len = dns__rbtnode_namelen(node); 1077 assert_int_equal(result, ISC_R_SUCCESS); 1078 assert_int_equal(len, 27); 1079 1080 node = NULL; 1081 result = insert_helper(ctx->rbt, "isc.org.", &node); 1082 len = dns__rbtnode_namelen(node); 1083 assert_int_equal(result, ISC_R_SUCCESS); 1084 assert_int_equal(len, 9); 1085 1086 node = NULL; 1087 result = insert_helper(ctx->rbt, "example.com.", &node); 1088 len = dns__rbtnode_namelen(node); 1089 assert_int_equal(result, ISC_R_SUCCESS); 1090 assert_int_equal(len, 13); 1091 1092 test_context_teardown(ctx); 1093 } 1094 1095 #if defined(DNS_BENCHMARK_TESTS) && !defined(__SANITIZE_THREAD__) 1096 1097 /* 1098 * XXXMUKS: Don't delete this code. It is useful in benchmarking the 1099 * RBT, but we don't require it as part of the unit test runs. 1100 */ 1101 1102 static dns_fixedname_t *fnames; 1103 static dns_name_t **names; 1104 static int *values; 1105 1106 static void * 1107 find_thread(void *arg) { 1108 dns_rbt_t *mytree; 1109 isc_result_t result; 1110 dns_rbtnode_t *node; 1111 unsigned int j, i; 1112 unsigned int start = 0; 1113 1114 mytree = (dns_rbt_t *)arg; 1115 while (start == 0) { 1116 start = random() % 4000000; 1117 } 1118 1119 /* Query 32 million random names from it in each thread */ 1120 for (j = 0; j < 8; j++) { 1121 for (i = start; i != start - 1; i = (i + 1) % 4000000) { 1122 node = NULL; 1123 result = dns_rbt_findnode(mytree, names[i], NULL, &node, 1124 NULL, DNS_RBTFIND_EMPTYDATA, 1125 NULL, NULL); 1126 assert_int_equal(result, ISC_R_SUCCESS); 1127 assert_non_null(node); 1128 assert_int_equal(values[i], (intptr_t)node->data); 1129 } 1130 } 1131 1132 return NULL; 1133 } 1134 1135 /* Benchmark RBT implementation */ 1136 ISC_RUN_TEST_IMPL(benchmark) { 1137 isc_result_t result; 1138 char namestr[sizeof("name18446744073709551616.example.org.")]; 1139 unsigned int r; 1140 dns_rbt_t *mytree; 1141 dns_rbtnode_t *node; 1142 unsigned int i; 1143 unsigned int maxvalue = 1000000; 1144 isc_time_t ts1, ts2; 1145 double t; 1146 unsigned int nthreads; 1147 isc_thread_t threads[32]; 1148 1149 srandom(time(NULL)); 1150 1151 debug_mem_record = false; 1152 1153 fnames = (dns_fixedname_t *)malloc(4000000 * sizeof(dns_fixedname_t)); 1154 names = (dns_name_t **)malloc(4000000 * sizeof(dns_name_t *)); 1155 values = (int *)malloc(4000000 * sizeof(int)); 1156 1157 for (i = 0; i < 4000000; i++) { 1158 r = ((unsigned long)random()) % maxvalue; 1159 snprintf(namestr, sizeof(namestr), "name%u.example.org.", r); 1160 dns_test_namefromstring(namestr, &fnames[i]); 1161 names[i] = dns_fixedname_name(&fnames[i]); 1162 values[i] = r; 1163 } 1164 1165 /* Create a tree. */ 1166 mytree = NULL; 1167 result = dns_rbt_create(mctx, NULL, NULL, &mytree); 1168 assert_int_equal(result, ISC_R_SUCCESS); 1169 1170 /* Insert test data into the tree. */ 1171 for (i = 0; i < maxvalue; i++) { 1172 snprintf(namestr, sizeof(namestr), "name%u.example.org.", i); 1173 node = NULL; 1174 result = insert_helper(mytree, namestr, &node); 1175 assert_int_equal(result, ISC_R_SUCCESS); 1176 node->data = (void *)(intptr_t)i; 1177 } 1178 1179 ts1 = isc_time_now(); 1180 1181 nthreads = ISC_MIN(isc_os_ncpus(), 32); 1182 nthreads = ISC_MAX(nthreads, 1); 1183 for (i = 0; i < nthreads; i++) { 1184 isc_thread_create(find_thread, mytree, &threads[i]); 1185 } 1186 1187 for (i = 0; i < nthreads; i++) { 1188 isc_thread_join(threads[i], NULL); 1189 } 1190 1191 ts2 = isc_time_now(); 1192 1193 t = isc_time_microdiff(&ts2, &ts1); 1194 1195 printf("%u findnode calls, %f seconds, %f calls/second\n", 1196 nthreads * 8 * 4000000, t / 1000000.0, 1197 (nthreads * 8 * 4000000) / (t / 1000000.0)); 1198 1199 free(values); 1200 free(names); 1201 free(fnames); 1202 1203 dns_rbt_destroy(&mytree, 0); 1204 } 1205 #endif /* defined(DNS_BENCHMARK_TESTS) && !defined(__SANITIZE_THREAD__) */ 1206 1207 ISC_TEST_LIST_START 1208 ISC_TEST_ENTRY(rbt_create) 1209 ISC_TEST_ENTRY(rbt_nodecount) 1210 ISC_TEST_ENTRY(rbtnode_get_distance) 1211 ISC_TEST_ENTRY(rbt_check_distance_random) 1212 ISC_TEST_ENTRY(rbt_check_distance_ordered) 1213 ISC_TEST_ENTRY(rbt_insert) 1214 ISC_TEST_ENTRY(rbt_remove) 1215 ISC_TEST_ENTRY(rbt_insert_and_remove) 1216 ISC_TEST_ENTRY(rbt_nodechain) 1217 ISC_TEST_ENTRY(rbtnode_namelen) 1218 #if defined(DNS_BENCHMARK_TESTS) && !defined(__SANITIZE_THREAD__) 1219 ISC_TEST_ENTRY(benchmark) 1220 #endif /* defined(DNS_BENCHMARK_TESTS) && !defined(__SANITIZE_THREAD__) */ 1221 1222 ISC_TEST_LIST_END 1223 1224 ISC_TEST_MAIN 1225