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
fwd_cmp(const void * k1,const void * k2)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*
forwards_create(void)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
fwd_zone_free(struct iter_forward_zone * n)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
delfwdnode(rbnode_type * n,void * ATTR_UNUSED (arg))85 static void delfwdnode(rbnode_type* n, void* ATTR_UNUSED(arg))
86 {
87 struct iter_forward_zone* node = (struct iter_forward_zone*)n;
88 fwd_zone_free(node);
89 }
90
fwd_del_tree(struct iter_forwards * fwd)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
forwards_delete(struct iter_forwards * fwd)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
forwards_insert_data(struct iter_forwards * fwd,uint16_t c,uint8_t * nm,size_t nmlen,int nmlabs,struct delegpt * dp)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
forwards_insert(struct iter_forwards * fwd,uint16_t c,struct delegpt * dp)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
fwd_init_parents(struct iter_forwards * fwd)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*
read_fwds_name(struct config_stub * s)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
read_fwds_host(struct config_stub * s,struct delegpt * dp)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
read_fwds_addr(struct config_stub * s,struct delegpt * dp)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 char* tls_auth_name;
235 for(p = s->addrs; p; p = p->next) {
236 log_assert(p->str);
237 if(!authextstrtoaddr(p->str, &addr, &addrlen, &tls_auth_name)) {
238 log_err("cannot parse forward %s ip address: '%s'",
239 s->name, p->str);
240 return 0;
241 }
242 #if ! defined(HAVE_SSL_SET1_HOST) && ! defined(HAVE_X509_VERIFY_PARAM_SET1_HOST)
243 if(tls_auth_name)
244 log_err("no name verification functionality in "
245 "ssl library, ignored name for %s", p->str);
246 #endif
247 if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0,
248 tls_auth_name)) {
249 log_err("out of memory");
250 return 0;
251 }
252 }
253 return 1;
254 }
255
256 /** read forwards config */
257 static int
read_forwards(struct iter_forwards * fwd,struct config_file * cfg)258 read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
259 {
260 struct config_stub* s;
261 for(s = cfg->forwards; s; s = s->next) {
262 struct delegpt* dp;
263 if(!(dp=read_fwds_name(s)))
264 return 0;
265 if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
266 delegpt_free_mlc(dp);
267 return 0;
268 }
269 /* set flag that parent side NS information is included.
270 * Asking a (higher up) server on the internet is not useful */
271 /* the flag is turned off for 'forward-first' so that the
272 * last resort will ask for parent-side NS record and thus
273 * fallback to the internet name servers on a failure */
274 dp->has_parent_side_NS = (uint8_t)!s->isfirst;
275 /* Do not cache if set. */
276 dp->no_cache = s->no_cache;
277 /* use SSL for queries to this forwarder */
278 dp->ssl_upstream = (uint8_t)s->ssl_upstream;
279 /* use TCP for queries to this forwarder */
280 dp->tcp_upstream = (uint8_t)s->tcp_upstream;
281 verbose(VERB_QUERY, "Forward zone server list:");
282 delegpt_log(VERB_QUERY, dp);
283 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
284 return 0;
285 }
286 return 1;
287 }
288
289 /** insert a stub hole (if necessary) for stub name */
290 static int
fwd_add_stub_hole(struct iter_forwards * fwd,uint16_t c,uint8_t * nm)291 fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
292 {
293 struct iter_forward_zone key;
294 key.node.key = &key;
295 key.dclass = c;
296 key.name = nm;
297 key.namelabs = dname_count_size_labels(key.name, &key.namelen);
298 return forwards_insert_data(fwd, key.dclass, key.name,
299 key.namelen, key.namelabs, NULL);
300 }
301
302 /** make NULL entries for stubs */
303 static int
make_stub_holes(struct iter_forwards * fwd,struct config_file * cfg)304 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
305 {
306 struct config_stub* s;
307 uint8_t* dname;
308 size_t dname_len;
309 for(s = cfg->stubs; s; s = s->next) {
310 if(!s->name) continue;
311 dname = sldns_str2wire_dname(s->name, &dname_len);
312 if(!dname) {
313 log_err("cannot parse stub name '%s'", s->name);
314 return 0;
315 }
316 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
317 free(dname);
318 log_err("out of memory");
319 return 0;
320 }
321 free(dname);
322 }
323 return 1;
324 }
325
326 int
forwards_apply_cfg(struct iter_forwards * fwd,struct config_file * cfg)327 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
328 {
329 fwd_del_tree(fwd);
330 fwd->tree = rbtree_create(fwd_cmp);
331 if(!fwd->tree)
332 return 0;
333
334 /* read forward zones */
335 if(!read_forwards(fwd, cfg))
336 return 0;
337 if(!make_stub_holes(fwd, cfg))
338 return 0;
339 fwd_init_parents(fwd);
340 return 1;
341 }
342
343 struct delegpt*
forwards_find(struct iter_forwards * fwd,uint8_t * qname,uint16_t qclass)344 forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
345 {
346 rbnode_type* res = NULL;
347 struct iter_forward_zone key;
348 key.node.key = &key;
349 key.dclass = qclass;
350 key.name = qname;
351 key.namelabs = dname_count_size_labels(qname, &key.namelen);
352 res = rbtree_search(fwd->tree, &key);
353 if(res) return ((struct iter_forward_zone*)res)->dp;
354 return NULL;
355 }
356
357 struct delegpt*
forwards_lookup(struct iter_forwards * fwd,uint8_t * qname,uint16_t qclass)358 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
359 {
360 /* lookup the forward zone in the tree */
361 rbnode_type* res = NULL;
362 struct iter_forward_zone *result;
363 struct iter_forward_zone key;
364 key.node.key = &key;
365 key.dclass = qclass;
366 key.name = qname;
367 key.namelabs = dname_count_size_labels(qname, &key.namelen);
368 if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
369 /* exact */
370 result = (struct iter_forward_zone*)res;
371 } else {
372 /* smaller element (or no element) */
373 int m;
374 result = (struct iter_forward_zone*)res;
375 if(!result || result->dclass != qclass)
376 return NULL;
377 /* count number of labels matched */
378 (void)dname_lab_cmp(result->name, result->namelabs, key.name,
379 key.namelabs, &m);
380 while(result) { /* go up until qname is subdomain of stub */
381 if(result->namelabs <= m)
382 break;
383 result = result->parent;
384 }
385 }
386 if(result)
387 return result->dp;
388 return NULL;
389 }
390
391 struct delegpt*
forwards_lookup_root(struct iter_forwards * fwd,uint16_t qclass)392 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
393 {
394 uint8_t root = 0;
395 return forwards_lookup(fwd, &root, qclass);
396 }
397
398 int
forwards_next_root(struct iter_forwards * fwd,uint16_t * dclass)399 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
400 {
401 struct iter_forward_zone key;
402 rbnode_type* n;
403 struct iter_forward_zone* p;
404 if(*dclass == 0) {
405 /* first root item is first item in tree */
406 n = rbtree_first(fwd->tree);
407 if(n == RBTREE_NULL)
408 return 0;
409 p = (struct iter_forward_zone*)n;
410 if(dname_is_root(p->name)) {
411 *dclass = p->dclass;
412 return 1;
413 }
414 /* root not first item? search for higher items */
415 *dclass = p->dclass + 1;
416 return forwards_next_root(fwd, dclass);
417 }
418 /* find class n in tree, we may get a direct hit, or if we don't
419 * this is the last item of the previous class so rbtree_next() takes
420 * us to the next root (if any) */
421 key.node.key = &key;
422 key.name = (uint8_t*)"\000";
423 key.namelen = 1;
424 key.namelabs = 0;
425 key.dclass = *dclass;
426 n = NULL;
427 if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
428 /* exact */
429 return 1;
430 } else {
431 /* smaller element */
432 if(!n || n == RBTREE_NULL)
433 return 0; /* nothing found */
434 n = rbtree_next(n);
435 if(n == RBTREE_NULL)
436 return 0; /* no higher */
437 p = (struct iter_forward_zone*)n;
438 if(dname_is_root(p->name)) {
439 *dclass = p->dclass;
440 return 1;
441 }
442 /* not a root node, return next higher item */
443 *dclass = p->dclass+1;
444 return forwards_next_root(fwd, dclass);
445 }
446 }
447
448 size_t
forwards_get_mem(struct iter_forwards * fwd)449 forwards_get_mem(struct iter_forwards* fwd)
450 {
451 struct iter_forward_zone* p;
452 size_t s;
453 if(!fwd)
454 return 0;
455 s = sizeof(*fwd) + sizeof(*fwd->tree);
456 RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
457 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
458 }
459 return s;
460 }
461
462 static struct iter_forward_zone*
fwd_zone_find(struct iter_forwards * fwd,uint16_t c,uint8_t * nm)463 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
464 {
465 struct iter_forward_zone key;
466 key.node.key = &key;
467 key.dclass = c;
468 key.name = nm;
469 key.namelabs = dname_count_size_labels(nm, &key.namelen);
470 return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
471 }
472
473 int
forwards_add_zone(struct iter_forwards * fwd,uint16_t c,struct delegpt * dp)474 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
475 {
476 struct iter_forward_zone *z;
477 if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
478 (void)rbtree_delete(fwd->tree, &z->node);
479 fwd_zone_free(z);
480 }
481 if(!forwards_insert(fwd, c, dp))
482 return 0;
483 fwd_init_parents(fwd);
484 return 1;
485 }
486
487 void
forwards_delete_zone(struct iter_forwards * fwd,uint16_t c,uint8_t * nm)488 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
489 {
490 struct iter_forward_zone *z;
491 if(!(z=fwd_zone_find(fwd, c, nm)))
492 return; /* nothing to do */
493 (void)rbtree_delete(fwd->tree, &z->node);
494 fwd_zone_free(z);
495 fwd_init_parents(fwd);
496 }
497
498 int
forwards_add_stub_hole(struct iter_forwards * fwd,uint16_t c,uint8_t * nm)499 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
500 {
501 if(!fwd_add_stub_hole(fwd, c, nm)) {
502 return 0;
503 }
504 fwd_init_parents(fwd);
505 return 1;
506 }
507
508 void
forwards_delete_stub_hole(struct iter_forwards * fwd,uint16_t c,uint8_t * nm)509 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
510 {
511 struct iter_forward_zone *z;
512 if(!(z=fwd_zone_find(fwd, c, nm)))
513 return; /* nothing to do */
514 if(z->dp != NULL)
515 return; /* not a stub hole */
516 (void)rbtree_delete(fwd->tree, &z->node);
517 fwd_zone_free(z);
518 fwd_init_parents(fwd);
519 }
520
521