82ddae820c63b19ff59693771512ae541cc95d63Tinderbox User * Copyright (C) 1999-2016, 2018 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * This Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * License, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * file, You can obtain one at http://mozilla.org/MPL/2.0/.
6028d1ce0380d0ba7f6c6ecd1ad20b31ddd1becbDavid Lawrence#include <isc/string.h> /* Required for HP/UX (and others?) */
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * The rdataslab structure allows iteration to occur in both load order
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * and DNSSEC order. The structure is as follows:
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * header (reservelen bytes)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * record count (2 bytes)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * offset table (4 x record count bytes in load order)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * data records
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * data length (2 bytes)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * order (2 bytes)
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews * meta data (1 byte for RRSIG's)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * data (data length bytes)
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * If DNS_RDATASET_FIXED is defined to be zero (0) the format of a
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * rdataslab is as follows:
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * header (reservelen bytes)
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * record count (2 bytes)
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * data records
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * data length (2 bytes)
4a4066453f45c869fc9f91d9807b7b8b25b004a0Mark Andrews * meta data (1 byte for RRSIG's)
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * data (data length bytes)
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Offsets are from the end of the header.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Load order traversal is performed by walking the offset table to find
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * the start of the record (DNS_RDATASET_FIXED = 1).
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * DNSSEC order traversal is performed by walking the data records.
bdfaef63f576f810fab27f64395faccf2fcd9434Francis Dupont * The order is stored with record to allow for efficient reconstruction
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * of the offset table following a merge or subtraction.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * The iterator methods here currently only support DNSSEC order iteration.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * The iterator methods in rbtdb support both load order and DNSSEC order
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * iteration.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * rbtdb.c directly interacts with the slab's raw structures. If the
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * structure changes then rbtdb.c also needs to be updated to reflect
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * the changes. See the areas tagged with "RDATASLAB".
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*% Note: the "const void *" are just to make qsort happy. */
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellingtoncompare_rdata(const void *p1, const void *p2) {
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews return (dns_rdata_compare(&x1->rdata, &x2->rdata));
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrewsfillin_offsets(unsigned char *offsetbase, unsigned int *offsettable,
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews unsigned int i, j;
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews for (i = 0, j = 0; i < length; i++) {
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Fill in offset table.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Fill in table index.
cd82aa8fa32698240ecd6634f11e3052ca7a2448Michael Graffdns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
cd82aa8fa32698240ecd6634f11e3052ca7a2448Michael Graff isc_region_t *region, unsigned int reservelen)
735ca24fa61ad9cd0285776c2fc4c14032f8f194Mark Andrews * Use &removed as a sentinal pointer for duplicate
735ca24fa61ad9cd0285776c2fc4c14032f8f194Mark Andrews * rdata as rdata.data == NULL is valid.
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington unsigned int i;
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * If there are no rdata then we can just need to allocate a header
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * with zero a record count.
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * Remember the original number of items.
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington * Save all of the rdata members into an array.
c1ee8bb4ba3e9ab1463403ed685729631de406b1Mark Andrews if (result != ISC_R_SUCCESS && result != ISC_R_NOMORE)
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * Somehow we iterated over fewer rdatas than
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * dns_rdataset_count() said there were or there
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * were more items than dns_rdataset_count said
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews * there were.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Put into DNSSEC order.
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * Remove duplicates and compute the total storage required.
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * If an rdata is not a duplicate, accumulate the storage size
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * required for the rdata. We do not store the class, type, etc,
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * just the rdata, so our overhead is 2 bytes for the number of
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * records, and 8 for each rdata, (length(2), offset(4) and order(2))
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * and then the rdata itself.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Preserve the least order so A, B, A -> A, B
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * after duplicate removal.
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews * Provide space to store the per RR meta data.
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * Don't forget the last item!
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews * Provide space to store the per RR meta data.
bab57cc87ffc890ba1ba3dbc6c022ae1a36726bcBob Halley * Ensure that singleton types are actually singletons.
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * We have a singleton type, but there's more than one
383665e42ad838046472e847b16c4e0d3f1aaf76Bob Halley * RR in the rdataset.
cd82aa8fa32698240ecd6634f11e3052ca7a2448Michael Graff * Allocate the memory, set up a buffer, start copying in
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews /* Allocate temporary offset table. */
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews offsettable = isc_mem_get(mctx, nalloc * sizeof(unsigned int));
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews memset(offsettable, 0, nalloc * sizeof(unsigned int));
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews /* Skip load order table. Filled in later. */
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington for (i = 0; i < nalloc; i++) {
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews * Store the per RR meta data.
ec29d217ba3a2bf3e617a7b5b6708ae221bee999Mark Andrews *rawbuf++ = (x[i].rdata.flags & DNS_RDATA_OFFLINE) ?
e851ea826066ac5a5b01c2c23218faa0273a12e8Evan Hunt memmove(rawbuf, x[i].rdata.data, x[i].rdata.length);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews fillin_offsets(offsetbase, offsettable, nalloc);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
27b09ceb12ec95de461bd2780615d4064ccb1419Mark Andrews isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtonrdataset_disassociate(dns_rdataset_t *rdataset) {
80b782f356f0692c11b4e52e8dd46ec41704e5a2Mark Andrews * The privateuint4 field is the number of rdata beyond the cursor
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellington * position, so we decrement the total count by one before storing
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtonrdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellington dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtonrdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellington * Reset iterator state.
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtonstatic unsigned int
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtonstatic dns_rdatasetmethods_t rdataset_methods = {
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellingtondns_rdataslab_tordataset(unsigned char *slab, unsigned int reservelen,
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellington dns_rdataclass_t rdclass, dns_rdatatype_t rdtype,
f9f2e770a992cb0ed2234b2f985162273059c6d3Brian Wellington REQUIRE(!dns_rdataset_isassociated(rdataset));
8cf24d101a291aa3274e8fd07d1a13cb5fe9976bBrian Wellington * Reset iterator state.
e800570a5a7572a94604815cd7d7e788c0479ed2Bob Halleydns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
e800570a5a7572a94604815cd7d7e788c0479ed2Bob Halley while (count > 0) {
744c1db6352c4c3f11c8538e4a2a57c8b0e0d570Mark Andrewsdns_rdataslab_count(unsigned char *slab, unsigned int reservelen) {
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * Make the dns_rdata_t 'rdata' refer to the slab item
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * beginning at '*current', which is part of a slab of type
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * 'type' and class 'rdclass', and advance '*current' to
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * point to the next item in the slab.
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafssonstatic inline void
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson dns_rdataclass_t rdclass, dns_rdatatype_t type,
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson dns_rdata_fromregion(rdata, rdclass, type, ®ion);
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * contains an rdata identical to 'rdata'. This does case insensitive
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson * comparisons per DNSSEC.
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellingtonrdata_in_slab(unsigned char *slab, unsigned int reservelen,
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington dns_rdataclass_t rdclass, dns_rdatatype_t type,
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington for (i = 0; i < count; i++) {
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(¤t, rdclass, type, &trdata);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews if (n > 0) /* In DNSSEC order. */
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halleydns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent, *data;
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley unsigned int ocount, ncount, count, olength, tlength, tcount, length;
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * XXX Need parameter to allow "delete rdatasets in nslab" merge,
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * or perhaps another merge routine for this purpose.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Yes, this is inefficient!
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Figure out the length of the old slab's data.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Start figuring out the target length and count.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Add in the length of rdata in the new slab that aren't in
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * the old slab.
a76b380643a22f23a67a9df284e86cd7ef7608c1Mark Andrews rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * This rdata isn't in the old slab.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley } while (ncount > 0);
9d2c9f789654ace01489c29af64c68cf42c6cb30Mark Andrews if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
bab57cc87ffc890ba1ba3dbc6c022ae1a36726bcBob Halley * Ensure that singleton types are actually singletons.
bab57cc87ffc890ba1ba3dbc6c022ae1a36726bcBob Halley if (tcount > 1 && dns_rdatatype_issingleton(type)) {
bab57cc87ffc890ba1ba3dbc6c022ae1a36726bcBob Halley * We have a singleton type, but there's more than one
bab57cc87ffc890ba1ba3dbc6c022ae1a36726bcBob Halley * RR in the rdataset.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Copy the reserved area from the new slab.
5bfea18ff8bfa907b86ba7d17fb38b9cf493ae97Bob Halley * Write the new count.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews * Skip offset table.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews memset(offsettable, 0, (ocount + oncount) * sizeof(unsigned int));
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington * Merge the two slabs.
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(&ocurrent, rdclass, type, &ordata);
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington } while (rdata_in_slab(oslab, reservelen, rdclass,
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington while (oadded < ocount || nadded < ncount) {
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellington fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews offsettable[ocount + norder] = tcurrent - offsetbase;
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews fillin_offsets(offsetbase, offsettable, ocount + oncount);
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halleydns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews unsigned int mcount, scount, rcount ,count, tlength, tcount, i;
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Yes, this is inefficient!
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Start figuring out the target length and count.
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Add in the length of rdata in the mslab that aren't in
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * the sslab.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews for (i = 0; i < mcount; i++) {
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(&scurrent, rdclass, type, &srdata);
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * This rdata isn't in the sslab, and thus isn't
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * being subtracted.
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews tlength += (unsigned int)(mcurrent - mrdatabegin);
b55c30f2de6e1baaa3a9ba69b92f428f2c255ac3Mark Andrews * Check that all the records originally existed. The numeric
65085946d4f92481699678e276e3ced04bcfdafbMark Andrews * check only works as rdataslabs do not contain duplicates.
f8abaa0fae7f75d9601c10b6a4af8dd907494d45Mark Andrews if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Don't continue if the new rdataslab would be empty.
9b6fd12d8e53afbfc31022c881c16d2ccbe5fc51Bob Halley * If nothing is going to change, we can stop.
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Copy the reserved area from the mslab.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews offsettable = isc_mem_get(mctx, mcount * sizeof(unsigned int));
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews memset(offsettable, 0, mcount * sizeof(unsigned int));
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Write the new count.
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * Copy the parts of mslab not in sslab.
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews for (i = 0; i < mcount; i++) {
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
da41917c3f882b6e12c7101b653926830a396b81Andreas Gustafsson rdata_from_slab(&scurrent, rdclass, type, &srdata);
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * This rdata isn't in the sslab, and thus should be
926cde044f4334f7afd9d1123ab0f01ec93e7e72Bob Halley * copied to the tslab.
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews length = (unsigned int)(mcurrent - mrdatabegin);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews fillin_offsets(offsetbase, offsettable, mcount);
d76ed813a51465e5c47d521ab09ea20c06f1428dMark Andrews isc_mem_put(mctx, offsettable, mcount * sizeof(unsigned int));
88b9c12a3cbafc3bebedf50a731bec9ce2f99a13Brian Wellingtondns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
6434457b0b380aa43d7159299776959a00269d65Michael Graffdns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
6434457b0b380aa43d7159299776959a00269d65Michael Graff unsigned int reservelen, dns_rdataclass_t rdclass,
6434457b0b380aa43d7159299776959a00269d65Michael Graff while (count1-- > 0) {
6434457b0b380aa43d7159299776959a00269d65Michael Graff rdata_from_slab(¤t1, rdclass, type, &rdata1);