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