1238106Sdes/* 2238106Sdes * iterator/iter_fwd.c - iterative resolver module forward zones. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains functions to assist the iterator module. 40238106Sdes * Keep track of forward zones and config settings. 41238106Sdes */ 42238106Sdes#include "config.h" 43238106Sdes#include "iterator/iter_fwd.h" 44238106Sdes#include "iterator/iter_delegpt.h" 45238106Sdes#include "util/log.h" 46238106Sdes#include "util/config_file.h" 47238106Sdes#include "util/net_help.h" 48238106Sdes#include "util/data/dname.h" 49269257Sdes#include "ldns/rrdef.h" 50269257Sdes#include "ldns/str2wire.h" 51238106Sdes 52238106Sdesint 53238106Sdesfwd_cmp(const void* k1, const void* k2) 54238106Sdes{ 55238106Sdes int m; 56238106Sdes struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1; 57238106Sdes struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2; 58238106Sdes if(n1->dclass != n2->dclass) { 59238106Sdes if(n1->dclass < n2->dclass) 60238106Sdes return -1; 61238106Sdes return 1; 62238106Sdes } 63238106Sdes return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 64238106Sdes &m); 65238106Sdes} 66238106Sdes 67238106Sdesstruct iter_forwards* 68238106Sdesforwards_create(void) 69238106Sdes{ 70238106Sdes struct iter_forwards* fwd = (struct iter_forwards*)calloc(1, 71238106Sdes sizeof(struct iter_forwards)); 72238106Sdes if(!fwd) 73238106Sdes return NULL; 74238106Sdes return fwd; 75238106Sdes} 76238106Sdes 77238106Sdesstatic void fwd_zone_free(struct iter_forward_zone* n) 78238106Sdes{ 79238106Sdes if(!n) return; 80238106Sdes delegpt_free_mlc(n->dp); 81238106Sdes free(n->name); 82238106Sdes free(n); 83238106Sdes} 84238106Sdes 85238106Sdesstatic void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg)) 86238106Sdes{ 87238106Sdes struct iter_forward_zone* node = (struct iter_forward_zone*)n; 88238106Sdes fwd_zone_free(node); 89238106Sdes} 90238106Sdes 91238106Sdesstatic void fwd_del_tree(struct iter_forwards* fwd) 92238106Sdes{ 93238106Sdes if(fwd->tree) 94238106Sdes traverse_postorder(fwd->tree, &delfwdnode, NULL); 95238106Sdes free(fwd->tree); 96238106Sdes} 97238106Sdes 98238106Sdesvoid 99238106Sdesforwards_delete(struct iter_forwards* fwd) 100238106Sdes{ 101238106Sdes if(!fwd) 102238106Sdes return; 103238106Sdes fwd_del_tree(fwd); 104238106Sdes free(fwd); 105238106Sdes} 106238106Sdes 107238106Sdes/** insert info into forward structure */ 108238106Sdesstatic int 109238106Sdesforwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 110238106Sdes size_t nmlen, int nmlabs, struct delegpt* dp) 111238106Sdes{ 112238106Sdes struct iter_forward_zone* node = (struct iter_forward_zone*)malloc( 113238106Sdes sizeof(struct iter_forward_zone)); 114238106Sdes if(!node) { 115238106Sdes delegpt_free_mlc(dp); 116238106Sdes return 0; 117238106Sdes } 118238106Sdes node->node.key = node; 119238106Sdes node->dclass = c; 120238106Sdes node->name = memdup(nm, nmlen); 121238106Sdes if(!node->name) { 122238106Sdes delegpt_free_mlc(dp); 123238106Sdes free(node); 124238106Sdes return 0; 125238106Sdes } 126238106Sdes node->namelen = nmlen; 127238106Sdes node->namelabs = nmlabs; 128238106Sdes node->dp = dp; 129238106Sdes if(!rbtree_insert(fwd->tree, &node->node)) { 130249141Sdes char buf[257]; 131249141Sdes dname_str(nm, buf); 132249141Sdes log_err("duplicate forward zone %s ignored.", buf); 133238106Sdes delegpt_free_mlc(dp); 134238106Sdes free(node->name); 135238106Sdes free(node); 136238106Sdes } 137238106Sdes return 1; 138238106Sdes} 139238106Sdes 140238106Sdes/** insert new info into forward structure given dp */ 141238106Sdesstatic int 142238106Sdesforwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 143238106Sdes{ 144238106Sdes return forwards_insert_data(fwd, c, dp->name, dp->namelen, 145238106Sdes dp->namelabs, dp); 146238106Sdes} 147238106Sdes 148238106Sdes/** initialise parent pointers in the tree */ 149238106Sdesstatic void 150238106Sdesfwd_init_parents(struct iter_forwards* fwd) 151238106Sdes{ 152238106Sdes struct iter_forward_zone* node, *prev = NULL, *p; 153238106Sdes int m; 154238106Sdes RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) { 155238106Sdes node->parent = NULL; 156238106Sdes if(!prev || prev->dclass != node->dclass) { 157238106Sdes prev = node; 158238106Sdes continue; 159238106Sdes } 160238106Sdes (void)dname_lab_cmp(prev->name, prev->namelabs, node->name, 161238106Sdes node->namelabs, &m); /* we know prev is smaller */ 162238106Sdes /* sort order like: . com. bla.com. zwb.com. net. */ 163238106Sdes /* find the previous, or parent-parent-parent */ 164238106Sdes for(p = prev; p; p = p->parent) 165238106Sdes /* looking for name with few labels, a parent */ 166238106Sdes if(p->namelabs <= m) { 167238106Sdes /* ==: since prev matched m, this is closest*/ 168238106Sdes /* <: prev matches more, but is not a parent, 169238106Sdes * this one is a (grand)parent */ 170238106Sdes node->parent = p; 171238106Sdes break; 172238106Sdes } 173238106Sdes prev = node; 174238106Sdes } 175238106Sdes} 176238106Sdes 177238106Sdes/** set zone name */ 178238106Sdesstatic struct delegpt* 179238106Sdesread_fwds_name(struct config_stub* s) 180238106Sdes{ 181238106Sdes struct delegpt* dp; 182269257Sdes uint8_t* dname; 183269257Sdes size_t dname_len; 184238106Sdes if(!s->name) { 185238106Sdes log_err("forward zone without a name (use name \".\" to forward everything)"); 186238106Sdes return NULL; 187238106Sdes } 188269257Sdes dname = sldns_str2wire_dname(s->name, &dname_len); 189269257Sdes if(!dname) { 190238106Sdes log_err("cannot parse forward zone name %s", s->name); 191238106Sdes return NULL; 192238106Sdes } 193269257Sdes if(!(dp=delegpt_create_mlc(dname))) { 194269257Sdes free(dname); 195238106Sdes log_err("out of memory"); 196238106Sdes return NULL; 197238106Sdes } 198269257Sdes free(dname); 199238106Sdes return dp; 200238106Sdes} 201238106Sdes 202238106Sdes/** set fwd host names */ 203238106Sdesstatic int 204238106Sdesread_fwds_host(struct config_stub* s, struct delegpt* dp) 205238106Sdes{ 206238106Sdes struct config_strlist* p; 207269257Sdes uint8_t* dname; 208269257Sdes size_t dname_len; 209238106Sdes for(p = s->hosts; p; p = p->next) { 210238106Sdes log_assert(p->str); 211269257Sdes dname = sldns_str2wire_dname(p->str, &dname_len); 212269257Sdes if(!dname) { 213238106Sdes log_err("cannot parse forward %s server name: '%s'", 214238106Sdes s->name, p->str); 215238106Sdes return 0; 216238106Sdes } 217269257Sdes if(!delegpt_add_ns_mlc(dp, dname, 0)) { 218269257Sdes free(dname); 219238106Sdes log_err("out of memory"); 220238106Sdes return 0; 221238106Sdes } 222269257Sdes free(dname); 223238106Sdes } 224238106Sdes return 1; 225238106Sdes} 226238106Sdes 227238106Sdes/** set fwd server addresses */ 228238106Sdesstatic int 229238106Sdesread_fwds_addr(struct config_stub* s, struct delegpt* dp) 230238106Sdes{ 231238106Sdes struct config_strlist* p; 232238106Sdes struct sockaddr_storage addr; 233238106Sdes socklen_t addrlen; 234238106Sdes for(p = s->addrs; p; p = p->next) { 235238106Sdes log_assert(p->str); 236238106Sdes if(!extstrtoaddr(p->str, &addr, &addrlen)) { 237238106Sdes log_err("cannot parse forward %s ip address: '%s'", 238238106Sdes s->name, p->str); 239238106Sdes return 0; 240238106Sdes } 241238106Sdes if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) { 242238106Sdes log_err("out of memory"); 243238106Sdes return 0; 244238106Sdes } 245238106Sdes } 246238106Sdes return 1; 247238106Sdes} 248238106Sdes 249238106Sdes/** read forwards config */ 250238106Sdesstatic int 251238106Sdesread_forwards(struct iter_forwards* fwd, struct config_file* cfg) 252238106Sdes{ 253238106Sdes struct config_stub* s; 254238106Sdes for(s = cfg->forwards; s; s = s->next) { 255238106Sdes struct delegpt* dp; 256249141Sdes if(!(dp=read_fwds_name(s))) 257238106Sdes return 0; 258249141Sdes if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) { 259249141Sdes delegpt_free_mlc(dp); 260249141Sdes return 0; 261249141Sdes } 262238106Sdes /* set flag that parent side NS information is included. 263238106Sdes * Asking a (higher up) server on the internet is not useful */ 264238106Sdes /* the flag is turned off for 'forward-first' so that the 265238106Sdes * last resort will ask for parent-side NS record and thus 266238106Sdes * fallback to the internet name servers on a failure */ 267238106Sdes dp->has_parent_side_NS = (uint8_t)!s->isfirst; 268249141Sdes verbose(VERB_QUERY, "Forward zone server list:"); 269249141Sdes delegpt_log(VERB_QUERY, dp); 270238106Sdes if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 271238106Sdes return 0; 272238106Sdes } 273238106Sdes return 1; 274238106Sdes} 275238106Sdes 276238106Sdes/** insert a stub hole (if necessary) for stub name */ 277238106Sdesstatic int 278238106Sdesfwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 279238106Sdes{ 280238106Sdes struct iter_forward_zone key; 281238106Sdes key.node.key = &key; 282238106Sdes key.dclass = c; 283238106Sdes key.name = nm; 284238106Sdes key.namelabs = dname_count_size_labels(key.name, &key.namelen); 285249141Sdes return forwards_insert_data(fwd, key.dclass, key.name, 286249141Sdes key.namelen, key.namelabs, NULL); 287238106Sdes} 288238106Sdes 289238106Sdes/** make NULL entries for stubs */ 290238106Sdesstatic int 291238106Sdesmake_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 292238106Sdes{ 293238106Sdes struct config_stub* s; 294269257Sdes uint8_t* dname; 295269257Sdes size_t dname_len; 296238106Sdes for(s = cfg->stubs; s; s = s->next) { 297269257Sdes dname = sldns_str2wire_dname(s->name, &dname_len); 298269257Sdes if(!dname) { 299238106Sdes log_err("cannot parse stub name '%s'", s->name); 300238106Sdes return 0; 301238106Sdes } 302269257Sdes if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) { 303269257Sdes free(dname); 304238106Sdes log_err("out of memory"); 305238106Sdes return 0; 306238106Sdes } 307269257Sdes free(dname); 308238106Sdes } 309238106Sdes return 1; 310238106Sdes} 311238106Sdes 312238106Sdesint 313238106Sdesforwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 314238106Sdes{ 315238106Sdes fwd_del_tree(fwd); 316238106Sdes fwd->tree = rbtree_create(fwd_cmp); 317238106Sdes if(!fwd->tree) 318238106Sdes return 0; 319238106Sdes 320238106Sdes /* read forward zones */ 321238106Sdes if(!read_forwards(fwd, cfg)) 322238106Sdes return 0; 323238106Sdes if(!make_stub_holes(fwd, cfg)) 324238106Sdes return 0; 325238106Sdes fwd_init_parents(fwd); 326238106Sdes return 1; 327238106Sdes} 328238106Sdes 329238106Sdesstruct delegpt* 330269257Sdesforwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 331269257Sdes{ 332269257Sdes rbnode_t* res = NULL; 333269257Sdes struct iter_forward_zone key; 334269257Sdes key.node.key = &key; 335269257Sdes key.dclass = qclass; 336269257Sdes key.name = qname; 337269257Sdes key.namelabs = dname_count_size_labels(qname, &key.namelen); 338269257Sdes res = rbtree_search(fwd->tree, &key); 339269257Sdes if(res) return ((struct iter_forward_zone*)res)->dp; 340269257Sdes return NULL; 341269257Sdes} 342269257Sdes 343269257Sdesstruct delegpt* 344238106Sdesforwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 345238106Sdes{ 346238106Sdes /* lookup the forward zone in the tree */ 347238106Sdes rbnode_t* res = NULL; 348238106Sdes struct iter_forward_zone *result; 349238106Sdes struct iter_forward_zone key; 350238106Sdes key.node.key = &key; 351238106Sdes key.dclass = qclass; 352238106Sdes key.name = qname; 353238106Sdes key.namelabs = dname_count_size_labels(qname, &key.namelen); 354238106Sdes if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 355238106Sdes /* exact */ 356238106Sdes result = (struct iter_forward_zone*)res; 357238106Sdes } else { 358238106Sdes /* smaller element (or no element) */ 359238106Sdes int m; 360238106Sdes result = (struct iter_forward_zone*)res; 361238106Sdes if(!result || result->dclass != qclass) 362238106Sdes return NULL; 363238106Sdes /* count number of labels matched */ 364238106Sdes (void)dname_lab_cmp(result->name, result->namelabs, key.name, 365238106Sdes key.namelabs, &m); 366238106Sdes while(result) { /* go up until qname is subdomain of stub */ 367238106Sdes if(result->namelabs <= m) 368238106Sdes break; 369238106Sdes result = result->parent; 370238106Sdes } 371238106Sdes } 372238106Sdes if(result) 373238106Sdes return result->dp; 374238106Sdes return NULL; 375238106Sdes} 376238106Sdes 377238106Sdesstruct delegpt* 378238106Sdesforwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 379238106Sdes{ 380238106Sdes uint8_t root = 0; 381238106Sdes return forwards_lookup(fwd, &root, qclass); 382238106Sdes} 383238106Sdes 384238106Sdesint 385238106Sdesforwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 386238106Sdes{ 387238106Sdes struct iter_forward_zone key; 388238106Sdes rbnode_t* n; 389238106Sdes struct iter_forward_zone* p; 390238106Sdes if(*dclass == 0) { 391238106Sdes /* first root item is first item in tree */ 392238106Sdes n = rbtree_first(fwd->tree); 393238106Sdes if(n == RBTREE_NULL) 394238106Sdes return 0; 395238106Sdes p = (struct iter_forward_zone*)n; 396238106Sdes if(dname_is_root(p->name)) { 397238106Sdes *dclass = p->dclass; 398238106Sdes return 1; 399238106Sdes } 400238106Sdes /* root not first item? search for higher items */ 401238106Sdes *dclass = p->dclass + 1; 402238106Sdes return forwards_next_root(fwd, dclass); 403238106Sdes } 404238106Sdes /* find class n in tree, we may get a direct hit, or if we don't 405238106Sdes * this is the last item of the previous class so rbtree_next() takes 406238106Sdes * us to the next root (if any) */ 407238106Sdes key.node.key = &key; 408238106Sdes key.name = (uint8_t*)"\000"; 409238106Sdes key.namelen = 1; 410238106Sdes key.namelabs = 0; 411238106Sdes key.dclass = *dclass; 412238106Sdes n = NULL; 413238106Sdes if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 414238106Sdes /* exact */ 415238106Sdes return 1; 416238106Sdes } else { 417238106Sdes /* smaller element */ 418238106Sdes if(!n || n == RBTREE_NULL) 419238106Sdes return 0; /* nothing found */ 420238106Sdes n = rbtree_next(n); 421238106Sdes if(n == RBTREE_NULL) 422238106Sdes return 0; /* no higher */ 423238106Sdes p = (struct iter_forward_zone*)n; 424238106Sdes if(dname_is_root(p->name)) { 425238106Sdes *dclass = p->dclass; 426238106Sdes return 1; 427238106Sdes } 428238106Sdes /* not a root node, return next higher item */ 429238106Sdes *dclass = p->dclass+1; 430238106Sdes return forwards_next_root(fwd, dclass); 431238106Sdes } 432238106Sdes} 433238106Sdes 434238106Sdessize_t 435238106Sdesforwards_get_mem(struct iter_forwards* fwd) 436238106Sdes{ 437238106Sdes struct iter_forward_zone* p; 438238106Sdes size_t s; 439238106Sdes if(!fwd) 440238106Sdes return 0; 441238106Sdes s = sizeof(*fwd) + sizeof(*fwd->tree); 442238106Sdes RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) { 443238106Sdes s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp); 444238106Sdes } 445238106Sdes return s; 446238106Sdes} 447238106Sdes 448238106Sdesstatic struct iter_forward_zone* 449238106Sdesfwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 450238106Sdes{ 451238106Sdes struct iter_forward_zone key; 452238106Sdes key.node.key = &key; 453238106Sdes key.dclass = c; 454238106Sdes key.name = nm; 455238106Sdes key.namelabs = dname_count_size_labels(nm, &key.namelen); 456238106Sdes return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key); 457238106Sdes} 458238106Sdes 459238106Sdesint 460238106Sdesforwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 461238106Sdes{ 462238106Sdes struct iter_forward_zone *z; 463238106Sdes if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) { 464238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 465238106Sdes fwd_zone_free(z); 466238106Sdes } 467238106Sdes if(!forwards_insert(fwd, c, dp)) 468238106Sdes return 0; 469238106Sdes fwd_init_parents(fwd); 470238106Sdes return 1; 471238106Sdes} 472238106Sdes 473238106Sdesvoid 474238106Sdesforwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 475238106Sdes{ 476238106Sdes struct iter_forward_zone *z; 477238106Sdes if(!(z=fwd_zone_find(fwd, c, nm))) 478238106Sdes return; /* nothing to do */ 479238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 480238106Sdes fwd_zone_free(z); 481238106Sdes fwd_init_parents(fwd); 482238106Sdes} 483238106Sdes 484238106Sdesint 485238106Sdesforwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 486238106Sdes{ 487238106Sdes if(!fwd_add_stub_hole(fwd, c, nm)) { 488238106Sdes return 0; 489238106Sdes } 490238106Sdes fwd_init_parents(fwd); 491238106Sdes return 1; 492238106Sdes} 493238106Sdes 494238106Sdesvoid 495238106Sdesforwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 496238106Sdes{ 497238106Sdes struct iter_forward_zone *z; 498238106Sdes if(!(z=fwd_zone_find(fwd, c, nm))) 499238106Sdes return; /* nothing to do */ 500238106Sdes if(z->dp != NULL) 501238106Sdes return; /* not a stub hole */ 502238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 503238106Sdes fwd_zone_free(z); 504238106Sdes fwd_init_parents(fwd); 505238106Sdes} 506238106Sdes 507