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
52int
53fwd_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
67struct iter_forwards*
68forwards_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	lock_rw_init(&fwd->lock);
75	return fwd;
76}
77
78static void fwd_zone_free(struct iter_forward_zone* n)
79{
80	if(!n) return;
81	delegpt_free_mlc(n->dp);
82	free(n->name);
83	free(n);
84}
85
86static void delfwdnode(rbnode_type* n, void* ATTR_UNUSED(arg))
87{
88	struct iter_forward_zone* node = (struct iter_forward_zone*)n;
89	fwd_zone_free(node);
90}
91
92static void fwd_del_tree(struct iter_forwards* fwd)
93{
94	if(fwd->tree)
95		traverse_postorder(fwd->tree, &delfwdnode, NULL);
96	free(fwd->tree);
97}
98
99void
100forwards_delete(struct iter_forwards* fwd)
101{
102	if(!fwd)
103		return;
104	lock_rw_destroy(&fwd->lock);
105	fwd_del_tree(fwd);
106	free(fwd);
107}
108
109/** insert info into forward structure */
110static int
111forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
112	size_t nmlen, int nmlabs, struct delegpt* dp)
113{
114	struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
115		sizeof(struct iter_forward_zone));
116	if(!node) {
117		delegpt_free_mlc(dp);
118		return 0;
119	}
120	node->node.key = node;
121	node->dclass = c;
122	node->name = memdup(nm, nmlen);
123	if(!node->name) {
124		delegpt_free_mlc(dp);
125		free(node);
126		return 0;
127	}
128	node->namelen = nmlen;
129	node->namelabs = nmlabs;
130	node->dp = dp;
131	if(!rbtree_insert(fwd->tree, &node->node)) {
132		char buf[257];
133		dname_str(nm, buf);
134		log_err("duplicate forward zone %s ignored.", buf);
135		delegpt_free_mlc(dp);
136		free(node->name);
137		free(node);
138	}
139	return 1;
140}
141
142/** insert new info into forward structure given dp */
143static int
144forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
145{
146	return forwards_insert_data(fwd, c, dp->name, dp->namelen,
147		dp->namelabs, dp);
148}
149
150/** initialise parent pointers in the tree */
151static void
152fwd_init_parents(struct iter_forwards* fwd)
153{
154	struct iter_forward_zone* node, *prev = NULL, *p;
155	int m;
156	RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
157		node->parent = NULL;
158		if(!prev || prev->dclass != node->dclass) {
159			prev = node;
160			continue;
161		}
162		(void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
163			node->namelabs, &m); /* we know prev is smaller */
164		/* sort order like: . com. bla.com. zwb.com. net. */
165		/* find the previous, or parent-parent-parent */
166		for(p = prev; p; p = p->parent)
167			/* looking for name with few labels, a parent */
168			if(p->namelabs <= m) {
169				/* ==: since prev matched m, this is closest*/
170				/* <: prev matches more, but is not a parent,
171				 * this one is a (grand)parent */
172				node->parent = p;
173				break;
174			}
175		prev = node;
176	}
177}
178
179/** set zone name */
180static struct delegpt*
181read_fwds_name(struct config_stub* s)
182{
183	struct delegpt* dp;
184	uint8_t* dname;
185	size_t dname_len;
186	if(!s->name) {
187		log_err("forward zone without a name (use name \".\" to forward everything)");
188		return NULL;
189	}
190	dname = sldns_str2wire_dname(s->name, &dname_len);
191	if(!dname) {
192		log_err("cannot parse forward zone name %s", s->name);
193		return NULL;
194	}
195	if(!(dp=delegpt_create_mlc(dname))) {
196		free(dname);
197		log_err("out of memory");
198		return NULL;
199	}
200	free(dname);
201	return dp;
202}
203
204/** set fwd host names */
205static int
206read_fwds_host(struct config_stub* s, struct delegpt* dp)
207{
208	struct config_strlist* p;
209	uint8_t* dname;
210	char* tls_auth_name;
211	int port;
212	for(p = s->hosts; p; p = p->next) {
213		log_assert(p->str);
214		dname = authextstrtodname(p->str, &port, &tls_auth_name);
215		if(!dname) {
216			log_err("cannot parse forward %s server name: '%s'",
217				s->name, p->str);
218			return 0;
219		}
220#if ! defined(HAVE_SSL_SET1_HOST) && ! defined(HAVE_X509_VERIFY_PARAM_SET1_HOST)
221		if(tls_auth_name)
222			log_err("no name verification functionality in "
223				"ssl library, ignored name for %s", p->str);
224#endif
225		if(!delegpt_add_ns_mlc(dp, dname, 0, tls_auth_name, port)) {
226			free(dname);
227			log_err("out of memory");
228			return 0;
229		}
230		free(dname);
231	}
232	return 1;
233}
234
235/** set fwd server addresses */
236static int
237read_fwds_addr(struct config_stub* s, struct delegpt* dp)
238{
239	struct config_strlist* p;
240	struct sockaddr_storage addr;
241	socklen_t addrlen;
242	char* tls_auth_name;
243	for(p = s->addrs; p; p = p->next) {
244		log_assert(p->str);
245		if(!authextstrtoaddr(p->str, &addr, &addrlen, &tls_auth_name)) {
246			log_err("cannot parse forward %s ip address: '%s'",
247				s->name, p->str);
248			return 0;
249		}
250#if ! defined(HAVE_SSL_SET1_HOST) && ! defined(HAVE_X509_VERIFY_PARAM_SET1_HOST)
251		if(tls_auth_name)
252			log_err("no name verification functionality in "
253				"ssl library, ignored name for %s", p->str);
254#endif
255		if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0,
256			tls_auth_name, -1)) {
257			log_err("out of memory");
258			return 0;
259		}
260	}
261	return 1;
262}
263
264/** read forwards config */
265static int
266read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
267{
268	struct config_stub* s;
269	for(s = cfg->forwards; s; s = s->next) {
270		struct delegpt* dp;
271		if(!(dp=read_fwds_name(s)))
272			return 0;
273		if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
274			delegpt_free_mlc(dp);
275			return 0;
276		}
277		/* set flag that parent side NS information is included.
278		 * Asking a (higher up) server on the internet is not useful */
279		/* the flag is turned off for 'forward-first' so that the
280		 * last resort will ask for parent-side NS record and thus
281		 * fallback to the internet name servers on a failure */
282		dp->has_parent_side_NS = (uint8_t)!s->isfirst;
283		/* Do not cache if set. */
284		dp->no_cache = s->no_cache;
285		/* use SSL for queries to this forwarder */
286		dp->ssl_upstream = (uint8_t)s->ssl_upstream;
287		/* use TCP for queries to this forwarder */
288		dp->tcp_upstream = (uint8_t)s->tcp_upstream;
289		verbose(VERB_QUERY, "Forward zone server list:");
290		delegpt_log(VERB_QUERY, dp);
291		if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
292			return 0;
293	}
294	return 1;
295}
296
297/** insert a stub hole (if necessary) for stub name */
298static int
299fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
300{
301	struct iter_forward_zone key;
302	key.node.key = &key;
303	key.dclass = c;
304	key.name = nm;
305	key.namelabs = dname_count_size_labels(key.name, &key.namelen);
306	return forwards_insert_data(fwd, key.dclass, key.name,
307		key.namelen, key.namelabs, NULL);
308}
309
310/** make NULL entries for stubs */
311static int
312make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
313{
314	struct config_stub* s;
315	uint8_t* dname;
316	size_t dname_len;
317	for(s = cfg->stubs; s; s = s->next) {
318		if(!s->name) continue;
319		dname = sldns_str2wire_dname(s->name, &dname_len);
320		if(!dname) {
321			log_err("cannot parse stub name '%s'", s->name);
322			return 0;
323		}
324		if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
325			free(dname);
326			log_err("out of memory");
327			return 0;
328		}
329		free(dname);
330	}
331	return 1;
332}
333
334int
335forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
336{
337	if(fwd->tree) {
338		lock_unprotect(&fwd->lock, fwd->tree);
339	}
340	fwd_del_tree(fwd);
341	fwd->tree = rbtree_create(fwd_cmp);
342	if(!fwd->tree)
343		return 0;
344	lock_protect(&fwd->lock, fwd->tree, sizeof(*fwd->tree));
345
346	lock_rw_wrlock(&fwd->lock);
347	/* read forward zones */
348	if(!read_forwards(fwd, cfg)) {
349		lock_rw_unlock(&fwd->lock);
350		return 0;
351	}
352	if(!make_stub_holes(fwd, cfg)) {
353		lock_rw_unlock(&fwd->lock);
354		return 0;
355	}
356	fwd_init_parents(fwd);
357	lock_rw_unlock(&fwd->lock);
358	return 1;
359}
360
361struct delegpt*
362forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass,
363	int nolock)
364{
365	struct iter_forward_zone* res;
366	struct iter_forward_zone key;
367	int has_dp;
368	key.node.key = &key;
369	key.dclass = qclass;
370	key.name = qname;
371	key.namelabs = dname_count_size_labels(qname, &key.namelen);
372	/* lock_() calls are macros that could be nothing, surround in {} */
373	if(!nolock) { lock_rw_rdlock(&fwd->lock); }
374	res = (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
375	has_dp = res && res->dp;
376	if(!has_dp && !nolock) { lock_rw_unlock(&fwd->lock); }
377	return has_dp?res->dp:NULL;
378}
379
380struct delegpt*
381forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass,
382	int nolock)
383{
384	/* lookup the forward zone in the tree */
385	rbnode_type* res = NULL;
386	struct iter_forward_zone *result;
387	struct iter_forward_zone key;
388	int has_dp;
389	key.node.key = &key;
390	key.dclass = qclass;
391	key.name = qname;
392	key.namelabs = dname_count_size_labels(qname, &key.namelen);
393	/* lock_() calls are macros that could be nothing, surround in {} */
394	if(!nolock) { lock_rw_rdlock(&fwd->lock); }
395	if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
396		/* exact */
397		result = (struct iter_forward_zone*)res;
398	} else {
399		/* smaller element (or no element) */
400		int m;
401		result = (struct iter_forward_zone*)res;
402		if(!result || result->dclass != qclass) {
403			if(!nolock) { lock_rw_unlock(&fwd->lock); }
404			return NULL;
405		}
406		/* count number of labels matched */
407		(void)dname_lab_cmp(result->name, result->namelabs, key.name,
408			key.namelabs, &m);
409		while(result) { /* go up until qname is subdomain of stub */
410			if(result->namelabs <= m)
411				break;
412			result = result->parent;
413		}
414	}
415	has_dp = result && result->dp;
416	if(!has_dp && !nolock) { lock_rw_unlock(&fwd->lock); }
417	return has_dp?result->dp:NULL;
418}
419
420struct delegpt*
421forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass, int nolock)
422{
423	uint8_t root = 0;
424	return forwards_lookup(fwd, &root, qclass, nolock);
425}
426
427/* Finds next root item in forwards lookup tree.
428 * Caller needs to handle locking of the forwards structure. */
429static int
430next_root_locked(struct iter_forwards* fwd, uint16_t* dclass)
431{
432	struct iter_forward_zone key;
433	rbnode_type* n;
434	struct iter_forward_zone* p;
435	if(*dclass == 0) {
436		/* first root item is first item in tree */
437		n = rbtree_first(fwd->tree);
438		if(n == RBTREE_NULL)
439			return 0;
440		p = (struct iter_forward_zone*)n;
441		if(dname_is_root(p->name)) {
442			*dclass = p->dclass;
443			return 1;
444		}
445		/* root not first item? search for higher items */
446		*dclass = p->dclass + 1;
447		return next_root_locked(fwd, dclass);
448	}
449	/* find class n in tree, we may get a direct hit, or if we don't
450	 * this is the last item of the previous class so rbtree_next() takes
451	 * us to the next root (if any) */
452	key.node.key = &key;
453	key.name = (uint8_t*)"\000";
454	key.namelen = 1;
455	key.namelabs = 0;
456	key.dclass = *dclass;
457	n = NULL;
458	if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
459		/* exact */
460		return 1;
461	} else {
462		/* smaller element */
463		if(!n || n == RBTREE_NULL)
464			return 0; /* nothing found */
465		n = rbtree_next(n);
466		if(n == RBTREE_NULL)
467			return 0; /* no higher */
468		p = (struct iter_forward_zone*)n;
469		if(dname_is_root(p->name)) {
470			*dclass = p->dclass;
471			return 1;
472		}
473		/* not a root node, return next higher item */
474		*dclass = p->dclass+1;
475		return next_root_locked(fwd, dclass);
476	}
477}
478
479int
480forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass, int nolock)
481{
482	int ret;
483	/* lock_() calls are macros that could be nothing, surround in {} */
484	if(!nolock) { lock_rw_rdlock(&fwd->lock); }
485	ret = next_root_locked(fwd, dclass);
486	if(!nolock) { lock_rw_unlock(&fwd->lock); }
487	return ret;
488}
489
490size_t
491forwards_get_mem(struct iter_forwards* fwd)
492{
493	struct iter_forward_zone* p;
494	size_t s;
495	if(!fwd)
496		return 0;
497	lock_rw_rdlock(&fwd->lock);
498	s = sizeof(*fwd) + sizeof(*fwd->tree);
499	RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
500		s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
501	}
502	lock_rw_unlock(&fwd->lock);
503	return s;
504}
505
506static struct iter_forward_zone*
507fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
508{
509	struct iter_forward_zone key;
510	key.node.key = &key;
511	key.dclass = c;
512	key.name = nm;
513	key.namelabs = dname_count_size_labels(nm, &key.namelen);
514	return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
515}
516
517int
518forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp,
519	int nolock)
520{
521	struct iter_forward_zone *z;
522	/* lock_() calls are macros that could be nothing, surround in {} */
523	if(!nolock) { lock_rw_wrlock(&fwd->lock); }
524	if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
525		(void)rbtree_delete(fwd->tree, &z->node);
526		fwd_zone_free(z);
527	}
528	if(!forwards_insert(fwd, c, dp)) {
529		if(!nolock) { lock_rw_unlock(&fwd->lock); }
530		return 0;
531	}
532	fwd_init_parents(fwd);
533	if(!nolock) { lock_rw_unlock(&fwd->lock); }
534	return 1;
535}
536
537void
538forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
539	int nolock)
540{
541	struct iter_forward_zone *z;
542	/* lock_() calls are macros that could be nothing, surround in {} */
543	if(!nolock) { lock_rw_wrlock(&fwd->lock); }
544	if(!(z=fwd_zone_find(fwd, c, nm))) {
545		if(!nolock) { lock_rw_unlock(&fwd->lock); }
546		return; /* nothing to do */
547	}
548	(void)rbtree_delete(fwd->tree, &z->node);
549	fwd_zone_free(z);
550	fwd_init_parents(fwd);
551	if(!nolock) { lock_rw_unlock(&fwd->lock); }
552}
553
554int
555forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
556	int nolock)
557{
558	/* lock_() calls are macros that could be nothing, surround in {} */
559	if(!nolock) { lock_rw_wrlock(&fwd->lock); }
560	if(fwd_zone_find(fwd, c, nm) != NULL) {
561		if(!nolock) { lock_rw_unlock(&fwd->lock); }
562		return 1; /* already a stub zone there */
563	}
564	if(!fwd_add_stub_hole(fwd, c, nm)) {
565		if(!nolock) { lock_rw_unlock(&fwd->lock); }
566		return 0;
567	}
568	fwd_init_parents(fwd);
569	if(!nolock) { lock_rw_unlock(&fwd->lock); }
570	return 1;
571}
572
573void
574forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c,
575	uint8_t* nm, int nolock)
576{
577	struct iter_forward_zone *z;
578	/* lock_() calls are macros that could be nothing, surround in {} */
579	if(!nolock) { lock_rw_wrlock(&fwd->lock); }
580	if(!(z=fwd_zone_find(fwd, c, nm))) {
581		if(!nolock) { lock_rw_unlock(&fwd->lock); }
582		return; /* nothing to do */
583	}
584	if(z->dp != NULL) {
585		if(!nolock) { lock_rw_unlock(&fwd->lock); }
586		return; /* not a stub hole */
587	}
588	(void)rbtree_delete(fwd->tree, &z->node);
589	fwd_zone_free(z);
590	fwd_init_parents(fwd);
591	if(!nolock) { lock_rw_unlock(&fwd->lock); }
592}
593