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