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