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

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