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/regional.h" 49 #include "util/log.h" 50 #include "util/config_file.h" 51 #include "util/net_help.h" 52 #include "util/data/dname.h" 53 54 int 55 fwd_cmp(const void* k1, const void* k2) 56 { 57 int m; 58 struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1; 59 struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2; 60 if(n1->dclass != n2->dclass) { 61 if(n1->dclass < n2->dclass) 62 return -1; 63 return 1; 64 } 65 return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 66 &m); 67 } 68 69 struct iter_forwards* 70 forwards_create(void) 71 { 72 struct iter_forwards* fwd = (struct iter_forwards*)calloc(1, 73 sizeof(struct iter_forwards)); 74 if(!fwd) 75 return NULL; 76 fwd->region = regional_create(); 77 if(!fwd->region) { 78 forwards_delete(fwd); 79 return NULL; 80 } 81 return fwd; 82 } 83 84 void 85 forwards_delete(struct iter_forwards* fwd) 86 { 87 if(!fwd) 88 return; 89 regional_destroy(fwd->region); 90 free(fwd->tree); 91 free(fwd); 92 } 93 94 /** insert info into forward structure */ 95 static int 96 forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 97 size_t nmlen, int nmlabs, struct delegpt* dp) 98 { 99 struct iter_forward_zone* node = regional_alloc(fwd->region, 100 sizeof(struct iter_forward_zone)); 101 if(!node) 102 return 0; 103 node->node.key = node; 104 node->dclass = c; 105 node->name = regional_alloc_init(fwd->region, nm, nmlen); 106 if(!node->name) 107 return 0; 108 node->namelen = nmlen; 109 node->namelabs = nmlabs; 110 node->dp = dp; 111 if(!rbtree_insert(fwd->tree, &node->node)) { 112 log_err("duplicate forward zone ignored."); 113 } 114 return 1; 115 } 116 117 /** insert new info into forward structure given dp */ 118 static int 119 forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 120 { 121 return forwards_insert_data(fwd, c, dp->name, dp->namelen, 122 dp->namelabs, dp); 123 } 124 125 /** initialise parent pointers in the tree */ 126 static void 127 fwd_init_parents(struct iter_forwards* fwd) 128 { 129 struct iter_forward_zone* node, *prev = NULL, *p; 130 int m; 131 RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) { 132 node->parent = NULL; 133 if(!prev || prev->dclass != node->dclass) { 134 prev = node; 135 continue; 136 } 137 (void)dname_lab_cmp(prev->name, prev->namelabs, node->name, 138 node->namelabs, &m); /* we know prev is smaller */ 139 /* sort order like: . com. bla.com. zwb.com. net. */ 140 /* find the previous, or parent-parent-parent */ 141 for(p = prev; p; p = p->parent) 142 /* looking for name with few labels, a parent */ 143 if(p->namelabs <= m) { 144 /* ==: since prev matched m, this is closest*/ 145 /* <: prev matches more, but is not a parent, 146 * this one is a (grand)parent */ 147 node->parent = p; 148 break; 149 } 150 prev = node; 151 } 152 } 153 154 /** set zone name */ 155 static int 156 read_fwds_name(struct iter_forwards* fwd, struct config_stub* s, 157 struct delegpt* dp) 158 { 159 ldns_rdf* rdf; 160 if(!s->name) { 161 log_err("forward zone without a name (use name \".\" to forward everything)"); 162 return 0; 163 } 164 rdf = ldns_dname_new_frm_str(s->name); 165 if(!rdf) { 166 log_err("cannot parse forward zone name %s", s->name); 167 return 0; 168 } 169 if(!delegpt_set_name(dp, fwd->region, ldns_rdf_data(rdf))) { 170 ldns_rdf_deep_free(rdf); 171 log_err("out of memory"); 172 return 0; 173 } 174 ldns_rdf_deep_free(rdf); 175 return 1; 176 } 177 178 /** set fwd host names */ 179 static int 180 read_fwds_host(struct iter_forwards* fwd, struct config_stub* s, 181 struct delegpt* dp) 182 { 183 struct config_strlist* p; 184 ldns_rdf* rdf; 185 for(p = s->hosts; p; p = p->next) { 186 log_assert(p->str); 187 rdf = ldns_dname_new_frm_str(p->str); 188 if(!rdf) { 189 log_err("cannot parse forward %s server name: '%s'", 190 s->name, p->str); 191 return 0; 192 } 193 if(!delegpt_add_ns(dp, fwd->region, ldns_rdf_data(rdf), 0)) { 194 ldns_rdf_deep_free(rdf); 195 log_err("out of memory"); 196 return 0; 197 } 198 ldns_rdf_deep_free(rdf); 199 } 200 return 1; 201 } 202 203 /** set fwd server addresses */ 204 static int 205 read_fwds_addr(struct iter_forwards* fwd, struct config_stub* s, 206 struct delegpt* dp) 207 { 208 struct config_strlist* p; 209 struct sockaddr_storage addr; 210 socklen_t addrlen; 211 for(p = s->addrs; p; p = p->next) { 212 log_assert(p->str); 213 if(!extstrtoaddr(p->str, &addr, &addrlen)) { 214 log_err("cannot parse forward %s ip address: '%s'", 215 s->name, p->str); 216 return 0; 217 } 218 if(!delegpt_add_addr(dp, fwd->region, &addr, addrlen, 0, 0)) { 219 log_err("out of memory"); 220 return 0; 221 } 222 } 223 return 1; 224 } 225 226 /** read forwards config */ 227 static int 228 read_forwards(struct iter_forwards* fwd, struct config_file* cfg) 229 { 230 struct config_stub* s; 231 for(s = cfg->forwards; s; s = s->next) { 232 struct delegpt* dp = delegpt_create(fwd->region); 233 if(!dp) { 234 log_err("out of memory"); 235 return 0; 236 } 237 /* set flag that parent side NS information is included. 238 * Asking a (higher up) server on the internet is not useful */ 239 dp->has_parent_side_NS = 1; 240 if(!read_fwds_name(fwd, s, dp) || 241 !read_fwds_host(fwd, s, dp) || 242 !read_fwds_addr(fwd, s, dp)) 243 return 0; 244 if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp)) 245 return 0; 246 verbose(VERB_QUERY, "Forward zone server list:"); 247 delegpt_log(VERB_QUERY, dp); 248 } 249 return 1; 250 } 251 252 /** see if zone needs to have a hole inserted */ 253 static int 254 need_hole_insert(rbtree_t* tree, struct iter_forward_zone* zone) 255 { 256 struct iter_forward_zone k; 257 if(rbtree_search(tree, zone)) 258 return 0; /* exact match exists */ 259 k = *zone; 260 k.node.key = &k; 261 /* search up the tree */ 262 do { 263 dname_remove_label(&k.name, &k.namelen); 264 k.namelabs --; 265 if(rbtree_search(tree, &k)) 266 return 1; /* found an upper forward zone, need hole */ 267 } while(k.namelabs > 1); 268 return 0; /* no forwards above, no holes needed */ 269 } 270 271 /** make NULL entries for stubs */ 272 static int 273 make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg) 274 { 275 struct config_stub* s; 276 struct iter_forward_zone key; 277 key.node.key = &key; 278 key.dclass = LDNS_RR_CLASS_IN; 279 for(s = cfg->stubs; s; s = s->next) { 280 ldns_rdf* rdf = ldns_dname_new_frm_str(s->name); 281 if(!rdf) { 282 log_err("cannot parse stub name '%s'", s->name); 283 return 0; 284 } 285 key.name = ldns_rdf_data(rdf); 286 key.namelabs = dname_count_size_labels(key.name, &key.namelen); 287 if(!need_hole_insert(fwd->tree, &key)) { 288 ldns_rdf_deep_free(rdf); 289 continue; 290 } 291 if(!forwards_insert_data(fwd, key.dclass, key.name, 292 key.namelen, key.namelabs, NULL)) { 293 ldns_rdf_deep_free(rdf); 294 log_err("out of memory"); 295 return 0; 296 } 297 ldns_rdf_deep_free(rdf); 298 } 299 return 1; 300 } 301 302 int 303 forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg) 304 { 305 free(fwd->tree); 306 regional_free_all(fwd->region); 307 fwd->tree = rbtree_create(fwd_cmp); 308 if(!fwd->tree) 309 return 0; 310 311 /* read forward zones */ 312 if(!read_forwards(fwd, cfg)) 313 return 0; 314 if(!make_stub_holes(fwd, cfg)) 315 return 0; 316 fwd_init_parents(fwd); 317 return 1; 318 } 319 320 struct delegpt* 321 forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass) 322 { 323 /* lookup the forward zone in the tree */ 324 rbnode_t* res = NULL; 325 struct iter_forward_zone *result; 326 struct iter_forward_zone key; 327 key.node.key = &key; 328 key.dclass = qclass; 329 key.name = qname; 330 key.namelabs = dname_count_size_labels(qname, &key.namelen); 331 if(rbtree_find_less_equal(fwd->tree, &key, &res)) { 332 /* exact */ 333 result = (struct iter_forward_zone*)res; 334 } else { 335 /* smaller element (or no element) */ 336 int m; 337 result = (struct iter_forward_zone*)res; 338 if(!result || result->dclass != qclass) 339 return NULL; 340 /* count number of labels matched */ 341 (void)dname_lab_cmp(result->name, result->namelabs, key.name, 342 key.namelabs, &m); 343 while(result) { /* go up until qname is subdomain of stub */ 344 if(result->namelabs <= m) 345 break; 346 result = result->parent; 347 } 348 } 349 if(result) 350 return result->dp; 351 return NULL; 352 } 353 354 struct delegpt* 355 forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass) 356 { 357 uint8_t root = 0; 358 return forwards_lookup(fwd, &root, qclass); 359 } 360 361 int 362 forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass) 363 { 364 struct iter_forward_zone key; 365 rbnode_t* n; 366 struct iter_forward_zone* p; 367 if(*dclass == 0) { 368 /* first root item is first item in tree */ 369 n = rbtree_first(fwd->tree); 370 if(n == RBTREE_NULL) 371 return 0; 372 p = (struct iter_forward_zone*)n; 373 if(dname_is_root(p->name)) { 374 *dclass = p->dclass; 375 return 1; 376 } 377 /* root not first item? search for higher items */ 378 *dclass = p->dclass + 1; 379 return forwards_next_root(fwd, dclass); 380 } 381 /* find class n in tree, we may get a direct hit, or if we don't 382 * this is the last item of the previous class so rbtree_next() takes 383 * us to the next root (if any) */ 384 key.node.key = &key; 385 key.name = (uint8_t*)"\000"; 386 key.namelen = 1; 387 key.namelabs = 0; 388 key.dclass = *dclass; 389 n = NULL; 390 if(rbtree_find_less_equal(fwd->tree, &key, &n)) { 391 /* exact */ 392 return 1; 393 } else { 394 /* smaller element */ 395 if(!n || n == RBTREE_NULL) 396 return 0; /* nothing found */ 397 n = rbtree_next(n); 398 if(n == RBTREE_NULL) 399 return 0; /* no higher */ 400 p = (struct iter_forward_zone*)n; 401 if(dname_is_root(p->name)) { 402 *dclass = p->dclass; 403 return 1; 404 } 405 /* not a root node, return next higher item */ 406 *dclass = p->dclass+1; 407 return forwards_next_root(fwd, dclass); 408 } 409 } 410 411 size_t 412 forwards_get_mem(struct iter_forwards* fwd) 413 { 414 if(!fwd) 415 return 0; 416 return sizeof(*fwd) + sizeof(*fwd->tree) + 417 regional_get_mem(fwd->region); 418 } 419 420 int 421 forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp) 422 { 423 if(!forwards_insert(fwd, c, dp)) 424 return 0; 425 fwd_init_parents(fwd); 426 return 1; 427 } 428 429 void 430 forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm) 431 { 432 struct iter_forward_zone key; 433 key.node.key = &key; 434 key.dclass = c; 435 key.name = nm; 436 key.namelabs = dname_count_size_labels(nm, &key.namelen); 437 if(!rbtree_search(fwd->tree, &key)) 438 return; /* nothing to do */ 439 (void)rbtree_delete(fwd->tree, &key); 440 fwd_init_parents(fwd); 441 } 442 443