contrib/bind-9.5.2/lib/dns/diff.c

   1 /*
   2  * Copyright (C) 2004, 2005, 2007, 2009  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 2000-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: diff.c,v 1.14.128.3 2009/01/06 23:46:47 tbox Exp $ */
  19
  20 /*! \file */
  21
  22 #include <config.h>
  23
  24 #include <stdlib.h>
  25
  26 #include <isc/buffer.h>
  27 #include <isc/file.h>
  28 #include <isc/mem.h>
  29 #include <isc/string.h>
  30 #include <isc/util.h>
  31
  32 #include <dns/db.h>
  33 #include <dns/diff.h>
  34 #include <dns/log.h>
  35 #include <dns/rdataclass.h>
  36 #include <dns/rdatalist.h>
  37 #include <dns/rdataset.h>
  38 #include <dns/rdatatype.h>
  39 #include <dns/result.h>
  40
  41 #define CHECK(op) \
  42         do { result = (op);                                     \
  43                 if (result != ISC_R_SUCCESS) goto failure;      \
  44         } while (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, 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 = mctx;
  76         t->op = op;
  77
  78         datap = (unsigned char *)(t + 1);
  79
  80         memcpy(datap, name->ndata, name->length);
  81         dns_name_init(&t->name, NULL);
  82         dns_name_clone(name, &t->name);
  83         t->name.ndata = datap;
  84         datap += name->length;
  85
  86         t->ttl = ttl;
  87
  88         memcpy(datap, rdata->data, rdata->length);
  89         dns_rdata_init(&t->rdata);
  90         dns_rdata_clone(rdata, &t->rdata);
  91         t->rdata.data = datap;
  92         datap += rdata->length;
  93
  94         ISC_LINK_INIT(&t->rdata, link);
  95         ISC_LINK_INIT(t, link);
  96         t->magic = DNS_DIFFTUPLE_MAGIC;
  97
  98         INSIST(datap == (unsigned char *)t + size);
  99
 100         *tp = t;
 101         return (ISC_R_SUCCESS);
 102 }
 103
 104 void
 105 dns_difftuple_free(dns_difftuple_t **tp) {
 106         dns_difftuple_t *t = *tp;
 107         REQUIRE(DNS_DIFFTUPLE_VALID(t));
 108         dns_name_invalidate(&t->name);
 109         t->magic = 0;
 110         isc_mem_free(t->mctx, t);
 111         *tp = NULL;
 112 }
 113
 114 isc_result_t
 115 dns_difftuple_copy(dns_difftuple_t *orig, dns_difftuple_t **copyp) {
 116         return (dns_difftuple_create(orig->mctx, orig->op, &orig->name,
 117                                      orig->ttl, &orig->rdata, copyp));
 118 }
 119
 120 void
 121 dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) {
 122         diff->mctx = mctx;
 123         ISC_LIST_INIT(diff->tuples);
 124         diff->magic = DNS_DIFF_MAGIC;
 125 }
 126
 127 void
 128 dns_diff_clear(dns_diff_t *diff) {
 129         dns_difftuple_t *t;
 130         REQUIRE(DNS_DIFF_VALID(diff));
 131         while ((t = ISC_LIST_HEAD(diff->tuples)) != NULL) {
 132                 ISC_LIST_UNLINK(diff->tuples, t, link);
 133                 dns_difftuple_free(&t);
 134         }
 135         ENSURE(ISC_LIST_EMPTY(diff->tuples));
 136 }
 137
 138 void
 139 dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep)
 140 {
 141         ISC_LIST_APPEND(diff->tuples, *tuplep, link);
 142         *tuplep = NULL;
 143 }
 144
 145 /* XXX this is O(N) */
 146
 147 void
 148 dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep)
 149 {
 150         dns_difftuple_t *ot, *next_ot;
 151
 152         REQUIRE(DNS_DIFF_VALID(diff));
 153         REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep));
 154
 155         /*
 156          * Look for an existing tuple with the same owner name,
 157          * rdata, and TTL.   If we are doing an addition and find a
 158          * deletion or vice versa, remove both the old and the
 159          * new tuple since they cancel each other out (assuming
 160          * that we never delete nonexistent data or add existing
 161          * data).
 162          *
 163          * If we find an old update of the same kind as
 164          * the one we are doing, there must be a programming
 165          * error.  We report it but try to continue anyway.
 166          */
 167         for (ot = ISC_LIST_HEAD(diff->tuples); ot != NULL;
 168              ot = next_ot)
 169         {
 170                 next_ot = ISC_LIST_NEXT(ot, link);
 171                 if (dns_name_equal(&ot->name, &(*tuplep)->name) &&
 172                     dns_rdata_compare(&ot->rdata, &(*tuplep)->rdata) == 0 &&
 173                     ot->ttl == (*tuplep)->ttl)
 174                 {
 175                         ISC_LIST_UNLINK(diff->tuples, ot, link);
 176                         if ((*tuplep)->op == ot->op) {
 177                                 UNEXPECTED_ERROR(__FILE__, __LINE__,
 178                                          "unexpected non-minimal diff");
 179                         } else {
 180                                 dns_difftuple_free(tuplep);
 181                         }
 182                         dns_difftuple_free(&ot);
 183                         break;
 184                 }
 185         }
 186
 187         if (*tuplep != NULL) {
 188                 ISC_LIST_APPEND(diff->tuples, *tuplep, link);
 189                 *tuplep = NULL;
 190         }
 191
 192         ENSURE(*tuplep == NULL);
 193 }
 194
 195 static isc_result_t
 196 diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver,
 197            isc_boolean_t warn)
 198 {
 199         dns_difftuple_t *t;
 200         dns_dbnode_t *node = NULL;
 201         isc_result_t result;
 202         char namebuf[DNS_NAME_FORMATSIZE];
 203         char typebuf[DNS_RDATATYPE_FORMATSIZE];
 204         char classbuf[DNS_RDATACLASS_FORMATSIZE];
 205
 206         REQUIRE(DNS_DIFF_VALID(diff));
 207         REQUIRE(DNS_DB_VALID(db));
 208
 209         t = ISC_LIST_HEAD(diff->tuples);
 210         while (t != NULL) {
 211                 dns_name_t *name;
 212
 213                 INSIST(node == NULL);
 214                 name = &t->name;
 215                 /*
 216                  * Find the node.
 217                  * We create the node if it does not exist.
 218                  * This will cause an empty node to be created if the diff
 219                  * contains a deletion of an RR at a nonexistent name,
 220                  * but such diffs should never be created in the first
 221                  * place.
 222                  */
 223                 node = NULL;
 224                 CHECK(dns_db_findnode(db, name, ISC_TRUE, &node));
 225
 226                 while (t != NULL && dns_name_equal(&t->name, name)) {
 227                         dns_rdatatype_t type, covers;
 228                         dns_diffop_t op;
 229                         dns_rdatalist_t rdl;
 230                         dns_rdataset_t rds;
 231
 232                         op = t->op;
 233                         type = t->rdata.type;
 234                         covers = rdata_covers(&t->rdata);
 235
 236                         /*
 237                          * Collect a contiguous set of updates with
 238                          * the same operation (add/delete) and RR type
 239                          * into a single rdatalist so that the
 240                          * database rrset merging/subtraction code
 241                          * can work more efficiently than if each
 242                          * RR were merged into / subtracted from
 243                          * the database separately.
 244                          *
 245                          * This is done by linking rdata structures from the
 246                          * diff into "rdatalist".  This uses the rdata link
 247                          * field, not the diff link field, so the structure
 248                          * of the diff itself is not affected.
 249                          */
 250
 251                         rdl.type = type;
 252                         rdl.covers = covers;
 253                         rdl.rdclass = t->rdata.rdclass;
 254                         rdl.ttl = t->ttl;
 255                         ISC_LIST_INIT(rdl.rdata);
 256                         ISC_LINK_INIT(&rdl, link);
 257
 258                         while (t != NULL &&
 259                                dns_name_equal(&t->name, name) &&
 260                                t->op == op &&
 261                                t->rdata.type == type &&
 262                                rdata_covers(&t->rdata) == covers)
 263                         {
 264                                 dns_name_format(name, namebuf, sizeof(namebuf));
 265                                 dns_rdatatype_format(t->rdata.type, typebuf,
 266                                                      sizeof(typebuf));
 267                                 dns_rdataclass_format(t->rdata.rdclass,
 268                                                       classbuf,
 269                                                       sizeof(classbuf));
 270                                 if (t->ttl != rdl.ttl && warn)
 271                                         isc_log_write(DIFF_COMMON_LOGARGS,
 272                                                 ISC_LOG_WARNING,
 273                                                 "'%s/%s/%s': TTL differs in "
 274                                                 "rdataset, adjusting "
 275                                                 "%lu -> %lu",
 276                                                 namebuf, typebuf, classbuf,
 277                                                 (unsigned long) t->ttl,
 278                                                 (unsigned long) rdl.ttl);
 279                                 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
 280                                 t = ISC_LIST_NEXT(t, link);
 281                         }
 282
 283                         /*
 284                          * Convert the rdatalist into a rdataset.
 285                          */
 286                         dns_rdataset_init(&rds);
 287                         CHECK(dns_rdatalist_tordataset(&rdl, &rds));
 288                         rds.trust = dns_trust_ultimate;
 289
 290                         /*
 291                          * Merge the rdataset into the database.
 292                          */
 293                         if (op == DNS_DIFFOP_ADD) {
 294                                 result = dns_db_addrdataset(db, node, ver,
 295                                                             0, &rds,
 296                                                             DNS_DBADD_MERGE|
 297                                                             DNS_DBADD_EXACT|
 298                                                             DNS_DBADD_EXACTTTL,
 299                                                             NULL);
 300                         } else if (op == DNS_DIFFOP_DEL) {
 301                                 result = dns_db_subtractrdataset(db, node, ver,
 302                                                                &rds,
 303                                                                DNS_DBSUB_EXACT,
 304                                                                NULL);
 305                         } else {
 306                                 INSIST(0);
 307                         }
 308                         if (result == DNS_R_UNCHANGED) {
 309                                 /*
 310                                  * This will not happen when executing a
 311                                  * dynamic update, because that code will
 312                                  * generate strictly minimal diffs.
 313                                  * It may happen when receiving an IXFR
 314                                  * from a server that is not as careful.
 315                                  * Issue a warning and continue.
 316                                  */
 317                                 if (warn)
 318                                         isc_log_write(DIFF_COMMON_LOGARGS,
 319                                                       ISC_LOG_WARNING,
 320                                                       "update with no effect");
 321                         } else if (result == ISC_R_SUCCESS ||
 322                                    result == DNS_R_NXRRSET) {
 323                                 /*
 324                                  * OK.
 325                                  */
 326                         } else {
 327                                 CHECK(result);
 328                         }
 329                 }
 330                 dns_db_detachnode(db, &node);
 331         }
 332         return (ISC_R_SUCCESS);
 333
 334  failure:
 335         if (node != NULL)
 336                 dns_db_detachnode(db, &node);
 337         return (result);
 338 }
 339
 340 isc_result_t
 341 dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
 342         return (diff_apply(diff, db, ver, ISC_TRUE));
 343 }
 344
 345 isc_result_t
 346 dns_diff_applysilently(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
 347         return (diff_apply(diff, db, ver, ISC_FALSE));
 348 }
 349
 350 /* XXX this duplicates lots of code in diff_apply(). */
 351
 352 isc_result_t
 353 dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc,
 354               void *add_private)
 355 {
 356         dns_difftuple_t *t;
 357         isc_result_t result;
 358
 359         REQUIRE(DNS_DIFF_VALID(diff));
 360
 361         t = ISC_LIST_HEAD(diff->tuples);
 362         while (t != NULL) {
 363                 dns_name_t *name;
 364
 365                 name = &t->name;
 366                 while (t != NULL && dns_name_equal(&t->name, name)) {
 367                         dns_rdatatype_t type, covers;
 368                         dns_diffop_t op;
 369                         dns_rdatalist_t rdl;
 370                         dns_rdataset_t rds;
 371
 372                         op = t->op;
 373                         type = t->rdata.type;
 374                         covers = rdata_covers(&t->rdata);
 375
 376                         rdl.type = type;
 377                         rdl.covers = covers;
 378                         rdl.rdclass = t->rdata.rdclass;
 379                         rdl.ttl = t->ttl;
 380                         ISC_LIST_INIT(rdl.rdata);
 381                         ISC_LINK_INIT(&rdl, link);
 382
 383                         while (t != NULL && dns_name_equal(&t->name, name) &&
 384                                t->op == op && t->rdata.type == type &&
 385                                rdata_covers(&t->rdata) == covers)
 386                         {
 387                                 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
 388                                 t = ISC_LIST_NEXT(t, link);
 389                         }
 390
 391                         /*
 392                          * Convert the rdatalist into a rdataset.
 393                          */
 394                         dns_rdataset_init(&rds);
 395                         CHECK(dns_rdatalist_tordataset(&rdl, &rds));
 396                         rds.trust = dns_trust_ultimate;
 397
 398                         INSIST(op == DNS_DIFFOP_ADD);
 399                         result = (*addfunc)(add_private, name, &rds);
 400                         if (result == DNS_R_UNCHANGED) {
 401                                 isc_log_write(DIFF_COMMON_LOGARGS,
 402                                               ISC_LOG_WARNING,
 403                                               "update with no effect");
 404                         } else if (result == ISC_R_SUCCESS ||
 405                                    result == DNS_R_NXRRSET) {
 406                                 /*
 407                                  * OK.
 408                                  */
 409                         } else {
 410                                 CHECK(result);
 411                         }
 412                 }
 413         }
 414         result = ISC_R_SUCCESS;
 415  failure:
 416         return (result);
 417 }
 418
 419 /*
 420  * XXX uses qsort(); a merge sort would be more natural for lists,
 421  * and perhaps safer wrt thread stack overflow.
 422  */
 423 isc_result_t
 424 dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) {
 425         unsigned int length = 0;
 426         unsigned int i;
 427         dns_difftuple_t **v;
 428         dns_difftuple_t *p;
 429         REQUIRE(DNS_DIFF_VALID(diff));
 430
 431         for (p = ISC_LIST_HEAD(diff->tuples);
 432              p != NULL;
 433              p = ISC_LIST_NEXT(p, link))
 434                 length++;
 435         if (length == 0)
 436                 return (ISC_R_SUCCESS);
 437         v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *));
 438         if (v == NULL)
 439                 return (ISC_R_NOMEMORY);
 440         i = 0;
 441         for (i = 0; i < length; i++) {
 442                 p = ISC_LIST_HEAD(diff->tuples);
 443                 v[i] = p;
 444                 ISC_LIST_UNLINK(diff->tuples, p, link);
 445         }
 446         INSIST(ISC_LIST_HEAD(diff->tuples) == NULL);
 447         qsort(v, length, sizeof(v[0]), compare);
 448         for (i = 0; i < length; i++) {
 449                 ISC_LIST_APPEND(diff->tuples, v[i], link);
 450         }
 451         isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *));
 452         return (ISC_R_SUCCESS);
 453 }
 454
 455
 456 /*
 457  * Create an rdataset containing the single RR of the given
 458  * tuple.  The caller must allocate the rdata, rdataset and
 459  * an rdatalist structure for it to refer to.
 460  */
 461
 462 static isc_result_t
 463 diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata,
 464                       dns_rdatalist_t *rdl, dns_rdataset_t *rds)
 465 {
 466         REQUIRE(DNS_DIFFTUPLE_VALID(t));
 467         REQUIRE(rdl != NULL);
 468         REQUIRE(rds != NULL);
 469
 470         rdl->type = t->rdata.type;
 471         rdl->rdclass = t->rdata.rdclass;
 472         rdl->ttl = t->ttl;
 473         ISC_LIST_INIT(rdl->rdata);
 474         ISC_LINK_INIT(rdl, link);
 475         dns_rdataset_init(rds);
 476         ISC_LINK_INIT(rdata, link);
 477         dns_rdata_clone(&t->rdata, rdata);
 478         ISC_LIST_APPEND(rdl->rdata, rdata, link);
 479         return (dns_rdatalist_tordataset(rdl, rds));
 480 }
 481
 482 isc_result_t
 483 dns_diff_print(dns_diff_t *diff, FILE *file) {
 484         isc_result_t result;
 485         dns_difftuple_t *t;
 486         char *mem = NULL;
 487         unsigned int size = 2048;
 488
 489         REQUIRE(DNS_DIFF_VALID(diff));
 490
 491         mem = isc_mem_get(diff->mctx, size);
 492         if (mem == NULL)
 493                 return (ISC_R_NOMEMORY);
 494
 495         for (t = ISC_LIST_HEAD(diff->tuples); t != NULL;
 496              t = ISC_LIST_NEXT(t, link))
 497         {
 498                 isc_buffer_t buf;
 499                 isc_region_t r;
 500
 501                 dns_rdatalist_t rdl;
 502                 dns_rdataset_t rds;
 503                 dns_rdata_t rd = DNS_RDATA_INIT;
 504
 505                 result = diff_tuple_tordataset(t, &rd, &rdl, &rds);
 506                 if (result != ISC_R_SUCCESS) {
 507                         UNEXPECTED_ERROR(__FILE__, __LINE__,
 508                                          "diff_tuple_tordataset failed: %s",
 509                                          dns_result_totext(result));
 510                         result =  ISC_R_UNEXPECTED;
 511                         goto cleanup;
 512                 }
 513  again:
 514                 isc_buffer_init(&buf, mem, size);
 515                 result = dns_rdataset_totext(&rds, &t->name,
 516                                              ISC_FALSE, ISC_FALSE, &buf);
 517
 518                 if (result == ISC_R_NOSPACE) {
 519                         isc_mem_put(diff->mctx, mem, size);
 520                         size += 1024;
 521                         mem = isc_mem_get(diff->mctx, size);
 522                         if (mem == NULL) {
 523                                 result = ISC_R_NOMEMORY;
 524                                 goto cleanup;
 525                         }
 526                         goto again;
 527                 }
 528
 529                 if (result != ISC_R_SUCCESS)
 530                         goto cleanup;
 531                 /*
 532                  * Get rid of final newline.
 533                  */
 534                 INSIST(buf.used >= 1 &&
 535                        ((char *) buf.base)[buf.used-1] == '\n');
 536                 buf.used--;
 537
 538                 isc_buffer_usedregion(&buf, &r);
 539                 if (file != NULL)
 540                         fprintf(file, "%s %.*s\n",
 541                                 t->op == DNS_DIFFOP_ADD ?  "add" : "del",
 542                                 (int) r.length, (char *) r.base);
 543                 else
 544                         isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7),
 545                                       "%s %.*s",
 546                                       t->op == DNS_DIFFOP_ADD ?  "add" : "del",
 547                                       (int) r.length, (char *) r.base);
 548         }
 549         result = ISC_R_SUCCESS;
 550  cleanup:
 551         if (mem != NULL)
 552                 isc_mem_put(diff->mctx, mem, size);
 553         return (result);
 554 }