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