2 * validator/val_neg.c - validator aggressive negative caching functions.
4 * Copyright (c) 2008, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
39 * This file contains helper functions for the validator module.
40 * The functions help with aggressive negative caching.
41 * This creates new denials of existance, and proofs for absence of types
42 * from cached NSEC records.
45 #ifdef HAVE_OPENSSL_SSL_H
46 #include "openssl/ssl.h"
47 #define NSEC3_SHA_LEN SHA_DIGEST_LENGTH
49 #define NSEC3_SHA_LEN 20
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"
58 #include "util/net_help.h"
59 #include "util/config_file.h"
60 #include "services/cache/rrset.h"
61 #include "services/cache/dns.h"
63 int val_neg_data_compare(const void* a, const void* b)
65 struct val_neg_data* x = (struct val_neg_data*)a;
66 struct val_neg_data* y = (struct val_neg_data*)b;
68 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
71 int val_neg_zone_compare(const void* a, const void* b)
73 struct val_neg_zone* x = (struct val_neg_zone*)a;
74 struct val_neg_zone* y = (struct val_neg_zone*)b;
76 if(x->dclass != y->dclass) {
77 if(x->dclass < y->dclass)
81 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
84 struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter)
86 struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1,
89 log_err("Could not create neg cache: out of memory");
92 neg->nsec3_max_iter = maxiter;
93 neg->max = 1024*1024; /* 1 M is thousands of entries */
94 if(cfg) neg->max = cfg->neg_cache_size;
95 rbtree_init(&neg->tree, &val_neg_zone_compare);
96 lock_basic_init(&neg->lock);
97 lock_protect(&neg->lock, neg, sizeof(*neg));
101 size_t val_neg_get_mem(struct val_neg_cache* neg)
104 lock_basic_lock(&neg->lock);
105 result = sizeof(*neg) + neg->use;
106 lock_basic_unlock(&neg->lock);
110 /** clear datas on cache deletion */
112 neg_clear_datas(rbnode_t* n, void* ATTR_UNUSED(arg))
114 struct val_neg_data* d = (struct val_neg_data*)n;
119 /** clear zones on cache deletion */
121 neg_clear_zones(rbnode_t* n, void* ATTR_UNUSED(arg))
123 struct val_neg_zone* z = (struct val_neg_zone*)n;
124 /* delete all the rrset entries in the tree */
125 traverse_postorder(&z->tree, &neg_clear_datas, NULL);
131 void neg_cache_delete(struct val_neg_cache* neg)
134 lock_basic_destroy(&neg->lock);
135 /* delete all the zones in the tree */
136 traverse_postorder(&neg->tree, &neg_clear_zones, NULL);
141 * Put data element at the front of the LRU list.
142 * @param neg: negative cache with LRU start and end.
143 * @param data: this data is fronted.
145 static void neg_lru_front(struct val_neg_cache* neg,
146 struct val_neg_data* data)
149 data->next = neg->first;
152 else neg->first->prev = data;
157 * Remove data element from LRU list.
158 * @param neg: negative cache with LRU start and end.
159 * @param data: this data is removed from the list.
161 static void neg_lru_remove(struct val_neg_cache* neg,
162 struct val_neg_data* data)
165 data->prev->next = data->next;
166 else neg->first = data->next;
168 data->next->prev = data->prev;
169 else neg->last = data->prev;
173 * Touch LRU for data element, put it at the start of the LRU list.
174 * @param neg: negative cache with LRU start and end.
175 * @param data: this data is used.
177 static void neg_lru_touch(struct val_neg_cache* neg,
178 struct val_neg_data* data)
180 if(data == neg->first)
181 return; /* nothing to do */
182 /* remove from current lru position */
183 neg_lru_remove(neg, data);
185 neg_lru_front(neg, data);
189 * Delete a zone element from the negative cache.
190 * May delete other zone elements to keep tree coherent, or
191 * only mark the element as 'not in use'.
192 * @param neg: negative cache.
193 * @param z: zone element to delete.
195 static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z)
197 struct val_neg_zone* p, *np;
199 log_assert(z->in_use);
200 log_assert(z->count > 0);
203 /* go up the tree and reduce counts */
206 log_assert(p->count > 0);
211 /* remove zones with zero count */
213 while(p && p->count == 0) {
215 (void)rbtree_delete(&neg->tree, &p->node);
216 neg->use -= p->len + sizeof(*p);
224 void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el)
226 struct val_neg_zone* z;
227 struct val_neg_data* p, *np;
230 log_assert(el->in_use);
231 log_assert(el->count > 0);
234 /* remove it from the lru list */
235 neg_lru_remove(neg, el);
237 /* go up the tree and reduce counts */
240 log_assert(p->count > 0);
245 /* delete 0 count items from tree */
247 while(p && p->count == 0) {
249 (void)rbtree_delete(&z->tree, &p->node);
250 neg->use -= p->len + sizeof(*p);
256 /* check if the zone is now unused */
257 if(z->tree.count == 0) {
258 neg_delete_zone(neg, z);
263 * Create more space in negative cache
264 * The oldest elements are deleted until enough space is present.
265 * Empty zones are deleted.
266 * @param neg: negative cache.
267 * @param need: how many bytes are needed.
269 static void neg_make_space(struct val_neg_cache* neg, size_t need)
271 /* delete elements until enough space or its empty */
272 while(neg->last && neg->max < neg->use + need) {
273 neg_delete_data(neg, neg->last);
277 struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg,
278 uint8_t* nm, size_t len, uint16_t dclass)
280 struct val_neg_zone lookfor;
281 struct val_neg_zone* result;
282 lookfor.node.key = &lookfor;
285 lookfor.labs = dname_count_labels(lookfor.name);
286 lookfor.dclass = dclass;
288 result = (struct val_neg_zone*)
289 rbtree_search(&neg->tree, lookfor.node.key);
294 * Find the given data
295 * @param zone: negative zone
296 * @param nm: what to look for.
297 * @param len: length of nm
298 * @param labs: labels in nm
299 * @return data or NULL if not found.
301 static struct val_neg_data* neg_find_data(struct val_neg_zone* zone,
302 uint8_t* nm, size_t len, int labs)
304 struct val_neg_data lookfor;
305 struct val_neg_data* result;
306 lookfor.node.key = &lookfor;
311 result = (struct val_neg_data*)
312 rbtree_search(&zone->tree, lookfor.node.key);
317 * Calculate space needed for the data and all its parents
318 * @param rep: NSEC entries.
321 static size_t calc_data_need(struct reply_info* rep)
324 size_t i, len, res = 0;
326 for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) {
327 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
328 d = rep->rrsets[i]->rk.dname;
329 len = rep->rrsets[i]->rk.dname_len;
330 res = sizeof(struct val_neg_data) + len;
331 while(!dname_is_root(d)) {
332 log_assert(len > 1); /* not root label */
333 dname_remove_label(&d, &len);
334 res += sizeof(struct val_neg_data) + len;
342 * Calculate space needed for zone and all its parents
343 * @param d: name of zone
344 * @param len: length of name
347 static size_t calc_zone_need(uint8_t* d, size_t len)
349 size_t res = sizeof(struct val_neg_zone) + len;
350 while(!dname_is_root(d)) {
351 log_assert(len > 1); /* not root label */
352 dname_remove_label(&d, &len);
353 res += sizeof(struct val_neg_zone) + len;
359 * Find closest existing parent zone of the given name.
360 * @param neg: negative cache.
361 * @param nm: name to look for
362 * @param nm_len: length of nm
363 * @param labs: labelcount of nm.
364 * @param qclass: class.
365 * @return the zone or NULL if none found.
367 static struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg,
368 uint8_t* nm, size_t nm_len, int labs, uint16_t qclass)
370 struct val_neg_zone key;
371 struct val_neg_zone* result;
372 rbnode_t* res = NULL;
378 if(rbtree_find_less_equal(&neg->tree, &key, &res)) {
380 result = (struct val_neg_zone*)res;
382 /* smaller element (or no element) */
384 result = (struct val_neg_zone*)res;
385 if(!result || result->dclass != qclass)
387 /* count number of labels matched */
388 (void)dname_lab_cmp(result->name, result->labs, key.name,
390 while(result) { /* go up until qname is subdomain of stub */
391 if(result->labs <= m)
393 result = result->parent;
400 * Find closest existing parent data for the given name.
401 * @param zone: to look in.
402 * @param nm: name to look for
403 * @param nm_len: length of nm
404 * @param labs: labelcount of nm.
405 * @return the data or NULL if none found.
407 static struct val_neg_data* neg_closest_data_parent(
408 struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs)
410 struct val_neg_data key;
411 struct val_neg_data* result;
412 rbnode_t* res = NULL;
417 if(rbtree_find_less_equal(&zone->tree, &key, &res)) {
419 result = (struct val_neg_data*)res;
421 /* smaller element (or no element) */
423 result = (struct val_neg_data*)res;
426 /* count number of labels matched */
427 (void)dname_lab_cmp(result->name, result->labs, key.name,
429 while(result) { /* go up until qname is subdomain of stub */
430 if(result->labs <= m)
432 result = result->parent;
439 * Create a single zone node
440 * @param nm: name for zone (copied)
441 * @param nm_len: length of name
442 * @param labs: labels in name.
443 * @param dclass: class of zone, host order.
444 * @return new zone or NULL on failure
446 static struct val_neg_zone* neg_setup_zone_node(
447 uint8_t* nm, size_t nm_len, int labs, uint16_t dclass)
449 struct val_neg_zone* zone =
450 (struct val_neg_zone*)calloc(1, sizeof(*zone));
454 zone->node.key = zone;
455 zone->name = memdup(nm, nm_len);
462 zone->dclass = dclass;
464 rbtree_init(&zone->tree, &val_neg_data_compare);
469 * Create a linked list of parent zones, starting at longname ending on
470 * the parent (can be NULL, creates to the root).
471 * @param nm: name for lowest in chain
472 * @param nm_len: length of name
473 * @param labs: labels in name.
474 * @param dclass: class of zone.
475 * @param parent: NULL for to root, else so it fits under here.
476 * @return zone; a chain of zones and their parents up to the parent.
477 * or NULL on malloc failure
479 static struct val_neg_zone* neg_zone_chain(
480 uint8_t* nm, size_t nm_len, int labs, uint16_t dclass,
481 struct val_neg_zone* parent)
484 int tolabs = parent?parent->labs:0;
485 struct val_neg_zone* zone, *prev = NULL, *first = NULL;
487 /* create the new subtree, i is labelcount of current creation */
488 /* this creates a 'first' to z->parent=NULL list of zones */
489 for(i=labs; i!=tolabs; i--) {
490 /* create new item */
491 zone = neg_setup_zone_node(nm, nm_len, i, dclass);
493 /* need to delete other allocations in this routine!*/
494 struct val_neg_zone* p=first, *np;
508 /* prepare for next name */
510 dname_remove_label(&nm, &nm_len);
515 void val_neg_zone_take_inuse(struct val_neg_zone* zone)
518 struct val_neg_zone* p;
520 /* increase usage count of all parents */
521 for(p=zone; p; p = p->parent) {
527 struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
528 uint8_t* nm, size_t nm_len, uint16_t dclass)
530 struct val_neg_zone* zone;
531 struct val_neg_zone* parent;
532 struct val_neg_zone* p, *np;
533 int labs = dname_count_labels(nm);
535 /* find closest enclosing parent zone that (still) exists */
536 parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass);
537 if(parent && query_dname_compare(parent->name, nm) == 0)
538 return parent; /* already exists, weird */
539 /* if parent exists, it is in use */
540 log_assert(!parent || parent->count > 0);
541 zone = neg_zone_chain(nm, nm_len, labs, dclass, parent);
546 /* insert the list of zones into the tree */
551 neg->use += sizeof(struct val_neg_zone) + p->len;
553 (void)rbtree_insert(&neg->tree, &p->node);
554 /* last one needs proper parent pointer */
562 /** find zone name of message, returns the SOA record */
563 static struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep)
566 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
567 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA)
568 return rep->rrsets[i];
573 /** see if the reply has NSEC records worthy of caching */
574 static int reply_has_nsec(struct reply_info* rep)
577 struct packed_rrset_data* d;
578 if(rep->security != sec_status_secure)
580 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
581 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
582 d = (struct packed_rrset_data*)rep->rrsets[i]->
584 if(d->security == sec_status_secure)
593 * Create single node of data element.
594 * @param nm: name (copied)
595 * @param nm_len: length of name
596 * @param labs: labels in name.
597 * @return element with name nm, or NULL malloc failure.
599 static struct val_neg_data* neg_setup_data_node(
600 uint8_t* nm, size_t nm_len, int labs)
602 struct val_neg_data* el;
603 el = (struct val_neg_data*)calloc(1, sizeof(*el));
608 el->name = memdup(nm, nm_len);
619 * Create chain of data element and parents
621 * @param nm_len: length of name
622 * @param labs: labels in name.
623 * @param parent: up to where to make, if NULL up to root label.
624 * @return lowest element with name nm, or NULL malloc failure.
626 static struct val_neg_data* neg_data_chain(
627 uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent)
630 int tolabs = parent?parent->labs:0;
631 struct val_neg_data* el, *first = NULL, *prev = NULL;
633 /* create the new subtree, i is labelcount of current creation */
634 /* this creates a 'first' to z->parent=NULL list of zones */
635 for(i=labs; i!=tolabs; i--) {
636 /* create new item */
637 el = neg_setup_data_node(nm, nm_len, i);
639 /* need to delete other allocations in this routine!*/
640 struct val_neg_data* p = first, *np;
655 /* prepare for next name */
657 dname_remove_label(&nm, &nm_len);
663 * Remove NSEC records between start and end points.
664 * By walking the tree, the tree is sorted canonically.
665 * @param neg: negative cache.
666 * @param zone: the zone
667 * @param el: element to start walking at.
668 * @param nsec: the nsec record with the end point
670 static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone,
671 struct val_neg_data* el, struct ub_packed_rrset_key* nsec)
673 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
678 rbnode_t* walk, *next;
679 struct val_neg_data* cur;
682 if(!d || d->count == 0 || d->rr_len[0] < 2+1)
684 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) {
685 end = d->rr_data[0]+2;
686 end_len = dname_valid(end, d->rr_len[0]-2);
687 end_labs = dname_count_labels(end);
690 if(!nsec3_get_nextowner_b32(nsec, 0, buf, sizeof(buf)))
693 end_labs = dname_count_size_labels(end, &end_len);
696 /* sanity check, both owner and end must be below the zone apex */
697 if(!dname_subdomain_c(el->name, zone->name) ||
698 !dname_subdomain_c(end, zone->name))
701 /* detect end of zone NSEC ; wipe until the end of zone */
702 if(query_dname_compare(end, zone->name) == 0) {
706 walk = rbtree_next(&el->node);
707 while(walk && walk != RBTREE_NULL) {
708 cur = (struct val_neg_data*)walk;
709 /* sanity check: must be larger than start */
710 if(dname_canon_lab_cmp(cur->name, cur->labs,
711 el->name, el->labs, &m) <= 0) {
712 /* r == 0 skip original record. */
713 /* r < 0 too small! */
714 walk = rbtree_next(walk);
717 /* stop at endpoint, also data at empty nonterminals must be
718 * removed (no NSECs there) so everything between
720 if(end && dname_canon_lab_cmp(cur->name, cur->labs,
721 end, end_labs, &m) >= 0) {
724 /* this element has to be deleted, but we cannot do it
725 * now, because we are walking the tree still ... */
726 /* get the next element: */
727 next = rbtree_next(walk);
728 /* now delete the original element, this may trigger
729 * rbtree rebalances, but really, the next element is
731 * But it may trigger delete of other data and the
732 * entire zone. However, if that happens, this is done
733 * by deleting the *parents* of the element for deletion,
734 * and maybe also the entire zone if it is empty.
735 * But parents are smaller in canonical compare, thus,
736 * if a larger element exists, then it is not a parent,
737 * it cannot get deleted, the zone cannot get empty.
738 * If the next==NULL, then zone can be empty. */
740 neg_delete_data(neg, cur);
745 void neg_insert_data(struct val_neg_cache* neg,
746 struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec)
748 struct packed_rrset_data* d;
749 struct val_neg_data* parent;
750 struct val_neg_data* el;
751 uint8_t* nm = nsec->rk.dname;
752 size_t nm_len = nsec->rk.dname_len;
753 int labs = dname_count_labels(nsec->rk.dname);
755 d = (struct packed_rrset_data*)nsec->entry.data;
756 if( !(d->security == sec_status_secure ||
757 (d->security == sec_status_unchecked && d->rrsig_count > 0)))
759 log_nametypeclass(VERB_ALGO, "negcache rr",
760 nsec->rk.dname, ntohs(nsec->rk.type),
761 ntohs(nsec->rk.rrset_class));
763 /* find closest enclosing parent data that (still) exists */
764 parent = neg_closest_data_parent(zone, nm, nm_len, labs);
765 if(parent && query_dname_compare(parent->name, nm) == 0) {
766 /* perfect match already exists */
767 log_assert(parent->count > 0);
770 struct val_neg_data* p, *np;
772 /* create subtree for perfect match */
773 /* if parent exists, it is in use */
774 log_assert(!parent || parent->count > 0);
776 el = neg_data_chain(nm, nm_len, labs, parent);
778 log_err("out of memory inserting NSEC negative cache");
781 el->in_use = 0; /* set on below */
783 /* insert the list of zones into the tree */
788 neg->use += sizeof(struct val_neg_data) + p->len;
791 (void)rbtree_insert(&zone->tree, &p->node);
792 /* last one needs proper parent pointer */
800 struct val_neg_data* p;
803 /* increase usage count of all parents */
804 for(p=el; p; p = p->parent) {
808 neg_lru_front(neg, el);
810 /* in use, bring to front, lru */
811 neg_lru_touch(neg, el);
814 /* if nsec3 store last used parameters */
815 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) {
819 if(nsec3_get_params(nsec, 0, &h, &it, &s, &slen) &&
820 it <= neg->nsec3_max_iter &&
821 (h != zone->nsec3_hash || it != zone->nsec3_iter ||
822 slen != zone->nsec3_saltlen ||
823 memcmp(zone->nsec3_salt, s, slen) != 0)) {
824 uint8_t* sa = memdup(s, slen);
826 free(zone->nsec3_salt);
827 zone->nsec3_salt = sa;
828 zone->nsec3_saltlen = slen;
829 zone->nsec3_hash = h;
830 zone->nsec3_iter = it;
835 /* wipe out the cache items between NSEC start and end */
836 wipeout(neg, zone, el, nsec);
839 void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep)
842 struct ub_packed_rrset_key* soa;
843 struct val_neg_zone* zone;
844 /* see if secure nsecs inside */
845 if(!reply_has_nsec(rep))
847 /* find the zone name in message */
848 soa = reply_find_soa(rep);
852 log_nametypeclass(VERB_ALGO, "negcache insert for zone",
853 soa->rk.dname, LDNS_RR_TYPE_SOA, ntohs(soa->rk.rrset_class));
855 /* ask for enough space to store all of it */
856 need = calc_data_need(rep) +
857 calc_zone_need(soa->rk.dname, soa->rk.dname_len);
858 lock_basic_lock(&neg->lock);
859 neg_make_space(neg, need);
861 /* find or create the zone entry */
862 zone = neg_find_zone(neg, soa->rk.dname, soa->rk.dname_len,
863 ntohs(soa->rk.rrset_class));
865 if(!(zone = neg_create_zone(neg, soa->rk.dname,
866 soa->rk.dname_len, ntohs(soa->rk.rrset_class)))) {
867 lock_basic_unlock(&neg->lock);
868 log_err("out of memory adding negative zone");
872 val_neg_zone_take_inuse(zone);
874 /* insert the NSECs */
875 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
876 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC)
878 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname,
879 zone->name)) continue;
880 /* insert NSEC into this zone's tree */
881 neg_insert_data(neg, zone, rep->rrsets[i]);
883 if(zone->tree.count == 0) {
884 /* remove empty zone if inserts failed */
885 neg_delete_zone(neg, zone);
887 lock_basic_unlock(&neg->lock);
891 * Lookup closest data record. For NSEC denial.
892 * @param zone: zone to look in
893 * @param qname: name to look for.
894 * @param len: length of name
895 * @param labs: labels in name
896 * @param data: data element, exact or smaller or NULL
897 * @return true if exact match.
899 static int neg_closest_data(struct val_neg_zone* zone,
900 uint8_t* qname, size_t len, int labs, struct val_neg_data** data)
902 struct val_neg_data key;
908 if(rbtree_find_less_equal(&zone->tree, &key, &r)) {
910 *data = (struct val_neg_data*)r;
914 *data = (struct val_neg_data*)r;
919 int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len,
920 uint16_t qclass, struct rrset_cache* rrset_cache, uint32_t now)
922 /* lookup closest zone */
923 struct val_neg_zone* zone;
924 struct val_neg_data* data;
926 struct ub_packed_rrset_key* nsec;
927 struct packed_rrset_data* d;
930 struct query_info qinfo;
933 log_nametypeclass(VERB_ALGO, "negcache dlvlookup", qname,
934 LDNS_RR_TYPE_DLV, qclass);
936 labs = dname_count_labels(qname);
937 lock_basic_lock(&neg->lock);
938 zone = neg_closest_zone_parent(neg, qname, len, labs, qclass);
939 while(zone && !zone->in_use)
942 lock_basic_unlock(&neg->lock);
945 log_nametypeclass(VERB_ALGO, "negcache zone", zone->name, 0,
948 /* DLV is defined to use NSEC only */
949 if(zone->nsec3_hash) {
950 lock_basic_unlock(&neg->lock);
954 /* lookup closest data record */
955 (void)neg_closest_data(zone, qname, len, labs, &data);
956 while(data && !data->in_use)
959 lock_basic_unlock(&neg->lock);
962 log_nametypeclass(VERB_ALGO, "negcache rr", data->name,
963 LDNS_RR_TYPE_NSEC, zone->dclass);
965 /* lookup rrset in rrset cache */
967 if(query_dname_compare(data->name, zone->name) == 0)
968 flags = PACKED_RRSET_NSEC_AT_APEX;
969 nsec = rrset_cache_lookup(rrset_cache, data->name, data->len,
970 LDNS_RR_TYPE_NSEC, zone->dclass, flags, now, 0);
972 /* check if secure and TTL ok */
974 lock_basic_unlock(&neg->lock);
977 d = (struct packed_rrset_data*)nsec->entry.data;
978 if(!d || now > d->ttl) {
979 lock_rw_unlock(&nsec->entry.lock);
980 /* delete data record if expired */
981 neg_delete_data(neg, data);
982 lock_basic_unlock(&neg->lock);
985 if(d->security != sec_status_secure) {
986 lock_rw_unlock(&nsec->entry.lock);
987 neg_delete_data(neg, data);
988 lock_basic_unlock(&neg->lock);
991 verbose(VERB_ALGO, "negcache got secure rrset");
993 /* check NSEC security */
994 /* check if NSEC proves no DLV type exists */
995 /* check if NSEC proves NXDOMAIN for qname */
997 qinfo.qtype = LDNS_RR_TYPE_DLV;
998 qinfo.qclass = qclass;
999 if(!nsec_proves_nodata(nsec, &qinfo, &wc) &&
1000 !val_nsec_proves_name_error(nsec, qname)) {
1001 /* the NSEC is not a denial for the DLV */
1002 lock_rw_unlock(&nsec->entry.lock);
1003 lock_basic_unlock(&neg->lock);
1004 verbose(VERB_ALGO, "negcache not proven");
1007 /* so the NSEC was a NODATA proof, or NXDOMAIN proof. */
1009 /* no need to check for wildcard NSEC; no wildcards in DLV repos */
1010 /* no need to lookup SOA record for client; no response message */
1012 lock_rw_unlock(&nsec->entry.lock);
1013 /* if OK touch the LRU for neg_data element */
1014 neg_lru_touch(neg, data);
1015 lock_basic_unlock(&neg->lock);
1016 verbose(VERB_ALGO, "negcache DLV denial proven");
1020 /** see if the reply has signed NSEC records and return the signer */
1021 static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len,
1025 struct packed_rrset_data* d;
1027 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
1028 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC ||
1029 ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) {
1030 d = (struct packed_rrset_data*)rep->rrsets[i]->
1032 /* return first signer name of first NSEC */
1033 if(d->rrsig_count != 0) {
1034 val_find_rrset_signer(rep->rrsets[i],
1036 if(s && *signer_len) {
1037 *dclass = ntohs(rep->rrsets[i]->
1047 void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
1054 struct val_neg_zone* zone;
1055 /* no SOA in this message, find RRSIG over NSEC's signer name.
1056 * note the NSEC records are maybe not validated yet */
1057 signer = reply_nsec_signer(rep, &signer_len, &dclass);
1060 if(!dname_subdomain_c(signer, zone_name)) {
1061 /* the signer is not in the bailiwick, throw it out */
1065 log_nametypeclass(VERB_ALGO, "negcache insert referral ",
1066 signer, LDNS_RR_TYPE_NS, dclass);
1068 /* ask for enough space to store all of it */
1069 need = calc_data_need(rep) + calc_zone_need(signer, signer_len);
1070 lock_basic_lock(&neg->lock);
1071 neg_make_space(neg, need);
1073 /* find or create the zone entry */
1074 zone = neg_find_zone(neg, signer, signer_len, dclass);
1076 if(!(zone = neg_create_zone(neg, signer, signer_len,
1078 lock_basic_unlock(&neg->lock);
1079 log_err("out of memory adding negative zone");
1083 val_neg_zone_take_inuse(zone);
1085 /* insert the NSECs */
1086 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
1087 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC &&
1088 ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3)
1090 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname,
1091 zone->name)) continue;
1092 /* insert NSEC into this zone's tree */
1093 neg_insert_data(neg, zone, rep->rrsets[i]);
1095 if(zone->tree.count == 0) {
1096 /* remove empty zone if inserts failed */
1097 neg_delete_zone(neg, zone);
1099 lock_basic_unlock(&neg->lock);
1103 * Check that an NSEC3 rrset does not have a type set.
1104 * None of the nsec3s in a hash-collision are allowed to have the type.
1105 * (since we do not know which one is the nsec3 looked at, flags, ..., we
1106 * ignore the cached item and let it bypass negative caching).
1107 * @param k: the nsec3 rrset to check.
1108 * @param t: type to check
1109 * @return true if no RRs have the type.
1111 static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t)
1113 int count = (int)((struct packed_rrset_data*)k->entry.data)->count;
1115 for(i=0; i<count; i++)
1116 if(nsec3_has_type(k, i, t))
1122 * See if rrset exists in rrset cache.
1123 * If it does, the bit is checked, and if not expired, it is returned
1124 * allocated in region.
1125 * @param rrset_cache: rrset cache
1126 * @param qname: to lookup rrset name
1127 * @param qname_len: length of qname.
1128 * @param qtype: type of rrset to lookup, host order
1129 * @param qclass: class of rrset to lookup, host order
1130 * @param flags: flags for rrset to lookup
1131 * @param region: where to alloc result
1132 * @param checkbit: if true, a bit in the nsec typemap is checked for absence.
1133 * @param checktype: which bit to check
1134 * @param now: to check ttl against
1135 * @return rrset or NULL
1137 static struct ub_packed_rrset_key*
1138 grab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len,
1139 uint16_t qtype, uint16_t qclass, uint32_t flags,
1140 struct regional* region, int checkbit, uint16_t checktype,
1143 struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache,
1144 qname, qname_len, qtype, qclass, flags, now, 0);
1145 struct packed_rrset_data* d;
1147 d = (struct packed_rrset_data*)k->entry.data;
1149 lock_rw_unlock(&k->entry.lock);
1152 /* only secure or unchecked records that have signatures. */
1153 if( ! ( d->security == sec_status_secure ||
1154 (d->security == sec_status_unchecked &&
1155 d->rrsig_count > 0) ) ) {
1156 lock_rw_unlock(&k->entry.lock);
1159 /* check if checktype is absent */
1161 (qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) ||
1162 (qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype))
1164 lock_rw_unlock(&k->entry.lock);
1167 /* looks OK! copy to region and return it */
1168 r = packed_rrset_copy_region(k, region, now);
1169 /* if it failed, we return the NULL */
1170 lock_rw_unlock(&k->entry.lock);
1174 /** find nsec3 closest encloser in neg cache */
1175 static struct val_neg_data*
1176 neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
1177 int qlabs, ldns_buffer* buf, uint8_t* hashnc, size_t* nclen)
1179 struct val_neg_data* data;
1180 uint8_t hashce[NSEC3_SHA_LEN];
1182 size_t celen, b32len;
1187 if(!(celen=nsec3_get_hashed(buf, qname, qname_len,
1188 zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt,
1189 zone->nsec3_saltlen, hashce, sizeof(hashce))))
1191 if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name,
1192 zone->len, b32, sizeof(b32))))
1195 /* lookup (exact match only) */
1196 data = neg_find_data(zone, b32, b32len, zone->labs+1);
1197 if(data && data->in_use) {
1198 /* found ce match! */
1203 memmove(hashnc, hashce, celen);
1204 dname_remove_label(&qname, &qname_len);
1210 /** check nsec3 parameters on nsec3 rrset with current zone values */
1212 neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset)
1217 if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen))
1219 return (h == zone->nsec3_hash && it == zone->nsec3_iter &&
1220 slen == zone->nsec3_saltlen &&
1221 memcmp(zone->nsec3_salt, s, slen) == 0);
1224 /** get next closer for nsec3 proof */
1225 static struct ub_packed_rrset_key*
1226 neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen,
1227 struct rrset_cache* rrset_cache, struct regional* region,
1228 uint32_t now, uint8_t* b32, size_t maxb32)
1230 struct ub_packed_rrset_key* nc_rrset;
1231 struct val_neg_data* data;
1234 if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name,
1235 zone->len, b32, maxb32)))
1237 (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data);
1238 if(!data && zone->tree.count != 0) {
1239 /* could be before the first entry ; return the last
1240 * entry (possibly the rollover nsec3 at end) */
1241 data = (struct val_neg_data*)rbtree_last(&zone->tree);
1243 while(data && !data->in_use)
1244 data = data->parent;
1247 /* got a data element in tree, grab it */
1248 nc_rrset = grab_nsec(rrset_cache, data->name, data->len,
1249 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now);
1252 if(!neg_params_ok(zone, nc_rrset))
1257 /** neg cache nsec3 proof procedure*/
1258 static struct dns_msg*
1259 neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
1260 int qlabs, ldns_buffer* buf, struct rrset_cache* rrset_cache,
1261 struct regional* region, uint32_t now, uint8_t* topname)
1263 struct dns_msg* msg;
1264 struct val_neg_data* data;
1265 uint8_t hashnc[NSEC3_SHA_LEN];
1267 struct ub_packed_rrset_key* ce_rrset, *nc_rrset;
1268 struct nsec3_cached_hash c;
1269 uint8_t nc_b32[257];
1271 /* for NSEC3 ; determine the closest encloser for which we
1272 * can find an exact match. Remember the hashed lower name,
1273 * since that is the one we need a closest match for.
1274 * If we find a match straight away, then it becomes NODATA.
1275 * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation.
1276 * Also check that parameters are the same on closest encloser
1277 * and on closest match.
1279 if(!zone->nsec3_hash)
1280 return NULL; /* not nsec3 zone */
1282 if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf,
1287 /* grab the ce rrset */
1288 ce_rrset = grab_nsec(rrset_cache, data->name, data->len,
1289 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1,
1290 LDNS_RR_TYPE_DS, now);
1293 if(!neg_params_ok(zone, ce_rrset))
1297 /* exact match, just check the type bits */
1298 /* need: -SOA, -DS, +NS */
1299 if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) ||
1300 nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) ||
1301 !nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS))
1303 if(!(msg = dns_msg_create(qname, qname_len,
1304 LDNS_RR_TYPE_DS, zone->dclass, region, 1)))
1306 /* TTL reduced in grab_nsec */
1307 if(!dns_msg_authadd(msg, region, ce_rrset, 0))
1312 /* optout is not allowed without knowing the trust-anchor in use,
1313 * otherwise the optout could spoof away that anchor */
1317 /* if there is no exact match, it must be in an optout span
1318 * (an existing DS implies an NSEC3 must exist) */
1319 nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache,
1320 region, now, nc_b32, sizeof(nc_b32));
1323 if(!neg_params_ok(zone, nc_rrset))
1325 if(!nsec3_has_optout(nc_rrset, 0))
1330 c.b32_len = (size_t)nc_b32[0];
1331 if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) {
1332 /* nc_rrset covers the next closer name.
1333 * ce_rrset equals a closer encloser.
1334 * nc_rrset is optout.
1335 * No need to check wildcard for type DS */
1336 /* capacity=3: ce + nc + soa(if needed) */
1337 if(!(msg = dns_msg_create(qname, qname_len,
1338 LDNS_RR_TYPE_DS, zone->dclass, region, 3)))
1340 /* now=0 because TTL was reduced in grab_nsec */
1341 if(!dns_msg_authadd(msg, region, ce_rrset, 0))
1343 if(!dns_msg_authadd(msg, region, nc_rrset, 0))
1351 * Add SOA record for external responses.
1352 * @param rrset_cache: to look into.
1353 * @param now: current time.
1354 * @param region: where to perform the allocation
1355 * @param msg: current msg with NSEC.
1356 * @param zone: val_neg_zone if we have one.
1357 * @return false on lookup or alloc failure.
1359 static int add_soa(struct rrset_cache* rrset_cache, uint32_t now,
1360 struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone)
1362 struct ub_packed_rrset_key* soa;
1369 dclass = zone->dclass;
1371 /* Assumes the signer is the zone SOA to add */
1372 nm = reply_nsec_signer(msg->rep, &nmlen, &dclass);
1376 soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA,
1377 dclass, PACKED_RRSET_SOA_NEG, now, 0);
1380 if(!dns_msg_authadd(msg, region, soa, now)) {
1381 lock_rw_unlock(&soa->entry.lock);
1384 lock_rw_unlock(&soa->entry.lock);
1389 val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo,
1390 struct regional* region, struct rrset_cache* rrset_cache,
1391 ldns_buffer* buf, uint32_t now, int addsoa, uint8_t* topname)
1393 struct dns_msg* msg;
1394 struct ub_packed_rrset_key* rrset;
1398 struct val_neg_zone* zone;
1400 /* only for DS queries */
1401 if(qinfo->qtype != LDNS_RR_TYPE_DS)
1403 log_assert(!topname || dname_subdomain_c(qinfo->qname, topname));
1405 /* see if info from neg cache is available
1406 * For NSECs, because there is no optout; a DS next to a delegation
1407 * always has exactly an NSEC for it itself; check its DS bit.
1408 * flags=0 (not the zone apex).
1410 rrset = grab_nsec(rrset_cache, qinfo->qname, qinfo->qname_len,
1411 LDNS_RR_TYPE_NSEC, qinfo->qclass, 0, region, 1,
1414 /* return msg with that rrset */
1415 if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len,
1416 qinfo->qtype, qinfo->qclass, region, 2)))
1418 /* TTL already subtracted in grab_nsec */
1419 if(!dns_msg_authadd(msg, region, rrset, 0))
1421 if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL))
1426 /* check NSEC3 neg cache for type DS */
1427 /* need to look one zone higher for DS type */
1428 zname = qinfo->qname;
1429 zname_len = qinfo->qname_len;
1430 dname_remove_label(&zname, &zname_len);
1431 zname_labs = dname_count_labels(zname);
1433 /* lookup closest zone */
1434 lock_basic_lock(&neg->lock);
1435 zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs,
1437 while(zone && !zone->in_use)
1438 zone = zone->parent;
1439 /* check that the zone is not too high up so that we do not pick data
1440 * out of a zone that is above the last-seen key (or trust-anchor). */
1441 if(zone && topname) {
1442 if(!dname_subdomain_c(zone->name, topname))
1446 lock_basic_unlock(&neg->lock);
1450 msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len,
1451 zname_labs+1, buf, rrset_cache, region, now, topname);
1452 if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) {
1453 lock_basic_unlock(&neg->lock);
1456 lock_basic_unlock(&neg->lock);