"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.17.5/lib/dns/rdataslab.c" (4 Sep 2020, 24553 Bytes) of package /linux/misc/dns/bind9/9.17.5/bind-9.17.5.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rdataslab.c" see the Fossies "Dox" file reference documentation.

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