2 * Copyright (C) 2004, 2005, 2007, 2009 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 2000-2003 Internet Software Consortium.
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.
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.
18 /* $Id: diff.c,v 1.14.128.3 2009/01/06 23:46:47 tbox Exp $ */
26 #include <isc/buffer.h>
29 #include <isc/string.h>
35 #include <dns/rdataclass.h>
36 #include <dns/rdatalist.h>
37 #include <dns/rdataset.h>
38 #include <dns/rdatatype.h>
39 #include <dns/result.h>
43 if (result != ISC_R_SUCCESS) goto failure; \
46 #define DIFF_COMMON_LOGARGS \
47 dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF
49 static dns_rdatatype_t
50 rdata_covers(dns_rdata_t
*rdata
) {
51 return (rdata
->type
== dns_rdatatype_rrsig
?
52 dns_rdata_covers(rdata
) : 0);
56 dns_difftuple_create(isc_mem_t
*mctx
,
57 dns_diffop_t op
, dns_name_t
*name
, dns_ttl_t ttl
,
58 dns_rdata_t
*rdata
, dns_difftuple_t
**tp
)
64 REQUIRE(tp
!= NULL
&& *tp
== NULL
);
67 * Create a new tuple. The variable-size wire-format name data and
68 * rdata immediately follow the dns_difftuple_t structure
71 size
= sizeof(*t
) + name
->length
+ rdata
->length
;
72 t
= isc_mem_allocate(mctx
, size
);
74 return (ISC_R_NOMEMORY
);
78 datap
= (unsigned char *)(t
+ 1);
80 memcpy(datap
, name
->ndata
, name
->length
);
81 dns_name_init(&t
->name
, NULL
);
82 dns_name_clone(name
, &t
->name
);
83 t
->name
.ndata
= datap
;
84 datap
+= name
->length
;
88 memcpy(datap
, rdata
->data
, rdata
->length
);
89 dns_rdata_init(&t
->rdata
);
90 dns_rdata_clone(rdata
, &t
->rdata
);
91 t
->rdata
.data
= datap
;
92 datap
+= rdata
->length
;
94 ISC_LINK_INIT(&t
->rdata
, link
);
95 ISC_LINK_INIT(t
, link
);
96 t
->magic
= DNS_DIFFTUPLE_MAGIC
;
98 INSIST(datap
== (unsigned char *)t
+ size
);
101 return (ISC_R_SUCCESS
);
105 dns_difftuple_free(dns_difftuple_t
**tp
) {
106 dns_difftuple_t
*t
= *tp
;
107 REQUIRE(DNS_DIFFTUPLE_VALID(t
));
108 dns_name_invalidate(&t
->name
);
110 isc_mem_free(t
->mctx
, t
);
115 dns_difftuple_copy(dns_difftuple_t
*orig
, dns_difftuple_t
**copyp
) {
116 return (dns_difftuple_create(orig
->mctx
, orig
->op
, &orig
->name
,
117 orig
->ttl
, &orig
->rdata
, copyp
));
121 dns_diff_init(isc_mem_t
*mctx
, dns_diff_t
*diff
) {
123 ISC_LIST_INIT(diff
->tuples
);
124 diff
->magic
= DNS_DIFF_MAGIC
;
128 dns_diff_clear(dns_diff_t
*diff
) {
130 REQUIRE(DNS_DIFF_VALID(diff
));
131 while ((t
= ISC_LIST_HEAD(diff
->tuples
)) != NULL
) {
132 ISC_LIST_UNLINK(diff
->tuples
, t
, link
);
133 dns_difftuple_free(&t
);
135 ENSURE(ISC_LIST_EMPTY(diff
->tuples
));
139 dns_diff_append(dns_diff_t
*diff
, dns_difftuple_t
**tuplep
)
141 ISC_LIST_APPEND(diff
->tuples
, *tuplep
, link
);
145 /* XXX this is O(N) */
148 dns_diff_appendminimal(dns_diff_t
*diff
, dns_difftuple_t
**tuplep
)
150 dns_difftuple_t
*ot
, *next_ot
;
152 REQUIRE(DNS_DIFF_VALID(diff
));
153 REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep
));
156 * Look for an existing tuple with the same owner name,
157 * rdata, and TTL. If we are doing an addition and find a
158 * deletion or vice versa, remove both the old and the
159 * new tuple since they cancel each other out (assuming
160 * that we never delete nonexistent data or add existing
163 * If we find an old update of the same kind as
164 * the one we are doing, there must be a programming
165 * error. We report it but try to continue anyway.
167 for (ot
= ISC_LIST_HEAD(diff
->tuples
); ot
!= NULL
;
170 next_ot
= ISC_LIST_NEXT(ot
, link
);
171 if (dns_name_equal(&ot
->name
, &(*tuplep
)->name
) &&
172 dns_rdata_compare(&ot
->rdata
, &(*tuplep
)->rdata
) == 0 &&
173 ot
->ttl
== (*tuplep
)->ttl
)
175 ISC_LIST_UNLINK(diff
->tuples
, ot
, link
);
176 if ((*tuplep
)->op
== ot
->op
) {
177 UNEXPECTED_ERROR(__FILE__
, __LINE__
,
178 "unexpected non-minimal diff");
180 dns_difftuple_free(tuplep
);
182 dns_difftuple_free(&ot
);
187 if (*tuplep
!= NULL
) {
188 ISC_LIST_APPEND(diff
->tuples
, *tuplep
, link
);
192 ENSURE(*tuplep
== NULL
);
196 diff_apply(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
,
200 dns_dbnode_t
*node
= NULL
;
202 char namebuf
[DNS_NAME_FORMATSIZE
];
203 char typebuf
[DNS_RDATATYPE_FORMATSIZE
];
204 char classbuf
[DNS_RDATACLASS_FORMATSIZE
];
206 REQUIRE(DNS_DIFF_VALID(diff
));
207 REQUIRE(DNS_DB_VALID(db
));
209 t
= ISC_LIST_HEAD(diff
->tuples
);
213 INSIST(node
== NULL
);
217 * We create the node if it does not exist.
218 * This will cause an empty node to be created if the diff
219 * contains a deletion of an RR at a nonexistent name,
220 * but such diffs should never be created in the first
224 CHECK(dns_db_findnode(db
, name
, ISC_TRUE
, &node
));
226 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
)) {
227 dns_rdatatype_t type
, covers
;
233 type
= t
->rdata
.type
;
234 covers
= rdata_covers(&t
->rdata
);
237 * Collect a contiguous set of updates with
238 * the same operation (add/delete) and RR type
239 * into a single rdatalist so that the
240 * database rrset merging/subtraction code
241 * can work more efficiently than if each
242 * RR were merged into / subtracted from
243 * the database separately.
245 * This is done by linking rdata structures from the
246 * diff into "rdatalist". This uses the rdata link
247 * field, not the diff link field, so the structure
248 * of the diff itself is not affected.
253 rdl
.rdclass
= t
->rdata
.rdclass
;
255 ISC_LIST_INIT(rdl
.rdata
);
256 ISC_LINK_INIT(&rdl
, link
);
259 dns_name_equal(&t
->name
, name
) &&
261 t
->rdata
.type
== type
&&
262 rdata_covers(&t
->rdata
) == covers
)
264 dns_name_format(name
, namebuf
, sizeof(namebuf
));
265 dns_rdatatype_format(t
->rdata
.type
, typebuf
,
267 dns_rdataclass_format(t
->rdata
.rdclass
,
270 if (t
->ttl
!= rdl
.ttl
&& warn
)
271 isc_log_write(DIFF_COMMON_LOGARGS
,
273 "'%s/%s/%s': TTL differs in "
274 "rdataset, adjusting "
276 namebuf
, typebuf
, classbuf
,
277 (unsigned long) t
->ttl
,
278 (unsigned long) rdl
.ttl
);
279 ISC_LIST_APPEND(rdl
.rdata
, &t
->rdata
, link
);
280 t
= ISC_LIST_NEXT(t
, link
);
284 * Convert the rdatalist into a rdataset.
286 dns_rdataset_init(&rds
);
287 CHECK(dns_rdatalist_tordataset(&rdl
, &rds
));
288 rds
.trust
= dns_trust_ultimate
;
291 * Merge the rdataset into the database.
293 if (op
== DNS_DIFFOP_ADD
) {
294 result
= dns_db_addrdataset(db
, node
, ver
,
300 } else if (op
== DNS_DIFFOP_DEL
) {
301 result
= dns_db_subtractrdataset(db
, node
, ver
,
308 if (result
== DNS_R_UNCHANGED
) {
310 * This will not happen when executing a
311 * dynamic update, because that code will
312 * generate strictly minimal diffs.
313 * It may happen when receiving an IXFR
314 * from a server that is not as careful.
315 * Issue a warning and continue.
318 isc_log_write(DIFF_COMMON_LOGARGS
,
320 "update with no effect");
321 } else if (result
== ISC_R_SUCCESS
||
322 result
== DNS_R_NXRRSET
) {
330 dns_db_detachnode(db
, &node
);
332 return (ISC_R_SUCCESS
);
336 dns_db_detachnode(db
, &node
);
341 dns_diff_apply(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
) {
342 return (diff_apply(diff
, db
, ver
, ISC_TRUE
));
346 dns_diff_applysilently(dns_diff_t
*diff
, dns_db_t
*db
, dns_dbversion_t
*ver
) {
347 return (diff_apply(diff
, db
, ver
, ISC_FALSE
));
350 /* XXX this duplicates lots of code in diff_apply(). */
353 dns_diff_load(dns_diff_t
*diff
, dns_addrdatasetfunc_t addfunc
,
359 REQUIRE(DNS_DIFF_VALID(diff
));
361 t
= ISC_LIST_HEAD(diff
->tuples
);
366 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
)) {
367 dns_rdatatype_t type
, covers
;
373 type
= t
->rdata
.type
;
374 covers
= rdata_covers(&t
->rdata
);
378 rdl
.rdclass
= t
->rdata
.rdclass
;
380 ISC_LIST_INIT(rdl
.rdata
);
381 ISC_LINK_INIT(&rdl
, link
);
383 while (t
!= NULL
&& dns_name_equal(&t
->name
, name
) &&
384 t
->op
== op
&& t
->rdata
.type
== type
&&
385 rdata_covers(&t
->rdata
) == covers
)
387 ISC_LIST_APPEND(rdl
.rdata
, &t
->rdata
, link
);
388 t
= ISC_LIST_NEXT(t
, link
);
392 * Convert the rdatalist into a rdataset.
394 dns_rdataset_init(&rds
);
395 CHECK(dns_rdatalist_tordataset(&rdl
, &rds
));
396 rds
.trust
= dns_trust_ultimate
;
398 INSIST(op
== DNS_DIFFOP_ADD
);
399 result
= (*addfunc
)(add_private
, name
, &rds
);
400 if (result
== DNS_R_UNCHANGED
) {
401 isc_log_write(DIFF_COMMON_LOGARGS
,
403 "update with no effect");
404 } else if (result
== ISC_R_SUCCESS
||
405 result
== DNS_R_NXRRSET
) {
414 result
= ISC_R_SUCCESS
;
420 * XXX uses qsort(); a merge sort would be more natural for lists,
421 * and perhaps safer wrt thread stack overflow.
424 dns_diff_sort(dns_diff_t
*diff
, dns_diff_compare_func
*compare
) {
425 unsigned int length
= 0;
429 REQUIRE(DNS_DIFF_VALID(diff
));
431 for (p
= ISC_LIST_HEAD(diff
->tuples
);
433 p
= ISC_LIST_NEXT(p
, link
))
436 return (ISC_R_SUCCESS
);
437 v
= isc_mem_get(diff
->mctx
, length
* sizeof(dns_difftuple_t
*));
439 return (ISC_R_NOMEMORY
);
441 for (i
= 0; i
< length
; i
++) {
442 p
= ISC_LIST_HEAD(diff
->tuples
);
444 ISC_LIST_UNLINK(diff
->tuples
, p
, link
);
446 INSIST(ISC_LIST_HEAD(diff
->tuples
) == NULL
);
447 qsort(v
, length
, sizeof(v
[0]), compare
);
448 for (i
= 0; i
< length
; i
++) {
449 ISC_LIST_APPEND(diff
->tuples
, v
[i
], link
);
451 isc_mem_put(diff
->mctx
, v
, length
* sizeof(dns_difftuple_t
*));
452 return (ISC_R_SUCCESS
);
457 * Create an rdataset containing the single RR of the given
458 * tuple. The caller must allocate the rdata, rdataset and
459 * an rdatalist structure for it to refer to.
463 diff_tuple_tordataset(dns_difftuple_t
*t
, dns_rdata_t
*rdata
,
464 dns_rdatalist_t
*rdl
, dns_rdataset_t
*rds
)
466 REQUIRE(DNS_DIFFTUPLE_VALID(t
));
467 REQUIRE(rdl
!= NULL
);
468 REQUIRE(rds
!= NULL
);
470 rdl
->type
= t
->rdata
.type
;
471 rdl
->rdclass
= t
->rdata
.rdclass
;
473 ISC_LIST_INIT(rdl
->rdata
);
474 ISC_LINK_INIT(rdl
, link
);
475 dns_rdataset_init(rds
);
476 ISC_LINK_INIT(rdata
, link
);
477 dns_rdata_clone(&t
->rdata
, rdata
);
478 ISC_LIST_APPEND(rdl
->rdata
, rdata
, link
);
479 return (dns_rdatalist_tordataset(rdl
, rds
));
483 dns_diff_print(dns_diff_t
*diff
, FILE *file
) {
487 unsigned int size
= 2048;
489 REQUIRE(DNS_DIFF_VALID(diff
));
491 mem
= isc_mem_get(diff
->mctx
, size
);
493 return (ISC_R_NOMEMORY
);
495 for (t
= ISC_LIST_HEAD(diff
->tuples
); t
!= NULL
;
496 t
= ISC_LIST_NEXT(t
, link
))
503 dns_rdata_t rd
= DNS_RDATA_INIT
;
505 result
= diff_tuple_tordataset(t
, &rd
, &rdl
, &rds
);
506 if (result
!= ISC_R_SUCCESS
) {
507 UNEXPECTED_ERROR(__FILE__
, __LINE__
,
508 "diff_tuple_tordataset failed: %s",
509 dns_result_totext(result
));
510 result
= ISC_R_UNEXPECTED
;
514 isc_buffer_init(&buf
, mem
, size
);
515 result
= dns_rdataset_totext(&rds
, &t
->name
,
516 ISC_FALSE
, ISC_FALSE
, &buf
);
518 if (result
== ISC_R_NOSPACE
) {
519 isc_mem_put(diff
->mctx
, mem
, size
);
521 mem
= isc_mem_get(diff
->mctx
, size
);
523 result
= ISC_R_NOMEMORY
;
529 if (result
!= ISC_R_SUCCESS
)
532 * Get rid of final newline.
534 INSIST(buf
.used
>= 1 &&
535 ((char *) buf
.base
)[buf
.used
-1] == '\n');
538 isc_buffer_usedregion(&buf
, &r
);
540 fprintf(file
, "%s %.*s\n",
541 t
->op
== DNS_DIFFOP_ADD
? "add" : "del",
542 (int) r
.length
, (char *) r
.base
);
544 isc_log_write(DIFF_COMMON_LOGARGS
, ISC_LOG_DEBUG(7),
546 t
->op
== DNS_DIFFOP_ADD
? "add" : "del",
547 (int) r
.length
, (char *) r
.base
);
549 result
= ISC_R_SUCCESS
;
552 isc_mem_put(diff
->mctx
, mem
, size
);