<commit_before>/**
 *
 * /brief function for DNSSEC
 *
 * The priv_getdns_get_validation_chain function is called after an answer
 * has been fetched when the dnssec_return_validation_chain extension is set.
 * It fetches DNSKEYs, DSes and their signatures for all RRSIGs found in the
 * answer.
 */

/*
 * Copyright (c) 2013, NLnet Labs, Verisign, Inc.
 * All rights reserved.
 *
 * 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 names of the copyright holders 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 Verisign, Inc. 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.
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <unbound.h>
#include <ldns/ldns.h>
#include "getdns/getdns.h"
#include "config.h"
#include "context.h"
#include "util-internal.h"
#include "types-internal.h"
#include "dnssec.h"
#include "rr-dict.h"
#include "gldns/str2wire.h"
#include "gldns/wire2str.h"
#include "general.h"
#include "dict.h"

#if defined(SEC_DEBUG) && SEC_DEBUG
inline static void debug_sec_print_rr(const char *msg, priv_getdns_rr_iter *rr)
{
	char str_spc[8192], *str = str_spc;
	size_t str_len = sizeof(str_spc);
	uint8_t *data = rr->pos;
	size_t data_len = rr->nxt - rr->pos;

	if (!rr || !rr->pos) {
		DEBUG_SEC("%s<nil>\n", msg);
		return;
	}
	(void) gldns_wire2str_rr_scan(
	    &data, &data_len, &str, &str_len, rr->pkt, rr->pkt_end - rr->pkt);
	DEBUG_SEC("%s%s", msg, str_spc);
}
inline static void debug_sec_print_dname(const char *msg, uint8_t *label)
{
	char str[1024];

	if (gldns_wire2str_dname_buf(label, 256, str, sizeof(str)))
		DEBUG_SEC("%s%s\n", msg, str);
	else
		DEBUG_SEC("%s<nil>\n", msg);
}
#else
#define debug_sec_print_rr(...) DEBUG_OFF(__VA_ARGS__)
#define debug_sec_print_dname(...) DEBUG_OFF(__VA_ARGS__)
#endif


static inline uint16_t rr_iter_type(priv_getdns_rr_iter *rr)
{ return rr->rr_type + 2 <= rr->nxt ? gldns_read_uint16(rr->rr_type) : 0; }
static inline uint16_t rr_iter_class(priv_getdns_rr_iter *rr)
{ return rr->rr_type + 4 <= rr->nxt ? gldns_read_uint16(rr->rr_type + 2) : 0; }

static priv_getdns_rr_iter *rr_iter_ansauth(priv_getdns_rr_iter *rr)
{
	while (rr && rr->pos && !(
	    priv_getdns_rr_iter_section(rr) == GLDNS_SECTION_ANSWER ||
	    priv_getdns_rr_iter_section(rr) == GLDNS_SECTION_AUTHORITY))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

static int rr_owner_equal(priv_getdns_rr_iter *rr, uint8_t *name)
{
	uint8_t owner_spc[256], *owner;
	size_t  owner_len = sizeof(owner_spc);

	return (owner = priv_getdns_owner_if_or_as_decompressed(rr,  owner_spc
	                                                          , &owner_len))
	    && priv_getdns_dname_equal(owner, name);
}

static priv_getdns_rr_iter *rr_iter_name_class_type(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && !(
	    rr_iter_type(rr)  == rr_type  &&
	    rr_iter_class(rr) == rr_class &&
	    rr_owner_equal(rr, name)))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

static priv_getdns_rr_iter *rr_iter_not_name_class_type(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && (
	    rr_iter_type(rr)  == GETDNS_RRTYPE_RRSIG || (
	    rr_iter_type(rr)  == rr_type  &&
	    rr_iter_class(rr) == rr_class &&
	    rr_owner_equal(rr, name))))

		rr = priv_getdns_rr_iter_next(rr);
	
	return rr && rr->pos ? rr : NULL;
}

static priv_getdns_rr_iter *rr_iter_rrsig_covering(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && !(
	    rr_iter_type(rr)  == GETDNS_RRTYPE_RRSIG &&
	    rr_iter_class(rr) == rr_class &&
	    rr->rr_type + 12 <= rr->nxt &&
	    gldns_read_uint16(rr->rr_type + 10) == rr_type && 
	    rr_owner_equal(rr, name)))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

typedef struct getdns_rrset {
	uint8_t            *name;
	uint16_t            rr_class;
	uint16_t            rr_type;
	getdns_network_req *netreq;
	uint8_t             name_spc[];
} getdns_rrset;

typedef struct rrtype_iter {
	priv_getdns_rr_iter  rr_i;
	getdns_rrset        *rrset;
} rrtype_iter;

typedef struct rrsig_iter {
	priv_getdns_rr_iter  rr_i;
	getdns_rrset        *rrset;
} rrsig_iter;

static rrtype_iter *rrtype_iter_next(rrtype_iter *i)
{
	return (rrtype_iter *) rr_iter_name_class_type(
	    priv_getdns_rr_iter_next(&i->rr_i),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrtype_iter *rrtype_iter_init(rrtype_iter *i, getdns_rrset *rrset)
{
	i->rrset = rrset;
	return (rrtype_iter *) rr_iter_name_class_type(
	    priv_getdns_rr_iter_init(&i->rr_i, rrset->netreq->response
	                                     , rrset->netreq->response_len),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrsig_iter *rrsig_iter_next(rrsig_iter *i)
{
	return (rrsig_iter *) rr_iter_rrsig_covering(
	    priv_getdns_rr_iter_next(&i->rr_i),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrsig_iter *rrsig_iter_init(rrsig_iter *i, getdns_rrset *rrset)
{
	i->rrset = rrset;
	return (rrsig_iter *) rr_iter_rrsig_covering(
	    priv_getdns_rr_iter_init(&i->rr_i, rrset->netreq->response
	                                     , rrset->netreq->response_len),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

inline static int rrset_has_rrsigs(getdns_rrset *rrset)
{
	rrsig_iter rrsig;
	return rrsig_iter_init(&rrsig, rrset) != NULL;
}

#if defined(SEC_DEBUG) && SEC_DEBUG
static void debug_sec_print_rrset(const char *msg, getdns_rrset *rrset)
{
	char owner[1024];
	char buf_space[2048];
	gldns_buffer buf;
	rrtype_iter *rr, rr_space;
	rrsig_iter  *rrsig, rrsig_space;
	size_t i;

	if (!rrset) {
		DEBUG_SEC("<nil>");
		return;
	}
	gldns_buffer_init_frm_data(&buf, buf_space, sizeof(buf_space));
	if (gldns_wire2str_dname_buf(rrset->name, 256, owner, sizeof(owner)))
		gldns_buffer_printf(&buf, "%s ", owner);
	else	gldns_buffer_printf(&buf, "<nil> ");

	switch (rrset->rr_class) {
	case GETDNS_RRCLASS_IN	: gldns_buffer_printf(&buf, "IN ")  ; break;
	case GETDNS_RRCLASS_CH	: gldns_buffer_printf(&buf, "CH ")  ; break;
	case GETDNS_RRCLASS_HS	: gldns_buffer_printf(&buf, "HS ")  ; break;
	case GETDNS_RRCLASS_NONE: gldns_buffer_printf(&buf, "NONE "); break;
	case GETDNS_RRCLASS_ANY	: gldns_buffer_printf(&buf, "ANY ") ; break;
	default			: gldns_buffer_printf(&buf, "CLASS%d "
						          , rrset->rr_class);
				  break;
	}
	gldns_buffer_printf(&buf, "%s", priv_getdns_rr_type_name(rrset->rr_type));

	gldns_buffer_printf(&buf, ", rrs:");
	for ( rr = rrtype_iter_init(&rr_space, rrset), i = 1
	    ; rr
	    ; rr = rrtype_iter_next(rr), i++)
		gldns_buffer_printf(&buf, " %d", (int)i);

	gldns_buffer_printf(&buf, ", rrsigs:");
	for ( rrsig = rrsig_iter_init(&rrsig_space, rrset), i = 1
	    ; rrsig
	    ; rrsig = rrsig_iter_next(rrsig), i++)
		gldns_buffer_printf(&buf, " %d", (int)i);

	DEBUG_SEC("%s%s\n", msg, buf_space);
}
#else
#define debug_sec_print_rrset(...) DEBUG_OFF(__VA_ARGS__)
#endif



typedef struct rrset_iter rrset_iter;
struct rrset_iter {
	getdns_rrset        rrset;
	uint8_t             name_spc[256];
	size_t              name_len;
	priv_getdns_rr_iter rr_i;
};

static rrset_iter *rrset_iter_init(rrset_iter *i, getdns_network_req *netreq)
{
	priv_getdns_rr_iter *rr;

	i->rrset.name = i->name_spc;
	i->rrset.netreq = netreq;
	i->name_len = 0;

	for ( rr = priv_getdns_rr_iter_init(&i->rr_i
	                                   , netreq->response
	                                   , netreq->response_len)
	    ;(rr = rr_iter_ansauth(rr))
	    ; rr = priv_getdns_rr_iter_next(rr)) {

		if ((i->rrset.rr_type = rr_iter_type(rr))
		    == GETDNS_RRTYPE_RRSIG)
			continue;

		i->rrset.rr_class = rr_iter_class(rr);

		if (!(i->rrset.name = priv_getdns_owner_if_or_as_decompressed(
		    rr, i->name_spc, &i->name_len)))
			continue;

		return i;
	}
	return NULL;
}


static rrset_iter *rrset_iter_next(rrset_iter *i)
{
	priv_getdns_rr_iter *rr;

	if (!(rr = i && i->rr_i.pos ? &i->rr_i : NULL))
		return NULL;

	if (!(rr = rr_iter_not_name_class_type(rr,
	    i->rrset.name, i->rrset.rr_class, i->rrset.rr_type)))
		return NULL;

	i->rrset.rr_type  = rr_iter_type(rr);
	i->rrset.rr_class = rr_iter_class(rr);
	if (!(i->rrset.name = priv_getdns_owner_if_or_as_decompressed(
		    rr, i->name_spc, &i->name_len)))
		return rrset_iter_next(i);

	return i;
}

static getdns_rrset *rrset_iter_value(rrset_iter *i)
{
	if (!i)
		return NULL;
	if (!i->rr_i.pos)
		return NULL;
	return &i->rrset;
}

typedef struct chain_head chain_head;
typedef struct chain_node chain_node;

struct chain_head {
	struct mem_funcs  my_mf;

	chain_head       *next;
	chain_node       *parent;
	size_t            node_count; /* Number of nodes attached directly
	                               * to this head.  For cleaning.  */
	getdns_rrset      rrset;
	uint8_t           name_spc[];
};

struct chain_node {
	chain_node  *parent;
	
	getdns_rrset dnskey;
	getdns_rrset ds    ;
	getdns_rrset soa   ;

	chain_head  *chains;
};

static size_t count_outstanding_requests(chain_head *head)
{
	size_t count;
	chain_node *node;

	if (!head)
		return 0;

	for ( node = head->parent, count = 0
	    ; node
	    ; node = node->parent) {

		if (node->dnskey.netreq &&
		    node->dnskey.netreq->state != NET_REQ_FINISHED &&
		    node->dnskey.netreq->state != NET_REQ_CANCELED)
			count++;

		if (node->ds.netreq &&
		    node->ds.netreq->state != NET_REQ_FINISHED &&
		    node->ds.netreq->state != NET_REQ_CANCELED)
			count++;

		if (node->soa.netreq &&
		    node->soa.netreq->state != NET_REQ_FINISHED &&
		    node->soa.netreq->state != NET_REQ_CANCELED)
			count++;
	}
	return count + count_outstanding_requests(head->next);
}

static void append_rrs2val_chain_list(getdns_context *ctxt,
    getdns_list *val_chain_list, getdns_network_req *netreq)
{
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrtype_iter *rr, rr_spc;
	rrsig_iter  *rrsig, rrsig_spc;
	getdns_dict *rr_dict;

	for (i = rrset_iter_init(&i_spc, netreq); i; i = rrset_iter_next(i)) {
		rrset = rrset_iter_value(i);

		if (rrset->rr_type != GETDNS_RRTYPE_DNSKEY &&
		    rrset->rr_type != GETDNS_RRTYPE_DS     &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC   &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC3)
			continue;

		for ( rr = rrtype_iter_init(&rr_spc, rrset)
		    ; rr; rr = rrtype_iter_next(rr)) {

			rr_dict = priv_getdns_rr_iter2rr_dict(ctxt, &rr->rr_i);
			if (!rr_dict) continue;

			(void)getdns_list_append_dict(val_chain_list, rr_dict);
			getdns_dict_destroy(rr_dict);
		}
		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset)
		    ; rrsig; rrsig = rrsig_iter_next(rrsig)) {

			rr_dict=priv_getdns_rr_iter2rr_dict(ctxt,&rrsig->rr_i);
			if (!rr_dict) continue;

			(void)getdns_list_append_dict(val_chain_list, rr_dict);
			getdns_dict_destroy(rr_dict);
		}
	}
}

static void check_chain_complete(chain_head *chain)
{
	getdns_dns_req *dnsreq;
	size_t o, node_count;
	chain_head *head, *next;
	chain_node *node;
	getdns_list *val_chain_list;
	getdns_dict *response_dict;

	if ((o = count_outstanding_requests(chain)) > 0) {
		DEBUG_SEC("%zu outstanding requests\n", o);
		return;
	}
	DEBUG_SEC("Chain done!\n");
	dnsreq = chain->rrset.netreq->owner;
	/* TODO: DNSSEC validation of netreq! */

	val_chain_list = dnsreq->dnssec_return_validation_chain
		? getdns_list_create_with_context(dnsreq->context) : NULL;

	/* Cleanup the chain */
	for ( head = chain; head ; head = next ) {
		next = head->next;
		for ( node_count = head->node_count, node = head->parent
		    ; node_count
		    ; node_count--, node = node->parent ) {

			if (node->dnskey.netreq) {
				append_rrs2val_chain_list(dnsreq->context,
				    val_chain_list, node->dnskey.netreq);
				dns_req_free(node->dnskey.netreq->owner);
			}
			if (node->ds.netreq) {
				append_rrs2val_chain_list(dnsreq->context,
				    val_chain_list, node->ds.netreq);
				dns_req_free(node->ds.netreq->owner);
			}
		}
		GETDNS_FREE(head->my_mf, head);
	}

	response_dict = create_getdns_response(dnsreq);
	if (val_chain_list) {
		(void) getdns_dict_set_list(
		    response_dict, "validation_chain", val_chain_list);
		getdns_list_destroy(val_chain_list);
	}
	/* Final user callback */
	priv_getdns_call_user_callback(dnsreq, response_dict);
}

static void val_chain_node_soa_cb(getdns_dns_req *dnsreq);
static void val_chain_sched_soa_node(chain_node *node)
{
	getdns_context *context;
	getdns_eventloop *loop;
	getdns_dns_req *dnsreq;
	char  name[1024];

	context = node->chains->rrset.netreq->owner->context;
	loop    = node->chains->rrset.netreq->owner->loop;

	if (!gldns_wire2str_dname_buf(node->soa.name, 256, name, sizeof(name)))
		return;

	if (! node->soa.netreq &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_SOA,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL,
	    val_chain_node_soa_cb))

		node->soa.netreq = *dnsreq->netreqs;
}

static void val_chain_sched_soa(chain_head *head, uint8_t *dname)
{
	chain_node *node;

	if (!*dname)
		return;

	for ( node = head->parent
	    ; node && !priv_getdns_dname_equal(dname, node->dnskey.name)
	    ; node = node->parent);

	if (node)
		val_chain_sched_soa_node(node);
}

static void val_chain_node_cb(getdns_dns_req *dnsreq);
static void val_chain_sched_node(chain_node *node)
{
	getdns_context *context;
	getdns_eventloop *loop;
	getdns_dns_req *dnsreq;
	char  name[1024];

	context = node->chains->rrset.netreq->owner->context;
	loop    = node->chains->rrset.netreq->owner->loop;

	if (!gldns_wire2str_dname_buf(node->dnskey.name, 256, name, sizeof(name)))
		return;

	DEBUG_SEC("schedule DS & DNSKEY lookup for %s\n", name);

	if (! node->dnskey.netreq /* not scheduled */ &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_DNSKEY,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL, val_chain_node_cb))

		node->dnskey.netreq = *dnsreq->netreqs;

	if (! node->ds.netreq && node->parent /* not root */ &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_DS,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL, val_chain_node_cb))

		node->ds.netreq = *dnsreq->netreqs;
}

static void val_chain_sched(chain_head *head, uint8_t *dname)
{
	chain_node *node;

	for ( node = head->parent
	    ; node && !priv_getdns_dname_equal(dname, node->dnskey.name)
	    ; node = node->parent);
	if (node)
		val_chain_sched_node(node);
}

static void val_chain_sched_signer_node(chain_node *node, rrsig_iter *rrsig)
{
	priv_getdns_rdf_iter rdf_spc, *rdf;
	uint8_t signer_spc[256], *signer;
	size_t signer_len;
	
	if (!(rdf = priv_getdns_rdf_iter_init_at(&rdf_spc, &rrsig->rr_i, 7)))
		return;

	if (!(signer = priv_getdns_rdf_if_or_as_decompressed(
	    rdf, signer_spc, &signer_len)))
		return;

	while (node && !priv_getdns_dname_equal(signer, node->dnskey.name))
		node = node->parent;
	if (node)
		val_chain_sched_node(node);
}

static void val_chain_sched_signer(chain_head *head, rrsig_iter *rrsig)
{
	val_chain_sched_signer_node(head->parent, rrsig);
}

static void val_chain_node_cb(getdns_dns_req *dnsreq)
{
	chain_node *node = (chain_node *)dnsreq->user_pointer;
	getdns_network_req *netreq = dnsreq->netreqs[0];
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrsig_iter  *rrsig, rrsig_spc;

	getdns_context_clear_outbound_request(dnsreq);
	switch (netreq->request_type) {
	case GETDNS_RRTYPE_DS    : break;
	case GETDNS_RRTYPE_DNSKEY: node->dnskey.netreq = netreq;
	default                  : check_chain_complete(node->chains);
				   return;
	}
	for (i = rrset_iter_init(&i_spc, netreq); i; i = rrset_iter_next(i)) {
		rrset = rrset_iter_value(i);

		if (rrset->rr_type != GETDNS_RRTYPE_DS     &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC   &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC3)
			continue;

		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset)
		    ; rrsig; rrsig = rrsig_iter_next(rrsig))

			val_chain_sched_signer_node(node, rrsig);
	}
	check_chain_complete(node->chains);
}


static getdns_rrset *rrset_by_type(
    rrset_iter *i_spc, getdns_network_req *netreq, uint16_t rr_type)
{
	rrset_iter   *i;
	getdns_rrset *rrset;

	for (i = rrset_iter_init(i_spc, netreq); i; i = rrset_iter_next(i)) {
		rrset = rrset_iter_value(i);
		if (rrset->rr_type == rr_type)
			return rrset;
	}
	return NULL;
}

static void val_chain_node_soa_cb(getdns_dns_req *dnsreq)
{
	chain_node *node = (chain_node *)dnsreq->user_pointer;
	getdns_network_req *netreq = dnsreq->netreqs[0];
	rrset_iter i_spc;
	getdns_rrset *rrset;

	getdns_context_clear_outbound_request(dnsreq);

	if ((rrset = rrset_by_type(&i_spc, netreq, GETDNS_RRTYPE_SOA))) {

		while (node &&
		    ! priv_getdns_dname_equal(node->soa.name, rrset->name))
			node = node->parent;

		val_chain_sched_node(node);
	} else
		val_chain_sched_soa_node(node->parent);

	check_chain_complete(node->chains);
}

static int is_subdomain(
    const uint8_t * const subdomain, const uint8_t *domain)
{
	while (*domain) {
		if (priv_getdns_dname_equal(subdomain, domain))
			return 1;

		domain += *domain + 1;
	}
	return *subdomain == 0;
}

static uint8_t **reverse_labels(uint8_t *dname, uint8_t **labels)
{
	if (*dname)
		labels = reverse_labels(dname + *dname + 1, labels);
	*labels = dname;
	return labels + 1;
}

static chain_head *add_rrset2val_chain(
    struct mem_funcs *mf, chain_head **chain_p, getdns_rrset *rrset)
{
	chain_head *head;
	uint8_t    *labels[128], **last_label, **label;

	size_t      max_labels; /* max labels in common */
	chain_head *max_head;
	chain_node *max_node;

	size_t      dname_len, head_sz, node_count, n;
	uint8_t    *dname, *region;
	chain_node *node;

	last_label = reverse_labels(rrset->name, labels);

	/* Try to find a chain with the most overlapping labels.
	 * max_labels will be the number of labels in common from the root
	 *            (so at least one; the root)
	 * max_head   will be the head of the chain with max # labebs in common
	 */
	max_head = NULL;
	max_labels = 0;
	for (head = *chain_p; head; head = head->next) {
		for (label = labels; label < last_label; label++) {
			if (! is_subdomain(*label, head->rrset.name))
				break;
		}
		if (label - labels > max_labels) {
			max_labels = label - labels;
			max_head = head;
		}
	}
	/* Chain found.  Now set max_node to the point in the chain where nodes
	 *               will be common.
	 */
	if (max_head) {
		for ( node = max_head->parent, n = 0
		    ; node
		    ; node = node->parent, n++);

		for ( n -= max_labels, node = max_head->parent
		    ; n
		    ; n--, node = node->parent);
	} else
		max_node = NULL;

	/* node_count is the amount of nodes to still allocate.
	 * the last one's parent has to hook into the max_node.
	 */
	dname_len = *labels - last_label[-1] + 1;
	head_sz = (sizeof(chain_head) + dname_len + 7) / 8 * 8;
	node_count = last_label - labels - max_labels;
	DEBUG_SEC( "%zu labels in common. %zu labels to allocate\n"
	         , max_labels, node_count);

	if (! (region = GETDNS_XMALLOC(*mf, uint8_t, head_sz + 
	    node_count * sizeof(chain_node))))
		return NULL;
	
	/* Append the head on the linked list of heads */
	for (head = *chain_p; head && head->next; head = head->next);
	if  (head)
		head = head->next = (chain_head *)region;
	else
		head = *chain_p   = (chain_head *)region;

	head->my_mf = *mf;
	head->next = NULL;
	head->rrset.name = head->name_spc;
	memcpy(head->name_spc, rrset->name, dname_len);
	head->rrset.rr_class = rrset->rr_class;
	head->rrset.rr_type = rrset->rr_type;
	head->rrset.netreq = rrset->netreq;
	head->node_count = node_count;

	if (!node_count) {
		head->parent = max_head->parent;
		return head;
	}

	/* Initialize the nodes */
	node = (chain_node *)(region + head_sz);
	head->parent = node;

	for ( node = (chain_node *)(region + head_sz), head->parent = node
	                                             , dname = head->rrset.name
	    ; node_count
	    ; node_count--, node = node->parent =&node[1], dname += *dname + 1) {

		node->chains          = *chain_p;
		node->ds.name         = dname;
		node->dnskey.name     = dname;
		node->soa.name        = dname;
		node->ds.rr_class     = head->rrset.rr_class;
		node->dnskey.rr_class = head->rrset.rr_class;
		node->soa.rr_class    = head->rrset.rr_class;
		node->ds.rr_type      = GETDNS_RRTYPE_DS;
		node->dnskey.rr_type  = GETDNS_RRTYPE_DNSKEY;
		node->soa.rr_type     = GETDNS_RRTYPE_SOA;
		node->ds.netreq       = NULL;
		node->dnskey.netreq   = NULL;
		node->soa.netreq      = NULL;

		node->soa.rr_class = head->rrset.rr_class;
	}
	/* On the first chain, max_node == NULL.
	 * Schedule a root DNSKEY query, we always need that.
	 */
	if (!(node[-1].parent = max_node))
		val_chain_sched(head, (uint8_t *)"\0");

	return head;
}

static void add_netreq2val_chain(
    chain_head **chain_p, getdns_network_req *netreq)
{
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrsig_iter *rrsig, rrsig_spc;
	size_t n_rrsigs;
	chain_head *head;
	struct mem_funcs *mf;
	getdns_rrset empty_rrset;

	assert(netreq->response);
	assert(netreq->response_len >= GLDNS_HEADER_SIZE);

	mf = priv_getdns_context_mf(netreq->owner->context);

	/* On empty packet, find SOA (zonecut) for the qname and query DS */

	/* For all things with signatures, create a chain */

	/* For all things without signature, find SOA (zonecut) and query DS */

	if (GLDNS_ANCOUNT(netreq->response) == 0 &&
	    GLDNS_NSCOUNT(netreq->response) == 0) {

		empty_rrset.name = netreq->query + GLDNS_HEADER_SIZE;
		empty_rrset.rr_class = GETDNS_RRCLASS_IN;
		empty_rrset.rr_type  = 0;
		empty_rrset.netreq   = netreq;

		head = add_rrset2val_chain(mf, chain_p, &empty_rrset);
		val_chain_sched_soa(head, empty_rrset.name);
		return;
	}
	for (i = rrset_iter_init(&i_spc, netreq); i; i = rrset_iter_next(i)) {
		rrset = rrset_iter_value(i);
		debug_sec_print_rrset("rrset: ", rrset);

		head = add_rrset2val_chain(mf, chain_p, rrset);
		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset), n_rrsigs = 0
		    ; rrsig
		    ; rrsig = rrsig_iter_next(rrsig), n_rrsigs++) {
			
			val_chain_sched_signer(head, rrsig);
		}
		if (n_rrsigs)
			continue;
<commit_msg>Generalize getdns_rrset for raw pkt, not netreq<commit_after>/**
 *
 * /brief function for DNSSEC
 *
 * The priv_getdns_get_validation_chain function is called after an answer
 * has been fetched when the dnssec_return_validation_chain extension is set.
 * It fetches DNSKEYs, DSes and their signatures for all RRSIGs found in the
 * answer.
 */

/*
 * Copyright (c) 2013, NLnet Labs, Verisign, Inc.
 * All rights reserved.
 *
 * 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 names of the copyright holders 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 Verisign, Inc. 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.
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <unbound.h>
#include <ldns/ldns.h>
#include "getdns/getdns.h"
#include "config.h"
#include "context.h"
#include "util-internal.h"
#include "types-internal.h"
#include "dnssec.h"
#include "rr-dict.h"
#include "gldns/str2wire.h"
#include "gldns/wire2str.h"
#include "general.h"
#include "dict.h"

#if defined(SEC_DEBUG) && SEC_DEBUG
inline static void debug_sec_print_rr(const char *msg, priv_getdns_rr_iter *rr)
{
	char str_spc[8192], *str = str_spc;
	size_t str_len = sizeof(str_spc);
	uint8_t *data = rr->pos;
	size_t data_len = rr->nxt - rr->pos;

	if (!rr || !rr->pos) {
		DEBUG_SEC("%s<nil>\n", msg);
		return;
	}
	(void) gldns_wire2str_rr_scan(
	    &data, &data_len, &str, &str_len, rr->pkt, rr->pkt_end - rr->pkt);
	DEBUG_SEC("%s%s", msg, str_spc);
}
inline static void debug_sec_print_dname(const char *msg, uint8_t *label)
{
	char str[1024];

	if (gldns_wire2str_dname_buf(label, 256, str, sizeof(str)))
		DEBUG_SEC("%s%s\n", msg, str);
	else
		DEBUG_SEC("%s<nil>\n", msg);
}
#else
#define debug_sec_print_rr(...) DEBUG_OFF(__VA_ARGS__)
#define debug_sec_print_dname(...) DEBUG_OFF(__VA_ARGS__)
#endif


static inline uint16_t rr_iter_type(priv_getdns_rr_iter *rr)
{ return rr->rr_type + 2 <= rr->nxt ? gldns_read_uint16(rr->rr_type) : 0; }
static inline uint16_t rr_iter_class(priv_getdns_rr_iter *rr)
{ return rr->rr_type + 4 <= rr->nxt ? gldns_read_uint16(rr->rr_type + 2) : 0; }

static priv_getdns_rr_iter *rr_iter_ansauth(priv_getdns_rr_iter *rr)
{
	while (rr && rr->pos && !(
	    priv_getdns_rr_iter_section(rr) == GLDNS_SECTION_ANSWER ||
	    priv_getdns_rr_iter_section(rr) == GLDNS_SECTION_AUTHORITY))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

static int rr_owner_equal(priv_getdns_rr_iter *rr, uint8_t *name)
{
	uint8_t owner_spc[256], *owner;
	size_t  owner_len = sizeof(owner_spc);

	return (owner = priv_getdns_owner_if_or_as_decompressed(rr,  owner_spc
	                                                          , &owner_len))
	    && priv_getdns_dname_equal(owner, name);
}

static priv_getdns_rr_iter *rr_iter_name_class_type(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && !(
	    rr_iter_type(rr)  == rr_type  &&
	    rr_iter_class(rr) == rr_class &&
	    rr_owner_equal(rr, name)))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

static priv_getdns_rr_iter *rr_iter_not_name_class_type(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && (
	    rr_iter_type(rr)  == GETDNS_RRTYPE_RRSIG || (
	    rr_iter_type(rr)  == rr_type  &&
	    rr_iter_class(rr) == rr_class &&
	    rr_owner_equal(rr, name))))

		rr = priv_getdns_rr_iter_next(rr);
	
	return rr && rr->pos ? rr : NULL;
}

static priv_getdns_rr_iter *rr_iter_rrsig_covering(priv_getdns_rr_iter *rr,
    uint8_t *name, uint16_t rr_class, uint16_t rr_type)
{
	while (rr_iter_ansauth(rr) && !(
	    rr_iter_type(rr)  == GETDNS_RRTYPE_RRSIG &&
	    rr_iter_class(rr) == rr_class &&
	    rr->rr_type + 12 <= rr->nxt &&
	    gldns_read_uint16(rr->rr_type + 10) == rr_type && 
	    rr_owner_equal(rr, name)))

		rr = priv_getdns_rr_iter_next(rr);

	return rr && rr->pos ? rr : NULL;
}

typedef struct getdns_rrset {
	uint8_t  *name;
	uint16_t  rr_class;
	uint16_t  rr_type;
	uint8_t  *pkt;
	size_t    pkt_len;
	uint8_t   name_spc[];
} getdns_rrset;

typedef struct rrtype_iter {
	priv_getdns_rr_iter  rr_i;
	getdns_rrset        *rrset;
} rrtype_iter;

typedef struct rrsig_iter {
	priv_getdns_rr_iter  rr_i;
	getdns_rrset        *rrset;
} rrsig_iter;

static rrtype_iter *rrtype_iter_next(rrtype_iter *i)
{
	return (rrtype_iter *) rr_iter_name_class_type(
	    priv_getdns_rr_iter_next(&i->rr_i),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrtype_iter *rrtype_iter_init(rrtype_iter *i, getdns_rrset *rrset)
{
	i->rrset = rrset;
	return (rrtype_iter *) rr_iter_name_class_type(
	    priv_getdns_rr_iter_init(&i->rr_i, rrset->pkt, rrset->pkt_len ),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrsig_iter *rrsig_iter_next(rrsig_iter *i)
{
	return (rrsig_iter *) rr_iter_rrsig_covering(
	    priv_getdns_rr_iter_next(&i->rr_i),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

static rrsig_iter *rrsig_iter_init(rrsig_iter *i, getdns_rrset *rrset)
{
	i->rrset = rrset;
	return (rrsig_iter *) rr_iter_rrsig_covering(
	    priv_getdns_rr_iter_init(&i->rr_i, rrset->pkt, rrset->pkt_len),
	    i->rrset->name, i->rrset->rr_class, i->rrset->rr_type);
}

inline static int rrset_has_rrsigs(getdns_rrset *rrset)
{
	rrsig_iter rrsig;
	return rrsig_iter_init(&rrsig, rrset) != NULL;
}

#if defined(SEC_DEBUG) && SEC_DEBUG
static void debug_sec_print_rrset(const char *msg, getdns_rrset *rrset)
{
	char owner[1024];
	char buf_space[2048];
	gldns_buffer buf;
	rrtype_iter *rr, rr_space;
	rrsig_iter  *rrsig, rrsig_space;
	size_t i;

	if (!rrset) {
		DEBUG_SEC("<nil>");
		return;
	}
	gldns_buffer_init_frm_data(&buf, buf_space, sizeof(buf_space));
	if (gldns_wire2str_dname_buf(rrset->name, 256, owner, sizeof(owner)))
		gldns_buffer_printf(&buf, "%s ", owner);
	else	gldns_buffer_printf(&buf, "<nil> ");

	switch (rrset->rr_class) {
	case GETDNS_RRCLASS_IN	: gldns_buffer_printf(&buf, "IN ")  ; break;
	case GETDNS_RRCLASS_CH	: gldns_buffer_printf(&buf, "CH ")  ; break;
	case GETDNS_RRCLASS_HS	: gldns_buffer_printf(&buf, "HS ")  ; break;
	case GETDNS_RRCLASS_NONE: gldns_buffer_printf(&buf, "NONE "); break;
	case GETDNS_RRCLASS_ANY	: gldns_buffer_printf(&buf, "ANY ") ; break;
	default			: gldns_buffer_printf(&buf, "CLASS%d "
						          , rrset->rr_class);
				  break;
	}
	gldns_buffer_printf(&buf, "%s", priv_getdns_rr_type_name(rrset->rr_type));

	gldns_buffer_printf(&buf, ", rrs:");
	for ( rr = rrtype_iter_init(&rr_space, rrset), i = 1
	    ; rr
	    ; rr = rrtype_iter_next(rr), i++)
		gldns_buffer_printf(&buf, " %d", (int)i);

	gldns_buffer_printf(&buf, ", rrsigs:");
	for ( rrsig = rrsig_iter_init(&rrsig_space, rrset), i = 1
	    ; rrsig
	    ; rrsig = rrsig_iter_next(rrsig), i++)
		gldns_buffer_printf(&buf, " %d", (int)i);

	DEBUG_SEC("%s%s\n", msg, buf_space);
}
#else
#define debug_sec_print_rrset(...) DEBUG_OFF(__VA_ARGS__)
#endif

typedef struct rrset_iter rrset_iter;
struct rrset_iter {
	getdns_rrset        rrset;
	uint8_t             name_spc[256];
	size_t              name_len;
	priv_getdns_rr_iter rr_i;
};

static rrset_iter *rrset_iter_init(rrset_iter *i, uint8_t *pkt, size_t pkt_len)
{
	priv_getdns_rr_iter *rr;

	i->rrset.name = i->name_spc;
	i->rrset.pkt = pkt;
	i->rrset.pkt_len = pkt_len;
	i->name_len = 0;

	for ( rr = priv_getdns_rr_iter_init(&i->rr_i, pkt, pkt_len)
	    ;(rr = rr_iter_ansauth(rr))
	    ; rr = priv_getdns_rr_iter_next(rr)) {

		if ((i->rrset.rr_type = rr_iter_type(rr))
		    == GETDNS_RRTYPE_RRSIG)
			continue;

		i->rrset.rr_class = rr_iter_class(rr);

		if (!(i->rrset.name = priv_getdns_owner_if_or_as_decompressed(
		    rr, i->name_spc, &i->name_len)))
			continue;

		return i;
	}
	return NULL;
}

static rrset_iter *rrset_iter_next(rrset_iter *i)
{
	priv_getdns_rr_iter *rr;

	if (!(rr = i && i->rr_i.pos ? &i->rr_i : NULL))
		return NULL;

	if (!(rr = rr_iter_not_name_class_type(rr,
	    i->rrset.name, i->rrset.rr_class, i->rrset.rr_type)))
		return NULL;

	i->rrset.rr_type  = rr_iter_type(rr);
	i->rrset.rr_class = rr_iter_class(rr);
	if (!(i->rrset.name = priv_getdns_owner_if_or_as_decompressed(
		    rr, i->name_spc, &i->name_len)))
		return rrset_iter_next(i);

	return i;
}

static getdns_rrset *rrset_iter_value(rrset_iter *i)
{
	if (!i)
		return NULL;
	if (!i->rr_i.pos)
		return NULL;
	return &i->rrset;
}

/* ------------------------------------------------------------------------- */

typedef struct chain_head chain_head;
typedef struct chain_node chain_node;

struct chain_head {
	struct mem_funcs  my_mf;

	chain_head         *next;
	chain_node         *parent;
	size_t              node_count; /* Number of nodes attached directly
	                                 * to this head.  For cleaning.  */
	getdns_network_req *netreq;
	getdns_rrset        rrset;
	uint8_t             name_spc[];
};

struct chain_node {
	chain_node  *parent;
	
	getdns_network_req *dnskey_req;
	getdns_rrset        dnskey;
	getdns_network_req *ds_req;
	getdns_rrset        ds;
	getdns_network_req *soa_req;

	chain_head  *chains;
};

#ifdef STUB_NATIVE_DNSSEC
static int chain_head_validate_dnssec(chain_head *head, getdns_list *tas)
{
	return GETDNS_DNSSEC_INSECURE;
}

static void chain_validate_dnssec(chain_head *chain)
{
	chain_head *head;
	getdns_list *tas =
	    chain->netreq->owner->context->dnssec_trust_anchors;

	for (head = chain; head; head = head->next) {
		switch (chain_head_validate_dnssec(head, tas)) {
		case GETDNS_DNSSEC_SECURE: break;
		case GETDNS_DNSSEC_BOGUS : head->netreq->bogus = 1;
		default                  : continue;
		}
		/* TODO: Validate head->rrset */
	}
}
#endif

static size_t count_outstanding_requests(chain_head *head)
{
	size_t count;
	chain_node *node;

	if (!head)
		return 0;

	for ( node = head->parent, count = 0
	    ; node
	    ; node = node->parent) {

		if (node->dnskey_req &&
		    node->dnskey_req->state != NET_REQ_FINISHED &&
		    node->dnskey_req->state != NET_REQ_CANCELED)
			count++;

		if (node->ds_req &&
		    node->ds_req->state != NET_REQ_FINISHED &&
		    node->ds_req->state != NET_REQ_CANCELED)
			count++;

		if (node->soa_req &&
		    node->soa_req->state != NET_REQ_FINISHED &&
		    node->soa_req->state != NET_REQ_CANCELED)
			count++;
	}
	return count + count_outstanding_requests(head->next);
}

static void append_rrs2val_chain_list(getdns_context *ctxt,
    getdns_list *val_chain_list, getdns_network_req *netreq)
{
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrtype_iter *rr, rr_spc;
	rrsig_iter  *rrsig, rrsig_spc;
	getdns_dict *rr_dict;

	for ( i = rrset_iter_init(&i_spc,netreq->response,netreq->response_len)
	    ; i
	    ; i = rrset_iter_next(i)) {

		rrset = rrset_iter_value(i);

		if (rrset->rr_type != GETDNS_RRTYPE_DNSKEY &&
		    rrset->rr_type != GETDNS_RRTYPE_DS     &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC   &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC3)
			continue;

		for ( rr = rrtype_iter_init(&rr_spc, rrset)
		    ; rr; rr = rrtype_iter_next(rr)) {

			rr_dict = priv_getdns_rr_iter2rr_dict(ctxt, &rr->rr_i);
			if (!rr_dict) continue;

			(void)getdns_list_append_dict(val_chain_list, rr_dict);
			getdns_dict_destroy(rr_dict);
		}
		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset)
		    ; rrsig; rrsig = rrsig_iter_next(rrsig)) {

			rr_dict=priv_getdns_rr_iter2rr_dict(ctxt,&rrsig->rr_i);
			if (!rr_dict) continue;

			(void)getdns_list_append_dict(val_chain_list, rr_dict);
			getdns_dict_destroy(rr_dict);
		}
	}
}

static void check_chain_complete(chain_head *chain)
{
	getdns_dns_req *dnsreq;
	size_t o, node_count;
	chain_head *head, *next;
	chain_node *node;
	getdns_list *val_chain_list;
	getdns_dict *response_dict;

	if ((o = count_outstanding_requests(chain)) > 0) {
		DEBUG_SEC("%zu outstanding requests\n", o);
		return;
	}
	DEBUG_SEC("Chain done!\n");
	dnsreq = chain->netreq->owner;

#ifdef STUB_NATIVE_DNSSEC
	chain_validate_dnssec(chain);
#endif

	val_chain_list = dnsreq->dnssec_return_validation_chain
		? getdns_list_create_with_context(dnsreq->context) : NULL;

	/* Walk chain to add values to val_chain_list and to cleanup */
	for ( head = chain; head ; head = next ) {
		next = head->next;
		for ( node_count = head->node_count, node = head->parent
		    ; node_count
		    ; node_count--, node = node->parent ) {

			if (node->dnskey_req) {
				append_rrs2val_chain_list(dnsreq->context,
				    val_chain_list, node->dnskey_req);
				dns_req_free(node->dnskey_req->owner);
			}
			if (node->ds_req) {
				append_rrs2val_chain_list(dnsreq->context,
				    val_chain_list, node->ds_req);
				dns_req_free(node->ds_req->owner);
			}
		}
		GETDNS_FREE(head->my_mf, head);
	}

	response_dict = create_getdns_response(dnsreq);
	if (val_chain_list) {
		(void) getdns_dict_set_list(
		    response_dict, "validation_chain", val_chain_list);
		getdns_list_destroy(val_chain_list);
	}
	/* Final user callback */
	priv_getdns_call_user_callback(dnsreq, response_dict);
}

static void val_chain_node_soa_cb(getdns_dns_req *dnsreq);
static void val_chain_sched_soa_node(chain_node *node)
{
	getdns_context *context;
	getdns_eventloop *loop;
	getdns_dns_req *dnsreq;
	char  name[1024];

	context = node->chains->netreq->owner->context;
	loop    = node->chains->netreq->owner->loop;

	if (!gldns_wire2str_dname_buf(node->ds.name, 256, name, sizeof(name)))
		return;

	if (! node->soa_req &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_SOA,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL,
	    val_chain_node_soa_cb))

		node->soa_req     = dnsreq->netreqs[0];
}

static void val_chain_sched_soa(chain_head *head, uint8_t *dname)
{
	chain_node *node;

	if (!*dname)
		return;

	for ( node = head->parent
	    ; node && !priv_getdns_dname_equal(dname, node->ds.name)
	    ; node = node->parent);

	if (node)
		val_chain_sched_soa_node(node);
}

static void val_chain_node_cb(getdns_dns_req *dnsreq);
static void val_chain_sched_node(chain_node *node)
{
	getdns_context *context;
	getdns_eventloop *loop;
	getdns_dns_req *dnsreq;
	char  name[1024];

	context = node->chains->netreq->owner->context;
	loop    = node->chains->netreq->owner->loop;

	if (!gldns_wire2str_dname_buf(node->ds.name, 256, name, sizeof(name)))
		return;

	DEBUG_SEC("schedule DS & DNSKEY lookup for %s\n", name);

	if (! node->dnskey_req /* not scheduled */ &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_DNSKEY,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL, val_chain_node_cb))

		node->dnskey_req     = dnsreq->netreqs[0];

	if (! node->ds_req && node->parent /* not root */ &&
	    ! priv_getdns_general_loop(context, loop, name, GETDNS_RRTYPE_DS,
	    dnssec_ok_checking_disabled, node, &dnsreq, NULL, val_chain_node_cb))

		node->ds_req = dnsreq->netreqs[0];
}

static void val_chain_sched(chain_head *head, uint8_t *dname)
{
	chain_node *node;

	for ( node = head->parent
	    ; node && !priv_getdns_dname_equal(dname, node->ds.name)
	    ; node = node->parent);
	if (node)
		val_chain_sched_node(node);
}

static void val_chain_sched_signer_node(chain_node *node, rrsig_iter *rrsig)
{
	priv_getdns_rdf_iter rdf_spc, *rdf;
	uint8_t signer_spc[256], *signer;
	size_t signer_len;
	
	if (!(rdf = priv_getdns_rdf_iter_init_at(&rdf_spc, &rrsig->rr_i, 7)))
		return;

	if (!(signer = priv_getdns_rdf_if_or_as_decompressed(
	    rdf, signer_spc, &signer_len)))
		return;

	while (node && !priv_getdns_dname_equal(signer, node->ds.name))
		node = node->parent;
	if (node)
		val_chain_sched_node(node);
}

static void val_chain_sched_signer(chain_head *head, rrsig_iter *rrsig)
{
	val_chain_sched_signer_node(head->parent, rrsig);
}

static void val_chain_node_cb(getdns_dns_req *dnsreq)
{
	chain_node *node = (chain_node *)dnsreq->user_pointer;
	getdns_network_req *netreq = dnsreq->netreqs[0];
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrsig_iter  *rrsig, rrsig_spc;

	getdns_context_clear_outbound_request(dnsreq);
	switch (netreq->request_type) {
	case GETDNS_RRTYPE_DS    : node->ds.pkt     = netreq->response;
	                           node->ds.pkt_len = netreq->response_len;
	                           break;
	case GETDNS_RRTYPE_DNSKEY: node->dnskey.pkt     = netreq->response;
	                           node->dnskey.pkt_len = netreq->response_len;
	default                  : check_chain_complete(node->chains);
				   return;
	}
	for ( i = rrset_iter_init(&i_spc,netreq->response,netreq->response_len)
	    ; i
	    ; i = rrset_iter_next(i)) {

		rrset = rrset_iter_value(i);

		if (rrset->rr_type != GETDNS_RRTYPE_DS     &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC   &&
		    rrset->rr_type != GETDNS_RRTYPE_NSEC3)
			continue;

		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset)
		    ; rrsig; rrsig = rrsig_iter_next(rrsig))

			val_chain_sched_signer_node(node, rrsig);
	}
	check_chain_complete(node->chains);
}


static getdns_rrset *rrset_by_type(
    rrset_iter *i_spc, getdns_network_req *netreq, uint16_t rr_type)
{
	rrset_iter   *i;
	getdns_rrset *rrset;

	for ( i = rrset_iter_init(i_spc,netreq->response,netreq->response_len)
	    ; i
	    ; i = rrset_iter_next(i)) {

		rrset = rrset_iter_value(i);
		if (rrset->rr_type == rr_type) /* Check class too? */
			return rrset;
	}
	return NULL;
}

static void val_chain_node_soa_cb(getdns_dns_req *dnsreq)
{
	chain_node *node = (chain_node *)dnsreq->user_pointer;
	getdns_network_req *netreq = dnsreq->netreqs[0];
	rrset_iter i_spc;
	getdns_rrset *rrset;

	getdns_context_clear_outbound_request(dnsreq);

	if ((rrset = rrset_by_type(&i_spc, netreq, GETDNS_RRTYPE_SOA))) {

		while (node &&
		    ! priv_getdns_dname_equal(node->ds.name, rrset->name))
			node = node->parent;

		val_chain_sched_node(node);
	} else
		val_chain_sched_soa_node(node->parent);

	check_chain_complete(node->chains);
}

static int is_subdomain(
    const uint8_t * const subdomain, const uint8_t *domain)
{
	while (*domain) {
		if (priv_getdns_dname_equal(subdomain, domain))
			return 1;

		domain += *domain + 1;
	}
	return *subdomain == 0;
}

static uint8_t **reverse_labels(uint8_t *dname, uint8_t **labels)
{
	if (*dname)
		labels = reverse_labels(dname + *dname + 1, labels);
	*labels = dname;
	return labels + 1;
}

static chain_head *add_rrset2val_chain(struct mem_funcs *mf,
    chain_head **chain_p, getdns_rrset *rrset, getdns_network_req *netreq)
{
	chain_head *head;
	uint8_t    *labels[128], **last_label, **label;

	size_t      max_labels; /* max labels in common */
	chain_head *max_head;
	chain_node *max_node;

	size_t      dname_len, head_sz, node_count, n;
	uint8_t    *dname, *region;
	chain_node *node;

	last_label = reverse_labels(rrset->name, labels);

	/* Try to find a chain with the most overlapping labels.
	 * max_labels will be the number of labels in common from the root
	 *            (so at least one; the root)
	 * max_head   will be the head of the chain with max # labebs in common
	 */
	max_head = NULL;
	max_labels = 0;
	for (head = *chain_p; head; head = head->next) {
		for (label = labels; label < last_label; label++) {
			if (! is_subdomain(*label, head->rrset.name))
				break;
		}
		if (label - labels > max_labels) {
			max_labels = label - labels;
			max_head = head;
		}
	}
	/* Chain found.  Now set max_node to the point in the chain where nodes
	 *               will be common.
	 */
	if (max_head) {
		for ( node = max_head->parent, n = 0
		    ; node
		    ; node = node->parent, n++);

		for ( n -= max_labels, node = max_head->parent
		    ; n
		    ; n--, node = node->parent);
	} else
		max_node = NULL;

	/* node_count is the amount of nodes to still allocate.
	 * the last one's parent has to hook into the max_node.
	 */
	dname_len = *labels - last_label[-1] + 1;
	head_sz = (sizeof(chain_head) + dname_len + 7) / 8 * 8;
	node_count = last_label - labels - max_labels;
	DEBUG_SEC( "%zu labels in common. %zu labels to allocate\n"
	         , max_labels, node_count);

	if (! (region = GETDNS_XMALLOC(*mf, uint8_t, head_sz + 
	    node_count * sizeof(chain_node))))
		return NULL;
	
	/* Append the head on the linked list of heads */
	for (head = *chain_p; head && head->next; head = head->next);
	if  (head)
		head = head->next = (chain_head *)region;
	else
		head = *chain_p   = (chain_head *)region;

	head->my_mf = *mf;
	head->next = NULL;
	head->rrset.name = head->name_spc;
	memcpy(head->name_spc, rrset->name, dname_len);
	head->rrset.rr_class = rrset->rr_class;
	head->rrset.rr_type = rrset->rr_type;
	head->rrset.pkt = rrset->pkt;
	head->rrset.pkt_len = rrset->pkt_len;
	head->netreq = netreq;
	head->node_count = node_count;

	if (!node_count) {
		head->parent = max_head->parent;
		return head;
	}

	/* Initialize the nodes */
	node = (chain_node *)(region + head_sz);
	head->parent = node;

	for ( node = (chain_node *)(region + head_sz), head->parent = node
	                                             , dname = head->rrset.name
	    ; node_count
	    ; node_count--, node = node->parent =&node[1], dname += *dname + 1) {

		node->ds.name         = dname;
		node->dnskey.name     = dname;
		node->ds.rr_class     = head->rrset.rr_class;
		node->dnskey.rr_class = head->rrset.rr_class;
		node->ds.rr_type      = GETDNS_RRTYPE_DS;
		node->dnskey.rr_type  = GETDNS_RRTYPE_DNSKEY;
		node->ds.pkt          = NULL;
		node->ds.pkt_len      = 0;
		node->dnskey.pkt      = NULL;
		node->dnskey.pkt_len  = 0;
		node->ds_req          = NULL;
		node->dnskey_req      = NULL;
		node->soa_req         = NULL;

		node->chains          = *chain_p;
	}
	/* On the first chain, max_node == NULL.
	 * Schedule a root DNSKEY query, we always need that.
	 */
	if (!(node[-1].parent = max_node))
		val_chain_sched(head, (uint8_t *)"\0");

	return head;
}

static void add_netreq2val_chain(
    chain_head **chain_p, getdns_network_req *netreq)
{
	rrset_iter *i, i_spc;
	getdns_rrset *rrset;
	rrsig_iter *rrsig, rrsig_spc;
	size_t n_rrsigs;
	chain_head *head;
	struct mem_funcs *mf;
	getdns_rrset empty_rrset;

	assert(netreq->response);
	assert(netreq->response_len >= GLDNS_HEADER_SIZE);

	mf = priv_getdns_context_mf(netreq->owner->context);

	/* On empty packet, find SOA (zonecut) for the qname and query DS */

	/* For all things with signatures, create a chain */

	/* For all things without signature, find SOA (zonecut) and query DS */

	if (GLDNS_ANCOUNT(netreq->response) == 0 &&
	    GLDNS_NSCOUNT(netreq->response) == 0) {

		empty_rrset.name = netreq->query + GLDNS_HEADER_SIZE;
		empty_rrset.rr_class = GETDNS_RRCLASS_IN;
		empty_rrset.rr_type  = 0;
		empty_rrset.pkt = netreq->response;
		empty_rrset.pkt_len = netreq->response_len;

		head = add_rrset2val_chain(mf, chain_p, &empty_rrset, netreq);
		val_chain_sched_soa(head, empty_rrset.name);
		return;
	}
	for ( i = rrset_iter_init(&i_spc,netreq->response,netreq->response_len)
	    ; i
	    ; i = rrset_iter_next(i)) {

		rrset = rrset_iter_value(i);
		debug_sec_print_rrset("rrset: ", rrset);

		head = add_rrset2val_chain(mf, chain_p, rrset, netreq);
		for ( rrsig = rrsig_iter_init(&rrsig_spc, rrset), n_rrsigs = 0
		    ; rrsig
		    ; rrsig = rrsig_iter_next(rrsig), n_rrsigs++) {
			
			val_chain_sched_signer(head, rrsig);
		}
		if (n_rrsigs)
			continue;

{'fraction_non_alphanumeric': 0.1272651356993737, 'fraction_numerical': 0.006805845511482255, 'mean_word_length': 3.9270726188027156, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 526, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6833835', 'n_tokens_mistral': 20532, 'n_tokens_neox': 19351, 'n_words': 3789}