iter_fwd.c revision 269257
1368708Smm/* 2368708Smm * iterator/iter_fwd.c - iterative resolver module forward zones. 3368708Smm * 4368708Smm * Copyright (c) 2007, NLnet Labs. All rights reserved. 5362134Smm * 6362134Smm * This software is open source. 7362134Smm * 8362134Smm * Redistribution and use in source and binary forms, with or without 9362134Smm * modification, are permitted provided that the following conditions 10362134Smm * are met: 11358090Smm * 12358090Smm * Redistributions of source code must retain the above copyright notice, 13358090Smm * this list of conditions and the following disclaimer. 14358090Smm * 15358090Smm * Redistributions in binary form must reproduce the above copyright notice, 16358090Smm * this list of conditions and the following disclaimer in the documentation 17358090Smm * and/or other materials provided with the distribution. 18358090Smm * 19358090Smm * Neither the name of the NLNET LABS nor the names of its contributors may 20358090Smm * be used to endorse or promote products derived from this software without 21358090Smm * specific prior written permission. 22358090Smm * 23358090Smm * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24358090Smm * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25349525Smm * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26349525Smm * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27349525Smm * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28349525Smm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29348608Smm * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30348608Smm * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31348608Smm * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32348608Smm * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33348608Smm * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34348608Smm */ 35348608Smm 36348608Smm/** 37349525Smm * \file 38348608Smm * 39342361Smm * This file contains functions to assist the iterator module. 40342361Smm * Keep track of forward zones and config settings. 41338796Smm */ 42338796Smm#include "config.h" 43338796Smm#include "iterator/iter_fwd.h" 44338796Smm#include "iterator/iter_delegpt.h" 45338796Smm#include "util/log.h" 46338796Smm#include "util/config_file.h" 47338796Smm#include "util/net_help.h" 48338796Smm#include "util/data/dname.h" 49338796Smm#include "ldns/rrdef.h" 50338796Smm#include "ldns/str2wire.h" 51321304Smm 52321304Smmint 53316338Smmfwd_cmp(const void* k1, const void* k2) 54316338Smm{ 55315433Smm int m; 56315433Smm struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1; 57315433Smm struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2; 58315433Smm if(n1->dclass != n2->dclass) { 59315433Smm if(n1->dclass < n2->dclass) 60315433Smm return -1; 61313571Smm return 1; 62313571Smm } 63313571Smm return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 64313571Smm &m); 65313571Smm} 66313571Smm 67313571Smmstruct iter_forwards* 68315433Smmforwards_create(void) 69315433Smm{ 70311042Smm struct iter_forwards* fwd = (struct iter_forwards*)calloc(1, 71311042Smm sizeof(struct iter_forwards)); 72308152Smm if(!fwd) 73308152Smm return NULL; 74308152Smm return fwd; 75302295Smm} 76302295Smm 77302295Smmstatic void fwd_zone_free(struct iter_forward_zone* n) 78302295Smm{ 79302295Smm if(!n) return; 80302001Smm delegpt_free_mlc(n->dp); 81302001Smm free(n->name); 82302001Smm free(n); 83302001Smm} 84302001Smm 85302001Smmstatic void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg)) 86302001Smm{ 87302001Smm struct iter_forward_zone* node = (struct iter_forward_zone*)n; 88302001Smm fwd_zone_free(node); 89302001Smm} 90302001Smm 91302001Smmstatic void fwd_del_tree(struct iter_forwards* fwd) 92302001Smm{ 93302001Smm if(fwd->tree) 94302001Smm traverse_postorder(fwd->tree, &delfwdnode, NULL); 95302001Smm free(fwd->tree); 96302001Smm} 97302001Smm 98302001Smmvoid 99302001Smmforwards_delete(struct iter_forwards* fwd) 100302001Smm{ 101302001Smm if(!fwd) 102302001Smm return; 103302001Smm fwd_del_tree(fwd); 104302001Smm free(fwd); 105302001Smm} 106302001Smm 107302001Smm/** insert info into forward structure */ 108302001Smmstatic int 109302001Smmforwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 110302001Smm size_t nmlen, int nmlabs, struct delegpt* dp) 111302001Smm{ 112248616Smm struct iter_forward_zone* node = (struct iter_forward_zone*)malloc( 113248616Smm sizeof(struct iter_forward_zone)); 114248616Smm if(!node) { 115248616Smm delegpt_free_mlc(dp); 116248616Smm return 0; 117248616Smm } 118248616Smm node->node.key = node; 119248616Smm node->dclass = c; 120248616Smm node->name = memdup(nm, nmlen); 121248616Smm if(!node->name) { 122248616Smm delegpt_free_mlc(dp); 123248616Smm free(node); 124248616Smm return 0; 125248616Smm } 126248616Smm node->namelen = nmlen; 127248616Smm node->namelabs = nmlabs; 128248616Smm node->dp = dp; 129248616Smm if(!rbtree_insert(fwd->tree, &node->node)) { 130248616Smm char buf[257]; 131248616Smm dname_str(nm, buf); 132248616Smm log_err("duplicate forward zone %s ignored.", buf); 133248616Smm delegpt_free_mlc(dp); 134248616Smm free(node->name); 135248616Smm free(node); 136248616Smm } 137248616Smm return 1; 138248616Smm} 139238856Smm 140228753Smm/** insert new info into forward structure given dp */ 141238856Smmstatic int 142238856Smmforwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 143238856Smm{ 144238856Smm return forwards_insert_data(fwd, c, dp->name, dp->namelen, 145238856Smm dp->namelabs, dp); 146238856Smm} 147232153Smm 148232153Smm/** initialise parent pointers in the tree */ 149232153Smmstatic void 150232153Smmfwd_init_parents(struct iter_forwards* fwd) 151228753Smm{ 152232153Smm struct iter_forward_zone* node, *prev = NULL, *p; 153232153Smm int m; 154232153Smm RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) { 155232153Smm node->parent = NULL; 156232153Smm if(!prev || prev->dclass != node->dclass) { 157232153Smm prev = node; 158232153Smm continue; 159232153Smm } 160232153Smm (void)dname_lab_cmp(prev->name, prev->namelabs, node->name, 161232153Smm node->namelabs, &m); /* we know prev is smaller */ 162232153Smm /* sort order like: . com. bla.com. zwb.com. net. */ 163232153Smm /* find the previous, or parent-parent-parent */ 164232153Smm for(p = prev; p; p = p->parent) 165232153Smm /* looking for name with few labels, a parent */ 166232153Smm if(p->namelabs <= m) { 167232153Smm /* ==: since prev matched m, this is closest*/ 168232153Smm /* <: prev matches more, but is not a parent, 169232153Smm * this one is a (grand)parent */ 170232153Smm node->parent = p; 171232153Smm break; 172232153Smm } 173232153Smm prev = node; 174232153Smm } 175232153Smm} 176232153Smm 177232153Smm/** set zone name */ 178232153Smmstatic struct delegpt* 179232153Smmread_fwds_name(struct config_stub* s) 180232153Smm{ 181232153Smm struct delegpt* dp; 182232153Smm uint8_t* dname; 183232153Smm size_t dname_len; 184232153Smm if(!s->name) { 185232153Smm log_err("forward zone without a name (use name \".\" to forward everything)"); 186232153Smm return NULL; 187232153Smm } 188232153Smm dname = sldns_str2wire_dname(s->name, &dname_len); 189232153Smm if(!dname) { 190232153Smm log_err("cannot parse forward zone name %s", s->name); 191232153Smm return NULL; 192232153Smm } 193232153Smm if(!(dp=delegpt_create_mlc(dname))) { 194232153Smm free(dname); 195232153Smm log_err("out of memory"); 196232153Smm return NULL; 197228753Smm } 198228753Smm free(dname); 199232153Smm return dp; 200232153Smm} 201232153Smm 202232153Smm/** set fwd host names */ 203232153Smmstatic int 204232153Smmread_fwds_host(struct config_stub* s, struct delegpt* dp) 205232153Smm{ 206232153Smm struct config_strlist* p; 207232153Smm uint8_t* dname; 208232153Smm size_t dname_len; 209232153Smm for(p = s->hosts; p; p = p->next) { 210232153Smm log_assert(p->str); 211232153Smm dname = sldns_str2wire_dname(p->str, &dname_len); 212228753Smm if(!dname) { 213228753Smm log_err("cannot parse forward %s server name: '%s'", 214228753Smm s->name, p->str); 215228753Smm return 0; 216228753Smm } 217228753Smm if(!delegpt_add_ns_mlc(dp, dname, 0)) { 218228753Smm free(dname); 219228753Smm log_err("out of memory"); 220228753Smm return 0; 221228753Smm } 222228753Smm free(dname); 223228753Smm } 224228753Smm return 1; 225228753Smm} 226228753Smm 227228753Smm/** set fwd server addresses */ 228228753Smmstatic int 229228753Smmread_fwds_addr(struct config_stub* s, struct delegpt* dp) 230228753Smm{ 231228753Smm struct config_strlist* p; 232228753Smm struct sockaddr_storage addr; 233228753Smm socklen_t addrlen; 234228753Smm for(p = s->addrs; p; p = p->next) { 235228753Smm log_assert(p->str); 236228753Smm if(!extstrtoaddr(p->str, &addr, &addrlen)) { 237228753Smm log_err("cannot parse forward %s ip address: '%s'", 238228753Smm s->name, p->str); 239228753Smm return 0; 240228753Smm } 241228753Smm if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) { 242228753Smm log_err("out of memory"); 243228753Smm return 0; 244228753Smm } 245228753Smm } 246228753Smm return 1; 247228753Smm} 248228753Smm 249228753Smm/** read forwards config */ 250228753Smmstatic int 251228753Smmread_forwards(struct iter_forwards* fwd, struct config_file* cfg) 252228753Smm{ 253228753Smm struct config_stub* s; 254228753Smm for(s = cfg->forwards; s; s = s->next) { 255228753Smm struct delegpt* dp; 256228753Smm if(!(dp=read_fwds_name(s))) 257228753Smm return 0; 258228753Smm if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) { 259228753Smm delegpt_free_mlc(dp); 260228753Smm return 0; 261228753Smm } 262228753Smm /* set flag that parent side NS information is included. 263228753Smm * Asking a (higher up) server on the internet is not useful */ 264228753Smm /* the flag is turned off for 'forward-first' so that the 265228753Smm * last resort will ask for parent-side NS record and thus 266228753Smm * fallback to the internet name servers on a failure */ 267228753Smm dp->has_parent_side_NS = (uint8_t)!s->isfirst; 268228753Smm verbose(VERB_QUERY, "Forward zone server list:"); 269228753Smm delegpt_log(VERB_QUERY, dp); 270228753Smm if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 271228753Smm return 0; 272228753Smm } 273228753Smm return 1; 274228753Smm} 275228753Smm 276228753Smm/** insert a stub hole (if necessary) for stub name */ 277228753Smmstatic int 278228753Smmfwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 279228753Smm{ 280228753Smm struct iter_forward_zone key; 281228753Smm key.node.key = &key; 282228753Smm key.dclass = c; 283228753Smm key.name = nm; 284228753Smm key.namelabs = dname_count_size_labels(key.name, &key.namelen); 285228753Smm return forwards_insert_data(fwd, key.dclass, key.name, 286228753Smm key.namelen, key.namelabs, NULL); 287228753Smm} 288228753Smm 289228753Smm/** make NULL entries for stubs */ 290228753Smmstatic int 291228753Smmmake_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 292228753Smm{ 293228753Smm struct config_stub* s; 294228753Smm uint8_t* dname; 295228753Smm size_t dname_len; 296228753Smm for(s = cfg->stubs; s; s = s->next) { 297228753Smm dname = sldns_str2wire_dname(s->name, &dname_len); 298228753Smm if(!dname) { 299228753Smm log_err("cannot parse stub name '%s'", s->name); 300228753Smm return 0; 301228753Smm } 302228753Smm if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) { 303228753Smm free(dname); 304228753Smm log_err("out of memory"); 305228753Smm return 0; 306228753Smm } 307228753Smm free(dname); 308228753Smm } 309228753Smm return 1; 310228753Smm} 311228753Smm 312228753Smmint 313228753Smmforwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 314228753Smm{ 315228753Smm fwd_del_tree(fwd); 316228753Smm fwd->tree = rbtree_create(fwd_cmp); 317228753Smm if(!fwd->tree) 318228753Smm return 0; 319228753Smm 320228753Smm /* read forward zones */ 321228753Smm if(!read_forwards(fwd, cfg)) 322228753Smm return 0; 323228753Smm if(!make_stub_holes(fwd, cfg)) 324228753Smm return 0; 325228753Smm fwd_init_parents(fwd); 326228753Smm return 1; 327228753Smm} 328228753Smm 329228753Smmstruct delegpt* 330228753Smmforwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 331228753Smm{ 332228753Smm rbnode_t* res = NULL; 333228753Smm struct iter_forward_zone key; 334228753Smm key.node.key = &key; 335228753Smm key.dclass = qclass; 336228753Smm key.name = qname; 337228753Smm key.namelabs = dname_count_size_labels(qname, &key.namelen); 338228753Smm res = rbtree_search(fwd->tree, &key); 339228753Smm if(res) return ((struct iter_forward_zone*)res)->dp; 340228753Smm return NULL; 341228753Smm} 342228753Smm 343228753Smmstruct delegpt* 344228753Smmforwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 345228753Smm{ 346228753Smm /* lookup the forward zone in the tree */ 347228753Smm rbnode_t* res = NULL; 348228753Smm struct iter_forward_zone *result; 349228753Smm struct iter_forward_zone key; 350316338Smm key.node.key = &key; 351228753Smm key.dclass = qclass; 352228753Smm key.name = qname; 353228753Smm key.namelabs = dname_count_size_labels(qname, &key.namelen); 354228753Smm if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 355228753Smm /* exact */ 356228753Smm result = (struct iter_forward_zone*)res; 357228753Smm } else { 358228753Smm /* smaller element (or no element) */ 359228753Smm int m; 360228753Smm result = (struct iter_forward_zone*)res; 361228753Smm if(!result || result->dclass != qclass) 362228753Smm return NULL; 363228753Smm /* count number of labels matched */ 364228753Smm (void)dname_lab_cmp(result->name, result->namelabs, key.name, 365228753Smm key.namelabs, &m); 366228753Smm while(result) { /* go up until qname is subdomain of stub */ 367228753Smm if(result->namelabs <= m) 368228753Smm break; 369228753Smm result = result->parent; 370228753Smm } 371228753Smm } 372228753Smm if(result) 373228753Smm return result->dp; 374228753Smm return NULL; 375228753Smm} 376228753Smm 377228753Smmstruct delegpt* 378228753Smmforwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 379228753Smm{ 380228753Smm uint8_t root = 0; 381228753Smm return forwards_lookup(fwd, &root, qclass); 382228753Smm} 383228753Smm 384228753Smmint 385228753Smmforwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 386228753Smm{ 387228753Smm struct iter_forward_zone key; 388228753Smm rbnode_t* n; 389228753Smm struct iter_forward_zone* p; 390228753Smm if(*dclass == 0) { 391228753Smm /* first root item is first item in tree */ 392228753Smm n = rbtree_first(fwd->tree); 393228753Smm if(n == RBTREE_NULL) 394228753Smm return 0; 395228753Smm p = (struct iter_forward_zone*)n; 396228753Smm if(dname_is_root(p->name)) { 397228753Smm *dclass = p->dclass; 398228753Smm return 1; 399228753Smm } 400228753Smm /* root not first item? search for higher items */ 401228753Smm *dclass = p->dclass + 1; 402228753Smm return forwards_next_root(fwd, dclass); 403228753Smm } 404228753Smm /* find class n in tree, we may get a direct hit, or if we don't 405228753Smm * this is the last item of the previous class so rbtree_next() takes 406228753Smm * us to the next root (if any) */ 407228753Smm key.node.key = &key; 408228753Smm key.name = (uint8_t*)"\000"; 409228753Smm key.namelen = 1; 410228753Smm key.namelabs = 0; 411228753Smm key.dclass = *dclass; 412228753Smm n = NULL; 413228753Smm if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 414228753Smm /* exact */ 415228753Smm return 1; 416228753Smm } else { 417228753Smm /* smaller element */ 418228753Smm if(!n || n == RBTREE_NULL) 419228753Smm return 0; /* nothing found */ 420228753Smm n = rbtree_next(n); 421228753Smm if(n == RBTREE_NULL) 422228753Smm return 0; /* no higher */ 423228753Smm p = (struct iter_forward_zone*)n; 424228753Smm if(dname_is_root(p->name)) { 425228753Smm *dclass = p->dclass; 426228753Smm return 1; 427228753Smm } 428228753Smm /* not a root node, return next higher item */ 429228753Smm *dclass = p->dclass+1; 430228753Smm return forwards_next_root(fwd, dclass); 431228753Smm } 432228753Smm} 433228753Smm 434228753Smmsize_t 435228753Smmforwards_get_mem(struct iter_forwards* fwd) 436228753Smm{ 437228753Smm struct iter_forward_zone* p; 438228753Smm size_t s; 439228753Smm if(!fwd) 440228753Smm return 0; 441228753Smm s = sizeof(*fwd) + sizeof(*fwd->tree); 442228753Smm RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) { 443228753Smm s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp); 444228753Smm } 445228753Smm return s; 446228753Smm} 447228753Smm 448228753Smmstatic struct iter_forward_zone* 449228753Smmfwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 450228753Smm{ 451228753Smm struct iter_forward_zone key; 452228753Smm key.node.key = &key; 453228753Smm key.dclass = c; 454228753Smm key.name = nm; 455228753Smm key.namelabs = dname_count_size_labels(nm, &key.namelen); 456228753Smm return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key); 457228753Smm} 458228753Smm 459228753Smmint 460228753Smmforwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 461228753Smm{ 462228753Smm struct iter_forward_zone *z; 463228753Smm if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) { 464228753Smm (void)rbtree_delete(fwd->tree, &z->node); 465228753Smm fwd_zone_free(z); 466228753Smm } 467228753Smm if(!forwards_insert(fwd, c, dp)) 468228753Smm return 0; 469228753Smm fwd_init_parents(fwd); 470228753Smm return 1; 471228753Smm} 472228753Smm 473228753Smmvoid 474228753Smmforwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 475228753Smm{ 476228753Smm struct iter_forward_zone *z; 477228753Smm if(!(z=fwd_zone_find(fwd, c, nm))) 478228753Smm return; /* nothing to do */ 479228753Smm (void)rbtree_delete(fwd->tree, &z->node); 480228753Smm fwd_zone_free(z); 481228753Smm fwd_init_parents(fwd); 482228753Smm} 483228753Smm 484228753Smmint 485228753Smmforwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 486228753Smm{ 487228753Smm if(!fwd_add_stub_hole(fwd, c, nm)) { 488228753Smm return 0; 489228753Smm } 490228753Smm fwd_init_parents(fwd); 491228753Smm return 1; 492228753Smm} 493228753Smm 494228753Smmvoid 495228753Smmforwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 496228753Smm{ 497228753Smm struct iter_forward_zone *z; 498228753Smm if(!(z=fwd_zone_find(fwd, c, nm))) 499228753Smm return; /* nothing to do */ 500228753Smm if(z->dp != NULL) 501228753Smm return; /* not a stub hole */ 502228753Smm (void)rbtree_delete(fwd->tree, &z->node); 503228753Smm fwd_zone_free(z); 504228753Smm fwd_init_parents(fwd); 505228753Smm} 506228753Smm 507228753Smm