1 files changed, 442 insertions, 0 deletions
diff --git a/3rdParty/Unbound/src/src/iterator/iter_fwd.c b/3rdParty/Unbound/src/src/iterator/iter_fwd.c
new file mode 100644
index 0000000..2df1f9c
--- /dev/null
+++ b/3rdParty/Unbound/src/src/iterator/iter_fwd.c
@@ -0,0 +1,442 @@
+/*
+ * iterator/iter_fwd.c - iterative resolver module forward zones.
+ *
+ * Copyright (c) 2007, NLnet Labs. All rights reserved.
+ *
+ * This software is open source.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * 
+ * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * 
+ * Neither the name of the NLNET LABS nor the names of its contributors may
+ * be used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/**
+ * \file
+ *
+ * This file contains functions to assist the iterator module.
+ * Keep track of forward zones and config settings.
+ */
+#include "config.h"
+#include <ldns/rdata.h>
+#include <ldns/dname.h>
+#include <ldns/rr.h>
+#include "iterator/iter_fwd.h"
+#include "iterator/iter_delegpt.h"
+#include "util/regional.h"
+#include "util/log.h"
+#include "util/config_file.h"
+#include "util/net_help.h"
+#include "util/data/dname.h"
+
+int
+fwd_cmp(const void* k1, const void* k2)
+{
+	int m;
+	struct iter_forward_zone* n1 = (struct iter_forward_zone*)k1;
+	struct iter_forward_zone* n2 = (struct iter_forward_zone*)k2;
+	if(n1->dclass != n2->dclass) {
+		if(n1->dclass < n2->dclass)
+			return -1;
+		return 1;
+	}
+	return dname_lab_cmp(n1->name, n1->namelabs, n2->name, n2->namelabs, 
+		&m);
+}
+
+struct iter_forwards* 
+forwards_create(void)
+{
+	struct iter_forwards* fwd = (struct iter_forwards*)calloc(1,
+		sizeof(struct iter_forwards));
+	if(!fwd)
+		return NULL;
+	fwd->region = regional_create();
+	if(!fwd->region) {
+		forwards_delete(fwd);
+		return NULL;
+	}
+	return fwd;
+}
+
+void 
+forwards_delete(struct iter_forwards* fwd)
+{
+	if(!fwd) 
+		return;
+	regional_destroy(fwd->region);
+	free(fwd->tree);
+	free(fwd);
+}
+
+/** insert info into forward structure */
+static int
+forwards_insert_data(struct iter_forwards* fwd, uint16_t c, uint8_t* nm, 
+	size_t nmlen, int nmlabs, struct delegpt* dp)
+{
+	struct iter_forward_zone* node = regional_alloc(fwd->region,
+		sizeof(struct iter_forward_zone));
+	if(!node)
+		return 0;
+	node->node.key = node;
+	node->dclass = c;
+	node->name = regional_alloc_init(fwd->region, nm, nmlen);
+	if(!node->name)
+		return 0;
+	node->namelen = nmlen;
+	node->namelabs = nmlabs;
+	node->dp = dp;
+	if(!rbtree_insert(fwd->tree, &node->node)) {
+		log_err("duplicate forward zone ignored.");
+	}
+	return 1;
+}
+
+/** insert new info into forward structure given dp */
+static int
+forwards_insert(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
+{
+	return forwards_insert_data(fwd, c, dp->name, dp->namelen,
+		dp->namelabs, dp);
+}
+
+/** initialise parent pointers in the tree */
+static void
+fwd_init_parents(struct iter_forwards* fwd)
+{
+	struct iter_forward_zone* node, *prev = NULL, *p;
+	int m;
+	RBTREE_FOR(node, struct iter_forward_zone*, fwd->tree) {
+		node->parent = NULL;
+		if(!prev || prev->dclass != node->dclass) {
+			prev = node;
+			continue;
+		}
+		(void)dname_lab_cmp(prev->name, prev->namelabs, node->name,
+			node->namelabs, &m); /* we know prev is smaller */
+		/* sort order like: . com. bla.com. zwb.com. net. */
+		/* find the previous, or parent-parent-parent */
+		for(p = prev; p; p = p->parent)
+			/* looking for name with few labels, a parent */
+			if(p->namelabs <= m) {
+				/* ==: since prev matched m, this is closest*/
+				/* <: prev matches more, but is not a parent,
+				 * this one is a (grand)parent */
+				node->parent = p;
+				break;
+			}
+		prev = node;
+	}
+}
+
+/** set zone name */
+static int 
+read_fwds_name(struct iter_forwards* fwd, struct config_stub* s, 
+	struct delegpt* dp)
+{
+	ldns_rdf* rdf;
+	if(!s->name) {
+		log_err("forward zone without a name (use name \".\" to forward everything)");
+		return 0;
+	}
+	rdf = ldns_dname_new_frm_str(s->name);
+	if(!rdf) {
+		log_err("cannot parse forward zone name %s", s->name);
+		return 0;
+	}
+	if(!delegpt_set_name(dp, fwd->region, ldns_rdf_data(rdf))) {
+		ldns_rdf_deep_free(rdf);
+		log_err("out of memory");
+		return 0;
+	}
+	ldns_rdf_deep_free(rdf);
+	return 1;
+}
+
+/** set fwd host names */
+static int 
+read_fwds_host(struct iter_forwards* fwd, struct config_stub* s, 
+	struct delegpt* dp)
+{
+	struct config_strlist* p;
+	ldns_rdf* rdf;
+	for(p = s->hosts; p; p = p->next) {
+		log_assert(p->str);
+		rdf = ldns_dname_new_frm_str(p->str);
+		if(!rdf) {
+			log_err("cannot parse forward %s server name: '%s'", 
+				s->name, p->str);
+			return 0;
+		}
+		if(!delegpt_add_ns(dp, fwd->region, ldns_rdf_data(rdf), 0)) {
+			ldns_rdf_deep_free(rdf);
+			log_err("out of memory");
+			return 0;
+		}
+		ldns_rdf_deep_free(rdf);
+	}
+	return 1;
+}
+
+/** set fwd server addresses */
+static int 
+read_fwds_addr(struct iter_forwards* fwd, struct config_stub* s, 
+	struct delegpt* dp)
+{
+	struct config_strlist* p;
+	struct sockaddr_storage addr;
+	socklen_t addrlen;
+	for(p = s->addrs; p; p = p->next) {
+		log_assert(p->str);
+		if(!extstrtoaddr(p->str, &addr, &addrlen)) {
+			log_err("cannot parse forward %s ip address: '%s'", 
+				s->name, p->str);
+			return 0;
+		}
+		if(!delegpt_add_addr(dp, fwd->region, &addr, addrlen, 0, 0)) {
+			log_err("out of memory");
+			return 0;
+		}
+	}
+	return 1;
+}
+
+/** read forwards config */
+static int 
+read_forwards(struct iter_forwards* fwd, struct config_file* cfg)
+{
+	struct config_stub* s;
+	for(s = cfg->forwards; s; s = s->next) {
+		struct delegpt* dp = delegpt_create(fwd->region);
+		if(!dp) {
+			log_err("out of memory");
+			return 0;
+		}
+		/* set flag that parent side NS information is included.
+		 * Asking a (higher up) server on the internet is not useful */
+		dp->has_parent_side_NS = 1;
+		if(!read_fwds_name(fwd, s, dp) ||
+			!read_fwds_host(fwd, s, dp) ||
+			!read_fwds_addr(fwd, s, dp))
+			return 0;
+		if(!forwards_insert(fwd, LDNS_RR_CLASS_IN, dp))
+			return 0;
+		verbose(VERB_QUERY, "Forward zone server list:");
+		delegpt_log(VERB_QUERY, dp);
+	}
+	return 1;
+}
+
+/** see if zone needs to have a hole inserted */
+static int
+need_hole_insert(rbtree_t* tree, struct iter_forward_zone* zone)
+{
+	struct iter_forward_zone k;
+	if(rbtree_search(tree, zone))
+		return 0; /* exact match exists */
+	k = *zone;
+	k.node.key = &k;
+	/* search up the tree */
+	do {
+		dname_remove_label(&k.name, &k.namelen);
+		k.namelabs --;
+		if(rbtree_search(tree, &k))
+			return 1; /* found an upper forward zone, need hole */
+	} while(k.namelabs > 1);
+	return 0; /* no forwards above, no holes needed */
+}
+
+/** make NULL entries for stubs */
+static int
+make_stub_holes(struct iter_forwards* fwd, struct config_file* cfg)
+{
+	struct config_stub* s;
+	struct iter_forward_zone key;
+	key.node.key = &key;
+	key.dclass = LDNS_RR_CLASS_IN;
+	for(s = cfg->stubs; s; s = s->next) {
+		ldns_rdf* rdf = ldns_dname_new_frm_str(s->name);
+		if(!rdf) {
+			log_err("cannot parse stub name '%s'", s->name);
+			return 0;
+		}
+		key.name = ldns_rdf_data(rdf);
+		key.namelabs = dname_count_size_labels(key.name, &key.namelen);
+		if(!need_hole_insert(fwd->tree, &key)) {
+			ldns_rdf_deep_free(rdf);
+			continue;
+		}
+		if(!forwards_insert_data(fwd, key.dclass, key.name, 
+			key.namelen, key.namelabs, NULL)) {
+			ldns_rdf_deep_free(rdf);
+			log_err("out of memory");
+			return 0;
+		}
+		ldns_rdf_deep_free(rdf);
+	}
+	return 1;
+}
+
+int 
+forwards_apply_cfg(struct iter_forwards* fwd, struct config_file* cfg)
+{
+	free(fwd->tree);
+	regional_free_all(fwd->region);
+	fwd->tree = rbtree_create(fwd_cmp);
+	if(!fwd->tree)
+		return 0;
+
+	/* read forward zones */
+	if(!read_forwards(fwd, cfg))
+		return 0;
+	if(!make_stub_holes(fwd, cfg))
+		return 0;
+	fwd_init_parents(fwd);
+	return 1;
+}
+
+struct delegpt* 
+forwards_lookup(struct iter_forwards* fwd, uint8_t* qname, uint16_t qclass)
+{
+	/* lookup the forward zone in the tree */
+	rbnode_t* res = NULL;
+	struct iter_forward_zone *result;
+	struct iter_forward_zone key;
+	key.node.key = &key;
+	key.dclass = qclass;
+	key.name = qname;
+	key.namelabs = dname_count_size_labels(qname, &key.namelen);
+	if(rbtree_find_less_equal(fwd->tree, &key, &res)) {
+		/* exact */
+		result = (struct iter_forward_zone*)res;
+	} else {
+		/* smaller element (or no element) */
+		int m;
+		result = (struct iter_forward_zone*)res;
+		if(!result || result->dclass != qclass)
+			return NULL;
+		/* count number of labels matched */
+		(void)dname_lab_cmp(result->name, result->namelabs, key.name,
+			key.namelabs, &m);
+		while(result) { /* go up until qname is subdomain of stub */
+			if(result->namelabs <= m)
+				break;
+			result = result->parent;
+		}
+	}
+	if(result)
+		return result->dp;
+	return NULL;
+}
+
+struct delegpt* 
+forwards_lookup_root(struct iter_forwards* fwd, uint16_t qclass)
+{
+	uint8_t root = 0;
+	return forwards_lookup(fwd, &root, qclass);
+}
+
+int
+forwards_next_root(struct iter_forwards* fwd, uint16_t* dclass)
+{
+	struct iter_forward_zone key;
+	rbnode_t* n;
+	struct iter_forward_zone* p;
+	if(*dclass == 0) {
+		/* first root item is first item in tree */
+		n = rbtree_first(fwd->tree);
+		if(n == RBTREE_NULL)
+			return 0;
+		p = (struct iter_forward_zone*)n;
+		if(dname_is_root(p->name)) {
+			*dclass = p->dclass;
+			return 1;
+		}
+		/* root not first item? search for higher items */
+		*dclass = p->dclass + 1;
+		return forwards_next_root(fwd, dclass);
+	}
+	/* find class n in tree, we may get a direct hit, or if we don't
+	 * this is the last item of the previous class so rbtree_next() takes
+	 * us to the next root (if any) */
+	key.node.key = &key;
+	key.name = (uint8_t*)"\000";
+	key.namelen = 1;
+	key.namelabs = 0;
+	key.dclass = *dclass;
+	n = NULL;
+	if(rbtree_find_less_equal(fwd->tree, &key, &n)) {
+		/* exact */
+		return 1;
+	} else {
+		/* smaller element */
+		if(!n || n == RBTREE_NULL)
+			return 0; /* nothing found */
+		n = rbtree_next(n);
+		if(n == RBTREE_NULL)
+			return 0; /* no higher */
+		p = (struct iter_forward_zone*)n;
+		if(dname_is_root(p->name)) {
+			*dclass = p->dclass;
+			return 1;
+		}
+		/* not a root node, return next higher item */
+		*dclass = p->dclass+1;
+		return forwards_next_root(fwd, dclass);
+	}
+}
+
+size_t 
+forwards_get_mem(struct iter_forwards* fwd)
+{
+	if(!fwd)
+		return 0;
+	return sizeof(*fwd) + sizeof(*fwd->tree) + 
+		regional_get_mem(fwd->region);
+}
+
+int 
+forwards_add_zone(struct iter_forwards* fwd, uint16_t c, struct delegpt* dp)
+{
+	if(!forwards_insert(fwd, c, dp))
+		return 0;
+	fwd_init_parents(fwd);
+	return 1;
+}
+
+void 
+forwards_delete_zone(struct iter_forwards* fwd, uint16_t c, uint8_t* nm)
+{
+	struct iter_forward_zone key;
+	key.node.key = &key;
+	key.dclass = c;
+	key.name = nm;
+	key.namelabs = dname_count_size_labels(nm, &key.namelen);
+	if(!rbtree_search(fwd->tree, &key))
+		return; /* nothing to do */
+	(void)rbtree_delete(fwd->tree, &key);
+	fwd_init_parents(fwd);
+}
+