1 /* $NetBSD: diff.c,v 1.9 2015/07/08 17:28:58 christos Exp $ */ 2 3 /* 4 * Copyright (C) 2004, 2005, 2007-2009, 2011, 2013-2015 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 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); 56 } 57 58 isc_result_t 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) 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 = NULL; 79 isc_mem_attach(mctx, &t->mctx); 80 t->op = op; 81 82 datap = (unsigned char *)(t + 1); 83 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; 89 90 t->ttl = ttl; 91 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; 97 98 ISC_LINK_INIT(&t->rdata, link); 99 ISC_LINK_INIT(t, link); 100 t->magic = DNS_DIFFTUPLE_MAGIC; 101 102 INSIST(datap == (unsigned char *)t + size); 103 104 *tp = t; 105 return (ISC_R_SUCCESS); 106 } 107 108 void 109 dns_difftuple_free(dns_difftuple_t **tp) { 110 dns_difftuple_t *t = *tp; 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 *tp = NULL; 121 } 122 123 isc_result_t 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)); 127 } 128 129 void 130 dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) { 131 diff->mctx = mctx; 132 ISC_LIST_INIT(diff->tuples); 133 diff->magic = DNS_DIFF_MAGIC; 134 } 135 136 void 137 dns_diff_clear(dns_diff_t *diff) { 138 dns_difftuple_t *t; 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); 143 } 144 ENSURE(ISC_LIST_EMPTY(diff->tuples)); 145 } 146 147 void 148 dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep) 149 { 150 ISC_LIST_APPEND(diff->tuples, *tuplep, link); 151 *tuplep = NULL; 152 } 153 154 /* XXX this is O(N) */ 155 156 void 157 dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep) 158 { 159 dns_difftuple_t *ot, *next_ot; 160 161 REQUIRE(DNS_DIFF_VALID(diff)); 162 REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep)); 163 164 /* 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 170 * data). 171 * 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. 175 */ 176 for (ot = ISC_LIST_HEAD(diff->tuples); ot != NULL; 177 ot = next_ot) 178 { 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) 183 { 184 ISC_LIST_UNLINK(diff->tuples, ot, link); 185 if ((*tuplep)->op == ot->op) { 186 UNEXPECTED_ERROR(__FILE__, __LINE__, 187 "unexpected non-minimal diff"); 188 } else { 189 dns_difftuple_free(tuplep); 190 } 191 dns_difftuple_free(&ot); 192 break; 193 } 194 } 195 196 if (*tuplep != NULL) { 197 ISC_LIST_APPEND(diff->tuples, *tuplep, link); 198 *tuplep = NULL; 199 } 200 201 ENSURE(*tuplep == NULL); 202 } 203 204 static isc_stdtime_t 205 setresign(dns_rdataset_t *modified) { 206 dns_rdata_t rdata = DNS_RDATA_INIT; 207 dns_rdata_rrsig_t sig; 208 isc_stdtime_t when; 209 isc_result_t result; 210 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) 216 when = 0; 217 else 218 when = sig.timeexpire; 219 dns_rdata_reset(&rdata); 220 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) { 226 goto next_rr; 227 } 228 if (when == 0 || sig.timeexpire < when) 229 when = sig.timeexpire; 230 next_rr: 231 dns_rdata_reset(&rdata); 232 result = dns_rdataset_next(modified); 233 } 234 INSIST(result == ISC_R_NOMORE); 235 return (when); 236 } 237 238 static isc_result_t 239 diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver, 240 isc_boolean_t warn) 241 { 242 dns_difftuple_t *t; 243 dns_dbnode_t *node = NULL; 244 isc_result_t result; 245 char namebuf[DNS_NAME_FORMATSIZE]; 246 char typebuf[DNS_RDATATYPE_FORMATSIZE]; 247 char classbuf[DNS_RDATACLASS_FORMATSIZE]; 248 249 REQUIRE(DNS_DIFF_VALID(diff)); 250 REQUIRE(DNS_DB_VALID(db)); 251 252 t = ISC_LIST_HEAD(diff->tuples); 253 while (t != NULL) { 254 dns_name_t *name; 255 256 INSIST(node == NULL); 257 name = &t->name; 258 /* 259 * Find the node. 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 264 * place. 265 */ 266 267 while (t != NULL && dns_name_equal(&t->name, name)) { 268 dns_rdatatype_t type, covers; 269 dns_diffop_t op; 270 dns_rdatalist_t rdl; 271 dns_rdataset_t rds; 272 dns_rdataset_t ardataset; 273 dns_rdataset_t *modified = NULL; 274 275 op = t->op; 276 type = t->rdata.type; 277 covers = rdata_covers(&t->rdata); 278 279 /* 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. 287 * 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. 292 */ 293 294 rdl.type = type; 295 rdl.covers = covers; 296 rdl.rdclass = t->rdata.rdclass; 297 rdl.ttl = t->ttl; 298 ISC_LIST_INIT(rdl.rdata); 299 ISC_LINK_INIT(&rdl, link); 300 301 node = NULL; 302 if (type != dns_rdatatype_nsec3 && 303 covers != dns_rdatatype_nsec3) 304 CHECK(dns_db_findnode(db, name, ISC_TRUE, 305 &node)); 306 else 307 CHECK(dns_db_findnsec3node(db, name, ISC_TRUE, 308 &node)); 309 310 while (t != NULL && 311 dns_name_equal(&t->name, name) && 312 t->op == op && 313 t->rdata.type == type && 314 rdata_covers(&t->rdata) == covers) 315 { 316 dns_name_format(name, namebuf, sizeof(namebuf)); 317 dns_rdatatype_format(t->rdata.type, typebuf, 318 sizeof(typebuf)); 319 dns_rdataclass_format(t->rdata.rdclass, 320 classbuf, 321 sizeof(classbuf)); 322 if (t->ttl != rdl.ttl && warn) 323 isc_log_write(DIFF_COMMON_LOGARGS, 324 ISC_LOG_WARNING, 325 "'%s/%s/%s': TTL differs in " 326 "rdataset, adjusting " 327 "%lu -> %lu", 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); 333 } 334 335 /* 336 * Convert the rdatalist into a rdataset. 337 */ 338 dns_rdataset_init(&rds); 339 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 340 if (rds.type == dns_rdatatype_rrsig) 341 switch (op) { 342 case DNS_DIFFOP_ADDRESIGN: 343 case DNS_DIFFOP_DELRESIGN: 344 modified = &ardataset; 345 dns_rdataset_init(modified); 346 break; 347 default: 348 break; 349 } 350 rds.trust = dns_trust_ultimate; 351 352 /* 353 * Merge the rdataset into the database. 354 */ 355 switch (op) { 356 case DNS_DIFFOP_ADD: 357 case DNS_DIFFOP_ADDRESIGN: 358 result = dns_db_addrdataset(db, node, ver, 359 0, &rds, 360 DNS_DBADD_MERGE| 361 DNS_DBADD_EXACT| 362 DNS_DBADD_EXACTTTL, 363 modified); 364 break; 365 case DNS_DIFFOP_DEL: 366 case DNS_DIFFOP_DELRESIGN: 367 result = dns_db_subtractrdataset(db, node, ver, 368 &rds, 369 DNS_DBSUB_EXACT, 370 modified); 371 break; 372 default: 373 INSIST(0); 374 } 375 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, 381 resign); 382 } 383 } else if (result == DNS_R_UNCHANGED) { 384 /* 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. 391 */ 392 if (warn) { 393 dns_name_format(dns_db_origin(db), 394 namebuf, 395 sizeof(namebuf)); 396 dns_rdataclass_format(dns_db_class(db), 397 classbuf, 398 sizeof(classbuf)); 399 isc_log_write(DIFF_COMMON_LOGARGS, 400 ISC_LOG_WARNING, 401 "%s/%s: dns_diff_apply: " 402 "update with no effect", 403 namebuf, classbuf); 404 } 405 } else if (result == DNS_R_NXRRSET) { 406 /* 407 * OK. 408 */ 409 } else { 410 if (modified != NULL && 411 dns_rdataset_isassociated(modified)) 412 dns_rdataset_disassociate(modified); 413 CHECK(result); 414 } 415 dns_db_detachnode(db, &node); 416 if (modified != NULL && 417 dns_rdataset_isassociated(modified)) 418 dns_rdataset_disassociate(modified); 419 } 420 } 421 return (ISC_R_SUCCESS); 422 423 failure: 424 if (node != NULL) 425 dns_db_detachnode(db, &node); 426 return (result); 427 } 428 429 isc_result_t 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)); 432 } 433 434 isc_result_t 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)); 437 } 438 439 /* XXX this duplicates lots of code in diff_apply(). */ 440 441 isc_result_t 442 dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc, 443 void *add_private) 444 { 445 dns_difftuple_t *t; 446 isc_result_t result; 447 448 REQUIRE(DNS_DIFF_VALID(diff)); 449 450 t = ISC_LIST_HEAD(diff->tuples); 451 while (t != NULL) { 452 dns_name_t *name; 453 454 name = &t->name; 455 while (t != NULL && dns_name_equal(&t->name, name)) { 456 dns_rdatatype_t type, covers; 457 dns_diffop_t op; 458 dns_rdatalist_t rdl; 459 dns_rdataset_t rds; 460 461 op = t->op; 462 type = t->rdata.type; 463 covers = rdata_covers(&t->rdata); 464 465 rdl.type = type; 466 rdl.covers = covers; 467 rdl.rdclass = t->rdata.rdclass; 468 rdl.ttl = t->ttl; 469 ISC_LIST_INIT(rdl.rdata); 470 ISC_LINK_INIT(&rdl, link); 471 472 while (t != NULL && dns_name_equal(&t->name, name) && 473 t->op == op && t->rdata.type == type && 474 rdata_covers(&t->rdata) == covers) 475 { 476 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link); 477 t = ISC_LIST_NEXT(t, link); 478 } 479 480 /* 481 * Convert the rdatalist into a rdataset. 482 */ 483 dns_rdataset_init(&rds); 484 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 485 rds.trust = dns_trust_ultimate; 486 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, 491 ISC_LOG_WARNING, 492 "dns_diff_load: " 493 "update with no effect"); 494 } else if (result == ISC_R_SUCCESS || 495 result == DNS_R_NXRRSET) { 496 /* 497 * OK. 498 */ 499 } else { 500 CHECK(result); 501 } 502 } 503 } 504 result = ISC_R_SUCCESS; 505 failure: 506 return (result); 507 } 508 509 /* 510 * XXX uses qsort(); a merge sort would be more natural for lists, 511 * and perhaps safer wrt thread stack overflow. 512 */ 513 isc_result_t 514 dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) { 515 unsigned int length = 0; 516 unsigned int i; 517 dns_difftuple_t **v; 518 dns_difftuple_t *p; 519 REQUIRE(DNS_DIFF_VALID(diff)); 520 521 for (p = ISC_LIST_HEAD(diff->tuples); 522 p != NULL; 523 p = ISC_LIST_NEXT(p, link)) 524 length++; 525 if (length == 0) 526 return (ISC_R_SUCCESS); 527 v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *)); 528 if (v == NULL) 529 return (ISC_R_NOMEMORY); 530 for (i = 0; i < length; i++) { 531 p = ISC_LIST_HEAD(diff->tuples); 532 v[i] = p; 533 ISC_LIST_UNLINK(diff->tuples, p, link); 534 } 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); 539 } 540 isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *)); 541 return (ISC_R_SUCCESS); 542 } 543 544 545 /* 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. 549 */ 550 551 static isc_result_t 552 diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata, 553 dns_rdatalist_t *rdl, dns_rdataset_t *rds) 554 { 555 REQUIRE(DNS_DIFFTUPLE_VALID(t)); 556 REQUIRE(rdl != NULL); 557 REQUIRE(rds != NULL); 558 559 rdl->type = t->rdata.type; 560 rdl->rdclass = t->rdata.rdclass; 561 rdl->ttl = t->ttl; 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)); 569 } 570 571 isc_result_t 572 dns_diff_print(dns_diff_t *diff, FILE *file) { 573 isc_result_t result; 574 dns_difftuple_t *t; 575 char *mem = NULL; 576 unsigned int size = 2048; 577 const char *op = NULL; 578 579 REQUIRE(DNS_DIFF_VALID(diff)); 580 581 mem = isc_mem_get(diff->mctx, size); 582 if (mem == NULL) 583 return (ISC_R_NOMEMORY); 584 585 for (t = ISC_LIST_HEAD(diff->tuples); t != NULL; 586 t = ISC_LIST_NEXT(t, link)) 587 { 588 isc_buffer_t buf; 589 isc_region_t r; 590 591 dns_rdatalist_t rdl; 592 dns_rdataset_t rds; 593 dns_rdata_t rd = DNS_RDATA_INIT; 594 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; 601 goto cleanup; 602 } 603 again: 604 isc_buffer_init(&buf, mem, size); 605 result = dns_rdataset_totext(&rds, &t->name, 606 ISC_FALSE, ISC_FALSE, &buf); 607 608 if (result == ISC_R_NOSPACE) { 609 isc_mem_put(diff->mctx, mem, size); 610 size += 1024; 611 mem = isc_mem_get(diff->mctx, size); 612 if (mem == NULL) { 613 result = ISC_R_NOMEMORY; 614 goto cleanup; 615 } 616 goto again; 617 } 618 619 if (result != ISC_R_SUCCESS) 620 goto cleanup; 621 /* 622 * Get rid of final newline. 623 */ 624 INSIST(buf.used >= 1 && 625 ((char *) buf.base)[buf.used-1] == '\n'); 626 buf.used--; 627 628 isc_buffer_usedregion(&buf, &r); 629 switch (t->op) { 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; 635 } 636 if (file != NULL) 637 fprintf(file, "%s %.*s\n", op, (int) r.length, 638 (char *) r.base); 639 else 640 isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7), 641 "%s %.*s", op, (int) r.length, 642 (char *) r.base); 643 } 644 result = ISC_R_SUCCESS; 645 cleanup: 646 if (mem != NULL) 647 isc_mem_put(diff->mctx, mem, size); 648 return (result); 649 } 650