iter_fwd.c revision 238106
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 24238106Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25238106Sdes * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26238106Sdes * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27238106Sdes * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28238106Sdes * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29238106Sdes * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30238106Sdes * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31238106Sdes * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32238106Sdes * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33238106Sdes * 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 <ldns/rdata.h> 44238106Sdes#include <ldns/dname.h> 45238106Sdes#include <ldns/rr.h> 46238106Sdes#include "iterator/iter_fwd.h" 47238106Sdes#include "iterator/iter_delegpt.h" 48238106Sdes#include "util/log.h" 49238106Sdes#include "util/config_file.h" 50238106Sdes#include "util/net_help.h" 51238106Sdes#include "util/data/dname.h" 52238106Sdes 53238106Sdesint 54238106Sdesfwd_cmp(const void* k1, const void* k2) 55238106Sdes{ 56238106Sdes int m; 57238106Sdes struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1; 58238106Sdes struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2; 59238106Sdes if(n1->dclass != n2->dclass) { 60238106Sdes if(n1->dclass < n2->dclass) 61238106Sdes return -1; 62238106Sdes return 1; 63238106Sdes } 64238106Sdes return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 65238106Sdes &m); 66238106Sdes} 67238106Sdes 68238106Sdesstruct iter_forwards* 69238106Sdesforwards_create(void) 70238106Sdes{ 71238106Sdes struct iter_forwards* fwd = (struct iter_forwards*)calloc(1, 72238106Sdes sizeof(struct iter_forwards)); 73238106Sdes if(!fwd) 74238106Sdes return NULL; 75238106Sdes return fwd; 76238106Sdes} 77238106Sdes 78238106Sdesstatic void fwd_zone_free(struct iter_forward_zone* n) 79238106Sdes{ 80238106Sdes if(!n) return; 81238106Sdes delegpt_free_mlc(n->dp); 82238106Sdes free(n->name); 83238106Sdes free(n); 84238106Sdes} 85238106Sdes 86238106Sdesstatic void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg)) 87238106Sdes{ 88238106Sdes struct iter_forward_zone* node = (struct iter_forward_zone*)n; 89238106Sdes fwd_zone_free(node); 90238106Sdes} 91238106Sdes 92238106Sdesstatic void fwd_del_tree(struct iter_forwards* fwd) 93238106Sdes{ 94238106Sdes if(fwd->tree) 95238106Sdes traverse_postorder(fwd->tree, &delfwdnode, NULL); 96238106Sdes free(fwd->tree); 97238106Sdes} 98238106Sdes 99238106Sdesvoid 100238106Sdesforwards_delete(struct iter_forwards* fwd) 101238106Sdes{ 102238106Sdes if(!fwd) 103238106Sdes return; 104238106Sdes fwd_del_tree(fwd); 105238106Sdes free(fwd); 106238106Sdes} 107238106Sdes 108238106Sdes/** insert info into forward structure */ 109238106Sdesstatic int 110238106Sdesforwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 111238106Sdes size_t nmlen, int nmlabs, struct delegpt* dp) 112238106Sdes{ 113238106Sdes struct iter_forward_zone* node = (struct iter_forward_zone*)malloc( 114238106Sdes sizeof(struct iter_forward_zone)); 115238106Sdes if(!node) { 116238106Sdes delegpt_free_mlc(dp); 117238106Sdes return 0; 118238106Sdes } 119238106Sdes node->node.key = node; 120238106Sdes node->dclass = c; 121238106Sdes node->name = memdup(nm, nmlen); 122238106Sdes if(!node->name) { 123238106Sdes delegpt_free_mlc(dp); 124238106Sdes free(node); 125238106Sdes return 0; 126238106Sdes } 127238106Sdes node->namelen = nmlen; 128238106Sdes node->namelabs = nmlabs; 129238106Sdes node->dp = dp; 130238106Sdes if(!rbtree_insert(fwd->tree, &node->node)) { 131238106Sdes log_err("duplicate forward zone ignored."); 132238106Sdes delegpt_free_mlc(dp); 133238106Sdes free(node->name); 134238106Sdes free(node); 135238106Sdes } 136238106Sdes return 1; 137238106Sdes} 138238106Sdes 139238106Sdes/** insert new info into forward structure given dp */ 140238106Sdesstatic int 141238106Sdesforwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 142238106Sdes{ 143238106Sdes return forwards_insert_data(fwd, c, dp->name, dp->namelen, 144238106Sdes dp->namelabs, dp); 145238106Sdes} 146238106Sdes 147238106Sdes/** initialise parent pointers in the tree */ 148238106Sdesstatic void 149238106Sdesfwd_init_parents(struct iter_forwards* fwd) 150238106Sdes{ 151238106Sdes struct iter_forward_zone* node, *prev = NULL, *p; 152238106Sdes int m; 153238106Sdes RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) { 154238106Sdes node->parent = NULL; 155238106Sdes if(!prev || prev->dclass != node->dclass) { 156238106Sdes prev = node; 157238106Sdes continue; 158238106Sdes } 159238106Sdes (void)dname_lab_cmp(prev->name, prev->namelabs, node->name, 160238106Sdes node->namelabs, &m); /* we know prev is smaller */ 161238106Sdes /* sort order like: . com. bla.com. zwb.com. net. */ 162238106Sdes /* find the previous, or parent-parent-parent */ 163238106Sdes for(p = prev; p; p = p->parent) 164238106Sdes /* looking for name with few labels, a parent */ 165238106Sdes if(p->namelabs <= m) { 166238106Sdes /* ==: since prev matched m, this is closest*/ 167238106Sdes /* <: prev matches more, but is not a parent, 168238106Sdes * this one is a (grand)parent */ 169238106Sdes node->parent = p; 170238106Sdes break; 171238106Sdes } 172238106Sdes prev = node; 173238106Sdes } 174238106Sdes} 175238106Sdes 176238106Sdes/** set zone name */ 177238106Sdesstatic struct delegpt* 178238106Sdesread_fwds_name(struct config_stub* s) 179238106Sdes{ 180238106Sdes struct delegpt* dp; 181238106Sdes ldns_rdf* rdf; 182238106Sdes if(!s->name) { 183238106Sdes log_err("forward zone without a name (use name \".\" to forward everything)"); 184238106Sdes return NULL; 185238106Sdes } 186238106Sdes rdf = ldns_dname_new_frm_str(s->name); 187238106Sdes if(!rdf) { 188238106Sdes log_err("cannot parse forward zone name %s", s->name); 189238106Sdes return NULL; 190238106Sdes } 191238106Sdes if(!(dp=delegpt_create_mlc(ldns_rdf_data(rdf)))) { 192238106Sdes ldns_rdf_deep_free(rdf); 193238106Sdes log_err("out of memory"); 194238106Sdes return NULL; 195238106Sdes } 196238106Sdes ldns_rdf_deep_free(rdf); 197238106Sdes return dp; 198238106Sdes} 199238106Sdes 200238106Sdes/** set fwd host names */ 201238106Sdesstatic int 202238106Sdesread_fwds_host(struct config_stub* s, struct delegpt* dp) 203238106Sdes{ 204238106Sdes struct config_strlist* p; 205238106Sdes ldns_rdf* rdf; 206238106Sdes for(p = s->hosts; p; p = p->next) { 207238106Sdes log_assert(p->str); 208238106Sdes rdf = ldns_dname_new_frm_str(p->str); 209238106Sdes if(!rdf) { 210238106Sdes log_err("cannot parse forward %s server name: '%s'", 211238106Sdes s->name, p->str); 212238106Sdes return 0; 213238106Sdes } 214238106Sdes if(!delegpt_add_ns_mlc(dp, ldns_rdf_data(rdf), 0)) { 215238106Sdes ldns_rdf_deep_free(rdf); 216238106Sdes log_err("out of memory"); 217238106Sdes return 0; 218238106Sdes } 219238106Sdes ldns_rdf_deep_free(rdf); 220238106Sdes } 221238106Sdes return 1; 222238106Sdes} 223238106Sdes 224238106Sdes/** set fwd server addresses */ 225238106Sdesstatic int 226238106Sdesread_fwds_addr(struct config_stub* s, struct delegpt* dp) 227238106Sdes{ 228238106Sdes struct config_strlist* p; 229238106Sdes struct sockaddr_storage addr; 230238106Sdes socklen_t addrlen; 231238106Sdes for(p = s->addrs; p; p = p->next) { 232238106Sdes log_assert(p->str); 233238106Sdes if(!extstrtoaddr(p->str, &addr, &addrlen)) { 234238106Sdes log_err("cannot parse forward %s ip address: '%s'", 235238106Sdes s->name, p->str); 236238106Sdes return 0; 237238106Sdes } 238238106Sdes if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) { 239238106Sdes log_err("out of memory"); 240238106Sdes return 0; 241238106Sdes } 242238106Sdes } 243238106Sdes return 1; 244238106Sdes} 245238106Sdes 246238106Sdes/** read forwards config */ 247238106Sdesstatic int 248238106Sdesread_forwards(struct iter_forwards* fwd, struct config_file* cfg) 249238106Sdes{ 250238106Sdes struct config_stub* s; 251238106Sdes for(s = cfg->forwards; s; s = s->next) { 252238106Sdes struct delegpt* dp; 253238106Sdes if(!(dp=read_fwds_name(s)) || 254238106Sdes !read_fwds_host(s, dp) || 255238106Sdes !read_fwds_addr(s, dp)) 256238106Sdes return 0; 257238106Sdes /* set flag that parent side NS information is included. 258238106Sdes * Asking a (higher up) server on the internet is not useful */ 259238106Sdes /* the flag is turned off for 'forward-first' so that the 260238106Sdes * last resort will ask for parent-side NS record and thus 261238106Sdes * fallback to the internet name servers on a failure */ 262238106Sdes dp->has_parent_side_NS = (uint8_t)!s->isfirst; 263238106Sdes if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 264238106Sdes return 0; 265238106Sdes verbose(VERB_QUERY, "Forward zone server list:"); 266238106Sdes delegpt_log(VERB_QUERY, dp); 267238106Sdes } 268238106Sdes return 1; 269238106Sdes} 270238106Sdes 271238106Sdes/** see if zone needs to have a hole inserted */ 272238106Sdesstatic int 273238106Sdesneed_hole_insert(rbtree_t* tree, struct iter_forward_zone* zone) 274238106Sdes{ 275238106Sdes struct iter_forward_zone k; 276238106Sdes if(rbtree_search(tree, zone)) 277238106Sdes return 0; /* exact match exists */ 278238106Sdes k = *zone; 279238106Sdes k.node.key = &k; 280238106Sdes /* search up the tree */ 281238106Sdes do { 282238106Sdes dname_remove_label(&k.name, &k.namelen); 283238106Sdes k.namelabs --; 284238106Sdes if(rbtree_search(tree, &k)) 285238106Sdes return 1; /* found an upper forward zone, need hole */ 286238106Sdes } while(k.namelabs > 1); 287238106Sdes return 0; /* no forwards above, no holes needed */ 288238106Sdes} 289238106Sdes 290238106Sdes/** insert a stub hole (if necessary) for stub name */ 291238106Sdesstatic int 292238106Sdesfwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 293238106Sdes{ 294238106Sdes struct iter_forward_zone key; 295238106Sdes key.node.key = &key; 296238106Sdes key.dclass = c; 297238106Sdes key.name = nm; 298238106Sdes key.namelabs = dname_count_size_labels(key.name, &key.namelen); 299238106Sdes if(need_hole_insert(fwd->tree, &key)) { 300238106Sdes return forwards_insert_data(fwd, key.dclass, key.name, 301238106Sdes key.namelen, key.namelabs, NULL); 302238106Sdes } 303238106Sdes return 1; 304238106Sdes} 305238106Sdes 306238106Sdes/** make NULL entries for stubs */ 307238106Sdesstatic int 308238106Sdesmake_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 309238106Sdes{ 310238106Sdes struct config_stub* s; 311238106Sdes for(s = cfg->stubs; s; s = s->next) { 312238106Sdes ldns_rdf* rdf = ldns_dname_new_frm_str(s->name); 313238106Sdes if(!rdf) { 314238106Sdes log_err("cannot parse stub name '%s'", s->name); 315238106Sdes return 0; 316238106Sdes } 317238106Sdes if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, 318238106Sdes ldns_rdf_data(rdf))) { 319238106Sdes ldns_rdf_deep_free(rdf); 320238106Sdes log_err("out of memory"); 321238106Sdes return 0; 322238106Sdes } 323238106Sdes ldns_rdf_deep_free(rdf); 324238106Sdes } 325238106Sdes return 1; 326238106Sdes} 327238106Sdes 328238106Sdesint 329238106Sdesforwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 330238106Sdes{ 331238106Sdes fwd_del_tree(fwd); 332238106Sdes fwd->tree = rbtree_create(fwd_cmp); 333238106Sdes if(!fwd->tree) 334238106Sdes return 0; 335238106Sdes 336238106Sdes /* read forward zones */ 337238106Sdes if(!read_forwards(fwd, cfg)) 338238106Sdes return 0; 339238106Sdes if(!make_stub_holes(fwd, cfg)) 340238106Sdes return 0; 341238106Sdes fwd_init_parents(fwd); 342238106Sdes return 1; 343238106Sdes} 344238106Sdes 345238106Sdesstruct delegpt* 346238106Sdesforwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 347238106Sdes{ 348238106Sdes /* lookup the forward zone in the tree */ 349238106Sdes rbnode_t* res = NULL; 350238106Sdes struct iter_forward_zone *result; 351238106Sdes struct iter_forward_zone key; 352238106Sdes key.node.key = &key; 353238106Sdes key.dclass = qclass; 354238106Sdes key.name = qname; 355238106Sdes key.namelabs = dname_count_size_labels(qname, &key.namelen); 356238106Sdes if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 357238106Sdes /* exact */ 358238106Sdes result = (struct iter_forward_zone*)res; 359238106Sdes } else { 360238106Sdes /* smaller element (or no element) */ 361238106Sdes int m; 362238106Sdes result = (struct iter_forward_zone*)res; 363238106Sdes if(!result || result->dclass != qclass) 364238106Sdes return NULL; 365238106Sdes /* count number of labels matched */ 366238106Sdes (void)dname_lab_cmp(result->name, result->namelabs, key.name, 367238106Sdes key.namelabs, &m); 368238106Sdes while(result) { /* go up until qname is subdomain of stub */ 369238106Sdes if(result->namelabs <= m) 370238106Sdes break; 371238106Sdes result = result->parent; 372238106Sdes } 373238106Sdes } 374238106Sdes if(result) 375238106Sdes return result->dp; 376238106Sdes return NULL; 377238106Sdes} 378238106Sdes 379238106Sdesstruct delegpt* 380238106Sdesforwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 381238106Sdes{ 382238106Sdes uint8_t root = 0; 383238106Sdes return forwards_lookup(fwd, &root, qclass); 384238106Sdes} 385238106Sdes 386238106Sdesint 387238106Sdesforwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 388238106Sdes{ 389238106Sdes struct iter_forward_zone key; 390238106Sdes rbnode_t* n; 391238106Sdes struct iter_forward_zone* p; 392238106Sdes if(*dclass == 0) { 393238106Sdes /* first root item is first item in tree */ 394238106Sdes n = rbtree_first(fwd->tree); 395238106Sdes if(n == RBTREE_NULL) 396238106Sdes return 0; 397238106Sdes p = (struct iter_forward_zone*)n; 398238106Sdes if(dname_is_root(p->name)) { 399238106Sdes *dclass = p->dclass; 400238106Sdes return 1; 401238106Sdes } 402238106Sdes /* root not first item? search for higher items */ 403238106Sdes *dclass = p->dclass + 1; 404238106Sdes return forwards_next_root(fwd, dclass); 405238106Sdes } 406238106Sdes /* find class n in tree, we may get a direct hit, or if we don't 407238106Sdes * this is the last item of the previous class so rbtree_next() takes 408238106Sdes * us to the next root (if any) */ 409238106Sdes key.node.key = &key; 410238106Sdes key.name = (uint8_t*)"\000"; 411238106Sdes key.namelen = 1; 412238106Sdes key.namelabs = 0; 413238106Sdes key.dclass = *dclass; 414238106Sdes n = NULL; 415238106Sdes if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 416238106Sdes /* exact */ 417238106Sdes return 1; 418238106Sdes } else { 419238106Sdes /* smaller element */ 420238106Sdes if(!n || n == RBTREE_NULL) 421238106Sdes return 0; /* nothing found */ 422238106Sdes n = rbtree_next(n); 423238106Sdes if(n == RBTREE_NULL) 424238106Sdes return 0; /* no higher */ 425238106Sdes p = (struct iter_forward_zone*)n; 426238106Sdes if(dname_is_root(p->name)) { 427238106Sdes *dclass = p->dclass; 428238106Sdes return 1; 429238106Sdes } 430238106Sdes /* not a root node, return next higher item */ 431238106Sdes *dclass = p->dclass+1; 432238106Sdes return forwards_next_root(fwd, dclass); 433238106Sdes } 434238106Sdes} 435238106Sdes 436238106Sdessize_t 437238106Sdesforwards_get_mem(struct iter_forwards* fwd) 438238106Sdes{ 439238106Sdes struct iter_forward_zone* p; 440238106Sdes size_t s; 441238106Sdes if(!fwd) 442238106Sdes return 0; 443238106Sdes s = sizeof(*fwd) + sizeof(*fwd->tree); 444238106Sdes RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) { 445238106Sdes s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp); 446238106Sdes } 447238106Sdes return s; 448238106Sdes} 449238106Sdes 450238106Sdesstatic struct iter_forward_zone* 451238106Sdesfwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 452238106Sdes{ 453238106Sdes struct iter_forward_zone key; 454238106Sdes key.node.key = &key; 455238106Sdes key.dclass = c; 456238106Sdes key.name = nm; 457238106Sdes key.namelabs = dname_count_size_labels(nm, &key.namelen); 458238106Sdes return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key); 459238106Sdes} 460238106Sdes 461238106Sdesint 462238106Sdesforwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 463238106Sdes{ 464238106Sdes struct iter_forward_zone *z; 465238106Sdes if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) { 466238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 467238106Sdes fwd_zone_free(z); 468238106Sdes } 469238106Sdes if(!forwards_insert(fwd, c, dp)) 470238106Sdes return 0; 471238106Sdes fwd_init_parents(fwd); 472238106Sdes return 1; 473238106Sdes} 474238106Sdes 475238106Sdesvoid 476238106Sdesforwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 477238106Sdes{ 478238106Sdes struct iter_forward_zone *z; 479238106Sdes if(!(z=fwd_zone_find(fwd, c, nm))) 480238106Sdes return; /* nothing to do */ 481238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 482238106Sdes fwd_zone_free(z); 483238106Sdes fwd_init_parents(fwd); 484238106Sdes} 485238106Sdes 486238106Sdesint 487238106Sdesforwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 488238106Sdes{ 489238106Sdes if(!fwd_add_stub_hole(fwd, c, nm)) { 490238106Sdes return 0; 491238106Sdes } 492238106Sdes fwd_init_parents(fwd); 493238106Sdes return 1; 494238106Sdes} 495238106Sdes 496238106Sdesvoid 497238106Sdesforwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 498238106Sdes{ 499238106Sdes struct iter_forward_zone *z; 500238106Sdes if(!(z=fwd_zone_find(fwd, c, nm))) 501238106Sdes return; /* nothing to do */ 502238106Sdes if(z->dp != NULL) 503238106Sdes return; /* not a stub hole */ 504238106Sdes (void)rbtree_delete(fwd->tree, &z->node); 505238106Sdes fwd_zone_free(z); 506238106Sdes fwd_init_parents(fwd); 507238106Sdes} 508238106Sdes 509