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