1 /* 2 * validator/val_neg.c - validator aggressive negative caching functions. 3 * 4 * Copyright (c) 2008, 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 helper functions for the validator module. 40 * The functions help with aggressive negative caching. 41 * This creates new denials of existence, and proofs for absence of types 42 * from cached NSEC records. 43 */ 44 #include "config.h" 45 #ifdef HAVE_OPENSSL_SSL_H 46 #include "openssl/ssl.h" 47 #define NSEC3_SHA_LEN SHA_DIGEST_LENGTH 48 #else 49 #define NSEC3_SHA_LEN 20 50 #endif 51 #include "validator/val_neg.h" 52 #include "validator/val_nsec.h" 53 #include "validator/val_nsec3.h" 54 #include "validator/val_utils.h" 55 #include "util/data/dname.h" 56 #include "util/data/msgreply.h" 57 #include "util/log.h" 58 #include "util/net_help.h" 59 #include "util/config_file.h" 60 #include "services/cache/rrset.h" 61 #include "services/cache/dns.h" 62 #include "sldns/rrdef.h" 63 #include "sldns/sbuffer.h" 64 65 int val_neg_data_compare(const void* a, const void* b) 66 { 67 struct val_neg_data* x = (struct val_neg_data*)a; 68 struct val_neg_data* y = (struct val_neg_data*)b; 69 int m; 70 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 71 } 72 73 int val_neg_zone_compare(const void* a, const void* b) 74 { 75 struct val_neg_zone* x = (struct val_neg_zone*)a; 76 struct val_neg_zone* y = (struct val_neg_zone*)b; 77 int m; 78 if(x->dclass != y->dclass) { 79 if(x->dclass < y->dclass) 80 return -1; 81 return 1; 82 } 83 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 84 } 85 86 struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter) 87 { 88 struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1, 89 sizeof(*neg)); 90 if(!neg) { 91 log_err("Could not create neg cache: out of memory"); 92 return NULL; 93 } 94 neg->nsec3_max_iter = maxiter; 95 neg->max = 1024*1024; /* 1 M is thousands of entries */ 96 if(cfg) neg->max = cfg->neg_cache_size; 97 rbtree_init(&neg->tree, &val_neg_zone_compare); 98 lock_basic_init(&neg->lock); 99 lock_protect(&neg->lock, neg, sizeof(*neg)); 100 return neg; 101 } 102 103 size_t val_neg_get_mem(struct val_neg_cache* neg) 104 { 105 size_t result; 106 lock_basic_lock(&neg->lock); 107 result = sizeof(*neg) + neg->use; 108 lock_basic_unlock(&neg->lock); 109 return result; 110 } 111 112 /** clear datas on cache deletion */ 113 static void 114 neg_clear_datas(rbnode_t* n, void* ATTR_UNUSED(arg)) 115 { 116 struct val_neg_data* d = (struct val_neg_data*)n; 117 free(d->name); 118 free(d); 119 } 120 121 /** clear zones on cache deletion */ 122 static void 123 neg_clear_zones(rbnode_t* n, void* ATTR_UNUSED(arg)) 124 { 125 struct val_neg_zone* z = (struct val_neg_zone*)n; 126 /* delete all the rrset entries in the tree */ 127 traverse_postorder(&z->tree, &neg_clear_datas, NULL); 128 free(z->nsec3_salt); 129 free(z->name); 130 free(z); 131 } 132 133 void neg_cache_delete(struct val_neg_cache* neg) 134 { 135 if(!neg) return; 136 lock_basic_destroy(&neg->lock); 137 /* delete all the zones in the tree */ 138 traverse_postorder(&neg->tree, &neg_clear_zones, NULL); 139 free(neg); 140 } 141 142 /** 143 * Put data element at the front of the LRU list. 144 * @param neg: negative cache with LRU start and end. 145 * @param data: this data is fronted. 146 */ 147 static void neg_lru_front(struct val_neg_cache* neg, 148 struct val_neg_data* data) 149 { 150 data->prev = NULL; 151 data->next = neg->first; 152 if(!neg->first) 153 neg->last = data; 154 else neg->first->prev = data; 155 neg->first = data; 156 } 157 158 /** 159 * Remove data element from LRU list. 160 * @param neg: negative cache with LRU start and end. 161 * @param data: this data is removed from the list. 162 */ 163 static void neg_lru_remove(struct val_neg_cache* neg, 164 struct val_neg_data* data) 165 { 166 if(data->prev) 167 data->prev->next = data->next; 168 else neg->first = data->next; 169 if(data->next) 170 data->next->prev = data->prev; 171 else neg->last = data->prev; 172 } 173 174 /** 175 * Touch LRU for data element, put it at the start of the LRU list. 176 * @param neg: negative cache with LRU start and end. 177 * @param data: this data is used. 178 */ 179 static void neg_lru_touch(struct val_neg_cache* neg, 180 struct val_neg_data* data) 181 { 182 if(data == neg->first) 183 return; /* nothing to do */ 184 /* remove from current lru position */ 185 neg_lru_remove(neg, data); 186 /* add at front */ 187 neg_lru_front(neg, data); 188 } 189 190 /** 191 * Delete a zone element from the negative cache. 192 * May delete other zone elements to keep tree coherent, or 193 * only mark the element as 'not in use'. 194 * @param neg: negative cache. 195 * @param z: zone element to delete. 196 */ 197 static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z) 198 { 199 struct val_neg_zone* p, *np; 200 if(!z) return; 201 log_assert(z->in_use); 202 log_assert(z->count > 0); 203 z->in_use = 0; 204 205 /* go up the tree and reduce counts */ 206 p = z; 207 while(p) { 208 log_assert(p->count > 0); 209 p->count --; 210 p = p->parent; 211 } 212 213 /* remove zones with zero count */ 214 p = z; 215 while(p && p->count == 0) { 216 np = p->parent; 217 (void)rbtree_delete(&neg->tree, &p->node); 218 neg->use -= p->len + sizeof(*p); 219 free(p->nsec3_salt); 220 free(p->name); 221 free(p); 222 p = np; 223 } 224 } 225 226 void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el) 227 { 228 struct val_neg_zone* z; 229 struct val_neg_data* p, *np; 230 if(!el) return; 231 z = el->zone; 232 log_assert(el->in_use); 233 log_assert(el->count > 0); 234 el->in_use = 0; 235 236 /* remove it from the lru list */ 237 neg_lru_remove(neg, el); 238 239 /* go up the tree and reduce counts */ 240 p = el; 241 while(p) { 242 log_assert(p->count > 0); 243 p->count --; 244 p = p->parent; 245 } 246 247 /* delete 0 count items from tree */ 248 p = el; 249 while(p && p->count == 0) { 250 np = p->parent; 251 (void)rbtree_delete(&z->tree, &p->node); 252 neg->use -= p->len + sizeof(*p); 253 free(p->name); 254 free(p); 255 p = np; 256 } 257 258 /* check if the zone is now unused */ 259 if(z->tree.count == 0) { 260 neg_delete_zone(neg, z); 261 } 262 } 263 264 /** 265 * Create more space in negative cache 266 * The oldest elements are deleted until enough space is present. 267 * Empty zones are deleted. 268 * @param neg: negative cache. 269 * @param need: how many bytes are needed. 270 */ 271 static void neg_make_space(struct val_neg_cache* neg, size_t need) 272 { 273 /* delete elements until enough space or its empty */ 274 while(neg->last && neg->max < neg->use + need) { 275 neg_delete_data(neg, neg->last); 276 } 277 } 278 279 struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 280 uint8_t* nm, size_t len, uint16_t dclass) 281 { 282 struct val_neg_zone lookfor; 283 struct val_neg_zone* result; 284 lookfor.node.key = &lookfor; 285 lookfor.name = nm; 286 lookfor.len = len; 287 lookfor.labs = dname_count_labels(lookfor.name); 288 lookfor.dclass = dclass; 289 290 result = (struct val_neg_zone*) 291 rbtree_search(&neg->tree, lookfor.node.key); 292 return result; 293 } 294 295 /** 296 * Find the given data 297 * @param zone: negative zone 298 * @param nm: what to look for. 299 * @param len: length of nm 300 * @param labs: labels in nm 301 * @return data or NULL if not found. 302 */ 303 static struct val_neg_data* neg_find_data(struct val_neg_zone* zone, 304 uint8_t* nm, size_t len, int labs) 305 { 306 struct val_neg_data lookfor; 307 struct val_neg_data* result; 308 lookfor.node.key = &lookfor; 309 lookfor.name = nm; 310 lookfor.len = len; 311 lookfor.labs = labs; 312 313 result = (struct val_neg_data*) 314 rbtree_search(&zone->tree, lookfor.node.key); 315 return result; 316 } 317 318 /** 319 * Calculate space needed for the data and all its parents 320 * @param rep: NSEC entries. 321 * @return size. 322 */ 323 static size_t calc_data_need(struct reply_info* rep) 324 { 325 uint8_t* d; 326 size_t i, len, res = 0; 327 328 for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) { 329 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 330 d = rep->rrsets[i]->rk.dname; 331 len = rep->rrsets[i]->rk.dname_len; 332 res = sizeof(struct val_neg_data) + len; 333 while(!dname_is_root(d)) { 334 log_assert(len > 1); /* not root label */ 335 dname_remove_label(&d, &len); 336 res += sizeof(struct val_neg_data) + len; 337 } 338 } 339 } 340 return res; 341 } 342 343 /** 344 * Calculate space needed for zone and all its parents 345 * @param d: name of zone 346 * @param len: length of name 347 * @return size. 348 */ 349 static size_t calc_zone_need(uint8_t* d, size_t len) 350 { 351 size_t res = sizeof(struct val_neg_zone) + len; 352 while(!dname_is_root(d)) { 353 log_assert(len > 1); /* not root label */ 354 dname_remove_label(&d, &len); 355 res += sizeof(struct val_neg_zone) + len; 356 } 357 return res; 358 } 359 360 /** 361 * Find closest existing parent zone of the given name. 362 * @param neg: negative cache. 363 * @param nm: name to look for 364 * @param nm_len: length of nm 365 * @param labs: labelcount of nm. 366 * @param qclass: class. 367 * @return the zone or NULL if none found. 368 */ 369 static struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg, 370 uint8_t* nm, size_t nm_len, int labs, uint16_t qclass) 371 { 372 struct val_neg_zone key; 373 struct val_neg_zone* result; 374 rbnode_t* res = NULL; 375 key.node.key = &key; 376 key.name = nm; 377 key.len = nm_len; 378 key.labs = labs; 379 key.dclass = qclass; 380 if(rbtree_find_less_equal(&neg->tree, &key, &res)) { 381 /* exact match */ 382 result = (struct val_neg_zone*)res; 383 } else { 384 /* smaller element (or no element) */ 385 int m; 386 result = (struct val_neg_zone*)res; 387 if(!result || result->dclass != qclass) 388 return NULL; 389 /* count number of labels matched */ 390 (void)dname_lab_cmp(result->name, result->labs, key.name, 391 key.labs, &m); 392 while(result) { /* go up until qname is subdomain of stub */ 393 if(result->labs <= m) 394 break; 395 result = result->parent; 396 } 397 } 398 return result; 399 } 400 401 /** 402 * Find closest existing parent data for the given name. 403 * @param zone: to look in. 404 * @param nm: name to look for 405 * @param nm_len: length of nm 406 * @param labs: labelcount of nm. 407 * @return the data or NULL if none found. 408 */ 409 static struct val_neg_data* neg_closest_data_parent( 410 struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs) 411 { 412 struct val_neg_data key; 413 struct val_neg_data* result; 414 rbnode_t* res = NULL; 415 key.node.key = &key; 416 key.name = nm; 417 key.len = nm_len; 418 key.labs = labs; 419 if(rbtree_find_less_equal(&zone->tree, &key, &res)) { 420 /* exact match */ 421 result = (struct val_neg_data*)res; 422 } else { 423 /* smaller element (or no element) */ 424 int m; 425 result = (struct val_neg_data*)res; 426 if(!result) 427 return NULL; 428 /* count number of labels matched */ 429 (void)dname_lab_cmp(result->name, result->labs, key.name, 430 key.labs, &m); 431 while(result) { /* go up until qname is subdomain of stub */ 432 if(result->labs <= m) 433 break; 434 result = result->parent; 435 } 436 } 437 return result; 438 } 439 440 /** 441 * Create a single zone node 442 * @param nm: name for zone (copied) 443 * @param nm_len: length of name 444 * @param labs: labels in name. 445 * @param dclass: class of zone, host order. 446 * @return new zone or NULL on failure 447 */ 448 static struct val_neg_zone* neg_setup_zone_node( 449 uint8_t* nm, size_t nm_len, int labs, uint16_t dclass) 450 { 451 struct val_neg_zone* zone = 452 (struct val_neg_zone*)calloc(1, sizeof(*zone)); 453 if(!zone) { 454 return NULL; 455 } 456 zone->node.key = zone; 457 zone->name = memdup(nm, nm_len); 458 if(!zone->name) { 459 free(zone); 460 return NULL; 461 } 462 zone->len = nm_len; 463 zone->labs = labs; 464 zone->dclass = dclass; 465 466 rbtree_init(&zone->tree, &val_neg_data_compare); 467 return zone; 468 } 469 470 /** 471 * Create a linked list of parent zones, starting at longname ending on 472 * the parent (can be NULL, creates to the root). 473 * @param nm: name for lowest in chain 474 * @param nm_len: length of name 475 * @param labs: labels in name. 476 * @param dclass: class of zone. 477 * @param parent: NULL for to root, else so it fits under here. 478 * @return zone; a chain of zones and their parents up to the parent. 479 * or NULL on malloc failure 480 */ 481 static struct val_neg_zone* neg_zone_chain( 482 uint8_t* nm, size_t nm_len, int labs, uint16_t dclass, 483 struct val_neg_zone* parent) 484 { 485 int i; 486 int tolabs = parent?parent->labs:0; 487 struct val_neg_zone* zone, *prev = NULL, *first = NULL; 488 489 /* create the new subtree, i is labelcount of current creation */ 490 /* this creates a 'first' to z->parent=NULL list of zones */ 491 for(i=labs; i!=tolabs; i--) { 492 /* create new item */ 493 zone = neg_setup_zone_node(nm, nm_len, i, dclass); 494 if(!zone) { 495 /* need to delete other allocations in this routine!*/ 496 struct val_neg_zone* p=first, *np; 497 while(p) { 498 np = p->parent; 499 free(p->name); 500 free(p); 501 p = np; 502 } 503 return NULL; 504 } 505 if(i == labs) { 506 first = zone; 507 } else { 508 prev->parent = zone; 509 } 510 /* prepare for next name */ 511 prev = zone; 512 dname_remove_label(&nm, &nm_len); 513 } 514 return first; 515 } 516 517 void val_neg_zone_take_inuse(struct val_neg_zone* zone) 518 { 519 if(!zone->in_use) { 520 struct val_neg_zone* p; 521 zone->in_use = 1; 522 /* increase usage count of all parents */ 523 for(p=zone; p; p = p->parent) { 524 p->count++; 525 } 526 } 527 } 528 529 struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg, 530 uint8_t* nm, size_t nm_len, uint16_t dclass) 531 { 532 struct val_neg_zone* zone; 533 struct val_neg_zone* parent; 534 struct val_neg_zone* p, *np; 535 int labs = dname_count_labels(nm); 536 537 /* find closest enclosing parent zone that (still) exists */ 538 parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass); 539 if(parent && query_dname_compare(parent->name, nm) == 0) 540 return parent; /* already exists, weird */ 541 /* if parent exists, it is in use */ 542 log_assert(!parent || parent->count > 0); 543 zone = neg_zone_chain(nm, nm_len, labs, dclass, parent); 544 if(!zone) { 545 return NULL; 546 } 547 548 /* insert the list of zones into the tree */ 549 p = zone; 550 while(p) { 551 np = p->parent; 552 /* mem use */ 553 neg->use += sizeof(struct val_neg_zone) + p->len; 554 /* insert in tree */ 555 (void)rbtree_insert(&neg->tree, &p->node); 556 /* last one needs proper parent pointer */ 557 if(np == NULL) 558 p->parent = parent; 559 p = np; 560 } 561 return zone; 562 } 563 564 /** find zone name of message, returns the SOA record */ 565 static struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep) 566 { 567 size_t i; 568 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 569 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA) 570 return rep->rrsets[i]; 571 } 572 return NULL; 573 } 574 575 /** see if the reply has NSEC records worthy of caching */ 576 static int reply_has_nsec(struct reply_info* rep) 577 { 578 size_t i; 579 struct packed_rrset_data* d; 580 if(rep->security != sec_status_secure) 581 return 0; 582 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 583 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 584 d = (struct packed_rrset_data*)rep->rrsets[i]-> 585 entry.data; 586 if(d->security == sec_status_secure) 587 return 1; 588 } 589 } 590 return 0; 591 } 592 593 594 /** 595 * Create single node of data element. 596 * @param nm: name (copied) 597 * @param nm_len: length of name 598 * @param labs: labels in name. 599 * @return element with name nm, or NULL malloc failure. 600 */ 601 static struct val_neg_data* neg_setup_data_node( 602 uint8_t* nm, size_t nm_len, int labs) 603 { 604 struct val_neg_data* el; 605 el = (struct val_neg_data*)calloc(1, sizeof(*el)); 606 if(!el) { 607 return NULL; 608 } 609 el->node.key = el; 610 el->name = memdup(nm, nm_len); 611 if(!el->name) { 612 free(el); 613 return NULL; 614 } 615 el->len = nm_len; 616 el->labs = labs; 617 return el; 618 } 619 620 /** 621 * Create chain of data element and parents 622 * @param nm: name 623 * @param nm_len: length of name 624 * @param labs: labels in name. 625 * @param parent: up to where to make, if NULL up to root label. 626 * @return lowest element with name nm, or NULL malloc failure. 627 */ 628 static struct val_neg_data* neg_data_chain( 629 uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent) 630 { 631 int i; 632 int tolabs = parent?parent->labs:0; 633 struct val_neg_data* el, *first = NULL, *prev = NULL; 634 635 /* create the new subtree, i is labelcount of current creation */ 636 /* this creates a 'first' to z->parent=NULL list of zones */ 637 for(i=labs; i!=tolabs; i--) { 638 /* create new item */ 639 el = neg_setup_data_node(nm, nm_len, i); 640 if(!el) { 641 /* need to delete other allocations in this routine!*/ 642 struct val_neg_data* p = first, *np; 643 while(p) { 644 np = p->parent; 645 free(p->name); 646 free(p); 647 p = np; 648 } 649 return NULL; 650 } 651 if(i == labs) { 652 first = el; 653 } else { 654 prev->parent = el; 655 } 656 657 /* prepare for next name */ 658 prev = el; 659 dname_remove_label(&nm, &nm_len); 660 } 661 return first; 662 } 663 664 /** 665 * Remove NSEC records between start and end points. 666 * By walking the tree, the tree is sorted canonically. 667 * @param neg: negative cache. 668 * @param zone: the zone 669 * @param el: element to start walking at. 670 * @param nsec: the nsec record with the end point 671 */ 672 static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone, 673 struct val_neg_data* el, struct ub_packed_rrset_key* nsec) 674 { 675 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> 676 entry.data; 677 uint8_t* end; 678 size_t end_len; 679 int end_labs, m; 680 rbnode_t* walk, *next; 681 struct val_neg_data* cur; 682 uint8_t buf[257]; 683 /* get endpoint */ 684 if(!d || d->count == 0 || d->rr_len[0] < 2+1) 685 return; 686 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) { 687 end = d->rr_data[0]+2; 688 end_len = dname_valid(end, d->rr_len[0]-2); 689 end_labs = dname_count_labels(end); 690 } else { 691 /* NSEC3 */ 692 if(!nsec3_get_nextowner_b32(nsec, 0, buf, sizeof(buf))) 693 return; 694 end = buf; 695 end_labs = dname_count_size_labels(end, &end_len); 696 } 697 698 /* sanity check, both owner and end must be below the zone apex */ 699 if(!dname_subdomain_c(el->name, zone->name) || 700 !dname_subdomain_c(end, zone->name)) 701 return; 702 703 /* detect end of zone NSEC ; wipe until the end of zone */ 704 if(query_dname_compare(end, zone->name) == 0) { 705 end = NULL; 706 } 707 708 walk = rbtree_next(&el->node); 709 while(walk && walk != RBTREE_NULL) { 710 cur = (struct val_neg_data*)walk; 711 /* sanity check: must be larger than start */ 712 if(dname_canon_lab_cmp(cur->name, cur->labs, 713 el->name, el->labs, &m) <= 0) { 714 /* r == 0 skip original record. */ 715 /* r < 0 too small! */ 716 walk = rbtree_next(walk); 717 continue; 718 } 719 /* stop at endpoint, also data at empty nonterminals must be 720 * removed (no NSECs there) so everything between 721 * start and end */ 722 if(end && dname_canon_lab_cmp(cur->name, cur->labs, 723 end, end_labs, &m) >= 0) { 724 break; 725 } 726 /* this element has to be deleted, but we cannot do it 727 * now, because we are walking the tree still ... */ 728 /* get the next element: */ 729 next = rbtree_next(walk); 730 /* now delete the original element, this may trigger 731 * rbtree rebalances, but really, the next element is 732 * the one we need. 733 * But it may trigger delete of other data and the 734 * entire zone. However, if that happens, this is done 735 * by deleting the *parents* of the element for deletion, 736 * and maybe also the entire zone if it is empty. 737 * But parents are smaller in canonical compare, thus, 738 * if a larger element exists, then it is not a parent, 739 * it cannot get deleted, the zone cannot get empty. 740 * If the next==NULL, then zone can be empty. */ 741 if(cur->in_use) 742 neg_delete_data(neg, cur); 743 walk = next; 744 } 745 } 746 747 void neg_insert_data(struct val_neg_cache* neg, 748 struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec) 749 { 750 struct packed_rrset_data* d; 751 struct val_neg_data* parent; 752 struct val_neg_data* el; 753 uint8_t* nm = nsec->rk.dname; 754 size_t nm_len = nsec->rk.dname_len; 755 int labs = dname_count_labels(nsec->rk.dname); 756 757 d = (struct packed_rrset_data*)nsec->entry.data; 758 if( !(d->security == sec_status_secure || 759 (d->security == sec_status_unchecked && d->rrsig_count > 0))) 760 return; 761 log_nametypeclass(VERB_ALGO, "negcache rr", 762 nsec->rk.dname, ntohs(nsec->rk.type), 763 ntohs(nsec->rk.rrset_class)); 764 765 /* find closest enclosing parent data that (still) exists */ 766 parent = neg_closest_data_parent(zone, nm, nm_len, labs); 767 if(parent && query_dname_compare(parent->name, nm) == 0) { 768 /* perfect match already exists */ 769 log_assert(parent->count > 0); 770 el = parent; 771 } else { 772 struct val_neg_data* p, *np; 773 774 /* create subtree for perfect match */ 775 /* if parent exists, it is in use */ 776 log_assert(!parent || parent->count > 0); 777 778 el = neg_data_chain(nm, nm_len, labs, parent); 779 if(!el) { 780 log_err("out of memory inserting NSEC negative cache"); 781 return; 782 } 783 el->in_use = 0; /* set on below */ 784 785 /* insert the list of zones into the tree */ 786 p = el; 787 while(p) { 788 np = p->parent; 789 /* mem use */ 790 neg->use += sizeof(struct val_neg_data) + p->len; 791 /* insert in tree */ 792 p->zone = zone; 793 (void)rbtree_insert(&zone->tree, &p->node); 794 /* last one needs proper parent pointer */ 795 if(np == NULL) 796 p->parent = parent; 797 p = np; 798 } 799 } 800 801 if(!el->in_use) { 802 struct val_neg_data* p; 803 804 el->in_use = 1; 805 /* increase usage count of all parents */ 806 for(p=el; p; p = p->parent) { 807 p->count++; 808 } 809 810 neg_lru_front(neg, el); 811 } else { 812 /* in use, bring to front, lru */ 813 neg_lru_touch(neg, el); 814 } 815 816 /* if nsec3 store last used parameters */ 817 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) { 818 int h; 819 uint8_t* s; 820 size_t slen, it; 821 if(nsec3_get_params(nsec, 0, &h, &it, &s, &slen) && 822 it <= neg->nsec3_max_iter && 823 (h != zone->nsec3_hash || it != zone->nsec3_iter || 824 slen != zone->nsec3_saltlen || 825 memcmp(zone->nsec3_salt, s, slen) != 0)) { 826 827 if(slen > 0) { 828 uint8_t* sa = memdup(s, slen); 829 if(sa) { 830 free(zone->nsec3_salt); 831 zone->nsec3_salt = sa; 832 zone->nsec3_saltlen = slen; 833 zone->nsec3_iter = it; 834 zone->nsec3_hash = h; 835 } 836 } else { 837 free(zone->nsec3_salt); 838 zone->nsec3_salt = NULL; 839 zone->nsec3_saltlen = 0; 840 zone->nsec3_iter = it; 841 zone->nsec3_hash = h; 842 } 843 } 844 } 845 846 /* wipe out the cache items between NSEC start and end */ 847 wipeout(neg, zone, el, nsec); 848 } 849 850 void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep) 851 { 852 size_t i, need; 853 struct ub_packed_rrset_key* soa; 854 struct val_neg_zone* zone; 855 /* see if secure nsecs inside */ 856 if(!reply_has_nsec(rep)) 857 return; 858 /* find the zone name in message */ 859 soa = reply_find_soa(rep); 860 if(!soa) 861 return; 862 863 log_nametypeclass(VERB_ALGO, "negcache insert for zone", 864 soa->rk.dname, LDNS_RR_TYPE_SOA, ntohs(soa->rk.rrset_class)); 865 866 /* ask for enough space to store all of it */ 867 need = calc_data_need(rep) + 868 calc_zone_need(soa->rk.dname, soa->rk.dname_len); 869 lock_basic_lock(&neg->lock); 870 neg_make_space(neg, need); 871 872 /* find or create the zone entry */ 873 zone = neg_find_zone(neg, soa->rk.dname, soa->rk.dname_len, 874 ntohs(soa->rk.rrset_class)); 875 if(!zone) { 876 if(!(zone = neg_create_zone(neg, soa->rk.dname, 877 soa->rk.dname_len, ntohs(soa->rk.rrset_class)))) { 878 lock_basic_unlock(&neg->lock); 879 log_err("out of memory adding negative zone"); 880 return; 881 } 882 } 883 val_neg_zone_take_inuse(zone); 884 885 /* insert the NSECs */ 886 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 887 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC) 888 continue; 889 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 890 zone->name)) continue; 891 /* insert NSEC into this zone's tree */ 892 neg_insert_data(neg, zone, rep->rrsets[i]); 893 } 894 if(zone->tree.count == 0) { 895 /* remove empty zone if inserts failed */ 896 neg_delete_zone(neg, zone); 897 } 898 lock_basic_unlock(&neg->lock); 899 } 900 901 /** 902 * Lookup closest data record. For NSEC denial. 903 * @param zone: zone to look in 904 * @param qname: name to look for. 905 * @param len: length of name 906 * @param labs: labels in name 907 * @param data: data element, exact or smaller or NULL 908 * @return true if exact match. 909 */ 910 static int neg_closest_data(struct val_neg_zone* zone, 911 uint8_t* qname, size_t len, int labs, struct val_neg_data** data) 912 { 913 struct val_neg_data key; 914 rbnode_t* r; 915 key.node.key = &key; 916 key.name = qname; 917 key.len = len; 918 key.labs = labs; 919 if(rbtree_find_less_equal(&zone->tree, &key, &r)) { 920 /* exact match */ 921 *data = (struct val_neg_data*)r; 922 return 1; 923 } else { 924 /* smaller match */ 925 *data = (struct val_neg_data*)r; 926 return 0; 927 } 928 } 929 930 int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len, 931 uint16_t qclass, struct rrset_cache* rrset_cache, time_t now) 932 { 933 /* lookup closest zone */ 934 struct val_neg_zone* zone; 935 struct val_neg_data* data; 936 int labs; 937 struct ub_packed_rrset_key* nsec; 938 struct packed_rrset_data* d; 939 uint32_t flags; 940 uint8_t* wc; 941 struct query_info qinfo; 942 if(!neg) return 0; 943 944 log_nametypeclass(VERB_ALGO, "negcache dlvlookup", qname, 945 LDNS_RR_TYPE_DLV, qclass); 946 947 labs = dname_count_labels(qname); 948 lock_basic_lock(&neg->lock); 949 zone = neg_closest_zone_parent(neg, qname, len, labs, qclass); 950 while(zone && !zone->in_use) 951 zone = zone->parent; 952 if(!zone) { 953 lock_basic_unlock(&neg->lock); 954 return 0; 955 } 956 log_nametypeclass(VERB_ALGO, "negcache zone", zone->name, 0, 957 zone->dclass); 958 959 /* DLV is defined to use NSEC only */ 960 if(zone->nsec3_hash) { 961 lock_basic_unlock(&neg->lock); 962 return 0; 963 } 964 965 /* lookup closest data record */ 966 (void)neg_closest_data(zone, qname, len, labs, &data); 967 while(data && !data->in_use) 968 data = data->parent; 969 if(!data) { 970 lock_basic_unlock(&neg->lock); 971 return 0; 972 } 973 log_nametypeclass(VERB_ALGO, "negcache rr", data->name, 974 LDNS_RR_TYPE_NSEC, zone->dclass); 975 976 /* lookup rrset in rrset cache */ 977 flags = 0; 978 if(query_dname_compare(data->name, zone->name) == 0) 979 flags = PACKED_RRSET_NSEC_AT_APEX; 980 nsec = rrset_cache_lookup(rrset_cache, data->name, data->len, 981 LDNS_RR_TYPE_NSEC, zone->dclass, flags, now, 0); 982 983 /* check if secure and TTL ok */ 984 if(!nsec) { 985 lock_basic_unlock(&neg->lock); 986 return 0; 987 } 988 d = (struct packed_rrset_data*)nsec->entry.data; 989 if(!d || now > d->ttl) { 990 lock_rw_unlock(&nsec->entry.lock); 991 /* delete data record if expired */ 992 neg_delete_data(neg, data); 993 lock_basic_unlock(&neg->lock); 994 return 0; 995 } 996 if(d->security != sec_status_secure) { 997 lock_rw_unlock(&nsec->entry.lock); 998 neg_delete_data(neg, data); 999 lock_basic_unlock(&neg->lock); 1000 return 0; 1001 } 1002 verbose(VERB_ALGO, "negcache got secure rrset"); 1003 1004 /* check NSEC security */ 1005 /* check if NSEC proves no DLV type exists */ 1006 /* check if NSEC proves NXDOMAIN for qname */ 1007 qinfo.qname = qname; 1008 qinfo.qtype = LDNS_RR_TYPE_DLV; 1009 qinfo.qclass = qclass; 1010 if(!nsec_proves_nodata(nsec, &qinfo, &wc) && 1011 !val_nsec_proves_name_error(nsec, qname)) { 1012 /* the NSEC is not a denial for the DLV */ 1013 lock_rw_unlock(&nsec->entry.lock); 1014 lock_basic_unlock(&neg->lock); 1015 verbose(VERB_ALGO, "negcache not proven"); 1016 return 0; 1017 } 1018 /* so the NSEC was a NODATA proof, or NXDOMAIN proof. */ 1019 1020 /* no need to check for wildcard NSEC; no wildcards in DLV repos */ 1021 /* no need to lookup SOA record for client; no response message */ 1022 1023 lock_rw_unlock(&nsec->entry.lock); 1024 /* if OK touch the LRU for neg_data element */ 1025 neg_lru_touch(neg, data); 1026 lock_basic_unlock(&neg->lock); 1027 verbose(VERB_ALGO, "negcache DLV denial proven"); 1028 return 1; 1029 } 1030 1031 /** see if the reply has signed NSEC records and return the signer */ 1032 static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len, 1033 uint16_t* dclass) 1034 { 1035 size_t i; 1036 struct packed_rrset_data* d; 1037 uint8_t* s; 1038 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 1039 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC || 1040 ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) { 1041 d = (struct packed_rrset_data*)rep->rrsets[i]-> 1042 entry.data; 1043 /* return first signer name of first NSEC */ 1044 if(d->rrsig_count != 0) { 1045 val_find_rrset_signer(rep->rrsets[i], 1046 &s, signer_len); 1047 if(s && *signer_len) { 1048 *dclass = ntohs(rep->rrsets[i]-> 1049 rk.rrset_class); 1050 return s; 1051 } 1052 } 1053 } 1054 } 1055 return 0; 1056 } 1057 1058 void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep, 1059 uint8_t* zone_name) 1060 { 1061 size_t i, need; 1062 uint8_t* signer; 1063 size_t signer_len; 1064 uint16_t dclass; 1065 struct val_neg_zone* zone; 1066 /* no SOA in this message, find RRSIG over NSEC's signer name. 1067 * note the NSEC records are maybe not validated yet */ 1068 signer = reply_nsec_signer(rep, &signer_len, &dclass); 1069 if(!signer) 1070 return; 1071 if(!dname_subdomain_c(signer, zone_name)) { 1072 /* the signer is not in the bailiwick, throw it out */ 1073 return; 1074 } 1075 1076 log_nametypeclass(VERB_ALGO, "negcache insert referral ", 1077 signer, LDNS_RR_TYPE_NS, dclass); 1078 1079 /* ask for enough space to store all of it */ 1080 need = calc_data_need(rep) + calc_zone_need(signer, signer_len); 1081 lock_basic_lock(&neg->lock); 1082 neg_make_space(neg, need); 1083 1084 /* find or create the zone entry */ 1085 zone = neg_find_zone(neg, signer, signer_len, dclass); 1086 if(!zone) { 1087 if(!(zone = neg_create_zone(neg, signer, signer_len, 1088 dclass))) { 1089 lock_basic_unlock(&neg->lock); 1090 log_err("out of memory adding negative zone"); 1091 return; 1092 } 1093 } 1094 val_neg_zone_take_inuse(zone); 1095 1096 /* insert the NSECs */ 1097 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 1098 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC && 1099 ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3) 1100 continue; 1101 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 1102 zone->name)) continue; 1103 /* insert NSEC into this zone's tree */ 1104 neg_insert_data(neg, zone, rep->rrsets[i]); 1105 } 1106 if(zone->tree.count == 0) { 1107 /* remove empty zone if inserts failed */ 1108 neg_delete_zone(neg, zone); 1109 } 1110 lock_basic_unlock(&neg->lock); 1111 } 1112 1113 /** 1114 * Check that an NSEC3 rrset does not have a type set. 1115 * None of the nsec3s in a hash-collision are allowed to have the type. 1116 * (since we do not know which one is the nsec3 looked at, flags, ..., we 1117 * ignore the cached item and let it bypass negative caching). 1118 * @param k: the nsec3 rrset to check. 1119 * @param t: type to check 1120 * @return true if no RRs have the type. 1121 */ 1122 static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t) 1123 { 1124 int count = (int)((struct packed_rrset_data*)k->entry.data)->count; 1125 int i; 1126 for(i=0; i<count; i++) 1127 if(nsec3_has_type(k, i, t)) 1128 return 0; 1129 return 1; 1130 } 1131 1132 /** 1133 * See if rrset exists in rrset cache. 1134 * If it does, the bit is checked, and if not expired, it is returned 1135 * allocated in region. 1136 * @param rrset_cache: rrset cache 1137 * @param qname: to lookup rrset name 1138 * @param qname_len: length of qname. 1139 * @param qtype: type of rrset to lookup, host order 1140 * @param qclass: class of rrset to lookup, host order 1141 * @param flags: flags for rrset to lookup 1142 * @param region: where to alloc result 1143 * @param checkbit: if true, a bit in the nsec typemap is checked for absence. 1144 * @param checktype: which bit to check 1145 * @param now: to check ttl against 1146 * @return rrset or NULL 1147 */ 1148 static struct ub_packed_rrset_key* 1149 grab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len, 1150 uint16_t qtype, uint16_t qclass, uint32_t flags, 1151 struct regional* region, int checkbit, uint16_t checktype, 1152 time_t now) 1153 { 1154 struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache, 1155 qname, qname_len, qtype, qclass, flags, now, 0); 1156 struct packed_rrset_data* d; 1157 if(!k) return NULL; 1158 d = (struct packed_rrset_data*)k->entry.data; 1159 if(d->ttl < now) { 1160 lock_rw_unlock(&k->entry.lock); 1161 return NULL; 1162 } 1163 /* only secure or unchecked records that have signatures. */ 1164 if( ! ( d->security == sec_status_secure || 1165 (d->security == sec_status_unchecked && 1166 d->rrsig_count > 0) ) ) { 1167 lock_rw_unlock(&k->entry.lock); 1168 return NULL; 1169 } 1170 /* check if checktype is absent */ 1171 if(checkbit && ( 1172 (qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) || 1173 (qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype)) 1174 )) { 1175 lock_rw_unlock(&k->entry.lock); 1176 return NULL; 1177 } 1178 /* looks OK! copy to region and return it */ 1179 r = packed_rrset_copy_region(k, region, now); 1180 /* if it failed, we return the NULL */ 1181 lock_rw_unlock(&k->entry.lock); 1182 return r; 1183 } 1184 1185 /** find nsec3 closest encloser in neg cache */ 1186 static struct val_neg_data* 1187 neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 1188 int qlabs, sldns_buffer* buf, uint8_t* hashnc, size_t* nclen) 1189 { 1190 struct val_neg_data* data; 1191 uint8_t hashce[NSEC3_SHA_LEN]; 1192 uint8_t b32[257]; 1193 size_t celen, b32len; 1194 1195 *nclen = 0; 1196 while(qlabs > 0) { 1197 /* hash */ 1198 if(!(celen=nsec3_get_hashed(buf, qname, qname_len, 1199 zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt, 1200 zone->nsec3_saltlen, hashce, sizeof(hashce)))) 1201 return NULL; 1202 if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name, 1203 zone->len, b32, sizeof(b32)))) 1204 return NULL; 1205 1206 /* lookup (exact match only) */ 1207 data = neg_find_data(zone, b32, b32len, zone->labs+1); 1208 if(data && data->in_use) { 1209 /* found ce match! */ 1210 return data; 1211 } 1212 1213 *nclen = celen; 1214 memmove(hashnc, hashce, celen); 1215 dname_remove_label(&qname, &qname_len); 1216 qlabs --; 1217 } 1218 return NULL; 1219 } 1220 1221 /** check nsec3 parameters on nsec3 rrset with current zone values */ 1222 static int 1223 neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset) 1224 { 1225 int h; 1226 uint8_t* s; 1227 size_t slen, it; 1228 if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen)) 1229 return 0; 1230 return (h == zone->nsec3_hash && it == zone->nsec3_iter && 1231 slen == zone->nsec3_saltlen && 1232 memcmp(zone->nsec3_salt, s, slen) == 0); 1233 } 1234 1235 /** get next closer for nsec3 proof */ 1236 static struct ub_packed_rrset_key* 1237 neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen, 1238 struct rrset_cache* rrset_cache, struct regional* region, 1239 time_t now, uint8_t* b32, size_t maxb32) 1240 { 1241 struct ub_packed_rrset_key* nc_rrset; 1242 struct val_neg_data* data; 1243 size_t b32len; 1244 1245 if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name, 1246 zone->len, b32, maxb32))) 1247 return NULL; 1248 (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data); 1249 if(!data && zone->tree.count != 0) { 1250 /* could be before the first entry ; return the last 1251 * entry (possibly the rollover nsec3 at end) */ 1252 data = (struct val_neg_data*)rbtree_last(&zone->tree); 1253 } 1254 while(data && !data->in_use) 1255 data = data->parent; 1256 if(!data) 1257 return NULL; 1258 /* got a data element in tree, grab it */ 1259 nc_rrset = grab_nsec(rrset_cache, data->name, data->len, 1260 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now); 1261 if(!nc_rrset) 1262 return NULL; 1263 if(!neg_params_ok(zone, nc_rrset)) 1264 return NULL; 1265 return nc_rrset; 1266 } 1267 1268 /** neg cache nsec3 proof procedure*/ 1269 static struct dns_msg* 1270 neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 1271 int qlabs, sldns_buffer* buf, struct rrset_cache* rrset_cache, 1272 struct regional* region, time_t now, uint8_t* topname) 1273 { 1274 struct dns_msg* msg; 1275 struct val_neg_data* data; 1276 uint8_t hashnc[NSEC3_SHA_LEN]; 1277 size_t nclen; 1278 struct ub_packed_rrset_key* ce_rrset, *nc_rrset; 1279 struct nsec3_cached_hash c; 1280 uint8_t nc_b32[257]; 1281 1282 /* for NSEC3 ; determine the closest encloser for which we 1283 * can find an exact match. Remember the hashed lower name, 1284 * since that is the one we need a closest match for. 1285 * If we find a match straight away, then it becomes NODATA. 1286 * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation. 1287 * Also check that parameters are the same on closest encloser 1288 * and on closest match. 1289 */ 1290 if(!zone->nsec3_hash) 1291 return NULL; /* not nsec3 zone */ 1292 1293 if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf, 1294 hashnc, &nclen))) { 1295 return NULL; 1296 } 1297 1298 /* grab the ce rrset */ 1299 ce_rrset = grab_nsec(rrset_cache, data->name, data->len, 1300 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1, 1301 LDNS_RR_TYPE_DS, now); 1302 if(!ce_rrset) 1303 return NULL; 1304 if(!neg_params_ok(zone, ce_rrset)) 1305 return NULL; 1306 1307 if(nclen == 0) { 1308 /* exact match, just check the type bits */ 1309 /* need: -SOA, -DS, +NS */ 1310 if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) || 1311 nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) || 1312 !nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS)) 1313 return NULL; 1314 if(!(msg = dns_msg_create(qname, qname_len, 1315 LDNS_RR_TYPE_DS, zone->dclass, region, 1))) 1316 return NULL; 1317 /* TTL reduced in grab_nsec */ 1318 if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1319 return NULL; 1320 return msg; 1321 } 1322 1323 /* optout is not allowed without knowing the trust-anchor in use, 1324 * otherwise the optout could spoof away that anchor */ 1325 if(!topname) 1326 return NULL; 1327 1328 /* if there is no exact match, it must be in an optout span 1329 * (an existing DS implies an NSEC3 must exist) */ 1330 nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache, 1331 region, now, nc_b32, sizeof(nc_b32)); 1332 if(!nc_rrset) 1333 return NULL; 1334 if(!neg_params_ok(zone, nc_rrset)) 1335 return NULL; 1336 if(!nsec3_has_optout(nc_rrset, 0)) 1337 return NULL; 1338 c.hash = hashnc; 1339 c.hash_len = nclen; 1340 c.b32 = nc_b32+1; 1341 c.b32_len = (size_t)nc_b32[0]; 1342 if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) { 1343 /* nc_rrset covers the next closer name. 1344 * ce_rrset equals a closer encloser. 1345 * nc_rrset is optout. 1346 * No need to check wildcard for type DS */ 1347 /* capacity=3: ce + nc + soa(if needed) */ 1348 if(!(msg = dns_msg_create(qname, qname_len, 1349 LDNS_RR_TYPE_DS, zone->dclass, region, 3))) 1350 return NULL; 1351 /* now=0 because TTL was reduced in grab_nsec */ 1352 if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1353 return NULL; 1354 if(!dns_msg_authadd(msg, region, nc_rrset, 0)) 1355 return NULL; 1356 return msg; 1357 } 1358 return NULL; 1359 } 1360 1361 /** 1362 * Add SOA record for external responses. 1363 * @param rrset_cache: to look into. 1364 * @param now: current time. 1365 * @param region: where to perform the allocation 1366 * @param msg: current msg with NSEC. 1367 * @param zone: val_neg_zone if we have one. 1368 * @return false on lookup or alloc failure. 1369 */ 1370 static int add_soa(struct rrset_cache* rrset_cache, time_t now, 1371 struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone) 1372 { 1373 struct ub_packed_rrset_key* soa; 1374 uint8_t* nm; 1375 size_t nmlen; 1376 uint16_t dclass; 1377 if(zone) { 1378 nm = zone->name; 1379 nmlen = zone->len; 1380 dclass = zone->dclass; 1381 } else { 1382 /* Assumes the signer is the zone SOA to add */ 1383 nm = reply_nsec_signer(msg->rep, &nmlen, &dclass); 1384 if(!nm) 1385 return 0; 1386 } 1387 soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA, 1388 dclass, PACKED_RRSET_SOA_NEG, now, 0); 1389 if(!soa) 1390 return 0; 1391 if(!dns_msg_authadd(msg, region, soa, now)) { 1392 lock_rw_unlock(&soa->entry.lock); 1393 return 0; 1394 } 1395 lock_rw_unlock(&soa->entry.lock); 1396 return 1; 1397 } 1398 1399 struct dns_msg* 1400 val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo, 1401 struct regional* region, struct rrset_cache* rrset_cache, 1402 sldns_buffer* buf, time_t now, int addsoa, uint8_t* topname) 1403 { 1404 struct dns_msg* msg; 1405 struct ub_packed_rrset_key* rrset; 1406 uint8_t* zname; 1407 size_t zname_len; 1408 int zname_labs; 1409 struct val_neg_zone* zone; 1410 1411 /* only for DS queries */ 1412 if(qinfo->qtype != LDNS_RR_TYPE_DS) 1413 return NULL; 1414 log_assert(!topname || dname_subdomain_c(qinfo->qname, topname)); 1415 1416 /* see if info from neg cache is available 1417 * For NSECs, because there is no optout; a DS next to a delegation 1418 * always has exactly an NSEC for it itself; check its DS bit. 1419 * flags=0 (not the zone apex). 1420 */ 1421 rrset = grab_nsec(rrset_cache, qinfo->qname, qinfo->qname_len, 1422 LDNS_RR_TYPE_NSEC, qinfo->qclass, 0, region, 1, 1423 qinfo->qtype, now); 1424 if(rrset) { 1425 /* return msg with that rrset */ 1426 if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 1427 qinfo->qtype, qinfo->qclass, region, 2))) 1428 return NULL; 1429 /* TTL already subtracted in grab_nsec */ 1430 if(!dns_msg_authadd(msg, region, rrset, 0)) 1431 return NULL; 1432 if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL)) 1433 return NULL; 1434 return msg; 1435 } 1436 1437 /* check NSEC3 neg cache for type DS */ 1438 /* need to look one zone higher for DS type */ 1439 zname = qinfo->qname; 1440 zname_len = qinfo->qname_len; 1441 dname_remove_label(&zname, &zname_len); 1442 zname_labs = dname_count_labels(zname); 1443 1444 /* lookup closest zone */ 1445 lock_basic_lock(&neg->lock); 1446 zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs, 1447 qinfo->qclass); 1448 while(zone && !zone->in_use) 1449 zone = zone->parent; 1450 /* check that the zone is not too high up so that we do not pick data 1451 * out of a zone that is above the last-seen key (or trust-anchor). */ 1452 if(zone && topname) { 1453 if(!dname_subdomain_c(zone->name, topname)) 1454 zone = NULL; 1455 } 1456 if(!zone) { 1457 lock_basic_unlock(&neg->lock); 1458 return NULL; 1459 } 1460 1461 msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len, 1462 zname_labs+1, buf, rrset_cache, region, now, topname); 1463 if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) { 1464 lock_basic_unlock(&neg->lock); 1465 return NULL; 1466 } 1467 lock_basic_unlock(&neg->lock); 1468 return msg; 1469 } 1470