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