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