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