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