1 /* $NetBSD: rbt_test.c,v 1.8 2023/06/26 22:02:59 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 <stdbool.h>
17 #include <stdlib.h>
18
19 #include <isc/commandline.h>
20 #include <isc/mem.h>
21 #include <isc/print.h>
22 #include <isc/string.h>
23 #include <isc/util.h>
24
25 #include <dns/fixedname.h>
26 #include <dns/rbt.h>
27 #include <dns/result.h>
28
29 const char *progname;
30 isc_mem_t *mctx;
31
32 #define DNSNAMELEN 255
33
34 static dns_name_t *
create_name(char * s)35 create_name(char *s) {
36 int length;
37 isc_result_t result;
38 isc_buffer_t source, target;
39 static dns_name_t *name;
40
41 if (s == NULL || *s == '\0') {
42 printf("missing name argument\n");
43 return (NULL);
44 }
45
46 length = strlen(s);
47
48 isc_buffer_init(&source, s, length);
49 isc_buffer_add(&source, length);
50
51 /*
52 * It isn't really necessary in this program to create individual
53 * memory spaces for each name structure and its associated character
54 * string. It is done here to provide a relatively easy way to test
55 * the callback from dns_rbt_deletename that is supposed to free the
56 * data associated with a node.
57 *
58 * The buffer for the actual name will immediately follow the
59 * name structure.
60 */
61 name = isc_mem_get(mctx, sizeof(*name) + DNSNAMELEN);
62
63 dns_name_init(name, NULL);
64 isc_buffer_init(&target, name + 1, DNSNAMELEN);
65
66 result = dns_name_fromtext(name, &source, dns_rootname, 0, &target);
67
68 if (result != ISC_R_SUCCESS) {
69 printf("dns_name_fromtext(%s) failed: %s\n", s,
70 dns_result_totext(result));
71 return (NULL);
72 }
73
74 return (name);
75 }
76
77 static void
delete_name(void * data,void * arg)78 delete_name(void *data, void *arg) {
79 dns_name_t *name;
80
81 UNUSED(arg);
82 name = data;
83 isc_mem_put(mctx, name, sizeof(*name) + DNSNAMELEN);
84 }
85
86 static void
print_name(dns_name_t * name)87 print_name(dns_name_t *name) {
88 isc_buffer_t target;
89 char buffer[1024];
90
91 isc_buffer_init(&target, buffer, sizeof(buffer));
92
93 /*
94 * false means absolute names have the final dot added.
95 */
96 dns_name_totext(name, false, &target);
97
98 printf("%.*s", (int)target.used, (char *)target.base);
99 }
100
101 static void
detail(dns_rbt_t * rbt,dns_name_t * name)102 detail(dns_rbt_t *rbt, dns_name_t *name) {
103 dns_name_t *foundname, *origin, *fullname;
104 dns_fixedname_t fixedfoundname, fixedorigin, fixedfullname;
105 dns_rbtnode_t *node1, *node2;
106 dns_rbtnodechain_t chain;
107 isc_result_t result;
108 bool nodes_should_match = false;
109
110 dns_rbtnodechain_init(&chain);
111
112 origin = dns_fixedname_initname(&fixedorigin);
113 fullname = dns_fixedname_initname(&fixedfullname);
114 foundname = dns_fixedname_initname(&fixedfoundname);
115
116 node1 = node2 = NULL;
117
118 printf("checking chain information for ");
119 print_name(name);
120 printf("\n");
121
122 result = dns_rbt_findnode(rbt, name, foundname, &node1, &chain,
123 DNS_RBTFIND_EMPTYDATA, NULL, NULL);
124
125 switch (result) {
126 case ISC_R_SUCCESS:
127 printf(" found exact.");
128 nodes_should_match = true;
129 break;
130 case DNS_R_PARTIALMATCH:
131 printf(" found parent.");
132 break;
133 case ISC_R_NOTFOUND:
134 printf(" name not found.");
135 break;
136 default:
137 printf(" unexpected result: %s\n", dns_result_totext(result));
138 return;
139 }
140
141 if (node1 != NULL && node1->data != NULL) {
142 printf(" data at node: ");
143 print_name(node1->data);
144 } else {
145 printf(" no data at node.");
146 }
147
148 if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH) {
149 printf("\n name from dns_rbt_findnode: ");
150 print_name(foundname);
151 }
152
153 result = dns_rbtnodechain_current(&chain, foundname, origin, &node2);
154
155 if (result == ISC_R_SUCCESS) {
156 printf("\n name from dns_rbtnodechain_current: ");
157
158 result = dns_name_concatenate(foundname, origin, fullname,
159 NULL);
160 if (result == ISC_R_SUCCESS) {
161 print_name(fullname);
162 } else {
163 printf("%s\n", dns_result_totext(result));
164 }
165 printf("\n (foundname = ");
166 print_name(foundname);
167 printf(", origin = ");
168 print_name(origin);
169 printf(")\n");
170 if (nodes_should_match && node1 != node2) {
171 printf(" nodes returned from each function "
172 "DO NOT match!\n");
173 }
174 } else {
175 printf("\n result from dns_rbtnodechain_current: %s\n",
176 dns_result_totext(result));
177 }
178
179 printf(" level_matches = %u, level_count = %u\n", chain.level_matches,
180 chain.level_count);
181 }
182
183 static void
iterate(dns_rbt_t * rbt,bool forward)184 iterate(dns_rbt_t *rbt, bool forward) {
185 dns_name_t foundname, *origin;
186 dns_rbtnodechain_t chain;
187 dns_fixedname_t fixedorigin;
188 isc_result_t result;
189 isc_result_t (*move)(dns_rbtnodechain_t *chain, dns_name_t *name,
190 dns_name_t *origin);
191
192 dns_rbtnodechain_init(&chain);
193
194 dns_name_init(&foundname, NULL);
195 origin = dns_fixedname_initname(&fixedorigin);
196
197 if (forward) {
198 printf("iterating forward\n");
199 move = dns_rbtnodechain_next;
200
201 result = dns_rbtnodechain_first(&chain, rbt, &foundname,
202 origin);
203 } else {
204 printf("iterating backward\n");
205 move = dns_rbtnodechain_prev;
206
207 result = dns_rbtnodechain_last(&chain, rbt, &foundname, origin);
208 }
209
210 if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN) {
211 printf("start not found!\n");
212 } else {
213 for (;;) {
214 if (result == DNS_R_NEWORIGIN) {
215 printf(" new origin: ");
216 print_name(origin);
217 printf("\n");
218 }
219
220 if (result == ISC_R_SUCCESS ||
221 result == DNS_R_NEWORIGIN)
222 {
223 print_name(&foundname);
224 printf("\n");
225 } else {
226 if (result != ISC_R_NOMORE) {
227 printf("UNEXPECTED ITERATION ERROR: %s",
228 dns_result_totext(result));
229 }
230 break;
231 }
232
233 result = move(&chain, &foundname, origin);
234 }
235 }
236 }
237
238 #define CMDCHECK(s) (strncasecmp(command, (s), length) == 0)
239 #define PRINTERR(r) \
240 if (r != ISC_R_SUCCESS) \
241 printf("... %s\n", dns_result_totext(r));
242
243 int
main(int argc,char ** argv)244 main(int argc, char **argv) {
245 char *command, *arg, buffer[1024];
246 const char *whitespace;
247 dns_name_t *name, *foundname;
248 dns_fixedname_t fixedname;
249 dns_rbt_t *rbt = NULL;
250 int length, ch;
251 bool show_final_mem = false;
252 isc_result_t result;
253 void *data;
254
255 progname = strrchr(*argv, '/');
256 if (progname != NULL) {
257 progname++;
258 } else {
259 progname = *argv;
260 }
261
262 while ((ch = isc_commandline_parse(argc, argv, "m")) != -1) {
263 switch (ch) {
264 case 'm':
265 show_final_mem = true;
266 break;
267 }
268 }
269
270 argc -= isc_commandline_index;
271 argv += isc_commandline_index;
272 POST(argv);
273
274 if (argc > 1) {
275 printf("Usage: %s [-m]\n", progname);
276 exit(1);
277 }
278
279 setbuf(stdout, NULL);
280
281 /*
282 * So isc_mem_stats() can report any allocation leaks.
283 */
284 isc_mem_debugging = ISC_MEM_DEBUGRECORD;
285
286 isc_mem_create(&mctx);
287
288 result = dns_rbt_create(mctx, delete_name, NULL, &rbt);
289 if (result != ISC_R_SUCCESS) {
290 printf("dns_rbt_create: %s: exiting\n",
291 dns_result_totext(result));
292 exit(1);
293 }
294
295 whitespace = " \t";
296
297 while (fgets(buffer, sizeof(buffer), stdin) != NULL) {
298 length = strlen(buffer);
299
300 if (buffer[length - 1] != '\n') {
301 printf("line to long (%lu max), ignored\n",
302 (unsigned long)sizeof(buffer) - 2);
303 continue;
304 }
305
306 buffer[length - 1] = '\0';
307
308 command = buffer + strspn(buffer, whitespace);
309
310 if (*command == '#') {
311 continue;
312 }
313
314 arg = strpbrk(command, whitespace);
315 if (arg != NULL) {
316 *arg++ = '\0';
317 arg += strspn(arg, whitespace);
318 }
319
320 length = strlen(command);
321 if (*command != '\0') {
322 if (CMDCHECK("add")) {
323 name = create_name(arg);
324 if (name != NULL) {
325 printf("adding name %s\n", arg);
326 result = dns_rbt_addname(rbt, name,
327 name);
328 PRINTERR(result);
329 }
330 } else if (CMDCHECK("delete")) {
331 name = create_name(arg);
332 if (name != NULL) {
333 printf("deleting name %s\n", arg);
334 result = dns_rbt_deletename(rbt, name,
335 false);
336 PRINTERR(result);
337 delete_name(name, NULL);
338 }
339 } else if (CMDCHECK("nuke")) {
340 name = create_name(arg);
341 if (name != NULL) {
342 printf("nuking name %s "
343 "and its descendants\n",
344 arg);
345 result = dns_rbt_deletename(rbt, name,
346 true);
347 PRINTERR(result);
348 delete_name(name, NULL);
349 }
350 } else if (CMDCHECK("search")) {
351 name = create_name(arg);
352 if (name != NULL) {
353 printf("searching for name %s ... ",
354 arg);
355
356 foundname = dns_fixedname_initname(
357 &fixedname);
358 data = NULL;
359
360 result = dns_rbt_findname(
361 rbt, name, 0, foundname, &data);
362 switch (result) {
363 case ISC_R_SUCCESS:
364 printf("found exact: ");
365 print_name(data);
366 putchar('\n');
367 break;
368 case DNS_R_PARTIALMATCH:
369 printf("found parent: ");
370 print_name(data);
371 printf("\n\t(foundname: ");
372 print_name(foundname);
373 printf(")\n");
374 break;
375 case ISC_R_NOTFOUND:
376 printf("NOT FOUND!\n");
377 break;
378 case ISC_R_NOMEMORY:
379 printf("OUT OF MEMORY!\n");
380 break;
381 default:
382 printf("UNEXPECTED RESULT\n");
383 }
384
385 delete_name(name, NULL);
386 }
387 } else if (CMDCHECK("check")) {
388 /*
389 * Or "chain". I know, I know. Lame name.
390 * I was having a hard time thinking of a
391 * name (especially one that did not have
392 * a conflicting first letter with another
393 * command) that would differentiate this
394 * from the search command.
395 *
396 * But it is just a test program, eh?
397 */
398 name = create_name(arg);
399 if (name != NULL) {
400 detail(rbt, name);
401
402 delete_name(name, NULL);
403 }
404 } else if (CMDCHECK("forward")) {
405 iterate(rbt, true);
406 } else if (CMDCHECK("backward")) {
407 iterate(rbt, false);
408 } else if (CMDCHECK("print")) {
409 if (arg == NULL || *arg == '\0') {
410 dns_rbt_printtext(rbt, NULL, stdout);
411 } else {
412 printf("usage: print\n");
413 }
414 } else if (CMDCHECK("quit")) {
415 if (arg == NULL || *arg == '\0') {
416 break;
417 } else {
418 printf("usage: quit\n");
419 }
420 } else {
421 printf("a(dd) NAME, d(elete) NAME, "
422 "s(earch) NAME, p(rint), or q(uit)\n");
423 }
424 }
425 }
426
427 dns_rbt_destroy(&rbt);
428
429 if (show_final_mem) {
430 isc_mem_stats(mctx, stderr);
431 }
432
433 return (0);
434 }
435