1/*
2 * Copyright (C) 2004, 2005, 2007-2009, 2011, 2012  Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 2000-2003  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$ */
19
20/*! \file */
21
22#include <config.h>
23
24#include <stdlib.h>
25
26#include <isc/buffer.h>
27#include <isc/file.h>
28#include <isc/mem.h>
29#include <isc/string.h>
30#include <isc/util.h>
31
32#include <dns/db.h>
33#include <dns/diff.h>
34#include <dns/log.h>
35#include <dns/rdataclass.h>
36#include <dns/rdatalist.h>
37#include <dns/rdataset.h>
38#include <dns/rdatastruct.h>
39#include <dns/rdatatype.h>
40#include <dns/result.h>
41
42#define CHECK(op) \
43	do { result = (op);					\
44		if (result != ISC_R_SUCCESS) goto failure;	\
45	} while (0)
46
47#define DIFF_COMMON_LOGARGS \
48	dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF
49
50static dns_rdatatype_t
51rdata_covers(dns_rdata_t *rdata) {
52	return (rdata->type == dns_rdatatype_rrsig ?
53		dns_rdata_covers(rdata) : 0);
54}
55
56isc_result_t
57dns_difftuple_create(isc_mem_t *mctx,
58		     dns_diffop_t op, dns_name_t *name, dns_ttl_t ttl,
59		     dns_rdata_t *rdata, dns_difftuple_t **tp)
60{
61	dns_difftuple_t *t;
62	unsigned int size;
63	unsigned char *datap;
64
65	REQUIRE(tp != NULL && *tp == NULL);
66
67	/*
68	 * Create a new tuple.  The variable-size wire-format name data and
69	 * rdata immediately follow the dns_difftuple_t structure
70	 * in memory.
71	 */
72	size = sizeof(*t) + name->length + rdata->length;
73	t = isc_mem_allocate(mctx, size);
74	if (t == NULL)
75		return (ISC_R_NOMEMORY);
76	t->mctx = mctx;
77	t->op = op;
78
79	datap = (unsigned char *)(t + 1);
80
81	memcpy(datap, name->ndata, name->length);
82	dns_name_init(&t->name, NULL);
83	dns_name_clone(name, &t->name);
84	t->name.ndata = datap;
85	datap += name->length;
86
87	t->ttl = ttl;
88
89	memcpy(datap, rdata->data, rdata->length);
90	dns_rdata_init(&t->rdata);
91	dns_rdata_clone(rdata, &t->rdata);
92	t->rdata.data = datap;
93	datap += rdata->length;
94
95	ISC_LINK_INIT(&t->rdata, link);
96	ISC_LINK_INIT(t, link);
97	t->magic = DNS_DIFFTUPLE_MAGIC;
98
99	INSIST(datap == (unsigned char *)t + size);
100
101	*tp = t;
102	return (ISC_R_SUCCESS);
103}
104
105void
106dns_difftuple_free(dns_difftuple_t **tp) {
107	dns_difftuple_t *t = *tp;
108	REQUIRE(DNS_DIFFTUPLE_VALID(t));
109	dns_name_invalidate(&t->name);
110	t->magic = 0;
111	isc_mem_free(t->mctx, t);
112	*tp = NULL;
113}
114
115isc_result_t
116dns_difftuple_copy(dns_difftuple_t *orig, dns_difftuple_t **copyp) {
117	return (dns_difftuple_create(orig->mctx, orig->op, &orig->name,
118				     orig->ttl, &orig->rdata, copyp));
119}
120
121void
122dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) {
123	diff->mctx = mctx;
124	diff->resign = 0;
125	ISC_LIST_INIT(diff->tuples);
126	diff->magic = DNS_DIFF_MAGIC;
127}
128
129void
130dns_diff_clear(dns_diff_t *diff) {
131	dns_difftuple_t *t;
132	REQUIRE(DNS_DIFF_VALID(diff));
133	while ((t = ISC_LIST_HEAD(diff->tuples)) != NULL) {
134		ISC_LIST_UNLINK(diff->tuples, t, link);
135		dns_difftuple_free(&t);
136	}
137	ENSURE(ISC_LIST_EMPTY(diff->tuples));
138}
139
140void
141dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep)
142{
143	ISC_LIST_APPEND(diff->tuples, *tuplep, link);
144	*tuplep = NULL;
145}
146
147/* XXX this is O(N) */
148
149void
150dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep)
151{
152	dns_difftuple_t *ot, *next_ot;
153
154	REQUIRE(DNS_DIFF_VALID(diff));
155	REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep));
156
157	/*
158	 * Look for an existing tuple with the same owner name,
159	 * rdata, and TTL.   If we are doing an addition and find a
160	 * deletion or vice versa, remove both the old and the
161	 * new tuple since they cancel each other out (assuming
162	 * that we never delete nonexistent data or add existing
163	 * data).
164	 *
165	 * If we find an old update of the same kind as
166	 * the one we are doing, there must be a programming
167	 * error.  We report it but try to continue anyway.
168	 */
169	for (ot = ISC_LIST_HEAD(diff->tuples); ot != NULL;
170	     ot = next_ot)
171	{
172		next_ot = ISC_LIST_NEXT(ot, link);
173		if (dns_name_equal(&ot->name, &(*tuplep)->name) &&
174		    dns_rdata_compare(&ot->rdata, &(*tuplep)->rdata) == 0 &&
175		    ot->ttl == (*tuplep)->ttl)
176		{
177			ISC_LIST_UNLINK(diff->tuples, ot, link);
178			if ((*tuplep)->op == ot->op) {
179				UNEXPECTED_ERROR(__FILE__, __LINE__,
180					 "unexpected non-minimal diff");
181			} else {
182				dns_difftuple_free(tuplep);
183			}
184			dns_difftuple_free(&ot);
185			break;
186		}
187	}
188
189	if (*tuplep != NULL) {
190		ISC_LIST_APPEND(diff->tuples, *tuplep, link);
191		*tuplep = NULL;
192	}
193
194	ENSURE(*tuplep == NULL);
195}
196
197static isc_stdtime_t
198setresign(dns_rdataset_t *modified, isc_uint32_t delta) {
199	dns_rdata_t rdata = DNS_RDATA_INIT;
200	dns_rdata_rrsig_t sig;
201	isc_stdtime_t when;
202	isc_result_t result;
203
204	result = dns_rdataset_first(modified);
205	INSIST(result == ISC_R_SUCCESS);
206	dns_rdataset_current(modified, &rdata);
207	(void)dns_rdata_tostruct(&rdata, &sig, NULL);
208	if ((rdata.flags & DNS_RDATA_OFFLINE) != 0)
209		when = 0;
210	else
211		when = sig.timeexpire - delta;
212	dns_rdata_reset(&rdata);
213
214	result = dns_rdataset_next(modified);
215	while (result == ISC_R_SUCCESS) {
216		dns_rdataset_current(modified, &rdata);
217		(void)dns_rdata_tostruct(&rdata, &sig, NULL);
218		if ((rdata.flags & DNS_RDATA_OFFLINE) != 0) {
219			goto next_rr;
220		}
221		if (when == 0 || sig.timeexpire - delta < when)
222			when = sig.timeexpire - delta;
223 next_rr:
224		dns_rdata_reset(&rdata);
225		result = dns_rdataset_next(modified);
226	}
227	INSIST(result == ISC_R_NOMORE);
228	return (when);
229}
230
231static isc_result_t
232diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver,
233	   isc_boolean_t warn)
234{
235	dns_difftuple_t *t;
236	dns_dbnode_t *node = NULL;
237	isc_result_t result;
238	char namebuf[DNS_NAME_FORMATSIZE];
239	char typebuf[DNS_RDATATYPE_FORMATSIZE];
240	char classbuf[DNS_RDATACLASS_FORMATSIZE];
241
242	REQUIRE(DNS_DIFF_VALID(diff));
243	REQUIRE(DNS_DB_VALID(db));
244
245	t = ISC_LIST_HEAD(diff->tuples);
246	while (t != NULL) {
247		dns_name_t *name;
248
249		INSIST(node == NULL);
250		name = &t->name;
251		/*
252		 * Find the node.
253		 * We create the node if it does not exist.
254		 * This will cause an empty node to be created if the diff
255		 * contains a deletion of an RR at a nonexistent name,
256		 * but such diffs should never be created in the first
257		 * place.
258		 */
259
260		while (t != NULL && dns_name_equal(&t->name, name)) {
261			dns_rdatatype_t type, covers;
262			dns_diffop_t op;
263			dns_rdatalist_t rdl;
264			dns_rdataset_t rds;
265			dns_rdataset_t ardataset;
266			dns_rdataset_t *modified = NULL;
267
268			op = t->op;
269			type = t->rdata.type;
270			covers = rdata_covers(&t->rdata);
271
272			/*
273			 * Collect a contiguous set of updates with
274			 * the same operation (add/delete) and RR type
275			 * into a single rdatalist so that the
276			 * database rrset merging/subtraction code
277			 * can work more efficiently than if each
278			 * RR were merged into / subtracted from
279			 * the database separately.
280			 *
281			 * This is done by linking rdata structures from the
282			 * diff into "rdatalist".  This uses the rdata link
283			 * field, not the diff link field, so the structure
284			 * of the diff itself is not affected.
285			 */
286
287			rdl.type = type;
288			rdl.covers = covers;
289			rdl.rdclass = t->rdata.rdclass;
290			rdl.ttl = t->ttl;
291			ISC_LIST_INIT(rdl.rdata);
292			ISC_LINK_INIT(&rdl, link);
293
294			node = NULL;
295			if (type != dns_rdatatype_nsec3 &&
296			    covers != dns_rdatatype_nsec3)
297				CHECK(dns_db_findnode(db, name, ISC_TRUE,
298						      &node));
299			else
300				CHECK(dns_db_findnsec3node(db, name, ISC_TRUE,
301							   &node));
302
303			while (t != NULL &&
304			       dns_name_equal(&t->name, name) &&
305			       t->op == op &&
306			       t->rdata.type == type &&
307			       rdata_covers(&t->rdata) == covers)
308			{
309				dns_name_format(name, namebuf, sizeof(namebuf));
310				dns_rdatatype_format(t->rdata.type, typebuf,
311						     sizeof(typebuf));
312				dns_rdataclass_format(t->rdata.rdclass,
313						      classbuf,
314						      sizeof(classbuf));
315				if (t->ttl != rdl.ttl && warn)
316					isc_log_write(DIFF_COMMON_LOGARGS,
317						ISC_LOG_WARNING,
318						"'%s/%s/%s': TTL differs in "
319						"rdataset, adjusting "
320						"%lu -> %lu",
321						namebuf, typebuf, classbuf,
322						(unsigned long) t->ttl,
323						(unsigned long) rdl.ttl);
324				ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
325				t = ISC_LIST_NEXT(t, link);
326			}
327
328			/*
329			 * Convert the rdatalist into a rdataset.
330			 */
331			dns_rdataset_init(&rds);
332			CHECK(dns_rdatalist_tordataset(&rdl, &rds));
333			if (rds.type == dns_rdatatype_rrsig)
334				switch (op) {
335				case DNS_DIFFOP_ADDRESIGN:
336				case DNS_DIFFOP_DELRESIGN:
337					modified = &ardataset;
338					dns_rdataset_init(modified);
339					break;
340				default:
341					break;
342				}
343			rds.trust = dns_trust_ultimate;
344
345			/*
346			 * Merge the rdataset into the database.
347			 */
348			switch (op) {
349			case DNS_DIFFOP_ADD:
350			case DNS_DIFFOP_ADDRESIGN:
351				result = dns_db_addrdataset(db, node, ver,
352							    0, &rds,
353							    DNS_DBADD_MERGE|
354							    DNS_DBADD_EXACT|
355							    DNS_DBADD_EXACTTTL,
356							    modified);
357				break;
358			case DNS_DIFFOP_DEL:
359			case DNS_DIFFOP_DELRESIGN:
360				result = dns_db_subtractrdataset(db, node, ver,
361							       &rds,
362							       DNS_DBSUB_EXACT,
363							       modified);
364				break;
365			default:
366				INSIST(0);
367			}
368
369			if (result == ISC_R_SUCCESS) {
370				if (modified != NULL) {
371					isc_stdtime_t resign;
372					resign = setresign(modified,
373							   diff->resign);
374					dns_db_setsigningtime(db, modified,
375							      resign);
376					if (diff->resign == 0 &&
377					    (op == DNS_DIFFOP_ADDRESIGN ||
378					     op == DNS_DIFFOP_DELRESIGN))
379						isc_log_write(
380							DIFF_COMMON_LOGARGS,
381							ISC_LOG_WARNING,
382							"resign requested "
383							"with 0 resign "
384							"interval");
385				}
386			} else if (result == DNS_R_UNCHANGED) {
387				/*
388				 * This will not happen when executing a
389				 * dynamic update, because that code will
390				 * generate strictly minimal diffs.
391				 * It may happen when receiving an IXFR
392				 * from a server that is not as careful.
393				 * Issue a warning and continue.
394				 */
395				if (warn) {
396					char classbuf[DNS_RDATATYPE_FORMATSIZE];
397					char namebuf[DNS_NAME_FORMATSIZE];
398
399					dns_name_format(dns_db_origin(db),
400							namebuf,
401							sizeof(namebuf));
402					dns_rdataclass_format(dns_db_class(db),
403							      classbuf,
404							      sizeof(classbuf));
405					isc_log_write(DIFF_COMMON_LOGARGS,
406						      ISC_LOG_WARNING,
407						      "%s/%s: dns_diff_apply: "
408						      "update with no effect",
409						      namebuf, classbuf);
410				}
411			} else if (result == DNS_R_NXRRSET) {
412				/*
413				 * OK.
414				 */
415			} else {
416				if (modified != NULL &&
417				    dns_rdataset_isassociated(modified))
418					dns_rdataset_disassociate(modified);
419				CHECK(result);
420			}
421			dns_db_detachnode(db, &node);
422			if (modified != NULL &&
423			    dns_rdataset_isassociated(modified))
424				dns_rdataset_disassociate(modified);
425		}
426	}
427	return (ISC_R_SUCCESS);
428
429 failure:
430	if (node != NULL)
431		dns_db_detachnode(db, &node);
432	return (result);
433}
434
435isc_result_t
436dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
437	return (diff_apply(diff, db, ver, ISC_TRUE));
438}
439
440isc_result_t
441dns_diff_applysilently(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
442	return (diff_apply(diff, db, ver, ISC_FALSE));
443}
444
445/* XXX this duplicates lots of code in diff_apply(). */
446
447isc_result_t
448dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc,
449	      void *add_private)
450{
451	dns_difftuple_t *t;
452	isc_result_t result;
453
454	REQUIRE(DNS_DIFF_VALID(diff));
455
456	t = ISC_LIST_HEAD(diff->tuples);
457	while (t != NULL) {
458		dns_name_t *name;
459
460		name = &t->name;
461		while (t != NULL && dns_name_equal(&t->name, name)) {
462			dns_rdatatype_t type, covers;
463			dns_diffop_t op;
464			dns_rdatalist_t rdl;
465			dns_rdataset_t rds;
466
467			op = t->op;
468			type = t->rdata.type;
469			covers = rdata_covers(&t->rdata);
470
471			rdl.type = type;
472			rdl.covers = covers;
473			rdl.rdclass = t->rdata.rdclass;
474			rdl.ttl = t->ttl;
475			ISC_LIST_INIT(rdl.rdata);
476			ISC_LINK_INIT(&rdl, link);
477
478			while (t != NULL && dns_name_equal(&t->name, name) &&
479			       t->op == op && t->rdata.type == type &&
480			       rdata_covers(&t->rdata) == covers)
481			{
482				ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
483				t = ISC_LIST_NEXT(t, link);
484			}
485
486			/*
487			 * Convert the rdatalist into a rdataset.
488			 */
489			dns_rdataset_init(&rds);
490			CHECK(dns_rdatalist_tordataset(&rdl, &rds));
491			rds.trust = dns_trust_ultimate;
492
493			INSIST(op == DNS_DIFFOP_ADD);
494			result = (*addfunc)(add_private, name, &rds);
495			if (result == DNS_R_UNCHANGED) {
496				isc_log_write(DIFF_COMMON_LOGARGS,
497					      ISC_LOG_WARNING,
498					      "dns_diff_load: "
499					      "update with no effect");
500			} else if (result == ISC_R_SUCCESS ||
501				   result == DNS_R_NXRRSET) {
502				/*
503				 * OK.
504				 */
505			} else {
506				CHECK(result);
507			}
508		}
509	}
510	result = ISC_R_SUCCESS;
511 failure:
512	return (result);
513}
514
515/*
516 * XXX uses qsort(); a merge sort would be more natural for lists,
517 * and perhaps safer wrt thread stack overflow.
518 */
519isc_result_t
520dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) {
521	unsigned int length = 0;
522	unsigned int i;
523	dns_difftuple_t **v;
524	dns_difftuple_t *p;
525	REQUIRE(DNS_DIFF_VALID(diff));
526
527	for (p = ISC_LIST_HEAD(diff->tuples);
528	     p != NULL;
529	     p = ISC_LIST_NEXT(p, link))
530		length++;
531	if (length == 0)
532		return (ISC_R_SUCCESS);
533	v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *));
534	if (v == NULL)
535		return (ISC_R_NOMEMORY);
536	for (i = 0; i < length; i++) {
537		p = ISC_LIST_HEAD(diff->tuples);
538		v[i] = p;
539		ISC_LIST_UNLINK(diff->tuples, p, link);
540	}
541	INSIST(ISC_LIST_HEAD(diff->tuples) == NULL);
542	qsort(v, length, sizeof(v[0]), compare);
543	for (i = 0; i < length; i++) {
544		ISC_LIST_APPEND(diff->tuples, v[i], link);
545	}
546	isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *));
547	return (ISC_R_SUCCESS);
548}
549
550
551/*
552 * Create an rdataset containing the single RR of the given
553 * tuple.  The caller must allocate the rdata, rdataset and
554 * an rdatalist structure for it to refer to.
555 */
556
557static isc_result_t
558diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata,
559		      dns_rdatalist_t *rdl, dns_rdataset_t *rds)
560{
561	REQUIRE(DNS_DIFFTUPLE_VALID(t));
562	REQUIRE(rdl != NULL);
563	REQUIRE(rds != NULL);
564
565	rdl->type = t->rdata.type;
566	rdl->rdclass = t->rdata.rdclass;
567	rdl->ttl = t->ttl;
568	ISC_LIST_INIT(rdl->rdata);
569	ISC_LINK_INIT(rdl, link);
570	dns_rdataset_init(rds);
571	ISC_LINK_INIT(rdata, link);
572	dns_rdata_clone(&t->rdata, rdata);
573	ISC_LIST_APPEND(rdl->rdata, rdata, link);
574	return (dns_rdatalist_tordataset(rdl, rds));
575}
576
577isc_result_t
578dns_diff_print(dns_diff_t *diff, FILE *file) {
579	isc_result_t result;
580	dns_difftuple_t *t;
581	char *mem = NULL;
582	unsigned int size = 2048;
583	const char *op = NULL;
584
585	REQUIRE(DNS_DIFF_VALID(diff));
586
587	mem = isc_mem_get(diff->mctx, size);
588	if (mem == NULL)
589		return (ISC_R_NOMEMORY);
590
591	for (t = ISC_LIST_HEAD(diff->tuples); t != NULL;
592	     t = ISC_LIST_NEXT(t, link))
593	{
594		isc_buffer_t buf;
595		isc_region_t r;
596
597		dns_rdatalist_t rdl;
598		dns_rdataset_t rds;
599		dns_rdata_t rd = DNS_RDATA_INIT;
600
601		result = diff_tuple_tordataset(t, &rd, &rdl, &rds);
602		if (result != ISC_R_SUCCESS) {
603			UNEXPECTED_ERROR(__FILE__, __LINE__,
604					 "diff_tuple_tordataset failed: %s",
605					 dns_result_totext(result));
606			result =  ISC_R_UNEXPECTED;
607			goto cleanup;
608		}
609 again:
610		isc_buffer_init(&buf, mem, size);
611		result = dns_rdataset_totext(&rds, &t->name,
612					     ISC_FALSE, ISC_FALSE, &buf);
613
614		if (result == ISC_R_NOSPACE) {
615			isc_mem_put(diff->mctx, mem, size);
616			size += 1024;
617			mem = isc_mem_get(diff->mctx, size);
618			if (mem == NULL) {
619				result = ISC_R_NOMEMORY;
620				goto cleanup;
621			}
622			goto again;
623		}
624
625		if (result != ISC_R_SUCCESS)
626			goto cleanup;
627		/*
628		 * Get rid of final newline.
629		 */
630		INSIST(buf.used >= 1 &&
631		       ((char *) buf.base)[buf.used-1] == '\n');
632		buf.used--;
633
634		isc_buffer_usedregion(&buf, &r);
635		switch (t->op) {
636		case DNS_DIFFOP_EXISTS: op = "exists"; break;
637		case DNS_DIFFOP_ADD: op = "add"; break;
638		case DNS_DIFFOP_DEL: op = "del"; break;
639		case DNS_DIFFOP_ADDRESIGN: op = "add re-sign"; break;
640		case DNS_DIFFOP_DELRESIGN: op = "del re-sign"; break;
641		}
642		if (file != NULL)
643			fprintf(file, "%s %.*s\n", op, (int) r.length,
644				(char *) r.base);
645		else
646			isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7),
647				      "%s %.*s", op, (int) r.length,
648				      (char *) r.base);
649	}
650	result = ISC_R_SUCCESS;
651 cleanup:
652	if (mem != NULL)
653		isc_mem_put(diff->mctx, mem, size);
654	return (result);
655}
656