1/* $NetBSD: diff.c,v 1.1 2024/02/18 20:57:31 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 50static dns_rdatatype_t 51rdata_covers(dns_rdata_t *rdata) { 52 return (rdata->type == dns_rdatatype_rrsig ? dns_rdata_covers(rdata) 53 : 0); 54} 55 56isc_result_t 57dns_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 107void 108dns_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 122isc_result_t 123dns_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 128void 129dns_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 135void 136dns_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 146void 147dns_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 154void 155dns_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 197static isc_stdtime_t 198setresign(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 233static void 234getownercase(dns_rdataset_t *rdataset, dns_name_t *name) { 235 if (dns_rdataset_isassociated(rdataset)) { 236 dns_rdataset_getownercase(rdataset, name); 237 } 238} 239 240static void 241setownercase(dns_rdataset_t *rdataset, const dns_name_t *name) { 242 if (dns_rdataset_isassociated(rdataset)) { 243 dns_rdataset_setownercase(rdataset, name); 244 } 245} 246 247static isc_result_t 248diff_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 { 311 CHECK(dns_db_findnode(db, name, true, &node)); 312 } else { 313 CHECK(dns_db_findnsec3node(db, name, true, 314 &node)); 315 } 316 317 while (t != NULL && dns_name_equal(&t->name, name) && 318 t->op == op && t->rdata.type == type && 319 rdata_covers(&t->rdata) == covers) 320 { 321 /* 322 * Remember the add name for 323 * dns_rdataset_setownercase. 324 */ 325 name = &t->name; 326 if (t->ttl != rdl.ttl && warn) { 327 dns_name_format(name, namebuf, 328 sizeof(namebuf)); 329 dns_rdatatype_format(t->rdata.type, 330 typebuf, 331 sizeof(typebuf)); 332 dns_rdataclass_format(t->rdata.rdclass, 333 classbuf, 334 sizeof(classbuf)); 335 isc_log_write(DIFF_COMMON_LOGARGS, 336 ISC_LOG_WARNING, 337 "'%s/%s/%s': TTL differs " 338 "in " 339 "rdataset, adjusting " 340 "%lu -> %lu", 341 namebuf, typebuf, 342 classbuf, 343 (unsigned long)t->ttl, 344 (unsigned long)rdl.ttl); 345 } 346 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link); 347 t = ISC_LIST_NEXT(t, link); 348 } 349 350 /* 351 * Convert the rdatalist into a rdataset. 352 */ 353 dns_rdataset_init(&rds); 354 dns_rdataset_init(&ardataset); 355 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 356 rds.trust = dns_trust_ultimate; 357 358 /* 359 * Merge the rdataset into the database. 360 */ 361 switch (op) { 362 case DNS_DIFFOP_ADD: 363 case DNS_DIFFOP_ADDRESIGN: 364 options = DNS_DBADD_MERGE | DNS_DBADD_EXACT | 365 DNS_DBADD_EXACTTTL; 366 result = dns_db_addrdataset(db, node, ver, 0, 367 &rds, options, 368 &ardataset); 369 break; 370 case DNS_DIFFOP_DEL: 371 case DNS_DIFFOP_DELRESIGN: 372 options = DNS_DBSUB_EXACT | DNS_DBSUB_WANTOLD; 373 result = dns_db_subtractrdataset(db, node, ver, 374 &rds, options, 375 &ardataset); 376 break; 377 default: 378 UNREACHABLE(); 379 } 380 381 if (result == ISC_R_SUCCESS) { 382 if (rds.type == dns_rdatatype_rrsig && 383 (op == DNS_DIFFOP_DELRESIGN || 384 op == DNS_DIFFOP_ADDRESIGN)) 385 { 386 isc_stdtime_t resign; 387 resign = setresign(&ardataset); 388 dns_db_setsigningtime(db, &ardataset, 389 resign); 390 } 391 if (op == DNS_DIFFOP_ADD || 392 op == DNS_DIFFOP_ADDRESIGN) 393 { 394 setownercase(&ardataset, name); 395 } 396 if (op == DNS_DIFFOP_DEL || 397 op == DNS_DIFFOP_DELRESIGN) 398 { 399 getownercase(&ardataset, name); 400 } 401 } else if (result == DNS_R_UNCHANGED) { 402 /* 403 * This will not happen when executing a 404 * dynamic update, because that code will 405 * generate strictly minimal diffs. 406 * It may happen when receiving an IXFR 407 * from a server that is not as careful. 408 * Issue a warning and continue. 409 */ 410 if (warn) { 411 dns_name_format(dns_db_origin(db), 412 namebuf, 413 sizeof(namebuf)); 414 dns_rdataclass_format(dns_db_class(db), 415 classbuf, 416 sizeof(classbuf)); 417 isc_log_write(DIFF_COMMON_LOGARGS, 418 ISC_LOG_WARNING, 419 "%s/%s: dns_diff_apply: " 420 "update with no effect", 421 namebuf, classbuf); 422 } 423 if (op == DNS_DIFFOP_ADD || 424 op == DNS_DIFFOP_ADDRESIGN) 425 { 426 setownercase(&ardataset, name); 427 } 428 if (op == DNS_DIFFOP_DEL || 429 op == DNS_DIFFOP_DELRESIGN) 430 { 431 getownercase(&ardataset, name); 432 } 433 } else if (result == DNS_R_NXRRSET) { 434 /* 435 * OK. 436 */ 437 if (op == DNS_DIFFOP_DEL || 438 op == DNS_DIFFOP_DELRESIGN) 439 { 440 getownercase(&ardataset, name); 441 } 442 if (dns_rdataset_isassociated(&ardataset)) { 443 dns_rdataset_disassociate(&ardataset); 444 } 445 } else { 446 if (dns_rdataset_isassociated(&ardataset)) { 447 dns_rdataset_disassociate(&ardataset); 448 } 449 CHECK(result); 450 } 451 dns_db_detachnode(db, &node); 452 if (dns_rdataset_isassociated(&ardataset)) { 453 dns_rdataset_disassociate(&ardataset); 454 } 455 } 456 } 457 return (ISC_R_SUCCESS); 458 459failure: 460 if (node != NULL) { 461 dns_db_detachnode(db, &node); 462 } 463 return (result); 464} 465 466isc_result_t 467dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) { 468 return (diff_apply(diff, db, ver, true)); 469} 470 471isc_result_t 472dns_diff_applysilently(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) { 473 return (diff_apply(diff, db, ver, false)); 474} 475 476/* XXX this duplicates lots of code in diff_apply(). */ 477 478isc_result_t 479dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc, 480 void *add_private) { 481 dns_difftuple_t *t; 482 isc_result_t result; 483 484 REQUIRE(DNS_DIFF_VALID(diff)); 485 486 t = ISC_LIST_HEAD(diff->tuples); 487 while (t != NULL) { 488 dns_name_t *name; 489 490 name = &t->name; 491 while (t != NULL && dns_name_caseequal(&t->name, name)) { 492 dns_rdatatype_t type, covers; 493 dns_diffop_t op; 494 dns_rdatalist_t rdl; 495 dns_rdataset_t rds; 496 497 op = t->op; 498 type = t->rdata.type; 499 covers = rdata_covers(&t->rdata); 500 501 dns_rdatalist_init(&rdl); 502 rdl.type = type; 503 rdl.covers = covers; 504 rdl.rdclass = t->rdata.rdclass; 505 rdl.ttl = t->ttl; 506 507 while (t != NULL && 508 dns_name_caseequal(&t->name, name) && 509 t->op == op && t->rdata.type == type && 510 rdata_covers(&t->rdata) == covers) 511 { 512 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link); 513 t = ISC_LIST_NEXT(t, link); 514 } 515 516 /* 517 * Convert the rdatalist into a rdataset. 518 */ 519 dns_rdataset_init(&rds); 520 CHECK(dns_rdatalist_tordataset(&rdl, &rds)); 521 rds.trust = dns_trust_ultimate; 522 523 INSIST(op == DNS_DIFFOP_ADD); 524 result = (*addfunc)(add_private, name, &rds); 525 if (result == DNS_R_UNCHANGED) { 526 isc_log_write(DIFF_COMMON_LOGARGS, 527 ISC_LOG_WARNING, 528 "dns_diff_load: " 529 "update with no effect"); 530 } else if (result == ISC_R_SUCCESS || 531 result == DNS_R_NXRRSET) 532 { 533 /* 534 * OK. 535 */ 536 } else { 537 CHECK(result); 538 } 539 } 540 } 541 result = ISC_R_SUCCESS; 542failure: 543 return (result); 544} 545 546/* 547 * XXX uses qsort(); a merge sort would be more natural for lists, 548 * and perhaps safer wrt thread stack overflow. 549 */ 550isc_result_t 551dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) { 552 unsigned int length = 0; 553 unsigned int i; 554 dns_difftuple_t **v; 555 dns_difftuple_t *p; 556 REQUIRE(DNS_DIFF_VALID(diff)); 557 558 for (p = ISC_LIST_HEAD(diff->tuples); p != NULL; 559 p = ISC_LIST_NEXT(p, link)) 560 { 561 length++; 562 } 563 if (length == 0) { 564 return (ISC_R_SUCCESS); 565 } 566 v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *)); 567 for (i = 0; i < length; i++) { 568 p = ISC_LIST_HEAD(diff->tuples); 569 v[i] = p; 570 ISC_LIST_UNLINK(diff->tuples, p, link); 571 } 572 INSIST(ISC_LIST_HEAD(diff->tuples) == NULL); 573 qsort(v, length, sizeof(v[0]), compare); 574 for (i = 0; i < length; i++) { 575 ISC_LIST_APPEND(diff->tuples, v[i], link); 576 } 577 isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *)); 578 return (ISC_R_SUCCESS); 579} 580 581/* 582 * Create an rdataset containing the single RR of the given 583 * tuple. The caller must allocate the rdata, rdataset and 584 * an rdatalist structure for it to refer to. 585 */ 586 587static isc_result_t 588diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata, 589 dns_rdatalist_t *rdl, dns_rdataset_t *rds) { 590 REQUIRE(DNS_DIFFTUPLE_VALID(t)); 591 REQUIRE(rdl != NULL); 592 REQUIRE(rds != NULL); 593 594 dns_rdatalist_init(rdl); 595 rdl->type = t->rdata.type; 596 rdl->rdclass = t->rdata.rdclass; 597 rdl->ttl = t->ttl; 598 dns_rdataset_init(rds); 599 ISC_LINK_INIT(rdata, link); 600 dns_rdata_clone(&t->rdata, rdata); 601 ISC_LIST_APPEND(rdl->rdata, rdata, link); 602 return (dns_rdatalist_tordataset(rdl, rds)); 603} 604 605isc_result_t 606dns_diff_print(dns_diff_t *diff, FILE *file) { 607 isc_result_t result; 608 dns_difftuple_t *t; 609 char *mem = NULL; 610 unsigned int size = 2048; 611 const char *op = NULL; 612 613 REQUIRE(DNS_DIFF_VALID(diff)); 614 615 mem = isc_mem_get(diff->mctx, size); 616 617 for (t = ISC_LIST_HEAD(diff->tuples); t != NULL; 618 t = ISC_LIST_NEXT(t, link)) 619 { 620 isc_buffer_t buf; 621 isc_region_t r; 622 623 dns_rdatalist_t rdl; 624 dns_rdataset_t rds; 625 dns_rdata_t rd = DNS_RDATA_INIT; 626 627 result = diff_tuple_tordataset(t, &rd, &rdl, &rds); 628 if (result != ISC_R_SUCCESS) { 629 UNEXPECTED_ERROR(__FILE__, __LINE__, 630 "diff_tuple_tordataset failed: %s", 631 dns_result_totext(result)); 632 result = ISC_R_UNEXPECTED; 633 goto cleanup; 634 } 635 again: 636 isc_buffer_init(&buf, mem, size); 637 result = dns_rdataset_totext(&rds, &t->name, false, false, 638 &buf); 639 640 if (result == ISC_R_NOSPACE) { 641 isc_mem_put(diff->mctx, mem, size); 642 size += 1024; 643 mem = isc_mem_get(diff->mctx, size); 644 goto again; 645 } 646 647 if (result != ISC_R_SUCCESS) { 648 goto cleanup; 649 } 650 /* 651 * Get rid of final newline. 652 */ 653 INSIST(buf.used >= 1 && 654 ((char *)buf.base)[buf.used - 1] == '\n'); 655 buf.used--; 656 657 isc_buffer_usedregion(&buf, &r); 658 switch (t->op) { 659 case DNS_DIFFOP_EXISTS: 660 op = "exists"; 661 break; 662 case DNS_DIFFOP_ADD: 663 op = "add"; 664 break; 665 case DNS_DIFFOP_DEL: 666 op = "del"; 667 break; 668 case DNS_DIFFOP_ADDRESIGN: 669 op = "add re-sign"; 670 break; 671 case DNS_DIFFOP_DELRESIGN: 672 op = "del re-sign"; 673 break; 674 } 675 if (file != NULL) { 676 fprintf(file, "%s %.*s\n", op, (int)r.length, 677 (char *)r.base); 678 } else { 679 isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7), 680 "%s %.*s", op, (int)r.length, 681 (char *)r.base); 682 } 683 } 684 result = ISC_R_SUCCESS; 685cleanup: 686 if (mem != NULL) { 687 isc_mem_put(diff->mctx, mem, size); 688 } 689 return (result); 690} 691