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 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_type* 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         qinfo.local_alias = NULL;
1011         if(!nsec_proves_nodata(nsec, &qinfo, &wc) &&
1012                 !val_nsec_proves_name_error(nsec, qname)) {
1013                 /* the NSEC is not a denial for the DLV */
1014                 lock_rw_unlock(&nsec->entry.lock);
1015                 lock_basic_unlock(&neg->lock);
1016                 verbose(VERB_ALGO, "negcache not proven");
1017                 return 0;
1018         }
1019         /* so the NSEC was a NODATA proof, or NXDOMAIN proof. */
1020
1021         /* no need to check for wildcard NSEC; no wildcards in DLV repos */
1022         /* no need to lookup SOA record for client; no response message */
1023
1024         lock_rw_unlock(&nsec->entry.lock);
1025         /* if OK touch the LRU for neg_data element */
1026         neg_lru_touch(neg, data);
1027         lock_basic_unlock(&neg->lock);
1028         verbose(VERB_ALGO, "negcache DLV denial proven");
1029         return 1;
1030 }
1031
1032 /** see if the reply has signed NSEC records and return the signer */
1033 static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len,
1034         uint16_t* dclass)
1035 {
1036         size_t i;
1037         struct packed_rrset_data* d;
1038         uint8_t* s;
1039         for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
1040                 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC ||
1041                         ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) {
1042                         d = (struct packed_rrset_data*)rep->rrsets[i]->
1043                                 entry.data;
1044                         /* return first signer name of first NSEC */
1045                         if(d->rrsig_count != 0) {
1046                                 val_find_rrset_signer(rep->rrsets[i],
1047                                         &s, signer_len);
1048                                 if(s && *signer_len) {
1049                                         *dclass = ntohs(rep->rrsets[i]->
1050                                                 rk.rrset_class);
1051                                         return s;
1052                                 }
1053                         }
1054                 }
1055         }
1056         return 0;
1057 }
1058
1059 void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
1060         uint8_t* zone_name)
1061 {
1062         size_t i, need;
1063         uint8_t* signer;
1064         size_t signer_len;
1065         uint16_t dclass;
1066         struct val_neg_zone* zone;
1067         /* no SOA in this message, find RRSIG over NSEC's signer name.
1068          * note the NSEC records are maybe not validated yet */
1069         signer = reply_nsec_signer(rep, &signer_len, &dclass);
1070         if(!signer)
1071                 return;
1072         if(!dname_subdomain_c(signer, zone_name)) {
1073                 /* the signer is not in the bailiwick, throw it out */
1074                 return;
1075         }
1076
1077         log_nametypeclass(VERB_ALGO, "negcache insert referral ",
1078                 signer, LDNS_RR_TYPE_NS, dclass);
1079
1080         /* ask for enough space to store all of it */
1081         need = calc_data_need(rep) + calc_zone_need(signer, signer_len);
1082         lock_basic_lock(&neg->lock);
1083         neg_make_space(neg, need);
1084
1085         /* find or create the zone entry */
1086         zone = neg_find_zone(neg, signer, signer_len, dclass);
1087         if(!zone) {
1088                 if(!(zone = neg_create_zone(neg, signer, signer_len,
1089                         dclass))) {
1090                         lock_basic_unlock(&neg->lock);
1091                         log_err("out of memory adding negative zone");
1092                         return;
1093                 }
1094         }
1095         val_neg_zone_take_inuse(zone);
1096
1097         /* insert the NSECs */
1098         for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
1099                 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC &&
1100                         ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3)
1101                         continue;
1102                 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname,
1103                         zone->name)) continue;
1104                 /* insert NSEC into this zone's tree */
1105                 neg_insert_data(neg, zone, rep->rrsets[i]);
1106         }
1107         if(zone->tree.count == 0) {
1108                 /* remove empty zone if inserts failed */
1109                 neg_delete_zone(neg, zone);
1110         }
1111         lock_basic_unlock(&neg->lock);
1112 }
1113
1114 /**
1115  * Check that an NSEC3 rrset does not have a type set.
1116  * None of the nsec3s in a hash-collision are allowed to have the type.
1117  * (since we do not know which one is the nsec3 looked at, flags, ..., we
1118  * ignore the cached item and let it bypass negative caching).
1119  * @param k: the nsec3 rrset to check.
1120  * @param t: type to check
1121  * @return true if no RRs have the type.
1122  */
1123 static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t)
1124 {
1125         int count = (int)((struct packed_rrset_data*)k->entry.data)->count;
1126         int i;
1127         for(i=0; i<count; i++)
1128                 if(nsec3_has_type(k, i, t))
1129                         return 0;
1130         return 1;
1131 }
1132
1133 /**
1134  * See if rrset exists in rrset cache.
1135  * If it does, the bit is checked, and if not expired, it is returned
1136  * allocated in region.
1137  * @param rrset_cache: rrset cache
1138  * @param qname: to lookup rrset name
1139  * @param qname_len: length of qname.
1140  * @param qtype: type of rrset to lookup, host order
1141  * @param qclass: class of rrset to lookup, host order
1142  * @param flags: flags for rrset to lookup
1143  * @param region: where to alloc result
1144  * @param checkbit: if true, a bit in the nsec typemap is checked for absence.
1145  * @param checktype: which bit to check
1146  * @param now: to check ttl against
1147  * @return rrset or NULL
1148  */
1149 static struct ub_packed_rrset_key*
1150 grab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len,
1151         uint16_t qtype, uint16_t qclass, uint32_t flags,
1152         struct regional* region, int checkbit, uint16_t checktype,
1153         time_t now)
1154 {
1155         struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache,
1156                 qname, qname_len, qtype, qclass, flags, now, 0);
1157         struct packed_rrset_data* d;
1158         if(!k) return NULL;
1159         d = (struct packed_rrset_data*)k->entry.data;
1160         if(d->ttl < now) {
1161                 lock_rw_unlock(&k->entry.lock);
1162                 return NULL;
1163         }
1164         /* only secure or unchecked records that have signatures. */
1165         if( ! ( d->security == sec_status_secure ||
1166                 (d->security == sec_status_unchecked &&
1167                 d->rrsig_count > 0) ) ) {
1168                 lock_rw_unlock(&k->entry.lock);
1169                 return NULL;
1170         }
1171         /* check if checktype is absent */
1172         if(checkbit && (
1173                 (qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) ||
1174                 (qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype))
1175                 )) {
1176                 lock_rw_unlock(&k->entry.lock);
1177                 return NULL;
1178         }
1179         /* looks OK! copy to region and return it */
1180         r = packed_rrset_copy_region(k, region, now);
1181         /* if it failed, we return the NULL */
1182         lock_rw_unlock(&k->entry.lock);
1183         return r;
1184 }
1185
1186 /** find nsec3 closest encloser in neg cache */
1187 static struct val_neg_data*
1188 neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
1189                 int qlabs, sldns_buffer* buf, uint8_t* hashnc, size_t* nclen)
1190 {
1191         struct val_neg_data* data;
1192         uint8_t hashce[NSEC3_SHA_LEN];
1193         uint8_t b32[257];
1194         size_t celen, b32len;
1195
1196         *nclen = 0;
1197         while(qlabs > 0) {
1198                 /* hash */
1199                 if(!(celen=nsec3_get_hashed(buf, qname, qname_len,
1200                         zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt,
1201                         zone->nsec3_saltlen, hashce, sizeof(hashce))))
1202                         return NULL;
1203                 if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name,
1204                         zone->len, b32, sizeof(b32))))
1205                         return NULL;
1206
1207                 /* lookup (exact match only) */
1208                 data = neg_find_data(zone, b32, b32len, zone->labs+1);
1209                 if(data && data->in_use) {
1210                         /* found ce match! */
1211                         return data;
1212                 }
1213
1214                 *nclen = celen;
1215                 memmove(hashnc, hashce, celen);
1216                 dname_remove_label(&qname, &qname_len);
1217                 qlabs --;
1218         }
1219         return NULL;
1220 }
1221
1222 /** check nsec3 parameters on nsec3 rrset with current zone values */
1223 static int
1224 neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset)
1225 {
1226         int h;
1227         uint8_t* s;
1228         size_t slen, it;
1229         if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen))
1230                 return 0;
1231         return (h == zone->nsec3_hash && it == zone->nsec3_iter &&
1232                 slen == zone->nsec3_saltlen &&
1233                 memcmp(zone->nsec3_salt, s, slen) == 0);
1234 }
1235
1236 /** get next closer for nsec3 proof */
1237 static struct ub_packed_rrset_key*
1238 neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen,
1239         struct rrset_cache* rrset_cache, struct regional* region,
1240         time_t now, uint8_t* b32, size_t maxb32)
1241 {
1242         struct ub_packed_rrset_key* nc_rrset;
1243         struct val_neg_data* data;
1244         size_t b32len;
1245
1246         if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name,
1247                 zone->len, b32, maxb32)))
1248                 return NULL;
1249         (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data);
1250         if(!data && zone->tree.count != 0) {
1251                 /* could be before the first entry ; return the last
1252                  * entry (possibly the rollover nsec3 at end) */
1253                 data = (struct val_neg_data*)rbtree_last(&zone->tree);
1254         }
1255         while(data && !data->in_use)
1256                 data = data->parent;
1257         if(!data)
1258                 return NULL;
1259         /* got a data element in tree, grab it */
1260         nc_rrset = grab_nsec(rrset_cache, data->name, data->len,
1261                 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now);
1262         if(!nc_rrset)
1263                 return NULL;
1264         if(!neg_params_ok(zone, nc_rrset))
1265                 return NULL;
1266         return nc_rrset;
1267 }
1268
1269 /** neg cache nsec3 proof procedure*/
1270 static struct dns_msg*
1271 neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
1272                 int qlabs, sldns_buffer* buf, struct rrset_cache* rrset_cache,
1273                 struct regional* region, time_t now, uint8_t* topname)
1274 {
1275         struct dns_msg* msg;
1276         struct val_neg_data* data;
1277         uint8_t hashnc[NSEC3_SHA_LEN];
1278         size_t nclen;
1279         struct ub_packed_rrset_key* ce_rrset, *nc_rrset;
1280         struct nsec3_cached_hash c;
1281         uint8_t nc_b32[257];
1282
1283         /* for NSEC3 ; determine the closest encloser for which we
1284          * can find an exact match. Remember the hashed lower name,
1285          * since that is the one we need a closest match for.
1286          * If we find a match straight away, then it becomes NODATA.
1287          * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation.
1288          * Also check that parameters are the same on closest encloser
1289          * and on closest match.
1290          */
1291         if(!zone->nsec3_hash)
1292                 return NULL; /* not nsec3 zone */
1293
1294         if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf,
1295                 hashnc, &nclen))) {
1296                 return NULL;
1297         }
1298
1299         /* grab the ce rrset */
1300         ce_rrset = grab_nsec(rrset_cache, data->name, data->len,
1301                 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1,
1302                 LDNS_RR_TYPE_DS, now);
1303         if(!ce_rrset)
1304                 return NULL;
1305         if(!neg_params_ok(zone, ce_rrset))
1306                 return NULL;
1307
1308         if(nclen == 0) {
1309                 /* exact match, just check the type bits */
1310                 /* need: -SOA, -DS, +NS */
1311                 if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) ||
1312                         nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) ||
1313                         !nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS))
1314                         return NULL;
1315                 if(!(msg = dns_msg_create(qname, qname_len,
1316                         LDNS_RR_TYPE_DS, zone->dclass, region, 1)))
1317                         return NULL;
1318                 /* TTL reduced in grab_nsec */
1319                 if(!dns_msg_authadd(msg, region, ce_rrset, 0))
1320                         return NULL;
1321                 return msg;
1322         }
1323
1324         /* optout is not allowed without knowing the trust-anchor in use,
1325          * otherwise the optout could spoof away that anchor */
1326         if(!topname)
1327                 return NULL;
1328
1329         /* if there is no exact match, it must be in an optout span
1330          * (an existing DS implies an NSEC3 must exist) */
1331         nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache,
1332                 region, now, nc_b32, sizeof(nc_b32));
1333         if(!nc_rrset)
1334                 return NULL;
1335         if(!neg_params_ok(zone, nc_rrset))
1336                 return NULL;
1337         if(!nsec3_has_optout(nc_rrset, 0))
1338                 return NULL;
1339         c.hash = hashnc;
1340         c.hash_len = nclen;
1341         c.b32 = nc_b32+1;
1342         c.b32_len = (size_t)nc_b32[0];
1343         if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) {
1344                 /* nc_rrset covers the next closer name.
1345                  * ce_rrset equals a closer encloser.
1346                  * nc_rrset is optout.
1347                  * No need to check wildcard for type DS */
1348                 /* capacity=3: ce + nc + soa(if needed) */
1349                 if(!(msg = dns_msg_create(qname, qname_len,
1350                         LDNS_RR_TYPE_DS, zone->dclass, region, 3)))
1351                         return NULL;
1352                 /* now=0 because TTL was reduced in grab_nsec */
1353                 if(!dns_msg_authadd(msg, region, ce_rrset, 0))
1354                         return NULL;
1355                 if(!dns_msg_authadd(msg, region, nc_rrset, 0))
1356                         return NULL;
1357                 return msg;
1358         }
1359         return NULL;
1360 }
1361
1362 /**
1363  * Add SOA record for external responses.
1364  * @param rrset_cache: to look into.
1365  * @param now: current time.
1366  * @param region: where to perform the allocation
1367  * @param msg: current msg with NSEC.
1368  * @param zone: val_neg_zone if we have one.
1369  * @return false on lookup or alloc failure.
1370  */
1371 static int add_soa(struct rrset_cache* rrset_cache, time_t now,
1372         struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone)
1373 {
1374         struct ub_packed_rrset_key* soa;
1375         uint8_t* nm;
1376         size_t nmlen;
1377         uint16_t dclass;
1378         if(zone) {
1379                 nm = zone->name;
1380                 nmlen = zone->len;
1381                 dclass = zone->dclass;
1382         } else {
1383                 /* Assumes the signer is the zone SOA to add */
1384                 nm = reply_nsec_signer(msg->rep, &nmlen, &dclass);
1385                 if(!nm)
1386                         return 0;
1387         }
1388         soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA,
1389                 dclass, PACKED_RRSET_SOA_NEG, now, 0);
1390         if(!soa)
1391                 return 0;
1392         if(!dns_msg_authadd(msg, region, soa, now)) {
1393                 lock_rw_unlock(&soa->entry.lock);
1394                 return 0;
1395         }
1396         lock_rw_unlock(&soa->entry.lock);
1397         return 1;
1398 }
1399
1400 struct dns_msg*
1401 val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo,
1402         struct regional* region, struct rrset_cache* rrset_cache,
1403         sldns_buffer* buf, time_t now, int addsoa, uint8_t* topname)
1404 {
1405         struct dns_msg* msg;
1406         struct ub_packed_rrset_key* rrset;
1407         uint8_t* zname;
1408         size_t zname_len;
1409         int zname_labs;
1410         struct val_neg_zone* zone;
1411
1412         /* only for DS queries */
1413         if(qinfo->qtype != LDNS_RR_TYPE_DS)
1414                 return NULL;
1415         log_assert(!topname || dname_subdomain_c(qinfo->qname, topname));
1416
1417         /* see if info from neg cache is available
1418          * For NSECs, because there is no optout; a DS next to a delegation
1419          * always has exactly an NSEC for it itself; check its DS bit.
1420          * flags=0 (not the zone apex).
1421          */
1422         rrset = grab_nsec(rrset_cache, qinfo->qname, qinfo->qname_len,
1423                 LDNS_RR_TYPE_NSEC, qinfo->qclass, 0, region, 1,
1424                 qinfo->qtype, now);
1425         if(rrset) {
1426                 /* return msg with that rrset */
1427                 if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len,
1428                         qinfo->qtype, qinfo->qclass, region, 2)))
1429                         return NULL;
1430                 /* TTL already subtracted in grab_nsec */
1431                 if(!dns_msg_authadd(msg, region, rrset, 0))
1432                         return NULL;
1433                 if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL))
1434                         return NULL;
1435                 return msg;
1436         }
1437
1438         /* check NSEC3 neg cache for type DS */
1439         /* need to look one zone higher for DS type */
1440         zname = qinfo->qname;
1441         zname_len = qinfo->qname_len;
1442         dname_remove_label(&zname, &zname_len);
1443         zname_labs = dname_count_labels(zname);
1444
1445         /* lookup closest zone */
1446         lock_basic_lock(&neg->lock);
1447         zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs,
1448                 qinfo->qclass);
1449         while(zone && !zone->in_use)
1450                 zone = zone->parent;
1451         /* check that the zone is not too high up so that we do not pick data
1452          * out of a zone that is above the last-seen key (or trust-anchor). */
1453         if(zone && topname) {
1454                 if(!dname_subdomain_c(zone->name, topname))
1455                         zone = NULL;
1456         }
1457         if(!zone) {
1458                 lock_basic_unlock(&neg->lock);
1459                 return NULL;
1460         }
1461
1462         msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len,
1463                 zname_labs+1, buf, rrset_cache, region, now, topname);
1464         if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) {
1465                 lock_basic_unlock(&neg->lock);
1466                 return NULL;
1467         }
1468         lock_basic_unlock(&neg->lock);
1469         return msg;
1470 }