1/*
2 * Copyright (C) 2004, 2005, 2007, 2009, 2010  Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 2000, 2001  Internet Software Consortium.
4 *
5 * Permission to use, copy, modify, and/or distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
16 */
17
18/* $Id: keytable.c,v 1.41 2010/06/25 23:46:51 tbox Exp $ */
19
20/*! \file */
21
22#include <config.h>
23
24#include <isc/mem.h>
25#include <isc/rwlock.h>
26#include <isc/string.h>		/* Required for HP/UX (and others?) */
27#include <isc/util.h>
28
29#include <dns/keytable.h>
30#include <dns/fixedname.h>
31#include <dns/rbt.h>
32#include <dns/result.h>
33
34static void
35free_keynode(void *node, void *arg) {
36	dns_keynode_t *keynode = node;
37	isc_mem_t *mctx = arg;
38
39	dns_keynode_detachall(mctx, &keynode);
40}
41
42isc_result_t
43dns_keytable_create(isc_mem_t *mctx, dns_keytable_t **keytablep) {
44	dns_keytable_t *keytable;
45	isc_result_t result;
46
47	/*
48	 * Create a keytable.
49	 */
50
51	REQUIRE(keytablep != NULL && *keytablep == NULL);
52
53	keytable = isc_mem_get(mctx, sizeof(*keytable));
54	if (keytable == NULL)
55		return (ISC_R_NOMEMORY);
56
57	keytable->table = NULL;
58	result = dns_rbt_create(mctx, free_keynode, mctx, &keytable->table);
59	if (result != ISC_R_SUCCESS)
60		goto cleanup_keytable;
61
62	result = isc_mutex_init(&keytable->lock);
63	if (result != ISC_R_SUCCESS)
64		goto cleanup_rbt;
65
66	result = isc_rwlock_init(&keytable->rwlock, 0, 0);
67	if (result != ISC_R_SUCCESS)
68		goto cleanup_lock;
69
70	keytable->mctx = mctx;
71	keytable->active_nodes = 0;
72	keytable->references = 1;
73	keytable->magic = KEYTABLE_MAGIC;
74	*keytablep = keytable;
75
76	return (ISC_R_SUCCESS);
77
78   cleanup_lock:
79	DESTROYLOCK(&keytable->lock);
80
81   cleanup_rbt:
82	dns_rbt_destroy(&keytable->table);
83
84   cleanup_keytable:
85	isc_mem_put(mctx, keytable, sizeof(*keytable));
86
87	return (result);
88}
89
90void
91dns_keytable_attach(dns_keytable_t *source, dns_keytable_t **targetp) {
92
93	/*
94	 * Attach *targetp to source.
95	 */
96
97	REQUIRE(VALID_KEYTABLE(source));
98	REQUIRE(targetp != NULL && *targetp == NULL);
99
100	RWLOCK(&source->rwlock, isc_rwlocktype_write);
101
102	INSIST(source->references > 0);
103	source->references++;
104	INSIST(source->references != 0);
105
106	RWUNLOCK(&source->rwlock, isc_rwlocktype_write);
107
108	*targetp = source;
109}
110
111void
112dns_keytable_detach(dns_keytable_t **keytablep) {
113	isc_boolean_t destroy = ISC_FALSE;
114	dns_keytable_t *keytable;
115
116	/*
117	 * Detach *keytablep from its keytable.
118	 */
119
120	REQUIRE(keytablep != NULL && VALID_KEYTABLE(*keytablep));
121
122	keytable = *keytablep;
123
124	RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
125
126	INSIST(keytable->references > 0);
127	keytable->references--;
128	LOCK(&keytable->lock);
129	if (keytable->references == 0 && keytable->active_nodes == 0)
130		destroy = ISC_TRUE;
131	UNLOCK(&keytable->lock);
132
133	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
134
135	if (destroy) {
136		dns_rbt_destroy(&keytable->table);
137		isc_rwlock_destroy(&keytable->rwlock);
138		DESTROYLOCK(&keytable->lock);
139		keytable->magic = 0;
140		isc_mem_put(keytable->mctx, keytable, sizeof(*keytable));
141	}
142
143	*keytablep = NULL;
144}
145
146static isc_result_t
147insert(dns_keytable_t *keytable, isc_boolean_t managed,
148       dns_name_t *keyname, dst_key_t **keyp)
149{
150	isc_result_t result;
151	dns_keynode_t *knode = NULL;
152	dns_rbtnode_t *node;
153
154	REQUIRE(keyp == NULL || *keyp != NULL);
155	REQUIRE(VALID_KEYTABLE(keytable));
156
157	result = dns_keynode_create(keytable->mctx, &knode);
158	if (result != ISC_R_SUCCESS)
159		return (result);
160
161	knode->managed = managed;
162
163	RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
164
165	node = NULL;
166	result = dns_rbt_addnode(keytable->table, keyname, &node);
167
168	if (keyp != NULL) {
169		if (result == ISC_R_EXISTS) {
170			/* Key already in table? */
171			dns_keynode_t *k;
172			for (k = node->data; k != NULL; k = k->next) {
173				if (k->key == NULL) {
174					k->key = *keyp;
175					break;
176				}
177				if (dst_key_compare(k->key, *keyp) == ISC_TRUE)
178					break;
179			}
180
181			if (k == NULL)
182				result = ISC_R_SUCCESS;
183			else
184				dst_key_free(keyp);
185		}
186
187		if (result == ISC_R_SUCCESS) {
188			knode->key = *keyp;
189			knode->next = node->data;
190			*keyp = NULL;
191		}
192	}
193
194	if (result == ISC_R_SUCCESS) {
195		node->data = knode;
196		knode = NULL;
197	}
198
199	/* Key was already there?  That's the same as a success */
200	if (result == ISC_R_EXISTS)
201		result = ISC_R_SUCCESS;
202
203	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
204
205	if (knode != NULL)
206		dns_keynode_detach(keytable->mctx, &knode);
207
208	return (result);
209}
210
211isc_result_t
212dns_keytable_add(dns_keytable_t *keytable, isc_boolean_t managed,
213		 dst_key_t **keyp)
214{
215	REQUIRE(keyp != NULL && *keyp != NULL);
216	return (insert(keytable, managed, dst_key_name(*keyp), keyp));
217}
218
219isc_result_t
220dns_keytable_marksecure(dns_keytable_t *keytable, dns_name_t *name) {
221	return (insert(keytable, ISC_TRUE, name, NULL));
222}
223
224isc_result_t
225dns_keytable_delete(dns_keytable_t *keytable, dns_name_t *keyname) {
226	isc_result_t result;
227	dns_rbtnode_t *node = NULL;
228
229	REQUIRE(VALID_KEYTABLE(keytable));
230	REQUIRE(keyname != NULL);
231
232	RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
233	result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
234				  DNS_RBTFIND_NOOPTIONS, NULL, NULL);
235	if (result == ISC_R_SUCCESS) {
236		if (node->data != NULL)
237			result = dns_rbt_deletenode(keytable->table,
238						    node, ISC_FALSE);
239		else
240			result = ISC_R_NOTFOUND;
241	} else if (result == DNS_R_PARTIALMATCH)
242		result = ISC_R_NOTFOUND;
243	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
244
245	return (result);
246}
247
248isc_result_t
249dns_keytable_deletekeynode(dns_keytable_t *keytable, dst_key_t *dstkey) {
250	isc_result_t result;
251	dns_name_t *keyname;
252	dns_rbtnode_t *node = NULL;
253	dns_keynode_t *knode = NULL, **kprev = NULL;
254
255	REQUIRE(VALID_KEYTABLE(keytable));
256	REQUIRE(dstkey != NULL);
257
258	keyname = dst_key_name(dstkey);
259
260	RWLOCK(&keytable->rwlock, isc_rwlocktype_write);
261	result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
262				  DNS_RBTFIND_NOOPTIONS, NULL, NULL);
263
264	if (result == DNS_R_PARTIALMATCH)
265		result = ISC_R_NOTFOUND;
266	if (result != ISC_R_SUCCESS)
267		goto finish;
268
269	if (node->data == NULL) {
270		result = ISC_R_NOTFOUND;
271		goto finish;
272	}
273
274	knode = node->data;
275	if (knode->next == NULL &&
276	    (knode->key == NULL ||
277	     dst_key_compare(knode->key, dstkey) == ISC_TRUE)) {
278		result = dns_rbt_deletenode(keytable->table, node, ISC_FALSE);
279		goto finish;
280	}
281
282	kprev = (dns_keynode_t **) &node->data;
283	while (knode != NULL) {
284		if (dst_key_compare(knode->key, dstkey) == ISC_TRUE)
285			break;
286		kprev = &knode->next;
287		knode = knode->next;
288	}
289
290	if (knode != NULL) {
291		if (knode->key != NULL)
292			dst_key_free(&knode->key);
293		/*
294		 * This is equivalent to:
295		 * dns_keynode_attach(knode->next, &tmp);
296		 * dns_keynode_detach(kprev);
297		 * dns_keynode_attach(tmp, &kprev);
298		 * dns_keynode_detach(&tmp);
299		 */
300		*kprev = knode->next;
301		knode->next = NULL;
302		dns_keynode_detach(keytable->mctx, &knode);
303	} else
304		result = DNS_R_PARTIALMATCH;
305  finish:
306	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_write);
307	return (result);
308}
309
310isc_result_t
311dns_keytable_find(dns_keytable_t *keytable, dns_name_t *keyname,
312		  dns_keynode_t **keynodep)
313{
314	isc_result_t result;
315	dns_rbtnode_t *node = NULL;
316
317	REQUIRE(VALID_KEYTABLE(keytable));
318	REQUIRE(keyname != NULL);
319	REQUIRE(keynodep != NULL && *keynodep == NULL);
320
321	RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
322	result = dns_rbt_findnode(keytable->table, keyname, NULL, &node, NULL,
323				  DNS_RBTFIND_NOOPTIONS, NULL, NULL);
324	if (result == ISC_R_SUCCESS) {
325		if (node->data != NULL) {
326			LOCK(&keytable->lock);
327			keytable->active_nodes++;
328			UNLOCK(&keytable->lock);
329			dns_keynode_attach(node->data, keynodep);
330		} else
331			result = ISC_R_NOTFOUND;
332	} else if (result == DNS_R_PARTIALMATCH)
333		result = ISC_R_NOTFOUND;
334	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
335
336	return (result);
337}
338
339isc_result_t
340dns_keytable_nextkeynode(dns_keytable_t *keytable, dns_keynode_t *keynode,
341			 dns_keynode_t **nextnodep)
342{
343	/*
344	 * Return the next key after 'keynode', regardless of
345	 * properties.
346	 */
347
348	REQUIRE(VALID_KEYTABLE(keytable));
349	REQUIRE(VALID_KEYNODE(keynode));
350	REQUIRE(nextnodep != NULL && *nextnodep == NULL);
351
352	if (keynode->next == NULL)
353		return (ISC_R_NOTFOUND);
354
355	dns_keynode_attach(keynode->next, nextnodep);
356	LOCK(&keytable->lock);
357	keytable->active_nodes++;
358	UNLOCK(&keytable->lock);
359
360	return (ISC_R_SUCCESS);
361}
362
363isc_result_t
364dns_keytable_findkeynode(dns_keytable_t *keytable, dns_name_t *name,
365			 dns_secalg_t algorithm, dns_keytag_t tag,
366			 dns_keynode_t **keynodep)
367{
368	isc_result_t result;
369	dns_keynode_t *knode;
370	void *data;
371
372	/*
373	 * Search for a key named 'name', matching 'algorithm' and 'tag' in
374	 * 'keytable'.
375	 */
376
377	REQUIRE(VALID_KEYTABLE(keytable));
378	REQUIRE(dns_name_isabsolute(name));
379	REQUIRE(keynodep != NULL && *keynodep == NULL);
380
381	RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
382
383	/*
384	 * Note we don't want the DNS_R_PARTIALMATCH from dns_rbt_findname()
385	 * as that indicates that 'name' was not found.
386	 *
387	 * DNS_R_PARTIALMATCH indicates that the name was found but we
388	 * didn't get a match on algorithm and key id arguments.
389	 */
390	knode = NULL;
391	data = NULL;
392	result = dns_rbt_findname(keytable->table, name, 0, NULL, &data);
393
394	if (result == ISC_R_SUCCESS) {
395		INSIST(data != NULL);
396		for (knode = data; knode != NULL; knode = knode->next) {
397			if (knode->key == NULL) {
398				knode = NULL;
399				break;
400			}
401			if (algorithm == dst_key_alg(knode->key)
402			    && tag == dst_key_id(knode->key))
403				break;
404		}
405		if (knode != NULL) {
406			LOCK(&keytable->lock);
407			keytable->active_nodes++;
408			UNLOCK(&keytable->lock);
409			dns_keynode_attach(knode, keynodep);
410		} else
411			result = DNS_R_PARTIALMATCH;
412	} else if (result == DNS_R_PARTIALMATCH)
413		result = ISC_R_NOTFOUND;
414
415	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
416
417	return (result);
418}
419
420isc_result_t
421dns_keytable_findnextkeynode(dns_keytable_t *keytable, dns_keynode_t *keynode,
422			     dns_keynode_t **nextnodep)
423{
424	isc_result_t result;
425	dns_keynode_t *knode;
426
427	/*
428	 * Search for the next key with the same properties as 'keynode' in
429	 * 'keytable'.
430	 */
431
432	REQUIRE(VALID_KEYTABLE(keytable));
433	REQUIRE(VALID_KEYNODE(keynode));
434	REQUIRE(nextnodep != NULL && *nextnodep == NULL);
435
436	for (knode = keynode->next; knode != NULL; knode = knode->next) {
437		if (knode->key == NULL) {
438			knode = NULL;
439			break;
440		}
441		if (dst_key_alg(keynode->key) == dst_key_alg(knode->key) &&
442		    dst_key_id(keynode->key) == dst_key_id(knode->key))
443			break;
444	}
445	if (knode != NULL) {
446		LOCK(&keytable->lock);
447		keytable->active_nodes++;
448		UNLOCK(&keytable->lock);
449		result = ISC_R_SUCCESS;
450		dns_keynode_attach(knode, nextnodep);
451	} else
452		result = ISC_R_NOTFOUND;
453
454	return (result);
455}
456
457isc_result_t
458dns_keytable_finddeepestmatch(dns_keytable_t *keytable, dns_name_t *name,
459			      dns_name_t *foundname)
460{
461	isc_result_t result;
462	void *data;
463
464	/*
465	 * Search for the deepest match in 'keytable'.
466	 */
467
468	REQUIRE(VALID_KEYTABLE(keytable));
469	REQUIRE(dns_name_isabsolute(name));
470	REQUIRE(foundname != NULL);
471
472	RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
473
474	data = NULL;
475	result = dns_rbt_findname(keytable->table, name, 0, foundname, &data);
476
477	if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH)
478		result = ISC_R_SUCCESS;
479
480	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
481
482	return (result);
483}
484
485void
486dns_keytable_attachkeynode(dns_keytable_t *keytable, dns_keynode_t *source,
487			   dns_keynode_t **target)
488{
489	/*
490	 * Give back a keynode found via dns_keytable_findkeynode().
491	 */
492
493	REQUIRE(VALID_KEYTABLE(keytable));
494	REQUIRE(VALID_KEYNODE(source));
495	REQUIRE(target != NULL && *target == NULL);
496
497	LOCK(&keytable->lock);
498	keytable->active_nodes++;
499	UNLOCK(&keytable->lock);
500
501	dns_keynode_attach(source, target);
502}
503
504void
505dns_keytable_detachkeynode(dns_keytable_t *keytable, dns_keynode_t **keynodep)
506{
507	/*
508	 * Give back a keynode found via dns_keytable_findkeynode().
509	 */
510
511	REQUIRE(VALID_KEYTABLE(keytable));
512	REQUIRE(keynodep != NULL && VALID_KEYNODE(*keynodep));
513
514	LOCK(&keytable->lock);
515	INSIST(keytable->active_nodes > 0);
516	keytable->active_nodes--;
517	UNLOCK(&keytable->lock);
518
519	dns_keynode_detach(keytable->mctx, keynodep);
520}
521
522isc_result_t
523dns_keytable_issecuredomain(dns_keytable_t *keytable, dns_name_t *name,
524			    isc_boolean_t *wantdnssecp)
525{
526	isc_result_t result;
527	void *data;
528
529	/*
530	 * Is 'name' at or beneath a trusted key?
531	 */
532
533	REQUIRE(VALID_KEYTABLE(keytable));
534	REQUIRE(dns_name_isabsolute(name));
535	REQUIRE(wantdnssecp != NULL);
536
537	RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
538
539	data = NULL;
540	result = dns_rbt_findname(keytable->table, name, 0, NULL, &data);
541
542	if (result == ISC_R_SUCCESS || result == DNS_R_PARTIALMATCH) {
543		INSIST(data != NULL);
544		*wantdnssecp = ISC_TRUE;
545		result = ISC_R_SUCCESS;
546	} else if (result == ISC_R_NOTFOUND) {
547		*wantdnssecp = ISC_FALSE;
548		result = ISC_R_SUCCESS;
549	}
550
551	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
552
553	return (result);
554}
555
556isc_result_t
557dns_keytable_dump(dns_keytable_t *keytable, FILE *fp)
558{
559	isc_result_t result;
560	dns_keynode_t *knode;
561	dns_rbtnode_t *node;
562	dns_rbtnodechain_t chain;
563
564	REQUIRE(VALID_KEYTABLE(keytable));
565
566	RWLOCK(&keytable->rwlock, isc_rwlocktype_read);
567	dns_rbtnodechain_init(&chain, keytable->mctx);
568	result = dns_rbtnodechain_first(&chain, keytable->table, NULL, NULL);
569	if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN)
570		goto cleanup;
571	for (;;) {
572		char pbuf[DST_KEY_FORMATSIZE];
573
574		dns_rbtnodechain_current(&chain, NULL, NULL, &node);
575		for (knode = node->data; knode != NULL; knode = knode->next) {
576			dst_key_format(knode->key, pbuf, sizeof(pbuf));
577			fprintf(fp, "%s ; %s\n", pbuf,
578				knode->managed ? "managed" : "trusted");
579		}
580		result = dns_rbtnodechain_next(&chain, NULL, NULL);
581		if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN) {
582			if (result == ISC_R_NOMORE)
583				result = ISC_R_SUCCESS;
584			break;
585		}
586	}
587
588   cleanup:
589	dns_rbtnodechain_invalidate(&chain);
590	RWUNLOCK(&keytable->rwlock, isc_rwlocktype_read);
591	return (result);
592}
593
594dst_key_t *
595dns_keynode_key(dns_keynode_t *keynode) {
596
597	/*
598	 * Get the DST key associated with keynode.
599	 */
600
601	REQUIRE(VALID_KEYNODE(keynode));
602
603	return (keynode->key);
604}
605
606isc_boolean_t
607dns_keynode_managed(dns_keynode_t *keynode) {
608	/*
609	 * Is this a managed key?
610	 */
611	REQUIRE(VALID_KEYNODE(keynode));
612
613	return (keynode->managed);
614}
615
616isc_result_t
617dns_keynode_create(isc_mem_t *mctx, dns_keynode_t **target) {
618	isc_result_t result;
619	dns_keynode_t *knode = NULL;
620
621	REQUIRE(target != NULL && *target == NULL);
622
623	knode = isc_mem_get(mctx, sizeof(dns_keynode_t));
624	if (knode == NULL)
625		return (ISC_R_NOMEMORY);
626
627	knode->magic = KEYNODE_MAGIC;
628	knode->managed = ISC_FALSE;
629	knode->key = NULL;
630	knode->next = NULL;
631
632	result = isc_refcount_init(&knode->refcount, 1);
633	if (result != ISC_R_SUCCESS)
634		return (result);
635
636	*target = knode;
637	return (ISC_R_SUCCESS);
638}
639
640void
641dns_keynode_attach(dns_keynode_t *source, dns_keynode_t **target) {
642	REQUIRE(VALID_KEYNODE(source));
643	isc_refcount_increment(&source->refcount, NULL);
644	*target = source;
645}
646
647void
648dns_keynode_detach(isc_mem_t *mctx, dns_keynode_t **keynode) {
649	unsigned int refs;
650	dns_keynode_t *node = *keynode;
651	REQUIRE(VALID_KEYNODE(node));
652	isc_refcount_decrement(&node->refcount, &refs);
653	if (refs == 0) {
654		if (node->key != NULL)
655			dst_key_free(&node->key);
656		isc_refcount_destroy(&node->refcount);
657		isc_mem_put(mctx, node, sizeof(dns_keynode_t));
658	}
659	*keynode = NULL;
660}
661
662void
663dns_keynode_detachall(isc_mem_t *mctx, dns_keynode_t **keynode) {
664	dns_keynode_t *next = NULL, *node = *keynode;
665	REQUIRE(VALID_KEYNODE(node));
666	while (node != NULL) {
667		next = node->next;
668		dns_keynode_detach(mctx, &node);
669		node = next;
670	}
671	*keynode = NULL;
672}
673