1 /* $NetBSD: diff.c,v 1.6 2021/04/05 11:27:01 rillig Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 9 * 10 * See the COPYRIGHT file distributed with this work for additional 11 * information regarding copyright ownership. 12 */ 13 14 /*! \file */ 15 16 #include <inttypes.h> 17 #include <stdbool.h> 18 #include <stdlib.h> 19 20 #include <isc/buffer.h> 21 #include <isc/file.h> 22 #include <isc/mem.h> 23 #include <isc/print.h> 24 #include <isc/string.h> 25 #include <isc/util.h> 26 27 #include <dns/db.h> 28 #include <dns/diff.h> 29 #include <dns/log.h> 30 #include <dns/rdataclass.h> 31 #include <dns/rdatalist.h> 32 #include <dns/rdataset.h> 33 #include <dns/rdatastruct.h> 34 #include <dns/rdatatype.h> 35 #include <dns/result.h> 36 #include <dns/time.h> 37 38 #define CHECK(op) \ 39 do { \ 40 result = (op); \ 41 if (result != ISC_R_SUCCESS) \ 42 goto failure; \ 43 } while (0) 44 45 #define DIFF_COMMON_LOGARGS \ 46 dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF 47 48 static dns_rdatatype_t 49 rdata_covers(dns_rdata_t *rdata) { 50 return (rdata->type == dns_rdatatype_rrsig ? dns_rdata_covers(rdata) 51 : 0); 52 } 53 54 isc_result_t 55 dns_difftuple_create(isc_mem_t *mctx, dns_diffop_t op, const dns_name_t *name, 56 dns_ttl_t ttl, dns_rdata_t *rdata, dns_difftuple_t **tp) { 57 dns_difftuple_t *t; 58 unsigned int size; 59 unsigned char *datap; 60 61 REQUIRE(tp != NULL && *tp == NULL); 62 63 /* 64 * Create a new tuple. The variable-size wire-format name data and 65 * rdata immediately follow the dns_difftuple_t structure 66 * in memory. 67 */ 68 size = sizeof(*t) + name->length + rdata->length; 69 t = isc_mem_allocate(mctx, size); 70 t->mctx = NULL; 71 isc_mem_attach(mctx, &t->mctx); 72 t->op = op; 73 74 datap = (unsigned char *)(t + 1); 75 76 memmove(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; 81 82 t->ttl = ttl; 83 84 dns_rdata_init(&t->rdata); 85 dns_rdata_clone(rdata, &t->rdata); 86 if (rdata->data != NULL) { 87 memmove(datap, rdata->data, rdata->length); 88 t->rdata.data = datap; 89 datap += rdata->length; 90 } else { 91 t->rdata.data = NULL; 92 INSIST(rdata->length == 0); 93 } 94 95 ISC_LINK_INIT(&t->rdata, link); 96 ISC_LINK_INIT(t, link); 97 t->magic = DNS_DIFFTUPLE_MAGIC; 98 99 INSIST(datap == (unsigned char *)t + size); 100 101 *tp = t; 102 return (ISC_R_SUCCESS); 103 } 104 105 void 106 dns_difftuple_free(dns_difftuple_t **tp) { 107 dns_difftuple_t *t = *tp; 108 *tp = NULL; 109 isc_mem_t *mctx; 110 111 REQUIRE(DNS_DIFFTUPLE_VALID(t)); 112 113 dns_name_invalidate(&t->name); 114 t->magic = 0; 115 mctx = t->mctx; 116 isc_mem_free(mctx, t); 117 isc_mem_detach(&mctx); 118 } 119 120 isc_result_t 121 dns_difftuple_copy(dns_difftuple_t *orig, dns_difftuple_t **copyp) { 122 return (dns_difftuple_create(orig->mctx, orig->op, &orig->name, 123 orig->ttl, &orig->rdata, copyp)); 124 } 125 126 void 127 dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) { 128 diff->mctx = mctx; 129 ISC_LIST_INIT(diff->tuples); 130 diff->magic = DNS_DIFF_MAGIC; 131 } 132 133 void 134 dns_diff_clear(dns_diff_t *diff) { 135 dns_difftuple_t *t; 136 REQUIRE(DNS_DIFF_VALID(diff)); 137 while ((t = ISC_LIST_HEAD(diff->tuples)) != NULL) { 138 ISC_LIST_UNLINK(diff->tuples, t, link); 139 dns_difftuple_free(&t); 140 } 141 ENSURE(ISC_LIST_EMPTY(diff->tuples)); 142 } 143 144 void 145 dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep) { 146 ISC_LIST_APPEND(diff->tuples, *tuplep, link); 147 *tuplep = NULL; 148 } 149 150 /* XXX this is O(N) */ 151 152 void 153 dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep) { 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; ot = next_ot) { 172 next_ot = ISC_LIST_NEXT(ot, link); 173 if (dns_name_caseequal(&ot->name, &(*tuplep)->name) && 174 dns_rdata_compare(&ot->rdata, &(*tuplep)->rdata) == 0 && 175 ot->ttl == (*tuplep)->ttl) 176 { 177 ISC_LIST_UNLINK(diff->tuples, ot, link); 178 if ((*tuplep)->op == ot->op) { 179 UNEXPECTED_ERROR(__FILE__, __LINE__, 180 "unexpected non-minimal diff"); 181 } else { 182 dns_difftuple_free(tuplep); 183 } 184 dns_difftuple_free(&ot); 185 break; 186 } 187 } 188 189 if (*tuplep != NULL) { 190 ISC_LIST_APPEND(diff->tuples, *tuplep, link); 191 *tuplep = NULL; 192 } 193 } 194 195 static isc_stdtime_t 196 setresign(dns_rdataset_t *modified) { 197 dns_rdata_t rdata = DNS_RDATA_INIT; 198 dns_rdata_rrsig_t sig; 199 int64_t when; 200 isc_result_t result; 201 202 result = dns_rdataset_first(modified); 203 INSIST(result == ISC_R_SUCCESS); 204 dns_rdataset_current(modified, &rdata); 205 (void)dns_rdata_tostruct(&rdata, &sig, NULL); 206 if ((rdata.flags & DNS_RDATA_OFFLINE) != 0) { 207 when = 0; 208 } else { 209 when = dns_time64_from32(sig.timeexpire); 210 } 211 dns_rdata_reset(&rdata); 212 213 result = dns_rdataset_next(modified); 214 while (result == ISC_R_SUCCESS) { 215 dns_rdataset_current(modified, &rdata); 216 (void)dns_rdata_tostruct(&rdata, &sig, NULL); 217 if ((rdata.flags & DNS_RDATA_OFFLINE) != 0) { 218 goto next_rr; 219 } 220 if (when == 0 || dns_time64_from32(sig.timeexpire) < when) { 221 when = dns_time64_from32(sig.timeexpire); 222 } 223 next_rr: 224 dns_rdata_reset(&rdata); 225 result = dns_rdataset_next(modified); 226 } 227 INSIST(result == ISC_R_NOMORE); 228 return ((isc_stdtime_t)when); 229 } 230 231 static void 232 getownercase(dns_rdataset_t *rdataset, dns_name_t *name) { 233 if (dns_rdataset_isassociated(rdataset)) { 234 dns_rdataset_getownercase(rdataset, name); 235 } 236 } 237 238 static void 239 setownercase(dns_rdataset_t *rdataset, const dns_name_t *name) { 240 if (dns_rdataset_isassociated(rdataset)) { 241 dns_rdataset_setownercase(rdataset, name); 242 } 243 } 244 245 static isc_result_t 246 diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver, bool warn) { 247 dns_difftuple_t *t; 248 dns_dbnode_t *node = NULL; 249 isc_result_t result; 250 char namebuf[DNS_NAME_FORMATSIZE]; 251 char typebuf[DNS_RDATATYPE_FORMATSIZE]; 252 char classbuf[DNS_RDATACLASS_FORMATSIZE]; 253 254 REQUIRE(DNS_DIFF_VALID(diff)); 255 REQUIRE(DNS_DB_VALID(db)); 256 257 t = ISC_LIST_HEAD(diff->tuples); 258 while (t != NULL) { 259 dns_name_t *name; 260 261 INSIST(node == NULL); 262 name = &t->name; 263 /* 264 * Find the node. 265 * We create the node if it does not exist. 266 * This will cause an empty node to be created if the diff 267 * contains a deletion of an RR at a nonexistent name, 268 * but such diffs should never be created in the first 269 * place. 270 */ 271 272 while (t != NULL && dns_name_equal(&t->name, name)) { 273 dns_rdatatype_t type, covers; 274 dns_diffop_t op; 275 dns_rdatalist_t rdl; 276 dns_rdataset_t rds; 277 dns_rdataset_t ardataset; 278 unsigned int options; 279 280 op = t->op; 281 type = t->rdata.type; 282 covers = rdata_covers(&t->rdata); 283 284 /* 285 * Collect a contiguous set of updates with 286 * the same operation (add/delete) and RR type 287 * into a single rdatalist so that the 288 * database rrset merging/subtraction code 289 * can work more efficiently than if each 290 * RR were merged into / subtracted from 291 * the database separately. 292 * 293 * This is done by linking rdata structures from the 294 * diff into "rdatalist". This uses the rdata link 295 * field, not the diff link field, so the structure 296 * of the diff itself is not affected. 297 */ 298 299 dns_rdatalist_init(&rdl); 300 rdl.type = type; 301 rdl.covers = covers; 302 rdl.rdclass = t->rdata.rdclass; 303 rdl.ttl = t->ttl; 304 305 node = NULL; 306 if (type != dns_rdatatype_nsec3 && 307 covers != dns_rdatatype_nsec3) { 308 CHECK(dns_db_findnode(db, name, true, &node)); 309 } else { 310 CHECK(dns_db_findnsec3node(db, name, true, 311 &node)); 312 } 313 314 while (t != NULL && dns_name_equal(&t->name, name) && 315 t->op == op && t->rdata.type == type && 316 rdata_covers(&t->rdata) == covers) 317 { 318 /* 319 * Remember the add name for 320 * dns_rdataset_setownercase. 321 */ 322 name = &t->name; 323 if (t->ttl != rdl.ttl && warn) { 324 dns_name_format(name, namebuf, 325 sizeof(namebuf)); 326 dns_rdatatype_format(t->rdata.type, 327 typebuf, 328 sizeof(typebuf)); 329 dns_rdataclass_format(t->rdata.rdclass, 330 classbuf, 331 sizeof(classbuf)); 332 isc_log_write(DIFF_COMMON_LOGARGS, 333 ISC_LOG_WARNING, 334 "'%s/%s/%s': TTL differs " 335 "in " 336 "rdataset, adjusting " 337 "%lu -> %lu", 338 namebuf, typebuf, 339 classbuf, 340 (unsigned long)t->ttl, 341 (unsigned long)rdl.ttl); 342 } 343 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link); 344 t = ISC_LIST_NEXT(t, link); 345 } 346 347 /* 348 * Convert the rdatalist into a rdataset. 349 */ 350 dns_rdataset_init(&rds); 351 dns_rdataset_init(&ardataset); 352 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 353 rds.trust = dns_trust_ultimate; 354 355 /* 356 * Merge the rdataset into the database. 357 */ 358 switch (op) { 359 case DNS_DIFFOP_ADD: 360 case DNS_DIFFOP_ADDRESIGN: 361 options = DNS_DBADD_MERGE | DNS_DBADD_EXACT | 362 DNS_DBADD_EXACTTTL; 363 result = dns_db_addrdataset(db, node, ver, 0, 364 &rds, options, 365 &ardataset); 366 break; 367 case DNS_DIFFOP_DEL: 368 case DNS_DIFFOP_DELRESIGN: 369 options = DNS_DBSUB_EXACT | DNS_DBSUB_WANTOLD; 370 result = dns_db_subtractrdataset(db, node, ver, 371 &rds, options, 372 &ardataset); 373 break; 374 default: 375 INSIST(0); 376 ISC_UNREACHABLE(); 377 } 378 379 if (result == ISC_R_SUCCESS) { 380 if (rds.type == dns_rdatatype_rrsig && 381 (op == DNS_DIFFOP_DELRESIGN || 382 op == DNS_DIFFOP_ADDRESIGN)) 383 { 384 isc_stdtime_t resign; 385 resign = setresign(&ardataset); 386 dns_db_setsigningtime(db, &ardataset, 387 resign); 388 } 389 if (op == DNS_DIFFOP_ADD || 390 op == DNS_DIFFOP_ADDRESIGN) { 391 setownercase(&ardataset, name); 392 } 393 if (op == DNS_DIFFOP_DEL || 394 op == DNS_DIFFOP_DELRESIGN) { 395 getownercase(&ardataset, name); 396 } 397 } else if (result == DNS_R_UNCHANGED) { 398 /* 399 * This will not happen when executing a 400 * dynamic update, because that code will 401 * generate strictly minimal diffs. 402 * It may happen when receiving an IXFR 403 * from a server that is not as careful. 404 * Issue a warning and continue. 405 */ 406 if (warn) { 407 dns_name_format(dns_db_origin(db), 408 namebuf, 409 sizeof(namebuf)); 410 dns_rdataclass_format(dns_db_class(db), 411 classbuf, 412 sizeof(classbuf)); 413 isc_log_write(DIFF_COMMON_LOGARGS, 414 ISC_LOG_WARNING, 415 "%s/%s: dns_diff_apply: " 416 "update with no effect", 417 namebuf, classbuf); 418 } 419 if (op == DNS_DIFFOP_ADD || 420 op == DNS_DIFFOP_ADDRESIGN) { 421 setownercase(&ardataset, name); 422 } 423 if (op == DNS_DIFFOP_DEL || 424 op == DNS_DIFFOP_DELRESIGN) { 425 getownercase(&ardataset, name); 426 } 427 } else if (result == DNS_R_NXRRSET) { 428 /* 429 * OK. 430 */ 431 if (op == DNS_DIFFOP_DEL || 432 op == DNS_DIFFOP_DELRESIGN) { 433 getownercase(&ardataset, name); 434 } 435 if (dns_rdataset_isassociated(&ardataset)) { 436 dns_rdataset_disassociate(&ardataset); 437 } 438 } else { 439 if (dns_rdataset_isassociated(&ardataset)) { 440 dns_rdataset_disassociate(&ardataset); 441 } 442 CHECK(result); 443 } 444 dns_db_detachnode(db, &node); 445 if (dns_rdataset_isassociated(&ardataset)) { 446 dns_rdataset_disassociate(&ardataset); 447 } 448 } 449 } 450 return (ISC_R_SUCCESS); 451 452 failure: 453 if (node != NULL) { 454 dns_db_detachnode(db, &node); 455 } 456 return (result); 457 } 458 459 isc_result_t 460 dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) { 461 return (diff_apply(diff, db, ver, true)); 462 } 463 464 isc_result_t 465 dns_diff_applysilently(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) { 466 return (diff_apply(diff, db, ver, false)); 467 } 468 469 /* XXX this duplicates lots of code in diff_apply(). */ 470 471 isc_result_t 472 dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc, 473 void *add_private) { 474 dns_difftuple_t *t; 475 isc_result_t result; 476 477 REQUIRE(DNS_DIFF_VALID(diff)); 478 479 t = ISC_LIST_HEAD(diff->tuples); 480 while (t != NULL) { 481 dns_name_t *name; 482 483 name = &t->name; 484 while (t != NULL && dns_name_caseequal(&t->name, name)) { 485 dns_rdatatype_t type, covers; 486 dns_diffop_t op; 487 dns_rdatalist_t rdl; 488 dns_rdataset_t rds; 489 490 op = t->op; 491 type = t->rdata.type; 492 covers = rdata_covers(&t->rdata); 493 494 dns_rdatalist_init(&rdl); 495 rdl.type = type; 496 rdl.covers = covers; 497 rdl.rdclass = t->rdata.rdclass; 498 rdl.ttl = t->ttl; 499 500 while (t != NULL && 501 dns_name_caseequal(&t->name, name) && 502 t->op == op && t->rdata.type == type && 503 rdata_covers(&t->rdata) == covers) 504 { 505 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link); 506 t = ISC_LIST_NEXT(t, link); 507 } 508 509 /* 510 * Convert the rdatalist into a rdataset. 511 */ 512 dns_rdataset_init(&rds); 513 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 514 rds.trust = dns_trust_ultimate; 515 516 INSIST(op == DNS_DIFFOP_ADD); 517 result = (*addfunc)(add_private, name, &rds); 518 if (result == DNS_R_UNCHANGED) { 519 isc_log_write(DIFF_COMMON_LOGARGS, 520 ISC_LOG_WARNING, 521 "dns_diff_load: " 522 "update with no effect"); 523 } else if (result == ISC_R_SUCCESS || 524 result == DNS_R_NXRRSET) { 525 /* 526 * OK. 527 */ 528 } else { 529 CHECK(result); 530 } 531 } 532 } 533 result = ISC_R_SUCCESS; 534 failure: 535 return (result); 536 } 537 538 /* 539 * XXX uses qsort(); a merge sort would be more natural for lists, 540 * and perhaps safer wrt thread stack overflow. 541 */ 542 isc_result_t 543 dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) { 544 unsigned int length = 0; 545 unsigned int i; 546 dns_difftuple_t **v; 547 dns_difftuple_t *p; 548 REQUIRE(DNS_DIFF_VALID(diff)); 549 550 for (p = ISC_LIST_HEAD(diff->tuples); p != NULL; 551 p = ISC_LIST_NEXT(p, link)) { 552 length++; 553 } 554 if (length == 0) { 555 return (ISC_R_SUCCESS); 556 } 557 v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *)); 558 for (i = 0; i < length; i++) { 559 p = ISC_LIST_HEAD(diff->tuples); 560 v[i] = p; 561 ISC_LIST_UNLINK(diff->tuples, p, link); 562 } 563 INSIST(ISC_LIST_HEAD(diff->tuples) == NULL); 564 qsort(v, length, sizeof(v[0]), compare); 565 for (i = 0; i < length; i++) { 566 ISC_LIST_APPEND(diff->tuples, v[i], link); 567 } 568 isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *)); 569 return (ISC_R_SUCCESS); 570 } 571 572 /* 573 * Create an rdataset containing the single RR of the given 574 * tuple. The caller must allocate the rdata, rdataset and 575 * an rdatalist structure for it to refer to. 576 */ 577 578 static isc_result_t 579 diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata, 580 dns_rdatalist_t *rdl, dns_rdataset_t *rds) { 581 REQUIRE(DNS_DIFFTUPLE_VALID(t)); 582 REQUIRE(rdl != NULL); 583 REQUIRE(rds != NULL); 584 585 dns_rdatalist_init(rdl); 586 rdl->type = t->rdata.type; 587 rdl->rdclass = t->rdata.rdclass; 588 rdl->ttl = t->ttl; 589 dns_rdataset_init(rds); 590 ISC_LINK_INIT(rdata, link); 591 dns_rdata_clone(&t->rdata, rdata); 592 ISC_LIST_APPEND(rdl->rdata, rdata, link); 593 return (dns_rdatalist_tordataset(rdl, rds)); 594 } 595 596 isc_result_t 597 dns_diff_print(dns_diff_t *diff, FILE *file) { 598 isc_result_t result; 599 dns_difftuple_t *t; 600 char *mem = NULL; 601 unsigned int size = 2048; 602 const char *op = NULL; 603 604 REQUIRE(DNS_DIFF_VALID(diff)); 605 606 mem = isc_mem_get(diff->mctx, size); 607 608 for (t = ISC_LIST_HEAD(diff->tuples); t != NULL; 609 t = ISC_LIST_NEXT(t, link)) { 610 isc_buffer_t buf; 611 isc_region_t r; 612 613 dns_rdatalist_t rdl; 614 dns_rdataset_t rds; 615 dns_rdata_t rd = DNS_RDATA_INIT; 616 617 result = diff_tuple_tordataset(t, &rd, &rdl, &rds); 618 if (result != ISC_R_SUCCESS) { 619 UNEXPECTED_ERROR(__FILE__, __LINE__, 620 "diff_tuple_tordataset failed: %s", 621 dns_result_totext(result)); 622 result = ISC_R_UNEXPECTED; 623 goto cleanup; 624 } 625 again: 626 isc_buffer_init(&buf, mem, size); 627 result = dns_rdataset_totext(&rds, &t->name, false, false, 628 &buf); 629 630 if (result == ISC_R_NOSPACE) { 631 isc_mem_put(diff->mctx, mem, size); 632 size += 1024; 633 mem = isc_mem_get(diff->mctx, size); 634 goto again; 635 } 636 637 if (result != ISC_R_SUCCESS) { 638 goto cleanup; 639 } 640 /* 641 * Get rid of final newline. 642 */ 643 INSIST(buf.used >= 1 && 644 ((char *)buf.base)[buf.used - 1] == '\n'); 645 buf.used--; 646 647 isc_buffer_usedregion(&buf, &r); 648 switch (t->op) { 649 case DNS_DIFFOP_EXISTS: 650 op = "exists"; 651 break; 652 case DNS_DIFFOP_ADD: 653 op = "add"; 654 break; 655 case DNS_DIFFOP_DEL: 656 op = "del"; 657 break; 658 case DNS_DIFFOP_ADDRESIGN: 659 op = "add re-sign"; 660 break; 661 case DNS_DIFFOP_DELRESIGN: 662 op = "del re-sign"; 663 break; 664 } 665 if (file != NULL) { 666 fprintf(file, "%s %.*s\n", op, (int)r.length, 667 (char *)r.base); 668 } else { 669 isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7), 670 "%s %.*s", op, (int)r.length, 671 (char *)r.base); 672 } 673 } 674 result = ISC_R_SUCCESS; 675 cleanup: 676 if (mem != NULL) { 677 isc_mem_put(diff->mctx, mem, size); 678 } 679 return (result); 680 } 681