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 "ldns/rrdef.h"
  50 #include "ldns/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                 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
 312 int
 313 forwards_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
 329 struct delegpt*
 330 forwards_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
 343 struct delegpt*
 344 forwards_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
 377 struct delegpt*
 378 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
 379 {
 380         uint8_t root = 0;
 381         return forwards_lookup(fwd, &root, qclass);
 382 }
 383
 384 int
 385 forwards_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
 434 size_t
 435 forwards_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
 448 static struct iter_forward_zone*
 449 fwd_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
 459 int
 460 forwards_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
 473 void
 474 forwards_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
 484 int
 485 forwards_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
 494 void
 495 forwards_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