1 files changed, 1455 insertions, 0 deletions
diff --git a/3rdParty/Unbound/src/src/validator/val_neg.c b/3rdParty/Unbound/src/src/validator/val_neg.c
new file mode 100644
index 0000000..60434db
--- /dev/null
+++ b/3rdParty/Unbound/src/src/validator/val_neg.c
@@ -0,0 +1,1455 @@
+/*
+ * validator/val_neg.c - validator aggressive negative caching functions.
+ *
+ * Copyright (c) 2008, NLnet Labs. All rights reserved.
+ *
+ * This software is open source.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * 
+ * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * 
+ * Neither the name of the NLNET LABS nor the names of its contributors may
+ * be used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/**
+ * \file
+ *
+ * This file contains helper functions for the validator module.
+ * The functions help with aggressive negative caching.
+ * This creates new denials of existance, and proofs for absence of types
+ * from cached NSEC records.
+ */
+#include "config.h"
+#ifdef HAVE_OPENSSL_SSL_H
+#include "openssl/ssl.h"
+#endif
+#include "validator/val_neg.h"
+#include "validator/val_nsec.h"
+#include "validator/val_nsec3.h"
+#include "validator/val_utils.h"
+#include "util/data/dname.h"
+#include "util/data/msgreply.h"
+#include "util/log.h"
+#include "util/net_help.h"
+#include "util/config_file.h"
+#include "services/cache/rrset.h"
+#include "services/cache/dns.h"
+
+int val_neg_data_compare(const void* a, const void* b)
+{
+	struct val_neg_data* x = (struct val_neg_data*)a;
+	struct val_neg_data* y = (struct val_neg_data*)b;
+	int m;
+	return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
+}
+
+int val_neg_zone_compare(const void* a, const void* b)
+{
+	struct val_neg_zone* x = (struct val_neg_zone*)a;
+	struct val_neg_zone* y = (struct val_neg_zone*)b;
+	int m;
+	if(x->dclass != y->dclass) {
+		if(x->dclass < y->dclass)
+			return -1;
+		return 1;
+	}
+	return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
+}
+
+struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter)
+{
+	struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1, 
+		sizeof(*neg));
+	if(!neg) {
+		log_err("Could not create neg cache: out of memory");
+		return NULL;
+	}
+	neg->nsec3_max_iter = maxiter;
+	neg->max = 1024*1024; /* 1 M is thousands of entries */
+	if(cfg) neg->max = cfg->neg_cache_size;
+	rbtree_init(&neg->tree, &val_neg_zone_compare);
+	lock_basic_init(&neg->lock);
+	lock_protect(&neg->lock, neg, sizeof(*neg));
+	return neg;
+}
+
+size_t val_neg_get_mem(struct val_neg_cache* neg)
+{
+	size_t result;
+	lock_basic_lock(&neg->lock);
+	result = sizeof(*neg) + neg->use;
+	lock_basic_unlock(&neg->lock);
+	return result;
+}
+
+/** clear datas on cache deletion */
+static void
+neg_clear_datas(rbnode_t* n, void* ATTR_UNUSED(arg))
+{
+	struct val_neg_data* d = (struct val_neg_data*)n;
+	free(d->name);
+	free(d);
+}
+
+/** clear zones on cache deletion */
+static void
+neg_clear_zones(rbnode_t* n, void* ATTR_UNUSED(arg))
+{
+	struct val_neg_zone* z = (struct val_neg_zone*)n;
+	/* delete all the rrset entries in the tree */
+	traverse_postorder(&z->tree, &neg_clear_datas, NULL);
+	free(z->nsec3_salt);
+	free(z->name);
+	free(z);
+}
+
+void neg_cache_delete(struct val_neg_cache* neg)
+{
+	if(!neg) return;
+	lock_basic_destroy(&neg->lock);
+	/* delete all the zones in the tree */
+	traverse_postorder(&neg->tree, &neg_clear_zones, NULL);
+	free(neg);
+}
+
+/**
+ * Put data element at the front of the LRU list.
+ * @param neg: negative cache with LRU start and end.
+ * @param data: this data is fronted.
+ */
+static void neg_lru_front(struct val_neg_cache* neg, 
+	struct val_neg_data* data)
+{
+	data->prev = NULL;
+	data->next = neg->first;
+	if(!neg->first)
+		neg->last = data;
+	else	neg->first->prev = data;
+	neg->first = data;
+}
+
+/**
+ * Remove data element from LRU list.
+ * @param neg: negative cache with LRU start and end.
+ * @param data: this data is removed from the list.
+ */
+static void neg_lru_remove(struct val_neg_cache* neg, 
+	struct val_neg_data* data)
+{
+	if(data->prev)
+		data->prev->next = data->next;
+	else	neg->first = data->next;
+	if(data->next)
+		data->next->prev = data->prev;
+	else	neg->last = data->prev;
+}
+
+/**
+ * Touch LRU for data element, put it at the start of the LRU list.
+ * @param neg: negative cache with LRU start and end.
+ * @param data: this data is used.
+ */
+static void neg_lru_touch(struct val_neg_cache* neg, 
+	struct val_neg_data* data)
+{
+	if(data == neg->first)
+		return; /* nothing to do */
+	/* remove from current lru position */
+	neg_lru_remove(neg, data);
+	/* add at front */
+	neg_lru_front(neg, data);
+}
+
+/**
+ * Delete a zone element from the negative cache.
+ * May delete other zone elements to keep tree coherent, or
+ * only mark the element as 'not in use'.
+ * @param neg: negative cache.
+ * @param z: zone element to delete.
+ */
+static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z)
+{
+	struct val_neg_zone* p, *np;
+	if(!z) return;
+	log_assert(z->in_use);
+	log_assert(z->count > 0);
+	z->in_use = 0;
+
+	/* go up the tree and reduce counts */
+	p = z;
+	while(p) {
+		log_assert(p->count > 0);
+		p->count --;
+		p = p->parent;
+	}
+
+	/* remove zones with zero count */
+	p = z;
+	while(p && p->count == 0) {
+		np = p->parent;
+		(void)rbtree_delete(&neg->tree, &p->node);
+		neg->use -= p->len + sizeof(*p);
+		free(p->nsec3_salt);
+		free(p->name);
+		free(p);
+		p = np;
+	}
+}
+	
+void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el)
+{
+	struct val_neg_zone* z;
+	struct val_neg_data* p, *np;
+	if(!el) return;
+	z = el->zone;
+	log_assert(el->in_use);
+	log_assert(el->count > 0);
+	el->in_use = 0;
+
+	/* remove it from the lru list */
+	neg_lru_remove(neg, el);
+	
+	/* go up the tree and reduce counts */
+	p = el;
+	while(p) {
+		log_assert(p->count > 0);
+		p->count --;
+		p = p->parent;
+	}
+
+	/* delete 0 count items from tree */
+	p = el;
+	while(p && p->count == 0) {
+		np = p->parent;
+		(void)rbtree_delete(&z->tree, &p->node);
+		neg->use -= p->len + sizeof(*p);
+		free(p->name);
+		free(p);
+		p = np;
+	}
+
+	/* check if the zone is now unused */
+	if(z->tree.count == 0) {
+		neg_delete_zone(neg, z);
+	}
+}
+
+/**
+ * Create more space in negative cache
+ * The oldest elements are deleted until enough space is present.
+ * Empty zones are deleted.
+ * @param neg: negative cache.
+ * @param need: how many bytes are needed.
+ */
+static void neg_make_space(struct val_neg_cache* neg, size_t need)
+{
+	/* delete elements until enough space or its empty */
+	while(neg->last && neg->max < neg->use + need) {
+		neg_delete_data(neg, neg->last);
+	}
+}
+
+struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 
+	uint8_t* nm, size_t len, uint16_t dclass)
+{
+	struct val_neg_zone lookfor;
+	struct val_neg_zone* result;
+	lookfor.node.key = &lookfor;
+	lookfor.name = nm;
+	lookfor.len = len;
+	lookfor.labs = dname_count_labels(lookfor.name);
+	lookfor.dclass = dclass;
+
+	result = (struct val_neg_zone*)
+		rbtree_search(&neg->tree, lookfor.node.key);
+	return result;
+}
+
+/**
+ * Find the given data
+ * @param zone: negative zone
+ * @param nm: what to look for.
+ * @param len: length of nm
+ * @param labs: labels in nm
+ * @return data or NULL if not found.
+ */
+static struct val_neg_data* neg_find_data(struct val_neg_zone* zone, 
+	uint8_t* nm, size_t len, int labs)
+{
+	struct val_neg_data lookfor;
+	struct val_neg_data* result;
+	lookfor.node.key = &lookfor;
+	lookfor.name = nm;
+	lookfor.len = len;
+	lookfor.labs = labs;
+
+	result = (struct val_neg_data*)
+		rbtree_search(&zone->tree, lookfor.node.key);
+	return result;
+}
+
+/**
+ * Calculate space needed for the data and all its parents
+ * @param rep: NSEC entries.
+ * @return size.
+ */
+static size_t calc_data_need(struct reply_info* rep)
+{
+	uint8_t* d;
+	size_t i, len, res = 0;
+
+	for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) {
+		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
+			d = rep->rrsets[i]->rk.dname;
+			len = rep->rrsets[i]->rk.dname_len;
+			res = sizeof(struct val_neg_data) + len;
+			while(!dname_is_root(d)) {
+				log_assert(len > 1); /* not root label */
+				dname_remove_label(&d, &len);
+				res += sizeof(struct val_neg_data) + len;
+			}
+		}
+	}
+	return res;
+}
+
+/**
+ * Calculate space needed for zone and all its parents
+ * @param d: name of zone
+ * @param len: length of name
+ * @return size.
+ */
+static size_t calc_zone_need(uint8_t* d, size_t len)
+{
+	size_t res = sizeof(struct val_neg_zone) + len;
+	while(!dname_is_root(d)) {
+		log_assert(len > 1); /* not root label */
+		dname_remove_label(&d, &len);
+		res += sizeof(struct val_neg_zone) + len;
+	}
+	return res;
+}
+
+/**
+ * Find closest existing parent zone of the given name.
+ * @param neg: negative cache.
+ * @param nm: name to look for
+ * @param nm_len: length of nm
+ * @param labs: labelcount of nm.
+ * @param qclass: class.
+ * @return the zone or NULL if none found.
+ */
+static struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg,
+	uint8_t* nm, size_t nm_len, int labs, uint16_t qclass)
+{
+	struct val_neg_zone key;
+	struct val_neg_zone* result;
+	rbnode_t* res = NULL;
+	key.node.key = &key;
+	key.name = nm;
+	key.len = nm_len;
+	key.labs = labs;
+	key.dclass = qclass;
+	if(rbtree_find_less_equal(&neg->tree, &key, &res)) {
+		/* exact match */
+		result = (struct val_neg_zone*)res;
+	} else {
+		/* smaller element (or no element) */
+		int m;
+		result = (struct val_neg_zone*)res;
+		if(!result || result->dclass != qclass)
+			return NULL;
+		/* count number of labels matched */
+		(void)dname_lab_cmp(result->name, result->labs, key.name,
+			key.labs, &m);
+		while(result) { /* go up until qname is subdomain of stub */
+			if(result->labs <= m)
+				break;
+			result = result->parent;
+		}
+	}
+	return result;
+}
+
+/**
+ * Find closest existing parent data for the given name.
+ * @param zone: to look in.
+ * @param nm: name to look for
+ * @param nm_len: length of nm
+ * @param labs: labelcount of nm.
+ * @return the data or NULL if none found.
+ */
+static struct val_neg_data* neg_closest_data_parent(
+	struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs)
+{
+	struct val_neg_data key;
+	struct val_neg_data* result;
+	rbnode_t* res = NULL;
+	key.node.key = &key;
+	key.name = nm;
+	key.len = nm_len;
+	key.labs = labs;
+	if(rbtree_find_less_equal(&zone->tree, &key, &res)) {
+		/* exact match */
+		result = (struct val_neg_data*)res;
+	} else {
+		/* smaller element (or no element) */
+		int m;
+		result = (struct val_neg_data*)res;
+		if(!result)
+			return NULL;
+		/* count number of labels matched */
+		(void)dname_lab_cmp(result->name, result->labs, key.name,
+			key.labs, &m);
+		while(result) { /* go up until qname is subdomain of stub */
+			if(result->labs <= m)
+				break;
+			result = result->parent;
+		}
+	}
+	return result;
+}
+
+/**
+ * Create a single zone node
+ * @param nm: name for zone (copied)
+ * @param nm_len: length of name
+ * @param labs: labels in name.
+ * @param dclass: class of zone, host order.
+ * @return new zone or NULL on failure
+ */
+static struct val_neg_zone* neg_setup_zone_node(
+	uint8_t* nm, size_t nm_len, int labs, uint16_t dclass)
+{
+	struct val_neg_zone* zone = 
+		(struct val_neg_zone*)calloc(1, sizeof(*zone));
+	if(!zone) {
+		return NULL;
+	}
+	zone->node.key = zone;
+	zone->name = memdup(nm, nm_len);
+	if(!zone->name) {
+		free(zone);
+		return NULL;
+	}
+	zone->len = nm_len;
+	zone->labs = labs;
+	zone->dclass = dclass;
+
+	rbtree_init(&zone->tree, &val_neg_data_compare);
+	return zone;
+}
+
+/**
+ * Create a linked list of parent zones, starting at longname ending on
+ * the parent (can be NULL, creates to the root).
+ * @param nm: name for lowest in chain
+ * @param nm_len: length of name
+ * @param labs: labels in name.
+ * @param dclass: class of zone.
+ * @param parent: NULL for to root, else so it fits under here.
+ * @return zone; a chain of zones and their parents up to the parent.
+ *  	or NULL on malloc failure
+ */
+static struct val_neg_zone* neg_zone_chain(
+	uint8_t* nm, size_t nm_len, int labs, uint16_t dclass,
+	struct val_neg_zone* parent)
+{
+	int i;
+	int tolabs = parent?parent->labs:0;
+	struct val_neg_zone* zone, *prev = NULL, *first = NULL;
+
+	/* create the new subtree, i is labelcount of current creation */
+	/* this creates a 'first' to z->parent=NULL list of zones */
+	for(i=labs; i!=tolabs; i--) {
+		/* create new item */
+		zone = neg_setup_zone_node(nm, nm_len, i, dclass);
+		if(!zone) {
+			/* need to delete other allocations in this routine!*/
+			struct val_neg_zone* p=first, *np;
+			while(p) {
+				np = p->parent;
+				free(p);
+				free(p->name);
+				p = np;
+			}
+			return NULL;
+		}
+		if(i == labs) {
+			first = zone;
+		} else {
+			prev->parent = zone;
+		}
+		/* prepare for next name */
+		prev = zone;
+		dname_remove_label(&nm, &nm_len);
+	}
+	return first;
+}	
+
+void val_neg_zone_take_inuse(struct val_neg_zone* zone)
+{
+	if(!zone->in_use) {
+		struct val_neg_zone* p;
+		zone->in_use = 1;
+		/* increase usage count of all parents */
+		for(p=zone; p; p = p->parent) {
+			p->count++;
+		}
+	}
+}
+
+struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
+	uint8_t* nm, size_t nm_len, uint16_t dclass)
+{
+	struct val_neg_zone* zone;
+	struct val_neg_zone* parent;
+	struct val_neg_zone* p, *np;
+	int labs = dname_count_labels(nm);
+
+	/* find closest enclosing parent zone that (still) exists */
+	parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass);
+	if(parent && query_dname_compare(parent->name, nm) == 0)
+		return parent; /* already exists, weird */
+	/* if parent exists, it is in use */
+	log_assert(!parent || parent->count > 0);
+	zone = neg_zone_chain(nm, nm_len, labs, dclass, parent);
+	if(!zone) {
+		return NULL;
+	}
+
+	/* insert the list of zones into the tree */
+	p = zone;
+	while(p) {
+		np = p->parent;
+		/* mem use */
+		neg->use += sizeof(struct val_neg_zone) + p->len;
+		/* insert in tree */
+		(void)rbtree_insert(&neg->tree, &p->node);
+		/* last one needs proper parent pointer */
+		if(np == NULL)
+			p->parent = parent;
+		p = np;
+	}
+	return zone;
+}
+
+/** find zone name of message, returns the SOA record */
+static struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep)
+{
+	size_t i;
+	for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
+		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA)
+			return rep->rrsets[i];
+	}
+	return NULL;
+}
+
+/** see if the reply has NSEC records worthy of caching */
+static int reply_has_nsec(struct reply_info* rep)
+{
+	size_t i;
+	struct packed_rrset_data* d;
+	if(rep->security != sec_status_secure)
+		return 0;
+	for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
+		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
+			d = (struct packed_rrset_data*)rep->rrsets[i]->
+				entry.data;
+			if(d->security == sec_status_secure)
+				return 1;
+		}
+	}
+	return 0;
+}
+
+
+/**
+ * Create single node of data element.
+ * @param nm: name (copied)
+ * @param nm_len: length of name
+ * @param labs: labels in name.
+ * @return element with name nm, or NULL malloc failure.
+ */
+static struct val_neg_data* neg_setup_data_node(
+	uint8_t* nm, size_t nm_len, int labs)
+{
+	struct val_neg_data* el;
+	el = (struct val_neg_data*)calloc(1, sizeof(*el));
+	if(!el) {
+		return NULL;
+	}
+	el->node.key = el;
+	el->name = memdup(nm, nm_len);
+	if(!el->name) {
+		free(el);
+		return NULL;
+	}
+	el->len = nm_len;
+	el->labs = labs;
+	return el;
+}
+
+/**
+ * Create chain of data element and parents
+ * @param nm: name
+ * @param nm_len: length of name
+ * @param labs: labels in name.
+ * @param parent: up to where to make, if NULL up to root label.
+ * @return lowest element with name nm, or NULL malloc failure.
+ */
+static struct val_neg_data* neg_data_chain(
+	uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent)
+{
+	int i;
+	int tolabs = parent?parent->labs:0;
+	struct val_neg_data* el, *first = NULL, *prev = NULL;
+
+	/* create the new subtree, i is labelcount of current creation */
+	/* this creates a 'first' to z->parent=NULL list of zones */
+	for(i=labs; i!=tolabs; i--) {
+		/* create new item */
+		el = neg_setup_data_node(nm, nm_len, i);
+		if(!el) {
+			/* need to delete other allocations in this routine!*/
+			struct val_neg_data* p = first, *np;
+			while(p) {
+				np = p->parent;
+				free(p);
+				free(p->name);
+				p = np;
+			}
+			return NULL;
+		}
+		if(i == labs) {
+			first = el;
+		} else {
+			prev->parent = el;
+		}
+
+		/* prepare for next name */
+		prev = el;
+		dname_remove_label(&nm, &nm_len);
+	}
+	return first;
+}
+
+/**
+ * Remove NSEC records between start and end points.
+ * By walking the tree, the tree is sorted canonically.
+ * @param neg: negative cache.
+ * @param zone: the zone
+ * @param el: element to start walking at.
+ * @param nsec: the nsec record with the end point
+ */
+static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone, 
+	struct val_neg_data* el, struct ub_packed_rrset_key* nsec)
+{
+	struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
+		entry.data;
+	uint8_t* end;
+	size_t end_len;
+	int end_labs, m;
+	rbnode_t* walk, *next;
+	struct val_neg_data* cur;
+	uint8_t buf[257];
+	/* get endpoint */
+	if(!d || d->count == 0 || d->rr_len[0] < 2+1)
+		return;
+	if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) {
+		end = d->rr_data[0]+2;
+		end_len = dname_valid(end, d->rr_len[0]-2);
+		end_labs = dname_count_labels(end);
+	} else {
+		/* NSEC3 */
+		if(!nsec3_get_nextowner_b32(nsec, 0, buf, sizeof(buf)))
+			return;
+		end = buf;
+		end_labs = dname_count_size_labels(end, &end_len);
+	}
+
+	/* sanity check, both owner and end must be below the zone apex */
+	if(!dname_subdomain_c(el->name, zone->name) || 
+		!dname_subdomain_c(end, zone->name))
+		return;
+
+	/* detect end of zone NSEC ; wipe until the end of zone */
+	if(query_dname_compare(end, zone->name) == 0) {
+		end = NULL;
+	}
+
+	walk = rbtree_next(&el->node);
+	while(walk && walk != RBTREE_NULL) {
+		cur = (struct val_neg_data*)walk;
+		/* sanity check: must be larger than start */
+		if(dname_canon_lab_cmp(cur->name, cur->labs, 
+			el->name, el->labs, &m) <= 0) {
+			/* r == 0 skip original record. */
+			/* r < 0  too small! */
+			walk = rbtree_next(walk);
+			continue;
+		}
+		/* stop at endpoint, also data at empty nonterminals must be
+		 * removed (no NSECs there) so everything between 
+		 * start and end */
+		if(end && dname_canon_lab_cmp(cur->name, cur->labs,
+			end, end_labs, &m) >= 0) {
+			break;
+		}
+		/* this element has to be deleted, but we cannot do it
+		 * now, because we are walking the tree still ... */
+		/* get the next element: */
+		next = rbtree_next(walk);
+		/* now delete the original element, this may trigger
+		 * rbtree rebalances, but really, the next element is
+		 * the one we need.
+		 * But it may trigger delete of other data and the
+		 * entire zone. However, if that happens, this is done
+		 * by deleting the *parents* of the element for deletion,
+		 * and maybe also the entire zone if it is empty. 
+		 * But parents are smaller in canonical compare, thus,
+		 * if a larger element exists, then it is not a parent,
+		 * it cannot get deleted, the zone cannot get empty.
+		 * If the next==NULL, then zone can be empty. */
+		if(cur->in_use)
+			neg_delete_data(neg, cur);
+		walk = next;
+	}
+}
+
+void neg_insert_data(struct val_neg_cache* neg, 
+	struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec)
+{
+	struct packed_rrset_data* d;
+	struct val_neg_data* parent;
+	struct val_neg_data* el;
+	uint8_t* nm = nsec->rk.dname;
+	size_t nm_len = nsec->rk.dname_len;
+	int labs = dname_count_labels(nsec->rk.dname);
+
+	d = (struct packed_rrset_data*)nsec->entry.data;
+	if( !(d->security == sec_status_secure ||
+		(d->security == sec_status_unchecked && d->rrsig_count > 0)))
+		return;
+	log_nametypeclass(VERB_ALGO, "negcache rr", 
+		nsec->rk.dname, ntohs(nsec->rk.type), 
+		ntohs(nsec->rk.rrset_class));
+
+	/* find closest enclosing parent data that (still) exists */
+	parent = neg_closest_data_parent(zone, nm, nm_len, labs);
+	if(parent && query_dname_compare(parent->name, nm) == 0) {
+		/* perfect match already exists */
+		log_assert(parent->count > 0);
+		el = parent;
+	} else { 
+		struct val_neg_data* p, *np;
+
+		/* create subtree for perfect match */
+		/* if parent exists, it is in use */
+		log_assert(!parent || parent->count > 0);
+
+		el = neg_data_chain(nm, nm_len, labs, parent);
+		if(!el) {
+			log_err("out of memory inserting NSEC negative cache");
+			return;
+		}
+		el->in_use = 0; /* set on below */
+
+		/* insert the list of zones into the tree */
+		p = el;
+		while(p) {
+			np = p->parent;
+			/* mem use */
+			neg->use += sizeof(struct val_neg_data) + p->len;
+			/* insert in tree */
+			p->zone = zone;
+			(void)rbtree_insert(&zone->tree, &p->node);
+			/* last one needs proper parent pointer */
+			if(np == NULL)
+				p->parent = parent;
+			p = np;
+		}
+	}
+
+	if(!el->in_use) {
+		struct val_neg_data* p;
+
+		el->in_use = 1;
+		/* increase usage count of all parents */
+		for(p=el; p; p = p->parent) {
+			p->count++;
+		}
+
+		neg_lru_front(neg, el);
+	} else {
+		/* in use, bring to front, lru */
+		neg_lru_touch(neg, el);
+	}
+
+	/* if nsec3 store last used parameters */
+	if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) {
+		int h;
+		uint8_t* s;
+		size_t slen, it;
+		if(nsec3_get_params(nsec, 0, &h, &it, &s, &slen) &&
+			it <= neg->nsec3_max_iter &&
+			(h != zone->nsec3_hash || it != zone->nsec3_iter ||
+			slen != zone->nsec3_saltlen || 
+			memcmp(zone->nsec3_salt, s, slen) != 0)) {
+			uint8_t* sa = memdup(s, slen);
+			if(sa) {
+				free(zone->nsec3_salt);
+				zone->nsec3_salt = sa;
+				zone->nsec3_saltlen = slen;
+				zone->nsec3_hash = h;
+				zone->nsec3_iter = it;
+			}
+		}
+	}
+
+	/* wipe out the cache items between NSEC start and end */
+	wipeout(neg, zone, el, nsec);
+}
+
+void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep)
+{
+	size_t i, need;
+	struct ub_packed_rrset_key* soa;
+	struct val_neg_zone* zone;
+	/* see if secure nsecs inside */
+	if(!reply_has_nsec(rep))
+		return;
+	/* find the zone name in message */
+	soa = reply_find_soa(rep);
+	if(!soa)
+		return;
+
+	log_nametypeclass(VERB_ALGO, "negcache insert for zone",
+		soa->rk.dname, LDNS_RR_TYPE_SOA, ntohs(soa->rk.rrset_class));
+	
+	/* ask for enough space to store all of it */
+	need = calc_data_need(rep) + 
+		calc_zone_need(soa->rk.dname, soa->rk.dname_len);
+	lock_basic_lock(&neg->lock);
+	neg_make_space(neg, need);
+
+	/* find or create the zone entry */
+	zone = neg_find_zone(neg, soa->rk.dname, soa->rk.dname_len,
+		ntohs(soa->rk.rrset_class));
+	if(!zone) {
+		if(!(zone = neg_create_zone(neg, soa->rk.dname, 
+			soa->rk.dname_len, ntohs(soa->rk.rrset_class)))) {
+			lock_basic_unlock(&neg->lock);
+			log_err("out of memory adding negative zone");
+			return;
+		}
+	}
+	val_neg_zone_take_inuse(zone);
+
+	/* insert the NSECs */
+	for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
+		if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC)
+			continue;
+		if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 
+			zone->name)) continue;
+		/* insert NSEC into this zone's tree */
+		neg_insert_data(neg, zone, rep->rrsets[i]);
+	}
+	if(zone->tree.count == 0) {
+		/* remove empty zone if inserts failed */
+		neg_delete_zone(neg, zone);
+	}
+	lock_basic_unlock(&neg->lock);
+}
+
+/**
+ * Lookup closest data record. For NSEC denial.
+ * @param zone: zone to look in
+ * @param qname: name to look for.
+ * @param len: length of name
+ * @param labs: labels in name
+ * @param data: data element, exact or smaller or NULL
+ * @return true if exact match.
+ */
+static int neg_closest_data(struct val_neg_zone* zone,
+	uint8_t* qname, size_t len, int labs, struct val_neg_data** data)
+{
+	struct val_neg_data key;
+	rbnode_t* r;
+	key.node.key = &key;
+	key.name = qname;
+	key.len = len;
+	key.labs = labs;
+	if(rbtree_find_less_equal(&zone->tree, &key, &r)) {
+		/* exact match */
+		*data = (struct val_neg_data*)r;
+		return 1;
+	} else {
+		/* smaller match */
+		*data = (struct val_neg_data*)r;
+		return 0;
+	}
+}
+
+int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len,
+        uint16_t qclass, struct rrset_cache* rrset_cache, uint32_t now)
+{
+	/* lookup closest zone */
+	struct val_neg_zone* zone;
+	struct val_neg_data* data;
+	int labs;
+	struct ub_packed_rrset_key* nsec;
+	struct packed_rrset_data* d;
+	uint32_t flags;
+	uint8_t* wc;
+	struct query_info qinfo;
+	if(!neg) return 0;
+
+	log_nametypeclass(VERB_ALGO, "negcache dlvlookup", qname, 
+		LDNS_RR_TYPE_DLV, qclass);
+	
+	labs = dname_count_labels(qname);
+	lock_basic_lock(&neg->lock);
+	zone = neg_closest_zone_parent(neg, qname, len, labs, qclass);
+	while(zone && !zone->in_use)
+		zone = zone->parent;
+	if(!zone) {
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+	log_nametypeclass(VERB_ALGO, "negcache zone", zone->name, 0, 
+		zone->dclass);
+
+	/* DLV is defined to use NSEC only */
+	if(zone->nsec3_hash) {
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+
+	/* lookup closest data record */
+	(void)neg_closest_data(zone, qname, len, labs, &data);
+	while(data && !data->in_use)
+		data = data->parent;
+	if(!data) {
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+	log_nametypeclass(VERB_ALGO, "negcache rr", data->name, 
+		LDNS_RR_TYPE_NSEC, zone->dclass);
+
+	/* lookup rrset in rrset cache */
+	flags = 0;
+	if(query_dname_compare(data->name, zone->name) == 0)
+		flags = PACKED_RRSET_NSEC_AT_APEX;
+	nsec = rrset_cache_lookup(rrset_cache, data->name, data->len,
+		LDNS_RR_TYPE_NSEC, zone->dclass, flags, now, 0);
+
+	/* check if secure and TTL ok */
+	if(!nsec) {
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+	d = (struct packed_rrset_data*)nsec->entry.data;
+	if(!d || now > d->ttl) {
+		lock_rw_unlock(&nsec->entry.lock);
+		/* delete data record if expired */
+		neg_delete_data(neg, data);
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+	if(d->security != sec_status_secure) {
+		lock_rw_unlock(&nsec->entry.lock);
+		neg_delete_data(neg, data);
+		lock_basic_unlock(&neg->lock);
+		return 0;
+	}
+	verbose(VERB_ALGO, "negcache got secure rrset");
+
+	/* check NSEC security */
+	/* check if NSEC proves no DLV type exists */
+	/* check if NSEC proves NXDOMAIN for qname */
+	qinfo.qname = qname;
+	qinfo.qtype = LDNS_RR_TYPE_DLV;
+	qinfo.qclass = qclass;
+	if(!nsec_proves_nodata(nsec, &qinfo, &wc) &&
+		!val_nsec_proves_name_error(nsec, qname)) {
+		/* the NSEC is not a denial for the DLV */
+		lock_rw_unlock(&nsec->entry.lock);
+		lock_basic_unlock(&neg->lock);
+		verbose(VERB_ALGO, "negcache not proven");
+		return 0;
+	}
+	/* so the NSEC was a NODATA proof, or NXDOMAIN proof. */
+
+	/* no need to check for wildcard NSEC; no wildcards in DLV repos */
+	/* no need to lookup SOA record for client; no response message */
+
+	lock_rw_unlock(&nsec->entry.lock);
+	/* if OK touch the LRU for neg_data element */
+	neg_lru_touch(neg, data);
+	lock_basic_unlock(&neg->lock);
+	verbose(VERB_ALGO, "negcache DLV denial proven");
+	return 1;
+}
+
+/** see if the reply has signed NSEC records and return the signer */
+static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len,
+	uint16_t* dclass)
+{
+	size_t i;
+	struct packed_rrset_data* d;
+	uint8_t* s;
+	for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
+		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC ||
+			ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) {
+			d = (struct packed_rrset_data*)rep->rrsets[i]->
+				entry.data;
+			/* return first signer name of first NSEC */
+			if(d->rrsig_count != 0) {
+				val_find_rrset_signer(rep->rrsets[i],
+					&s, signer_len);
+				if(s && *signer_len) {
+					*dclass = ntohs(rep->rrsets[i]->
+						rk.rrset_class);
+					return s;
+				}
+			}
+		}
+	}
+	return 0;
+}
+
+void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
+	uint8_t* zone_name)
+{
+	size_t i, need;
+	uint8_t* signer;
+	size_t signer_len;
+	uint16_t dclass;
+	struct val_neg_zone* zone;
+	/* no SOA in this message, find RRSIG over NSEC's signer name.
+	 * note the NSEC records are maybe not validated yet */
+	signer = reply_nsec_signer(rep, &signer_len, &dclass);
+	if(!signer) 
+		return;
+	if(!dname_subdomain_c(signer, zone_name)) {
+		/* the signer is not in the bailiwick, throw it out */
+		return;
+	}
+
+	log_nametypeclass(VERB_ALGO, "negcache insert referral ",
+		signer, LDNS_RR_TYPE_NS, dclass);
+	
+	/* ask for enough space to store all of it */
+	need = calc_data_need(rep) + calc_zone_need(signer, signer_len);
+	lock_basic_lock(&neg->lock);
+	neg_make_space(neg, need);
+
+	/* find or create the zone entry */
+	zone = neg_find_zone(neg, signer, signer_len, dclass);
+	if(!zone) {
+		if(!(zone = neg_create_zone(neg, signer, signer_len, 
+			dclass))) {
+			lock_basic_unlock(&neg->lock);
+			log_err("out of memory adding negative zone");
+			return;
+		}
+	}
+	val_neg_zone_take_inuse(zone);
+
+	/* insert the NSECs */
+	for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
+		if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC &&
+			ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3)
+			continue;
+		if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 
+			zone->name)) continue;
+		/* insert NSEC into this zone's tree */
+		neg_insert_data(neg, zone, rep->rrsets[i]);
+	}
+	if(zone->tree.count == 0) {
+		/* remove empty zone if inserts failed */
+		neg_delete_zone(neg, zone);
+	}
+	lock_basic_unlock(&neg->lock);
+}
+
+/**
+ * Check that an NSEC3 rrset does not have a type set.
+ * None of the nsec3s in a hash-collision are allowed to have the type.
+ * (since we do not know which one is the nsec3 looked at, flags, ..., we
+ * ignore the cached item and let it bypass negative caching).
+ * @param k: the nsec3 rrset to check.
+ * @param t: type to check
+ * @return true if no RRs have the type.
+ */
+static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t)
+{
+	int count = (int)((struct packed_rrset_data*)k->entry.data)->count;
+	int i;
+	for(i=0; i<count; i++)
+		if(nsec3_has_type(k, i, t))
+			return 0;
+	return 1;
+}
+
+/**
+ * See if rrset exists in rrset cache.
+ * If it does, the bit is checked, and if not expired, it is returned
+ * allocated in region.
+ * @param rrset_cache: rrset cache
+ * @param qname: to lookup rrset name
+ * @param qname_len: length of qname.
+ * @param qtype: type of rrset to lookup, host order
+ * @param qclass: class of rrset to lookup, host order
+ * @param flags: flags for rrset to lookup
+ * @param region: where to alloc result
+ * @param checkbit: if true, a bit in the nsec typemap is checked for absence.
+ * @param checktype: which bit to check
+ * @param now: to check ttl against
+ * @return rrset or NULL
+ */
+static struct ub_packed_rrset_key*
+grab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len,
+	uint16_t qtype, uint16_t qclass, uint32_t flags, 
+	struct regional* region, int checkbit, uint16_t checktype, 
+	uint32_t now)
+{
+	struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache,
+		qname, qname_len, qtype, qclass, flags, now, 0);
+	struct packed_rrset_data* d;
+	if(!k) return NULL;
+	d = (struct packed_rrset_data*)k->entry.data;
+	if(d->ttl < now) {
+		lock_rw_unlock(&k->entry.lock);
+		return NULL;
+	}
+	/* only secure or unchecked records that have signatures. */
+	if( ! ( d->security == sec_status_secure ||
+		(d->security == sec_status_unchecked &&
+		d->rrsig_count > 0) ) ) {
+		lock_rw_unlock(&k->entry.lock);
+		return NULL;
+	}
+	/* check if checktype is absent */
+	if(checkbit && (
+		(qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) ||
+		(qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype))
+		)) {
+		lock_rw_unlock(&k->entry.lock);
+		return NULL;
+	}
+	/* looks OK! copy to region and return it */
+	r = packed_rrset_copy_region(k, region, now);
+	/* if it failed, we return the NULL */
+	lock_rw_unlock(&k->entry.lock);
+	return r;
+}
+
+/** find nsec3 closest encloser in neg cache */
+static struct val_neg_data*
+neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
+		int qlabs, ldns_buffer* buf, uint8_t* hashnc, size_t* nclen)
+{
+	struct val_neg_data* data;
+	uint8_t hashce[SHA_DIGEST_LENGTH];
+	uint8_t b32[257];
+	size_t celen, b32len;
+
+	*nclen = 0;
+	while(qlabs > 0) {
+		/* hash */
+		if(!(celen=nsec3_get_hashed(buf, qname, qname_len, 
+			zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt, 
+			zone->nsec3_saltlen, hashce, sizeof(hashce))))
+			return NULL;
+		if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name,
+			zone->len, b32, sizeof(b32))))
+			return NULL;
+
+		/* lookup (exact match only) */
+		data = neg_find_data(zone, b32, b32len, zone->labs+1);
+		if(data && data->in_use) {
+			/* found ce match! */
+			return data;
+		}
+
+		*nclen = celen;
+		memmove(hashnc, hashce, celen);
+		dname_remove_label(&qname, &qname_len);
+		qlabs --;
+	}
+	return NULL;
+}
+
+/** check nsec3 parameters on nsec3 rrset with current zone values */
+static int
+neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset)
+{
+	int h;
+	uint8_t* s;
+	size_t slen, it;
+	if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen))
+		return 0;
+	return (h == zone->nsec3_hash && it == zone->nsec3_iter &&
+		slen == zone->nsec3_saltlen &&
+		memcmp(zone->nsec3_salt, s, slen) == 0);
+}
+
+/** get next closer for nsec3 proof */
+static struct ub_packed_rrset_key*
+neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen,
+	struct rrset_cache* rrset_cache, struct regional* region, 
+	uint32_t now, uint8_t* b32, size_t maxb32)
+{
+	struct ub_packed_rrset_key* nc_rrset;
+	struct val_neg_data* data;
+	size_t b32len;
+
+	if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name,
+		zone->len, b32, maxb32)))
+		return NULL;
+	(void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data);
+	if(!data && zone->tree.count != 0) {
+		/* could be before the first entry ; return the last
+		 * entry (possibly the rollover nsec3 at end) */
+		data = (struct val_neg_data*)rbtree_last(&zone->tree);
+	}
+	while(data && !data->in_use)
+		data = data->parent;
+	if(!data)
+		return NULL;
+	/* got a data element in tree, grab it */
+	nc_rrset = grab_nsec(rrset_cache, data->name, data->len, 
+		LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now);
+	if(!nc_rrset)
+		return NULL;
+	if(!neg_params_ok(zone, nc_rrset))
+		return NULL;
+	return nc_rrset;
+}
+
+/** neg cache nsec3 proof procedure*/
+static struct dns_msg*
+neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
+		int qlabs, ldns_buffer* buf, struct rrset_cache* rrset_cache,
+		struct regional* region, uint32_t now, uint8_t* topname)
+{
+	struct dns_msg* msg;
+	struct val_neg_data* data;
+	uint8_t hashnc[SHA_DIGEST_LENGTH];
+	size_t nclen;
+	struct ub_packed_rrset_key* ce_rrset, *nc_rrset;
+	struct nsec3_cached_hash c;
+	uint8_t nc_b32[257];
+
+	/* for NSEC3 ; determine the closest encloser for which we
+	 * can find an exact match. Remember the hashed lower name,
+	 * since that is the one we need a closest match for. 
+	 * If we find a match straight away, then it becomes NODATA.
+	 * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation.
+	 * Also check that parameters are the same on closest encloser
+	 * and on closest match.
+	 */
+	if(!zone->nsec3_hash) 
+		return NULL; /* not nsec3 zone */
+
+	if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf,
+		hashnc, &nclen))) {
+		return NULL;
+	}
+
+	/* grab the ce rrset */
+	ce_rrset = grab_nsec(rrset_cache, data->name, data->len, 
+		LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1, 
+		LDNS_RR_TYPE_DS, now);
+	if(!ce_rrset)
+		return NULL;
+	if(!neg_params_ok(zone, ce_rrset))
+		return NULL;
+
+	if(nclen == 0) {
+		/* exact match, just check the type bits */
+		/* need: -SOA, -DS, +NS */
+		if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) ||
+			nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) ||
+			!nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS))
+			return NULL;
+		if(!(msg = dns_msg_create(qname, qname_len, 
+			LDNS_RR_TYPE_DS, zone->dclass, region, 1))) 
+			return NULL;
+		/* TTL reduced in grab_nsec */
+		if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 
+			return NULL;
+		return msg;
+	}
+
+	/* optout is not allowed without knowing the trust-anchor in use,
+	 * otherwise the optout could spoof away that anchor */
+	if(!topname)
+		return NULL;
+
+	/* if there is no exact match, it must be in an optout span
+	 * (an existing DS implies an NSEC3 must exist) */
+	nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache, 
+		region, now, nc_b32, sizeof(nc_b32));
+	if(!nc_rrset) 
+		return NULL;
+	if(!neg_params_ok(zone, nc_rrset))
+		return NULL;
+	if(!nsec3_has_optout(nc_rrset, 0))
+		return NULL;
+	c.hash = hashnc;
+	c.hash_len = nclen;
+	c.b32 = nc_b32+1;
+	c.b32_len = (size_t)nc_b32[0];
+	if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) {
+		/* nc_rrset covers the next closer name.
+		 * ce_rrset equals a closer encloser.
+		 * nc_rrset is optout.
+		 * No need to check wildcard for type DS */
+		/* capacity=3: ce + nc + soa(if needed) */
+		if(!(msg = dns_msg_create(qname, qname_len, 
+			LDNS_RR_TYPE_DS, zone->dclass, region, 3))) 
+			return NULL;
+		/* now=0 because TTL was reduced in grab_nsec */
+		if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 
+			return NULL;
+		if(!dns_msg_authadd(msg, region, nc_rrset, 0)) 
+			return NULL;
+		return msg;
+	}
+	return NULL;
+}
+
+/**
+ * Add SOA record for external responses.
+ * @param rrset_cache: to look into.
+ * @param now: current time.
+ * @param region: where to perform the allocation
+ * @param msg: current msg with NSEC.
+ * @param zone: val_neg_zone if we have one.
+ * @return false on lookup or alloc failure.
+ */
+static int add_soa(struct rrset_cache* rrset_cache, uint32_t now,
+	struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone)
+{
+	struct ub_packed_rrset_key* soa;
+	uint8_t* nm;
+	size_t nmlen;
+	uint16_t dclass;
+	if(zone) {
+		nm = zone->name;
+		nmlen = zone->len;
+		dclass = zone->dclass;
+	} else {
+		/* Assumes the signer is the zone SOA to add */
+		nm = reply_nsec_signer(msg->rep, &nmlen, &dclass);
+		if(!nm) 
+			return 0;
+	}
+	soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA, 
+		dclass, PACKED_RRSET_SOA_NEG, now, 0);
+	if(!soa)
+		return 0;
+	if(!dns_msg_authadd(msg, region, soa, now)) {
+		lock_rw_unlock(&soa->entry.lock);
+		return 0;
+	}
+	lock_rw_unlock(&soa->entry.lock);
+	return 1;
+}
+
+struct dns_msg* 
+val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo, 
+	struct regional* region, struct rrset_cache* rrset_cache, 
+	ldns_buffer* buf, uint32_t now, int addsoa, uint8_t* topname)
+{
+	struct dns_msg* msg;
+	struct ub_packed_rrset_key* rrset;
+	uint8_t* zname;
+	size_t zname_len;
+	int zname_labs;
+	struct val_neg_zone* zone;
+
+	/* only for DS queries */
+	if(qinfo->qtype != LDNS_RR_TYPE_DS)
+		return NULL;
+	log_assert(!topname || dname_subdomain_c(qinfo->qname, topname));
+
+	/* see if info from neg cache is available 
+	 * For NSECs, because there is no optout; a DS next to a delegation
+	 * always has exactly an NSEC for it itself; check its DS bit.
+	 * flags=0 (not the zone apex).
+	 */
+	rrset = grab_nsec(rrset_cache, qinfo->qname, qinfo->qname_len,
+		LDNS_RR_TYPE_NSEC, qinfo->qclass, 0, region, 1, 
+		qinfo->qtype, now);
+	if(rrset) {
+		/* return msg with that rrset */
+		if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 
+			qinfo->qtype, qinfo->qclass, region, 2))) 
+			return NULL;
+		/* TTL already subtracted in grab_nsec */
+		if(!dns_msg_authadd(msg, region, rrset, 0)) 
+			return NULL;
+		if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL))
+			return NULL;
+		return msg;
+	}
+
+	/* check NSEC3 neg cache for type DS */
+	/* need to look one zone higher for DS type */
+	zname = qinfo->qname;
+	zname_len = qinfo->qname_len;
+	dname_remove_label(&zname, &zname_len);
+	zname_labs = dname_count_labels(zname);
+
+	/* lookup closest zone */
+	lock_basic_lock(&neg->lock);
+	zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs, 
+		qinfo->qclass);
+	while(zone && !zone->in_use)
+		zone = zone->parent;
+	/* check that the zone is not too high up so that we do not pick data
+	 * out of a zone that is above the last-seen key (or trust-anchor). */
+	if(zone && topname) {
+		if(!dname_subdomain_c(zone->name, topname))
+			zone = NULL;
+	}
+	if(!zone) {
+		lock_basic_unlock(&neg->lock);
+		return NULL;
+	}
+
+	msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len, 
+		zname_labs+1, buf, rrset_cache, region, now, topname);
+	if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) {
+		lock_basic_unlock(&neg->lock);
+		return NULL;
+	}
+	lock_basic_unlock(&neg->lock);
+	return msg;
+}