external/bsd/bind/dist/lib/dns/rdataslab.c

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