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