rbt.c

/*
 * Copyright (C) 2004, 2005, 2007-2009, 2011-2014  Internet Systems Consortium, Inc. ("ISC")
 * Copyright (C) 1999-2003  Internet Software Consortium.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

/*! \file */

/* Principal Authors: DCL */

#include <config.h>

#include <sys/stat.h>
#ifdef HAVE_INTTYPES_H
#include <inttypes.h> /* uintptr_t */
#endif

#include <isc/crc64.h>
#include <isc/file.h>
#include <isc/hex.h>
#include <isc/mem.h>
#include <isc/platform.h>
#include <isc/print.h>
#include <isc/refcount.h>
#include <isc/socket.h>
#include <isc/stdio.h>
#include <isc/string.h>
#include <isc/util.h>

/*%
 * This define is so dns/name.h (included by dns/fixedname.h) uses more
 * efficient macro calls instead of functions for a few operations.
 */
#define DNS_NAME_USEINLINE 1

#include <dns/fixedname.h>
#include <dns/log.h>
#include <dns/rbt.h>
#include <dns/result.h>
#include <dns/version.h>

#include <unistd.h>

#define CHECK(x) \
	do { \
		result = (x); \
		if (result != ISC_R_SUCCESS) \
			goto cleanup; \
	} while (0)

#define RBT_MAGIC               ISC_MAGIC('R', 'B', 'T', '+')
#define VALID_RBT(rbt)          ISC_MAGIC_VALID(rbt, RBT_MAGIC)

/*
 * XXXDCL Since parent pointers were added in again, I could remove all of the
 * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
 * _lastnode.  This would involve pretty major change to the API.
 */
#define CHAIN_MAGIC             ISC_MAGIC('0', '-', '0', '-')
#define VALID_CHAIN(chain)      ISC_MAGIC_VALID(chain, CHAIN_MAGIC)

#define RBT_HASH_SIZE           64

#ifdef RBT_MEM_TEST
#undef RBT_HASH_SIZE
#define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
#endif

struct dns_rbt {
	unsigned int            magic;
	isc_mem_t *             mctx;
	dns_rbtnode_t *         root;
	void                    (*data_deleter)(void *, void *);
	void *                  deleter_arg;
	unsigned int            nodecount;
	unsigned int            hashsize;
	dns_rbtnode_t **        hashtable;
	void *                  mmap_location;
};

#define RED 0
#define BLACK 1

/*
 * This is the header for map-format RBT images.  It is populated,
 * and then written, as the LAST thing done to the file before returning.
 * Writing this last (with zeros in the header area initially) will ensure
 * that the header is only valid when the RBT image is also valid.
 */
typedef struct file_header file_header_t;

/* Pad to 32 bytes */
static char FILE_VERSION[32] = "\0";

/* Header length, always the same size regardless of structure size */
#define HEADER_LENGTH		1024

struct file_header {
	char version1[32];
	isc_uint64_t first_node_offset;	/* usually 1024 */
	/*
	 * information about the system on which the map file was generated
	 * will be used to tell if we can load the map file or not
	 */
	isc_uint32_t ptrsize;
	unsigned int bigendian:1;	/* big or little endian system */
	unsigned int rdataset_fixed:1;	/* compiled with --enable-rrset-fixed */
	unsigned int nodecount;		/* shadow from rbt structure */
	isc_uint64_t crc;
	char version2[32];  		/* repeated; must match version1 */
};

/*
 * The following declarations are for the serialization of an RBT:
 *
 * step one: write out a zeroed header of 1024 bytes
 * step two: walk the tree in a depth-first, left-right-down order, writing
 * out the nodes, reserving space as we go, correcting addresses to point
 * at the proper offset in the file, and setting a flag for each pointer to
 * indicate that it is a reference to a location in the file, rather than in
 * memory.
 * step three: write out the header, adding the information that will be
 * needed to re-create the tree object itself.
 *
 * The RBTDB object will do this three times, once for each of the three
 * RBT objects it contains.
 *
 * Note: 'file' must point an actual open file that can be mmapped
 * and fseeked, not to a pipe or stream
 */

static isc_result_t
dns_rbt_zero_header(FILE *file);

static isc_result_t
write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
	     isc_uint64_t crc);

static isc_result_t
serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
	       uintptr_t right, uintptr_t down, uintptr_t parent,
	       uintptr_t data, isc_uint64_t *crc);

static isc_result_t
serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
		dns_rbtdatawriter_t datawriter, void *writer_arg,
		uintptr_t *where, isc_uint64_t *crc);
/*
 * The following functions allow you to get the actual address of a pointer
 * without having to use an if statement to check to see if that address is
 * relative or not
 */
static inline dns_rbtnode_t *
getparent(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->parent);
	adjusted_address += node->parent_is_relative * (uintptr_t)header;

	return ((dns_rbtnode_t *)adjusted_address);
}

static inline dns_rbtnode_t *
getleft(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->left);
	adjusted_address += node->left_is_relative * (uintptr_t)header;

	return ((dns_rbtnode_t *)adjusted_address);
}

static inline dns_rbtnode_t *
getright(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->right);
	adjusted_address += node->right_is_relative * (uintptr_t)header;

	return ((dns_rbtnode_t *)adjusted_address);
}

static inline dns_rbtnode_t *
getdown(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->down);
	adjusted_address += node->down_is_relative * (uintptr_t)header;

	return ((dns_rbtnode_t *)adjusted_address);
}

static inline dns_rbtnode_t *
getdata(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->data);
	adjusted_address += node->data_is_relative * (uintptr_t)header;

	return ((dns_rbtnode_t *)adjusted_address);
}

/*%
 * Elements of the rbtnode structure.
 */
#define PARENT(node)            ((node)->parent)
#define LEFT(node)              ((node)->left)
#define RIGHT(node)             ((node)->right)
#define DOWN(node)              ((node)->down)
#define DATA(node)              ((node)->data)
#define HASHNEXT(node)          ((node)->hashnext)
#define HASHVAL(node)           ((node)->hashval)
#define COLOR(node)             ((node)->color)
#define NAMELEN(node)           ((node)->namelen)
#define OLDNAMELEN(node)        ((node)->oldnamelen)
#define OFFSETLEN(node)         ((node)->offsetlen)
#define ATTRS(node)             ((node)->attributes)
#define IS_ROOT(node)           ISC_TF((node)->is_root == 1)
#define FINDCALLBACK(node)      ISC_TF((node)->find_callback == 1)

/*%
 * Structure elements from the rbtdb.c, not
 * used as part of the rbt.c algorithms.
 */
#define DIRTY(node)     ((node)->dirty)
#define WILD(node)      ((node)->wild)
#define LOCKNUM(node)   ((node)->locknum)

/*%
 * The variable length stuff stored after the node has the following
 * structure.
 *
 *	<name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
 *
 * <name_data> contains the name of the node when it was created.
 * <oldoffsetlen> contains the length of <offsets> when the node was created.
 * <offsets> contains the offets into name for each label when the node was
 * created.
 */

#define NAME(node)      ((unsigned char *)((node) + 1))
#define OFFSETS(node)   (NAME(node) + OLDNAMELEN(node) + 1)
#define OLDOFFSETLEN(node) (OFFSETS(node)[-1])

#define NODE_SIZE(node) (sizeof(*node) + \
			 OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)

/*%
 * Color management.
 */
#define IS_RED(node)            ((node) != NULL && (node)->color == RED)
#define IS_BLACK(node)          ((node) == NULL || (node)->color == BLACK)
#define MAKE_RED(node)          ((node)->color = RED)
#define MAKE_BLACK(node)        ((node)->color = BLACK)

/*%
 * Chain management.
 *
 * The "ancestors" member of chains were removed, with their job now
 * being wholly handled by parent pointers (which didn't exist, because
 * of memory concerns, when chains were first implemented).
 */
#define ADD_LEVEL(chain, node) \
			(chain)->levels[(chain)->level_count++] = (node)

/*%
 * The following macros directly access normally private name variables.
 * These macros are used to avoid a lot of function calls in the critical
 * path of the tree traversal code.
 */

static inline void
NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
	name->length = NAMELEN(node);
	name->labels = OFFSETLEN(node);
	name->ndata = NAME(node);
	name->offsets = OFFSETS(node);
	name->attributes = ATTRS(node);
	name->attributes |= DNS_NAMEATTR_READONLY;
}

#ifdef DNS_RBT_USEHASH
static isc_result_t
inithash(dns_rbt_t *rbt);
#endif

#ifdef DEBUG
#define inline
/*
 * A little something to help out in GDB.
 */
dns_name_t Name(dns_rbtnode_t *node);
dns_name_t
Name(dns_rbtnode_t *node) {
	dns_name_t name;

	dns_name_init(&name, NULL);
	if (node != NULL)
		NODENAME(node, &name);

	return (name);
}

static void printnodename(dns_rbtnode_t *node);

static void
hexdump(const char *desc, unsigned char *data, size_t size) {
	char hexdump[BUFSIZ];
	isc_buffer_t b;
	isc_region_t r;

	isc_buffer_init(&b, hexdump, sizeof(hexdump));
	r.base = data;
	r.length = size;
	isc_hex_totext(&r, 0, "", &b);
	isc_buffer_putuint8(&b, 0);
	fprintf(stderr, "%s: %s\n", desc, hexdump);
}
#endif

static inline dns_rbtnode_t *
find_up(dns_rbtnode_t *node) {
	dns_rbtnode_t *root;

	/*
	 * Return the node in the level above the argument node that points
	 * to the level the argument node is in.  If the argument node is in
	 * the top level, the return value is NULL.
	 */
	for (root = node; ! IS_ROOT(root); root = PARENT(root))
		; /* Nothing. */

	return (PARENT(root));
}

/*
 * Forward declarations.
 */
static isc_result_t
create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);

#ifdef DNS_RBT_USEHASH
static inline void
hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
static inline void
unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
static void
rehash(dns_rbt_t *rbt, unsigned int newcount);
#else
#define hash_node(rbt, node, name)
#define unhash_node(rbt, node)
#define rehash(rbt, newcount)
#endif

static inline void
rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
static inline void
rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);

static void
addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
	   dns_rbtnode_t **rootp);

static void
deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);

static isc_result_t
treefix(dns_rbt_t *rbt, void *base, size_t size,
	dns_rbtnode_t *n, dns_name_t *name,
	dns_rbtdatafixer_t datafixer, void *fixer_arg,
	isc_uint64_t *crc);

static isc_result_t
deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);

static void
deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep);

static void
printnodename(dns_rbtnode_t *node);

static void
freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);

static isc_result_t
dns_rbt_zero_header(FILE *file) {
	/*
	 * Write out a zeroed header as a placeholder.  Doing this ensures
	 * that the file will not read while it is partially written, should
	 * writing fail or be interrupted.
	 */
	char buffer[HEADER_LENGTH];
	isc_result_t result;

	memset(buffer, 0, HEADER_LENGTH);
	result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
	if (result != ISC_R_SUCCESS)
		return (result);

	result = fflush(file);
	if (result != ISC_R_SUCCESS)
		return (result);

	return (ISC_R_SUCCESS);
}

/*
 * Write out the real header, including NodeDump version information
 * and the offset of the first node.
 *
 * Any information stored in the rbt object itself should be stored
 * here.
 */
static isc_result_t
write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
	     isc_uint64_t crc)
{
	file_header_t header;
	isc_result_t result;
	off_t location;

	if (FILE_VERSION[0] == '\0') {
		memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
		snprintf(FILE_VERSION, sizeof(FILE_VERSION),
			 "RBT Image %s %s", dns_major, dns_mapapi);
	}

	memset(&header, 0, sizeof(file_header_t));
	memmove(header.version1, FILE_VERSION, sizeof(header.version1));
	memmove(header.version2, FILE_VERSION, sizeof(header.version2));
	header.first_node_offset = first_node_offset;
	header.ptrsize = (isc_uint32_t) sizeof(void *);
	header.bigendian = (1 == htonl(1)) ? 1 : 0;

#ifdef DNS_RDATASET_FIXED
	header.rdataset_fixed = 1;
#else
	header.rdataset_fixed = 0;
#endif

	header.nodecount = rbt->nodecount;

	header.crc = crc;

	CHECK(isc_stdio_tell(file, &location));
	location = dns_rbt_serialize_align(location);
	CHECK(isc_stdio_seek(file, location, SEEK_SET));
	CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
	CHECK(fflush(file));

	/* Ensure we are always at the end of the file. */
	CHECK(isc_stdio_seek(file, 0, SEEK_END));

 cleanup:
	return (result);
}

static isc_result_t
serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
	       uintptr_t right, uintptr_t down, uintptr_t parent,
	       uintptr_t data, isc_uint64_t *crc)
{
	dns_rbtnode_t temp_node;
	off_t file_position;
	unsigned char *node_data;
	size_t datasize;
	isc_result_t result;
#ifdef DEBUG
	dns_name_t nodename;
#endif

	INSIST(node != NULL);

	CHECK(isc_stdio_tell(file, &file_position));
	file_position = dns_rbt_serialize_align(file_position);
	CHECK(isc_stdio_seek(file, file_position, SEEK_SET));

	temp_node = *node;
	temp_node.down_is_relative = 0;
	temp_node.left_is_relative = 0;
	temp_node.right_is_relative = 0;
	temp_node.parent_is_relative = 0;
	temp_node.data_is_relative = 0;
	temp_node.is_mmapped = 1;

	/*
	 * If the next node is not NULL, calculate the next node's location
	 * in the file.  Note that this will have to change when the data
	 * structure changes, and it also assumes that we always write the
	 * nodes out in list order (which we currently do.)
	*/
	if (temp_node.parent != NULL) {
		temp_node.parent = (dns_rbtnode_t *)(parent);
		temp_node.parent_is_relative = 1;
	}
	if (temp_node.left != NULL) {
		temp_node.left = (dns_rbtnode_t *)(left);
		temp_node.left_is_relative = 1;
	}
	if (temp_node.right != NULL) {
		temp_node.right = (dns_rbtnode_t *)(right);
		temp_node.right_is_relative = 1;
	}
	if (temp_node.down != NULL) {
		temp_node.down = (dns_rbtnode_t *)(down);
		temp_node.down_is_relative = 1;
	}
	if (temp_node.data != NULL) {
		temp_node.data = (dns_rbtnode_t *)(data);
		temp_node.data_is_relative = 1;
	}

	node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
	datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);

	CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
			      file, NULL));
	CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));

#ifdef DEBUG
	dns_name_init(&nodename, NULL);
	NODENAME(node, &nodename);
	fprintf(stderr, "serialize ");
	dns_name_print(&nodename, stderr);
	fprintf(stderr, "\n");
	hexdump("node header", (unsigned char*) &temp_node,
		sizeof(dns_rbtnode_t));
	hexdump("node data", node_data, datasize);
#endif

	isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,
			sizeof(dns_rbtnode_t));
	isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);

 cleanup:
	return (result);
}

static isc_result_t
serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
		dns_rbtdatawriter_t datawriter, void *writer_arg,
		uintptr_t *where, isc_uint64_t *crc)
{
	uintptr_t left = 0, right = 0, down = 0, data = 0;
	off_t location = 0, offset_adjust;
	isc_result_t result;

	if (node == NULL) {
		if (where != NULL)
			*where = 0;
		return (ISC_R_SUCCESS);
	}

	/* Reserve space for current node. */
	CHECK(isc_stdio_tell(file, &location));
	location = dns_rbt_serialize_align(location);
	CHECK(isc_stdio_seek(file, location, SEEK_SET));

	offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
	CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));

	/*
	 * Serialize the rest of the tree.
	 *
	 * WARNING: A change in the order (from left, right, down)
	 * will break the way the crc hash is computed.
	 */
	CHECK(serialize_nodes(file, getleft(node, NULL), location,
			      datawriter, writer_arg, &left, crc));
	CHECK(serialize_nodes(file, getright(node, NULL), location,
			      datawriter, writer_arg, &right, crc));
	CHECK(serialize_nodes(file, getdown(node, NULL), location,
			      datawriter, writer_arg, &down, crc));

	if (node->data != NULL) {
		off_t ret;

		CHECK(isc_stdio_tell(file, &ret));
		ret = dns_rbt_serialize_align(ret);
		CHECK(isc_stdio_seek(file, ret, SEEK_SET));
		data = ret;

		datawriter(file, node->data, writer_arg, crc);
	}

	/* Seek back to reserved space. */
	CHECK(isc_stdio_seek(file, location, SEEK_SET));

	/* Serialize the current node. */
	CHECK(serialize_node(file, node, left, right, down, parent, data, crc));

	/* Ensure we are always at the end of the file. */
	CHECK(isc_stdio_seek(file, 0, SEEK_END));

	if (where != NULL)
		*where = (uintptr_t) location;

 cleanup:
	return (result);
}

off_t
dns_rbt_serialize_align(off_t target) {
	off_t offset = target % 8;

	if (offset == 0)
		return (target);
	else
		return (target + 8 - offset);
}

isc_result_t
dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
		       dns_rbtdatawriter_t datawriter,
		       void *writer_arg, off_t *offset)
{
	isc_result_t result;
	off_t header_position, node_position, end_position;
	isc_uint64_t crc;

	REQUIRE(file != NULL);

	CHECK(isc_file_isplainfilefd(fileno(file)));

	isc_crc64_init(&crc);

	CHECK(isc_stdio_tell(file, &header_position));

	/* Write dummy header */
	CHECK(dns_rbt_zero_header(file));

	/* Serialize nodes */
	CHECK(isc_stdio_tell(file, &node_position));
	CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
			      writer_arg, NULL, &crc));

	CHECK(isc_stdio_tell(file, &end_position));
	if (node_position == end_position) {
		CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
		*offset = 0;
		return (ISC_R_SUCCESS);
	}

	isc_crc64_final(&crc);
#ifdef DEBUG
	hexdump("serializing CRC", &crc, sizeof(crc));
#endif

	/* Serialize header */
	CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
	CHECK(write_header(file, rbt, HEADER_LENGTH, crc));

	/* Ensure we are always at the end of the file. */
	CHECK(isc_stdio_seek(file, 0, SEEK_END));
	*offset = dns_rbt_serialize_align(header_position);

 cleanup:
	return (result);
}

#define CONFIRM(a) do { \
	if (! (a)) { \
		result = ISC_R_INVALIDFILE; \
		goto cleanup; \
	} \
} while(0);

static isc_result_t
treefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
	dns_name_t *name, dns_rbtdatafixer_t datafixer,
	void *fixer_arg, isc_uint64_t *crc)
{
	isc_result_t result = ISC_R_SUCCESS;
	dns_fixedname_t fixed;
	dns_name_t nodename, *fullname;
	unsigned char *node_data;
	dns_rbtnode_t header;
	size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);

	if (n == NULL)
		return (ISC_R_SUCCESS);

	CONFIRM((void *) n >= base);
	CONFIRM((char *) n - (char *) base <= (int) nodemax);
	CONFIRM(DNS_RBTNODE_VALID(n));

	dns_name_init(&nodename, NULL);
	NODENAME(n, &nodename);

	fullname = &nodename;
	CONFIRM(dns_name_isvalid(fullname));

	if (!dns_name_isabsolute(&nodename)) {
		dns_fixedname_init(&fixed);
		fullname = dns_fixedname_name(&fixed);
		CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
	}

	/* memorize header contents prior to fixup */
	memmove(&header, n, sizeof(header));

	if (n->left_is_relative) {
		CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);
		n->left = getleft(n, rbt->mmap_location);
		n->left_is_relative = 0;
		CONFIRM(DNS_RBTNODE_VALID(n->left));
	} else
		CONFIRM(n->left == NULL);

	if (n->right_is_relative) {
		CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
		n->right = getright(n, rbt->mmap_location);
		n->right_is_relative = 0;
		CONFIRM(DNS_RBTNODE_VALID(n->right));
	} else
		CONFIRM(n->right == NULL);

	if (n->down_is_relative) {
		CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);
		n->down = getdown(n, rbt->mmap_location);
		n->down_is_relative = 0;
		CONFIRM(n->down > (dns_rbtnode_t *) n);
		CONFIRM(DNS_RBTNODE_VALID(n->down));
	} else
		CONFIRM(n->down == NULL);

	if (n->parent_is_relative) {
		CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
		n->parent = getparent(n, rbt->mmap_location);
		n->parent_is_relative = 0;
		CONFIRM(n->parent < (dns_rbtnode_t *) n);
		CONFIRM(DNS_RBTNODE_VALID(n->parent));
	} else
		CONFIRM(n->parent == NULL);

	if (n->data_is_relative) {
		CONFIRM(n->data <= (void *) filesize);
		n->data = getdata(n, rbt->mmap_location);
		n->data_is_relative = 0;
		CONFIRM(n->data > (void *) n);
	} else
		CONFIRM(n->data == NULL);

	hash_node(rbt, n, fullname);

	/* a change in the order (from left, right, down) will break hashing*/
	if (n->left != NULL)
		CHECK(treefix(rbt, base, filesize, n->left, name,
			      datafixer, fixer_arg, crc));
	if (n->right != NULL)
		CHECK(treefix(rbt, base, filesize, n->right, name,
			      datafixer, fixer_arg, crc));
	if (n->down != NULL)
		CHECK(treefix(rbt, base, filesize, n->down, fullname,
			      datafixer, fixer_arg, crc));

	if (datafixer != NULL && n->data != NULL)
		CHECK(datafixer(n, base, filesize, fixer_arg, crc));

	rbt->nodecount++;
	node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
	datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);

#ifdef DEBUG
	fprintf(stderr, "deserialize ");
	dns_name_print(&nodename, stderr);
	fprintf(stderr, "\n");
	hexdump("node header", (unsigned char *) &header,
		sizeof(dns_rbtnode_t));
	hexdump("node data", node_data, datasize);
#endif
	isc_crc64_update(crc, (const isc_uint8_t *) &header,
			sizeof(dns_rbtnode_t));
	isc_crc64_update(crc, (const isc_uint8_t *) node_data,
			datasize);

 cleanup:
	return (result);
}

isc_result_t
dns_rbt_deserialize_tree(void *base_address, size_t filesize,
			 off_t header_offset, isc_mem_t *mctx,
			 dns_rbtdeleter_t deleter, void *deleter_arg,
			 dns_rbtdatafixer_t datafixer, void *fixer_arg,
			 dns_rbtnode_t **originp, dns_rbt_t **rbtp)
{
	isc_result_t result = ISC_R_SUCCESS;
	file_header_t *header;
	dns_rbt_t *rbt = NULL;
	isc_uint64_t crc;

	REQUIRE(originp == NULL || *originp == NULL);
	REQUIRE(rbtp != NULL && *rbtp == NULL);

	isc_crc64_init(&crc);

	CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));

	rbt->mmap_location = base_address;

	header = (file_header_t *)((char *)base_address + header_offset);

#ifdef DNS_RDATASET_FIXED
	if (header->rdataset_fixed != 1) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}

#else
	if (header->rdataset_fixed != 0) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}
#endif

	if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}
	if (header->bigendian != (1 == htonl(1)) ? 1 : 0) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}

	/* Copy other data items from the header into our rbt. */
	rbt->root = (dns_rbtnode_t *)((char *)base_address +
				header_offset + header->first_node_offset);

	if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}
	rehash(rbt, header->nodecount);

	CHECK(treefix(rbt, base_address, filesize, rbt->root,
		      dns_rootname, datafixer, fixer_arg, &crc));

	isc_crc64_final(&crc);
#ifdef DEBUG
	hexdump("deserializing CRC", &crc, sizeof(crc));
#endif

	/* Check file hash */
	if (header->crc != crc) {
		result = ISC_R_INVALIDFILE;
		goto cleanup;
	}

	*rbtp = rbt;
	if (originp != NULL)
		*originp = rbt->root;

	if (header->nodecount != rbt->nodecount)
		result = ISC_R_INVALIDFILE;

 cleanup:
	if (result != ISC_R_SUCCESS) {
		rbt->root = NULL;
		rbt->nodecount = 0;
		dns_rbt_destroy(&rbt);
	}

	return (result);
}

/*
 * Initialize a red/black tree of trees.
 */
isc_result_t
dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
	       void *deleter_arg, dns_rbt_t **rbtp)
{
#ifdef DNS_RBT_USEHASH
	isc_result_t result;
#endif
	dns_rbt_t *rbt;

	REQUIRE(mctx != NULL);
	REQUIRE(rbtp != NULL && *rbtp == NULL);
	REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);

	rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
	if (rbt == NULL)
		return (ISC_R_NOMEMORY);

	rbt->mctx = NULL;
	isc_mem_attach(mctx, &rbt->mctx);
	rbt->data_deleter = deleter;
	rbt->deleter_arg = deleter_arg;
	rbt->root = NULL;
	rbt->nodecount = 0;
	rbt->hashtable = NULL;
	rbt->hashsize = 0;
	rbt->mmap_location = NULL;

#ifdef DNS_RBT_USEHASH
	result = inithash(rbt);
	if (result != ISC_R_SUCCESS) {
		isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
		return (result);
	}
#endif

	rbt->magic = RBT_MAGIC;

	*rbtp = rbt;

	return (ISC_R_SUCCESS);
}

/*
 * Deallocate a red/black tree of trees.
 */
void
dns_rbt_destroy(dns_rbt_t **rbtp) {
	RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
}

isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
	dns_rbt_t *rbt;

	REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));

	rbt = *rbtp;

	deletetreeflat(rbt, quantum, &rbt->root);
	if (rbt->root != NULL)
		return (ISC_R_QUOTA);

	INSIST(rbt->nodecount == 0);

	rbt->mmap_location = NULL;

	if (rbt->hashtable != NULL)
		isc_mem_put(rbt->mctx, rbt->hashtable,
			    rbt->hashsize * sizeof(dns_rbtnode_t *));

	rbt->magic = 0;

	isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
	*rbtp = NULL;
	return (ISC_R_SUCCESS);
}

unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt) {

	REQUIRE(VALID_RBT(rbt));

	return (rbt->nodecount);
}

unsigned int
dns_rbt_hashsize(dns_rbt_t *rbt) {

	REQUIRE(VALID_RBT(rbt));

	return (rbt->hashsize);
}

static inline isc_result_t