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