contrib/bind9/lib/dns/rdataslab.c

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