xref: /freebsd/contrib/unbound/iterator/iter_fwd.c (revision b6a05070fa77edc7ce6e60b61623fd806e807be6)
1 /*
2  * iterator/iter_fwd.c - iterative resolver module forward zones.
3  *
4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
5  *
6  * This software is open source.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  *
15  * Redistributions in binary form must reproduce the above copyright notice,
16  * this list of conditions and the following disclaimer in the documentation
17  * and/or other materials provided with the distribution.
18  *
19  * Neither the name of the NLNET LABS nor the names of its contributors may
20  * be used to endorse or promote products derived from this software without
21  * specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35 
36 /**
37  * \file
38  *
39  * This file contains functions to assist the iterator module.
40  * Keep track of forward zones and config settings.
41  */
42 #include "config.h"
43 #include "iterator/iter_fwd.h"
44 #include "iterator/iter_delegpt.h"
45 #include "util/log.h"
46 #include "util/config_file.h"
47 #include "util/net_help.h"
48 #include "util/data/dname.h"
49 #include "sldns/rrdef.h"
50 #include "sldns/str2wire.h"
51 
52 int
53 fwd_cmp(const void* k1, const void* k2)
54 {
55 	int m;
56 	struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1;
57 	struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2;
58 	if(n1->dclass != n2->dclass) {
59 		if(n1->dclass < n2->dclass)
60 			return -1;
61 		return 1;
62 	}
63 	return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs,
64 		&m);
65 }
66 
67 struct iter_forwards*
68 forwards_create(void)
69 {
70 	struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
71 		sizeof(struct iter_forwards));
72 	if(!fwd)
73 		return NULL;
74 	return fwd;
75 }
76 
77 static void fwd_zone_free(struct iter_forward_zone* n)
78 {
79 	if(!n) return;
80 	delegpt_free_mlc(n->dp);
81 	free(n->name);
82 	free(n);
83 }
84 
85 static void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg))
86 {
87 	struct iter_forward_zone* node = (struct iter_forward_zone*)n;
88 	fwd_zone_free(node);
89 }
90 
91 static void fwd_del_tree(struct iter_forwards* fwd)
92 {
93 	if(fwd->tree)
94 		traverse_postorder(fwd->tree, &delfwdnode, NULL);
95 	free(fwd->tree);
96 }
97 
98 void
99 forwards_delete(struct iter_forwards* fwd)
100 {
101 	if(!fwd)
102 		return;
103 	fwd_del_tree(fwd);
104 	free(fwd);
105 }
106 
107 /** insert info into forward structure */
108 static int
109 forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
110 	size_t nmlen, int nmlabs, struct delegpt* dp)
111 {
112 	struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
113 		sizeof(struct iter_forward_zone));
114 	if(!node) {
115 		delegpt_free_mlc(dp);
116 		return 0;
117 	}
118 	node->node.key = node;
119 	node->dclass = c;
120 	node->name = memdup(nm, nmlen);
121 	if(!node->name) {
122 		delegpt_free_mlc(dp);
123 		free(node);
124 		return 0;
125 	}
126 	node->namelen = nmlen;
127 	node->namelabs = nmlabs;
128 	node->dp = dp;
129 	if(!rbtree_insert(fwd->tree, &node->node)) {
130 		char buf[257];
131 		dname_str(nm, buf);
132 		log_err("duplicate forward zone %s ignored.", buf);
133 		delegpt_free_mlc(dp);
134 		free(node->name);
135 		free(node);
136 	}
137 	return 1;
138 }
139 
140 /** insert new info into forward structure given dp */
141 static int
142 forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
143 {
144 	return forwards_insert_data(fwd, c, dp->name, dp->namelen,
145 		dp->namelabs, dp);
146 }
147 
148 /** initialise parent pointers in the tree */
149 static void
150 fwd_init_parents(struct iter_forwards* fwd)
151 {
152 	struct iter_forward_zone* node, *prev = NULL, *p;
153 	int m;
154 	RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
155 		node->parent = NULL;
156 		if(!prev || prev->dclass != node->dclass) {
157 			prev = node;
158 			continue;
159 		}
160 		(void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
161 			node->namelabs, &m); /* we know prev is smaller */
162 		/* sort order like: . com. bla.com. zwb.com. net. */
163 		/* find the previous, or parent-parent-parent */
164 		for(p = prev; p; p = p->parent)
165 			/* looking for name with few labels, a parent */
166 			if(p->namelabs <= m) {
167 				/* ==: since prev matched m, this is closest*/
168 				/* <: prev matches more, but is not a parent,
169 				 * this one is a (grand)parent */
170 				node->parent = p;
171 				break;
172 			}
173 		prev = node;
174 	}
175 }
176 
177 /** set zone name */
178 static struct delegpt*
179 read_fwds_name(struct config_stub* s)
180 {
181 	struct delegpt* dp;
182 	uint8_t* dname;
183 	size_t dname_len;
184 	if(!s->name) {
185 		log_err("forward zone without a name (use name \".\" to forward everything)");
186 		return NULL;
187 	}
188 	dname = sldns_str2wire_dname(s->name, &dname_len);
189 	if(!dname) {
190 		log_err("cannot parse forward zone name %s", s->name);
191 		return NULL;
192 	}
193 	if(!(dp=delegpt_create_mlc(dname))) {
194 		free(dname);
195 		log_err("out of memory");
196 		return NULL;
197 	}
198 	free(dname);
199 	return dp;
200 }
201 
202 /** set fwd host names */
203 static int
204 read_fwds_host(struct config_stub* s, struct delegpt* dp)
205 {
206 	struct config_strlist* p;
207 	uint8_t* dname;
208 	size_t dname_len;
209 	for(p = s->hosts; p; p = p->next) {
210 		log_assert(p->str);
211 		dname = sldns_str2wire_dname(p->str, &dname_len);
212 		if(!dname) {
213 			log_err("cannot parse forward %s server name: '%s'",
214 				s->name, p->str);
215 			return 0;
216 		}
217 		if(!delegpt_add_ns_mlc(dp, dname, 0)) {
218 			free(dname);
219 			log_err("out of memory");
220 			return 0;
221 		}
222 		free(dname);
223 	}
224 	return 1;
225 }
226 
227 /** set fwd server addresses */
228 static int
229 read_fwds_addr(struct config_stub* s, struct delegpt* dp)
230 {
231 	struct config_strlist* p;
232 	struct sockaddr_storage addr;
233 	socklen_t addrlen;
234 	for(p = s->addrs; p; p = p->next) {
235 		log_assert(p->str);
236 		if(!extstrtoaddr(p->str, &addr, &addrlen)) {
237 			log_err("cannot parse forward %s ip address: '%s'",
238 				s->name, p->str);
239 			return 0;
240 		}
241 		if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) {
242 			log_err("out of memory");
243 			return 0;
244 		}
245 	}
246 	return 1;
247 }
248 
249 /** read forwards config */
250 static int
251 read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
252 {
253 	struct config_stub* s;
254 	for(s = cfg->forwards; s; s = s->next) {
255 		struct delegpt* dp;
256 		if(!(dp=read_fwds_name(s)))
257 			return 0;
258 		if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
259 			delegpt_free_mlc(dp);
260 			return 0;
261 		}
262 		/* set flag that parent side NS information is included.
263 		 * Asking a (higher up) server on the internet is not useful */
264 		/* the flag is turned off for 'forward-first' so that the
265 		 * last resort will ask for parent-side NS record and thus
266 		 * fallback to the internet name servers on a failure */
267 		dp->has_parent_side_NS = (uint8_t)!s->isfirst;
268 		verbose(VERB_QUERY, "Forward zone server list:");
269 		delegpt_log(VERB_QUERY, dp);
270 		if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
271 			return 0;
272 	}
273 	return 1;
274 }
275 
276 /** insert a stub hole (if necessary) for stub name */
277 static int
278 fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
279 {
280 	struct iter_forward_zone key;
281 	key.node.key = &key;
282 	key.dclass = c;
283 	key.name = nm;
284 	key.namelabs = dname_count_size_labels(key.name, &key.namelen);
285 	return forwards_insert_data(fwd, key.dclass, key.name,
286 		key.namelen, key.namelabs, NULL);
287 }
288 
289 /** make NULL entries for stubs */
290 static int
291 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
292 {
293 	struct config_stub* s;
294 	uint8_t* dname;
295 	size_t dname_len;
296 	for(s = cfg->stubs; s; s = s->next) {
297 		dname = sldns_str2wire_dname(s->name, &dname_len);
298 		if(!dname) {
299 			log_err("cannot parse stub name '%s'", s->name);
300 			return 0;
301 		}
302 		if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
303 			free(dname);
304 			log_err("out of memory");
305 			return 0;
306 		}
307 		free(dname);
308 	}
309 	return 1;
310 }
311 
312 int
313 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
314 {
315 	fwd_del_tree(fwd);
316 	fwd->tree = rbtree_create(fwd_cmp);
317 	if(!fwd->tree)
318 		return 0;
319 
320 	/* read forward zones */
321 	if(!read_forwards(fwd, cfg))
322 		return 0;
323 	if(!make_stub_holes(fwd, cfg))
324 		return 0;
325 	fwd_init_parents(fwd);
326 	return 1;
327 }
328 
329 struct delegpt*
330 forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
331 {
332 	rbnode_t* res = NULL;
333 	struct iter_forward_zone key;
334 	key.node.key = &key;
335 	key.dclass = qclass;
336 	key.name = qname;
337 	key.namelabs = dname_count_size_labels(qname, &key.namelen);
338 	res = rbtree_search(fwd->tree, &key);
339 	if(res) return ((struct iter_forward_zone*)res)->dp;
340 	return NULL;
341 }
342 
343 struct delegpt*
344 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
345 {
346 	/* lookup the forward zone in the tree */
347 	rbnode_t* res = NULL;
348 	struct iter_forward_zone *result;
349 	struct iter_forward_zone key;
350 	key.node.key = &key;
351 	key.dclass = qclass;
352 	key.name = qname;
353 	key.namelabs = dname_count_size_labels(qname, &key.namelen);
354 	if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
355 		/* exact */
356 		result = (struct iter_forward_zone*)res;
357 	} else {
358 		/* smaller element (or no element) */
359 		int m;
360 		result = (struct iter_forward_zone*)res;
361 		if(!result || result->dclass != qclass)
362 			return NULL;
363 		/* count number of labels matched */
364 		(void)dname_lab_cmp(result->name, result->namelabs, key.name,
365 			key.namelabs, &m);
366 		while(result) { /* go up until qname is subdomain of stub */
367 			if(result->namelabs <= m)
368 				break;
369 			result = result->parent;
370 		}
371 	}
372 	if(result)
373 		return result->dp;
374 	return NULL;
375 }
376 
377 struct delegpt*
378 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
379 {
380 	uint8_t root = 0;
381 	return forwards_lookup(fwd, &root, qclass);
382 }
383 
384 int
385 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
386 {
387 	struct iter_forward_zone key;
388 	rbnode_t* n;
389 	struct iter_forward_zone* p;
390 	if(*dclass == 0) {
391 		/* first root item is first item in tree */
392 		n = rbtree_first(fwd->tree);
393 		if(n == RBTREE_NULL)
394 			return 0;
395 		p = (struct iter_forward_zone*)n;
396 		if(dname_is_root(p->name)) {
397 			*dclass = p->dclass;
398 			return 1;
399 		}
400 		/* root not first item? search for higher items */
401 		*dclass = p->dclass + 1;
402 		return forwards_next_root(fwd, dclass);
403 	}
404 	/* find class n in tree, we may get a direct hit, or if we don't
405 	 * this is the last item of the previous class so rbtree_next() takes
406 	 * us to the next root (if any) */
407 	key.node.key = &key;
408 	key.name = (uint8_t*)"\000";
409 	key.namelen = 1;
410 	key.namelabs = 0;
411 	key.dclass = *dclass;
412 	n = NULL;
413 	if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
414 		/* exact */
415 		return 1;
416 	} else {
417 		/* smaller element */
418 		if(!n || n == RBTREE_NULL)
419 			return 0; /* nothing found */
420 		n = rbtree_next(n);
421 		if(n == RBTREE_NULL)
422 			return 0; /* no higher */
423 		p = (struct iter_forward_zone*)n;
424 		if(dname_is_root(p->name)) {
425 			*dclass = p->dclass;
426 			return 1;
427 		}
428 		/* not a root node, return next higher item */
429 		*dclass = p->dclass+1;
430 		return forwards_next_root(fwd, dclass);
431 	}
432 }
433 
434 size_t
435 forwards_get_mem(struct iter_forwards* fwd)
436 {
437 	struct iter_forward_zone* p;
438 	size_t s;
439 	if(!fwd)
440 		return 0;
441 	s = sizeof(*fwd) + sizeof(*fwd->tree);
442 	RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
443 		s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
444 	}
445 	return s;
446 }
447 
448 static struct iter_forward_zone*
449 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
450 {
451 	struct iter_forward_zone key;
452 	key.node.key = &key;
453 	key.dclass = c;
454 	key.name = nm;
455 	key.namelabs = dname_count_size_labels(nm, &key.namelen);
456 	return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
457 }
458 
459 int
460 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
461 {
462 	struct iter_forward_zone *z;
463 	if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
464 		(void)rbtree_delete(fwd->tree, &z->node);
465 		fwd_zone_free(z);
466 	}
467 	if(!forwards_insert(fwd, c, dp))
468 		return 0;
469 	fwd_init_parents(fwd);
470 	return 1;
471 }
472 
473 void
474 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
475 {
476 	struct iter_forward_zone *z;
477 	if(!(z=fwd_zone_find(fwd, c, nm)))
478 		return; /* nothing to do */
479 	(void)rbtree_delete(fwd->tree, &z->node);
480 	fwd_zone_free(z);
481 	fwd_init_parents(fwd);
482 }
483 
484 int
485 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
486 {
487 	if(!fwd_add_stub_hole(fwd, c, nm)) {
488 		return 0;
489 	}
490 	fwd_init_parents(fwd);
491 	return 1;
492 }
493 
494 void
495 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
496 {
497 	struct iter_forward_zone *z;
498 	if(!(z=fwd_zone_find(fwd, c, nm)))
499 		return; /* nothing to do */
500 	if(z->dp != NULL)
501 		return; /* not a stub hole */
502 	(void)rbtree_delete(fwd->tree, &z->node);
503 	fwd_zone_free(z);
504 	fwd_init_parents(fwd);
505 }
506 
507