contrib/unbound/iterator/iter_fwd.c

   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
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE 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 "iterator/iter_fwd.h"
  44 #include "iterator/iter_delegpt.h"
  45 #include "util/log.h"
  46 #include "util/config_file.h"
  47 #include "util/net_help.h"
  48 #include "util/data/dname.h"
  49 #include "sldns/rrdef.h"
  50 #include "sldns/str2wire.h"
  51
  52 int
  53 fwd_cmp(const void* k1, const void* k2)
  54 {
  55         int m;
  56         struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1;
  57         struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2;
  58         if(n1->dclass != n2->dclass) {
  59                 if(n1->dclass < n2->dclass)
  60                         return -1;
  61                 return 1;
  62         }
  63         return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs,
  64                 &m);
  65 }
  66
  67 struct iter_forwards*
  68 forwards_create(void)
  69 {
  70         struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
  71                 sizeof(struct iter_forwards));
  72         if(!fwd)
  73                 return NULL;
  74         return fwd;
  75 }
  76
  77 static void fwd_zone_free(struct iter_forward_zone* n)
  78 {
  79         if(!n) return;
  80         delegpt_free_mlc(n->dp);
  81         free(n->name);
  82         free(n);
  83 }
  84
  85 static void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg))
  86 {
  87         struct iter_forward_zone* node = (struct iter_forward_zone*)n;
  88         fwd_zone_free(node);
  89 }
  90
  91 static void fwd_del_tree(struct iter_forwards* fwd)
  92 {
  93         if(fwd->tree)
  94                 traverse_postorder(fwd->tree, &delfwdnode, NULL);
  95         free(fwd->tree);
  96 }
  97
  98 void
  99 forwards_delete(struct iter_forwards* fwd)
 100 {
 101         if(!fwd)
 102                 return;
 103         fwd_del_tree(fwd);
 104         free(fwd);
 105 }
 106
 107 /** insert info into forward structure */
 108 static int
 109 forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
 110         size_t nmlen, int nmlabs, struct delegpt* dp)
 111 {
 112         struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
 113                 sizeof(struct iter_forward_zone));
 114         if(!node) {
 115                 delegpt_free_mlc(dp);
 116                 return 0;
 117         }
 118         node->node.key = node;
 119         node->dclass = c;
 120         node->name = memdup(nm, nmlen);
 121         if(!node->name) {
 122                 delegpt_free_mlc(dp);
 123                 free(node);
 124                 return 0;
 125         }
 126         node->namelen = nmlen;
 127         node->namelabs = nmlabs;
 128         node->dp = dp;
 129         if(!rbtree_insert(fwd->tree, &node->node)) {
 130                 char buf[257];
 131                 dname_str(nm, buf);
 132                 log_err("duplicate forward zone %s ignored.", buf);
 133                 delegpt_free_mlc(dp);
 134                 free(node->name);
 135                 free(node);
 136         }
 137         return 1;
 138 }
 139
 140 /** insert new info into forward structure given dp */
 141 static int
 142 forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
 143 {
 144         return forwards_insert_data(fwd, c, dp->name, dp->namelen,
 145                 dp->namelabs, dp);
 146 }
 147
 148 /** initialise parent pointers in the tree */
 149 static void
 150 fwd_init_parents(struct iter_forwards* fwd)
 151 {
 152         struct iter_forward_zone* node, *prev = NULL, *p;
 153         int m;
 154         RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
 155                 node->parent = NULL;
 156                 if(!prev || prev->dclass != node->dclass) {
 157                         prev = node;
 158                         continue;
 159                 }
 160                 (void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
 161                         node->namelabs, &m); /* we know prev is smaller */
 162                 /* sort order like: . com. bla.com. zwb.com. net. */
 163                 /* find the previous, or parent-parent-parent */
 164                 for(p = prev; p; p = p->parent)
 165                         /* 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 */
 178 static struct delegpt*
 179 read_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 */
 203 static int
 204 read_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 */
 228 static int
 229 read_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 */
 250 static int
 251 read_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 */
 277 static int
 278 fwd_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 */
 290 static int
 291 make_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                 if(!s->name) continue;
 298                 dname = sldns_str2wire_dname(s->name, &dname_len);
 299                 if(!dname) {
 300                         log_err("cannot parse stub name '%s'", s->name);
 301                         return 0;
 302                 }
 303                 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN, dname)) {
 304                         free(dname);
 305                         log_err("out of memory");
 306                         return 0;
 307                 }
 308                 free(dname);
 309         }
 310         return 1;
 311 }
 312
 313 int
 314 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
 315 {
 316         fwd_del_tree(fwd);
 317         fwd->tree = rbtree_create(fwd_cmp);
 318         if(!fwd->tree)
 319                 return 0;
 320
 321         /* read forward zones */
 322         if(!read_forwards(fwd, cfg))
 323                 return 0;
 324         if(!make_stub_holes(fwd, cfg))
 325                 return 0;
 326         fwd_init_parents(fwd);
 327         return 1;
 328 }
 329
 330 struct delegpt*
 331 forwards_find(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
 332 {
 333         rbnode_t* res = NULL;
 334         struct iter_forward_zone key;
 335         key.node.key = &key;
 336         key.dclass = qclass;
 337         key.name = qname;
 338         key.namelabs = dname_count_size_labels(qname, &key.namelen);
 339         res = rbtree_search(fwd->tree, &key);
 340         if(res) return ((struct iter_forward_zone*)res)->dp;
 341         return NULL;
 342 }
 343
 344 struct delegpt*
 345 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
 346 {
 347         /* lookup the forward zone in the tree */
 348         rbnode_t* res = NULL;
 349         struct iter_forward_zone *result;
 350         struct iter_forward_zone key;
 351         key.node.key = &key;
 352         key.dclass = qclass;
 353         key.name = qname;
 354         key.namelabs = dname_count_size_labels(qname, &key.namelen);
 355         if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
 356                 /* exact */
 357                 result = (struct iter_forward_zone*)res;
 358         } else {
 359                 /* smaller element (or no element) */
 360                 int m;
 361                 result = (struct iter_forward_zone*)res;
 362                 if(!result || result->dclass != qclass)
 363                         return NULL;
 364                 /* count number of labels matched */
 365                 (void)dname_lab_cmp(result->name, result->namelabs, key.name,
 366                         key.namelabs, &m);
 367                 while(result) { /* go up until qname is subdomain of stub */
 368                         if(result->namelabs <= m)
 369                                 break;
 370                         result = result->parent;
 371                 }
 372         }
 373         if(result)
 374                 return result->dp;
 375         return NULL;
 376 }
 377
 378 struct delegpt*
 379 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
 380 {
 381         uint8_t root = 0;
 382         return forwards_lookup(fwd, &root, qclass);
 383 }
 384
 385 int
 386 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
 387 {
 388         struct iter_forward_zone key;
 389         rbnode_t* n;
 390         struct iter_forward_zone* p;
 391         if(*dclass == 0) {
 392                 /* first root item is first item in tree */
 393                 n = rbtree_first(fwd->tree);
 394                 if(n == RBTREE_NULL)
 395                         return 0;
 396                 p = (struct iter_forward_zone*)n;
 397                 if(dname_is_root(p->name)) {
 398                         *dclass = p->dclass;
 399                         return 1;
 400                 }
 401                 /* root not first item? search for higher items */
 402                 *dclass = p->dclass + 1;
 403                 return forwards_next_root(fwd, dclass);
 404         }
 405         /* find class n in tree, we may get a direct hit, or if we don't
 406          * this is the last item of the previous class so rbtree_next() takes
 407          * us to the next root (if any) */
 408         key.node.key = &key;
 409         key.name = (uint8_t*)"\000";
 410         key.namelen = 1;
 411         key.namelabs = 0;
 412         key.dclass = *dclass;
 413         n = NULL;
 414         if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
 415                 /* exact */
 416                 return 1;
 417         } else {
 418                 /* smaller element */
 419                 if(!n || n == RBTREE_NULL)
 420                         return 0; /* nothing found */
 421                 n = rbtree_next(n);
 422                 if(n == RBTREE_NULL)
 423                         return 0; /* no higher */
 424                 p = (struct iter_forward_zone*)n;
 425                 if(dname_is_root(p->name)) {
 426                         *dclass = p->dclass;
 427                         return 1;
 428                 }
 429                 /* not a root node, return next higher item */
 430                 *dclass = p->dclass+1;
 431                 return forwards_next_root(fwd, dclass);
 432         }
 433 }
 434
 435 size_t
 436 forwards_get_mem(struct iter_forwards* fwd)
 437 {
 438         struct iter_forward_zone* p;
 439         size_t s;
 440         if(!fwd)
 441                 return 0;
 442         s = sizeof(*fwd) + sizeof(*fwd->tree);
 443         RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
 444                 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
 445         }
 446         return s;
 447 }
 448
 449 static struct iter_forward_zone*
 450 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 451 {
 452         struct iter_forward_zone key;
 453         key.node.key = &key;
 454         key.dclass = c;
 455         key.name = nm;
 456         key.namelabs = dname_count_size_labels(nm, &key.namelen);
 457         return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
 458 }
 459
 460 int
 461 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
 462 {
 463         struct iter_forward_zone *z;
 464         if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
 465                 (void)rbtree_delete(fwd->tree, &z->node);
 466                 fwd_zone_free(z);
 467         }
 468         if(!forwards_insert(fwd, c, dp))
 469                 return 0;
 470         fwd_init_parents(fwd);
 471         return 1;
 472 }
 473
 474 void
 475 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 476 {
 477         struct iter_forward_zone *z;
 478         if(!(z=fwd_zone_find(fwd, c, nm)))
 479                 return; /* nothing to do */
 480         (void)rbtree_delete(fwd->tree, &z->node);
 481         fwd_zone_free(z);
 482         fwd_init_parents(fwd);
 483 }
 484
 485 int
 486 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 487 {
 488         if(!fwd_add_stub_hole(fwd, c, nm)) {
 489                 return 0;
 490         }
 491         fwd_init_parents(fwd);
 492         return 1;
 493 }
 494
 495 void
 496 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 497 {
 498         struct iter_forward_zone *z;
 499         if(!(z=fwd_zone_find(fwd, c, nm)))
 500                 return; /* nothing to do */
 501         if(z->dp != NULL)
 502                 return; /* not a stub hole */
 503         (void)rbtree_delete(fwd->tree, &z->node);
 504         fwd_zone_free(z);
 505         fwd_init_parents(fwd);
 506 }
 507