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 LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * 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 <ldns/rdata.h>
  44 #include <ldns/dname.h>
  45 #include <ldns/rr.h>
  46 #include "iterator/iter_fwd.h"
  47 #include "iterator/iter_delegpt.h"
  48 #include "util/log.h"
  49 #include "util/config_file.h"
  50 #include "util/net_help.h"
  51 #include "util/data/dname.h"
  52
  53 int
  54 fwd_cmp(const void* k1, const void* k2)
  55 {
  56         int m;
  57         struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1;
  58         struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2;
  59         if(n1->dclass != n2->dclass) {
  60                 if(n1->dclass < n2->dclass)
  61                         return -1;
  62                 return 1;
  63         }
  64         return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs,
  65                 &m);
  66 }
  67
  68 struct iter_forwards*
  69 forwards_create(void)
  70 {
  71         struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
  72                 sizeof(struct iter_forwards));
  73         if(!fwd)
  74                 return NULL;
  75         return fwd;
  76 }
  77
  78 static void fwd_zone_free(struct iter_forward_zone* n)
  79 {
  80         if(!n) return;
  81         delegpt_free_mlc(n->dp);
  82         free(n->name);
  83         free(n);
  84 }
  85
  86 static void delfwdnode(rbnode_t* n, void* ATTR_UNUSED(arg))
  87 {
  88         struct iter_forward_zone* node = (struct iter_forward_zone*)n;
  89         fwd_zone_free(node);
  90 }
  91
  92 static void fwd_del_tree(struct iter_forwards* fwd)
  93 {
  94         if(fwd->tree)
  95                 traverse_postorder(fwd->tree, &delfwdnode, NULL);
  96         free(fwd->tree);
  97 }
  98
  99 void
 100 forwards_delete(struct iter_forwards* fwd)
 101 {
 102         if(!fwd)
 103                 return;
 104         fwd_del_tree(fwd);
 105         free(fwd);
 106 }
 107
 108 /** insert info into forward structure */
 109 static int
 110 forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm,
 111         size_t nmlen, int nmlabs, struct delegpt* dp)
 112 {
 113         struct iter_forward_zone* node = (struct iter_forward_zone*)malloc(
 114                 sizeof(struct iter_forward_zone));
 115         if(!node) {
 116                 delegpt_free_mlc(dp);
 117                 return 0;
 118         }
 119         node->node.key = node;
 120         node->dclass = c;
 121         node->name = memdup(nm, nmlen);
 122         if(!node->name) {
 123                 delegpt_free_mlc(dp);
 124                 free(node);
 125                 return 0;
 126         }
 127         node->namelen = nmlen;
 128         node->namelabs = nmlabs;
 129         node->dp = dp;
 130         if(!rbtree_insert(fwd->tree, &node->node)) {
 131                 char buf[257];
 132                 dname_str(nm, buf);
 133                 log_err("duplicate forward zone %s ignored.", buf);
 134                 delegpt_free_mlc(dp);
 135                 free(node->name);
 136                 free(node);
 137         }
 138         return 1;
 139 }
 140
 141 /** insert new info into forward structure given dp */
 142 static int
 143 forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
 144 {
 145         return forwards_insert_data(fwd, c, dp->name, dp->namelen,
 146                 dp->namelabs, dp);
 147 }
 148
 149 /** initialise parent pointers in the tree */
 150 static void
 151 fwd_init_parents(struct iter_forwards* fwd)
 152 {
 153         struct iter_forward_zone* node, *prev = NULL, *p;
 154         int m;
 155         RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
 156                 node->parent = NULL;
 157                 if(!prev || prev->dclass != node->dclass) {
 158                         prev = node;
 159                         continue;
 160                 }
 161                 (void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
 162                         node->namelabs, &m); /* we know prev is smaller */
 163                 /* sort order like: . com. bla.com. zwb.com. net. */
 164                 /* find the previous, or parent-parent-parent */
 165                 for(p = prev; p; p = p->parent)
 166                         /* looking for name with few labels, a parent */
 167                         if(p->namelabs <= m) {
 168                                 /* ==: since prev matched m, this is closest*/
 169                                 /* <: prev matches more, but is not a parent,
 170                                  * this one is a (grand)parent */
 171                                 node->parent = p;
 172                                 break;
 173                         }
 174                 prev = node;
 175         }
 176 }
 177
 178 /** set zone name */
 179 static struct delegpt*
 180 read_fwds_name(struct config_stub* s)
 181 {
 182         struct delegpt* dp;
 183         ldns_rdf* rdf;
 184         if(!s->name) {
 185                 log_err("forward zone without a name (use name \".\" to forward everything)");
 186                 return NULL;
 187         }
 188         rdf = ldns_dname_new_frm_str(s->name);
 189         if(!rdf) {
 190                 log_err("cannot parse forward zone name %s", s->name);
 191                 return NULL;
 192         }
 193         if(!(dp=delegpt_create_mlc(ldns_rdf_data(rdf)))) {
 194                 ldns_rdf_deep_free(rdf);
 195                 log_err("out of memory");
 196                 return NULL;
 197         }
 198         ldns_rdf_deep_free(rdf);
 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         ldns_rdf* rdf;
 208         for(p = s->hosts; p; p = p->next) {
 209                 log_assert(p->str);
 210                 rdf = ldns_dname_new_frm_str(p->str);
 211                 if(!rdf) {
 212                         log_err("cannot parse forward %s server name: '%s'",
 213                                 s->name, p->str);
 214                         return 0;
 215                 }
 216                 if(!delegpt_add_ns_mlc(dp, ldns_rdf_data(rdf), 0)) {
 217                         ldns_rdf_deep_free(rdf);
 218                         log_err("out of memory");
 219                         return 0;
 220                 }
 221                 ldns_rdf_deep_free(rdf);
 222         }
 223         return 1;
 224 }
 225
 226 /** set fwd server addresses */
 227 static int
 228 read_fwds_addr(struct config_stub* s, struct delegpt* dp)
 229 {
 230         struct config_strlist* p;
 231         struct sockaddr_storage addr;
 232         socklen_t addrlen;
 233         for(p = s->addrs; p; p = p->next) {
 234                 log_assert(p->str);
 235                 if(!extstrtoaddr(p->str, &addr, &addrlen)) {
 236                         log_err("cannot parse forward %s ip address: '%s'",
 237                                 s->name, p->str);
 238                         return 0;
 239                 }
 240                 if(!delegpt_add_addr_mlc(dp, &addr, addrlen, 0, 0)) {
 241                         log_err("out of memory");
 242                         return 0;
 243                 }
 244         }
 245         return 1;
 246 }
 247
 248 /** read forwards config */
 249 static int
 250 read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
 251 {
 252         struct config_stub* s;
 253         for(s = cfg->forwards; s; s = s->next) {
 254                 struct delegpt* dp;
 255                 if(!(dp=read_fwds_name(s)))
 256                         return 0;
 257                 if(!read_fwds_host(s, dp) || !read_fwds_addr(s, dp)) {
 258                         delegpt_free_mlc(dp);
 259                         return 0;
 260                 }
 261                 /* set flag that parent side NS information is included.
 262                  * Asking a (higher up) server on the internet is not useful */
 263                 /* the flag is turned off for 'forward-first' so that the
 264                  * last resort will ask for parent-side NS record and thus
 265                  * fallback to the internet name servers on a failure */
 266                 dp->has_parent_side_NS = (uint8_t)!s->isfirst;
 267                 verbose(VERB_QUERY, "Forward zone server list:");
 268                 delegpt_log(VERB_QUERY, dp);
 269                 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
 270                         return 0;
 271         }
 272         return 1;
 273 }
 274
 275 /** insert a stub hole (if necessary) for stub name */
 276 static int
 277 fwd_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 278 {
 279         struct iter_forward_zone key;
 280         key.node.key = &key;
 281         key.dclass = c;
 282         key.name = nm;
 283         key.namelabs = dname_count_size_labels(key.name, &key.namelen);
 284         return forwards_insert_data(fwd, key.dclass, key.name,
 285                 key.namelen, key.namelabs, NULL);
 286 }
 287
 288 /** make NULL entries for stubs */
 289 static int
 290 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
 291 {
 292         struct config_stub* s;
 293         for(s = cfg->stubs; s; s = s->next) {
 294                 ldns_rdf* rdf = ldns_dname_new_frm_str(s->name);
 295                 if(!rdf) {
 296                         log_err("cannot parse stub name '%s'", s->name);
 297                         return 0;
 298                 }
 299                 if(!fwd_add_stub_hole(fwd, LDNS_RR_CLASS_IN,
 300                                 ldns_rdf_data(rdf))) {
 301                         ldns_rdf_deep_free(rdf);
 302                         log_err("out of memory");
 303                         return 0;
 304                 }
 305                 ldns_rdf_deep_free(rdf);
 306         }
 307         return 1;
 308 }
 309
 310 int
 311 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
 312 {
 313         fwd_del_tree(fwd);
 314         fwd->tree = rbtree_create(fwd_cmp);
 315         if(!fwd->tree)
 316                 return 0;
 317
 318         /* read forward zones */
 319         if(!read_forwards(fwd, cfg))
 320                 return 0;
 321         if(!make_stub_holes(fwd, cfg))
 322                 return 0;
 323         fwd_init_parents(fwd);
 324         return 1;
 325 }
 326
 327 struct delegpt*
 328 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
 329 {
 330         /* lookup the forward zone in the tree */
 331         rbnode_t* res = NULL;
 332         struct iter_forward_zone *result;
 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         if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
 339                 /* exact */
 340                 result = (struct iter_forward_zone*)res;
 341         } else {
 342                 /* smaller element (or no element) */
 343                 int m;
 344                 result = (struct iter_forward_zone*)res;
 345                 if(!result || result->dclass != qclass)
 346                         return NULL;
 347                 /* count number of labels matched */
 348                 (void)dname_lab_cmp(result->name, result->namelabs, key.name,
 349                         key.namelabs, &m);
 350                 while(result) { /* go up until qname is subdomain of stub */
 351                         if(result->namelabs <= m)
 352                                 break;
 353                         result = result->parent;
 354                 }
 355         }
 356         if(result)
 357                 return result->dp;
 358         return NULL;
 359 }
 360
 361 struct delegpt*
 362 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
 363 {
 364         uint8_t root = 0;
 365         return forwards_lookup(fwd, &root, qclass);
 366 }
 367
 368 int
 369 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
 370 {
 371         struct iter_forward_zone key;
 372         rbnode_t* n;
 373         struct iter_forward_zone* p;
 374         if(*dclass == 0) {
 375                 /* first root item is first item in tree */
 376                 n = rbtree_first(fwd->tree);
 377                 if(n == RBTREE_NULL)
 378                         return 0;
 379                 p = (struct iter_forward_zone*)n;
 380                 if(dname_is_root(p->name)) {
 381                         *dclass = p->dclass;
 382                         return 1;
 383                 }
 384                 /* root not first item? search for higher items */
 385                 *dclass = p->dclass + 1;
 386                 return forwards_next_root(fwd, dclass);
 387         }
 388         /* find class n in tree, we may get a direct hit, or if we don't
 389          * this is the last item of the previous class so rbtree_next() takes
 390          * us to the next root (if any) */
 391         key.node.key = &key;
 392         key.name = (uint8_t*)"\000";
 393         key.namelen = 1;
 394         key.namelabs = 0;
 395         key.dclass = *dclass;
 396         n = NULL;
 397         if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
 398                 /* exact */
 399                 return 1;
 400         } else {
 401                 /* smaller element */
 402                 if(!n || n == RBTREE_NULL)
 403                         return 0; /* nothing found */
 404                 n = rbtree_next(n);
 405                 if(n == RBTREE_NULL)
 406                         return 0; /* no higher */
 407                 p = (struct iter_forward_zone*)n;
 408                 if(dname_is_root(p->name)) {
 409                         *dclass = p->dclass;
 410                         return 1;
 411                 }
 412                 /* not a root node, return next higher item */
 413                 *dclass = p->dclass+1;
 414                 return forwards_next_root(fwd, dclass);
 415         }
 416 }
 417
 418 size_t
 419 forwards_get_mem(struct iter_forwards* fwd)
 420 {
 421         struct iter_forward_zone* p;
 422         size_t s;
 423         if(!fwd)
 424                 return 0;
 425         s = sizeof(*fwd) + sizeof(*fwd->tree);
 426         RBTREE_FOR(p, struct iter_forward_zone*, fwd->tree) {
 427                 s += sizeof(*p) + p->namelen + delegpt_get_mem(p->dp);
 428         }
 429         return s;
 430 }
 431
 432 static struct iter_forward_zone*
 433 fwd_zone_find(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 434 {
 435         struct iter_forward_zone key;
 436         key.node.key = &key;
 437         key.dclass = c;
 438         key.name = nm;
 439         key.namelabs = dname_count_size_labels(nm, &key.namelen);
 440         return (struct iter_forward_zone*)rbtree_search(fwd->tree, &key);
 441 }
 442
 443 int
 444 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
 445 {
 446         struct iter_forward_zone *z;
 447         if((z=fwd_zone_find(fwd, c, dp->name)) != NULL) {
 448                 (void)rbtree_delete(fwd->tree, &z->node);
 449                 fwd_zone_free(z);
 450         }
 451         if(!forwards_insert(fwd, c, dp))
 452                 return 0;
 453         fwd_init_parents(fwd);
 454         return 1;
 455 }
 456
 457 void
 458 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 459 {
 460         struct iter_forward_zone *z;
 461         if(!(z=fwd_zone_find(fwd, c, nm)))
 462                 return; /* nothing to do */
 463         (void)rbtree_delete(fwd->tree, &z->node);
 464         fwd_zone_free(z);
 465         fwd_init_parents(fwd);
 466 }
 467
 468 int
 469 forwards_add_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 470 {
 471         if(!fwd_add_stub_hole(fwd, c, nm)) {
 472                 return 0;
 473         }
 474         fwd_init_parents(fwd);
 475         return 1;
 476 }
 477
 478 void
 479 forwards_delete_stub_hole(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
 480 {
 481         struct iter_forward_zone *z;
 482         if(!(z=fwd_zone_find(fwd, c, nm)))
 483                 return; /* nothing to do */
 484         if(z->dp != NULL)
 485                 return; /* not a stub hole */
 486         (void)rbtree_delete(fwd->tree, &z->node);
 487         fwd_zone_free(z);
 488         fwd_init_parents(fwd);
 489 }
 490