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