2 * Copyright (C) 2004 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2001, 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.3 2004/03/09 06:11:06 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 dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
157 unsigned int count, length;
158 unsigned char *current;
160 REQUIRE(slab != NULL);
162 current = slab + reservelen;
163 count = *current++ * 256;
167 length = *current++ * 256;
168 length += *current++;
172 return ((unsigned int)(current - slab));
176 * Make the dns_rdata_t 'rdata' refer to the slab item
177 * beginning at '*current', which is part of a slab of type
178 * 'type' and class 'rdclass', and advance '*current' to
179 * point to the next item in the slab.
182 rdata_from_slab(unsigned char **current,
183 dns_rdataclass_t rdclass, dns_rdatatype_t type,
186 unsigned char *tcurrent = *current;
189 region.length = *tcurrent++ * 256;
190 region.length += *tcurrent++;
191 region.base = tcurrent;
192 tcurrent += region.length;
193 dns_rdata_fromregion(rdata, rdclass, type, ®ion);
198 * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
199 * contains an rdata identical to 'rdata'. This does case insensitive
200 * comparisons per DNSSEC.
202 static inline isc_boolean_t
203 rdata_in_slab(unsigned char *slab, unsigned int reservelen,
204 dns_rdataclass_t rdclass, dns_rdatatype_t type,
207 unsigned int count, i;
208 unsigned char *current;
209 dns_rdata_t trdata = DNS_RDATA_INIT;
211 current = slab + reservelen;
212 count = *current++ * 256;
215 for (i = 0; i < count; i++) {
216 rdata_from_slab(¤t, rdclass, type, &trdata);
217 if (dns_rdata_compare(&trdata, rdata) == 0)
219 dns_rdata_reset(&trdata);
225 dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
226 unsigned int reservelen, isc_mem_t *mctx,
227 dns_rdataclass_t rdclass, dns_rdatatype_t type,
228 unsigned int flags, unsigned char **tslabp)
230 unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent;
231 unsigned int ocount, ncount, count, olength, tlength, tcount, length;
232 isc_region_t nregion;
233 dns_rdata_t ordata = DNS_RDATA_INIT;
234 dns_rdata_t nrdata = DNS_RDATA_INIT;
235 isc_boolean_t added_something = ISC_FALSE;
236 unsigned int oadded = 0;
237 unsigned int nadded = 0;
238 unsigned int nncount = 0;
241 * XXX Need parameter to allow "delete rdatasets in nslab" merge,
242 * or perhaps another merge routine for this purpose.
245 REQUIRE(tslabp != NULL && *tslabp == NULL);
246 REQUIRE(oslab != NULL && nslab != NULL);
248 ocurrent = oslab + reservelen;
249 ocount = *ocurrent++ * 256;
250 ocount += *ocurrent++;
252 ncurrent = nslab + reservelen;
253 ncount = *ncurrent++ * 256;
254 ncount += *ncurrent++;
255 INSIST(ocount > 0 && ncount > 0);
258 * Yes, this is inefficient!
262 * Figure out the length of the old slab's data.
265 for (count = 0; count < ocount; count++) {
266 length = *ocurrent++ * 256;
267 length += *ocurrent++;
268 olength += length + 2;
273 * Start figuring out the target length and count.
275 tlength = reservelen + 2 + olength;
279 * Add in the length of rdata in the new slab that aren't in
283 nregion.length = *ncurrent++ * 256;
284 nregion.length += *ncurrent++;
285 nregion.base = ncurrent;
286 dns_rdata_init(&nrdata);
287 dns_rdata_fromregion(&nrdata, rdclass, type, &nregion);
288 if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
291 * This rdata isn't in the old slab.
293 tlength += nregion.length + 2;
296 added_something = ISC_TRUE;
298 ncurrent += nregion.length;
300 } while (ncount > 0);
303 if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
304 (tcount != ncount + ocount))
305 return (DNS_R_NOTEXACT);
307 if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
308 return (DNS_R_UNCHANGED);
311 * Ensure that singleton types are actually singletons.
313 if (tcount > 1 && dns_rdatatype_issingleton(type)) {
315 * We have a singleton type, but there's more than one
316 * RR in the rdataset.
318 return (DNS_R_SINGLETON);
322 * Copy the reserved area from the new slab.
324 tstart = isc_mem_get(mctx, tlength);
326 return (ISC_R_NOMEMORY);
327 memcpy(tstart, nslab, reservelen);
328 tcurrent = tstart + reservelen;
331 * Write the new count.
333 *tcurrent++ = (tcount & 0xff00) >> 8;
334 *tcurrent++ = (tcount & 0x00ff);
337 * Merge the two slabs.
341 rdata_from_slab(&ocurrent, rdclass, type, &ordata);
343 ncurrent = nslab + reservelen + 2;
346 dns_rdata_reset(&nrdata);
347 rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
348 } while (rdata_in_slab(oslab, reservelen, rdclass,
352 while (oadded < ocount || nadded < ncount) {
353 isc_boolean_t fromold;
354 if (oadded == ocount)
356 else if (nadded == ncount)
359 fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
361 length = ordata.length;
362 *tcurrent++ = (length & 0xff00) >> 8;
363 *tcurrent++ = (length & 0x00ff);
364 memcpy(tcurrent, ordata.data, length);
367 if (oadded < ocount) {
368 dns_rdata_reset(&ordata);
369 rdata_from_slab(&ocurrent, rdclass, type,
373 length = nrdata.length;
374 *tcurrent++ = (length & 0xff00) >> 8;
375 *tcurrent++ = (length & 0x00ff);
376 memcpy(tcurrent, nrdata.data, length);
379 if (nadded < ncount) {
381 dns_rdata_reset(&nrdata);
382 rdata_from_slab(&ncurrent, rdclass,
384 } while (rdata_in_slab(oslab, reservelen,
391 INSIST(tcurrent == tstart + tlength);
395 return (ISC_R_SUCCESS);
399 dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
400 unsigned int reservelen, isc_mem_t *mctx,
401 dns_rdataclass_t rdclass, dns_rdatatype_t type,
402 unsigned int flags, unsigned char **tslabp)
404 unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
405 unsigned int mcount, scount, rcount ,count, tlength, tcount;
406 dns_rdata_t srdata = DNS_RDATA_INIT;
407 dns_rdata_t mrdata = DNS_RDATA_INIT;
409 REQUIRE(tslabp != NULL && *tslabp == NULL);
410 REQUIRE(mslab != NULL && sslab != NULL);
412 mcurrent = mslab + reservelen;
413 mcount = *mcurrent++ * 256;
414 mcount += *mcurrent++;
415 scurrent = sslab + reservelen;
416 scount = *scurrent++ * 256;
417 scount += *scurrent++;
419 INSIST(mcount > 0 && scount > 0);
422 * Yes, this is inefficient!
426 * Start figuring out the target length and count.
428 tlength = reservelen + 2;
433 * Add in the length of rdata in the mslab that aren't in
437 unsigned char *mrdatabegin = mcurrent;
438 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
440 for (count = 0; count < scount; count++) {
441 dns_rdata_reset(&srdata);
442 rdata_from_slab(&scurrent, rdclass, type, &srdata);
443 if (dns_rdata_compare(&mrdata, &srdata) == 0)
446 if (count == scount) {
448 * This rdata isn't in the sslab, and thus isn't
451 tlength += mcurrent - mrdatabegin;
456 dns_rdata_reset(&mrdata);
457 } while (mcount > 0);
460 * Check that all the records originally existed. The numeric
461 * check only works as rdataslabs do not contain duplicates.
463 if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
464 return (DNS_R_NOTEXACT);
467 * Don't continue if the new rdataslab would be empty.
470 return (DNS_R_NXRRSET);
473 * If nothing is going to change, we can stop.
476 return (DNS_R_UNCHANGED);
479 * Copy the reserved area from the mslab.
481 tstart = isc_mem_get(mctx, tlength);
483 return (ISC_R_NOMEMORY);
484 memcpy(tstart, mslab, reservelen);
485 tcurrent = tstart + reservelen;
488 * Write the new count.
490 *tcurrent++ = (tcount & 0xff00) >> 8;
491 *tcurrent++ = (tcount & 0x00ff);
494 * Copy the parts of mslab not in sslab.
496 mcurrent = mslab + reservelen;
497 mcount = *mcurrent++ * 256;
498 mcount += *mcurrent++;
500 unsigned char *mrdatabegin = mcurrent;
501 rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
503 for (count = 0; count < scount; count++) {
504 dns_rdata_reset(&srdata);
505 rdata_from_slab(&scurrent, rdclass, type, &srdata);
506 if (dns_rdata_compare(&mrdata, &srdata) == 0)
509 if (count == scount) {
511 * This rdata isn't in the sslab, and thus should be
512 * copied to the tslab.
514 unsigned int length = mcurrent - mrdatabegin;
515 memcpy(tcurrent, mrdatabegin, length);
518 dns_rdata_reset(&mrdata);
520 } while (mcount > 0);
522 INSIST(tcurrent == tstart + tlength);
526 return (ISC_R_SUCCESS);
530 dns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
531 unsigned int reservelen)
533 unsigned char *current1, *current2;
534 unsigned int count1, count2;
535 unsigned int length1, length2;
537 current1 = slab1 + reservelen;
538 count1 = *current1++ * 256;
539 count1 += *current1++;
541 current2 = slab2 + reservelen;
542 count2 = *current2++ * 256;
543 count2 += *current2++;
545 if (count1 != count2)
549 length1 = *current1++ * 256;
550 length1 += *current1++;
552 length2 = *current2++ * 256;
553 length2 += *current2++;
555 if (length1 != length2 ||
556 memcmp(current1, current2, length1) != 0)
568 dns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
569 unsigned int reservelen, dns_rdataclass_t rdclass,
570 dns_rdatatype_t type)
572 unsigned char *current1, *current2;
573 unsigned int count1, count2;
574 dns_rdata_t rdata1 = DNS_RDATA_INIT;
575 dns_rdata_t rdata2 = DNS_RDATA_INIT;
577 current1 = slab1 + reservelen;
578 count1 = *current1++ * 256;
579 count1 += *current1++;
581 current2 = slab2 + reservelen;
582 count2 = *current2++ * 256;
583 count2 += *current2++;
585 if (count1 != count2)
588 while (count1-- > 0) {
589 rdata_from_slab(¤t1, rdclass, type, &rdata1);
590 rdata_from_slab(¤t2, rdclass, type, &rdata2);
591 if (dns_rdata_compare(&rdata1, &rdata2) != 0)
593 dns_rdata_reset(&rdata1);
594 dns_rdata_reset(&rdata2);