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