1238106Sdes/* 2238106Sdes * validator/val_neg.c - validator aggressive negative caching functions. 3238106Sdes * 4238106Sdes * Copyright (c) 2008, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24266114Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25266114Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26266114Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27266114Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28266114Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29266114Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30266114Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31266114Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32266114Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33266114Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains helper functions for the validator module. 40238106Sdes * The functions help with aggressive negative caching. 41292206Sdes * This creates new denials of existence, and proofs for absence of types 42238106Sdes * from cached NSEC records. 43238106Sdes */ 44238106Sdes#include "config.h" 45238106Sdes#ifdef HAVE_OPENSSL_SSL_H 46238106Sdes#include "openssl/ssl.h" 47249141Sdes#define NSEC3_SHA_LEN SHA_DIGEST_LENGTH 48249141Sdes#else 49249141Sdes#define NSEC3_SHA_LEN 20 50238106Sdes#endif 51238106Sdes#include "validator/val_neg.h" 52238106Sdes#include "validator/val_nsec.h" 53238106Sdes#include "validator/val_nsec3.h" 54238106Sdes#include "validator/val_utils.h" 55238106Sdes#include "util/data/dname.h" 56238106Sdes#include "util/data/msgreply.h" 57238106Sdes#include "util/log.h" 58238106Sdes#include "util/net_help.h" 59238106Sdes#include "util/config_file.h" 60238106Sdes#include "services/cache/rrset.h" 61238106Sdes#include "services/cache/dns.h" 62287917Sdes#include "sldns/rrdef.h" 63287917Sdes#include "sldns/sbuffer.h" 64238106Sdes 65238106Sdesint val_neg_data_compare(const void* a, const void* b) 66238106Sdes{ 67238106Sdes struct val_neg_data* x = (struct val_neg_data*)a; 68238106Sdes struct val_neg_data* y = (struct val_neg_data*)b; 69238106Sdes int m; 70238106Sdes return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 71238106Sdes} 72238106Sdes 73238106Sdesint val_neg_zone_compare(const void* a, const void* b) 74238106Sdes{ 75238106Sdes struct val_neg_zone* x = (struct val_neg_zone*)a; 76238106Sdes struct val_neg_zone* y = (struct val_neg_zone*)b; 77238106Sdes int m; 78238106Sdes if(x->dclass != y->dclass) { 79238106Sdes if(x->dclass < y->dclass) 80238106Sdes return -1; 81238106Sdes return 1; 82238106Sdes } 83238106Sdes return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 84238106Sdes} 85238106Sdes 86238106Sdesstruct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter) 87238106Sdes{ 88238106Sdes struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1, 89238106Sdes sizeof(*neg)); 90238106Sdes if(!neg) { 91238106Sdes log_err("Could not create neg cache: out of memory"); 92238106Sdes return NULL; 93238106Sdes } 94238106Sdes neg->nsec3_max_iter = maxiter; 95238106Sdes neg->max = 1024*1024; /* 1 M is thousands of entries */ 96238106Sdes if(cfg) neg->max = cfg->neg_cache_size; 97238106Sdes rbtree_init(&neg->tree, &val_neg_zone_compare); 98238106Sdes lock_basic_init(&neg->lock); 99238106Sdes lock_protect(&neg->lock, neg, sizeof(*neg)); 100238106Sdes return neg; 101238106Sdes} 102238106Sdes 103238106Sdessize_t val_neg_get_mem(struct val_neg_cache* neg) 104238106Sdes{ 105238106Sdes size_t result; 106238106Sdes lock_basic_lock(&neg->lock); 107238106Sdes result = sizeof(*neg) + neg->use; 108238106Sdes lock_basic_unlock(&neg->lock); 109238106Sdes return result; 110238106Sdes} 111238106Sdes 112238106Sdes/** clear datas on cache deletion */ 113238106Sdesstatic void 114356345Scyneg_clear_datas(rbnode_type* n, void* ATTR_UNUSED(arg)) 115238106Sdes{ 116238106Sdes struct val_neg_data* d = (struct val_neg_data*)n; 117238106Sdes free(d->name); 118238106Sdes free(d); 119238106Sdes} 120238106Sdes 121238106Sdes/** clear zones on cache deletion */ 122238106Sdesstatic void 123356345Scyneg_clear_zones(rbnode_type* n, void* ATTR_UNUSED(arg)) 124238106Sdes{ 125238106Sdes struct val_neg_zone* z = (struct val_neg_zone*)n; 126238106Sdes /* delete all the rrset entries in the tree */ 127238106Sdes traverse_postorder(&z->tree, &neg_clear_datas, NULL); 128238106Sdes free(z->nsec3_salt); 129238106Sdes free(z->name); 130238106Sdes free(z); 131238106Sdes} 132238106Sdes 133238106Sdesvoid neg_cache_delete(struct val_neg_cache* neg) 134238106Sdes{ 135238106Sdes if(!neg) return; 136238106Sdes lock_basic_destroy(&neg->lock); 137238106Sdes /* delete all the zones in the tree */ 138238106Sdes traverse_postorder(&neg->tree, &neg_clear_zones, NULL); 139238106Sdes free(neg); 140238106Sdes} 141238106Sdes 142238106Sdes/** 143238106Sdes * Put data element at the front of the LRU list. 144238106Sdes * @param neg: negative cache with LRU start and end. 145238106Sdes * @param data: this data is fronted. 146238106Sdes */ 147238106Sdesstatic void neg_lru_front(struct val_neg_cache* neg, 148238106Sdes struct val_neg_data* data) 149238106Sdes{ 150238106Sdes data->prev = NULL; 151238106Sdes data->next = neg->first; 152238106Sdes if(!neg->first) 153238106Sdes neg->last = data; 154238106Sdes else neg->first->prev = data; 155238106Sdes neg->first = data; 156238106Sdes} 157238106Sdes 158238106Sdes/** 159238106Sdes * Remove data element from LRU list. 160238106Sdes * @param neg: negative cache with LRU start and end. 161238106Sdes * @param data: this data is removed from the list. 162238106Sdes */ 163238106Sdesstatic void neg_lru_remove(struct val_neg_cache* neg, 164238106Sdes struct val_neg_data* data) 165238106Sdes{ 166238106Sdes if(data->prev) 167238106Sdes data->prev->next = data->next; 168238106Sdes else neg->first = data->next; 169238106Sdes if(data->next) 170238106Sdes data->next->prev = data->prev; 171238106Sdes else neg->last = data->prev; 172238106Sdes} 173238106Sdes 174238106Sdes/** 175238106Sdes * Touch LRU for data element, put it at the start of the LRU list. 176238106Sdes * @param neg: negative cache with LRU start and end. 177238106Sdes * @param data: this data is used. 178238106Sdes */ 179238106Sdesstatic void neg_lru_touch(struct val_neg_cache* neg, 180238106Sdes struct val_neg_data* data) 181238106Sdes{ 182238106Sdes if(data == neg->first) 183238106Sdes return; /* nothing to do */ 184238106Sdes /* remove from current lru position */ 185238106Sdes neg_lru_remove(neg, data); 186238106Sdes /* add at front */ 187238106Sdes neg_lru_front(neg, data); 188238106Sdes} 189238106Sdes 190238106Sdes/** 191238106Sdes * Delete a zone element from the negative cache. 192238106Sdes * May delete other zone elements to keep tree coherent, or 193238106Sdes * only mark the element as 'not in use'. 194238106Sdes * @param neg: negative cache. 195238106Sdes * @param z: zone element to delete. 196238106Sdes */ 197238106Sdesstatic void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z) 198238106Sdes{ 199238106Sdes struct val_neg_zone* p, *np; 200238106Sdes if(!z) return; 201238106Sdes log_assert(z->in_use); 202238106Sdes log_assert(z->count > 0); 203238106Sdes z->in_use = 0; 204238106Sdes 205238106Sdes /* go up the tree and reduce counts */ 206238106Sdes p = z; 207238106Sdes while(p) { 208238106Sdes log_assert(p->count > 0); 209238106Sdes p->count --; 210238106Sdes p = p->parent; 211238106Sdes } 212238106Sdes 213238106Sdes /* remove zones with zero count */ 214238106Sdes p = z; 215238106Sdes while(p && p->count == 0) { 216238106Sdes np = p->parent; 217238106Sdes (void)rbtree_delete(&neg->tree, &p->node); 218238106Sdes neg->use -= p->len + sizeof(*p); 219238106Sdes free(p->nsec3_salt); 220238106Sdes free(p->name); 221238106Sdes free(p); 222238106Sdes p = np; 223238106Sdes } 224238106Sdes} 225238106Sdes 226238106Sdesvoid neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el) 227238106Sdes{ 228238106Sdes struct val_neg_zone* z; 229238106Sdes struct val_neg_data* p, *np; 230238106Sdes if(!el) return; 231238106Sdes z = el->zone; 232238106Sdes log_assert(el->in_use); 233238106Sdes log_assert(el->count > 0); 234238106Sdes el->in_use = 0; 235238106Sdes 236238106Sdes /* remove it from the lru list */ 237238106Sdes neg_lru_remove(neg, el); 238356345Scy log_assert(neg->first != el && neg->last != el); 239238106Sdes 240238106Sdes /* go up the tree and reduce counts */ 241238106Sdes p = el; 242238106Sdes while(p) { 243238106Sdes log_assert(p->count > 0); 244238106Sdes p->count --; 245238106Sdes p = p->parent; 246238106Sdes } 247238106Sdes 248238106Sdes /* delete 0 count items from tree */ 249238106Sdes p = el; 250238106Sdes while(p && p->count == 0) { 251238106Sdes np = p->parent; 252238106Sdes (void)rbtree_delete(&z->tree, &p->node); 253238106Sdes neg->use -= p->len + sizeof(*p); 254238106Sdes free(p->name); 255238106Sdes free(p); 256238106Sdes p = np; 257238106Sdes } 258238106Sdes 259238106Sdes /* check if the zone is now unused */ 260238106Sdes if(z->tree.count == 0) { 261238106Sdes neg_delete_zone(neg, z); 262238106Sdes } 263238106Sdes} 264238106Sdes 265238106Sdes/** 266238106Sdes * Create more space in negative cache 267238106Sdes * The oldest elements are deleted until enough space is present. 268238106Sdes * Empty zones are deleted. 269238106Sdes * @param neg: negative cache. 270238106Sdes * @param need: how many bytes are needed. 271238106Sdes */ 272238106Sdesstatic void neg_make_space(struct val_neg_cache* neg, size_t need) 273238106Sdes{ 274238106Sdes /* delete elements until enough space or its empty */ 275238106Sdes while(neg->last && neg->max < neg->use + need) { 276238106Sdes neg_delete_data(neg, neg->last); 277238106Sdes } 278238106Sdes} 279238106Sdes 280238106Sdesstruct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 281238106Sdes uint8_t* nm, size_t len, uint16_t dclass) 282238106Sdes{ 283238106Sdes struct val_neg_zone lookfor; 284238106Sdes struct val_neg_zone* result; 285238106Sdes lookfor.node.key = &lookfor; 286238106Sdes lookfor.name = nm; 287238106Sdes lookfor.len = len; 288238106Sdes lookfor.labs = dname_count_labels(lookfor.name); 289238106Sdes lookfor.dclass = dclass; 290238106Sdes 291238106Sdes result = (struct val_neg_zone*) 292238106Sdes rbtree_search(&neg->tree, lookfor.node.key); 293238106Sdes return result; 294238106Sdes} 295238106Sdes 296238106Sdes/** 297238106Sdes * Find the given data 298238106Sdes * @param zone: negative zone 299238106Sdes * @param nm: what to look for. 300238106Sdes * @param len: length of nm 301238106Sdes * @param labs: labels in nm 302238106Sdes * @return data or NULL if not found. 303238106Sdes */ 304238106Sdesstatic struct val_neg_data* neg_find_data(struct val_neg_zone* zone, 305238106Sdes uint8_t* nm, size_t len, int labs) 306238106Sdes{ 307238106Sdes struct val_neg_data lookfor; 308238106Sdes struct val_neg_data* result; 309238106Sdes lookfor.node.key = &lookfor; 310238106Sdes lookfor.name = nm; 311238106Sdes lookfor.len = len; 312238106Sdes lookfor.labs = labs; 313238106Sdes 314238106Sdes result = (struct val_neg_data*) 315238106Sdes rbtree_search(&zone->tree, lookfor.node.key); 316238106Sdes return result; 317238106Sdes} 318238106Sdes 319238106Sdes/** 320238106Sdes * Calculate space needed for the data and all its parents 321238106Sdes * @param rep: NSEC entries. 322238106Sdes * @return size. 323238106Sdes */ 324238106Sdesstatic size_t calc_data_need(struct reply_info* rep) 325238106Sdes{ 326238106Sdes uint8_t* d; 327238106Sdes size_t i, len, res = 0; 328238106Sdes 329238106Sdes for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) { 330238106Sdes if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 331238106Sdes d = rep->rrsets[i]->rk.dname; 332238106Sdes len = rep->rrsets[i]->rk.dname_len; 333238106Sdes res = sizeof(struct val_neg_data) + len; 334238106Sdes while(!dname_is_root(d)) { 335238106Sdes log_assert(len > 1); /* not root label */ 336238106Sdes dname_remove_label(&d, &len); 337238106Sdes res += sizeof(struct val_neg_data) + len; 338238106Sdes } 339238106Sdes } 340238106Sdes } 341238106Sdes return res; 342238106Sdes} 343238106Sdes 344238106Sdes/** 345238106Sdes * Calculate space needed for zone and all its parents 346238106Sdes * @param d: name of zone 347238106Sdes * @param len: length of name 348238106Sdes * @return size. 349238106Sdes */ 350238106Sdesstatic size_t calc_zone_need(uint8_t* d, size_t len) 351238106Sdes{ 352238106Sdes size_t res = sizeof(struct val_neg_zone) + len; 353238106Sdes while(!dname_is_root(d)) { 354238106Sdes log_assert(len > 1); /* not root label */ 355238106Sdes dname_remove_label(&d, &len); 356238106Sdes res += sizeof(struct val_neg_zone) + len; 357238106Sdes } 358238106Sdes return res; 359238106Sdes} 360238106Sdes 361238106Sdes/** 362238106Sdes * Find closest existing parent zone of the given name. 363238106Sdes * @param neg: negative cache. 364238106Sdes * @param nm: name to look for 365238106Sdes * @param nm_len: length of nm 366238106Sdes * @param labs: labelcount of nm. 367238106Sdes * @param qclass: class. 368238106Sdes * @return the zone or NULL if none found. 369238106Sdes */ 370238106Sdesstatic struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg, 371238106Sdes uint8_t* nm, size_t nm_len, int labs, uint16_t qclass) 372238106Sdes{ 373238106Sdes struct val_neg_zone key; 374238106Sdes struct val_neg_zone* result; 375356345Scy rbnode_type* res = NULL; 376238106Sdes key.node.key = &key; 377238106Sdes key.name = nm; 378238106Sdes key.len = nm_len; 379238106Sdes key.labs = labs; 380238106Sdes key.dclass = qclass; 381238106Sdes if(rbtree_find_less_equal(&neg->tree, &key, &res)) { 382238106Sdes /* exact match */ 383238106Sdes result = (struct val_neg_zone*)res; 384238106Sdes } else { 385238106Sdes /* smaller element (or no element) */ 386238106Sdes int m; 387238106Sdes result = (struct val_neg_zone*)res; 388238106Sdes if(!result || result->dclass != qclass) 389238106Sdes return NULL; 390238106Sdes /* count number of labels matched */ 391238106Sdes (void)dname_lab_cmp(result->name, result->labs, key.name, 392238106Sdes key.labs, &m); 393238106Sdes while(result) { /* go up until qname is subdomain of stub */ 394238106Sdes if(result->labs <= m) 395238106Sdes break; 396238106Sdes result = result->parent; 397238106Sdes } 398238106Sdes } 399238106Sdes return result; 400238106Sdes} 401238106Sdes 402238106Sdes/** 403238106Sdes * Find closest existing parent data for the given name. 404238106Sdes * @param zone: to look in. 405238106Sdes * @param nm: name to look for 406238106Sdes * @param nm_len: length of nm 407238106Sdes * @param labs: labelcount of nm. 408238106Sdes * @return the data or NULL if none found. 409238106Sdes */ 410238106Sdesstatic struct val_neg_data* neg_closest_data_parent( 411238106Sdes struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs) 412238106Sdes{ 413238106Sdes struct val_neg_data key; 414238106Sdes struct val_neg_data* result; 415356345Scy rbnode_type* res = NULL; 416238106Sdes key.node.key = &key; 417238106Sdes key.name = nm; 418238106Sdes key.len = nm_len; 419238106Sdes key.labs = labs; 420238106Sdes if(rbtree_find_less_equal(&zone->tree, &key, &res)) { 421238106Sdes /* exact match */ 422238106Sdes result = (struct val_neg_data*)res; 423238106Sdes } else { 424238106Sdes /* smaller element (or no element) */ 425238106Sdes int m; 426238106Sdes result = (struct val_neg_data*)res; 427238106Sdes if(!result) 428238106Sdes return NULL; 429238106Sdes /* count number of labels matched */ 430238106Sdes (void)dname_lab_cmp(result->name, result->labs, key.name, 431238106Sdes key.labs, &m); 432238106Sdes while(result) { /* go up until qname is subdomain of stub */ 433238106Sdes if(result->labs <= m) 434238106Sdes break; 435238106Sdes result = result->parent; 436238106Sdes } 437238106Sdes } 438238106Sdes return result; 439238106Sdes} 440238106Sdes 441238106Sdes/** 442238106Sdes * Create a single zone node 443238106Sdes * @param nm: name for zone (copied) 444238106Sdes * @param nm_len: length of name 445238106Sdes * @param labs: labels in name. 446238106Sdes * @param dclass: class of zone, host order. 447238106Sdes * @return new zone or NULL on failure 448238106Sdes */ 449238106Sdesstatic struct val_neg_zone* neg_setup_zone_node( 450238106Sdes uint8_t* nm, size_t nm_len, int labs, uint16_t dclass) 451238106Sdes{ 452238106Sdes struct val_neg_zone* zone = 453238106Sdes (struct val_neg_zone*)calloc(1, sizeof(*zone)); 454238106Sdes if(!zone) { 455238106Sdes return NULL; 456238106Sdes } 457238106Sdes zone->node.key = zone; 458238106Sdes zone->name = memdup(nm, nm_len); 459238106Sdes if(!zone->name) { 460238106Sdes free(zone); 461238106Sdes return NULL; 462238106Sdes } 463238106Sdes zone->len = nm_len; 464238106Sdes zone->labs = labs; 465238106Sdes zone->dclass = dclass; 466238106Sdes 467238106Sdes rbtree_init(&zone->tree, &val_neg_data_compare); 468238106Sdes return zone; 469238106Sdes} 470238106Sdes 471238106Sdes/** 472238106Sdes * Create a linked list of parent zones, starting at longname ending on 473238106Sdes * the parent (can be NULL, creates to the root). 474238106Sdes * @param nm: name for lowest in chain 475238106Sdes * @param nm_len: length of name 476238106Sdes * @param labs: labels in name. 477238106Sdes * @param dclass: class of zone. 478238106Sdes * @param parent: NULL for to root, else so it fits under here. 479238106Sdes * @return zone; a chain of zones and their parents up to the parent. 480238106Sdes * or NULL on malloc failure 481238106Sdes */ 482238106Sdesstatic struct val_neg_zone* neg_zone_chain( 483238106Sdes uint8_t* nm, size_t nm_len, int labs, uint16_t dclass, 484238106Sdes struct val_neg_zone* parent) 485238106Sdes{ 486238106Sdes int i; 487238106Sdes int tolabs = parent?parent->labs:0; 488238106Sdes struct val_neg_zone* zone, *prev = NULL, *first = NULL; 489238106Sdes 490238106Sdes /* create the new subtree, i is labelcount of current creation */ 491238106Sdes /* this creates a 'first' to z->parent=NULL list of zones */ 492238106Sdes for(i=labs; i!=tolabs; i--) { 493238106Sdes /* create new item */ 494238106Sdes zone = neg_setup_zone_node(nm, nm_len, i, dclass); 495238106Sdes if(!zone) { 496238106Sdes /* need to delete other allocations in this routine!*/ 497238106Sdes struct val_neg_zone* p=first, *np; 498238106Sdes while(p) { 499238106Sdes np = p->parent; 500266114Sdes free(p->name); 501238106Sdes free(p); 502238106Sdes p = np; 503238106Sdes } 504238106Sdes return NULL; 505238106Sdes } 506238106Sdes if(i == labs) { 507238106Sdes first = zone; 508238106Sdes } else { 509238106Sdes prev->parent = zone; 510238106Sdes } 511238106Sdes /* prepare for next name */ 512238106Sdes prev = zone; 513238106Sdes dname_remove_label(&nm, &nm_len); 514238106Sdes } 515238106Sdes return first; 516238106Sdes} 517238106Sdes 518238106Sdesvoid val_neg_zone_take_inuse(struct val_neg_zone* zone) 519238106Sdes{ 520238106Sdes if(!zone->in_use) { 521238106Sdes struct val_neg_zone* p; 522238106Sdes zone->in_use = 1; 523238106Sdes /* increase usage count of all parents */ 524238106Sdes for(p=zone; p; p = p->parent) { 525238106Sdes p->count++; 526238106Sdes } 527238106Sdes } 528238106Sdes} 529238106Sdes 530238106Sdesstruct val_neg_zone* neg_create_zone(struct val_neg_cache* neg, 531238106Sdes uint8_t* nm, size_t nm_len, uint16_t dclass) 532238106Sdes{ 533238106Sdes struct val_neg_zone* zone; 534238106Sdes struct val_neg_zone* parent; 535238106Sdes struct val_neg_zone* p, *np; 536238106Sdes int labs = dname_count_labels(nm); 537238106Sdes 538238106Sdes /* find closest enclosing parent zone that (still) exists */ 539238106Sdes parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass); 540238106Sdes if(parent && query_dname_compare(parent->name, nm) == 0) 541238106Sdes return parent; /* already exists, weird */ 542238106Sdes /* if parent exists, it is in use */ 543238106Sdes log_assert(!parent || parent->count > 0); 544238106Sdes zone = neg_zone_chain(nm, nm_len, labs, dclass, parent); 545238106Sdes if(!zone) { 546238106Sdes return NULL; 547238106Sdes } 548238106Sdes 549238106Sdes /* insert the list of zones into the tree */ 550238106Sdes p = zone; 551238106Sdes while(p) { 552238106Sdes np = p->parent; 553238106Sdes /* mem use */ 554238106Sdes neg->use += sizeof(struct val_neg_zone) + p->len; 555238106Sdes /* insert in tree */ 556238106Sdes (void)rbtree_insert(&neg->tree, &p->node); 557238106Sdes /* last one needs proper parent pointer */ 558238106Sdes if(np == NULL) 559238106Sdes p->parent = parent; 560238106Sdes p = np; 561238106Sdes } 562238106Sdes return zone; 563238106Sdes} 564238106Sdes 565238106Sdes/** find zone name of message, returns the SOA record */ 566238106Sdesstatic struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep) 567238106Sdes{ 568238106Sdes size_t i; 569238106Sdes for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 570238106Sdes if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA) 571238106Sdes return rep->rrsets[i]; 572238106Sdes } 573238106Sdes return NULL; 574238106Sdes} 575238106Sdes 576238106Sdes/** see if the reply has NSEC records worthy of caching */ 577238106Sdesstatic int reply_has_nsec(struct reply_info* rep) 578238106Sdes{ 579238106Sdes size_t i; 580238106Sdes struct packed_rrset_data* d; 581238106Sdes if(rep->security != sec_status_secure) 582238106Sdes return 0; 583238106Sdes for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 584238106Sdes if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 585238106Sdes d = (struct packed_rrset_data*)rep->rrsets[i]-> 586238106Sdes entry.data; 587238106Sdes if(d->security == sec_status_secure) 588238106Sdes return 1; 589238106Sdes } 590238106Sdes } 591238106Sdes return 0; 592238106Sdes} 593238106Sdes 594238106Sdes 595238106Sdes/** 596238106Sdes * Create single node of data element. 597238106Sdes * @param nm: name (copied) 598238106Sdes * @param nm_len: length of name 599238106Sdes * @param labs: labels in name. 600238106Sdes * @return element with name nm, or NULL malloc failure. 601238106Sdes */ 602238106Sdesstatic struct val_neg_data* neg_setup_data_node( 603238106Sdes uint8_t* nm, size_t nm_len, int labs) 604238106Sdes{ 605238106Sdes struct val_neg_data* el; 606238106Sdes el = (struct val_neg_data*)calloc(1, sizeof(*el)); 607238106Sdes if(!el) { 608238106Sdes return NULL; 609238106Sdes } 610238106Sdes el->node.key = el; 611238106Sdes el->name = memdup(nm, nm_len); 612238106Sdes if(!el->name) { 613238106Sdes free(el); 614238106Sdes return NULL; 615238106Sdes } 616238106Sdes el->len = nm_len; 617238106Sdes el->labs = labs; 618238106Sdes return el; 619238106Sdes} 620238106Sdes 621238106Sdes/** 622238106Sdes * Create chain of data element and parents 623238106Sdes * @param nm: name 624238106Sdes * @param nm_len: length of name 625238106Sdes * @param labs: labels in name. 626238106Sdes * @param parent: up to where to make, if NULL up to root label. 627238106Sdes * @return lowest element with name nm, or NULL malloc failure. 628238106Sdes */ 629238106Sdesstatic struct val_neg_data* neg_data_chain( 630238106Sdes uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent) 631238106Sdes{ 632238106Sdes int i; 633238106Sdes int tolabs = parent?parent->labs:0; 634238106Sdes struct val_neg_data* el, *first = NULL, *prev = NULL; 635238106Sdes 636238106Sdes /* create the new subtree, i is labelcount of current creation */ 637238106Sdes /* this creates a 'first' to z->parent=NULL list of zones */ 638238106Sdes for(i=labs; i!=tolabs; i--) { 639238106Sdes /* create new item */ 640238106Sdes el = neg_setup_data_node(nm, nm_len, i); 641238106Sdes if(!el) { 642238106Sdes /* need to delete other allocations in this routine!*/ 643238106Sdes struct val_neg_data* p = first, *np; 644238106Sdes while(p) { 645238106Sdes np = p->parent; 646266114Sdes free(p->name); 647238106Sdes free(p); 648238106Sdes p = np; 649238106Sdes } 650238106Sdes return NULL; 651238106Sdes } 652238106Sdes if(i == labs) { 653238106Sdes first = el; 654238106Sdes } else { 655238106Sdes prev->parent = el; 656238106Sdes } 657238106Sdes 658238106Sdes /* prepare for next name */ 659238106Sdes prev = el; 660238106Sdes dname_remove_label(&nm, &nm_len); 661238106Sdes } 662238106Sdes return first; 663238106Sdes} 664238106Sdes 665238106Sdes/** 666238106Sdes * Remove NSEC records between start and end points. 667238106Sdes * By walking the tree, the tree is sorted canonically. 668238106Sdes * @param neg: negative cache. 669238106Sdes * @param zone: the zone 670238106Sdes * @param el: element to start walking at. 671238106Sdes * @param nsec: the nsec record with the end point 672238106Sdes */ 673238106Sdesstatic void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone, 674238106Sdes struct val_neg_data* el, struct ub_packed_rrset_key* nsec) 675238106Sdes{ 676238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> 677238106Sdes entry.data; 678238106Sdes uint8_t* end; 679238106Sdes size_t end_len; 680238106Sdes int end_labs, m; 681356345Scy rbnode_type* walk, *next; 682238106Sdes struct val_neg_data* cur; 683238106Sdes uint8_t buf[257]; 684238106Sdes /* get endpoint */ 685238106Sdes if(!d || d->count == 0 || d->rr_len[0] < 2+1) 686238106Sdes return; 687238106Sdes if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) { 688238106Sdes end = d->rr_data[0]+2; 689238106Sdes end_len = dname_valid(end, d->rr_len[0]-2); 690238106Sdes end_labs = dname_count_labels(end); 691238106Sdes } else { 692238106Sdes /* NSEC3 */ 693238106Sdes if(!nsec3_get_nextowner_b32(nsec, 0, buf, sizeof(buf))) 694238106Sdes return; 695238106Sdes end = buf; 696238106Sdes end_labs = dname_count_size_labels(end, &end_len); 697238106Sdes } 698238106Sdes 699238106Sdes /* sanity check, both owner and end must be below the zone apex */ 700238106Sdes if(!dname_subdomain_c(el->name, zone->name) || 701238106Sdes !dname_subdomain_c(end, zone->name)) 702238106Sdes return; 703238106Sdes 704238106Sdes /* detect end of zone NSEC ; wipe until the end of zone */ 705238106Sdes if(query_dname_compare(end, zone->name) == 0) { 706238106Sdes end = NULL; 707238106Sdes } 708238106Sdes 709238106Sdes walk = rbtree_next(&el->node); 710238106Sdes while(walk && walk != RBTREE_NULL) { 711238106Sdes cur = (struct val_neg_data*)walk; 712238106Sdes /* sanity check: must be larger than start */ 713238106Sdes if(dname_canon_lab_cmp(cur->name, cur->labs, 714238106Sdes el->name, el->labs, &m) <= 0) { 715238106Sdes /* r == 0 skip original record. */ 716238106Sdes /* r < 0 too small! */ 717238106Sdes walk = rbtree_next(walk); 718238106Sdes continue; 719238106Sdes } 720238106Sdes /* stop at endpoint, also data at empty nonterminals must be 721238106Sdes * removed (no NSECs there) so everything between 722238106Sdes * start and end */ 723238106Sdes if(end && dname_canon_lab_cmp(cur->name, cur->labs, 724238106Sdes end, end_labs, &m) >= 0) { 725238106Sdes break; 726238106Sdes } 727238106Sdes /* this element has to be deleted, but we cannot do it 728238106Sdes * now, because we are walking the tree still ... */ 729238106Sdes /* get the next element: */ 730238106Sdes next = rbtree_next(walk); 731238106Sdes /* now delete the original element, this may trigger 732238106Sdes * rbtree rebalances, but really, the next element is 733238106Sdes * the one we need. 734238106Sdes * But it may trigger delete of other data and the 735238106Sdes * entire zone. However, if that happens, this is done 736238106Sdes * by deleting the *parents* of the element for deletion, 737238106Sdes * and maybe also the entire zone if it is empty. 738238106Sdes * But parents are smaller in canonical compare, thus, 739238106Sdes * if a larger element exists, then it is not a parent, 740238106Sdes * it cannot get deleted, the zone cannot get empty. 741238106Sdes * If the next==NULL, then zone can be empty. */ 742238106Sdes if(cur->in_use) 743238106Sdes neg_delete_data(neg, cur); 744238106Sdes walk = next; 745238106Sdes } 746238106Sdes} 747238106Sdes 748238106Sdesvoid neg_insert_data(struct val_neg_cache* neg, 749238106Sdes struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec) 750238106Sdes{ 751238106Sdes struct packed_rrset_data* d; 752238106Sdes struct val_neg_data* parent; 753238106Sdes struct val_neg_data* el; 754238106Sdes uint8_t* nm = nsec->rk.dname; 755238106Sdes size_t nm_len = nsec->rk.dname_len; 756238106Sdes int labs = dname_count_labels(nsec->rk.dname); 757238106Sdes 758238106Sdes d = (struct packed_rrset_data*)nsec->entry.data; 759238106Sdes if( !(d->security == sec_status_secure || 760238106Sdes (d->security == sec_status_unchecked && d->rrsig_count > 0))) 761238106Sdes return; 762238106Sdes log_nametypeclass(VERB_ALGO, "negcache rr", 763238106Sdes nsec->rk.dname, ntohs(nsec->rk.type), 764238106Sdes ntohs(nsec->rk.rrset_class)); 765238106Sdes 766238106Sdes /* find closest enclosing parent data that (still) exists */ 767238106Sdes parent = neg_closest_data_parent(zone, nm, nm_len, labs); 768238106Sdes if(parent && query_dname_compare(parent->name, nm) == 0) { 769238106Sdes /* perfect match already exists */ 770238106Sdes log_assert(parent->count > 0); 771238106Sdes el = parent; 772238106Sdes } else { 773238106Sdes struct val_neg_data* p, *np; 774238106Sdes 775238106Sdes /* create subtree for perfect match */ 776238106Sdes /* if parent exists, it is in use */ 777238106Sdes log_assert(!parent || parent->count > 0); 778238106Sdes 779238106Sdes el = neg_data_chain(nm, nm_len, labs, parent); 780238106Sdes if(!el) { 781238106Sdes log_err("out of memory inserting NSEC negative cache"); 782238106Sdes return; 783238106Sdes } 784238106Sdes el->in_use = 0; /* set on below */ 785238106Sdes 786238106Sdes /* insert the list of zones into the tree */ 787238106Sdes p = el; 788238106Sdes while(p) { 789238106Sdes np = p->parent; 790238106Sdes /* mem use */ 791238106Sdes neg->use += sizeof(struct val_neg_data) + p->len; 792238106Sdes /* insert in tree */ 793238106Sdes p->zone = zone; 794238106Sdes (void)rbtree_insert(&zone->tree, &p->node); 795238106Sdes /* last one needs proper parent pointer */ 796238106Sdes if(np == NULL) 797238106Sdes p->parent = parent; 798238106Sdes p = np; 799238106Sdes } 800238106Sdes } 801238106Sdes 802238106Sdes if(!el->in_use) { 803238106Sdes struct val_neg_data* p; 804238106Sdes 805238106Sdes el->in_use = 1; 806238106Sdes /* increase usage count of all parents */ 807238106Sdes for(p=el; p; p = p->parent) { 808238106Sdes p->count++; 809238106Sdes } 810238106Sdes 811238106Sdes neg_lru_front(neg, el); 812238106Sdes } else { 813238106Sdes /* in use, bring to front, lru */ 814238106Sdes neg_lru_touch(neg, el); 815238106Sdes } 816238106Sdes 817238106Sdes /* if nsec3 store last used parameters */ 818238106Sdes if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) { 819238106Sdes int h; 820238106Sdes uint8_t* s; 821238106Sdes size_t slen, it; 822238106Sdes if(nsec3_get_params(nsec, 0, &h, &it, &s, &slen) && 823238106Sdes it <= neg->nsec3_max_iter && 824238106Sdes (h != zone->nsec3_hash || it != zone->nsec3_iter || 825238106Sdes slen != zone->nsec3_saltlen || 826238106Sdes memcmp(zone->nsec3_salt, s, slen) != 0)) { 827296415Sdes 828296415Sdes if(slen > 0) { 829296415Sdes uint8_t* sa = memdup(s, slen); 830296415Sdes if(sa) { 831296415Sdes free(zone->nsec3_salt); 832296415Sdes zone->nsec3_salt = sa; 833296415Sdes zone->nsec3_saltlen = slen; 834296415Sdes zone->nsec3_iter = it; 835296415Sdes zone->nsec3_hash = h; 836296415Sdes } 837296415Sdes } else { 838238106Sdes free(zone->nsec3_salt); 839296415Sdes zone->nsec3_salt = NULL; 840296415Sdes zone->nsec3_saltlen = 0; 841296415Sdes zone->nsec3_iter = it; 842238106Sdes zone->nsec3_hash = h; 843238106Sdes } 844238106Sdes } 845238106Sdes } 846238106Sdes 847238106Sdes /* wipe out the cache items between NSEC start and end */ 848238106Sdes wipeout(neg, zone, el, nsec); 849238106Sdes} 850238106Sdes 851356345Scy/** see if the reply has signed NSEC records and return the signer */ 852356345Scystatic uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len, 853356345Scy uint16_t* dclass) 854356345Scy{ 855356345Scy size_t i; 856356345Scy struct packed_rrset_data* d; 857356345Scy uint8_t* s; 858356345Scy for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 859356345Scy if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC || 860356345Scy ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) { 861356345Scy d = (struct packed_rrset_data*)rep->rrsets[i]-> 862356345Scy entry.data; 863356345Scy /* return first signer name of first NSEC */ 864356345Scy if(d->rrsig_count != 0) { 865356345Scy val_find_rrset_signer(rep->rrsets[i], 866356345Scy &s, signer_len); 867356345Scy if(s && *signer_len) { 868356345Scy *dclass = ntohs(rep->rrsets[i]-> 869356345Scy rk.rrset_class); 870356345Scy return s; 871356345Scy } 872356345Scy } 873356345Scy } 874356345Scy } 875356345Scy return 0; 876356345Scy} 877356345Scy 878238106Sdesvoid val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep) 879238106Sdes{ 880238106Sdes size_t i, need; 881238106Sdes struct ub_packed_rrset_key* soa; 882356345Scy uint8_t* dname = NULL; 883356345Scy size_t dname_len; 884356345Scy uint16_t rrset_class; 885238106Sdes struct val_neg_zone* zone; 886238106Sdes /* see if secure nsecs inside */ 887238106Sdes if(!reply_has_nsec(rep)) 888238106Sdes return; 889238106Sdes /* find the zone name in message */ 890356345Scy if((soa = reply_find_soa(rep))) { 891356345Scy dname = soa->rk.dname; 892356345Scy dname_len = soa->rk.dname_len; 893356345Scy rrset_class = ntohs(soa->rk.rrset_class); 894356345Scy } 895356345Scy else { 896356345Scy /* No SOA in positive (wildcard) answer. Use signer from the 897356345Scy * validated answer RRsets' signature. */ 898356345Scy if(!(dname = reply_nsec_signer(rep, &dname_len, &rrset_class))) 899356345Scy return; 900356345Scy } 901238106Sdes 902238106Sdes log_nametypeclass(VERB_ALGO, "negcache insert for zone", 903356345Scy dname, LDNS_RR_TYPE_SOA, rrset_class); 904238106Sdes 905238106Sdes /* ask for enough space to store all of it */ 906238106Sdes need = calc_data_need(rep) + 907356345Scy calc_zone_need(dname, dname_len); 908238106Sdes lock_basic_lock(&neg->lock); 909238106Sdes neg_make_space(neg, need); 910238106Sdes 911238106Sdes /* find or create the zone entry */ 912356345Scy zone = neg_find_zone(neg, dname, dname_len, rrset_class); 913238106Sdes if(!zone) { 914356345Scy if(!(zone = neg_create_zone(neg, dname, dname_len, 915356345Scy rrset_class))) { 916238106Sdes lock_basic_unlock(&neg->lock); 917238106Sdes log_err("out of memory adding negative zone"); 918238106Sdes return; 919238106Sdes } 920238106Sdes } 921238106Sdes val_neg_zone_take_inuse(zone); 922238106Sdes 923238106Sdes /* insert the NSECs */ 924238106Sdes for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 925238106Sdes if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC) 926238106Sdes continue; 927238106Sdes if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 928238106Sdes zone->name)) continue; 929238106Sdes /* insert NSEC into this zone's tree */ 930238106Sdes neg_insert_data(neg, zone, rep->rrsets[i]); 931238106Sdes } 932238106Sdes if(zone->tree.count == 0) { 933238106Sdes /* remove empty zone if inserts failed */ 934238106Sdes neg_delete_zone(neg, zone); 935238106Sdes } 936238106Sdes lock_basic_unlock(&neg->lock); 937238106Sdes} 938238106Sdes 939238106Sdes/** 940238106Sdes * Lookup closest data record. For NSEC denial. 941238106Sdes * @param zone: zone to look in 942238106Sdes * @param qname: name to look for. 943238106Sdes * @param len: length of name 944238106Sdes * @param labs: labels in name 945238106Sdes * @param data: data element, exact or smaller or NULL 946238106Sdes * @return true if exact match. 947238106Sdes */ 948238106Sdesstatic int neg_closest_data(struct val_neg_zone* zone, 949238106Sdes uint8_t* qname, size_t len, int labs, struct val_neg_data** data) 950238106Sdes{ 951238106Sdes struct val_neg_data key; 952356345Scy rbnode_type* r; 953238106Sdes key.node.key = &key; 954238106Sdes key.name = qname; 955238106Sdes key.len = len; 956238106Sdes key.labs = labs; 957238106Sdes if(rbtree_find_less_equal(&zone->tree, &key, &r)) { 958238106Sdes /* exact match */ 959238106Sdes *data = (struct val_neg_data*)r; 960238106Sdes return 1; 961238106Sdes } else { 962238106Sdes /* smaller match */ 963238106Sdes *data = (struct val_neg_data*)r; 964238106Sdes return 0; 965238106Sdes } 966238106Sdes} 967238106Sdes 968238106Sdesvoid val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep, 969238106Sdes uint8_t* zone_name) 970238106Sdes{ 971238106Sdes size_t i, need; 972238106Sdes uint8_t* signer; 973238106Sdes size_t signer_len; 974238106Sdes uint16_t dclass; 975238106Sdes struct val_neg_zone* zone; 976238106Sdes /* no SOA in this message, find RRSIG over NSEC's signer name. 977238106Sdes * note the NSEC records are maybe not validated yet */ 978238106Sdes signer = reply_nsec_signer(rep, &signer_len, &dclass); 979238106Sdes if(!signer) 980238106Sdes return; 981238106Sdes if(!dname_subdomain_c(signer, zone_name)) { 982238106Sdes /* the signer is not in the bailiwick, throw it out */ 983238106Sdes return; 984238106Sdes } 985238106Sdes 986238106Sdes log_nametypeclass(VERB_ALGO, "negcache insert referral ", 987238106Sdes signer, LDNS_RR_TYPE_NS, dclass); 988238106Sdes 989238106Sdes /* ask for enough space to store all of it */ 990238106Sdes need = calc_data_need(rep) + calc_zone_need(signer, signer_len); 991238106Sdes lock_basic_lock(&neg->lock); 992238106Sdes neg_make_space(neg, need); 993238106Sdes 994238106Sdes /* find or create the zone entry */ 995238106Sdes zone = neg_find_zone(neg, signer, signer_len, dclass); 996238106Sdes if(!zone) { 997238106Sdes if(!(zone = neg_create_zone(neg, signer, signer_len, 998238106Sdes dclass))) { 999238106Sdes lock_basic_unlock(&neg->lock); 1000238106Sdes log_err("out of memory adding negative zone"); 1001238106Sdes return; 1002238106Sdes } 1003238106Sdes } 1004238106Sdes val_neg_zone_take_inuse(zone); 1005238106Sdes 1006238106Sdes /* insert the NSECs */ 1007238106Sdes for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 1008238106Sdes if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC && 1009238106Sdes ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3) 1010238106Sdes continue; 1011238106Sdes if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 1012238106Sdes zone->name)) continue; 1013238106Sdes /* insert NSEC into this zone's tree */ 1014238106Sdes neg_insert_data(neg, zone, rep->rrsets[i]); 1015238106Sdes } 1016238106Sdes if(zone->tree.count == 0) { 1017238106Sdes /* remove empty zone if inserts failed */ 1018238106Sdes neg_delete_zone(neg, zone); 1019238106Sdes } 1020238106Sdes lock_basic_unlock(&neg->lock); 1021238106Sdes} 1022238106Sdes 1023238106Sdes/** 1024238106Sdes * Check that an NSEC3 rrset does not have a type set. 1025238106Sdes * None of the nsec3s in a hash-collision are allowed to have the type. 1026238106Sdes * (since we do not know which one is the nsec3 looked at, flags, ..., we 1027238106Sdes * ignore the cached item and let it bypass negative caching). 1028238106Sdes * @param k: the nsec3 rrset to check. 1029238106Sdes * @param t: type to check 1030238106Sdes * @return true if no RRs have the type. 1031238106Sdes */ 1032238106Sdesstatic int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t) 1033238106Sdes{ 1034238106Sdes int count = (int)((struct packed_rrset_data*)k->entry.data)->count; 1035238106Sdes int i; 1036238106Sdes for(i=0; i<count; i++) 1037238106Sdes if(nsec3_has_type(k, i, t)) 1038238106Sdes return 0; 1039238106Sdes return 1; 1040238106Sdes} 1041238106Sdes 1042238106Sdes/** 1043238106Sdes * See if rrset exists in rrset cache. 1044238106Sdes * If it does, the bit is checked, and if not expired, it is returned 1045238106Sdes * allocated in region. 1046238106Sdes * @param rrset_cache: rrset cache 1047238106Sdes * @param qname: to lookup rrset name 1048238106Sdes * @param qname_len: length of qname. 1049238106Sdes * @param qtype: type of rrset to lookup, host order 1050238106Sdes * @param qclass: class of rrset to lookup, host order 1051238106Sdes * @param flags: flags for rrset to lookup 1052238106Sdes * @param region: where to alloc result 1053238106Sdes * @param checkbit: if true, a bit in the nsec typemap is checked for absence. 1054238106Sdes * @param checktype: which bit to check 1055238106Sdes * @param now: to check ttl against 1056238106Sdes * @return rrset or NULL 1057238106Sdes */ 1058238106Sdesstatic struct ub_packed_rrset_key* 1059238106Sdesgrab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len, 1060238106Sdes uint16_t qtype, uint16_t qclass, uint32_t flags, 1061238106Sdes struct regional* region, int checkbit, uint16_t checktype, 1062266114Sdes time_t now) 1063238106Sdes{ 1064238106Sdes struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache, 1065238106Sdes qname, qname_len, qtype, qclass, flags, now, 0); 1066238106Sdes struct packed_rrset_data* d; 1067238106Sdes if(!k) return NULL; 1068238106Sdes d = (struct packed_rrset_data*)k->entry.data; 1069238106Sdes if(d->ttl < now) { 1070238106Sdes lock_rw_unlock(&k->entry.lock); 1071238106Sdes return NULL; 1072238106Sdes } 1073238106Sdes /* only secure or unchecked records that have signatures. */ 1074238106Sdes if( ! ( d->security == sec_status_secure || 1075238106Sdes (d->security == sec_status_unchecked && 1076238106Sdes d->rrsig_count > 0) ) ) { 1077238106Sdes lock_rw_unlock(&k->entry.lock); 1078238106Sdes return NULL; 1079238106Sdes } 1080238106Sdes /* check if checktype is absent */ 1081238106Sdes if(checkbit && ( 1082238106Sdes (qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) || 1083238106Sdes (qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype)) 1084238106Sdes )) { 1085238106Sdes lock_rw_unlock(&k->entry.lock); 1086238106Sdes return NULL; 1087238106Sdes } 1088238106Sdes /* looks OK! copy to region and return it */ 1089238106Sdes r = packed_rrset_copy_region(k, region, now); 1090238106Sdes /* if it failed, we return the NULL */ 1091238106Sdes lock_rw_unlock(&k->entry.lock); 1092238106Sdes return r; 1093238106Sdes} 1094238106Sdes 1095356345Scy/** 1096356345Scy * Get best NSEC record for qname. Might be matching, covering or totally 1097356345Scy * useless. 1098356345Scy * @param neg_cache: neg cache 1099356345Scy * @param qname: to lookup rrset name 1100356345Scy * @param qname_len: length of qname. 1101356345Scy * @param qclass: class of rrset to lookup, host order 1102356345Scy * @param rrset_cache: rrset cache 1103356345Scy * @param now: to check ttl against 1104356345Scy * @param region: where to alloc result 1105356345Scy * @return rrset or NULL 1106356345Scy */ 1107356345Scystatic struct ub_packed_rrset_key* 1108356345Scyneg_find_nsec(struct val_neg_cache* neg_cache, uint8_t* qname, size_t qname_len, 1109356345Scy uint16_t qclass, struct rrset_cache* rrset_cache, time_t now, 1110356345Scy struct regional* region) 1111356345Scy{ 1112356345Scy int labs; 1113356345Scy uint32_t flags; 1114356345Scy struct val_neg_zone* zone; 1115356345Scy struct val_neg_data* data; 1116356345Scy struct ub_packed_rrset_key* nsec; 1117356345Scy 1118356345Scy labs = dname_count_labels(qname); 1119356345Scy lock_basic_lock(&neg_cache->lock); 1120356345Scy zone = neg_closest_zone_parent(neg_cache, qname, qname_len, labs, 1121356345Scy qclass); 1122356345Scy while(zone && !zone->in_use) 1123356345Scy zone = zone->parent; 1124356345Scy if(!zone) { 1125356345Scy lock_basic_unlock(&neg_cache->lock); 1126356345Scy return NULL; 1127356345Scy } 1128356345Scy 1129356345Scy /* NSEC only for now */ 1130356345Scy if(zone->nsec3_hash) { 1131356345Scy lock_basic_unlock(&neg_cache->lock); 1132356345Scy return NULL; 1133356345Scy } 1134356345Scy 1135356345Scy /* ignore return value, don't care if it is an exact or smaller match */ 1136356345Scy (void)neg_closest_data(zone, qname, qname_len, labs, &data); 1137356345Scy if(!data) { 1138356345Scy lock_basic_unlock(&neg_cache->lock); 1139356345Scy return NULL; 1140356345Scy } 1141356345Scy 1142356345Scy /* ENT nodes are not in use, try the previous node. If the previous node 1143356345Scy * is not in use, we don't have an useful NSEC and give up. */ 1144356345Scy if(!data->in_use) { 1145356345Scy data = (struct val_neg_data*)rbtree_previous((rbnode_type*)data); 1146356345Scy if((rbnode_type*)data == RBTREE_NULL || !data->in_use) { 1147356345Scy lock_basic_unlock(&neg_cache->lock); 1148356345Scy return NULL; 1149356345Scy } 1150356345Scy } 1151356345Scy 1152356345Scy flags = 0; 1153356345Scy if(query_dname_compare(data->name, zone->name) == 0) 1154356345Scy flags = PACKED_RRSET_NSEC_AT_APEX; 1155356345Scy 1156356345Scy nsec = grab_nsec(rrset_cache, data->name, data->len, LDNS_RR_TYPE_NSEC, 1157356345Scy zone->dclass, flags, region, 0, 0, now); 1158356345Scy lock_basic_unlock(&neg_cache->lock); 1159356345Scy return nsec; 1160356345Scy} 1161356345Scy 1162238106Sdes/** find nsec3 closest encloser in neg cache */ 1163238106Sdesstatic struct val_neg_data* 1164238106Sdesneg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 1165266114Sdes int qlabs, sldns_buffer* buf, uint8_t* hashnc, size_t* nclen) 1166238106Sdes{ 1167238106Sdes struct val_neg_data* data; 1168249141Sdes uint8_t hashce[NSEC3_SHA_LEN]; 1169238106Sdes uint8_t b32[257]; 1170238106Sdes size_t celen, b32len; 1171238106Sdes 1172238106Sdes *nclen = 0; 1173238106Sdes while(qlabs > 0) { 1174238106Sdes /* hash */ 1175238106Sdes if(!(celen=nsec3_get_hashed(buf, qname, qname_len, 1176238106Sdes zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt, 1177238106Sdes zone->nsec3_saltlen, hashce, sizeof(hashce)))) 1178238106Sdes return NULL; 1179238106Sdes if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name, 1180238106Sdes zone->len, b32, sizeof(b32)))) 1181238106Sdes return NULL; 1182238106Sdes 1183238106Sdes /* lookup (exact match only) */ 1184238106Sdes data = neg_find_data(zone, b32, b32len, zone->labs+1); 1185238106Sdes if(data && data->in_use) { 1186238106Sdes /* found ce match! */ 1187238106Sdes return data; 1188238106Sdes } 1189238106Sdes 1190238106Sdes *nclen = celen; 1191238106Sdes memmove(hashnc, hashce, celen); 1192238106Sdes dname_remove_label(&qname, &qname_len); 1193238106Sdes qlabs --; 1194238106Sdes } 1195238106Sdes return NULL; 1196238106Sdes} 1197238106Sdes 1198238106Sdes/** check nsec3 parameters on nsec3 rrset with current zone values */ 1199238106Sdesstatic int 1200238106Sdesneg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset) 1201238106Sdes{ 1202238106Sdes int h; 1203238106Sdes uint8_t* s; 1204238106Sdes size_t slen, it; 1205238106Sdes if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen)) 1206238106Sdes return 0; 1207238106Sdes return (h == zone->nsec3_hash && it == zone->nsec3_iter && 1208238106Sdes slen == zone->nsec3_saltlen && 1209238106Sdes memcmp(zone->nsec3_salt, s, slen) == 0); 1210238106Sdes} 1211238106Sdes 1212238106Sdes/** get next closer for nsec3 proof */ 1213238106Sdesstatic struct ub_packed_rrset_key* 1214238106Sdesneg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen, 1215238106Sdes struct rrset_cache* rrset_cache, struct regional* region, 1216266114Sdes time_t now, uint8_t* b32, size_t maxb32) 1217238106Sdes{ 1218238106Sdes struct ub_packed_rrset_key* nc_rrset; 1219238106Sdes struct val_neg_data* data; 1220238106Sdes size_t b32len; 1221238106Sdes 1222238106Sdes if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name, 1223238106Sdes zone->len, b32, maxb32))) 1224238106Sdes return NULL; 1225238106Sdes (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data); 1226238106Sdes if(!data && zone->tree.count != 0) { 1227238106Sdes /* could be before the first entry ; return the last 1228238106Sdes * entry (possibly the rollover nsec3 at end) */ 1229238106Sdes data = (struct val_neg_data*)rbtree_last(&zone->tree); 1230238106Sdes } 1231238106Sdes while(data && !data->in_use) 1232238106Sdes data = data->parent; 1233238106Sdes if(!data) 1234238106Sdes return NULL; 1235238106Sdes /* got a data element in tree, grab it */ 1236238106Sdes nc_rrset = grab_nsec(rrset_cache, data->name, data->len, 1237238106Sdes LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now); 1238238106Sdes if(!nc_rrset) 1239238106Sdes return NULL; 1240238106Sdes if(!neg_params_ok(zone, nc_rrset)) 1241238106Sdes return NULL; 1242238106Sdes return nc_rrset; 1243238106Sdes} 1244238106Sdes 1245238106Sdes/** neg cache nsec3 proof procedure*/ 1246238106Sdesstatic struct dns_msg* 1247238106Sdesneg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 1248266114Sdes int qlabs, sldns_buffer* buf, struct rrset_cache* rrset_cache, 1249266114Sdes struct regional* region, time_t now, uint8_t* topname) 1250238106Sdes{ 1251238106Sdes struct dns_msg* msg; 1252238106Sdes struct val_neg_data* data; 1253249141Sdes uint8_t hashnc[NSEC3_SHA_LEN]; 1254238106Sdes size_t nclen; 1255238106Sdes struct ub_packed_rrset_key* ce_rrset, *nc_rrset; 1256238106Sdes struct nsec3_cached_hash c; 1257238106Sdes uint8_t nc_b32[257]; 1258238106Sdes 1259238106Sdes /* for NSEC3 ; determine the closest encloser for which we 1260238106Sdes * can find an exact match. Remember the hashed lower name, 1261238106Sdes * since that is the one we need a closest match for. 1262238106Sdes * If we find a match straight away, then it becomes NODATA. 1263238106Sdes * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation. 1264238106Sdes * Also check that parameters are the same on closest encloser 1265238106Sdes * and on closest match. 1266238106Sdes */ 1267238106Sdes if(!zone->nsec3_hash) 1268238106Sdes return NULL; /* not nsec3 zone */ 1269238106Sdes 1270238106Sdes if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf, 1271238106Sdes hashnc, &nclen))) { 1272238106Sdes return NULL; 1273238106Sdes } 1274238106Sdes 1275238106Sdes /* grab the ce rrset */ 1276238106Sdes ce_rrset = grab_nsec(rrset_cache, data->name, data->len, 1277238106Sdes LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1, 1278238106Sdes LDNS_RR_TYPE_DS, now); 1279238106Sdes if(!ce_rrset) 1280238106Sdes return NULL; 1281238106Sdes if(!neg_params_ok(zone, ce_rrset)) 1282238106Sdes return NULL; 1283238106Sdes 1284238106Sdes if(nclen == 0) { 1285238106Sdes /* exact match, just check the type bits */ 1286238106Sdes /* need: -SOA, -DS, +NS */ 1287238106Sdes if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) || 1288238106Sdes nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) || 1289238106Sdes !nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS)) 1290238106Sdes return NULL; 1291238106Sdes if(!(msg = dns_msg_create(qname, qname_len, 1292238106Sdes LDNS_RR_TYPE_DS, zone->dclass, region, 1))) 1293238106Sdes return NULL; 1294238106Sdes /* TTL reduced in grab_nsec */ 1295238106Sdes if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1296238106Sdes return NULL; 1297238106Sdes return msg; 1298238106Sdes } 1299238106Sdes 1300238106Sdes /* optout is not allowed without knowing the trust-anchor in use, 1301238106Sdes * otherwise the optout could spoof away that anchor */ 1302238106Sdes if(!topname) 1303238106Sdes return NULL; 1304238106Sdes 1305238106Sdes /* if there is no exact match, it must be in an optout span 1306238106Sdes * (an existing DS implies an NSEC3 must exist) */ 1307238106Sdes nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache, 1308238106Sdes region, now, nc_b32, sizeof(nc_b32)); 1309238106Sdes if(!nc_rrset) 1310238106Sdes return NULL; 1311238106Sdes if(!neg_params_ok(zone, nc_rrset)) 1312238106Sdes return NULL; 1313238106Sdes if(!nsec3_has_optout(nc_rrset, 0)) 1314238106Sdes return NULL; 1315238106Sdes c.hash = hashnc; 1316238106Sdes c.hash_len = nclen; 1317238106Sdes c.b32 = nc_b32+1; 1318238106Sdes c.b32_len = (size_t)nc_b32[0]; 1319238106Sdes if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) { 1320238106Sdes /* nc_rrset covers the next closer name. 1321238106Sdes * ce_rrset equals a closer encloser. 1322238106Sdes * nc_rrset is optout. 1323238106Sdes * No need to check wildcard for type DS */ 1324238106Sdes /* capacity=3: ce + nc + soa(if needed) */ 1325238106Sdes if(!(msg = dns_msg_create(qname, qname_len, 1326238106Sdes LDNS_RR_TYPE_DS, zone->dclass, region, 3))) 1327238106Sdes return NULL; 1328238106Sdes /* now=0 because TTL was reduced in grab_nsec */ 1329238106Sdes if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1330238106Sdes return NULL; 1331238106Sdes if(!dns_msg_authadd(msg, region, nc_rrset, 0)) 1332238106Sdes return NULL; 1333238106Sdes return msg; 1334238106Sdes } 1335238106Sdes return NULL; 1336238106Sdes} 1337238106Sdes 1338238106Sdes/** 1339238106Sdes * Add SOA record for external responses. 1340238106Sdes * @param rrset_cache: to look into. 1341238106Sdes * @param now: current time. 1342238106Sdes * @param region: where to perform the allocation 1343238106Sdes * @param msg: current msg with NSEC. 1344238106Sdes * @param zone: val_neg_zone if we have one. 1345238106Sdes * @return false on lookup or alloc failure. 1346238106Sdes */ 1347266114Sdesstatic int add_soa(struct rrset_cache* rrset_cache, time_t now, 1348238106Sdes struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone) 1349238106Sdes{ 1350238106Sdes struct ub_packed_rrset_key* soa; 1351238106Sdes uint8_t* nm; 1352238106Sdes size_t nmlen; 1353238106Sdes uint16_t dclass; 1354238106Sdes if(zone) { 1355238106Sdes nm = zone->name; 1356238106Sdes nmlen = zone->len; 1357238106Sdes dclass = zone->dclass; 1358238106Sdes } else { 1359238106Sdes /* Assumes the signer is the zone SOA to add */ 1360238106Sdes nm = reply_nsec_signer(msg->rep, &nmlen, &dclass); 1361238106Sdes if(!nm) 1362238106Sdes return 0; 1363238106Sdes } 1364238106Sdes soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA, 1365238106Sdes dclass, PACKED_RRSET_SOA_NEG, now, 0); 1366238106Sdes if(!soa) 1367238106Sdes return 0; 1368238106Sdes if(!dns_msg_authadd(msg, region, soa, now)) { 1369238106Sdes lock_rw_unlock(&soa->entry.lock); 1370238106Sdes return 0; 1371238106Sdes } 1372238106Sdes lock_rw_unlock(&soa->entry.lock); 1373238106Sdes return 1; 1374238106Sdes} 1375238106Sdes 1376238106Sdesstruct dns_msg* 1377238106Sdesval_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo, 1378238106Sdes struct regional* region, struct rrset_cache* rrset_cache, 1379356345Scy sldns_buffer* buf, time_t now, int addsoa, uint8_t* topname, 1380356345Scy struct config_file* cfg) 1381238106Sdes{ 1382238106Sdes struct dns_msg* msg; 1383356345Scy struct ub_packed_rrset_key* nsec; /* qname matching/covering nsec */ 1384356345Scy struct ub_packed_rrset_key* wcrr; /* wildcard record or nsec */ 1385356345Scy uint8_t* nodata_wc = NULL; 1386356345Scy uint8_t* ce = NULL; 1387356345Scy size_t ce_len; 1388356345Scy uint8_t wc_ce[LDNS_MAX_DOMAINLEN+3]; 1389356345Scy struct query_info wc_qinfo; 1390356345Scy struct ub_packed_rrset_key* cache_wc; 1391356345Scy struct packed_rrset_data* wcrr_data; 1392356345Scy int rcode = LDNS_RCODE_NOERROR; 1393238106Sdes uint8_t* zname; 1394238106Sdes size_t zname_len; 1395238106Sdes int zname_labs; 1396238106Sdes struct val_neg_zone* zone; 1397238106Sdes 1398356345Scy /* only for DS queries when aggressive use of NSEC is disabled */ 1399356345Scy if(qinfo->qtype != LDNS_RR_TYPE_DS && !cfg->aggressive_nsec) 1400238106Sdes return NULL; 1401238106Sdes log_assert(!topname || dname_subdomain_c(qinfo->qname, topname)); 1402238106Sdes 1403356345Scy /* Get best available NSEC for qname */ 1404356345Scy nsec = neg_find_nsec(neg, qinfo->qname, qinfo->qname_len, qinfo->qclass, 1405356345Scy rrset_cache, now, region); 1406356345Scy 1407356345Scy /* Matching NSEC, use to generate No Data answer. Not creating answers 1408356345Scy * yet for No Data proven using wildcard. */ 1409356345Scy if(nsec && nsec_proves_nodata(nsec, qinfo, &nodata_wc) && !nodata_wc) { 1410238106Sdes if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 1411238106Sdes qinfo->qtype, qinfo->qclass, region, 2))) 1412238106Sdes return NULL; 1413356345Scy if(!dns_msg_authadd(msg, region, nsec, 0)) 1414238106Sdes return NULL; 1415238106Sdes if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL)) 1416238106Sdes return NULL; 1417356345Scy 1418356345Scy lock_basic_lock(&neg->lock); 1419356345Scy neg->num_neg_cache_noerror++; 1420356345Scy lock_basic_unlock(&neg->lock); 1421238106Sdes return msg; 1422356345Scy } else if(nsec && val_nsec_proves_name_error(nsec, qinfo->qname)) { 1423356345Scy if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 1424356345Scy qinfo->qtype, qinfo->qclass, region, 3))) 1425356345Scy return NULL; 1426356345Scy if(!(ce = nsec_closest_encloser(qinfo->qname, nsec))) 1427356345Scy return NULL; 1428356345Scy dname_count_size_labels(ce, &ce_len); 1429356345Scy 1430356345Scy /* No extra extra NSEC required if both nameerror qname and 1431356345Scy * nodata *.ce. are proven already. */ 1432356345Scy if(!nodata_wc || query_dname_compare(nodata_wc, ce) != 0) { 1433356345Scy /* Qname proven non existing, get wildcard record for 1434356345Scy * QTYPE or NSEC covering or matching wildcard. */ 1435356345Scy 1436356345Scy /* Num labels in ce is always smaller than in qname, 1437356345Scy * therefore adding the wildcard label cannot overflow 1438356345Scy * buffer. */ 1439356345Scy wc_ce[0] = 1; 1440356345Scy wc_ce[1] = (uint8_t)'*'; 1441356345Scy memmove(wc_ce+2, ce, ce_len); 1442356345Scy wc_qinfo.qname = wc_ce; 1443356345Scy wc_qinfo.qname_len = ce_len + 2; 1444356345Scy wc_qinfo.qtype = qinfo->qtype; 1445356345Scy 1446356345Scy 1447356345Scy if((cache_wc = rrset_cache_lookup(rrset_cache, wc_qinfo.qname, 1448356345Scy wc_qinfo.qname_len, wc_qinfo.qtype, 1449356345Scy qinfo->qclass, 0/*flags*/, now, 0/*read only*/))) { 1450356345Scy /* Synthesize wildcard answer */ 1451356345Scy wcrr_data = (struct packed_rrset_data*)cache_wc->entry.data; 1452356345Scy if(!(wcrr_data->security == sec_status_secure || 1453356345Scy (wcrr_data->security == sec_status_unchecked && 1454356345Scy wcrr_data->rrsig_count > 0))) { 1455356345Scy lock_rw_unlock(&cache_wc->entry.lock); 1456356345Scy return NULL; 1457356345Scy } 1458356345Scy if(!(wcrr = packed_rrset_copy_region(cache_wc, 1459356345Scy region, now))) { 1460356345Scy lock_rw_unlock(&cache_wc->entry.lock); 1461356345Scy return NULL; 1462356345Scy }; 1463356345Scy lock_rw_unlock(&cache_wc->entry.lock); 1464356345Scy wcrr->rk.dname = qinfo->qname; 1465356345Scy wcrr->rk.dname_len = qinfo->qname_len; 1466356345Scy if(!dns_msg_ansadd(msg, region, wcrr, 0)) 1467356345Scy return NULL; 1468356345Scy /* No SOA needed for wildcard synthesised 1469356345Scy * answer. */ 1470356345Scy addsoa = 0; 1471356345Scy } else { 1472356345Scy /* Get wildcard NSEC for possible non existence 1473356345Scy * proof */ 1474356345Scy if(!(wcrr = neg_find_nsec(neg, wc_qinfo.qname, 1475356345Scy wc_qinfo.qname_len, qinfo->qclass, 1476356345Scy rrset_cache, now, region))) 1477356345Scy return NULL; 1478356345Scy 1479356345Scy nodata_wc = NULL; 1480356345Scy if(val_nsec_proves_name_error(wcrr, wc_ce)) 1481356345Scy rcode = LDNS_RCODE_NXDOMAIN; 1482356345Scy else if(!nsec_proves_nodata(wcrr, &wc_qinfo, 1483356345Scy &nodata_wc) || nodata_wc) 1484356345Scy /* &nodata_wc shouldn't be set, wc_qinfo 1485356345Scy * already contains wildcard domain. */ 1486356345Scy /* NSEC doesn't prove anything for 1487356345Scy * wildcard. */ 1488356345Scy return NULL; 1489356345Scy if(query_dname_compare(wcrr->rk.dname, 1490356345Scy nsec->rk.dname) != 0) 1491356345Scy if(!dns_msg_authadd(msg, region, wcrr, 0)) 1492356345Scy return NULL; 1493356345Scy } 1494356345Scy } 1495356345Scy 1496356345Scy if(!dns_msg_authadd(msg, region, nsec, 0)) 1497356345Scy return NULL; 1498356345Scy if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL)) 1499356345Scy return NULL; 1500356345Scy 1501356345Scy /* Increment statistic counters */ 1502356345Scy lock_basic_lock(&neg->lock); 1503356345Scy if(rcode == LDNS_RCODE_NOERROR) 1504356345Scy neg->num_neg_cache_noerror++; 1505356345Scy else if(rcode == LDNS_RCODE_NXDOMAIN) 1506356345Scy neg->num_neg_cache_nxdomain++; 1507356345Scy lock_basic_unlock(&neg->lock); 1508356345Scy 1509356345Scy FLAGS_SET_RCODE(msg->rep->flags, rcode); 1510356345Scy return msg; 1511238106Sdes } 1512238106Sdes 1513356345Scy /* No aggressive use of NSEC3 for now, only proceed for DS types. */ 1514356345Scy if(qinfo->qtype != LDNS_RR_TYPE_DS){ 1515356345Scy return NULL; 1516356345Scy } 1517238106Sdes /* check NSEC3 neg cache for type DS */ 1518238106Sdes /* need to look one zone higher for DS type */ 1519238106Sdes zname = qinfo->qname; 1520238106Sdes zname_len = qinfo->qname_len; 1521238106Sdes dname_remove_label(&zname, &zname_len); 1522238106Sdes zname_labs = dname_count_labels(zname); 1523238106Sdes 1524238106Sdes /* lookup closest zone */ 1525238106Sdes lock_basic_lock(&neg->lock); 1526238106Sdes zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs, 1527238106Sdes qinfo->qclass); 1528238106Sdes while(zone && !zone->in_use) 1529238106Sdes zone = zone->parent; 1530238106Sdes /* check that the zone is not too high up so that we do not pick data 1531238106Sdes * out of a zone that is above the last-seen key (or trust-anchor). */ 1532238106Sdes if(zone && topname) { 1533238106Sdes if(!dname_subdomain_c(zone->name, topname)) 1534238106Sdes zone = NULL; 1535238106Sdes } 1536238106Sdes if(!zone) { 1537238106Sdes lock_basic_unlock(&neg->lock); 1538238106Sdes return NULL; 1539238106Sdes } 1540238106Sdes 1541238106Sdes msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len, 1542238106Sdes zname_labs+1, buf, rrset_cache, region, now, topname); 1543238106Sdes if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) { 1544238106Sdes lock_basic_unlock(&neg->lock); 1545238106Sdes return NULL; 1546238106Sdes } 1547238106Sdes lock_basic_unlock(&neg->lock); 1548238106Sdes return msg; 1549238106Sdes} 1550