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