1 files changed, 356 insertions, 79 deletions

diff --git a/usr.sbin/nsd/namedb.c b/usr.sbin/nsd/namedb.c
index 82801fb545a..b30e96b01c7 100644
--- a/usr.sbin/nsd/namedb.c
+++ b/usr.sbin/nsd/namedb.c
@@ -7,7 +7,7 @@
  *
  */
 
-#include <config.h>
+#include "config.h"
 
 #include <sys/types.h>
 
@@ -18,12 +18,12 @@
 #include <string.h>
 
 #include "namedb.h"
-
+#include "nsec3.h"
 
 static domain_type *
-allocate_domain_info(domain_table_type *table,
-		     const dname_type *dname,
-		     domain_type *parent)
+allocate_domain_info(domain_table_type* table,
+		     const dname_type* dname,
+		     domain_type* parent)
 {
 	domain_type *result;
 
@@ -33,62 +33,312 @@ allocate_domain_info(domain_table_type *table,
 
 	result = (domain_type *) region_alloc(table->region,
 					      sizeof(domain_type));
-	result->node.key = dname_partial_copy(
+	result->dname = dname_partial_copy(
 		table->region, dname, domain_dname(parent)->label_count + 1);
 	result->parent = parent;
 	result->wildcard_child_closest_match = result;
 	result->rrsets = NULL;
-	result->number = 0;
+	result->usage = 0;
 #ifdef NSEC3
-	result->nsec3_cover = NULL;
-	result->nsec3_wcard_child_cover = NULL;
-	result->nsec3_ds_parent_cover = NULL;
-	result->nsec3_lookup = NULL;
-	result->nsec3_is_exact = 0;
-	result->nsec3_ds_parent_is_exact = 0;
+	result->nsec3 = NULL;
 #endif
 	result->is_existing = 0;
 	result->is_apex = 0;
+	assert(table->numlist_last); /* it exists because root exists */
+	/* push this domain at the end of the numlist */
+	result->number = table->numlist_last->number+1;
+	result->numlist_next = NULL;
+	result->numlist_prev = table->numlist_last;
+	table->numlist_last->numlist_next = result;
+	table->numlist_last = result;
 
 	return result;
 }
 
+#ifdef NSEC3
+void
+allocate_domain_nsec3(domain_table_type* table, domain_type* result)
+{
+	if(result->nsec3)
+		return;
+	result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region,
+		sizeof(struct nsec3_domain_data));
+	result->nsec3->nsec3_cover = NULL;
+	result->nsec3->nsec3_wcard_child_cover = NULL;
+	result->nsec3->nsec3_ds_parent_cover = NULL;
+	result->nsec3->nsec3_is_exact = 0;
+	result->nsec3->nsec3_ds_parent_is_exact = 0;
+	result->nsec3->have_nsec3_hash = 0;
+	result->nsec3->have_nsec3_wc_hash = 0;
+	result->nsec3->have_nsec3_ds_parent_hash = 0;
+	result->nsec3->prehash_prev = NULL;
+	result->nsec3->prehash_next = NULL;
+	result->nsec3->nsec3_node.key = NULL;
+	result->nsec3->hash_node.key = NULL;
+	result->nsec3->wchash_node.key = NULL;
+	result->nsec3->dshash_node.key = NULL;
+}
+#endif /* NSEC3 */
+
+/** make the domain last in the numlist, changes numbers of domains */
+static void
+numlist_make_last(domain_table_type* table, domain_type* domain)
+{
+	size_t sw;
+	domain_type* last = table->numlist_last;
+	if(domain == last)
+		return;
+	/* swap numbers with the last element */
+	sw = domain->number;
+	domain->number = last->number;
+	last->number = sw;
+	/* swap list position with the last element */
+	assert(domain->numlist_next);
+	assert(last->numlist_prev);
+	if(domain->numlist_next != last) {
+		/* case 1: there are nodes between domain .. last */
+		domain_type* span_start = domain->numlist_next;
+		domain_type* span_end = last->numlist_prev;
+		/* these assignments walk the new list from start to end */
+		if(domain->numlist_prev)
+			domain->numlist_prev->numlist_next = last;
+		last->numlist_prev = domain->numlist_prev;
+		last->numlist_next = span_start;
+		span_start->numlist_prev = last;
+		span_end->numlist_next = domain;
+		domain->numlist_prev = span_end;
+		domain->numlist_next = NULL;
+	} else {
+		/* case 2: domain and last are neighbors */
+		/* these assignments walk the new list from start to end */
+		if(domain->numlist_prev)
+			domain->numlist_prev->numlist_next = last;
+		last->numlist_prev = domain->numlist_prev;
+		last->numlist_next = domain;
+		domain->numlist_prev = last;
+		domain->numlist_next = NULL;
+	}
+	table->numlist_last = domain;
+}
+
+/** pop the biggest domain off the numlist */
+static domain_type*
+numlist_pop_last(domain_table_type* table)
+{
+	domain_type* d = table->numlist_last;
+	table->numlist_last = table->numlist_last->numlist_prev;
+	if(table->numlist_last)
+		table->numlist_last->numlist_next = NULL;
+	return d;
+}
+
+/** see if a domain is eligible to be deleted, and thus is not used */
+static int
+domain_can_be_deleted(domain_type* domain)
+{
+	domain_type* n;
+	/* it has data or it has usage, do not delete it */
+	if(domain->rrsets) return 0;
+	if(domain->usage) return 0;
+	n = domain_next(domain);
+	/* it has children domains, do not delete it */
+	if(n && domain_is_subdomain(n, domain))
+		return 0;
+	return 1;
+}
+
+#ifdef NSEC3
+/** see if domain is on the prehash list */
+int domain_is_prehash(domain_table_type* table, domain_type* domain)
+{
+	if(domain->nsec3
+		&& (domain->nsec3->prehash_prev || domain->nsec3->prehash_next))
+		return 1;
+	return (table->prehash_list == domain);
+}
+
+/** remove domain node from NSEC3 tree in hash space */
+void
+zone_del_domain_in_hash_tree(rbtree_t* tree, rbnode_t* node)
+{
+	if(!node->key)
+		return;
+	rbtree_delete(tree, node->key);
+	/* note that domain is no longer in the tree */
+	node->key = NULL;
+}
+
+/** clear the prehash list */
+void prehash_clear(domain_table_type* table)
+{
+	domain_type* d = table->prehash_list, *n;
+	while(d) {
+		n = d->nsec3->prehash_next;
+		d->nsec3->prehash_prev = NULL;
+		d->nsec3->prehash_next = NULL;
+		d = n;
+	}
+	table->prehash_list = NULL;
+}
+
+/** add domain to prehash list */
+void
+prehash_add(domain_table_type* table, domain_type* domain)
+{
+	if(domain_is_prehash(table, domain))
+		return;
+	allocate_domain_nsec3(table, domain);
+	domain->nsec3->prehash_next = table->prehash_list;
+	if(table->prehash_list)
+		table->prehash_list->nsec3->prehash_prev = domain;
+	table->prehash_list = domain;
+}
+
+/** remove domain from prehash list */
+void
+prehash_del(domain_table_type* table, domain_type* domain)
+{
+	if(domain->nsec3->prehash_next)
+		domain->nsec3->prehash_next->nsec3->prehash_prev =
+			domain->nsec3->prehash_prev;
+	if(domain->nsec3->prehash_prev)
+		domain->nsec3->prehash_prev->nsec3->prehash_next =
+			domain->nsec3->prehash_next;
+	else	table->prehash_list = domain->nsec3->prehash_next;
+	domain->nsec3->prehash_next = NULL;
+	domain->nsec3->prehash_prev = NULL;
+}
+#endif /* NSEC3 */
+
+/** perform domain name deletion */
+static void
+do_deldomain(namedb_type* db, domain_type* domain)
+{
+	assert(domain && domain->parent); /* exists and not root */
+	/* first adjust the number list so that domain is the last one */
+	numlist_make_last(db->domains, domain);
+	/* pop off the domain from the number list */
+	(void)numlist_pop_last(db->domains);
+
+#ifdef NSEC3
+	/* if on prehash list, remove from prehash */
+	if(domain_is_prehash(db->domains, domain))
+		prehash_del(db->domains, domain);
+
+	/* see if nsec3-nodes are used */
+	if(domain->nsec3) {
+		if(domain->nsec3->nsec3_node.key)
+			zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
+				->nsec3tree, &domain->nsec3->nsec3_node);
+		if(domain->nsec3->hash_node.key)
+			zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
+				->hashtree, &domain->nsec3->hash_node);
+		if(domain->nsec3->wchash_node.key)
+			zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
+				->wchashtree, &domain->nsec3->wchash_node);
+		if(domain->nsec3->dshash_node.key)
+			zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain)
+				->dshashtree, &domain->nsec3->dshash_node);
+		region_recycle(db->domains->region, domain->nsec3,
+			sizeof(struct nsec3_domain_data));
+	}
+#endif /* NSEC3 */
+
+	/* see if this domain is someones wildcard-child-closest-match,
+	 * which can only be the parent, and then it should use the
+	 * one-smaller than this domain as closest-match. */
+	if(domain->parent->wildcard_child_closest_match == domain)
+		domain->parent->wildcard_child_closest_match =
+			domain_previous_existing_child(domain);
+
+	/* actual removal */
+	radix_delete(db->domains->nametree, domain->rnode);
+	region_recycle(db->domains->region, (dname_type*)domain->dname,
+		dname_total_size(domain->dname));
+	region_recycle(db->domains->region, domain, sizeof(domain_type));
+}
+
+void
+domain_table_deldomain(namedb_type* db, domain_type* domain)
+{
+	while(domain_can_be_deleted(domain)) {
+		/* delete it */
+		do_deldomain(db, domain);
+		/* test parent */
+		domain = domain->parent;
+	}
+}
+
+/** clear hash tree */
+void
+hash_tree_clear(rbtree_t* tree)
+{
+	rbnode_t* n;
+	if(!tree) return;
+
+	/* note that elements are no longer in the tree */
+	for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) {
+		n->key = NULL;
+	}
+	tree->count = 0;
+	tree->root = RBTREE_NULL;
+}
+
+void hash_tree_delete(region_type* region, rbtree_t* tree)
+{
+	region_recycle(region, tree, sizeof(rbtree_t));
+}
+
+/** add domain nsec3 node to hashedspace tree */
+void zone_add_domain_in_hash_tree(region_type* region, rbtree_t** tree,
+	int (*cmpf)(const void*, const void*),
+	domain_type* domain, rbnode_t* node)
+{
+	if(!*tree)
+		*tree = rbtree_create(region, cmpf);
+	memset(node, 0, sizeof(rbnode_t));
+	node->key = domain;
+	rbtree_insert(*tree, node);
+}
+
 domain_table_type *
-domain_table_create(region_type *region)
+domain_table_create(region_type* region)
 {
-	const dname_type *origin;
-	domain_table_type *result;
-	domain_type *root;
+	const dname_type* origin;
+	domain_table_type* result;
+	domain_type* root;
 
 	assert(region);
 
 	origin = dname_make(region, (uint8_t *) "", 0);
 
 	root = (domain_type *) region_alloc(region, sizeof(domain_type));
-	root->node.key = origin;
+	root->dname = origin;
 	root->parent = NULL;
 	root->wildcard_child_closest_match = root;
 	root->rrsets = NULL;
 	root->number = 1; /* 0 is used for after header */
+	root->usage = 1; /* do not delete root, ever */
 	root->is_existing = 0;
 	root->is_apex = 0;
+	root->numlist_prev = NULL;
+	root->numlist_next = NULL;
 #ifdef NSEC3
-	root->nsec3_is_exact = 0;
-	root->nsec3_ds_parent_is_exact = 0;
-	root->nsec3_cover = NULL;
-	root->nsec3_wcard_child_cover = NULL;
-	root->nsec3_ds_parent_cover = NULL;
-	root->nsec3_lookup = NULL;
+	root->nsec3 = NULL;
 #endif
 
 	result = (domain_table_type *) region_alloc(region,
 						    sizeof(domain_table_type));
 	result->region = region;
-	result->names_to_domains = rbtree_create(
-		region, (int (*)(const void *, const void *)) dname_compare);
-	rbtree_insert(result->names_to_domains, (rbnode_t *) root);
+	result->nametree = radix_tree_create(region);
+	root->rnode = radname_insert(result->nametree, dname_name(root->dname),
+		root->dname->name_size, root);
 
 	result->root = root;
+	result->numlist_last = root;
+#ifdef NSEC3
+	result->prehash_list = NULL;
+#endif
 
 	return result;
 }
@@ -107,7 +357,9 @@ domain_table_search(domain_table_type *table,
 	assert(closest_match);
 	assert(closest_encloser);
 
-	exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_t **) closest_match);
+	exact = radname_find_less_equal(table->nametree, dname_name(dname),
+		dname->name_size, (struct radnode**)closest_match);
+	*closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem);
 	assert(*closest_match);
 
 	*closest_encloser = *closest_match;
@@ -127,11 +379,11 @@ domain_table_search(domain_table_type *table,
 }
 
 domain_type *
-domain_table_find(domain_table_type *table,
-		  const dname_type *dname)
+domain_table_find(domain_table_type* table,
+		  const dname_type* dname)
 {
-	domain_type *closest_match;
-	domain_type *closest_encloser;
+	domain_type* closest_match;
+	domain_type* closest_encloser;
 	int exact;
 
 	exact = domain_table_search(
@@ -141,12 +393,12 @@ domain_table_find(domain_table_type *table,
 
 
 domain_type *
-domain_table_insert(domain_table_type *table,
-		    const dname_type  *dname)
+domain_table_insert(domain_table_type* table,
+		    const dname_type* dname)
 {
-	domain_type *closest_match;
-	domain_type *closest_encloser;
-	domain_type *result;
+	domain_type* closest_match;
+	domain_type* closest_encloser;
+	domain_type* result;
 	int exact;
 
 	assert(table);
@@ -164,8 +416,9 @@ domain_table_insert(domain_table_type *table,
 			result = allocate_domain_info(table,
 						      dname,
 						      closest_encloser);
-			rbtree_insert(table->names_to_domains, (rbnode_t *) result);
-			result->number = table->names_to_domains->count;
+			result->rnode = radname_insert(table->nametree,
+				dname_name(result->dname),
+				result->dname->name_size, result);
 
 			/*
 			 * If the newly added domain name is larger
@@ -191,26 +444,32 @@ domain_table_insert(domain_table_type *table,
 }
 
 int
-domain_table_iterate(domain_table_type *table,
+domain_table_iterate(domain_table_type* table,
 		    domain_table_iterator_type iterator,
-		    void *user_data)
+		    void* user_data)
 {
-	const void *dname;
-	void *node;
 	int error = 0;
-
-	assert(table);
-
-	RBTREE_WALK(table->names_to_domains, dname, node) {
-		error += iterator((domain_type *) node, user_data);
+	struct radnode* n;
+	for(n = radix_first(table->nametree); n; n = radix_next(n)) {
+		error += iterator((domain_type*)n->elem, user_data);
 	}
-
 	return error;
 }
 
+domain_type *domain_previous_existing_child(domain_type* domain)
+{
+	domain_type* parent = domain->parent;
+	domain = domain_previous(domain);
+	while(domain && !domain->is_existing) {
+		if(domain == parent) /* do not walk back above parent */
+			return parent;
+		domain = domain_previous(domain);
+	}
+	return domain;
+}
 
 void
-domain_add_rrset(domain_type *domain, rrset_type *rrset)
+domain_add_rrset(domain_type* domain, rrset_type* rrset)
 {
 #if 0 	/* fast */
 	rrset->next = domain->rrsets;
@@ -226,15 +485,24 @@ domain_add_rrset(domain_type *domain, rrset_type *rrset)
 
 	while (domain && !domain->is_existing) {
 		domain->is_existing = 1;
+		/* does this name in existance update the parent's
+		 * wildcard closest match? */
+		if(domain->parent
+		   && label_compare(dname_name(domain_dname(domain)),
+			(const uint8_t *) "\001*") <= 0
+		   && dname_compare(domain_dname(domain),
+		   	domain_dname(domain->parent->wildcard_child_closest_match)) > 0) {
+			domain->parent->wildcard_child_closest_match = domain;
+		}
 		domain = domain->parent;
 	}
 }
 
 
 rrset_type *
-domain_find_rrset(domain_type *domain, zone_type *zone, uint16_t type)
+domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type)
 {
-	rrset_type *result = domain->rrsets;
+	rrset_type* result = domain->rrsets;
 
 	while (result) {
 		if (result->zone == zone && rrset_rrtype(result) == type) {
@@ -246,9 +514,9 @@ domain_find_rrset(domain_type *domain, zone_type *zone, uint16_t type)
 }
 
 rrset_type *
-domain_find_any_rrset(domain_type *domain, zone_type *zone)
+domain_find_any_rrset(domain_type* domain, zone_type* zone)
 {
-	rrset_type *result = domain->rrsets;
+	rrset_type* result = domain->rrsets;
 
 	while (result) {
 		if (result->zone == zone) {
@@ -260,14 +528,17 @@ domain_find_any_rrset(domain_type *domain, zone_type *zone)
 }
 
 zone_type *
-domain_find_zone(domain_type *domain)
+domain_find_zone(namedb_type* db, domain_type* domain)
 {
-	rrset_type *rrset;
+	rrset_type* rrset;
 	while (domain) {
-		for (rrset = domain->rrsets; rrset; rrset = rrset->next) {
-			if (rrset_rrtype(rrset) == TYPE_SOA) {
-				return rrset->zone;
+		if(domain->is_apex) {
+			for (rrset = domain->rrsets; rrset; rrset = rrset->next) {
+				if (rrset_rrtype(rrset) == TYPE_SOA) {
+					return rrset->zone;
+				}
 			}
+			return namedb_find_zone(db, domain_dname(domain));
 		}
 		domain = domain->parent;
 	}
@@ -275,9 +546,9 @@ domain_find_zone(domain_type *domain)
 }
 
 zone_type *
-domain_find_parent_zone(zone_type *zone)
+domain_find_parent_zone(zone_type* zone)
 {
-	rrset_type *rrset;
+	rrset_type* rrset;
 
 	assert(zone);
 
@@ -290,7 +561,7 @@ domain_find_parent_zone(zone_type *zone)
 }
 
 domain_type *
-domain_find_ns_rrsets(domain_type *domain, zone_type *zone, rrset_type **ns)
+domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns)
 {
 	while (domain && domain != zone->apex) {
 		*ns = domain_find_rrset(domain, zone, TYPE_NS);
@@ -304,18 +575,18 @@ domain_find_ns_rrsets(domain_type *domain, zone_type *zone, rrset_type **ns)
 }
 
 int
-domain_is_glue(domain_type *domain, zone_type *zone)
+domain_is_glue(domain_type* domain, zone_type* zone)
 {
-	rrset_type *unused;
-	domain_type *ns_domain = domain_find_ns_rrsets(domain, zone, &unused);
+	rrset_type* unused;
+	domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused);
 	return (ns_domain != NULL &&
 		domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL);
 }
 
 domain_type *
-domain_wildcard_child(domain_type *domain)
+domain_wildcard_child(domain_type* domain)
 {
-	domain_type *wildcard_child;
+	domain_type* wildcard_child;
 
 	assert(domain);
 	assert(domain->wildcard_child_closest_match);
@@ -331,14 +602,14 @@ domain_wildcard_child(domain_type *domain)
 }
 
 int
-zone_is_secure(zone_type *zone)
+zone_is_secure(zone_type* zone)
 {
 	assert(zone);
 	return zone->is_secure;
 }
 
 uint16_t
-rr_rrsig_type_covered(rr_type *rr)
+rr_rrsig_type_covered(rr_type* rr)
 {
 	assert(rr->type == TYPE_RRSIG);
 	assert(rr->rdata_count > 0);
@@ -348,20 +619,16 @@ rr_rrsig_type_covered(rr_type *rr)
 }
 
 zone_type *
-namedb_find_zone(namedb_type *db, domain_type *domain)
+namedb_find_zone(namedb_type* db, const dname_type* dname)
 {
-	zone_type *zone;
-
-	for (zone = db->zones; zone; zone = zone->next) {
-		if (zone->apex == domain)
-			break;
-	}
-
-	return zone;
+	struct radnode* n = radname_search(db->zonetree, dname_name(dname),
+		dname->name_size);
+	if(n) return (zone_type*)n->elem;
+	return NULL;
 }
 
 rrset_type *
-domain_find_non_cname_rrset(domain_type *domain, zone_type *zone)
+domain_find_non_cname_rrset(domain_type* domain, zone_type* zone)
 {
 	/* find any rrset type that is not allowed next to a CNAME */
 	/* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */
@@ -381,3 +648,13 @@ domain_find_non_cname_rrset(domain_type *domain, zone_type *zone)
 	}
 	return NULL;
 }
+
+int
+namedb_lookup(struct namedb* db,
+	      const dname_type* dname,
+	      domain_type     **closest_match,
+	      domain_type     **closest_encloser)
+{
+	return domain_table_search(
+		db->domains, dname, closest_match, closest_encloser);
+}