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