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