f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

d09197467bbb156dccf0cbe72bb5c63480d5cfdcDavid Lawrence

d09197467bbb156dccf0cbe72bb5c63480d5cfdcDavid Lawrence

64ba6e4cc3a0ccf8c8c6349fa75b937ca9bad9a6Michael Graff#include <config.h>

64ba6e4cc3a0ccf8c8c6349fa75b937ca9bad9a6Michael Graff

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <sys/stat.h>

62ac31d7fd09b0bf2231e5f55ed85aed39bc2df6Evan Hunt#ifdef HAVE_INTTYPES_H

62ac31d7fd09b0bf2231e5f55ed85aed39bc2df6Evan Hunt#include <inttypes.h> /* uintptr_t */

62ac31d7fd09b0bf2231e5f55ed85aed39bc2df6Evan Hunt#endif

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt#include <isc/crc64.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <isc/file.h>

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#include <isc/hex.h>

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence#include <isc/mem.h>

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt#include <isc/once.h>

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrews#include <isc/platform.h>

dd57718608494835363244429432599aa15124a3Andreas Gustafsson#include <isc/print.h>

5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉#include <isc/refcount.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <isc/socket.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <isc/stdio.h>

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrence#include <isc/string.h>

82a1986c04057804edf670bf5d59f716785af789Bob Halley#include <isc/util.h>

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

891a1bead8d02d29eb7b4993d7c0975047b0963dDavid Lawrence#define DNS_NAME_USEINLINE 1

891a1bead8d02d29eb7b4993d7c0975047b0963dDavid Lawrence

891a1bead8d02d29eb7b4993d7c0975047b0963dDavid Lawrence#include <dns/fixedname.h>

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#include <dns/log.h>

73d62a89f1493865c33c689b3ee3de91c74ad58eDavid Lawrence#include <dns/rbt.h>

73d62a89f1493865c33c689b3ee3de91c74ad58eDavid Lawrence#include <dns/result.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <dns/version.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#include <unistd.h>

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#define CHECK(x) \

7829fad4093f2c1985b1efb7cea00287ff015d2bckb do { \

7829fad4093f2c1985b1efb7cea00287ff015d2bckb result = (x); \

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (result != ISC_R_SUCCESS) \

7829fad4093f2c1985b1efb7cea00287ff015d2bckb goto cleanup; \

7829fad4093f2c1985b1efb7cea00287ff015d2bckb } while (0)

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)

33950f0a0262f4d49528c4adcf8be42807fa2576David Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define RBT_HASH_SIZE 64

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence#ifdef RBT_MEM_TEST

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence#undef RBT_HASH_SIZE

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence#endif

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrencestruct dns_rbt {

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman unsigned int magic;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman isc_mem_t * mctx;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman dns_rbtnode_t * root;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman void (*data_deleter)(void *, void *);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman void * deleter_arg;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman unsigned int nodecount;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman size_t hashsize;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman dns_rbtnode_t ** hashtable;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman void * mmap_location;

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence};

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence#define RED 0

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence#define BLACK 1

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence

7829fad4093f2c1985b1efb7cea00287ff015d2bckbtypedef struct file_header file_header_t;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic char FILE_VERSION[32] = "\0";

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

b4a865ee130c8a1623a7060c27efec0c1f238403Francis Dupont#define HEADER_LENGTH 1024

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstruct file_header {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char version1[32];

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_uint64_t first_node_offset; /* usually 1024 */

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User /*

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_uint32_t ptrsize;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb unsigned int bigendian:1; /* big or little endian system */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb unsigned int rdataset_fixed:1; /* compiled with --enable-rrset-fixed */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb unsigned int nodecount; /* shadow from rbt structure */

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_uint64_t crc;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char version2[32]; /* repeated; must match version1 */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb};

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic isc_result_t

7829fad4093f2c1985b1efb7cea00287ff015d2bckbdns_rbt_zero_header(FILE *file);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic isc_result_t

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Huntwrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_uint64_t crc);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntstatic isc_boolean_t

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntmatch_header_version(file_header_t *header);

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic isc_result_t

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox Userserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User uintptr_t right, uintptr_t down, uintptr_t parent,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt uintptr_t data, isc_uint64_t *crc);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic isc_result_t

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox Userserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt dns_rbtdatawriter_t datawriter, void *writer_arg,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt uintptr_t *where, isc_uint64_t *crc);

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline dns_rbtnode_t *

7829fad4093f2c1985b1efb7cea00287ff015d2bckbgetparent(dns_rbtnode_t *node, file_header_t *header) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char *adjusted_address = (char *)(node->parent);

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User adjusted_address += node->parent_is_relative * (uintptr_t)header;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return ((dns_rbtnode_t *)adjusted_address);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline dns_rbtnode_t *

7829fad4093f2c1985b1efb7cea00287ff015d2bckbgetleft(dns_rbtnode_t *node, file_header_t *header) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char *adjusted_address = (char *)(node->left);

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User adjusted_address += node->left_is_relative * (uintptr_t)header;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return ((dns_rbtnode_t *)adjusted_address);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline dns_rbtnode_t *

7829fad4093f2c1985b1efb7cea00287ff015d2bckbgetright(dns_rbtnode_t *node, file_header_t *header) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char *adjusted_address = (char *)(node->right);

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User adjusted_address += node->right_is_relative * (uintptr_t)header;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return ((dns_rbtnode_t *)adjusted_address);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline dns_rbtnode_t *

7829fad4093f2c1985b1efb7cea00287ff015d2bckbgetdown(dns_rbtnode_t *node, file_header_t *header) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char *adjusted_address = (char *)(node->down);

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User adjusted_address += node->down_is_relative * (uintptr_t)header;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return ((dns_rbtnode_t *)adjusted_address);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline dns_rbtnode_t *

7829fad4093f2c1985b1efb7cea00287ff015d2bckbgetdata(dns_rbtnode_t *node, file_header_t *header) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char *adjusted_address = (char *)(node->data);

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User adjusted_address += node->data_is_relative * (uintptr_t)header;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return ((dns_rbtnode_t *)adjusted_address);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define PARENT(node) ((node)->parent)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define LEFT(node) ((node)->left)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define RIGHT(node) ((node)->right)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define DOWN(node) ((node)->down)

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#ifdef DNS_RBT_USEHASH

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#define UPPERNODE(node) ((node)->uppernode)

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#endif /* DNS_RBT_USEHASH */

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define DATA(node) ((node)->data)

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman#define IS_EMPTY(node) ((node)->data == NULL)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define HASHNEXT(node) ((node)->hashnext)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define HASHVAL(node) ((node)->hashval)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define COLOR(node) ((node)->color)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define NAMELEN(node) ((node)->namelen)

7704a47aec081144bdb7a0218d5e2dd5296b6b08Mark Andrews#define OLDNAMELEN(node) ((node)->oldnamelen)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define OFFSETLEN(node) ((node)->offsetlen)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define ATTRS(node) ((node)->attributes)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define IS_ROOT(node) ISC_TF((node)->is_root == 1)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)

f036af2c718147408d738081cdb0a564b981b4cdDavid Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define DIRTY(node) ((node)->dirty)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define WILD(node) ((node)->wild)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define LOCKNUM(node) ((node)->locknum)

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

7704a47aec081144bdb7a0218d5e2dd5296b6b08Mark Andrews

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define NAME(node) ((unsigned char *)((node) + 1))

7704a47aec081144bdb7a0218d5e2dd5296b6b08Mark Andrews#define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)

7704a47aec081144bdb7a0218d5e2dd5296b6b08Mark Andrews#define OLDOFFSETLEN(node) (OFFSETS(node)[-1])

f036af2c718147408d738081cdb0a564b981b4cdDavid Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define NODE_SIZE(node) (sizeof(*node) + \

7704a47aec081144bdb7a0218d5e2dd5296b6b08Mark Andrews OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)

f036af2c718147408d738081cdb0a564b981b4cdDavid Lawrence

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define IS_RED(node) ((node) != NULL && (node)->color == RED)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define MAKE_RED(node) ((node)->color = RED)

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff#define MAKE_BLACK(node) ((node)->color = BLACK)

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence

f036af2c718147408d738081cdb0a564b981b4cdDavid Lawrence#define ADD_LEVEL(chain, node) \

b16d99bac1d100735224ab3eaa84632537ff21b5Mark Andrews do { \

b16d99bac1d100735224ab3eaa84632537ff21b5Mark Andrews INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \

b16d99bac1d100735224ab3eaa84632537ff21b5Mark Andrews (chain)->levels[(chain)->level_count++] = (node); \

b16d99bac1d100735224ab3eaa84632537ff21b5Mark Andrews } while (0)

1630fce031f7a3e33f0579e477a3e17d1993e1f9Bob Halley

1630fce031f7a3e33f0579e477a3e17d1993e1f9Bob Halley

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic inline void

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan HuntNODENAME(dns_rbtnode_t *node, dns_name_t *name) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->length = NAMELEN(node);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->labels = OFFSETLEN(node);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->ndata = NAME(node);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->offsets = OFFSETS(node);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->attributes = ATTRS(node);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb name->attributes |= DNS_NAMEATTR_READONLY;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

1630fce031f7a3e33f0579e477a3e17d1993e1f9Bob Halley

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramandns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->length = NAMELEN(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->labels = OFFSETLEN(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->ndata = NAME(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->offsets = OFFSETS(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->attributes = ATTRS(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman name->attributes |= DNS_NAMEATTR_READONLY;

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman}

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramandns_rbtnode_t *

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramandns_rbt_root(dns_rbt_t *rbt) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman return rbt->root;

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman}

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#ifdef DNS_RBT_USEHASH

7554feaef6057f5ea2926076900ac7634b911456Mark Andrewsstatic isc_result_t

7554feaef6057f5ea2926076900ac7634b911456Mark Andrewsinithash(dns_rbt_t *rbt);

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#endif

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence#ifdef DEBUG

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence#define inline

bd1190c84b08e61a12789c54f083318c36449e5eDavid Lawrencedns_name_t Name(dns_rbtnode_t *node);

73d62a89f1493865c33c689b3ee3de91c74ad58eDavid LawrenceName(dns_rbtnode_t *node) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_t name;

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_init(&name, NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (node != NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater NODENAME(node, &name);

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (name);

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence}

401fc772b1bf058a981e3c474fa6502f6ee0e2bfDavid Lawrence

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Huntstatic void

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunthexdump(const char *desc, unsigned char *data, size_t size) {

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews char hexdump[BUFSIZ * 2 + 1];

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt isc_buffer_t b;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt isc_region_t r;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews isc_result_t result;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews size_t bytes;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews fprintf(stderr, "%s: ", desc);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews do {

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews isc_buffer_init(&b, hexdump, sizeof(hexdump));

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews r.base = data;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews result = isc_hex_totext(&r, 0, "", &b);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews RUNTIME_CHECK(result == ISC_R_SUCCESS);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews isc_buffer_putuint8(&b, 0);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews fprintf(stderr, "%s", hexdump);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews data += bytes;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews size -= bytes;

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews } while (size > 0);

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews fprintf(stderr, "\n");

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt}

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman#endif /* DEBUG */

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#ifdef DNS_RBT_USEHASH

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanstatic inline dns_rbtnode_t *

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanget_upper_node(dns_rbtnode_t *node) {

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman return (UPPERNODE(node));

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanstatic void

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanfixup_uppernodes_helper(dns_rbtnode_t *node, dns_rbtnode_t *uppernode) {

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman if (node == NULL)

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman return;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman UPPERNODE(node) = uppernode;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman fixup_uppernodes_helper(LEFT(node), uppernode);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman fixup_uppernodes_helper(RIGHT(node), uppernode);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman fixup_uppernodes_helper(DOWN(node), node);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanstatic void

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanfixup_uppernodes(dns_rbt_t *rbt) {

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman fixup_uppernodes_helper(rbt->root, NULL);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#else

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramanstatic inline dns_rbtnode_t *

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramanget_subtree_root(dns_rbtnode_t *node) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman while (!IS_ROOT(node)) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman node = PARENT(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman }

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman return (node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman}

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrencestatic inline dns_rbtnode_t *

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramanget_upper_node(dns_rbtnode_t *node) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman dns_rbtnode_t *root = get_subtree_root(node);

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater /*

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (PARENT(root));

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence}

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#endif /* DNS_RBT_USEHASH */

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramandns__rbtnode_getdistance(dns_rbtnode_t *node) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman size_t nodes = 1;

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman while (node != NULL) {

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman if (IS_ROOT(node))

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman break;

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman nodes++;

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman node = PARENT(node);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman }

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman return (nodes);

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman}

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic isc_result_t

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencecreate_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);

a09c545af1ceb8eb6f3aa2bb6fae286208a72141David Lawrence

08e57545c2b1068080f5bf317224160426801406Brian Wellington#ifdef DNS_RBT_USEHASH

7554feaef6057f5ea2926076900ac7634b911456Mark Andrewsstatic inline void

40e7c805a8f38ad9b20dd6c688496fc09fc971c2Mark Andrewshash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic inline void

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrenceunhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Huntstatic void

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Huntrehash(dns_rbt_t *rbt, unsigned int newcount);

08e57545c2b1068080f5bf317224160426801406Brian Wellington#else

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#define hash_node(rbt, node, name)

08e57545c2b1068080f5bf317224160426801406Brian Wellington#define unhash_node(rbt, node)

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt#define rehash(rbt, newcount)

08e57545c2b1068080f5bf317224160426801406Brian Wellington#endif

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrence

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic inline void

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencerotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic inline void

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencerotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic void

7829fad4093f2c1985b1efb7cea00287ff015d2bckbaddonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_rbtnode_t **rootp);

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrence

092b4e5359c5982a438e36ced3dbefc313f7fbfcDavid Lawrencestatic void

bfde61d5194a534d800f3b90008d1f52261922c5Mark Andrewsdeletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Huntstatic isc_result_t

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunttreefix(dns_rbt_t *rbt, void *base, size_t size,

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt dns_rbtnode_t *n, dns_name_t *name,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt dns_rbtdatafixer_t datafixer, void *fixer_arg,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt isc_uint64_t *crc);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic void

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramandeletetreeflat(dns_rbt_t *rbt, unsigned int quantum, isc_boolean_t unhash,

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman dns_rbtnode_t **nodep);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic void

ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramanprintnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckbstatic void

7829fad4093f2c1985b1efb7cea00287ff015d2bckbfreenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

d27343c5544b0473679503d839a793a5b567b503Mark Andrewsstatic isc_result_t

7829fad4093f2c1985b1efb7cea00287ff015d2bckbdns_rbt_zero_header(FILE *file) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /*

7829fad4093f2c1985b1efb7cea00287ff015d2bckb char buffer[HEADER_LENGTH];

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_result_t result;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb memset(buffer, 0, HEADER_LENGTH);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (result != ISC_R_SUCCESS)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb result = fflush(file);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (result != ISC_R_SUCCESS)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (ISC_R_SUCCESS);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntstatic isc_once_t once = ISC_ONCE_INIT;

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntstatic void

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntinit_file_version(void) {

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt int n;

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt memset(FILE_VERSION, 0, sizeof(FILE_VERSION));

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt n = snprintf(FILE_VERSION, sizeof(FILE_VERSION),

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt "RBT Image %s %s", dns_major, dns_mapapi);

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt INSIST(n > 0 && (unsigned int)n < sizeof(FILE_VERSION));

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt}

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox Userstatic isc_result_t

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Huntwrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_uint64_t crc)

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt{

7829fad4093f2c1985b1efb7cea00287ff015d2bckb file_header_t header;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_result_t result;

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t location;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb memset(&header, 0, sizeof(file_header_t));

e851ea826066ac5a5b01c2c23218faa0273a12e8Evan Hunt memmove(header.version1, FILE_VERSION, sizeof(header.version1));

e851ea826066ac5a5b01c2c23218faa0273a12e8Evan Hunt memmove(header.version2, FILE_VERSION, sizeof(header.version2));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.first_node_offset = first_node_offset;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.ptrsize = (isc_uint32_t) sizeof(void *);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.bigendian = (1 == htonl(1)) ? 1 : 0;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#ifdef DNS_RDATASET_FIXED

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.rdataset_fixed = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#else

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.rdataset_fixed = 0;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User#endif

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header.nodecount = rbt->nodecount;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt header.crc = crc;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &location));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt location = dns_rbt_serialize_align(location);

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(isc_stdio_seek(file, location, SEEK_SET));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(fflush(file));

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Ensure we are always at the end of the file. */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, 0, SEEK_END));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb cleanup:

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntstatic isc_boolean_t

e7c0f978425f45731b08be1363f20626b0344f23Evan Huntmatch_header_version(file_header_t *header) {

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt if (memcmp(header->version1, FILE_VERSION,

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt sizeof(header->version1)) != 0 ||

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt memcmp(header->version2, FILE_VERSION,

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt sizeof(header->version1)) != 0)

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt {

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt return (ISC_FALSE);

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt }

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt return (ISC_TRUE);

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt}

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox Userstatic isc_result_t

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox Userserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User uintptr_t right, uintptr_t down, uintptr_t parent,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt uintptr_t data, isc_uint64_t *crc)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb{

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_rbtnode_t temp_node;

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t file_position;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb unsigned char *node_data;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb size_t datasize;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_result_t result;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#ifdef DEBUG

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt dns_name_t nodename;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#endif

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb INSIST(node != NULL);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &file_position));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb file_position = dns_rbt_serialize_align(file_position);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, file_position, SEEK_SET));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node = *node;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.down_is_relative = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.left_is_relative = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.right_is_relative = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.parent_is_relative = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.data_is_relative = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.is_mmapped = 1;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /*

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (temp_node.parent != NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.parent = (dns_rbtnode_t *)(parent);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.parent_is_relative = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (temp_node.left != NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.left = (dns_rbtnode_t *)(left);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.left_is_relative = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (temp_node.right != NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.right = (dns_rbtnode_t *)(right);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.right_is_relative = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (temp_node.down != NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.down = (dns_rbtnode_t *)(down);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.down_is_relative = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (temp_node.data != NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.data = (dns_rbtnode_t *)(data);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb temp_node.data_is_relative = 1;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),

7829fad4093f2c1985b1efb7cea00287ff015d2bckb file, NULL));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#ifdef DEBUG

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt dns_name_init(&nodename, NULL);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt NODENAME(node, &nodename);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt fprintf(stderr, "serialize ");

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt dns_name_print(&nodename, stderr);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt fprintf(stderr, "\n");

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt hexdump("node header", (unsigned char*) &temp_node,

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt sizeof(dns_rbtnode_t));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt hexdump("node data", node_data, datasize);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#endif

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt sizeof(dns_rbtnode_t));

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

7829fad4093f2c1985b1efb7cea00287ff015d2bckb cleanup:

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrewsstatic isc_result_t

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox Userserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt dns_rbtdatawriter_t datawriter, void *writer_arg,

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt uintptr_t *where, isc_uint64_t *crc)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb{

620620df3a74a5a57dc25221aae5033568703eb2Tinderbox User uintptr_t left = 0, right = 0, down = 0, data = 0;

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t location = 0, offset_adjust;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_result_t result;

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (node == NULL) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (where != NULL)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb *where = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (ISC_R_SUCCESS);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /* Reserve space for current node. */

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &location));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt location = dns_rbt_serialize_align(location);

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(isc_stdio_seek(file, location, SEEK_SET));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /*

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(serialize_nodes(file, getleft(node, NULL), location,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt datawriter, writer_arg, &left, crc));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(serialize_nodes(file, getright(node, NULL), location,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt datawriter, writer_arg, &right, crc));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(serialize_nodes(file, getdown(node, NULL), location,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt datawriter, writer_arg, &down, crc));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (node->data != NULL) {

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t ret;

a3fb84bd1b6a56585c0d8181f2ab0338b0cf852fTinderbox User

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &ret));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt ret = dns_rbt_serialize_align(ret);

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(isc_stdio_seek(file, ret, SEEK_SET));

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt data = ret;

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt datawriter(file, node->data, writer_arg, crc);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /* Seek back to reserved space. */

47c5b8af920a93763c97d9a93ea1fd766961a5b3Evan Hunt CHECK(isc_stdio_seek(file, location, SEEK_SET));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /* Serialize the current node. */

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt CHECK(serialize_node(file, node, left, right, down, parent, data, crc));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Ensure we are always at the end of the file. */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, 0, SEEK_END));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (where != NULL)

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt *where = (uintptr_t) location;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb cleanup:

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Huntdns_rbt_serialize_align(off_t target) {

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t offset = target % 8;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (offset == 0)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (target);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb else

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (target + 8 - offset);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox Userdns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_rbtdatawriter_t datawriter,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt void *writer_arg, off_t *offset)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb{

7829fad4093f2c1985b1efb7cea00287ff015d2bckb isc_result_t result;

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt off_t header_position, node_position, end_position;

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_uint64_t crc;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb REQUIRE(file != NULL);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_file_isplainfilefd(fileno(file)));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_init(&crc);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &header_position));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Write dummy header */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(dns_rbt_zero_header(file));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Serialize nodes */

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &node_position));

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt CHECK(serialize_nodes(file, rbt->root, 0, datawriter,

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt writer_arg, NULL, &crc));

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

31707708c585c53b61ca1edb2e224e6bb1b985a5Evan Hunt CHECK(isc_stdio_tell(file, &end_position));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (node_position == end_position) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, header_position, SEEK_SET));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb *offset = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (ISC_R_SUCCESS);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_final(&crc);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#ifdef DEBUG

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews hexdump("serializing CRC", (unsigned char *)&crc, sizeof(crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#endif

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Serialize header */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, header_position, SEEK_SET));

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt CHECK(write_header(file, rbt, HEADER_LENGTH, crc));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Ensure we are always at the end of the file. */

7829fad4093f2c1985b1efb7cea00287ff015d2bckb CHECK(isc_stdio_seek(file, 0, SEEK_END));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb *offset = dns_rbt_serialize_align(header_position);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb cleanup:

7829fad4093f2c1985b1efb7cea00287ff015d2bckb return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt#define CONFIRM(a) do { \

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (! (a)) { \

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt result = ISC_R_INVALIDFILE; \

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt goto cleanup; \

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } \

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt} while(0);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Huntstatic isc_result_t

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunttreefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt dns_name_t *name, dns_rbtdatafixer_t datafixer,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt void *fixer_arg, isc_uint64_t *crc)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb{

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt isc_result_t result = ISC_R_SUCCESS;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_fixedname_t fixed;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_name_t nodename, *fullname;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt unsigned char *node_data;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt dns_rbtnode_t header;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (n == NULL)

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt return (ISC_R_SUCCESS);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM((void *) n >= base);

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM((char *) n - (char *) base <= (int) nodemax);

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM(DNS_RBTNODE_VALID(n));

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_name_init(&nodename, NULL);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb NODENAME(n, &nodename);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb fullname = &nodename;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM(dns_name_isvalid(fullname));

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (!dns_name_isabsolute(&nodename)) {

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_fixedname_init(&fixed);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb fullname = dns_fixedname_name(&fixed);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /* memorize header contents prior to fixup */

e851ea826066ac5a5b01c2c23218faa0273a12e8Evan Hunt memmove(&header, n, sizeof(header));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (n->left_is_relative) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->left = getleft(n, rbt->mmap_location);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->left_is_relative = 0;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(DNS_RBTNODE_VALID(n->left));

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } else

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->left == NULL);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (n->right_is_relative) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->right = getright(n, rbt->mmap_location);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->right_is_relative = 0;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(DNS_RBTNODE_VALID(n->right));

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } else

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->right == NULL);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (n->down_is_relative) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->down = getdown(n, rbt->mmap_location);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->down_is_relative = 0;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM(n->down > (dns_rbtnode_t *) n);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(DNS_RBTNODE_VALID(n->down));

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } else

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->down == NULL);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (n->parent_is_relative) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->parent = getparent(n, rbt->mmap_location);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->parent_is_relative = 0;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM(n->parent < (dns_rbtnode_t *) n);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(DNS_RBTNODE_VALID(n->parent));

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } else

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->parent == NULL);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt if (n->data_is_relative) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->data <= (void *) filesize);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->data = getdata(n, rbt->mmap_location);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt n->data_is_relative = 0;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt CONFIRM(n->data > (void *) n);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt } else

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CONFIRM(n->data == NULL);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb hash_node(rbt, n, fullname);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt /* a change in the order (from left, right, down) will break hashing*/

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (n->left != NULL)

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CHECK(treefix(rbt, base, filesize, n->left, name,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt datafixer, fixer_arg, crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt if (n->right != NULL)

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CHECK(treefix(rbt, base, filesize, n->right, name,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt datafixer, fixer_arg, crc));

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (n->down != NULL)

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CHECK(treefix(rbt, base, filesize, n->down, fullname,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt datafixer, fixer_arg, crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt if (datafixer != NULL && n->data != NULL)

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt CHECK(datafixer(n, base, filesize, fixer_arg, crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt rbt->nodecount++;

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#ifdef DEBUG

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt fprintf(stderr, "deserialize ");

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt dns_name_print(&nodename, stderr);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt fprintf(stderr, "\n");

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt hexdump("node header", (unsigned char *) &header,

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt sizeof(dns_rbtnode_t));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt hexdump("node data", node_data, datasize);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#endif

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_update(crc, (const isc_uint8_t *) &header,

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt sizeof(dns_rbtnode_t));

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_update(crc, (const isc_uint8_t *) node_data,

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt datasize);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt cleanup:

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Huntdns_rbt_deserialize_tree(void *base_address, size_t filesize,

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt off_t header_offset, isc_mem_t *mctx,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt dns_rbtdeleter_t deleter, void *deleter_arg,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt dns_rbtdatafixer_t datafixer, void *fixer_arg,

7829fad4093f2c1985b1efb7cea00287ff015d2bckb dns_rbtnode_t **originp, dns_rbt_t **rbtp)

7829fad4093f2c1985b1efb7cea00287ff015d2bckb{

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt isc_result_t result = ISC_R_SUCCESS;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb file_header_t *header;

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt dns_rbt_t *rbt = NULL;

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_uint64_t crc;

c76e8412f4ff4f5945157410312df2a8950f942dMark Andrews unsigned int host_big_endian;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb REQUIRE(originp == NULL || *originp == NULL);

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt REQUIRE(rbtp != NULL && *rbtp == NULL);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_init(&crc);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

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

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt rbt->mmap_location = base_address;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

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

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt if (!match_header_version(header)) {

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt result = ISC_R_INVALIDFILE;

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt goto cleanup;

e7c0f978425f45731b08be1363f20626b0344f23Evan Hunt }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#ifdef DNS_RDATASET_FIXED

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (header->rdataset_fixed != 1) {

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt result = ISC_R_INVALIDFILE;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt goto cleanup;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#else

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (header->rdataset_fixed != 0) {

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt result = ISC_R_INVALIDFILE;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt goto cleanup;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb#endif

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt result = ISC_R_INVALIDFILE;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt goto cleanup;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

c76e8412f4ff4f5945157410312df2a8950f942dMark Andrews

c76e8412f4ff4f5945157410312df2a8950f942dMark Andrews host_big_endian = (1 == htonl(1));

c76e8412f4ff4f5945157410312df2a8950f942dMark Andrews if (header->bigendian != host_big_endian) {

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt result = ISC_R_INVALIDFILE;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt goto cleanup;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb }

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb /* Copy other data items from the header into our rbt. */

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt rbt->root = (dns_rbtnode_t *)((char *)base_address +

7829fad4093f2c1985b1efb7cea00287ff015d2bckb header_offset + header->first_node_offset);

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt result = ISC_R_INVALIDFILE;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt goto cleanup;

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt }

127a4a90b0d03ebf55ad44d25f75b30c3a6fb728Evan Hunt rehash(rbt, header->nodecount);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt CHECK(treefix(rbt, base_address, filesize, rbt->root,

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Hunt dns_rootname, datafixer, fixer_arg, &crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt isc_crc64_final(&crc);

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#ifdef DEBUG

3911e7610f29dc664cbe8336f35c0652cd74652eMark Andrews hexdump("deserializing CRC", (unsigned char *)&crc, sizeof(crc));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt#endif

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt /* Check file hash */

e59937c7283216ca22ce6e7937b06eab6d97f4acEvan Hunt if (header->crc != crc) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt result = ISC_R_INVALIDFILE;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt goto cleanup;

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt }

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman if (header->nodecount != rbt->nodecount) {

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman result = ISC_R_INVALIDFILE;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman goto cleanup;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#ifdef DNS_RBT_USEHASH

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman fixup_uppernodes(rbt);

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#endif /* DNS_RBT_USEHASH */

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt *rbtp = rbt;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb if (originp != NULL)

1a076410c260ff1d3124ce8b7e22ac111e9cf92aEvan Hunt *originp = rbt->root;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt cleanup:

adbb48b4a0c6216f96d8b40712f23da893444f1cMark Andrews if (result != ISC_R_SUCCESS && rbt != NULL) {

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt rbt->root = NULL;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt rbt->nodecount = 0;

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt dns_rbt_destroy(&rbt);

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt }

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt

d9f0c713fe1d50f1848ca827c5f31db79d904f04Evan Hunt return (result);

7829fad4093f2c1985b1efb7cea00287ff015d2bckb}

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrews

b7e40659efd6cf6f5e6b3b1f904f16f74efb0d16Evan Huntdns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater void *deleter_arg, dns_rbt_t **rbtp)

1630fce031f7a3e33f0579e477a3e17d1993e1f9Bob Halley{

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#ifdef DNS_RBT_USEHASH

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater isc_result_t result;

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#endif

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_rbt_t *rbt;

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(mctx != NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(rbtp != NULL && *rbtp == NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (rbt == NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (ISC_R_NOMEMORY);

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff

df925e6c66d45d960fbac0383169763967d2111cEvan Hunt rbt->mctx = NULL;

df925e6c66d45d960fbac0383169763967d2111cEvan Hunt isc_mem_attach(mctx, &rbt->mctx);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->data_deleter = deleter;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->deleter_arg = deleter_arg;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->root = NULL;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->nodecount = 0;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->hashtable = NULL;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->hashsize = 0;

7829fad4093f2c1985b1efb7cea00287ff015d2bckb rbt->mmap_location = NULL;

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#ifdef DNS_RBT_USEHASH

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater result = inithash(rbt);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (result != ISC_R_SUCCESS) {

df925e6c66d45d960fbac0383169763967d2111cEvan Hunt isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (result);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

7554feaef6057f5ea2926076900ac7634b911456Mark Andrews#endif

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->magic = RBT_MAGIC;

b239c8294a5653d21876d084e0c5b029f6b9fc5dMichael Graff

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater *rbtp = rbt;

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (ISC_R_SUCCESS);

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence}

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrencedns_rbt_destroy(dns_rbt_t **rbtp) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrews}

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrews

a03848252fa85734ca75beae3d0b01bb503c0a8bMark Andrewsdns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_rbt_t *rbt;

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

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

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt = *rbtp;

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman deletetreeflat(rbt, quantum, ISC_FALSE, &rbt->root);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (rbt->root != NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (ISC_R_QUOTA);

73d62a89f1493865c33c689b3ee3de91c74ad58eDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater INSIST(rbt->nodecount == 0);

8e6b386ab7e2d1bd8efedecbb8f4efb6b572a866Tinderbox User

7829fad4093f2c1985b1efb7cea00287ff015d2bckb rbt->mmap_location = NULL;

83e6eb0dfe7d3525dcf093f440e04e8971c4c5d2Brian Wellington

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (rbt->hashtable != NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater isc_mem_put(rbt->mctx, rbt->hashtable,

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->hashsize * sizeof(dns_rbtnode_t *));

b65f2ab14abb4b6ef906d7d02064fba158f07b1eDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->magic = 0;

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

df925e6c66d45d960fbac0383169763967d2111cEvan Hunt isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater *rbtp = NULL;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (ISC_R_SUCCESS);

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence}

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

83e6eb0dfe7d3525dcf093f440e04e8971c4c5d2Brian Wellingtonunsigned int

83e6eb0dfe7d3525dcf093f440e04e8971c4c5d2Brian Wellingtondns_rbt_nodecount(dns_rbt_t *rbt) {

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(VALID_RBT(rbt));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (rbt->nodecount);

83e6eb0dfe7d3525dcf093f440e04e8971c4c5d2Brian Wellington}

83e6eb0dfe7d3525dcf093f440e04e8971c4c5d2Brian Wellington

dd2a0a6d2dec1c23787351e51b434a838dec5603Evan Huntdns_rbt_hashsize(dns_rbt_t *rbt) {

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

dd2a0a6d2dec1c23787351e51b434a838dec5603Evan Hunt REQUIRE(VALID_RBT(rbt));

03b5d2689df73fa9a50ff684511fa9d81f317e6cEvan Hunt

dd2a0a6d2dec1c23787351e51b434a838dec5603Evan Hunt return (rbt->hashsize);

dd2a0a6d2dec1c23787351e51b434a838dec5603Evan Hunt}

dd2a0a6d2dec1c23787351e51b434a838dec5603Evan Hunt

3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graffstatic inline isc_result_t

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrencechain_name(dns_rbtnodechain_t *chain, dns_name_t *name,

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater isc_boolean_t include_chain_end)

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence{

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_t nodename;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater isc_result_t result = ISC_R_SUCCESS;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater int i;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_init(&nodename, NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (include_chain_end && chain->end != NULL) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater NODENAME(chain->end, &nodename);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater result = dns_name_copy(&nodename, name, NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (result != ISC_R_SUCCESS)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (result);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater } else

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_reset(name);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater for (i = (int)chain->level_count - 1; i >= 0; i--) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater NODENAME(chain->levels[i], &nodename);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater result = dns_name_concatenate(name, &nodename, name, NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (result != ISC_R_SUCCESS)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (result);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (result);

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence}

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graffstatic inline isc_result_t

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrencemove_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater do {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater /*

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater while (RIGHT(node) != NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater node = RIGHT(node);

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (DOWN(node) == NULL)

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater break;

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater ADD_LEVEL(chain, node);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater node = DOWN(node);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater } while (1);

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater chain->end = node;

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (ISC_R_SUCCESS);

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence}

ec80744ad68b97f15657b1fdf5591c30b559b57dDavid Lawrence

f389bc2c9e9e434380e10221778b7b548612a67fDavid Lawrence

0f5962ac3e4ef336faff68f1cb838505e64665e5David Lawrencedns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater /*

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_rbtnode_t **root, *parent, *child, *current, *new_current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_offsets_t current_offsets;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_namereln_t compared;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater isc_result_t result = ISC_R_SUCCESS;

9267cc8e83c4f3cf98cdebe6553143812250beccMukund Sivaraman unsigned int level_count;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater unsigned int common_labels;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater unsigned int nlabels, hlabels;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater int order;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(VALID_RBT(rbt));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(dns_name_isabsolute(name));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater REQUIRE(nodep != NULL && *nodep == NULL);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman /*

614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater /*

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_fixedname_init(&fixedcopy);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater add_name = dns_fixedname_name(&fixedcopy);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_clone(name, add_name);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

d1dbf6b20fdcfa95acd75cdb96fcd57067a31144Mukund Sivaraman if (ISC_UNLIKELY(rbt->root == NULL)) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater result = create_node(rbt->mctx, add_name, &new_current);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (result == ISC_R_SUCCESS) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->nodecount++;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater new_current->is_root = 1;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#ifdef DNS_RBT_USEHASH

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman UPPERNODE(new_current) = NULL;

5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman#endif /* DNS_RBT_USEHASH */

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater rbt->root = new_current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater *nodep = new_current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater hash_node(rbt, new_current, name);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater return (result);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

9267cc8e83c4f3cf98cdebe6553143812250beccMukund Sivaraman level_count = 0;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_fixedname_init(&fixedprefix);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_fixedname_init(&fixedsuffix);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater prefix = dns_fixedname_name(&fixedprefix);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater suffix = dns_fixedname_name(&fixedsuffix);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater root = &rbt->root;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater INSIST(IS_ROOT(*root));

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater parent = NULL;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater current = NULL;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater child = *root;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_name_init(&current_name, current_offsets);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater dns_fixedname_init(&fnewname);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater new_name = dns_fixedname_name(&fnewname);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater nlabels = dns_name_countlabels(name);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater hlabels = 0;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater do {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater current = child;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater NODENAME(current, &current_name);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater compared = dns_name_fullcompare(add_name, &current_name,

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater &order, &common_labels);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (compared == dns_namereln_equal) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater *nodep = current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater result = ISC_R_EXISTS;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater break;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (compared == dns_namereln_none) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater if (order < 0) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater parent = current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater child = LEFT(current);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater } else if (order > 0) {

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater parent = current;

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater child = RIGHT(current);

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater }

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater

f731b5d665e484c9b9634531c791cee9d87ab7a0Automatic Updater } else {