contrib/bind-9.2.4rc7/lib/dns/rdataslab.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001, 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: rdataslab.c,v 1.29.2.3 2004/03/09 06:11:06 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stdlib.h>
  23
  24 #include <isc/mem.h>
  25 #include <isc/region.h>
  26 #include <isc/string.h>         /* Required for HP/UX (and others?) */
  27 #include <isc/util.h>
  28
  29 #include <dns/result.h>
  30 #include <dns/rdata.h>
  31 #include <dns/rdataset.h>
  32 #include <dns/rdataslab.h>
  33
  34 /* Note: the "const void *" are just to make qsort happy. */
  35 static int
  36 compare_rdata(const void *p1, const void *p2) {
  37         const dns_rdata_t *rdata1 = p1;
  38         const dns_rdata_t *rdata2 = p2;
  39         return (dns_rdata_compare(rdata1, rdata2));
  40 }
  41
  42 isc_result_t
  43 dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
  44                            isc_region_t *region, unsigned int reservelen)
  45 {
  46         dns_rdata_t    *rdatas;
  47         unsigned char  *rawbuf;
  48         unsigned int    buflen;
  49         isc_result_t    result;
  50         unsigned int    nitems;
  51         unsigned int    nalloc;
  52         unsigned int    i;
  53
  54         buflen = reservelen + 2;
  55
  56         nalloc = dns_rdataset_count(rdataset);
  57         nitems = nalloc;
  58         if (nitems == 0)
  59                 return (ISC_R_FAILURE);
  60
  61         rdatas = isc_mem_get(mctx, nalloc * sizeof(dns_rdata_t));
  62         if (rdatas == NULL)
  63                 return (ISC_R_NOMEMORY);
  64
  65         /*
  66          * Save all of the rdata members into an array.
  67          */
  68         result = dns_rdataset_first(rdataset);
  69         if (result != ISC_R_SUCCESS)
  70                 goto free_rdatas;
  71         for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
  72                 INSIST(result == ISC_R_SUCCESS);
  73                 dns_rdata_init(&rdatas[i]);
  74                 dns_rdataset_current(rdataset, &rdatas[i]);
  75                 result = dns_rdataset_next(rdataset);
  76         }
  77         if (result != ISC_R_NOMORE)
  78                 goto free_rdatas;
  79         if (i != nalloc) {
  80                 /*
  81                  * Somehow we iterated over fewer rdatas than
  82                  * dns_rdataset_count() said there were!
  83                  */
  84                 result = ISC_R_FAILURE;
  85                 goto free_rdatas;
  86         }
  87
  88         qsort(rdatas, nalloc, sizeof(dns_rdata_t), compare_rdata);
  89
  90         /*
  91          * Remove duplicates and compute the total storage required.
  92          *
  93          * If an rdata is not a duplicate, accumulate the storage size
  94          * required for the rdata.  We do not store the class, type, etc,
  95          * just the rdata, so our overhead is 2 bytes for the number of
  96          * records, and 2 for each rdata length, and then the rdata itself.
  97          */
  98         for (i = 1; i < nalloc; i++) {
  99                 if (compare_rdata(&rdatas[i-1], &rdatas[i]) == 0) {
 100                         rdatas[i-1].data = NULL;
 101                         rdatas[i-1].length = 0;
 102                         nitems--;
 103                 } else
 104                         buflen += (2 + rdatas[i-1].length);
 105         }
 106         /*
 107          * Don't forget the last item!
 108          */
 109         buflen += (2 + rdatas[i-1].length);
 110
 111         /*
 112          * Ensure that singleton types are actually singletons.
 113          */
 114         if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
 115                 /*
 116                  * We have a singleton type, but there's more than one
 117                  * RR in the rdataset.
 118                  */
 119                 result = DNS_R_SINGLETON;
 120                 goto free_rdatas;
 121         }
 122
 123         /*
 124          * Allocate the memory, set up a buffer, start copying in
 125          * data.
 126          */
 127         rawbuf = isc_mem_get(mctx, buflen);
 128         if (rawbuf == NULL) {
 129                 result = ISC_R_NOMEMORY;
 130                 goto free_rdatas;
 131         }
 132
 133         region->base = rawbuf;
 134         region->length = buflen;
 135
 136         rawbuf += reservelen;
 137
 138         *rawbuf++ = (nitems & 0xff00) >> 8;
 139         *rawbuf++ = (nitems & 0x00ff);
 140         for (i = 0; i < nalloc; i++) {
 141                 if (rdatas[i].data == NULL)
 142                         continue;
 143                 *rawbuf++ = (rdatas[i].length & 0xff00) >> 8;
 144                 *rawbuf++ = (rdatas[i].length & 0x00ff);
 145                 memcpy(rawbuf, rdatas[i].data, rdatas[i].length);
 146                 rawbuf += rdatas[i].length;
 147         }
 148         result = ISC_R_SUCCESS;
 149
 150  free_rdatas:
 151         isc_mem_put(mctx, rdatas, nalloc * sizeof(dns_rdata_t));
 152         return (result);
 153 }
 154
 155 unsigned int
 156 dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
 157         unsigned int count, length;
 158         unsigned char *current;
 159
 160         REQUIRE(slab != NULL);
 161
 162         current = slab + reservelen;
 163         count = *current++ * 256;
 164         count += *current++;
 165         while (count > 0) {
 166                 count--;
 167                 length = *current++ * 256;
 168                 length += *current++;
 169                 current += length;
 170         }
 171
 172         return ((unsigned int)(current - slab));
 173 }
 174
 175 /*
 176  * Make the dns_rdata_t 'rdata' refer to the slab item
 177  * beginning at '*current', which is part of a slab of type
 178  * 'type' and class 'rdclass', and advance '*current' to
 179  * point to the next item in the slab.
 180  */
 181 static inline void
 182 rdata_from_slab(unsigned char **current,
 183               dns_rdataclass_t rdclass, dns_rdatatype_t type,
 184               dns_rdata_t *rdata)
 185 {
 186         unsigned char *tcurrent = *current;
 187         isc_region_t region;
 188
 189         region.length = *tcurrent++ * 256;
 190         region.length += *tcurrent++;
 191         region.base = tcurrent;
 192         tcurrent += region.length;
 193         dns_rdata_fromregion(rdata, rdclass, type, &region);
 194         *current = tcurrent;
 195 }
 196
 197 /*
 198  * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
 199  * contains an rdata identical to 'rdata'.  This does case insensitive
 200  * comparisons per DNSSEC.
 201  */
 202 static inline isc_boolean_t
 203 rdata_in_slab(unsigned char *slab, unsigned int reservelen,
 204               dns_rdataclass_t rdclass, dns_rdatatype_t type,
 205               dns_rdata_t *rdata)
 206 {
 207         unsigned int count, i;
 208         unsigned char *current;
 209         dns_rdata_t trdata = DNS_RDATA_INIT;
 210
 211         current = slab + reservelen;
 212         count = *current++ * 256;
 213         count += *current++;
 214
 215         for (i = 0; i < count; i++) {
 216                 rdata_from_slab(&current, rdclass, type, &trdata);
 217                 if (dns_rdata_compare(&trdata, rdata) == 0)
 218                         return (ISC_TRUE);
 219                 dns_rdata_reset(&trdata);
 220         }
 221         return (ISC_FALSE);
 222 }
 223
 224 isc_result_t
 225 dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
 226                     unsigned int reservelen, isc_mem_t *mctx,
 227                     dns_rdataclass_t rdclass, dns_rdatatype_t type,
 228                     unsigned int flags, unsigned char **tslabp)
 229 {
 230         unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent;
 231         unsigned int ocount, ncount, count, olength, tlength, tcount, length;
 232         isc_region_t nregion;
 233         dns_rdata_t ordata = DNS_RDATA_INIT;
 234         dns_rdata_t nrdata = DNS_RDATA_INIT;
 235         isc_boolean_t added_something = ISC_FALSE;
 236         unsigned int oadded = 0;
 237         unsigned int nadded = 0;
 238         unsigned int nncount = 0;
 239
 240         /*
 241          * XXX  Need parameter to allow "delete rdatasets in nslab" merge,
 242          * or perhaps another merge routine for this purpose.
 243          */
 244
 245         REQUIRE(tslabp != NULL && *tslabp == NULL);
 246         REQUIRE(oslab != NULL && nslab != NULL);
 247
 248         ocurrent = oslab + reservelen;
 249         ocount = *ocurrent++ * 256;
 250         ocount += *ocurrent++;
 251         ostart = ocurrent;
 252         ncurrent = nslab + reservelen;
 253         ncount = *ncurrent++ * 256;
 254         ncount += *ncurrent++;
 255         INSIST(ocount > 0 && ncount > 0);
 256
 257         /*
 258          * Yes, this is inefficient!
 259          */
 260
 261         /*
 262          * Figure out the length of the old slab's data.
 263          */
 264         olength = 0;
 265         for (count = 0; count < ocount; count++) {
 266                 length = *ocurrent++ * 256;
 267                 length += *ocurrent++;
 268                 olength += length + 2;
 269                 ocurrent += length;
 270         }
 271
 272         /*
 273          * Start figuring out the target length and count.
 274          */
 275         tlength = reservelen + 2 + olength;
 276         tcount = ocount;
 277
 278         /*
 279          * Add in the length of rdata in the new slab that aren't in
 280          * the old slab.
 281          */
 282         do {
 283                 nregion.length = *ncurrent++ * 256;
 284                 nregion.length += *ncurrent++;
 285                 nregion.base = ncurrent;
 286                 dns_rdata_init(&nrdata);
 287                 dns_rdata_fromregion(&nrdata, rdclass, type, &nregion);
 288                 if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
 289                 {
 290                         /*
 291                          * This rdata isn't in the old slab.
 292                          */
 293                         tlength += nregion.length + 2;
 294                         tcount++;
 295                         nncount++;
 296                         added_something = ISC_TRUE;
 297                 }
 298                 ncurrent += nregion.length;
 299                 ncount--;
 300         } while (ncount > 0);
 301         ncount = nncount;
 302
 303         if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
 304             (tcount != ncount + ocount))
 305                 return (DNS_R_NOTEXACT);
 306
 307         if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
 308                 return (DNS_R_UNCHANGED);
 309
 310         /*
 311          * Ensure that singleton types are actually singletons.
 312          */
 313         if (tcount > 1 && dns_rdatatype_issingleton(type)) {
 314                 /*
 315                  * We have a singleton type, but there's more than one
 316                  * RR in the rdataset.
 317                  */
 318                 return (DNS_R_SINGLETON);
 319         }
 320
 321         /*
 322          * Copy the reserved area from the new slab.
 323          */
 324         tstart = isc_mem_get(mctx, tlength);
 325         if (tstart == NULL)
 326                 return (ISC_R_NOMEMORY);
 327         memcpy(tstart, nslab, reservelen);
 328         tcurrent = tstart + reservelen;
 329
 330         /*
 331          * Write the new count.
 332          */
 333         *tcurrent++ = (tcount & 0xff00) >> 8;
 334         *tcurrent++ = (tcount & 0x00ff);
 335
 336         /*
 337          * Merge the two slabs.
 338          */
 339         ocurrent = ostart;
 340         INSIST(ocount != 0);
 341         rdata_from_slab(&ocurrent, rdclass, type, &ordata);
 342
 343         ncurrent = nslab + reservelen + 2;
 344         if (ncount > 0) {
 345                 do {
 346                         dns_rdata_reset(&nrdata);
 347                         rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
 348                 } while (rdata_in_slab(oslab, reservelen, rdclass,
 349                                        type, &nrdata));
 350         }
 351
 352         while (oadded < ocount || nadded < ncount) {
 353                 isc_boolean_t fromold;
 354                 if (oadded == ocount)
 355                         fromold = ISC_FALSE;
 356                 else if (nadded == ncount)
 357                         fromold = ISC_TRUE;
 358                 else
 359                         fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
 360                 if (fromold) {
 361                         length = ordata.length;
 362                         *tcurrent++ = (length & 0xff00) >> 8;
 363                         *tcurrent++ = (length & 0x00ff);
 364                         memcpy(tcurrent, ordata.data, length);
 365                         tcurrent += length;
 366                         oadded++;
 367                         if (oadded < ocount) {
 368                                 dns_rdata_reset(&ordata);
 369                                 rdata_from_slab(&ocurrent, rdclass, type,
 370                                                 &ordata);
 371                         }
 372                 } else {
 373                         length = nrdata.length;
 374                         *tcurrent++ = (length & 0xff00) >> 8;
 375                         *tcurrent++ = (length & 0x00ff);
 376                         memcpy(tcurrent, nrdata.data, length);
 377                         tcurrent += length;
 378                         nadded++;
 379                         if (nadded < ncount) {
 380                                 do {
 381                                         dns_rdata_reset(&nrdata);
 382                                         rdata_from_slab(&ncurrent, rdclass,
 383                                                         type, &nrdata);
 384                                 } while (rdata_in_slab(oslab, reservelen,
 385                                                        rdclass, type,
 386                                                        &nrdata));
 387                         }
 388                 }
 389         }
 390
 391         INSIST(tcurrent == tstart + tlength);
 392
 393         *tslabp = tstart;
 394
 395         return (ISC_R_SUCCESS);
 396 }
 397
 398 isc_result_t
 399 dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
 400                        unsigned int reservelen, isc_mem_t *mctx,
 401                        dns_rdataclass_t rdclass, dns_rdatatype_t type,
 402                        unsigned int flags, unsigned char **tslabp)
 403 {
 404         unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
 405         unsigned int mcount, scount, rcount ,count, tlength, tcount;
 406         dns_rdata_t srdata = DNS_RDATA_INIT;
 407         dns_rdata_t mrdata = DNS_RDATA_INIT;
 408
 409         REQUIRE(tslabp != NULL && *tslabp == NULL);
 410         REQUIRE(mslab != NULL && sslab != NULL);
 411
 412         mcurrent = mslab + reservelen;
 413         mcount = *mcurrent++ * 256;
 414         mcount += *mcurrent++;
 415         scurrent = sslab + reservelen;
 416         scount = *scurrent++ * 256;
 417         scount += *scurrent++;
 418         sstart = scurrent;
 419         INSIST(mcount > 0 && scount > 0);
 420
 421         /*
 422          * Yes, this is inefficient!
 423          */
 424
 425         /*
 426          * Start figuring out the target length and count.
 427          */
 428         tlength = reservelen + 2;
 429         tcount = 0;
 430         rcount = 0;
 431
 432         /*
 433          * Add in the length of rdata in the mslab that aren't in
 434          * the sslab.
 435          */
 436         do {
 437                 unsigned char *mrdatabegin = mcurrent;
 438                 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
 439                 scurrent = sstart;
 440                 for (count = 0; count < scount; count++) {
 441                         dns_rdata_reset(&srdata);
 442                         rdata_from_slab(&scurrent, rdclass, type, &srdata);
 443                         if (dns_rdata_compare(&mrdata, &srdata) == 0)
 444                                 break;
 445                 }
 446                 if (count == scount) {
 447                         /*
 448                          * This rdata isn't in the sslab, and thus isn't
 449                          * being subtracted.
 450                          */
 451                         tlength += mcurrent - mrdatabegin;
 452                         tcount++;
 453                 } else
 454                         rcount++;
 455                 mcount--;
 456                 dns_rdata_reset(&mrdata);
 457         } while (mcount > 0);
 458
 459         /*
 460          * Check that all the records originally existed.  The numeric
 461          * check only works as rdataslabs do not contain duplicates.
 462          */
 463         if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
 464                 return (DNS_R_NOTEXACT);
 465
 466         /*
 467          * Don't continue if the new rdataslab would be empty.
 468          */
 469         if (tcount == 0)
 470                 return (DNS_R_NXRRSET);
 471
 472         /*
 473          * If nothing is going to change, we can stop.
 474          */
 475         if (rcount == 0)
 476                 return (DNS_R_UNCHANGED);
 477
 478         /*
 479          * Copy the reserved area from the mslab.
 480          */
 481         tstart = isc_mem_get(mctx, tlength);
 482         if (tstart == NULL)
 483                 return (ISC_R_NOMEMORY);
 484         memcpy(tstart, mslab, reservelen);
 485         tcurrent = tstart + reservelen;
 486
 487         /*
 488          * Write the new count.
 489          */
 490         *tcurrent++ = (tcount & 0xff00) >> 8;
 491         *tcurrent++ = (tcount & 0x00ff);
 492
 493         /*
 494          * Copy the parts of mslab not in sslab.
 495          */
 496         mcurrent = mslab + reservelen;
 497         mcount = *mcurrent++ * 256;
 498         mcount += *mcurrent++;
 499         do {
 500                 unsigned char *mrdatabegin = mcurrent;
 501                 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
 502                 scurrent = sstart;
 503                 for (count = 0; count < scount; count++) {
 504                         dns_rdata_reset(&srdata);
 505                         rdata_from_slab(&scurrent, rdclass, type, &srdata);
 506                         if (dns_rdata_compare(&mrdata, &srdata) == 0)
 507                                 break;
 508                 }
 509                 if (count == scount) {
 510                         /*
 511                          * This rdata isn't in the sslab, and thus should be
 512                          * copied to the tslab.
 513                          */
 514                         unsigned int length = mcurrent - mrdatabegin;
 515                         memcpy(tcurrent, mrdatabegin, length);
 516                         tcurrent += length;
 517                 }
 518                 dns_rdata_reset(&mrdata);
 519                 mcount--;
 520         } while (mcount > 0);
 521
 522         INSIST(tcurrent == tstart + tlength);
 523
 524         *tslabp = tstart;
 525
 526         return (ISC_R_SUCCESS);
 527 }
 528
 529 isc_boolean_t
 530 dns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
 531                     unsigned int reservelen)
 532 {
 533         unsigned char *current1, *current2;
 534         unsigned int count1, count2;
 535         unsigned int length1, length2;
 536
 537         current1 = slab1 + reservelen;
 538         count1 = *current1++ * 256;
 539         count1 += *current1++;
 540
 541         current2 = slab2 + reservelen;
 542         count2 = *current2++ * 256;
 543         count2 += *current2++;
 544
 545         if (count1 != count2)
 546                 return (ISC_FALSE);
 547
 548         while (count1 > 0) {
 549                 length1 = *current1++ * 256;
 550                 length1 += *current1++;
 551
 552                 length2 = *current2++ * 256;
 553                 length2 += *current2++;
 554
 555                 if (length1 != length2 ||
 556                     memcmp(current1, current2, length1) != 0)
 557                         return (ISC_FALSE);
 558
 559                 current1 += length1;
 560                 current2 += length1;
 561
 562                 count1--;
 563         }
 564         return (ISC_TRUE);
 565 }
 566
 567 isc_boolean_t
 568 dns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
 569                      unsigned int reservelen, dns_rdataclass_t rdclass,
 570                      dns_rdatatype_t type)
 571 {
 572         unsigned char *current1, *current2;
 573         unsigned int count1, count2;
 574         dns_rdata_t rdata1 = DNS_RDATA_INIT;
 575         dns_rdata_t rdata2 = DNS_RDATA_INIT;
 576
 577         current1 = slab1 + reservelen;
 578         count1 = *current1++ * 256;
 579         count1 += *current1++;
 580
 581         current2 = slab2 + reservelen;
 582         count2 = *current2++ * 256;
 583         count2 += *current2++;
 584
 585         if (count1 != count2)
 586                 return (ISC_FALSE);
 587
 588         while (count1-- > 0) {
 589                 rdata_from_slab(&current1, rdclass, type, &rdata1);
 590                 rdata_from_slab(&current2, rdclass, type, &rdata2);
 591                 if (dns_rdata_compare(&rdata1, &rdata2) != 0)
 592                         return (ISC_FALSE);
 593                 dns_rdata_reset(&rdata1);
 594                 dns_rdata_reset(&rdata2);
 595         }
 596         return (ISC_TRUE);
 597 }