contrib/bind9/lib/dns/rdataslab.c

   1 /*
   2  * Copyright (C) 2004-2007  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-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: rdataslab.c,v 1.35.18.8 2007/08/28 07:20:05 tbox Exp $ */
  19
  20 /*! \file */
  21
  22 #include <config.h>
  23
  24 #include <stdlib.h>
  25
  26 #include <isc/mem.h>
  27 #include <isc/region.h>
  28 #include <isc/string.h>         /* Required for HP/UX (and others?) */
  29 #include <isc/util.h>
  30
  31 #include <dns/result.h>
  32 #include <dns/rdata.h>
  33 #include <dns/rdataset.h>
  34 #include <dns/rdataslab.h>
  35
  36 #ifndef DNS_RDATASET_FIXED
  37 #define DNS_RDATASET_FIXED 1
  38 #endif
  39
  40 /*
  41  * The rdataslab structure allows iteration to occur in both load order
  42  * and DNSSEC order.  The structure is as follows:
  43  *
  44  *      header          (reservelen bytes)
  45  *      record count    (2 bytes)
  46  *      offset table    (4 x record count bytes in load order)
  47  *      data records
  48  *              data length     (2 bytes)
  49  *              order           (2 bytes)
  50  *              data            (data length bytes)
  51  *
  52  * If DNS_RDATASET_FIXED is defined to be zero (0) the format of a
  53  * rdataslab is as follows:
  54  *
  55  *      header          (reservelen bytes)
  56  *      record count    (2 bytes)
  57  *      data records
  58  *              data length     (2 bytes)
  59  *              data            (data length bytes)
  60  *
  61  * Offsets are from the end of the header.
  62  *
  63  * Load order traversal is performed by walking the offset table to find
  64  * the start of the record (DNS_RDATASET_FIXED = 1).
  65  *
  66  * DNSSEC order traversal is performed by walking the data records.
  67  *
  68  * The order is stored with record to allow for efficient reconstuction of
  69  * of the offset table following a merge or subtraction.
  70  *
  71  * The iterator methods here currently only support DNSSEC order iteration.
  72  *
  73  * The iterator methods in rbtdb support both load order and DNSSEC order
  74  * iteration.
  75  *
  76  * WARNING:
  77  *      rbtdb.c directly interacts with the slab's raw structures.  If the
  78  *      structure changes then rbtdb.c also needs to be updated to reflect
  79  *      the changes.  See the areas tagged with "RDATASLAB".
  80  */
  81
  82 struct xrdata {
  83         dns_rdata_t     rdata;
  84         unsigned int    order;
  85 };
  86
  87 /*% Note: the "const void *" are just to make qsort happy.  */
  88 static int
  89 compare_rdata(const void *p1, const void *p2) {
  90         const struct xrdata *x1 = p1;
  91         const struct xrdata *x2 = p2;
  92         return (dns_rdata_compare(&x1->rdata, &x2->rdata));
  93 }
  94
  95 #if DNS_RDATASET_FIXED
  96 static void
  97 fillin_offsets(unsigned char *offsetbase, unsigned int *offsettable,
  98                unsigned length)
  99 {
 100         unsigned int i, j;
 101         unsigned char *raw;
 102
 103         for (i = 0, j = 0; i < length; i++) {
 104
 105                 if (offsettable[i] == 0)
 106                         continue;
 107
 108                 /*
 109                  * Fill in offset table.
 110                  */
 111                 raw = &offsetbase[j*4 + 2];
 112                 *raw++ = (offsettable[i] & 0xff000000) >> 24;
 113                 *raw++ = (offsettable[i] & 0xff0000) >> 16;
 114                 *raw++ = (offsettable[i] & 0xff00) >> 8;
 115                 *raw = offsettable[i] & 0xff;
 116
 117                 /*
 118                  * Fill in table index.
 119                  */
 120                 raw = offsetbase + offsettable[i] + 2;
 121                 *raw++ = (j & 0xff00) >> 8;
 122                 *raw = j++ & 0xff;
 123         }
 124 }
 125 #endif
 126
 127 isc_result_t
 128 dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
 129                            isc_region_t *region, unsigned int reservelen)
 130 {
 131         struct xrdata  *x;
 132         unsigned char  *rawbuf;
 133 #if DNS_RDATASET_FIXED
 134         unsigned char  *offsetbase;
 135 #endif
 136         unsigned int    buflen;
 137         isc_result_t    result;
 138         unsigned int    nitems;
 139         unsigned int    nalloc;
 140         unsigned int    i;
 141 #if DNS_RDATASET_FIXED
 142         unsigned int   *offsettable;
 143 #endif
 144
 145         buflen = reservelen + 2;
 146
 147         nalloc = dns_rdataset_count(rdataset);
 148         nitems = nalloc;
 149         if (nitems == 0)
 150                 return (ISC_R_FAILURE);
 151
 152         if (nalloc > 0xffff)
 153                 return (ISC_R_NOSPACE);
 154
 155         x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
 156         if (x == NULL)
 157                 return (ISC_R_NOMEMORY);
 158
 159         /*
 160          * Save all of the rdata members into an array.
 161          */
 162         result = dns_rdataset_first(rdataset);
 163         if (result != ISC_R_SUCCESS)
 164                 goto free_rdatas;
 165         for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
 166                 INSIST(result == ISC_R_SUCCESS);
 167                 dns_rdata_init(&x[i].rdata);
 168                 dns_rdataset_current(rdataset, &x[i].rdata);
 169 #if DNS_RDATASET_FIXED
 170                 x[i].order = i;
 171 #endif
 172                 result = dns_rdataset_next(rdataset);
 173         }
 174         if (result != ISC_R_NOMORE)
 175                 goto free_rdatas;
 176         if (i != nalloc) {
 177                 /*
 178                  * Somehow we iterated over fewer rdatas than
 179                  * dns_rdataset_count() said there were!
 180                  */
 181                 result = ISC_R_FAILURE;
 182                 goto free_rdatas;
 183         }
 184
 185         /*
 186          * Put into DNSSEC order.
 187          */
 188         qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
 189
 190         /*
 191          * Remove duplicates and compute the total storage required.
 192          *
 193          * If an rdata is not a duplicate, accumulate the storage size
 194          * required for the rdata.  We do not store the class, type, etc,
 195          * just the rdata, so our overhead is 2 bytes for the number of
 196          * records, and 8 for each rdata, (length(2), offset(4) and order(2))
 197          * and then the rdata itself.
 198          */
 199         for (i = 1; i < nalloc; i++) {
 200                 if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
 201                         x[i-1].rdata.data = NULL;
 202                         x[i-1].rdata.length = 0;
 203 #if DNS_RDATASET_FIXED
 204                         /*
 205                          * Preserve the least order so A, B, A -> A, B
 206                          * after duplicate removal.
 207                          */
 208                         if (x[i-1].order < x[i].order)
 209                                 x[i].order = x[i-1].order;
 210 #endif
 211                         nitems--;
 212                 } else
 213 #if DNS_RDATASET_FIXED
 214                         buflen += (8 + x[i-1].rdata.length);
 215 #else
 216                         buflen += (2 + x[i-1].rdata.length);
 217 #endif
 218         }
 219         /*
 220          * Don't forget the last item!
 221          */
 222 #if DNS_RDATASET_FIXED
 223         buflen += (8 + x[i-1].rdata.length);
 224 #else
 225         buflen += (2 + x[i-1].rdata.length);
 226 #endif
 227
 228         /*
 229          * Ensure that singleton types are actually singletons.
 230          */
 231         if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
 232                 /*
 233                  * We have a singleton type, but there's more than one
 234                  * RR in the rdataset.
 235                  */
 236                 result = DNS_R_SINGLETON;
 237                 goto free_rdatas;
 238         }
 239
 240         /*
 241          * Allocate the memory, set up a buffer, start copying in
 242          * data.
 243          */
 244         rawbuf = isc_mem_get(mctx, buflen);
 245         if (rawbuf == NULL) {
 246                 result = ISC_R_NOMEMORY;
 247                 goto free_rdatas;
 248         }
 249
 250 #if DNS_RDATASET_FIXED
 251         /* Allocate temporary offset table. */
 252         offsettable = isc_mem_get(mctx, nalloc * sizeof(unsigned int));
 253         if (offsettable == NULL) {
 254                 isc_mem_put(mctx, rawbuf, buflen);
 255                 result = ISC_R_NOMEMORY;
 256                 goto free_rdatas;
 257         }
 258         memset(offsettable, 0, nalloc * sizeof(unsigned int));
 259 #endif
 260
 261         region->base = rawbuf;
 262         region->length = buflen;
 263
 264         rawbuf += reservelen;
 265 #if DNS_RDATASET_FIXED
 266         offsetbase = rawbuf;
 267 #endif
 268
 269         *rawbuf++ = (nitems & 0xff00) >> 8;
 270         *rawbuf++ = (nitems & 0x00ff);
 271
 272 #if DNS_RDATASET_FIXED
 273         /* Skip load order table.  Filled in later. */
 274         rawbuf += nitems * 4;
 275 #endif
 276
 277         for (i = 0; i < nalloc; i++) {
 278                 if (x[i].rdata.data == NULL)
 279                         continue;
 280 #if DNS_RDATASET_FIXED
 281                 offsettable[x[i].order] = rawbuf - offsetbase;
 282 #endif
 283                 *rawbuf++ = (x[i].rdata.length & 0xff00) >> 8;
 284                 *rawbuf++ = (x[i].rdata.length & 0x00ff);
 285 #if DNS_RDATASET_FIXED
 286                 rawbuf += 2;    /* filled in later */
 287 #endif
 288                 memcpy(rawbuf, x[i].rdata.data, x[i].rdata.length);
 289                 rawbuf += x[i].rdata.length;
 290         }
 291
 292 #if DNS_RDATASET_FIXED
 293         fillin_offsets(offsetbase, offsettable, nalloc);
 294         isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
 295 #endif
 296
 297         result = ISC_R_SUCCESS;
 298
 299  free_rdatas:
 300         isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
 301         return (result);
 302 }
 303
 304 static void
 305 rdataset_disassociate(dns_rdataset_t *rdataset) {
 306         UNUSED(rdataset);
 307 }
 308
 309 static isc_result_t
 310 rdataset_first(dns_rdataset_t *rdataset) {
 311         unsigned char *raw = rdataset->private3;
 312         unsigned int count;
 313
 314         count = raw[0] * 256 + raw[1];
 315         if (count == 0) {
 316                 rdataset->private5 = NULL;
 317                 return (ISC_R_NOMORE);
 318         }
 319 #if DNS_RDATASET_FIXED
 320         raw += 2 + (4 * count);
 321 #else
 322         raw += 2;
 323 #endif
 324         /*
 325          * The privateuint4 field is the number of rdata beyond the cursor
 326          * position, so we decrement the total count by one before storing
 327          * it.
 328          */
 329         count--;
 330         rdataset->privateuint4 = count;
 331         rdataset->private5 = raw;
 332
 333         return (ISC_R_SUCCESS);
 334 }
 335
 336 static isc_result_t
 337 rdataset_next(dns_rdataset_t *rdataset) {
 338         unsigned int count;
 339         unsigned int length;
 340         unsigned char *raw;
 341
 342         count = rdataset->privateuint4;
 343         if (count == 0)
 344                 return (ISC_R_NOMORE);
 345         count--;
 346         rdataset->privateuint4 = count;
 347         raw = rdataset->private5;
 348         length = raw[0] * 256 + raw[1];
 349 #if DNS_RDATASET_FIXED
 350         raw += length + 4;
 351 #else
 352         raw += length + 2;
 353 #endif
 354         rdataset->private5 = raw;
 355
 356         return (ISC_R_SUCCESS);
 357 }
 358
 359 static void
 360 rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
 361         unsigned char *raw = rdataset->private5;
 362         isc_region_t r;
 363
 364         REQUIRE(raw != NULL);
 365
 366         r.length = raw[0] * 256 + raw[1];
 367 #if DNS_RDATASET_FIXED
 368         raw += 4;
 369 #else
 370         raw += 2;
 371 #endif
 372         r.base = raw;
 373         dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
 374 }
 375
 376 static void
 377 rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
 378         *target = *source;
 379
 380         /*
 381          * Reset iterator state.
 382          */
 383         target->privateuint4 = 0;
 384         target->private5 = NULL;
 385 }
 386
 387 static unsigned int
 388 rdataset_count(dns_rdataset_t *rdataset) {
 389         unsigned char *raw = rdataset->private3;
 390         unsigned int count;
 391
 392         count = raw[0] * 256 + raw[1];
 393
 394         return (count);
 395 }
 396
 397 static dns_rdatasetmethods_t rdataset_methods = {
 398         rdataset_disassociate,
 399         rdataset_first,
 400         rdataset_next,
 401         rdataset_current,
 402         rdataset_clone,
 403         rdataset_count,
 404         NULL,
 405         NULL,
 406         NULL,
 407         NULL,
 408         NULL
 409 };
 410
 411 void
 412 dns_rdataslab_tordataset(unsigned char *slab, unsigned int reservelen,
 413                          dns_rdataclass_t rdclass, dns_rdatatype_t rdtype,
 414                          dns_rdatatype_t covers, dns_ttl_t ttl,
 415                          dns_rdataset_t *rdataset)
 416 {
 417         REQUIRE(slab != NULL);
 418         REQUIRE(!dns_rdataset_isassociated(rdataset));
 419
 420         rdataset->methods = &rdataset_methods;
 421         rdataset->rdclass = rdclass;
 422         rdataset->type = rdtype;
 423         rdataset->covers = covers;
 424         rdataset->ttl = ttl;
 425         rdataset->trust = 0;
 426         rdataset->private1 = NULL;
 427         rdataset->private2 = NULL;
 428         rdataset->private3 = slab + reservelen;
 429
 430         /*
 431          * Reset iterator state.
 432          */
 433         rdataset->privateuint4 = 0;
 434         rdataset->private5 = NULL;
 435 }
 436
 437 unsigned int
 438 dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
 439         unsigned int count, length;
 440         unsigned char *current;
 441
 442         REQUIRE(slab != NULL);
 443
 444         current = slab + reservelen;
 445         count = *current++ * 256;
 446         count += *current++;
 447 #if DNS_RDATASET_FIXED
 448         current += (4 * count);
 449 #endif
 450         while (count > 0) {
 451                 count--;
 452                 length = *current++ * 256;
 453                 length += *current++;
 454 #if DNS_RDATASET_FIXED
 455                 current += length + 2;
 456 #else
 457                 current += length;
 458 #endif
 459         }
 460
 461         return ((unsigned int)(current - slab));
 462 }
 463
 464 /*
 465  * Make the dns_rdata_t 'rdata' refer to the slab item
 466  * beginning at '*current', which is part of a slab of type
 467  * 'type' and class 'rdclass', and advance '*current' to
 468  * point to the next item in the slab.
 469  */
 470 static inline void
 471 rdata_from_slab(unsigned char **current,
 472               dns_rdataclass_t rdclass, dns_rdatatype_t type,
 473               dns_rdata_t *rdata)
 474 {
 475         unsigned char *tcurrent = *current;
 476         isc_region_t region;
 477
 478         region.length = *tcurrent++ * 256;
 479         region.length += *tcurrent++;
 480 #if DNS_RDATASET_FIXED
 481         tcurrent += 2;
 482 #endif
 483         region.base = tcurrent;
 484         tcurrent += region.length;
 485         dns_rdata_fromregion(rdata, rdclass, type, &region);
 486         *current = tcurrent;
 487 }
 488
 489 /*
 490  * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
 491  * contains an rdata identical to 'rdata'.  This does case insensitive
 492  * comparisons per DNSSEC.
 493  */
 494 static inline isc_boolean_t
 495 rdata_in_slab(unsigned char *slab, unsigned int reservelen,
 496               dns_rdataclass_t rdclass, dns_rdatatype_t type,
 497               dns_rdata_t *rdata)
 498 {
 499         unsigned int count, i;
 500         unsigned char *current;
 501         dns_rdata_t trdata = DNS_RDATA_INIT;
 502         int n;
 503
 504         current = slab + reservelen;
 505         count = *current++ * 256;
 506         count += *current++;
 507
 508 #if DNS_RDATASET_FIXED
 509         current += (4 * count);
 510 #endif
 511
 512         for (i = 0; i < count; i++) {
 513                 rdata_from_slab(&current, rdclass, type, &trdata);
 514
 515                 n = dns_rdata_compare(&trdata, rdata);
 516                 if (n == 0)
 517                         return (ISC_TRUE);
 518                 if (n > 0)      /* In DNSSEC order. */
 519                         break;
 520                 dns_rdata_reset(&trdata);
 521         }
 522         return (ISC_FALSE);
 523 }
 524
 525 isc_result_t
 526 dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
 527                     unsigned int reservelen, isc_mem_t *mctx,
 528                     dns_rdataclass_t rdclass, dns_rdatatype_t type,
 529                     unsigned int flags, unsigned char **tslabp)
 530 {
 531         unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent;
 532         unsigned int ocount, ncount, count, olength, tlength, tcount, length;
 533         isc_region_t nregion;
 534         dns_rdata_t ordata = DNS_RDATA_INIT;
 535         dns_rdata_t nrdata = DNS_RDATA_INIT;
 536         isc_boolean_t added_something = ISC_FALSE;
 537         unsigned int oadded = 0;
 538         unsigned int nadded = 0;
 539         unsigned int nncount = 0;
 540 #if DNS_RDATASET_FIXED
 541         unsigned int oncount;
 542         unsigned int norder = 0;
 543         unsigned int oorder = 0;
 544         unsigned char *offsetbase;
 545         unsigned int *offsettable;
 546 #endif
 547
 548         /*
 549          * XXX  Need parameter to allow "delete rdatasets in nslab" merge,
 550          * or perhaps another merge routine for this purpose.
 551          */
 552
 553         REQUIRE(tslabp != NULL && *tslabp == NULL);
 554         REQUIRE(oslab != NULL && nslab != NULL);
 555
 556         ocurrent = oslab + reservelen;
 557         ocount = *ocurrent++ * 256;
 558         ocount += *ocurrent++;
 559 #if DNS_RDATASET_FIXED
 560         ocurrent += (4 * ocount);
 561 #endif
 562         ostart = ocurrent;
 563         ncurrent = nslab + reservelen;
 564         ncount = *ncurrent++ * 256;
 565         ncount += *ncurrent++;
 566 #if DNS_RDATASET_FIXED
 567         ncurrent += (4 * ncount);
 568 #endif
 569         INSIST(ocount > 0 && ncount > 0);
 570
 571 #if DNS_RDATASET_FIXED
 572         oncount = ncount;
 573 #endif
 574
 575         /*
 576          * Yes, this is inefficient!
 577          */
 578
 579         /*
 580          * Figure out the length of the old slab's data.
 581          */
 582         olength = 0;
 583         for (count = 0; count < ocount; count++) {
 584                 length = *ocurrent++ * 256;
 585                 length += *ocurrent++;
 586 #if DNS_RDATASET_FIXED
 587                 olength += length + 8;
 588                 ocurrent += length + 2;
 589 #else
 590                 olength += length + 2;
 591                 ocurrent += length;
 592 #endif
 593         }
 594
 595         /*
 596          * Start figuring out the target length and count.
 597          */
 598         tlength = reservelen + 2 + olength;
 599         tcount = ocount;
 600
 601         /*
 602          * Add in the length of rdata in the new slab that aren't in
 603          * the old slab.
 604          */
 605         do {
 606                 nregion.length = *ncurrent++ * 256;
 607                 nregion.length += *ncurrent++;
 608 #if DNS_RDATASET_FIXED
 609                 ncurrent += 2;                  /* Skip order. */
 610 #endif
 611                 nregion.base = ncurrent;
 612                 dns_rdata_init(&nrdata);
 613                 dns_rdata_fromregion(&nrdata, rdclass, type, &nregion);
 614                 if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
 615                 {
 616                         /*
 617                          * This rdata isn't in the old slab.
 618                          */
 619 #if DNS_RDATASET_FIXED
 620                         tlength += nregion.length + 8;
 621 #else
 622                         tlength += nregion.length + 2;
 623 #endif
 624                         tcount++;
 625                         nncount++;
 626                         added_something = ISC_TRUE;
 627                 }
 628                 ncurrent += nregion.length;
 629                 ncount--;
 630         } while (ncount > 0);
 631         ncount = nncount;
 632
 633         if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
 634             (tcount != ncount + ocount))
 635                 return (DNS_R_NOTEXACT);
 636
 637         if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
 638                 return (DNS_R_UNCHANGED);
 639
 640         /*
 641          * Ensure that singleton types are actually singletons.
 642          */
 643         if (tcount > 1 && dns_rdatatype_issingleton(type)) {
 644                 /*
 645                  * We have a singleton type, but there's more than one
 646                  * RR in the rdataset.
 647                  */
 648                 return (DNS_R_SINGLETON);
 649         }
 650
 651         if (tcount > 0xffff)
 652                 return (ISC_R_NOSPACE);
 653
 654         /*
 655          * Copy the reserved area from the new slab.
 656          */
 657         tstart = isc_mem_get(mctx, tlength);
 658         if (tstart == NULL)
 659                 return (ISC_R_NOMEMORY);
 660         memcpy(tstart, nslab, reservelen);
 661         tcurrent = tstart + reservelen;
 662 #if DNS_RDATASET_FIXED
 663         offsetbase = tcurrent;
 664 #endif
 665
 666         /*
 667          * Write the new count.
 668          */
 669         *tcurrent++ = (tcount & 0xff00) >> 8;
 670         *tcurrent++ = (tcount & 0x00ff);
 671
 672 #if DNS_RDATASET_FIXED
 673         /*
 674          * Skip offset table.
 675          */
 676         tcurrent += (tcount * 4);
 677
 678         offsettable = isc_mem_get(mctx,
 679                                   (ocount + oncount) * sizeof(unsigned int));
 680         if (offsettable == NULL) {
 681                 isc_mem_put(mctx, tstart, tlength);
 682                 return (ISC_R_NOMEMORY);
 683         }
 684         memset(offsettable, 0, (ocount + oncount) * sizeof(unsigned int));
 685 #endif
 686
 687         /*
 688          * Merge the two slabs.
 689          */
 690         ocurrent = ostart;
 691         INSIST(ocount != 0);
 692 #if DNS_RDATASET_FIXED
 693         oorder = ocurrent[2] * 256 + ocurrent[3];
 694         INSIST(oorder < ocount);
 695 #endif
 696         rdata_from_slab(&ocurrent, rdclass, type, &ordata);
 697
 698         ncurrent = nslab + reservelen + 2;
 699 #if DNS_RDATASET_FIXED
 700         ncurrent += (4 * oncount);
 701 #endif
 702
 703         if (ncount > 0) {
 704                 do {
 705                         dns_rdata_reset(&nrdata);
 706 #if DNS_RDATASET_FIXED
 707                         norder = ncurrent[2] * 256 + ncurrent[3];
 708
 709                         INSIST(norder < oncount);
 710 #endif
 711                         rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
 712                 } while (rdata_in_slab(oslab, reservelen, rdclass,
 713                                        type, &nrdata));
 714         }
 715
 716         while (oadded < ocount || nadded < ncount) {
 717                 isc_boolean_t fromold;
 718                 if (oadded == ocount)
 719                         fromold = ISC_FALSE;
 720                 else if (nadded == ncount)
 721                         fromold = ISC_TRUE;
 722                 else
 723                         fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
 724                 if (fromold) {
 725 #if DNS_RDATASET_FIXED
 726                         offsettable[oorder] = tcurrent - offsetbase;
 727 #endif
 728                         length = ordata.length;
 729                         *tcurrent++ = (length & 0xff00) >> 8;
 730                         *tcurrent++ = (length & 0x00ff);
 731 #if DNS_RDATASET_FIXED
 732                         tcurrent += 2;  /* fill in later */
 733 #endif
 734                         memcpy(tcurrent, ordata.data, length);
 735                         tcurrent += length;
 736                         oadded++;
 737                         if (oadded < ocount) {
 738                                 dns_rdata_reset(&ordata);
 739 #if DNS_RDATASET_FIXED
 740                                 oorder = ocurrent[2] * 256 + ocurrent[3];
 741                                 INSIST(oorder < ocount);
 742 #endif
 743                                 rdata_from_slab(&ocurrent, rdclass, type,
 744                                                 &ordata);
 745                         }
 746                 } else {
 747 #if DNS_RDATASET_FIXED
 748                         offsettable[ocount + norder] = tcurrent - offsetbase;
 749 #endif
 750                         length = nrdata.length;
 751                         *tcurrent++ = (length & 0xff00) >> 8;
 752                         *tcurrent++ = (length & 0x00ff);
 753 #if DNS_RDATASET_FIXED
 754                         tcurrent += 2;  /* fill in later */
 755 #endif
 756                         memcpy(tcurrent, nrdata.data, length);
 757                         tcurrent += length;
 758                         nadded++;
 759                         if (nadded < ncount) {
 760                                 do {
 761                                         dns_rdata_reset(&nrdata);
 762 #if DNS_RDATASET_FIXED
 763                                         norder = ncurrent[2] * 256 + ncurrent[3];
 764                                         INSIST(norder < oncount);
 765 #endif
 766                                         rdata_from_slab(&ncurrent, rdclass,
 767                                                         type, &nrdata);
 768                                 } while (rdata_in_slab(oslab, reservelen,
 769                                                        rdclass, type,
 770                                                        &nrdata));
 771                         }
 772                 }
 773         }
 774
 775 #if DNS_RDATASET_FIXED
 776         fillin_offsets(offsetbase, offsettable, ocount + oncount);
 777
 778         isc_mem_put(mctx, offsettable,
 779                     (ocount + oncount) * sizeof(unsigned int));
 780 #endif
 781
 782         INSIST(tcurrent == tstart + tlength);
 783
 784         *tslabp = tstart;
 785
 786         return (ISC_R_SUCCESS);
 787 }
 788
 789 isc_result_t
 790 dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
 791                        unsigned int reservelen, isc_mem_t *mctx,
 792                        dns_rdataclass_t rdclass, dns_rdatatype_t type,
 793                        unsigned int flags, unsigned char **tslabp)
 794 {
 795         unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
 796         unsigned int mcount, scount, rcount ,count, tlength, tcount, i;
 797         dns_rdata_t srdata = DNS_RDATA_INIT;
 798         dns_rdata_t mrdata = DNS_RDATA_INIT;
 799 #if DNS_RDATASET_FIXED
 800         unsigned char *offsetbase;
 801         unsigned int *offsettable;
 802 #endif
 803         unsigned int order;
 804
 805         REQUIRE(tslabp != NULL && *tslabp == NULL);
 806         REQUIRE(mslab != NULL && sslab != NULL);
 807
 808         mcurrent = mslab + reservelen;
 809         mcount = *mcurrent++ * 256;
 810         mcount += *mcurrent++;
 811         scurrent = sslab + reservelen;
 812         scount = *scurrent++ * 256;
 813         scount += *scurrent++;
 814         INSIST(mcount > 0 && scount > 0);
 815
 816         /*
 817          * Yes, this is inefficient!
 818          */
 819
 820         /*
 821          * Start figuring out the target length and count.
 822          */
 823         tlength = reservelen + 2;
 824         tcount = 0;
 825         rcount = 0;
 826
 827 #if DNS_RDATASET_FIXED
 828         mcurrent += 4 * mcount;
 829         scurrent += 4 * scount;
 830 #endif
 831         sstart = scurrent;
 832
 833         /*
 834          * Add in the length of rdata in the mslab that aren't in
 835          * the sslab.
 836          */
 837         for (i = 0; i < mcount; i++) {
 838                 unsigned char *mrdatabegin = mcurrent;
 839                 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
 840                 scurrent = sstart;
 841                 for (count = 0; count < scount; count++) {
 842                         dns_rdata_reset(&srdata);
 843                         rdata_from_slab(&scurrent, rdclass, type, &srdata);
 844                         if (dns_rdata_compare(&mrdata, &srdata) == 0)
 845                                 break;
 846                 }
 847                 if (count == scount) {
 848                         /*
 849                          * This rdata isn't in the sslab, and thus isn't
 850                          * being subtracted.
 851                          */
 852                         tlength += mcurrent - mrdatabegin;
 853                         tcount++;
 854                 } else
 855                         rcount++;
 856                 dns_rdata_reset(&mrdata);
 857         }
 858
 859 #if DNS_RDATASET_FIXED
 860         tlength += (4 * tcount);
 861 #endif
 862
 863         /*
 864          * Check that all the records originally existed.  The numeric
 865          * check only works as rdataslabs do not contain duplicates.
 866          */
 867         if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
 868                 return (DNS_R_NOTEXACT);
 869
 870         /*
 871          * Don't continue if the new rdataslab would be empty.
 872          */
 873         if (tcount == 0)
 874                 return (DNS_R_NXRRSET);
 875
 876         /*
 877          * If nothing is going to change, we can stop.
 878          */
 879         if (rcount == 0)
 880                 return (DNS_R_UNCHANGED);
 881
 882         /*
 883          * Copy the reserved area from the mslab.
 884          */
 885         tstart = isc_mem_get(mctx, tlength);
 886         if (tstart == NULL)
 887                 return (ISC_R_NOMEMORY);
 888         memcpy(tstart, mslab, reservelen);
 889         tcurrent = tstart + reservelen;
 890 #if DNS_RDATASET_FIXED
 891         offsetbase = tcurrent;
 892
 893         offsettable = isc_mem_get(mctx, mcount * sizeof(unsigned int));
 894         if (offsettable == NULL) {
 895                 isc_mem_put(mctx, tstart, tlength);
 896                 return (ISC_R_NOMEMORY);
 897         }
 898         memset(offsettable, 0, mcount * sizeof(unsigned int));
 899 #endif
 900
 901         /*
 902          * Write the new count.
 903          */
 904         *tcurrent++ = (tcount & 0xff00) >> 8;
 905         *tcurrent++ = (tcount & 0x00ff);
 906
 907 #if DNS_RDATASET_FIXED
 908         tcurrent += (4 * tcount);
 909 #endif
 910
 911         /*
 912          * Copy the parts of mslab not in sslab.
 913          */
 914         mcurrent = mslab + reservelen;
 915         mcount = *mcurrent++ * 256;
 916         mcount += *mcurrent++;
 917 #if DNS_RDATASET_FIXED
 918         mcurrent += (4 * mcount);
 919 #endif
 920         for (i = 0; i < mcount; i++) {
 921                 unsigned char *mrdatabegin = mcurrent;
 922 #if DNS_RDATASET_FIXED
 923                 order = mcurrent[2] * 256 + mcurrent[3];
 924                 INSIST(order < mcount);
 925 #endif
 926                 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
 927                 scurrent = sstart;
 928                 for (count = 0; count < scount; count++) {
 929                         dns_rdata_reset(&srdata);
 930                         rdata_from_slab(&scurrent, rdclass, type, &srdata);
 931                         if (dns_rdata_compare(&mrdata, &srdata) == 0)
 932                                 break;
 933                 }
 934                 if (count == scount) {
 935                         /*
 936                          * This rdata isn't in the sslab, and thus should be
 937                          * copied to the tslab.
 938                          */
 939                         unsigned int length = mcurrent - mrdatabegin;
 940 #if DNS_RDATASET_FIXED
 941                         offsettable[order] = tcurrent - offsetbase;
 942 #endif
 943                         memcpy(tcurrent, mrdatabegin, length);
 944                         tcurrent += length;
 945                 }
 946                 dns_rdata_reset(&mrdata);
 947         }
 948
 949 #if DNS_RDATASET_FIXED
 950         fillin_offsets(offsetbase, offsettable, mcount);
 951
 952         isc_mem_put(mctx, offsettable, mcount * sizeof(unsigned int));
 953 #endif
 954
 955         INSIST(tcurrent == tstart + tlength);
 956
 957         *tslabp = tstart;
 958
 959         return (ISC_R_SUCCESS);
 960 }
 961
 962 isc_boolean_t
 963 dns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
 964                     unsigned int reservelen)
 965 {
 966         unsigned char *current1, *current2;
 967         unsigned int count1, count2;
 968         unsigned int length1, length2;
 969
 970         current1 = slab1 + reservelen;
 971         count1 = *current1++ * 256;
 972         count1 += *current1++;
 973
 974         current2 = slab2 + reservelen;
 975         count2 = *current2++ * 256;
 976         count2 += *current2++;
 977
 978         if (count1 != count2)
 979                 return (ISC_FALSE);
 980
 981 #if DNS_RDATASET_FIXED
 982         current1 += (4 * count1);
 983         current2 += (4 * count2);
 984 #endif
 985
 986         while (count1 > 0) {
 987                 length1 = *current1++ * 256;
 988                 length1 += *current1++;
 989
 990                 length2 = *current2++ * 256;
 991                 length2 += *current2++;
 992
 993 #if DNS_RDATASET_FIXED
 994                 current1 += 2;
 995                 current2 += 2;
 996 #endif
 997
 998                 if (length1 != length2 ||
 999                     memcmp(current1, current2, length1) != 0)
1000                         return (ISC_FALSE);
1001
1002                 current1 += length1;
1003                 current2 += length1;
1004
1005                 count1--;
1006         }
1007         return (ISC_TRUE);
1008 }
1009
1010 isc_boolean_t
1011 dns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
1012                      unsigned int reservelen, dns_rdataclass_t rdclass,
1013                      dns_rdatatype_t type)
1014 {
1015         unsigned char *current1, *current2;
1016         unsigned int count1, count2;
1017         dns_rdata_t rdata1 = DNS_RDATA_INIT;
1018         dns_rdata_t rdata2 = DNS_RDATA_INIT;
1019
1020         current1 = slab1 + reservelen;
1021         count1 = *current1++ * 256;
1022         count1 += *current1++;
1023
1024         current2 = slab2 + reservelen;
1025         count2 = *current2++ * 256;
1026         count2 += *current2++;
1027
1028         if (count1 != count2)
1029                 return (ISC_FALSE);
1030
1031 #if DNS_RDATASET_FIXED
1032         current1 += (4 * count1);
1033         current2 += (4 * count2);
1034 #endif
1035
1036         while (count1-- > 0) {
1037                 rdata_from_slab(&current1, rdclass, type, &rdata1);
1038                 rdata_from_slab(&current2, rdclass, type, &rdata2);
1039                 if (dns_rdata_compare(&rdata1, &rdata2) != 0)
1040                         return (ISC_FALSE);
1041                 dns_rdata_reset(&rdata1);
1042                 dns_rdata_reset(&rdata2);
1043         }
1044         return (ISC_TRUE);
1045 }