iter_fwd.c revision 291767
1185743Ssam/* 2185743Ssam * iterator/iter_fwd.c - iterative resolver module forward zones. 3185743Ssam * 4185743Ssam * Copyright (c) 2007, NLnet Labs. All rights reserved. 5185743Ssam * 6185743Ssam * This software is open source. 7185743Ssam * 8185743Ssam * Redistribution and use in source and binary forms, with or without 9185743Ssam * modification, are permitted provided that the following conditions 10185743Ssam * are met: 11185743Ssam * 12185743Ssam * Redistributions of source code must retain the above copyright notice, 13185743Ssam * this list of conditions and the following disclaimer. 14185743Ssam * 15185743Ssam * Redistributions in binary form must reproduce the above copyright notice, 16185743Ssam * this list of conditions and the following disclaimer in the documentation 17185743Ssam * and/or other materials provided with the distribution. 18185743Ssam * 19185743Ssam * Neither the name of the NLNET LABS nor the names of its contributors may 20185743Ssam * be used to endorse or promote products derived from this software without 21185743Ssam * specific prior written permission. 22185743Ssam * 23185743Ssam * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24185743Ssam * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25185743Ssam * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26185743Ssam * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27185743Ssam * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28185743Ssam * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29185743Ssam * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30185743Ssam * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31185743Ssam * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32185743Ssam * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33185743Ssam * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34185743Ssam */ 35185743Ssam 36185743Ssam/** 37185743Ssam * \file 38185743Ssam * 39185743Ssam * This file contains functions to assist the iterator module. 40185743Ssam * Keep track of forward zones and config settings. 41185743Ssam */ 42185743Ssam#include "config.h" 43185743Ssam#include "iterator/iter_fwd.h" 44185743Ssam#include "iterator/iter_delegpt.h" 45185743Ssam#include "util/log.h" 46185743Ssam#include "util/config_file.h" 47185743Ssam#include "util/net_help.h" 48185743Ssam#include "util/data/dname.h" 49185743Ssam#include "sldns/rrdef.h" 50185743Ssam#include "sldns/str2wire.h" 51185743Ssam 52185743Ssamint 53185743Ssamfwd_cmp(const void* k1, const void* k2) 54185743Ssam{ 55185743Ssam int m; 56185743Ssam struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1; 57185743Ssam struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2; 58185743Ssam if(n1->dclass != n2->dclass) { 59185743Ssam if(n1->dclass < n2->dclass) 60185743Ssam return -1; 61185743Ssam return 1; 62185743Ssam } 63185743Ssam return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 64185743Ssam &m); 65185743Ssam} 66185743Ssam 67185743Ssamstruct iter_forwards* 68185743Ssamforwards_create(void) 69185743Ssam{ 70185743Ssam struct iter_forwards* fwd = (struct iter_forwards*)calloc(1, 71185743Ssam sizeof(struct iter_forwards)); 72185743Ssam if(!fwd) 73185743Ssam return NULL; 74185743Ssam return fwd; 75185743Ssam} 76185743Ssam 77185743Ssamstatic void fwd_zone_free(struct iter_forward_zone* n) 78185743Ssam{ 79185743Ssam if(!n) return; 80185743Ssam delegpt_free_mlc(n->dp); 81185743Ssam free(n->name); 82185743Ssam free(n); 83185743Ssam} 84185743Ssam 85185743Ssamstatic void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg)) 86185743Ssam{ 87185743Ssam struct iter_forward_zone* node = (struct iter_forward_zone*)n; 88185743Ssam fwd_zone_free(node); 89185743Ssam} 90185743Ssam 91185743Ssamstatic void fwd_del_tree(struct iter_forwards* fwd) 92185743Ssam{ 93185743Ssam if(fwd->tree) 94185743Ssam traverse_postorder(fwd->tree, &delfwdnode, NULL); 95185743Ssam free(fwd->tree); 96185743Ssam} 97185743Ssam 98185743Ssamvoid 99185743Ssamforwards_delete(struct iter_forwards* fwd) 100185743Ssam{ 101185743Ssam if(!fwd) 102185743Ssam return; 103185743Ssam fwd_del_tree(fwd); 104185743Ssam free(fwd); 105185743Ssam} 106185743Ssam 107185743Ssam/** insert info into forward structure */ 108185743Ssamstatic int 109185743Ssamforwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 110185743Ssam size_t nmlen, int nmlabs, struct delegpt* dp) 111185743Ssam{ 112185743Ssam struct iter_forward_zone* node = (struct iter_forward_zone*)malloc( 113185743Ssam sizeof(struct iter_forward_zone)); 114185743Ssam if(!node) { 115185743Ssam delegpt_free_mlc(dp); 116185743Ssam return 0; 117185743Ssam } 118185743Ssam node->node.key = node; 119185743Ssam node->dclass = c; 120185743Ssam node->name = memdup(nm, nmlen); 121185743Ssam if(!node->name) { 122185743Ssam delegpt_free_mlc(dp); 123185743Ssam free(node); 124185743Ssam return 0; 125185743Ssam } 126185743Ssam node->namelen = nmlen; 127185743Ssam node->namelabs = nmlabs; 128185743Ssam node->dp = dp; 129185743Ssam if(!rbtree_insert(fwd->tree, &node->node)) { 130185743Ssam char buf[257]; 131185743Ssam dname_str(nm, buf); 132185743Ssam log_err("duplicate forward zone %s ignored.", buf); 133185743Ssam delegpt_free_mlc(dp); 134185743Ssam free(node->name); 135185743Ssam free(node); 136185743Ssam } 137185743Ssam return 1; 138185743Ssam} 139185743Ssam 140185743Ssam/** insert new info into forward structure given dp */ 141185743Ssamstatic int 142185743Ssamforwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 143185743Ssam{ 144185743Ssam return forwards_insert_data(fwd, c, dp->name, dp->namelen, 145185743Ssam dp->namelabs, dp); 146185743Ssam} 147185743Ssam 148185743Ssam/** initialise parent pointers in the tree */ 149185743Ssamstatic void 150185743Ssamfwd_init_parents(struct iter_forwards* fwd) 151185743Ssam{ 152185743Ssam struct iter_forward_zone* node, *prev = NULL, *p; 153185743Ssam int m; 154185743Ssam RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) { 155185743Ssam node->parent = NULL; 156185743Ssam if(!prev || prev->dclass != node->dclass) { 157185743Ssam prev = node; 158185743Ssam continue; 159185743Ssam } 160185743Ssam (void)dname_lab_cmp(prev->name, prev->namelabs, node->name, 161185743Ssam node->namelabs, &m); /* we know prev is smaller */ 162185743Ssam /* sort order like: . com. bla.com. zwb.com. net. */ 163185743Ssam /* find the previous, or parent-parent-parent */ 164185743Ssam for(p = prev; p; p = p->parent) 165185743Ssam /* 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 */ 178static struct delegpt* 179read_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 */ 203static int 204read_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 */ 228static int 229read_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 for(p = s->addrs; p; p = p->next) { 235 log_assert(p->str); 236 if(!extstrtoaddr(p->str, &addr, &addrlen)) { 237 log_err("cannot parse forward %s ip address: '%s'", 238 s->name, p->str); 239 return 0; 240 } 241 if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) { 242 log_err("out of memory"); 243 return 0; 244 } 245 } 246 return 1; 247} 248 249/** read forwards config */ 250static int 251read_forwards(struct iter_forwards* fwd, struct config_file* cfg) 252{ 253 struct config_stub* s; 254 for(s = cfg->forwards; s; s = s->next) { 255 struct delegpt* dp; 256 if(!(dp=read_fwds_name(s))) 257 return 0; 258 if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) { 259 delegpt_free_mlc(dp); 260 return 0; 261 } 262 /* set flag that parent side NS information is included. 263 * Asking a (higher up) server on the internet is not useful */ 264 /* the flag is turned off for 'forward-first' so that the 265 * last resort will ask for parent-side NS record and thus 266 * fallback to the internet name servers on a failure */ 267 dp->has_parent_side_NS = (uint8_t)!s->isfirst; 268 verbose(VERB_QUERY, "Forward zone server list:"); 269 delegpt_log(VERB_QUERY, dp); 270 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 271 return 0; 272 } 273 return 1; 274} 275 276/** insert a stub hole (if necessary) for stub name */ 277static int 278fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 279{ 280 struct iter_forward_zone key; 281 key.node.key = &key; 282 key.dclass = c; 283 key.name = nm; 284 key.namelabs = dname_count_size_labels(key.name, &key.namelen); 285 return forwards_insert_data(fwd, key.dclass, key.name, 286 key.namelen, key.namelabs, NULL); 287} 288 289/** make NULL entries for stubs */ 290static int 291make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 292{ 293 struct config_stub* s; 294 uint8_t* dname; 295 size_t dname_len; 296 for(s = cfg->stubs; s; s = s->next) { 297 dname = sldns_str2wire_dname(s->name, &dname_len); 298 if(!dname) { 299 log_err("cannot parse stub name '%s'", s->name); 300 return 0; 301 } 302 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) { 303 free(dname); 304 log_err("out of memory"); 305 return 0; 306 } 307 free(dname); 308 } 309 return 1; 310} 311 312int 313forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 314{ 315 fwd_del_tree(fwd); 316 fwd->tree = rbtree_create(fwd_cmp); 317 if(!fwd->tree) 318 return 0; 319 320 /* read forward zones */ 321 if(!read_forwards(fwd, cfg)) 322 return 0; 323 if(!make_stub_holes(fwd, cfg)) 324 return 0; 325 fwd_init_parents(fwd); 326 return 1; 327} 328 329struct delegpt* 330forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 331{ 332 rbnode_t* res = NULL; 333 struct iter_forward_zone key; 334 key.node.key = &key; 335 key.dclass = qclass; 336 key.name = qname; 337 key.namelabs = dname_count_size_labels(qname, &key.namelen); 338 res = rbtree_search(fwd->tree, &key); 339 if(res) return ((struct iter_forward_zone*)res)->dp; 340 return NULL; 341} 342 343struct delegpt* 344forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 345{ 346 /* lookup the forward zone in the tree */ 347 rbnode_t* res = NULL; 348 struct iter_forward_zone *result; 349 struct iter_forward_zone key; 350 key.node.key = &key; 351 key.dclass = qclass; 352 key.name = qname; 353 key.namelabs = dname_count_size_labels(qname, &key.namelen); 354 if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 355 /* exact */ 356 result = (struct iter_forward_zone*)res; 357 } else { 358 /* smaller element (or no element) */ 359 int m; 360 result = (struct iter_forward_zone*)res; 361 if(!result || result->dclass != qclass) 362 return NULL; 363 /* count number of labels matched */ 364 (void)dname_lab_cmp(result->name, result->namelabs, key.name, 365 key.namelabs, &m); 366 while(result) { /* go up until qname is subdomain of stub */ 367 if(result->namelabs <= m) 368 break; 369 result = result->parent; 370 } 371 } 372 if(result) 373 return result->dp; 374 return NULL; 375} 376 377struct delegpt* 378forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 379{ 380 uint8_t root = 0; 381 return forwards_lookup(fwd, &root, qclass); 382} 383 384int 385forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 386{ 387 struct iter_forward_zone key; 388 rbnode_t* n; 389 struct iter_forward_zone* p; 390 if(*dclass == 0) { 391 /* first root item is first item in tree */ 392 n = rbtree_first(fwd->tree); 393 if(n == RBTREE_NULL) 394 return 0; 395 p = (struct iter_forward_zone*)n; 396 if(dname_is_root(p->name)) { 397 *dclass = p->dclass; 398 return 1; 399 } 400 /* root not first item? search for higher items */ 401 *dclass = p->dclass + 1; 402 return forwards_next_root(fwd, dclass); 403 } 404 /* find class n in tree, we may get a direct hit, or if we don't 405 * this is the last item of the previous class so rbtree_next() takes 406 * us to the next root (if any) */ 407 key.node.key = &key; 408 key.name = (uint8_t*)"\000"; 409 key.namelen = 1; 410 key.namelabs = 0; 411 key.dclass = *dclass; 412 n = NULL; 413 if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 414 /* exact */ 415 return 1; 416 } else { 417 /* smaller element */ 418 if(!n || n == RBTREE_NULL) 419 return 0; /* nothing found */ 420 n = rbtree_next(n); 421 if(n == RBTREE_NULL) 422 return 0; /* no higher */ 423 p = (struct iter_forward_zone*)n; 424 if(dname_is_root(p->name)) { 425 *dclass = p->dclass; 426 return 1; 427 } 428 /* not a root node, return next higher item */ 429 *dclass = p->dclass+1; 430 return forwards_next_root(fwd, dclass); 431 } 432} 433 434size_t 435forwards_get_mem(struct iter_forwards* fwd) 436{ 437 struct iter_forward_zone* p; 438 size_t s; 439 if(!fwd) 440 return 0; 441 s = sizeof(*fwd) + sizeof(*fwd->tree); 442 RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) { 443 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp); 444 } 445 return s; 446} 447 448static struct iter_forward_zone* 449fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 450{ 451 struct iter_forward_zone key; 452 key.node.key = &key; 453 key.dclass = c; 454 key.name = nm; 455 key.namelabs = dname_count_size_labels(nm, &key.namelen); 456 return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key); 457} 458 459int 460forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 461{ 462 struct iter_forward_zone *z; 463 if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) { 464 (void)rbtree_delete(fwd->tree, &z->node); 465 fwd_zone_free(z); 466 } 467 if(!forwards_insert(fwd, c, dp)) 468 return 0; 469 fwd_init_parents(fwd); 470 return 1; 471} 472 473void 474forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 475{ 476 struct iter_forward_zone *z; 477 if(!(z=fwd_zone_find(fwd, c, nm))) 478 return; /* nothing to do */ 479 (void)rbtree_delete(fwd->tree, &z->node); 480 fwd_zone_free(z); 481 fwd_init_parents(fwd); 482} 483 484int 485forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 486{ 487 if(!fwd_add_stub_hole(fwd, c, nm)) { 488 return 0; 489 } 490 fwd_init_parents(fwd); 491 return 1; 492} 493 494void 495forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 496{ 497 struct iter_forward_zone *z; 498 if(!(z=fwd_zone_find(fwd, c, nm))) 499 return; /* nothing to do */ 500 if(z->dp != NULL) 501 return; /* not a stub hole */ 502 (void)rbtree_delete(fwd->tree, &z->node); 503 fwd_zone_free(z); 504 fwd_init_parents(fwd); 505} 506 507