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