validator/val_neg.c

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