2 * iterator/iter_fwd.c - iterative resolver module forward zones.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
39 * This file contains functions to assist the iterator module.
40 * Keep track of forward zones and config settings.
43 #include "iterator/iter_fwd.h"
44 #include "iterator/iter_delegpt.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"
53 fwd_cmp(const void* k1, const void* k2)
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)
63 return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs,
70 struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
71 sizeof(struct iter_forwards));
77 static void fwd_zone_free(struct iter_forward_zone* n)
80 delegpt_free_mlc(n->dp);
85 static void delfwdnode(rbnode_type* n, void* ATTR_UNUSED(arg))
87 struct iter_forward_zone* node = (struct iter_forward_zone*)n;
91 static void fwd_del_tree(struct iter_forwards* fwd)
94 traverse_postorder(fwd->tree, &delfwdnode, NULL);
99 forwards_delete(struct iter_forwards* fwd)
107 /** insert info into forward structure */
109 forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
110 size_t nmlen, int nmlabs, struct delegpt* dp)
112 struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
113 sizeof(struct iter_forward_zone));
115 delegpt_free_mlc(dp);
118 node->node.key = node;
120 node->name = memdup(nm, nmlen);
122 delegpt_free_mlc(dp);
126 node->namelen = nmlen;
127 node->namelabs = nmlabs;
129 if(!rbtree_insert(fwd->tree, &node->node)) {
132 log_err("duplicate forward zone %s ignored.", buf);
133 delegpt_free_mlc(dp);
140 /** insert new info into forward structure given dp */
142 forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
144 return forwards_insert_data(fwd, c, dp->name, dp->namelen,
148 /** initialise parent pointers in the tree */
150 fwd_init_parents(struct iter_forwards* fwd)
152 struct iter_forward_zone* node, *prev = NULL, *p;
154 RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
156 if(!prev || prev->dclass != node->dclass) {
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 */
178 static struct delegpt*
179 read_fwds_name(struct config_stub* s)
185 log_err("forward zone without a name (use name \".\" to forward everything)");
188 dname = sldns_str2wire_dname(s->name, &dname_len);
190 log_err("cannot parse forward zone name %s", s->name);
193 if(!(dp=delegpt_create_mlc(dname))) {
195 log_err("out of memory");
202 /** set fwd host names */
204 read_fwds_host(struct config_stub* s, struct delegpt* dp)
206 struct config_strlist* p;
209 for(p = s->hosts; p; p = p->next) {
211 dname = sldns_str2wire_dname(p->str, &dname_len);
213 log_err("cannot parse forward %s server name: '%s'",
217 if(!delegpt_add_ns_mlc(dp, dname, 0)) {
219 log_err("out of memory");
227 /** set fwd server addresses */
229 read_fwds_addr(struct config_stub* s, struct delegpt* dp)
231 struct config_strlist* p;
232 struct sockaddr_storage addr;
235 for(p = s->addrs; p; p = p->next) {
237 if(!authextstrtoaddr(p->str, &addr, &addrlen, &tls_auth_name)) {
238 log_err("cannot parse forward %s ip address: '%s'",
242 if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0,
244 log_err("out of memory");
251 /** read forwards config */
253 read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
255 struct config_stub* s;
256 for(s = cfg->forwards; s; s = s->next) {
258 if(!(dp=read_fwds_name(s)))
260 if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
261 delegpt_free_mlc(dp);
264 /* set flag that parent side NS information is included.
265 * Asking a (higher up) server on the internet is not useful */
266 /* the flag is turned off for 'forward-first' so that the
267 * last resort will ask for parent-side NS record and thus
268 * fallback to the internet name servers on a failure */
269 dp->has_parent_side_NS = (uint8_t)!s->isfirst;
270 /* use SSL for queries to this forwarder */
271 dp->ssl_upstream = (uint8_t)s->ssl_upstream;
272 verbose(VERB_QUERY, "Forward zone server list:");
273 delegpt_log(VERB_QUERY, dp);
274 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
280 /** insert a stub hole (if necessary) for stub name */
282 fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
284 struct iter_forward_zone key;
288 key.namelabs = dname_count_size_labels(key.name, &key.namelen);
289 return forwards_insert_data(fwd, key.dclass, key.name,
290 key.namelen, key.namelabs, NULL);
293 /** make NULL entries for stubs */
295 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
297 struct config_stub* s;
300 for(s = cfg->stubs; s; s = s->next) {
301 if(!s->name) continue;
302 dname = sldns_str2wire_dname(s->name, &dname_len);
304 log_err("cannot parse stub name '%s'", s->name);
307 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
309 log_err("out of memory");
318 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
321 fwd->tree = rbtree_create(fwd_cmp);
325 /* read forward zones */
326 if(!read_forwards(fwd, cfg))
328 if(!make_stub_holes(fwd, cfg))
330 fwd_init_parents(fwd);
335 forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
337 rbnode_type* res = NULL;
338 struct iter_forward_zone key;
342 key.namelabs = dname_count_size_labels(qname, &key.namelen);
343 res = rbtree_search(fwd->tree, &key);
344 if(res) return ((struct iter_forward_zone*)res)->dp;
349 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
351 /* lookup the forward zone in the tree */
352 rbnode_type* res = NULL;
353 struct iter_forward_zone *result;
354 struct iter_forward_zone key;
358 key.namelabs = dname_count_size_labels(qname, &key.namelen);
359 if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
361 result = (struct iter_forward_zone*)res;
363 /* smaller element (or no element) */
365 result = (struct iter_forward_zone*)res;
366 if(!result || result->dclass != qclass)
368 /* count number of labels matched */
369 (void)dname_lab_cmp(result->name, result->namelabs, key.name,
371 while(result) { /* go up until qname is subdomain of stub */
372 if(result->namelabs <= m)
374 result = result->parent;
383 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
386 return forwards_lookup(fwd, &root, qclass);
390 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
392 struct iter_forward_zone key;
394 struct iter_forward_zone* p;
396 /* first root item is first item in tree */
397 n = rbtree_first(fwd->tree);
400 p = (struct iter_forward_zone*)n;
401 if(dname_is_root(p->name)) {
405 /* root not first item? search for higher items */
406 *dclass = p->dclass + 1;
407 return forwards_next_root(fwd, dclass);
409 /* find class n in tree, we may get a direct hit, or if we don't
410 * this is the last item of the previous class so rbtree_next() takes
411 * us to the next root (if any) */
413 key.name = (uint8_t*)"\000";
416 key.dclass = *dclass;
418 if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
422 /* smaller element */
423 if(!n || n == RBTREE_NULL)
424 return 0; /* nothing found */
427 return 0; /* no higher */
428 p = (struct iter_forward_zone*)n;
429 if(dname_is_root(p->name)) {
433 /* not a root node, return next higher item */
434 *dclass = p->dclass+1;
435 return forwards_next_root(fwd, dclass);
440 forwards_get_mem(struct iter_forwards* fwd)
442 struct iter_forward_zone* p;
446 s = sizeof(*fwd) + sizeof(*fwd->tree);
447 RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
448 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
453 static struct iter_forward_zone*
454 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
456 struct iter_forward_zone key;
460 key.namelabs = dname_count_size_labels(nm, &key.namelen);
461 return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
465 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
467 struct iter_forward_zone *z;
468 if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
469 (void)rbtree_delete(fwd->tree, &z->node);
472 if(!forwards_insert(fwd, c, dp))
474 fwd_init_parents(fwd);
479 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
481 struct iter_forward_zone *z;
482 if(!(z=fwd_zone_find(fwd, c, nm)))
483 return; /* nothing to do */
484 (void)rbtree_delete(fwd->tree, &z->node);
486 fwd_init_parents(fwd);
490 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
492 if(!fwd_add_stub_hole(fwd, c, nm)) {
495 fwd_init_parents(fwd);
500 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
502 struct iter_forward_zone *z;
503 if(!(z=fwd_zone_find(fwd, c, nm)))
504 return; /* nothing to do */
506 return; /* not a stub hole */
507 (void)rbtree_delete(fwd->tree, &z->node);
509 fwd_init_parents(fwd);