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