/usr/src/usr.sbin/unbound/validator/val

Bug Summary

File:	src/usr.sbin/unbound/validator/val_neg.c
Warning:	line 276, column 3 Use of memory after it is freed
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name val_neg.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/unbound/obj -resource-dir /usr/local/lib/clang/13.0.0 -I . -I /usr/src/usr.sbin/unbound -D SRCDIR=/usr/src/usr.sbin/unbound -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/unbound/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/unbound/validator/val_neg.c
1/*
* 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 COPYRIGHT
* HOLDER 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.
*/

36/**
* \file
*
* This file contains helper functions for the validator module.
* The functions help with aggressive negative caching.
* This creates new denials of existence, and proofs for absence of types
* from cached NSEC records.
*/
44#include "config.h"
45#ifdef HAVE_OPENSSL_SSL_H1
46#include "openssl/ssl.h"
47#define NSEC3_SHA_LEN20 SHA_DIGEST_LENGTH20
48#else
49#define NSEC3_SHA_LEN20 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"

65int val_neg_data_compare(const void* a, const void* b)
66{
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);
71}

73int val_neg_zone_compare(const void* a, const void* b)
74{
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);
84}

86struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter)
87{
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((void*)0);
}
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;
101}

103size_t val_neg_get_mem(struct val_neg_cache* neg)
104{
size_t result;
lock_basic_lock(&neg->lock);
result = sizeof(*neg) + neg->use;
lock_basic_unlock(&neg->lock);
return result;
110}

112/** clear datas on cache deletion */
113static void
114neg_clear_datas(rbnode_type* n, void* ATTR_UNUSED(arg)arg __attribute__((unused)))
115{
struct val_neg_data* d = (struct val_neg_data*)n;
free(d->name);
free(d);
119}

121/** clear zones on cache deletion */
122static void
123neg_clear_zones(rbnode_type* n, void* ATTR_UNUSED(arg)arg __attribute__((unused)))
124{
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((void*)0));
free(z->nsec3_salt);
free(z->name);
free(z);
131}

133void neg_cache_delete(struct val_neg_cache* neg)
134{
if(!neg) return;
lock_basic_destroy(&neg->lock);
/* delete all the zones in the tree */
traverse_postorder(&neg->tree, &neg_clear_zones, NULL((void*)0));
free(neg);
140}

142/**
* 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.
*/
147static void neg_lru_front(struct val_neg_cache* neg, 
struct val_neg_data* data)
149{
data->prev = NULL((void*)0);
data->next = neg->first;
if(!neg->first)
neg->last = data;
else	neg->first->prev = data;
neg->first = data;
156}

158/**
* Remove data element from LRU list.
* @param neg: negative cache with LRU start and end.
* @param data: this data is removed from the list.
*/
163static void neg_lru_remove(struct val_neg_cache* neg, 
struct val_neg_data* data)
165{
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;
172}

174/**
* 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.
*/
179static void neg_lru_touch(struct val_neg_cache* neg, 
struct val_neg_data* data)
181{
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);
188}

190/**
* 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.
*/
197static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z)
198{
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;
}
224}

226void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el)
227{
struct val_neg_zone* z;
struct val_neg_data* p, *np;
if(!el9.1
'el' is non-null
) return;
10
←
Taking false branch→
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);
log_assert(neg->first != el && neg->last != el);

/* go up the tree and reduce counts */
p = el;
while(p) {
11
←
Loop condition is true.  Entering loop body→
12
←
Loop condition is false. Execution continues on line 249→
log_assert(p->count > 0);
p->count --;
p = p->parent;
}

/* delete 0 count items from tree */
p = el;
while(p12.1
'p' is non-null
1
'p' is null
 && p->count == 0) {
13
←
Assuming field 'count' is equal to 0→
14
←
Loop condition is true.  Entering loop body→
np = p->parent;
(void)rbtree_delete(&z->tree, &p->node);
neg->use -= p->len + sizeof(*p);
free(p->name);
free(p);
15
←
Memory is released→
p = np;
}

/* check if the zone is now unused */
if(z->tree.count == 0) {
16
←
Assuming field 'count' is not equal to 0→
17
←
Taking false branch→
neg_delete_zone(neg, z);
}
263}

265/**
* 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.
*/
272static void neg_make_space(struct val_neg_cache* neg, size_t need)
273{
/* delete elements until enough space or its empty */
while(neg->last18.1
Field 'last' is non-null
 && neg->max < neg->use + need) {
6
←
Assuming field 'last' is non-null→
7
←
Assuming the condition is true→
8
←
Loop condition is true.  Entering loop body→
19
←
Assuming the condition is true→
20
←
Loop condition is true.  Entering loop body→
neg_delete_data(neg, neg->last);
9
←
Calling 'neg_delete_data'→
18
←
Returning; memory was released via 2nd parameter→
21
←
Use of memory after it is freed
}
278}

280struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 
uint8_t* nm, size_t len, uint16_t dclass)
282{
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;
294}

296/**
* 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.
*/
304static struct val_neg_data* neg_find_data(struct val_neg_zone* zone, 
uint8_t* nm, size_t len, int labs)
306{
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;
317}

319/**
* Calculate space needed for the data and all its parents
* @param rep: NSEC entries.
* @return size.
*/
324static size_t calc_data_need(struct reply_info* rep)
325{
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)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(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;
342}

344/**
* Calculate space needed for zone and all its parents
* @param d: name of zone
* @param len: length of name
* @return size.
*/
350static size_t calc_zone_need(uint8_t* d, size_t len)
351{
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;
359}

361/**
* 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.
*/
370static 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)
372{
struct val_neg_zone key;
struct val_neg_zone* result;
rbnode_type* res = NULL((void*)0);
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((void*)0);
/* 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;
400}

402/**
* 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.
*/
410static struct val_neg_data* neg_closest_data_parent(
struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs)
412{
struct val_neg_data key;
struct val_neg_data* result;
rbnode_type* res = NULL((void*)0);
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((void*)0);
/* 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;
439}

441/**
* 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
*/
449static struct val_neg_zone* neg_setup_zone_node(
uint8_t* nm, size_t nm_len, int labs, uint16_t dclass)
451{
struct val_neg_zone* zone = 
(struct val_neg_zone*)calloc(1, sizeof(*zone));
if(!zone) {
return NULL((void*)0);
}
zone->node.key = zone;
zone->name = memdup(nm, nm_len);
if(!zone->name) {
free(zone);
return NULL((void*)0);
}
zone->len = nm_len;
zone->labs = labs;
zone->dclass = dclass;

rbtree_init(&zone->tree, &val_neg_data_compare);
return zone;
469}

471/**
* 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
*/
482static struct val_neg_zone* neg_zone_chain(
uint8_t* nm, size_t nm_len, int labs, uint16_t dclass,
struct val_neg_zone* parent)
485{
int i;
int tolabs = parent?parent->labs:0;
struct val_neg_zone* zone, *prev = NULL((void*)0), *first = NULL((void*)0);

/* 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->name);
		free(p);
		p = np;
	}
	return NULL((void*)0);
}
if(i == labs) {
	first = zone;
} else {
	prev->parent = zone;
}
/* prepare for next name */
prev = zone;
dname_remove_label(&nm, &nm_len);
}
return first;
516}	

518void val_neg_zone_take_inuse(struct val_neg_zone* zone)
519{
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++;
}
}
528}

530struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
uint8_t* nm, size_t nm_len, uint16_t dclass)
532{
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((void*)0);
}

/* 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((void*)0))
	p->parent = parent;
p = np;
}
return zone;
563}

565/** find zone name of message, returns the SOA record */
566static struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep)
567{
size_t i;
for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
if(ntohs(rep->rrsets[i]->rk.type)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(rep->rrsets
[i]->rk.type)) == LDNS_RR_TYPE_SOA)
	return rep->rrsets[i];
}
return NULL((void*)0);
574}

576/** see if the reply has NSEC records worthy of caching */
577static int reply_has_nsec(struct reply_info* rep)
578{
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)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(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;
592}


595/**
* 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.
*/
602static struct val_neg_data* neg_setup_data_node(
uint8_t* nm, size_t nm_len, int labs)
604{
struct val_neg_data* el;
el = (struct val_neg_data*)calloc(1, sizeof(*el));
if(!el) {
return NULL((void*)0);
}
el->node.key = el;
el->name = memdup(nm, nm_len);
if(!el->name) {
free(el);
return NULL((void*)0);
}
el->len = nm_len;
el->labs = labs;
return el;
619}

621/**
* 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.
*/
629static struct val_neg_data* neg_data_chain(
uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent)
631{
int i;
int tolabs = parent?parent->labs:0;
struct val_neg_data* el, *first = NULL((void*)0), *prev = NULL((void*)0);

/* 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->name);
		free(p);
		p = np;
	}
	return NULL((void*)0);
}
if(i == labs) {
	first = el;
} else {
	prev->parent = el;
}

/* prepare for next name */
prev = el;
dname_remove_label(&nm, &nm_len);
}
return first;
663}

665/**
* 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
*/
673static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone, 
struct val_neg_data* el, struct ub_packed_rrset_key* nsec)
675{
struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
entry.data;
uint8_t* end;
size_t end_len;
int end_labs, m;
rbnode_type* 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)(__uint16_t)(__builtin_constant_p(nsec->rk.type) ? (__uint16_t
)(((__uint16_t)(nsec->rk.type) & 0xffU) << 8 | (
(__uint16_t)(nsec->rk.type) & 0xff00U) >> 8) : __swap16md
(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((void*)0);
}

walk = rbtree_next(&el->node);
while(walk && walk != RBTREE_NULL&rbtree_null_node) {
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;
}
746}

748void neg_insert_data(struct val_neg_cache* neg, 
struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec)
750{
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)(__uint16_t)(__builtin_constant_p(nsec->rk.type) ? (__uint16_t
)(((__uint16_t)(nsec->rk.type) & 0xffU) << 8 | (
(__uint16_t)(nsec->rk.type) & 0xff00U) >> 8) : __swap16md
(nsec->rk.type)), 
ntohs(nsec->rk.rrset_class)(__uint16_t)(__builtin_constant_p(nsec->rk.rrset_class) ? (
__uint16_t)(((__uint16_t)(nsec->rk.rrset_class) & 0xffU
) << 8 | ((__uint16_t)(nsec->rk.rrset_class) & 0xff00U
) >> 8) : __swap16md(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((void*)0))
		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)(__uint16_t)(__builtin_constant_p(nsec->rk.type) ? (__uint16_t
)(((__uint16_t)(nsec->rk.type) & 0xffU) << 8 | (
(__uint16_t)(nsec->rk.type) & 0xff00U) >> 8) : __swap16md
(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)) {

	if(slen > 0) {
		uint8_t* sa = memdup(s, slen);
		if(sa) {
			free(zone->nsec3_salt);
			zone->nsec3_salt = sa;
			zone->nsec3_saltlen = slen;
			zone->nsec3_iter = it;
			zone->nsec3_hash = h;
		}
	} else {
		free(zone->nsec3_salt);
		zone->nsec3_salt = NULL((void*)0);
		zone->nsec3_saltlen = 0;
		zone->nsec3_iter = it;
		zone->nsec3_hash = h;
	}
}
}

/* wipe out the cache items between NSEC start and end */
wipeout(neg, zone, el, nsec);
849}

851/** see if the reply has signed NSEC records and return the signer */
852static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len,
uint16_t* dclass)
854{
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)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(rep->rrsets
[i]->rk.type)) == LDNS_RR_TYPE_NSEC ||
	ntohs(rep->rrsets[i]->rk.type)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(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]->(__uint16_t)(__builtin_constant_p(rep->rrsets[i]-> rk.rrset_class
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]-> rk.rrset_class
) & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
 rk.rrset_class) & 0xff00U) >> 8) : __swap16md(rep->
rrsets[i]-> rk.rrset_class))
				rk.rrset_class)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]-> rk.rrset_class
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]-> rk.rrset_class
) & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
 rk.rrset_class) & 0xff00U) >> 8) : __swap16md(rep->
rrsets[i]-> rk.rrset_class));
			return s;
		}
	}
}
}
return 0;
876}

878void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep)
879{
size_t i, need;
struct ub_packed_rrset_key* soa;
uint8_t* dname = NULL((void*)0);
size_t dname_len;
uint16_t rrset_class;
struct val_neg_zone* zone;
/* see if secure nsecs inside */
if(!reply_has_nsec(rep))
return;
/* find the zone name in message */
if((soa = reply_find_soa(rep))) {
dname = soa->rk.dname;
dname_len = soa->rk.dname_len;
rrset_class = ntohs(soa->rk.rrset_class)(__uint16_t)(__builtin_constant_p(soa->rk.rrset_class) ? (
__uint16_t)(((__uint16_t)(soa->rk.rrset_class) & 0xffU
) << 8 | ((__uint16_t)(soa->rk.rrset_class) & 0xff00U
) >> 8) : __swap16md(soa->rk.rrset_class));
}
else {
/* No SOA in positive (wildcard) answer. Use signer from the 
 * validated answer RRsets' signature. */
if(!(dname = reply_nsec_signer(rep, &dname_len, &rrset_class)))
	return;
}

log_nametypeclass(VERB_ALGO, "negcache insert for zone",
dname, LDNS_RR_TYPE_SOA, rrset_class);

/* ask for enough space to store all of it */
need = calc_data_need(rep) + 
calc_zone_need(dname, dname_len);
lock_basic_lock(&neg->lock);
neg_make_space(neg, need);

/* find or create the zone entry */
zone = neg_find_zone(neg, dname, dname_len, rrset_class);
if(!zone) {
if(!(zone = neg_create_zone(neg, dname, dname_len,
	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)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(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);
937}

939/**
* 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.
*/
948static int neg_closest_data(struct val_neg_zone* zone,
uint8_t* qname, size_t len, int labs, struct val_neg_data** data)
950{
struct val_neg_data key;
rbnode_type* 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;
}
966}

968void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
uint8_t* zone_name)
970{
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) 
1
Assuming 'signer' is non-null→
2
←
Taking false branch→
return;
if(!dname_subdomain_c(signer, zone_name)) {
3
←
Assuming the condition is false→
4
←
Taking false branch→
/* 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);
5
←
Calling 'neg_make_space'→

/* 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)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(rep->rrsets
[i]->rk.type)) != LDNS_RR_TYPE_NSEC &&
	ntohs(rep->rrsets[i]->rk.type)(__uint16_t)(__builtin_constant_p(rep->rrsets[i]->rk.type
) ? (__uint16_t)(((__uint16_t)(rep->rrsets[i]->rk.type)
 & 0xffU) << 8 | ((__uint16_t)(rep->rrsets[i]->
rk.type) & 0xff00U) >> 8) : __swap16md(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);
1021}

1023/**
* 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.
*/
1032static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t)
1033{
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;
1040}

1042/**
* 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
*/
1058static struct ub_packed_rrset_key*
1059grab_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, 
time_t now)
1063{
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((void*)0);
d = (struct packed_rrset_data*)k->entry.data;
if(d->ttl < now) {
lock_rw_unlock(&k->entry.lock);
return NULL((void*)0);
}
/* 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((void*)0);
}
/* 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((void*)0);
}
/* 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;
1093}

1095/**
* Get best NSEC record for qname. Might be matching, covering or totally
* useless.
* @param neg_cache: neg cache
* @param qname: to lookup rrset name
* @param qname_len: length of qname.
* @param qclass: class of rrset to lookup, host order
* @param rrset_cache: rrset cache
* @param now: to check ttl against
* @param region: where to alloc result
* @return rrset or NULL
*/
1107static struct ub_packed_rrset_key*
1108neg_find_nsec(struct val_neg_cache* neg_cache, uint8_t* qname, size_t qname_len,
uint16_t qclass, struct rrset_cache* rrset_cache, time_t now,
struct regional* region)
1111{
int labs;
uint32_t flags;
struct val_neg_zone* zone;
struct val_neg_data* data;
struct ub_packed_rrset_key* nsec;

labs = dname_count_labels(qname);
lock_basic_lock(&neg_cache->lock);
zone = neg_closest_zone_parent(neg_cache, qname, qname_len, labs,
qclass);
while(zone && !zone->in_use)
zone = zone->parent;
if(!zone) {
lock_basic_unlock(&neg_cache->lock);
return NULL((void*)0);
}

/* NSEC only for now */
if(zone->nsec3_hash) {
lock_basic_unlock(&neg_cache->lock);
return NULL((void*)0);
}

/* ignore return value, don't care if it is an exact or smaller match */
(void)neg_closest_data(zone, qname, qname_len, labs, &data);
if(!data) {
lock_basic_unlock(&neg_cache->lock);
return NULL((void*)0);
}

/* ENT nodes are not in use, try the previous node. If the previous node
* is not in use, we don't have an useful NSEC and give up. */
if(!data->in_use) {
data = (struct val_neg_data*)rbtree_previous((rbnode_type*)data);
if((rbnode_type*)data == RBTREE_NULL&rbtree_null_node || !data->in_use) {
	lock_basic_unlock(&neg_cache->lock);
	return NULL((void*)0);
}
}

flags = 0;
if(query_dname_compare(data->name, zone->name) == 0)
flags = PACKED_RRSET_NSEC_AT_APEX0x1;

nsec = grab_nsec(rrset_cache, data->name, data->len, LDNS_RR_TYPE_NSEC,
zone->dclass, flags, region, 0, 0, now);
lock_basic_unlock(&neg_cache->lock);
return nsec;
1160}

1162/** find nsec3 closest encloser in neg cache */
1163static struct val_neg_data*
1164neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
int qlabs, sldns_buffer* buf, uint8_t* hashnc, size_t* nclen)
1166{
struct val_neg_data* data;
uint8_t hashce[NSEC3_SHA_LEN20];
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((void*)0);
if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name,
	zone->len, b32, sizeof(b32))))
	return NULL((void*)0);

/* 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((void*)0);
1196}

1198/** check nsec3 parameters on nsec3 rrset with current zone values */
1199static int
1200neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset)
1201{
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);
1210}

1212/** get next closer for nsec3 proof */
1213static struct ub_packed_rrset_key*
1214neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen,
struct rrset_cache* rrset_cache, struct regional* region, 
time_t now, uint8_t* b32, size_t maxb32)
1217{
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*)0);
(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((void*)0);
/* 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((void*)0);
if(!neg_params_ok(zone, nc_rrset))
return NULL((void*)0);
return nc_rrset;
1243}

1245/** neg cache nsec3 proof procedure*/
1246static struct dns_msg*
1247neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len,
int qlabs, sldns_buffer* buf, struct rrset_cache* rrset_cache,
struct regional* region, time_t now, uint8_t* topname)
1250{
struct dns_msg* msg;
struct val_neg_data* data;
uint8_t hashnc[NSEC3_SHA_LEN20];
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((void*)0); /* not nsec3 zone */

if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf,
hashnc, &nclen))) {
return NULL((void*)0);
}

/* 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((void*)0);
if(!neg_params_ok(zone, ce_rrset))
return NULL((void*)0);

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((void*)0);
if(!(msg = dns_msg_create(qname, qname_len, 
	LDNS_RR_TYPE_DS, zone->dclass, region, 1))) 
	return NULL((void*)0);
/* TTL reduced in grab_nsec */
if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 
	return NULL((void*)0);
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((void*)0);

/* 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((void*)0);
if(!neg_params_ok(zone, nc_rrset))
return NULL((void*)0);
if(!nsec3_has_optout(nc_rrset, 0))
return NULL((void*)0);
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((void*)0);
/* now=0 because TTL was reduced in grab_nsec */
if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 
	return NULL((void*)0);
if(!dns_msg_authadd(msg, region, nc_rrset, 0)) 
	return NULL((void*)0);
return msg;
}
return NULL((void*)0);
1336}

1338/**
* 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.
*/
1347static int add_soa(struct rrset_cache* rrset_cache, time_t now,
struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone)
1349{
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_NEG0x4, 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;
1374}

1376struct dns_msg* 
1377val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo, 
struct regional* region, struct rrset_cache* rrset_cache, 
sldns_buffer* buf, time_t now, int addsoa, uint8_t* topname,
struct config_file* cfg)
1381{
struct dns_msg* msg;
struct ub_packed_rrset_key* nsec; /* qname matching/covering nsec */
struct ub_packed_rrset_key* wcrr; /* wildcard record or nsec */
uint8_t* nodata_wc = NULL((void*)0);
uint8_t* ce = NULL((void*)0);
size_t ce_len;
uint8_t wc_ce[LDNS_MAX_DOMAINLEN255+3];
struct query_info wc_qinfo;
struct ub_packed_rrset_key* cache_wc;
struct packed_rrset_data* wcrr_data;
int rcode = LDNS_RCODE_NOERROR;
uint8_t* zname;
size_t zname_len;
int zname_labs;
struct val_neg_zone* zone;

/* only for DS queries when aggressive use of NSEC is disabled */
if(qinfo->qtype != LDNS_RR_TYPE_DS && !cfg->aggressive_nsec)
return NULL((void*)0);
log_assert(!topname || dname_subdomain_c(qinfo->qname, topname));

/* Get best available NSEC for qname */
nsec = neg_find_nsec(neg, qinfo->qname, qinfo->qname_len, qinfo->qclass,
rrset_cache, now, region);

/* Matching NSEC, use to generate No Data answer. Not creating answers
* yet for No Data proven using wildcard. */
if(nsec && nsec_proves_nodata(nsec, qinfo, &nodata_wc) && !nodata_wc) {
if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 
	qinfo->qtype, qinfo->qclass, region, 2))) 
	return NULL((void*)0);
if(!dns_msg_authadd(msg, region, nsec, 0)) 
	return NULL((void*)0);
if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL((void*)0)))
	return NULL((void*)0);

lock_basic_lock(&neg->lock);
neg->num_neg_cache_noerror++;
lock_basic_unlock(&neg->lock);
return msg;
} else if(nsec && val_nsec_proves_name_error(nsec, qinfo->qname)) {
if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 
	qinfo->qtype, qinfo->qclass, region, 3))) 
	return NULL((void*)0);
if(!(ce = nsec_closest_encloser(qinfo->qname, nsec)))
	return NULL((void*)0);
dname_count_size_labels(ce, &ce_len);

/* No extra extra NSEC required if both nameerror qname and
 * nodata *.ce. are proven already. */
if(!nodata_wc || query_dname_compare(nodata_wc, ce) != 0) {
	/* Qname proven non existing, get wildcard record for
	 * QTYPE or NSEC covering or matching wildcard. */

	/* Num labels in ce is always smaller than in qname,
	 * therefore adding the wildcard label cannot overflow
	 * buffer. */
	wc_ce[0] = 1;
	wc_ce[1] = (uint8_t)'*';
	memmove(wc_ce+2, ce, ce_len);
	wc_qinfo.qname = wc_ce;
	wc_qinfo.qname_len = ce_len + 2;
	wc_qinfo.qtype = qinfo->qtype;


	if((cache_wc = rrset_cache_lookup(rrset_cache, wc_qinfo.qname,
		wc_qinfo.qname_len, wc_qinfo.qtype,
		qinfo->qclass, 0/*flags*/, now, 0/*read only*/))) {
		/* Synthesize wildcard answer */
		wcrr_data = (struct packed_rrset_data*)cache_wc->entry.data;
		if(!(wcrr_data->security == sec_status_secure ||
			(wcrr_data->security == sec_status_unchecked &&
			wcrr_data->rrsig_count > 0))) {
			lock_rw_unlock(&cache_wc->entry.lock);
			return NULL((void*)0);
		}
		if(!(wcrr = packed_rrset_copy_region(cache_wc,
			region, now))) {
			lock_rw_unlock(&cache_wc->entry.lock);
			return NULL((void*)0);
		};
		lock_rw_unlock(&cache_wc->entry.lock);
		wcrr->rk.dname = qinfo->qname;
		wcrr->rk.dname_len = qinfo->qname_len;
		if(!dns_msg_ansadd(msg, region, wcrr, 0))
			return NULL((void*)0);
		/* No SOA needed for wildcard synthesised
		 * answer. */
		addsoa = 0;
	} else {
		/* Get wildcard NSEC for possible non existence
		 * proof */
		if(!(wcrr = neg_find_nsec(neg, wc_qinfo.qname,
			wc_qinfo.qname_len, qinfo->qclass,
			rrset_cache, now, region)))
			return NULL((void*)0);

		nodata_wc = NULL((void*)0);
		if(val_nsec_proves_name_error(wcrr, wc_ce))
			rcode = LDNS_RCODE_NXDOMAIN;
		else if(!nsec_proves_nodata(wcrr, &wc_qinfo,
			&nodata_wc) || nodata_wc)
			/* &nodata_wc shouldn't be set, wc_qinfo
			 * already contains wildcard domain. */
			/* NSEC doesn't prove anything for
			 * wildcard. */
			return NULL((void*)0);
		if(query_dname_compare(wcrr->rk.dname,
			nsec->rk.dname) != 0)
			if(!dns_msg_authadd(msg, region, wcrr, 0))
				return NULL((void*)0);
	}
}

if(!dns_msg_authadd(msg, region, nsec, 0))
	return NULL((void*)0);
if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL((void*)0)))
	return NULL((void*)0);

/* Increment statistic counters */
lock_basic_lock(&neg->lock);
if(rcode == LDNS_RCODE_NOERROR)
	neg->num_neg_cache_noerror++;
else if(rcode == LDNS_RCODE_NXDOMAIN)
	neg->num_neg_cache_nxdomain++;
lock_basic_unlock(&neg->lock);

FLAGS_SET_RCODE(msg->rep->flags, rcode)(msg->rep->flags = (((msg->rep->flags) & 0xfff0
) | (rcode)));
return msg;
}

/* No aggressive use of NSEC3 for now, only proceed for DS types. */
if(qinfo->qtype != LDNS_RR_TYPE_DS){
return NULL((void*)0);
}
/* 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((void*)0);
}
if(!zone) {
lock_basic_unlock(&neg->lock);
return NULL((void*)0);
}

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((void*)0);
}
lock_basic_unlock(&neg->lock);
return msg;
1549}