Home | History | Annotate | Line # | Download | only in dist
      1 /*
      2  * namedb.c -- common namedb operations.
      3  *
      4  * Copyright (c) 2001-2006, NLnet Labs. All rights reserved.
      5  *
      6  * See LICENSE for the license.
      7  *
      8  */
      9 
     10 #include "config.h"
     11 
     12 #include <sys/types.h>
     13 
     14 #include <assert.h>
     15 #include <ctype.h>
     16 #include <limits.h>
     17 #include <stdio.h>
     18 #include <string.h>
     19 
     20 #include "namedb.h"
     21 #include "nsec3.h"
     22 
     23 static domain_type *
     24 allocate_domain_info(domain_table_type* table,
     25 		     const dname_type* dname,
     26 		     domain_type* parent)
     27 {
     28 	domain_type *result;
     29 
     30 	assert(table);
     31 	assert(dname);
     32 	assert(parent);
     33 
     34 	result = (domain_type *) region_alloc(table->region,
     35 					      sizeof(domain_type));
     36 #ifdef USE_RADIX_TREE
     37 	result->dname
     38 #else
     39 	result->node.key
     40 #endif
     41 		= dname_partial_copy(
     42 		table->region, dname, domain_dname(parent)->label_count + 1);
     43 	result->parent = parent;
     44 	result->wildcard_child_closest_match = result;
     45 	result->rrsets = NULL;
     46 	result->usage = 0;
     47 #ifdef NSEC3
     48 	result->nsec3 = NULL;
     49 #endif
     50 	result->is_existing = 0;
     51 	result->is_apex = 0;
     52 	assert(table->numlist_last); /* it exists because root exists */
     53 	/* push this domain at the end of the numlist */
     54 	result->number = table->numlist_last->number+1;
     55 	result->numlist_next = NULL;
     56 	result->numlist_prev = table->numlist_last;
     57 	table->numlist_last->numlist_next = result;
     58 	table->numlist_last = result;
     59 
     60 	return result;
     61 }
     62 
     63 #ifdef NSEC3
     64 void
     65 allocate_domain_nsec3(domain_table_type* table, domain_type* result)
     66 {
     67 	if(result->nsec3)
     68 		return;
     69 	result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region,
     70 		sizeof(struct nsec3_domain_data));
     71 	result->nsec3->nsec3_cover = NULL;
     72 	result->nsec3->nsec3_wcard_child_cover = NULL;
     73 	result->nsec3->nsec3_ds_parent_cover = NULL;
     74 	result->nsec3->nsec3_is_exact = 0;
     75 	result->nsec3->nsec3_ds_parent_is_exact = 0;
     76 	result->nsec3->hash_wc = NULL;
     77 	result->nsec3->ds_parent_hash = NULL;
     78 	result->nsec3->prehash_prev = NULL;
     79 	result->nsec3->prehash_next = NULL;
     80 	result->nsec3->nsec3_node.key = NULL;
     81 }
     82 #endif /* NSEC3 */
     83 
     84 void
     85 numlist_make_last(domain_table_type* table, domain_type* domain)
     86 {
     87 	uint32_t sw;
     88 	domain_type* last = table->numlist_last;
     89 	if(domain == last)
     90 		return;
     91 	/* swap numbers with the last element */
     92 	sw = domain->number;
     93 	domain->number = last->number;
     94 	last->number = sw;
     95 	/* swap list position with the last element */
     96 	assert(domain->numlist_next);
     97 	assert(last->numlist_prev);
     98 	if(domain->numlist_next != last) {
     99 		/* case 1: there are nodes between domain .. last */
    100 		domain_type* span_start = domain->numlist_next;
    101 		domain_type* span_end = last->numlist_prev;
    102 		/* these assignments walk the new list from start to end */
    103 		if(domain->numlist_prev)
    104 			domain->numlist_prev->numlist_next = last;
    105 		last->numlist_prev = domain->numlist_prev;
    106 		last->numlist_next = span_start;
    107 		span_start->numlist_prev = last;
    108 		span_end->numlist_next = domain;
    109 		domain->numlist_prev = span_end;
    110 		domain->numlist_next = NULL;
    111 	} else {
    112 		/* case 2: domain and last are neighbors */
    113 		/* these assignments walk the new list from start to end */
    114 		if(domain->numlist_prev)
    115 			domain->numlist_prev->numlist_next = last;
    116 		last->numlist_prev = domain->numlist_prev;
    117 		last->numlist_next = domain;
    118 		domain->numlist_prev = last;
    119 		domain->numlist_next = NULL;
    120 	}
    121 	table->numlist_last = domain;
    122 }
    123 
    124 domain_type*
    125 numlist_pop_last(domain_table_type* table)
    126 {
    127 	domain_type* d = table->numlist_last;
    128 	table->numlist_last = table->numlist_last->numlist_prev;
    129 	if(table->numlist_last)
    130 		table->numlist_last->numlist_next = NULL;
    131 	return d;
    132 }
    133 
    134 /** see if a domain is eligible to be deleted, and thus is not used */
    135 static int
    136 domain_can_be_deleted(domain_type* domain)
    137 {
    138 	domain_type* n;
    139 	/* it has data or it has usage, do not delete it */
    140 	if(domain->rrsets) return 0;
    141 	if(domain->usage) return 0;
    142 	n = domain_next(domain);
    143 	/* it has children domains, do not delete it */
    144 	if(n && domain_is_subdomain(n, domain))
    145 		return 0;
    146 	return 1;
    147 }
    148 
    149 #ifdef NSEC3
    150 /** see if domain is on the prehash list */
    151 int domain_is_prehash(domain_table_type* table, domain_type* domain)
    152 {
    153 	if(domain->nsec3
    154 		&& (domain->nsec3->prehash_prev || domain->nsec3->prehash_next))
    155 		return 1;
    156 	return (table->prehash_list == domain);
    157 }
    158 
    159 /** remove domain node from NSEC3 tree in hash space */
    160 void
    161 zone_del_domain_in_hash_tree(rbtree_type* tree, rbnode_type* node)
    162 {
    163 	if(!node->key || !tree)
    164 		return;
    165 	rbtree_delete(tree, node->key);
    166 	/* note that domain is no longer in the tree */
    167 	node->key = NULL;
    168 }
    169 
    170 /** clear the prehash list */
    171 void prehash_clear(domain_table_type* table)
    172 {
    173 	domain_type* d = table->prehash_list, *n;
    174 	while(d) {
    175 		n = d->nsec3->prehash_next;
    176 		d->nsec3->prehash_prev = NULL;
    177 		d->nsec3->prehash_next = NULL;
    178 		d = n;
    179 	}
    180 	table->prehash_list = NULL;
    181 }
    182 
    183 /** add domain to prehash list */
    184 void
    185 prehash_add(domain_table_type* table, domain_type* domain)
    186 {
    187 	if(domain_is_prehash(table, domain))
    188 		return;
    189 	allocate_domain_nsec3(table, domain);
    190 	domain->nsec3->prehash_next = table->prehash_list;
    191 	if(table->prehash_list)
    192 		table->prehash_list->nsec3->prehash_prev = domain;
    193 	table->prehash_list = domain;
    194 }
    195 
    196 /** remove domain from prehash list */
    197 void
    198 prehash_del(domain_table_type* table, domain_type* domain)
    199 {
    200 	if(domain->nsec3->prehash_next)
    201 		domain->nsec3->prehash_next->nsec3->prehash_prev =
    202 			domain->nsec3->prehash_prev;
    203 	if(domain->nsec3->prehash_prev)
    204 		domain->nsec3->prehash_prev->nsec3->prehash_next =
    205 			domain->nsec3->prehash_next;
    206 	else	table->prehash_list = domain->nsec3->prehash_next;
    207 	domain->nsec3->prehash_next = NULL;
    208 	domain->nsec3->prehash_prev = NULL;
    209 }
    210 #endif /* NSEC3 */
    211 
    212 /** perform domain name deletion */
    213 static void
    214 do_deldomain(namedb_type* db, domain_type* domain)
    215 {
    216 	assert(domain && domain->parent); /* exists and not root */
    217 	/* first adjust the number list so that domain is the last one */
    218 	numlist_make_last(db->domains, domain);
    219 	/* pop off the domain from the number list */
    220 	(void)numlist_pop_last(db->domains);
    221 
    222 #ifdef NSEC3
    223 	/* if on prehash list, remove from prehash */
    224 	if(domain_is_prehash(db->domains, domain))
    225 		prehash_del(db->domains, domain);
    226 
    227 	/* see if nsec3-nodes are used */
    228 	if(domain->nsec3) {
    229 		if(domain->nsec3->nsec3_node.key)
    230 			zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
    231 				->nsec3tree, &domain->nsec3->nsec3_node);
    232 		if(domain->nsec3->hash_wc) {
    233 			if(domain->nsec3->hash_wc->hash.node.key)
    234 				zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
    235 					->hashtree, &domain->nsec3->hash_wc->hash.node);
    236 			if(domain->nsec3->hash_wc->wc.node.key)
    237 				zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain)
    238 					->wchashtree, &domain->nsec3->hash_wc->wc.node);
    239 		}
    240 		if(domain->nsec3->ds_parent_hash && domain->nsec3->ds_parent_hash->node.key)
    241 			zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain)
    242 				->dshashtree, &domain->nsec3->ds_parent_hash->node);
    243 		if(domain->nsec3->hash_wc) {
    244 			region_recycle(db->domains->region,
    245 				domain->nsec3->hash_wc,
    246 				sizeof(nsec3_hash_wc_node_type));
    247 		}
    248 		if(domain->nsec3->ds_parent_hash) {
    249 			region_recycle(db->domains->region,
    250 				domain->nsec3->ds_parent_hash,
    251 				sizeof(nsec3_hash_node_type));
    252 		}
    253 		region_recycle(db->domains->region, domain->nsec3,
    254 			sizeof(struct nsec3_domain_data));
    255 	}
    256 #endif /* NSEC3 */
    257 
    258 	/* see if this domain is someones wildcard-child-closest-match,
    259 	 * which can only be the parent, and then it should use the
    260 	 * one-smaller than this domain as closest-match. */
    261 	if(domain->parent->wildcard_child_closest_match == domain)
    262 		domain->parent->wildcard_child_closest_match =
    263 			domain_previous_existing_child(domain);
    264 
    265 	/* actual removal */
    266 #ifdef USE_RADIX_TREE
    267 	radix_delete(db->domains->nametree, domain->rnode);
    268 #else
    269 	rbtree_delete(db->domains->names_to_domains, domain->node.key);
    270 #endif
    271 	region_recycle(db->domains->region, domain_dname(domain),
    272 		dname_total_size(domain_dname(domain)));
    273 	region_recycle(db->domains->region, domain, sizeof(domain_type));
    274 }
    275 
    276 void
    277 domain_table_deldomain(namedb_type* db, domain_type* domain)
    278 {
    279 	domain_type* parent;
    280 
    281 	while(domain_can_be_deleted(domain)) {
    282 		parent = domain->parent;
    283 		/* delete it */
    284 		do_deldomain(db, domain);
    285 		/* test parent */
    286 		domain = parent;
    287 	}
    288 }
    289 
    290 void hash_tree_delete(region_type* region, rbtree_type* tree)
    291 {
    292 	region_recycle(region, tree, sizeof(rbtree_type));
    293 }
    294 
    295 /** add domain nsec3 node to hashedspace tree */
    296 void zone_add_domain_in_hash_tree(region_type* region, rbtree_type** tree,
    297 	int (*cmpf)(const void*, const void*),
    298 	domain_type* domain, rbnode_type* node)
    299 {
    300 	if(!*tree)
    301 		*tree = rbtree_create(region, cmpf);
    302 	if(node->key && node->key == domain
    303 	&& rbtree_search(*tree, domain) == node)
    304 		return;
    305 	memset(node, 0, sizeof(rbnode_type));
    306 	node->key = domain;
    307 	rbtree_insert(*tree, node);
    308 }
    309 
    310 domain_table_type *
    311 domain_table_create(region_type* region)
    312 {
    313 	const dname_type* origin;
    314 	domain_table_type* result;
    315 	domain_type* root;
    316 
    317 	assert(region);
    318 
    319 	origin = dname_make(region, (uint8_t *) "", 0);
    320 
    321 	root = (domain_type *) region_alloc(region, sizeof(domain_type));
    322 #ifdef USE_RADIX_TREE
    323 	root->dname
    324 #else
    325 	root->node.key
    326 #endif
    327 		= origin;
    328 	root->parent = NULL;
    329 	root->wildcard_child_closest_match = root;
    330 	root->rrsets = NULL;
    331 	root->number = 1; /* 0 is used for after header */
    332 	root->usage = 1; /* do not delete root, ever */
    333 	root->is_existing = 0;
    334 	root->is_apex = 0;
    335 	root->numlist_prev = NULL;
    336 	root->numlist_next = NULL;
    337 #ifdef NSEC3
    338 	root->nsec3 = NULL;
    339 #endif
    340 
    341 	result = (domain_table_type *) region_alloc(region,
    342 						    sizeof(domain_table_type));
    343 	result->region = region;
    344 #ifdef USE_RADIX_TREE
    345 	result->nametree = radix_tree_create(region);
    346 	root->rnode = radname_insert(result->nametree, dname_name(root->dname),
    347 		root->dname->name_size, root);
    348 #else
    349 	result->names_to_domains = rbtree_create(
    350 		region, (int (*)(const void *, const void *)) dname_compare);
    351 	rbtree_insert(result->names_to_domains, (rbnode_type *) root);
    352 #endif
    353 
    354 	result->root = root;
    355 	result->numlist_last = root;
    356 #ifdef NSEC3
    357 	result->prehash_list = NULL;
    358 #endif
    359 
    360 	return result;
    361 }
    362 
    363 int
    364 domain_table_search(domain_table_type *table,
    365 		   const dname_type   *dname,
    366 		   domain_type       **closest_match,
    367 		   domain_type       **closest_encloser)
    368 {
    369 	int exact;
    370 	uint8_t label_match_count;
    371 
    372 	assert(table);
    373 	assert(dname);
    374 	assert(closest_match);
    375 	assert(closest_encloser);
    376 
    377 #ifdef USE_RADIX_TREE
    378 	exact = radname_find_less_equal(table->nametree, dname_name(dname),
    379 		dname->name_size, (struct radnode**)closest_match);
    380 	*closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem);
    381 #else
    382 	exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_type **) closest_match);
    383 #endif
    384 	assert(*closest_match);
    385 
    386 	*closest_encloser = *closest_match;
    387 
    388 	if (!exact) {
    389 		label_match_count = dname_label_match_count(
    390 			domain_dname(*closest_encloser),
    391 			dname);
    392 		assert(label_match_count < dname->label_count);
    393 		while (label_match_count < domain_dname(*closest_encloser)->label_count) {
    394 			(*closest_encloser) = (*closest_encloser)->parent;
    395 			assert(*closest_encloser);
    396 		}
    397 	}
    398 
    399 	return exact;
    400 }
    401 
    402 domain_type *
    403 domain_table_find(domain_table_type* table,
    404 		  const dname_type* dname)
    405 {
    406 	domain_type* closest_match;
    407 	domain_type* closest_encloser;
    408 	int exact;
    409 
    410 	exact = domain_table_search(
    411 		table, dname, &closest_match, &closest_encloser);
    412 	return exact ? closest_encloser : NULL;
    413 }
    414 
    415 
    416 domain_type *
    417 domain_table_insert(domain_table_type* table,
    418 		    const dname_type* dname)
    419 {
    420 	domain_type* closest_match;
    421 	domain_type* closest_encloser;
    422 	domain_type* result;
    423 	int exact;
    424 
    425 	assert(table);
    426 	assert(dname);
    427 
    428 	exact = domain_table_search(
    429 		table, dname, &closest_match, &closest_encloser);
    430 	if (exact) {
    431 		result = closest_encloser;
    432 	} else {
    433 		assert(domain_dname(closest_encloser)->label_count < dname->label_count);
    434 
    435 		/* Insert new node(s).  */
    436 		do {
    437 			result = allocate_domain_info(table,
    438 						      dname,
    439 						      closest_encloser);
    440 #ifdef USE_RADIX_TREE
    441 			result->rnode = radname_insert(table->nametree,
    442 				dname_name(result->dname),
    443 				result->dname->name_size, result);
    444 #else
    445 			rbtree_insert(table->names_to_domains, (rbnode_type *) result);
    446 #endif
    447 
    448 			/*
    449 			 * If the newly added domain name is larger
    450 			 * than the parent's current
    451 			 * wildcard_child_closest_match but smaller or
    452 			 * equal to the wildcard domain name, update
    453 			 * the parent's wildcard_child_closest_match
    454 			 * field.
    455 			 */
    456 			if (label_compare(dname_name(domain_dname(result)),
    457 					  (const uint8_t *) "\001*") <= 0
    458 			    && dname_compare(domain_dname(result),
    459 					     domain_dname(closest_encloser->wildcard_child_closest_match)) > 0)
    460 			{
    461 				closest_encloser->wildcard_child_closest_match
    462 					= result;
    463 			}
    464 			closest_encloser = result;
    465 		} while (domain_dname(closest_encloser)->label_count < dname->label_count);
    466 	}
    467 
    468 	return result;
    469 }
    470 
    471 domain_type *domain_previous_existing_child(domain_type* domain)
    472 {
    473 	domain_type* parent = domain->parent;
    474 	domain = domain_previous(domain);
    475 	while(domain && !domain->is_existing) {
    476 		if(domain == parent) /* do not walk back above parent */
    477 			return parent;
    478 		domain = domain_previous(domain);
    479 	}
    480 	return domain;
    481 }
    482 
    483 void
    484 domain_add_rrset(domain_type* domain, rrset_type* rrset)
    485 {
    486 #if 0 	/* fast */
    487 	rrset->next = domain->rrsets;
    488 	domain->rrsets = rrset;
    489 #else
    490 	/* preserve ordering, add at end */
    491 	rrset_type** p = &domain->rrsets;
    492 	while(*p)
    493 		p = &((*p)->next);
    494 	*p = rrset;
    495 	rrset->next = 0;
    496 #endif
    497 
    498 	while (domain && !domain->is_existing) {
    499 		domain->is_existing = 1;
    500 		/* does this name in existance update the parent's
    501 		 * wildcard closest match? */
    502 		if(domain->parent
    503 		   && label_compare(dname_name(domain_dname(domain)),
    504 			(const uint8_t *) "\001*") <= 0
    505 		   && dname_compare(domain_dname(domain),
    506 		   	domain_dname(domain->parent->wildcard_child_closest_match)) > 0) {
    507 			domain->parent->wildcard_child_closest_match = domain;
    508 		}
    509 		domain = domain->parent;
    510 	}
    511 }
    512 
    513 
    514 rrset_type *
    515 domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type)
    516 {
    517 	rrset_type* result = domain->rrsets;
    518 
    519 	while (result) {
    520 		if (result->zone == zone && rrset_rrtype(result) == type) {
    521 			return result;
    522 		}
    523 		result = result->next;
    524 	}
    525 	return NULL;
    526 }
    527 
    528 rrset_type *
    529 domain_find_any_rrset(domain_type* domain, zone_type* zone)
    530 {
    531 	rrset_type* result = domain->rrsets;
    532 
    533 	while (result) {
    534 		if (result->zone == zone) {
    535 			return result;
    536 		}
    537 		result = result->next;
    538 	}
    539 	return NULL;
    540 }
    541 
    542 rrset_type *
    543 domain_find_rrset_and_prev(domain_type* domain, zone_type* zone, uint16_t type,
    544 	rrset_type** prev)
    545 {
    546 	rrset_type* result = domain->rrsets, *prevp = NULL;
    547 
    548 	while (result) {
    549 		if (result->zone == zone && rrset_rrtype(result) == type) {
    550 			*prev = prevp;
    551 			return result;
    552 		}
    553 		prevp = result;
    554 		result = result->next;
    555 	}
    556 	*prev = NULL;
    557 	return NULL;
    558 }
    559 
    560 zone_type *
    561 domain_find_zone(namedb_type* db, domain_type* domain)
    562 {
    563 	rrset_type* rrset;
    564 	while (domain) {
    565 		if(domain->is_apex) {
    566 			for (rrset = domain->rrsets; rrset; rrset = rrset->next) {
    567 				if (rrset_rrtype(rrset) == TYPE_SOA) {
    568 					return rrset->zone;
    569 				}
    570 			}
    571 			return namedb_find_zone(db, domain_dname(domain));
    572 		}
    573 		domain = domain->parent;
    574 	}
    575 	return NULL;
    576 }
    577 
    578 zone_type *
    579 domain_find_parent_zone(namedb_type* db, zone_type* zone)
    580 {
    581 	rrset_type* rrset;
    582 
    583 	assert(zone);
    584 
    585 	for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) {
    586 		if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) {
    587 			return rrset->zone;
    588 		}
    589 	}
    590 	/* the NS record in the parent zone above this zone is not present,
    591 	 * workaround to find that parent zone anyway */
    592 	if(zone->apex->parent)
    593 		return domain_find_zone(db, zone->apex->parent);
    594 	return NULL;
    595 }
    596 
    597 domain_type *
    598 domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns)
    599 {
    600 	/* return highest NS RRset in the zone that is a delegation above */
    601 	domain_type* result = NULL;
    602 	rrset_type* rrset = NULL;
    603 	while (domain && domain != zone->apex) {
    604 		rrset = domain_find_rrset(domain, zone, TYPE_NS);
    605 		if (rrset) {
    606 			*ns = rrset;
    607 			result = domain;
    608 		}
    609 		domain = domain->parent;
    610 	}
    611 
    612 	if(result)
    613 		return result;
    614 
    615 	*ns = NULL;
    616 	return NULL;
    617 }
    618 
    619 domain_type *
    620 find_dname_above(domain_type* domain, zone_type* zone)
    621 {
    622 	domain_type* d = domain->parent;
    623 	while(d && d != zone->apex) {
    624 		if(domain_find_rrset(d, zone, TYPE_DNAME))
    625 			return d;
    626 		d = d->parent;
    627 	}
    628 	return NULL;
    629 }
    630 
    631 int
    632 domain_is_glue(domain_type* domain, zone_type* zone)
    633 {
    634 	rrset_type* unused;
    635 	domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused);
    636 	return (ns_domain != NULL &&
    637 		domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL);
    638 }
    639 
    640 domain_type *
    641 domain_wildcard_child(domain_type* domain)
    642 {
    643 	domain_type* wildcard_child;
    644 
    645 	assert(domain);
    646 	assert(domain->wildcard_child_closest_match);
    647 
    648 	wildcard_child = domain->wildcard_child_closest_match;
    649 	if (wildcard_child != domain
    650 	    && label_is_wildcard(dname_name(domain_dname(wildcard_child))))
    651 	{
    652 		return wildcard_child;
    653 	} else {
    654 		return NULL;
    655 	}
    656 }
    657 
    658 int
    659 zone_is_secure(zone_type* zone)
    660 {
    661 	assert(zone);
    662 	return zone->is_secure;
    663 }
    664 
    665 uint16_t
    666 rr_rrsig_type_covered(rr_type* rr)
    667 {
    668 	uint16_t type;
    669 	assert(rr->type == TYPE_RRSIG);
    670 	assert(rr->rdlength > 2);
    671 	memcpy(&type, rr->rdata, sizeof(type));
    672 	return ntohs(type);
    673 }
    674 
    675 zone_type *
    676 namedb_find_zone(namedb_type* db, const dname_type* dname)
    677 {
    678 	struct radnode* n = radname_search(db->zonetree, dname_name(dname),
    679 		dname->name_size);
    680 	if(n) return (zone_type*)n->elem;
    681 	return NULL;
    682 }
    683 
    684 rrset_type *
    685 domain_find_non_cname_rrset(domain_type* domain, zone_type* zone)
    686 {
    687 	/* find any rrset type that is not allowed next to a CNAME */
    688 	/* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */
    689 	rrset_type *result = domain->rrsets;
    690 
    691 	while (result) {
    692 		if (result->zone == zone && /* here is the list of exceptions*/
    693 			rrset_rrtype(result) != TYPE_CNAME &&
    694 			rrset_rrtype(result) != TYPE_RRSIG &&
    695 			rrset_rrtype(result) != TYPE_NXT &&
    696 			rrset_rrtype(result) != TYPE_SIG &&
    697 			rrset_rrtype(result) != TYPE_NSEC &&
    698 			rrset_rrtype(result) != TYPE_NSEC3 ) {
    699 			return result;
    700 		}
    701 		result = result->next;
    702 	}
    703 	return NULL;
    704 }
    705 
    706 int
    707 namedb_lookup(struct namedb* db,
    708 	      const dname_type* dname,
    709 	      domain_type     **closest_match,
    710 	      domain_type     **closest_encloser)
    711 {
    712 	return domain_table_search(
    713 		db->domains, dname, closest_match, closest_encloser);
    714 }
    715 
    716 void zone_rr_iter_init(struct zone_rr_iter *iter, struct zone *zone)
    717 {
    718 	assert(iter != NULL);
    719 	assert(zone != NULL);
    720 	memset(iter, 0, sizeof(*iter));
    721 	iter->zone = zone;
    722 }
    723 
    724 rr_type *zone_rr_iter_next(struct zone_rr_iter *iter)
    725 {
    726 	assert(iter != NULL);
    727 	assert(iter->zone != NULL);
    728 
    729 	if(iter->index == -1) {
    730 		assert(iter->domain == NULL);
    731 		assert(iter->rrset == NULL);
    732 		return NULL;
    733 	} else if(iter->rrset == NULL) {
    734 		/* ensure SOA RR is returned first */
    735 		assert(iter->domain == NULL);
    736 		assert(iter->index == 0);
    737 		iter->rrset = iter->zone->soa_rrset;
    738 	}
    739 
    740 	while(iter->rrset != NULL) {
    741 		if(iter->index < iter->rrset->rr_count) {
    742 			return iter->rrset->rrs[iter->index++];
    743 		}
    744 		iter->index = 0;
    745 		if(iter->domain == NULL) {
    746 			assert(iter->rrset == iter->zone->soa_rrset);
    747 			iter->domain = iter->zone->apex;
    748 			iter->rrset = iter->domain->rrsets;
    749 		} else {
    750 			iter->rrset = iter->rrset->next;
    751 		}
    752 		/* ensure SOA RR is not returned again and RR belongs to zone */
    753 		while((iter->rrset == NULL && iter->domain != NULL) ||
    754 		      (iter->rrset != NULL && (iter->rrset == iter->zone->soa_rrset ||
    755 		                               iter->rrset->zone != iter->zone)))
    756 		{
    757 			if(iter->rrset != NULL) {
    758 				iter->rrset = iter->rrset->next;
    759 			} else {
    760 				iter->domain = domain_next(iter->domain);
    761 				if(iter->domain != NULL &&
    762 				   dname_is_subdomain(domain_dname(iter->domain),
    763 				                      domain_dname(iter->zone->apex)))
    764 				{
    765 					iter->rrset = iter->domain->rrsets;
    766 				}
    767 			}
    768 		}
    769 	}
    770 
    771 	assert(iter->rrset == NULL);
    772 	assert(iter->domain == NULL);
    773 	iter->index = -1;
    774 
    775 	return NULL;
    776 }
    777