1 /* $NetBSD: diff.c,v 1.9 2015/07/08 17:28:58 christos Exp $ */
4 * Copyright (C) 2004, 2005, 2007-2009, 2011, 2013-2015 Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 2000-2003 Internet Software Consortium.
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.
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.
20 /* Id: diff.c,v 1.26 2011/03/25 23:53:02 each Exp */
28 #include <isc/buffer.h>
31 #include <isc/string.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>
46 if (result != ISC_R_SUCCESS) goto failure; \
47 } while (/*CONSTCOND*/0)
49 #define DIFF_COMMON_LOGARGS \
50 dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF
52 static dns_rdatatype_t
53 rdata_covers(dns_rdata_t
*rdata
) {
54 return (rdata
->type
== dns_rdatatype_rrsig
?
55 dns_rdata_covers(rdata
) : 0);
59 dns_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
)
67 REQUIRE(tp
!= NULL
&& *tp
== NULL
);
70 * Create a new tuple. The variable-size wire-format name data and
71 * rdata immediately follow the dns_difftuple_t structure
74 size
= sizeof(*t
) + name
->length
+ rdata
->length
;
75 t
= isc_mem_allocate(mctx
, size
);
77 return (ISC_R_NOMEMORY
);
79 isc_mem_attach(mctx
, &t
->mctx
);
82 datap
= (unsigned char *)(t
+ 1);
84 memmove(datap
, name
->ndata
, name
->length
);
85 dns_name_init(&t
->name
, NULL
);
86 dns_name_clone(name
, &t
->name
);
87 t
->name
.ndata
= datap
;
88 datap
+= name
->length
;
92 memmove(datap
, rdata
->data
, rdata
->length
);
93 dns_rdata_init(&t
->rdata
);
94 dns_rdata_clone(rdata
, &t
->rdata
);
95 t
->rdata
.data
= datap
;
96 datap
+= rdata
->length
;
98 ISC_LINK_INIT(&t
->rdata
, link
);
99 ISC_LINK_INIT(t
, link
);
100 t
->magic
= DNS_DIFFTUPLE_MAGIC
;
102 INSIST(datap
== (unsigned char *)t
+ size
);
105 return (ISC_R_SUCCESS
);
109 dns_difftuple_free(dns_difftuple_t
**tp
) {
110 dns_difftuple_t
*t
= *tp
;
113 REQUIRE(DNS_DIFFTUPLE_VALID(t
));
115 dns_name_invalidate(&t
->name
);
118 isc_mem_free(mctx
, t
);
119 isc_mem_detach(&mctx
);
124 dns_difftuple_copy(dns_difftuple_t
*orig
, dns_difftuple_t
**copyp
) {
125 return (dns_difftuple_create(orig
->mctx
, orig
->op
, &orig
->name
,
126 orig
->ttl
, &orig
->rdata
, copyp
));
130 dns_diff_init(isc_mem_t
*mctx
, dns_diff_t
*diff
) {
132 ISC_LIST_INIT(diff
->tuples
);
133 diff
->magic
= DNS_DIFF_MAGIC
;
137 dns_diff_clear(dns_diff_t
*diff
) {
139 REQUIRE(DNS_DIFF_VALID(diff
));
140 while ((t
= ISC_LIST_HEAD(diff
->tuples
)) != NULL
) {
141 ISC_LIST_UNLINK(diff
->tuples
, t
, link
);
142 dns_difftuple_free(&t
);
144 ENSURE(ISC_LIST_EMPTY(diff
->tuples
));
148 dns_diff_append(dns_diff_t
*diff
, dns_difftuple_t
**tuplep
)
150 ISC_LIST_APPEND(diff
->tuples
, *tuplep
, link
);
154 /* XXX this is O(N) */
157 dns_diff_appendminimal(dns_diff_t
*diff
, dns_difftuple_t
**tuplep
)
159 dns_difftuple_t
*ot
, *next_ot
;
161 REQUIRE(DNS_DIFF_VALID(diff
));
162 REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep
));
165 * Look for an existing tuple with the same owner name,
166 * rdata, and TTL. If we are doing an addition and find a
167 * deletion or vice versa, remove both the old and the
168 * new tuple since they cancel each other out (assuming
169 * that we never delete nonexistent data or add existing
172 * If we find an old update of the same kind as
173 * the one we are doing, there must be a programming
174 * error. We report it but try to continue anyway.
176 for (ot
= ISC_LIST_HEAD(diff
->tuples
); ot
!= NULL
;
179 next_ot
= ISC_LIST_NEXT(ot
, link
);
180 if (dns_name_equal(&ot
->name
, &(*tuplep
)->name
) &&
181 dns_rdata_compare(&ot
->rdata
, &(*tuplep
)->rdata
) == 0 &&
182 ot
->ttl
== (*tuplep
)->ttl
)
184 ISC_LIST_UNLINK(diff
->tuples
, ot
, link
);
185 if ((*tuplep
)->op
== ot
->op
) {
186 UNEXPECTED_ERROR(__FILE__
, __LINE__
,
187 "unexpected non-minimal diff");
189 dns_difftuple_free(tuplep
);
191 dns_difftuple_free(&ot
);
196 if (*tuplep
!= NULL
) {
197 ISC_LIST_APPEND(diff
->tuples
, *tuplep
, link
);
201 ENSURE(*tuplep
== NULL
);
205 setresign(dns_rdataset_t
*modified
) {
206 dns_rdata_t rdata
= DNS_RDATA_INIT
;
207 dns_rdata_rrsig_t sig
;
211 result
= dns_rdataset_first(modified
);
212 INSIST(result
== ISC_R_SUCCESS
);
213 dns_rdataset_current(modified
, &rdata
);
214 (void)dns_rdata_tostruct(&rdata
, &sig
, NULL
);
215 if ((rdata
.flags
& DNS_RDATA_OFFLINE
) != 0)
218 when
= sig
.timeexpire
;
219 dns_rdata_reset(&rdata
);
221 result
= dns_rdataset_next(modified
);
222 while (result
== ISC_R_SUCCESS
) {
223 dns_rdataset_current(modified
, &rdata
);
224 (void)dns_rdata_tostruct(&rdata
, &sig
, NULL
);
225 if ((rdata
.flags
& DNS_RDATA_OFFLINE
) != 0) {
228 if (when
== 0 || sig
.timeexpire
< when
)
229 when
= sig
.timeexpire
;
231 dns_rdata_reset(&rdata
);
232 result
= dns_rdataset_next(modified
);
234 INSIST(result
== ISC_R_NOMORE
);
239 diff_apply(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
,
243 dns_dbnode_t
*node
= NULL
;
245 char namebuf
[DNS_NAME_FORMATSIZE
];
246 char typebuf
[DNS_RDATATYPE_FORMATSIZE
];
247 char classbuf
[DNS_RDATACLASS_FORMATSIZE
];
249 REQUIRE(DNS_DIFF_VALID(diff
));
250 REQUIRE(DNS_DB_VALID(db
));
252 t
= ISC_LIST_HEAD(diff
->tuples
);
256 INSIST(node
== NULL
);
260 * We create the node if it does not exist.
261 * This will cause an empty node to be created if the diff
262 * contains a deletion of an RR at a nonexistent name,
263 * but such diffs should never be created in the first
267 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
)) {
268 dns_rdatatype_t type
, covers
;
272 dns_rdataset_t ardataset
;
273 dns_rdataset_t
*modified
= NULL
;
276 type
= t
->rdata
.type
;
277 covers
= rdata_covers(&t
->rdata
);
280 * Collect a contiguous set of updates with
281 * the same operation (add/delete) and RR type
282 * into a single rdatalist so that the
283 * database rrset merging/subtraction code
284 * can work more efficiently than if each
285 * RR were merged into / subtracted from
286 * the database separately.
288 * This is done by linking rdata structures from the
289 * diff into "rdatalist". This uses the rdata link
290 * field, not the diff link field, so the structure
291 * of the diff itself is not affected.
296 rdl
.rdclass
= t
->rdata
.rdclass
;
298 ISC_LIST_INIT(rdl
.rdata
);
299 ISC_LINK_INIT(&rdl
, link
);
302 if (type
!= dns_rdatatype_nsec3
&&
303 covers
!= dns_rdatatype_nsec3
)
304 CHECK(dns_db_findnode(db
, name
, ISC_TRUE
,
307 CHECK(dns_db_findnsec3node(db
, name
, ISC_TRUE
,
311 dns_name_equal(&t
->name
, name
) &&
313 t
->rdata
.type
== type
&&
314 rdata_covers(&t
->rdata
) == covers
)
316 dns_name_format(name
, namebuf
, sizeof(namebuf
));
317 dns_rdatatype_format(t
->rdata
.type
, typebuf
,
319 dns_rdataclass_format(t
->rdata
.rdclass
,
322 if (t
->ttl
!= rdl
.ttl
&& warn
)
323 isc_log_write(DIFF_COMMON_LOGARGS
,
325 "'%s/%s/%s': TTL differs in "
326 "rdataset, adjusting "
328 namebuf
, typebuf
, classbuf
,
329 (unsigned long) t
->ttl
,
330 (unsigned long) rdl
.ttl
);
331 ISC_LIST_APPEND(rdl
.rdata
, &t
->rdata
, link
);
332 t
= ISC_LIST_NEXT(t
, link
);
336 * Convert the rdatalist into a rdataset.
338 dns_rdataset_init(&rds
);
339 CHECK(dns_rdatalist_tordataset(&rdl
, &rds
));
340 if (rds
.type
== dns_rdatatype_rrsig
)
342 case DNS_DIFFOP_ADDRESIGN
:
343 case DNS_DIFFOP_DELRESIGN
:
344 modified
= &ardataset
;
345 dns_rdataset_init(modified
);
350 rds
.trust
= dns_trust_ultimate
;
353 * Merge the rdataset into the database.
357 case DNS_DIFFOP_ADDRESIGN
:
358 result
= dns_db_addrdataset(db
, node
, ver
,
366 case DNS_DIFFOP_DELRESIGN
:
367 result
= dns_db_subtractrdataset(db
, node
, ver
,
376 if (result
== ISC_R_SUCCESS
) {
377 if (modified
!= NULL
) {
378 isc_stdtime_t resign
;
379 resign
= setresign(modified
);
380 dns_db_setsigningtime(db
, modified
,
383 } else if (result
== DNS_R_UNCHANGED
) {
385 * This will not happen when executing a
386 * dynamic update, because that code will
387 * generate strictly minimal diffs.
388 * It may happen when receiving an IXFR
389 * from a server that is not as careful.
390 * Issue a warning and continue.
393 dns_name_format(dns_db_origin(db
),
396 dns_rdataclass_format(dns_db_class(db
),
399 isc_log_write(DIFF_COMMON_LOGARGS
,
401 "%s/%s: dns_diff_apply: "
402 "update with no effect",
405 } else if (result
== DNS_R_NXRRSET
) {
410 if (modified
!= NULL
&&
411 dns_rdataset_isassociated(modified
))
412 dns_rdataset_disassociate(modified
);
415 dns_db_detachnode(db
, &node
);
416 if (modified
!= NULL
&&
417 dns_rdataset_isassociated(modified
))
418 dns_rdataset_disassociate(modified
);
421 return (ISC_R_SUCCESS
);
425 dns_db_detachnode(db
, &node
);
430 dns_diff_apply(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
) {
431 return (diff_apply(diff
, db
, ver
, ISC_TRUE
));
435 dns_diff_applysilently(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
) {
436 return (diff_apply(diff
, db
, ver
, ISC_FALSE
));
439 /* XXX this duplicates lots of code in diff_apply(). */
442 dns_diff_load(dns_diff_t
*diff
, dns_addrdatasetfunc_t addfunc
,
448 REQUIRE(DNS_DIFF_VALID(diff
));
450 t
= ISC_LIST_HEAD(diff
->tuples
);
455 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
)) {
456 dns_rdatatype_t type
, covers
;
462 type
= t
->rdata
.type
;
463 covers
= rdata_covers(&t
->rdata
);
467 rdl
.rdclass
= t
->rdata
.rdclass
;
469 ISC_LIST_INIT(rdl
.rdata
);
470 ISC_LINK_INIT(&rdl
, link
);
472 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
) &&
473 t
->op
== op
&& t
->rdata
.type
== type
&&
474 rdata_covers(&t
->rdata
) == covers
)
476 ISC_LIST_APPEND(rdl
.rdata
, &t
->rdata
, link
);
477 t
= ISC_LIST_NEXT(t
, link
);
481 * Convert the rdatalist into a rdataset.
483 dns_rdataset_init(&rds
);
484 CHECK(dns_rdatalist_tordataset(&rdl
, &rds
));
485 rds
.trust
= dns_trust_ultimate
;
487 INSIST(op
== DNS_DIFFOP_ADD
);
488 result
= (*addfunc
)(add_private
, name
, &rds
);
489 if (result
== DNS_R_UNCHANGED
) {
490 isc_log_write(DIFF_COMMON_LOGARGS
,
493 "update with no effect");
494 } else if (result
== ISC_R_SUCCESS
||
495 result
== DNS_R_NXRRSET
) {
504 result
= ISC_R_SUCCESS
;
510 * XXX uses qsort(); a merge sort would be more natural for lists,
511 * and perhaps safer wrt thread stack overflow.
514 dns_diff_sort(dns_diff_t
*diff
, dns_diff_compare_func
*compare
) {
515 unsigned int length
= 0;
519 REQUIRE(DNS_DIFF_VALID(diff
));
521 for (p
= ISC_LIST_HEAD(diff
->tuples
);
523 p
= ISC_LIST_NEXT(p
, link
))
526 return (ISC_R_SUCCESS
);
527 v
= isc_mem_get(diff
->mctx
, length
* sizeof(dns_difftuple_t
*));
529 return (ISC_R_NOMEMORY
);
530 for (i
= 0; i
< length
; i
++) {
531 p
= ISC_LIST_HEAD(diff
->tuples
);
533 ISC_LIST_UNLINK(diff
->tuples
, p
, link
);
535 INSIST(ISC_LIST_HEAD(diff
->tuples
) == NULL
);
536 qsort(v
, length
, sizeof(v
[0]), compare
);
537 for (i
= 0; i
< length
; i
++) {
538 ISC_LIST_APPEND(diff
->tuples
, v
[i
], link
);
540 isc_mem_put(diff
->mctx
, v
, length
* sizeof(dns_difftuple_t
*));
541 return (ISC_R_SUCCESS
);
546 * Create an rdataset containing the single RR of the given
547 * tuple. The caller must allocate the rdata, rdataset and
548 * an rdatalist structure for it to refer to.
552 diff_tuple_tordataset(dns_difftuple_t
*t
, dns_rdata_t
*rdata
,
553 dns_rdatalist_t
*rdl
, dns_rdataset_t
*rds
)
555 REQUIRE(DNS_DIFFTUPLE_VALID(t
));
556 REQUIRE(rdl
!= NULL
);
557 REQUIRE(rds
!= NULL
);
559 rdl
->type
= t
->rdata
.type
;
560 rdl
->rdclass
= t
->rdata
.rdclass
;
562 ISC_LIST_INIT(rdl
->rdata
);
563 ISC_LINK_INIT(rdl
, link
);
564 dns_rdataset_init(rds
);
565 ISC_LINK_INIT(rdata
, link
);
566 dns_rdata_clone(&t
->rdata
, rdata
);
567 ISC_LIST_APPEND(rdl
->rdata
, rdata
, link
);
568 return (dns_rdatalist_tordataset(rdl
, rds
));
572 dns_diff_print(dns_diff_t
*diff
, FILE *file
) {
576 unsigned int size
= 2048;
577 const char *op
= NULL
;
579 REQUIRE(DNS_DIFF_VALID(diff
));
581 mem
= isc_mem_get(diff
->mctx
, size
);
583 return (ISC_R_NOMEMORY
);
585 for (t
= ISC_LIST_HEAD(diff
->tuples
); t
!= NULL
;
586 t
= ISC_LIST_NEXT(t
, link
))
593 dns_rdata_t rd
= DNS_RDATA_INIT
;
595 result
= diff_tuple_tordataset(t
, &rd
, &rdl
, &rds
);
596 if (result
!= ISC_R_SUCCESS
) {
597 UNEXPECTED_ERROR(__FILE__
, __LINE__
,
598 "diff_tuple_tordataset failed: %s",
599 dns_result_totext(result
));
600 result
= ISC_R_UNEXPECTED
;
604 isc_buffer_init(&buf
, mem
, size
);
605 result
= dns_rdataset_totext(&rds
, &t
->name
,
606 ISC_FALSE
, ISC_FALSE
, &buf
);
608 if (result
== ISC_R_NOSPACE
) {
609 isc_mem_put(diff
->mctx
, mem
, size
);
611 mem
= isc_mem_get(diff
->mctx
, size
);
613 result
= ISC_R_NOMEMORY
;
619 if (result
!= ISC_R_SUCCESS
)
622 * Get rid of final newline.
624 INSIST(buf
.used
>= 1 &&
625 ((char *) buf
.base
)[buf
.used
-1] == '\n');
628 isc_buffer_usedregion(&buf
, &r
);
630 case DNS_DIFFOP_EXISTS
: op
= "exists"; break;
631 case DNS_DIFFOP_ADD
: op
= "add"; break;
632 case DNS_DIFFOP_DEL
: op
= "del"; break;
633 case DNS_DIFFOP_ADDRESIGN
: op
= "add re-sign"; break;
634 case DNS_DIFFOP_DELRESIGN
: op
= "del re-sign"; break;
637 fprintf(file
, "%s %.*s\n", op
, (int) r
.length
,
640 isc_log_write(DIFF_COMMON_LOGARGS
, ISC_LOG_DEBUG(7),
641 "%s %.*s", op
, (int) r
.length
,
644 result
= ISC_R_SUCCESS
;
647 isc_mem_put(diff
->mctx
, mem
, size
);