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