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_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 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 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 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 verbose(VERB_QUERY, "Forward zone server list:"); 280 delegpt_log(VERB_QUERY, dp); 281 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 282 return 0; 283 } 284 return 1; 285 } 286 287 /** insert a stub hole (if necessary) for stub name */ 288 static int 289 fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 290 { 291 struct iter_forward_zone key; 292 key.node.key = &key; 293 key.dclass = c; 294 key.name = nm; 295 key.namelabs = dname_count_size_labels(key.name, &key.namelen); 296 return forwards_insert_data(fwd, key.dclass, key.name, 297 key.namelen, key.namelabs, NULL); 298 } 299 300 /** make NULL entries for stubs */ 301 static int 302 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 303 { 304 struct config_stub* s; 305 uint8_t* dname; 306 size_t dname_len; 307 for(s = cfg->stubs; s; s = s->next) { 308 if(!s->name) continue; 309 dname = sldns_str2wire_dname(s->name, &dname_len); 310 if(!dname) { 311 log_err("cannot parse stub name '%s'", s->name); 312 return 0; 313 } 314 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) { 315 free(dname); 316 log_err("out of memory"); 317 return 0; 318 } 319 free(dname); 320 } 321 return 1; 322 } 323 324 int 325 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 326 { 327 fwd_del_tree(fwd); 328 fwd->tree = rbtree_create(fwd_cmp); 329 if(!fwd->tree) 330 return 0; 331 332 /* read forward zones */ 333 if(!read_forwards(fwd, cfg)) 334 return 0; 335 if(!make_stub_holes(fwd, cfg)) 336 return 0; 337 fwd_init_parents(fwd); 338 return 1; 339 } 340 341 struct delegpt* 342 forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 343 { 344 rbnode_type* res = NULL; 345 struct iter_forward_zone key; 346 key.node.key = &key; 347 key.dclass = qclass; 348 key.name = qname; 349 key.namelabs = dname_count_size_labels(qname, &key.namelen); 350 res = rbtree_search(fwd->tree, &key); 351 if(res) return ((struct iter_forward_zone*)res)->dp; 352 return NULL; 353 } 354 355 struct delegpt* 356 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 357 { 358 /* lookup the forward zone in the tree */ 359 rbnode_type* res = NULL; 360 struct iter_forward_zone *result; 361 struct iter_forward_zone key; 362 key.node.key = &key; 363 key.dclass = qclass; 364 key.name = qname; 365 key.namelabs = dname_count_size_labels(qname, &key.namelen); 366 if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 367 /* exact */ 368 result = (struct iter_forward_zone*)res; 369 } else { 370 /* smaller element (or no element) */ 371 int m; 372 result = (struct iter_forward_zone*)res; 373 if(!result || result->dclass != qclass) 374 return NULL; 375 /* count number of labels matched */ 376 (void)dname_lab_cmp(result->name, result->namelabs, key.name, 377 key.namelabs, &m); 378 while(result) { /* go up until qname is subdomain of stub */ 379 if(result->namelabs <= m) 380 break; 381 result = result->parent; 382 } 383 } 384 if(result) 385 return result->dp; 386 return NULL; 387 } 388 389 struct delegpt* 390 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 391 { 392 uint8_t root = 0; 393 return forwards_lookup(fwd, &root, qclass); 394 } 395 396 int 397 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 398 { 399 struct iter_forward_zone key; 400 rbnode_type* n; 401 struct iter_forward_zone* p; 402 if(*dclass == 0) { 403 /* first root item is first item in tree */ 404 n = rbtree_first(fwd->tree); 405 if(n == RBTREE_NULL) 406 return 0; 407 p = (struct iter_forward_zone*)n; 408 if(dname_is_root(p->name)) { 409 *dclass = p->dclass; 410 return 1; 411 } 412 /* root not first item? search for higher items */ 413 *dclass = p->dclass + 1; 414 return forwards_next_root(fwd, dclass); 415 } 416 /* find class n in tree, we may get a direct hit, or if we don't 417 * this is the last item of the previous class so rbtree_next() takes 418 * us to the next root (if any) */ 419 key.node.key = &key; 420 key.name = (uint8_t*)"\000"; 421 key.namelen = 1; 422 key.namelabs = 0; 423 key.dclass = *dclass; 424 n = NULL; 425 if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 426 /* exact */ 427 return 1; 428 } else { 429 /* smaller element */ 430 if(!n || n == RBTREE_NULL) 431 return 0; /* nothing found */ 432 n = rbtree_next(n); 433 if(n == RBTREE_NULL) 434 return 0; /* no higher */ 435 p = (struct iter_forward_zone*)n; 436 if(dname_is_root(p->name)) { 437 *dclass = p->dclass; 438 return 1; 439 } 440 /* not a root node, return next higher item */ 441 *dclass = p->dclass+1; 442 return forwards_next_root(fwd, dclass); 443 } 444 } 445 446 size_t 447 forwards_get_mem(struct iter_forwards* fwd) 448 { 449 struct iter_forward_zone* p; 450 size_t s; 451 if(!fwd) 452 return 0; 453 s = sizeof(*fwd) + sizeof(*fwd->tree); 454 RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) { 455 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp); 456 } 457 return s; 458 } 459 460 static struct iter_forward_zone* 461 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 462 { 463 struct iter_forward_zone key; 464 key.node.key = &key; 465 key.dclass = c; 466 key.name = nm; 467 key.namelabs = dname_count_size_labels(nm, &key.namelen); 468 return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key); 469 } 470 471 int 472 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 473 { 474 struct iter_forward_zone *z; 475 if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) { 476 (void)rbtree_delete(fwd->tree, &z->node); 477 fwd_zone_free(z); 478 } 479 if(!forwards_insert(fwd, c, dp)) 480 return 0; 481 fwd_init_parents(fwd); 482 return 1; 483 } 484 485 void 486 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 487 { 488 struct iter_forward_zone *z; 489 if(!(z=fwd_zone_find(fwd, c, nm))) 490 return; /* nothing to do */ 491 (void)rbtree_delete(fwd->tree, &z->node); 492 fwd_zone_free(z); 493 fwd_init_parents(fwd); 494 } 495 496 int 497 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 498 { 499 if(!fwd_add_stub_hole(fwd, c, nm)) { 500 return 0; 501 } 502 fwd_init_parents(fwd); 503 return 1; 504 } 505 506 void 507 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 508 { 509 struct iter_forward_zone *z; 510 if(!(z=fwd_zone_find(fwd, c, nm))) 511 return; /* nothing to do */ 512 if(z->dp != NULL) 513 return; /* not a stub hole */ 514 (void)rbtree_delete(fwd->tree, &z->node); 515 fwd_zone_free(z); 516 fwd_init_parents(fwd); 517 } 518 519