rdataslab.c revision 1bbd36c4db2c86762b582db4b0504e6e68a183f6
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Copyright (C) 2004-2012 Internet Systems Consortium, Inc. ("ISC")
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * Copyright (C) 1999-2003 Internet Software Consortium.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Permission to use, copy, modify, and/or distribute this software for any
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * purpose with or without fee is hereby granted, provided that the above
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * copyright notice and this permission notice appear in all copies.
15a44745412679c30a6d022733925af70a38b715David Lawrence * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
15a44745412679c30a6d022733925af70a38b715David Lawrence * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
15a44745412679c30a6d022733925af70a38b715David Lawrence * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
15a44745412679c30a6d022733925af70a38b715David Lawrence * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15a44745412679c30a6d022733925af70a38b715David Lawrence * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
15a44745412679c30a6d022733925af70a38b715David Lawrence * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15a44745412679c30a6d022733925af70a38b715David Lawrence * PERFORMANCE OF THIS SOFTWARE.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington#include <isc/string.h> /* Required for HP/UX (and others?) */
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * The rdataslab structure allows iteration to occur in both load order
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * and DNSSEC order. The structure is as follows:
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * header (reservelen bytes)
9a6bbb206efa528373c31928ebd0b7216c747a13Brian Wellington * record count (2 bytes)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * offset table (4 x record count bytes in load order)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * data records
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * data length (2 bytes)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * order (2 bytes)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * meta data (1 byte for RRSIG's)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * data (data length bytes)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * If DNS_RDATASET_FIXED is defined to be zero (0) the format of a
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * rdataslab is as follows:
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * header (reservelen bytes)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * record count (2 bytes)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * data records
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * data length (2 bytes)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * meta data (1 byte for RRSIG's)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * data (data length bytes)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Offsets are from the end of the header.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Load order traversal is performed by walking the offset table to find
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * the start of the record (DNS_RDATASET_FIXED = 1).
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * DNSSEC order traversal is performed by walking the data records.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * The order is stored with record to allow for efficient reconstruction
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * of the offset table following a merge or subtraction.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * The iterator methods here currently only support DNSSEC order iteration.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * The iterator methods in rbtdb support both load order and DNSSEC order
8a23742754e4640a298acb0d6bd7ed4da0c11798Brian Wellington * rbtdb.c directly interacts with the slab's raw structures. If the
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * structure changes then rbtdb.c also needs to be updated to reflect
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * the changes. See the areas tagged with "RDATASLAB".
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int order;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff/*% Note: the "const void *" are just to make qsort happy. */
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graffcompare_rdata(const void *p1, const void *p2) {
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff return (dns_rdata_compare(&x1->rdata, &x2->rdata));
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Grafffillin_offsets(unsigned char *offsetbase, unsigned int *offsettable,
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int i, j;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned char *raw;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff for (i = 0, j = 0; i < length; i++) {
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Fill in offset table.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Fill in table index.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graffdns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff isc_region_t *region, unsigned int reservelen)
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Use &removed as a sentinal pointer for duplicate
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * rdata as rdata.data == NULL is valid.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff static unsigned char removed;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned char *rawbuf;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned char *offsetbase;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int nitems;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int nalloc;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int i;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int *offsettable;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int length;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
8a23742754e4640a298acb0d6bd7ed4da0c11798Brian Wellington * Save all of the rdata members into an array.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington if (result != ISC_R_SUCCESS && result != ISC_R_NOMORE)
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington dns_rdataset_current(rdataset, &x[i].rdata);
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Somehow we iterated over fewer rdatas than
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * dns_rdataset_count() said there were!
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Put into DNSSEC order.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Remove duplicates and compute the total storage required.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * If an rdata is not a duplicate, accumulate the storage size
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * required for the rdata. We do not store the class, type, etc,
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * just the rdata, so our overhead is 2 bytes for the number of
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * records, and 8 for each rdata, (length(2), offset(4) and order(2))
9a6bbb206efa528373c31928ebd0b7216c747a13Brian Wellington * and then the rdata itself.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Preserve the least order so A, B, A -> A, B
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * after duplicate removal.
9a6bbb206efa528373c31928ebd0b7216c747a13Brian Wellington * Provide space to store the per RR meta data.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Don't forget the last item!
50980039820700108f1f5eef1e42aa998a44f087Brian Wellington * Provide space to store the per RR meta data.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Ensure that singleton types are actually singletons.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * We have a singleton type, but there's more than one
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * RR in the rdataset.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Allocate the memory, set up a buffer, start copying in
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington /* Allocate temporary offset table. */
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington offsettable = isc_mem_get(mctx, nalloc * sizeof(unsigned int));
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington memset(offsettable, 0, nalloc * sizeof(unsigned int));
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington /* Skip load order table. Filled in later. */
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington for (i = 0; i < nalloc; i++) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington offsettable[x[i].order] = rawbuf - offsetbase;
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff * Store the per RR meta data.
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff *rawbuf++ |= (x[i].rdata.flags & DNS_RDATA_OFFLINE) ?
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff memcpy(rawbuf, x[i].rdata.data, x[i].rdata.length);
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff fillin_offsets(offsetbase, offsettable, nalloc);
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellingtonrdataset_disassociate(dns_rdataset_t *rdataset) {
4e96d1fc0646de4d879e7a0bc1e7aba449a67596Michael Graff unsigned int count;
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * The privateuint4 field is the number of rdata beyond the cursor
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * position, so we decrement the total count by one before storing
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington unsigned char *raw;
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellingtonrdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington unsigned int flags = 0;
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington if (rdataset->type == dns_rdatatype_rrsig) {
50980039820700108f1f5eef1e42aa998a44f087Brian Wellington dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
50980039820700108f1f5eef1e42aa998a44f087Brian Wellingtonrdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellington * Reset iterator state.
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellingtonstatic unsigned int
878d3073b13833ee1a50dfeabf8e400b6fdfc754Brian Wellingtonstatic dns_rdatasetmethods_t rdataset_methods = {
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
unsigned char *current;
while (count > 0) {
count--;
unsigned int length;
length--;
tcurrent++;
if (offline)
static inline isc_boolean_t
unsigned int count, i;
unsigned char *current;
for (i = 0; i < count; i++) {
return (ISC_TRUE);
return (ISC_FALSE);
unsigned int oadded = 0;
unsigned int nadded = 0;
unsigned int nncount = 0;
unsigned int oncount;
unsigned int norder = 0;
unsigned int oorder = 0;
unsigned char *offsetbase;
unsigned int *offsettable;
olength = 0;
tlength++;
tcount++;
nncount++;
ncount--;
} while (ncount > 0);
return (DNS_R_NOTEXACT);
return (DNS_R_UNCHANGED);
return (DNS_R_SINGLETON);
return (ISC_R_NOSPACE);
return (ISC_R_NOMEMORY);
return (ISC_R_NOMEMORY);
if (ncount > 0) {
if (fromold) {
length++;
data--;
oadded++;
&ordata);
length++;
data--;
nadded++;
&nrdata));
return (ISC_R_SUCCESS);
unsigned char *offsetbase;
unsigned int *offsettable;
unsigned int order;
tcount = 0;
rcount = 0;
for (i = 0; i < mcount; i++) {
tcount++;
rcount++;
return (DNS_R_NOTEXACT);
if (tcount == 0)
return (DNS_R_NXRRSET);
if (rcount == 0)
return (DNS_R_UNCHANGED);
return (ISC_R_NOMEMORY);
return (ISC_R_NOMEMORY);
for (i = 0; i < mcount; i++) {
return (ISC_R_SUCCESS);
unsigned int reservelen)
return (ISC_FALSE);
while (count1 > 0) {
return (ISC_FALSE);
count1--;
return (ISC_TRUE);
return (ISC_FALSE);
while (count1-- > 0) {
return (ISC_FALSE);
return (ISC_TRUE);