2 * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2003 Internet Software Consortium.
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
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.
18 /* $Id: rdataslab.c,v 1.29.2.2.2.6 2004/03/08 09:04:31 marka Exp $ */
25 #include <isc/region.h>
26 #include <isc/string.h> /* Required for HP/UX (and others?) */
29 #include <dns/result.h>
30 #include <dns/rdata.h>
31 #include <dns/rdataset.h>
32 #include <dns/rdataslab.h>
34 /* Note: the "const void *" are just to make qsort happy. */
36 compare_rdata(const void *p1, const void *p2) {
37 const dns_rdata_t *rdata1 = p1;
38 const dns_rdata_t *rdata2 = p2;
39 return (dns_rdata_compare(rdata1, rdata2));
43 dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
44 isc_region_t *region, unsigned int reservelen)
47 unsigned char *rawbuf;
54 buflen = reservelen + 2;
56 nalloc = dns_rdataset_count(rdataset);
59 return (ISC_R_FAILURE);
61 rdatas = isc_mem_get(mctx, nalloc * sizeof(dns_rdata_t));
63 return (ISC_R_NOMEMORY);
66 * Save all of the rdata members into an array.
68 result = dns_rdataset_first(rdataset);
69 if (result != ISC_R_SUCCESS)
71 for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
72 INSIST(result == ISC_R_SUCCESS);
73 dns_rdata_init(&rdatas[i]);
74 dns_rdataset_current(rdataset, &rdatas[i]);
75 result = dns_rdataset_next(rdataset);
77 if (result != ISC_R_NOMORE)
81 * Somehow we iterated over fewer rdatas than
82 * dns_rdataset_count() said there were!
84 result = ISC_R_FAILURE;
88 qsort(rdatas, nalloc, sizeof(dns_rdata_t), compare_rdata);
91 * Remove duplicates and compute the total storage required.
93 * If an rdata is not a duplicate, accumulate the storage size
94 * required for the rdata. We do not store the class, type, etc,
95 * just the rdata, so our overhead is 2 bytes for the number of
96 * records, and 2 for each rdata length, and then the rdata itself.
98 for (i = 1; i < nalloc; i++) {
99 if (compare_rdata(&rdatas[i-1], &rdatas[i]) == 0) {
100 rdatas[i-1].data = NULL;
101 rdatas[i-1].length = 0;
104 buflen += (2 + rdatas[i-1].length);
107 * Don't forget the last item!
109 buflen += (2 + rdatas[i-1].length);
112 * Ensure that singleton types are actually singletons.
114 if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
116 * We have a singleton type, but there's more than one
117 * RR in the rdataset.
119 result = DNS_R_SINGLETON;
124 * Allocate the memory, set up a buffer, start copying in
127 rawbuf = isc_mem_get(mctx, buflen);
128 if (rawbuf == NULL) {
129 result = ISC_R_NOMEMORY;
133 region->base = rawbuf;
134 region->length = buflen;
136 rawbuf += reservelen;
138 *rawbuf++ = (nitems & 0xff00) >> 8;
139 *rawbuf++ = (nitems & 0x00ff);
140 for (i = 0; i < nalloc; i++) {
141 if (rdatas[i].data == NULL)
143 *rawbuf++ = (rdatas[i].length & 0xff00) >> 8;
144 *rawbuf++ = (rdatas[i].length & 0x00ff);
145 memcpy(rawbuf, rdatas[i].data, rdatas[i].length);
146 rawbuf += rdatas[i].length;
148 result = ISC_R_SUCCESS;
151 isc_mem_put(mctx, rdatas, nalloc * sizeof(dns_rdata_t));
156 rdataset_disassociate(dns_rdataset_t *rdataset) {
161 rdataset_first(dns_rdataset_t *rdataset) {
162 unsigned char *raw = rdataset->private3;
165 count = raw[0] * 256 + raw[1];
167 rdataset->private5 = NULL;
168 return (ISC_R_NOMORE);
172 * The privateuint4 field is the number of rdata beyond the cursor
173 * position, so we decrement the total count by one before storing
177 rdataset->privateuint4 = count;
178 rdataset->private5 = raw;
180 return (ISC_R_SUCCESS);
184 rdataset_next(dns_rdataset_t *rdataset) {
189 count = rdataset->privateuint4;
191 return (ISC_R_NOMORE);
193 rdataset->privateuint4 = count;
194 raw = rdataset->private5;
195 length = raw[0] * 256 + raw[1];
197 rdataset->private5 = raw;
199 return (ISC_R_SUCCESS);
203 rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
204 unsigned char *raw = rdataset->private5;
207 REQUIRE(raw != NULL);
209 r.length = raw[0] * 256 + raw[1];
212 dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
216 rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
220 * Reset iterator state.
222 target->privateuint4 = 0;
223 target->private5 = NULL;
227 rdataset_count(dns_rdataset_t *rdataset) {
228 unsigned char *raw = rdataset->private3;
231 count = raw[0] * 256 + raw[1];
236 static dns_rdatasetmethods_t rdataset_methods = {
237 rdataset_disassociate,
248 dns_rdataslab_tordataset(unsigned char *slab, unsigned int reservelen,
249 dns_rdataclass_t rdclass, dns_rdatatype_t rdtype,
250 dns_rdatatype_t covers, dns_ttl_t ttl,
251 dns_rdataset_t *rdataset)
253 REQUIRE(slab != NULL);
254 REQUIRE(!dns_rdataset_isassociated(rdataset));
256 rdataset->methods = &rdataset_methods;
257 rdataset->rdclass = rdclass;
258 rdataset->type = rdtype;
259 rdataset->covers = covers;
262 rdataset->private1 = NULL;
263 rdataset->private2 = NULL;
264 rdataset->private3 = slab + reservelen;
267 * Reset iterator state.
269 rdataset->privateuint4 = 0;
270 rdataset->private5 = NULL;
274 dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
275 unsigned int count, length;
276 unsigned char *current;
278 REQUIRE(slab != NULL);
280 current = slab + reservelen;
281 count = *current++ * 256;
285 length = *current++ * 256;
286 length += *current++;
290 return ((unsigned int)(current - slab));
294 * Make the dns_rdata_t 'rdata' refer to the slab item
295 * beginning at '*current', which is part of a slab of type
296 * 'type' and class 'rdclass', and advance '*current' to
297 * point to the next item in the slab.
300 rdata_from_slab(unsigned char **current,
301 dns_rdataclass_t rdclass, dns_rdatatype_t type,
304 unsigned char *tcurrent = *current;
307 region.length = *tcurrent++ * 256;
308 region.length += *tcurrent++;
309 region.base = tcurrent;
310 tcurrent += region.length;
311 dns_rdata_fromregion(rdata, rdclass, type, ®ion);
316 * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
317 * contains an rdata identical to 'rdata'. This does case insensitive
318 * comparisons per DNSSEC.
320 static inline isc_boolean_t
321 rdata_in_slab(unsigned char *slab, unsigned int reservelen,
322 dns_rdataclass_t rdclass, dns_rdatatype_t type,
325 unsigned int count, i;
326 unsigned char *current;
327 dns_rdata_t trdata = DNS_RDATA_INIT;
329 current = slab + reservelen;
330 count = *current++ * 256;
333 for (i = 0; i < count; i++) {
334 rdata_from_slab(¤t, rdclass, type, &trdata);
335 if (dns_rdata_compare(&trdata, rdata) == 0)
337 dns_rdata_reset(&trdata);
343 dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
344 unsigned int reservelen, isc_mem_t *mctx,
345 dns_rdataclass_t rdclass, dns_rdatatype_t type,
346 unsigned int flags, unsigned char **tslabp)
348 unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent;
349 unsigned int ocount, ncount, count, olength, tlength, tcount, length;
350 isc_region_t nregion;
351 dns_rdata_t ordata = DNS_RDATA_INIT;
352 dns_rdata_t nrdata = DNS_RDATA_INIT;
353 isc_boolean_t added_something = ISC_FALSE;
354 unsigned int oadded = 0;
355 unsigned int nadded = 0;
356 unsigned int nncount = 0;
359 * XXX Need parameter to allow "delete rdatasets in nslab" merge,
360 * or perhaps another merge routine for this purpose.
363 REQUIRE(tslabp != NULL && *tslabp == NULL);
364 REQUIRE(oslab != NULL && nslab != NULL);
366 ocurrent = oslab + reservelen;
367 ocount = *ocurrent++ * 256;
368 ocount += *ocurrent++;
370 ncurrent = nslab + reservelen;
371 ncount = *ncurrent++ * 256;
372 ncount += *ncurrent++;
373 INSIST(ocount > 0 && ncount > 0);
376 * Yes, this is inefficient!
380 * Figure out the length of the old slab's data.
383 for (count = 0; count < ocount; count++) {
384 length = *ocurrent++ * 256;
385 length += *ocurrent++;
386 olength += length + 2;
391 * Start figuring out the target length and count.
393 tlength = reservelen + 2 + olength;
397 * Add in the length of rdata in the new slab that aren't in
401 nregion.length = *ncurrent++ * 256;
402 nregion.length += *ncurrent++;
403 nregion.base = ncurrent;
404 dns_rdata_init(&nrdata);
405 dns_rdata_fromregion(&nrdata, rdclass, type, &nregion);
406 if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
409 * This rdata isn't in the old slab.
411 tlength += nregion.length + 2;
414 added_something = ISC_TRUE;
416 ncurrent += nregion.length;
418 } while (ncount > 0);
421 if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
422 (tcount != ncount + ocount))
423 return (DNS_R_NOTEXACT);
425 if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
426 return (DNS_R_UNCHANGED);
429 * Ensure that singleton types are actually singletons.
431 if (tcount > 1 && dns_rdatatype_issingleton(type)) {
433 * We have a singleton type, but there's more than one
434 * RR in the rdataset.
436 return (DNS_R_SINGLETON);
440 * Copy the reserved area from the new slab.
442 tstart = isc_mem_get(mctx, tlength);
444 return (ISC_R_NOMEMORY);
445 memcpy(tstart, nslab, reservelen);
446 tcurrent = tstart + reservelen;
449 * Write the new count.
451 *tcurrent++ = (tcount & 0xff00) >> 8;
452 *tcurrent++ = (tcount & 0x00ff);
455 * Merge the two slabs.
459 rdata_from_slab(&ocurrent, rdclass, type, &ordata);
461 ncurrent = nslab + reservelen + 2;
464 dns_rdata_reset(&nrdata);
465 rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
466 } while (rdata_in_slab(oslab, reservelen, rdclass,
470 while (oadded < ocount || nadded < ncount) {
471 isc_boolean_t fromold;
472 if (oadded == ocount)
474 else if (nadded == ncount)
477 fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
479 length = ordata.length;
480 *tcurrent++ = (length & 0xff00) >> 8;
481 *tcurrent++ = (length & 0x00ff);
482 memcpy(tcurrent, ordata.data, length);
485 if (oadded < ocount) {
486 dns_rdata_reset(&ordata);
487 rdata_from_slab(&ocurrent, rdclass, type,
491 length = nrdata.length;
492 *tcurrent++ = (length & 0xff00) >> 8;
493 *tcurrent++ = (length & 0x00ff);
494 memcpy(tcurrent, nrdata.data, length);
497 if (nadded < ncount) {
499 dns_rdata_reset(&nrdata);
500 rdata_from_slab(&ncurrent, rdclass,
502 } while (rdata_in_slab(oslab, reservelen,
509 INSIST(tcurrent == tstart + tlength);
513 return (ISC_R_SUCCESS);
517 dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
518 unsigned int reservelen, isc_mem_t *mctx,
519 dns_rdataclass_t rdclass, dns_rdatatype_t type,
520 unsigned int flags, unsigned char **tslabp)
522 unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
523 unsigned int mcount, scount, rcount ,count, tlength, tcount;
524 dns_rdata_t srdata = DNS_RDATA_INIT;
525 dns_rdata_t mrdata = DNS_RDATA_INIT;
527 REQUIRE(tslabp != NULL && *tslabp == NULL);
528 REQUIRE(mslab != NULL && sslab != NULL);
530 mcurrent = mslab + reservelen;
531 mcount = *mcurrent++ * 256;
532 mcount += *mcurrent++;
533 scurrent = sslab + reservelen;
534 scount = *scurrent++ * 256;
535 scount += *scurrent++;
537 INSIST(mcount > 0 && scount > 0);
540 * Yes, this is inefficient!
544 * Start figuring out the target length and count.
546 tlength = reservelen + 2;
551 * Add in the length of rdata in the mslab that aren't in
555 unsigned char *mrdatabegin = mcurrent;
556 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
558 for (count = 0; count < scount; count++) {
559 dns_rdata_reset(&srdata);
560 rdata_from_slab(&scurrent, rdclass, type, &srdata);
561 if (dns_rdata_compare(&mrdata, &srdata) == 0)
564 if (count == scount) {
566 * This rdata isn't in the sslab, and thus isn't
569 tlength += mcurrent - mrdatabegin;
574 dns_rdata_reset(&mrdata);
575 } while (mcount > 0);
578 * Check that all the records originally existed. The numeric
579 * check only works as rdataslabs do not contain duplicates.
581 if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
582 return (DNS_R_NOTEXACT);
585 * Don't continue if the new rdataslab would be empty.
588 return (DNS_R_NXRRSET);
591 * If nothing is going to change, we can stop.
594 return (DNS_R_UNCHANGED);
597 * Copy the reserved area from the mslab.
599 tstart = isc_mem_get(mctx, tlength);
601 return (ISC_R_NOMEMORY);
602 memcpy(tstart, mslab, reservelen);
603 tcurrent = tstart + reservelen;
606 * Write the new count.
608 *tcurrent++ = (tcount & 0xff00) >> 8;
609 *tcurrent++ = (tcount & 0x00ff);
612 * Copy the parts of mslab not in sslab.
614 mcurrent = mslab + reservelen;
615 mcount = *mcurrent++ * 256;
616 mcount += *mcurrent++;
618 unsigned char *mrdatabegin = mcurrent;
619 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
621 for (count = 0; count < scount; count++) {
622 dns_rdata_reset(&srdata);
623 rdata_from_slab(&scurrent, rdclass, type, &srdata);
624 if (dns_rdata_compare(&mrdata, &srdata) == 0)
627 if (count == scount) {
629 * This rdata isn't in the sslab, and thus should be
630 * copied to the tslab.
632 unsigned int length = mcurrent - mrdatabegin;
633 memcpy(tcurrent, mrdatabegin, length);
636 dns_rdata_reset(&mrdata);
638 } while (mcount > 0);
640 INSIST(tcurrent == tstart + tlength);
644 return (ISC_R_SUCCESS);
648 dns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
649 unsigned int reservelen)
651 unsigned char *current1, *current2;
652 unsigned int count1, count2;
653 unsigned int length1, length2;
655 current1 = slab1 + reservelen;
656 count1 = *current1++ * 256;
657 count1 += *current1++;
659 current2 = slab2 + reservelen;
660 count2 = *current2++ * 256;
661 count2 += *current2++;
663 if (count1 != count2)
667 length1 = *current1++ * 256;
668 length1 += *current1++;
670 length2 = *current2++ * 256;
671 length2 += *current2++;
673 if (length1 != length2 ||
674 memcmp(current1, current2, length1) != 0)
686 dns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
687 unsigned int reservelen, dns_rdataclass_t rdclass,
688 dns_rdatatype_t type)
690 unsigned char *current1, *current2;
691 unsigned int count1, count2;
692 dns_rdata_t rdata1 = DNS_RDATA_INIT;
693 dns_rdata_t rdata2 = DNS_RDATA_INIT;
695 current1 = slab1 + reservelen;
696 count1 = *current1++ * 256;
697 count1 += *current1++;
699 current2 = slab2 + reservelen;
700 count2 = *current2++ * 256;
701 count2 += *current2++;
703 if (count1 != count2)
706 while (count1-- > 0) {
707 rdata_from_slab(¤t1, rdclass, type, &rdata1);
708 rdata_from_slab(¤t2, rdclass, type, &rdata2);
709 if (dns_rdata_compare(&rdata1, &rdata2) != 0)
711 dns_rdata_reset(&rdata1);
712 dns_rdata_reset(&rdata2);