2 * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 2000-2002 Internet Software Consortium.
5 * Permission to use, copy, modify, and 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.4.2.3 2004/03/09 06:11:01 marka Exp $ */
24 #include <isc/buffer.h>
27 #include <isc/string.h>
33 #include <dns/rdatalist.h>
34 #include <dns/rdataset.h>
35 #include <dns/result.h>
39 if (result != ISC_R_SUCCESS) goto failure; \
42 #define DIFF_COMMON_LOGARGS \
43 dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF
45 static dns_rdatatype_t
46 rdata_covers(dns_rdata_t *rdata) {
47 return (rdata->type == dns_rdatatype_sig ?
48 dns_rdata_covers(rdata) : 0);
52 dns_difftuple_create(isc_mem_t *mctx,
53 dns_diffop_t op, dns_name_t *name, dns_ttl_t ttl,
54 dns_rdata_t *rdata, dns_difftuple_t **tp)
60 REQUIRE(tp != NULL && *tp == NULL);
63 * Create a new tuple. The variable-size wire-format name data and
64 * rdata immediately follow the dns_difftuple_t structure
67 size = sizeof(*t) + name->length + rdata->length;
68 t = isc_mem_allocate(mctx, size);
70 return (ISC_R_NOMEMORY);
74 datap = (unsigned char *)(t + 1);
76 memcpy(datap, name->ndata, name->length);
77 dns_name_init(&t->name, NULL);
78 dns_name_clone(name, &t->name);
79 t->name.ndata = datap;
80 datap += name->length;
84 memcpy(datap, rdata->data, rdata->length);
85 dns_rdata_init(&t->rdata);
86 dns_rdata_clone(rdata, &t->rdata);
87 t->rdata.data = datap;
88 datap += rdata->length;
90 ISC_LINK_INIT(&t->rdata, link);
91 ISC_LINK_INIT(t, link);
92 t->magic = DNS_DIFFTUPLE_MAGIC;
94 INSIST(datap == (unsigned char *)t + size);
97 return (ISC_R_SUCCESS);
101 dns_difftuple_free(dns_difftuple_t **tp) {
102 dns_difftuple_t *t = *tp;
103 REQUIRE(DNS_DIFFTUPLE_VALID(t));
104 dns_name_invalidate(&t->name);
106 isc_mem_free(t->mctx, t);
111 dns_difftuple_copy(dns_difftuple_t *orig, dns_difftuple_t **copyp) {
112 return (dns_difftuple_create(orig->mctx, orig->op, &orig->name,
113 orig->ttl, &orig->rdata, copyp));
117 dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) {
119 ISC_LIST_INIT(diff->tuples);
120 diff->magic = DNS_DIFF_MAGIC;
124 dns_diff_clear(dns_diff_t *diff) {
126 REQUIRE(DNS_DIFF_VALID(diff));
127 while ((t = ISC_LIST_HEAD(diff->tuples)) != NULL) {
128 ISC_LIST_UNLINK(diff->tuples, t, link);
129 dns_difftuple_free(&t);
131 ENSURE(ISC_LIST_EMPTY(diff->tuples));
135 dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep)
137 ISC_LIST_APPEND(diff->tuples, *tuplep, link);
141 /* XXX this is O(N) */
144 dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep)
146 dns_difftuple_t *ot, *next_ot;
148 REQUIRE(DNS_DIFF_VALID(diff));
149 REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep));
152 * Look for an existing tuple with the same owner name,
153 * rdata, and TTL. If we are doing an addition and find a
154 * deletion or vice versa, remove both the old and the
155 * new tuple since they cancel each other out (assuming
156 * that we never delete nonexistent data or add existing
159 * If we find an old update of the same kind as
160 * the one we are doing, there must be a programming
161 * error. We report it but try to continue anyway.
163 for (ot = ISC_LIST_HEAD(diff->tuples); ot != NULL;
166 next_ot = ISC_LIST_NEXT(ot, link);
167 if (dns_name_equal(&ot->name, &(*tuplep)->name) &&
168 dns_rdata_compare(&ot->rdata, &(*tuplep)->rdata) == 0 &&
169 ot->ttl == (*tuplep)->ttl)
171 ISC_LIST_UNLINK(diff->tuples, ot, link);
172 if ((*tuplep)->op == ot->op) {
173 UNEXPECTED_ERROR(__FILE__, __LINE__,
174 "unexpected non-minimal diff");
176 dns_difftuple_free(tuplep);
178 dns_difftuple_free(&ot);
183 if (*tuplep != NULL) {
184 ISC_LIST_APPEND(diff->tuples, *tuplep, link);
188 ENSURE(*tuplep == NULL);
192 dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver)
195 dns_dbnode_t *node = NULL;
198 REQUIRE(DNS_DIFF_VALID(diff));
199 REQUIRE(DNS_DB_VALID(db));
201 t = ISC_LIST_HEAD(diff->tuples);
205 INSIST(node == NULL);
209 * We create the node if it does not exist.
210 * This will cause an empty node to be created if the diff
211 * contains a deletion of an RR at a nonexistent name,
212 * but such diffs should never be created in the first
216 CHECK(dns_db_findnode(db, name, ISC_TRUE, &node));
218 while (t != NULL && dns_name_equal(&t->name, name)) {
219 dns_rdatatype_t type, covers;
225 type = t->rdata.type;
226 covers = rdata_covers(&t->rdata);
229 * Collect a contiguous set of updates with
230 * the same operation (add/delete) and RR type
231 * into a single rdatalist so that the
232 * database rrset merging/subtraction code
233 * can work more efficiently than if each
234 * RR were merged into / subtracted from
235 * the database separately.
237 * This is done by linking rdata structures from the
238 * diff into "rdatalist". This uses the rdata link
239 * field, not the diff link field, so the structure
240 * of the diff itself is not affected.
245 rdl.rdclass = t->rdata.rdclass;
247 ISC_LIST_INIT(rdl.rdata);
248 ISC_LINK_INIT(&rdl, link);
251 dns_name_equal(&t->name, name) &&
253 t->rdata.type == type &&
254 rdata_covers(&t->rdata) == covers)
256 if (t->ttl != rdl.ttl) {
257 isc_log_write(DIFF_COMMON_LOGARGS,
259 "TTL differs in rdataset, "
260 "adjusting %lu -> %lu",
261 (unsigned long) t->ttl,
262 (unsigned long) rdl.ttl);
264 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
265 t = ISC_LIST_NEXT(t, link);
269 * Convert the rdatalist into a rdataset.
271 dns_rdataset_init(&rds);
272 CHECK(dns_rdatalist_tordataset(&rdl, &rds));
273 rds.trust = dns_trust_ultimate;
276 * Merge the rdataset into the database.
278 if (op == DNS_DIFFOP_ADD) {
279 result = dns_db_addrdataset(db, node, ver,
285 } else if (op == DNS_DIFFOP_DEL) {
286 result = dns_db_subtractrdataset(db, node, ver,
293 if (result == DNS_R_UNCHANGED) {
295 * This will not happen when executing a
296 * dynamic update, because that code will
297 * generate strictly minimal diffs.
298 * It may happen when receiving an IXFR
299 * from a server that is not as careful.
300 * Issue a warning and continue.
302 isc_log_write(DIFF_COMMON_LOGARGS,
304 "update with no effect");
305 } else if (result == ISC_R_SUCCESS ||
306 result == DNS_R_NXRRSET) {
314 dns_db_detachnode(db, &node);
316 return (ISC_R_SUCCESS);
320 dns_db_detachnode(db, &node);
324 /* XXX this duplicates lots of code in dns_diff_apply(). */
327 dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc,
333 REQUIRE(DNS_DIFF_VALID(diff));
335 t = ISC_LIST_HEAD(diff->tuples);
340 while (t != NULL && dns_name_equal(&t->name, name)) {
341 dns_rdatatype_t type, covers;
347 type = t->rdata.type;
348 covers = rdata_covers(&t->rdata);
352 rdl.rdclass = t->rdata.rdclass;
354 ISC_LIST_INIT(rdl.rdata);
355 ISC_LINK_INIT(&rdl, link);
357 while (t != NULL && dns_name_equal(&t->name, name) &&
358 t->op == op && t->rdata.type == type &&
359 rdata_covers(&t->rdata) == covers)
361 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
362 t = ISC_LIST_NEXT(t, link);
366 * Convert the rdatalist into a rdataset.
368 dns_rdataset_init(&rds);
369 CHECK(dns_rdatalist_tordataset(&rdl, &rds));
370 rds.trust = dns_trust_ultimate;
372 INSIST(op == DNS_DIFFOP_ADD);
373 result = (*addfunc)(add_private, name, &rds);
374 if (result == DNS_R_UNCHANGED) {
375 isc_log_write(DIFF_COMMON_LOGARGS,
377 "update with no effect");
378 } else if (result == ISC_R_SUCCESS ||
379 result == DNS_R_NXRRSET) {
388 result = ISC_R_SUCCESS;
394 * XXX uses qsort(); a merge sort would be more natural for lists,
395 * and perhaps safer wrt thread stack overflow.
398 dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) {
399 unsigned int length = 0;
403 REQUIRE(DNS_DIFF_VALID(diff));
405 for (p = ISC_LIST_HEAD(diff->tuples);
407 p = ISC_LIST_NEXT(p, link))
410 return (ISC_R_SUCCESS);
411 v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *));
413 return (ISC_R_NOMEMORY);
415 for (i = 0; i < length; i++) {
416 p = ISC_LIST_HEAD(diff->tuples);
418 ISC_LIST_UNLINK(diff->tuples, p, link);
420 INSIST(ISC_LIST_HEAD(diff->tuples) == NULL);
421 qsort(v, length, sizeof(v[0]), compare);
422 for (i = 0; i < length; i++) {
423 ISC_LIST_APPEND(diff->tuples, v[i], link);
425 isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *));
426 return (ISC_R_SUCCESS);
431 * Create an rdataset containing the single RR of the given
432 * tuple. The caller must allocate the the rdata, rdataset and
433 * an rdatalist structure for it to refer to.
437 diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata,
438 dns_rdatalist_t *rdl, dns_rdataset_t *rds)
440 REQUIRE(DNS_DIFFTUPLE_VALID(t));
441 REQUIRE(rdl != NULL);
442 REQUIRE(rds != NULL);
444 rdl->type = t->rdata.type;
445 rdl->rdclass = t->rdata.rdclass;
447 ISC_LIST_INIT(rdl->rdata);
448 ISC_LINK_INIT(rdl, link);
449 dns_rdataset_init(rds);
450 ISC_LINK_INIT(rdata, link);
451 dns_rdata_clone(&t->rdata, rdata);
452 ISC_LIST_APPEND(rdl->rdata, rdata, link);
453 return (dns_rdatalist_tordataset(rdl, rds));
457 dns_diff_print(dns_diff_t *diff, FILE *file) {
461 unsigned int size = 2048;
463 REQUIRE(DNS_DIFF_VALID(diff));
465 mem = isc_mem_get(diff->mctx, size);
467 return (ISC_R_NOMEMORY);
469 for (t = ISC_LIST_HEAD(diff->tuples); t != NULL;
470 t = ISC_LIST_NEXT(t, link))
477 dns_rdata_t rd = DNS_RDATA_INIT;
479 result = diff_tuple_tordataset(t, &rd, &rdl, &rds);
480 if (result != ISC_R_SUCCESS) {
481 UNEXPECTED_ERROR(__FILE__, __LINE__,
482 "diff_tuple_tordataset failed: %s",
483 dns_result_totext(result));
484 result = ISC_R_UNEXPECTED;
488 isc_buffer_init(&buf, mem, size);
489 result = dns_rdataset_totext(&rds, &t->name,
490 ISC_FALSE, ISC_FALSE, &buf);
492 if (result == ISC_R_NOSPACE) {
493 isc_mem_put(diff->mctx, mem, size);
495 mem = isc_mem_get(diff->mctx, size);
497 result = ISC_R_NOMEMORY;
503 if (result != ISC_R_SUCCESS)
506 * Get rid of final newline.
508 INSIST(buf.used >= 1 &&
509 ((char *) buf.base)[buf.used-1] == '\n');
512 isc_buffer_usedregion(&buf, &r);
514 fprintf(file, "%s %.*s\n",
515 t->op == DNS_DIFFOP_ADD ? "add" : "del",
516 (int) r.length, (char *) r.base);
518 isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7),
520 t->op == DNS_DIFFOP_ADD ? "add" : "del",
521 (int) r.length, (char *) r.base);
523 result = ISC_R_SUCCESS;
526 isc_mem_put(diff->mctx, mem, size);