rbt.c 83.8 KB
Newer Older
1
/*
Tinderbox User's avatar
Tinderbox User committed
2
 * Copyright (C) 2004, 2005, 2007-2009, 2011-2014  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1999-2003  Internet Software Consortium.
4
 *
Automatic Updater's avatar
Automatic Updater committed
5
 * Permission to use, copy, modify, and/or distribute this software for any
6
7
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
8
 *
Mark Andrews's avatar
Mark Andrews committed
9
10
11
12
13
14
15
 * 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.
16
17
 */

18
/*! \file */
David Lawrence's avatar
David Lawrence committed
19
20
21

/* Principal Authors: DCL */

Michael Graff's avatar
Michael Graff committed
22
23
#include <config.h>

24
#include <sys/stat.h>
Evan Hunt's avatar
Evan Hunt committed
25
26
27
#ifdef HAVE_INTTYPES_H
#include <inttypes.h> /* uintptr_t */
#endif
28

29
#include <isc/crc64.h>
30
#include <isc/file.h>
Evan Hunt's avatar
Evan Hunt committed
31
#include <isc/hex.h>
32
#include <isc/mem.h>
33
#include <isc/platform.h>
Andreas Gustafsson's avatar
Andreas Gustafsson committed
34
#include <isc/print.h>
35
#include <isc/refcount.h>
36
37
#include <isc/socket.h>
#include <isc/stdio.h>
38
#include <isc/string.h>
39
#include <isc/util.h>
40

41
/*%
42
43
44
45
46
47
 * 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>
48
#include <dns/log.h>
David Lawrence's avatar
David Lawrence committed
49
50
#include <dns/rbt.h>
#include <dns/result.h>
51
52
53
54
55
56
57
58
59
60
#include <dns/version.h>

#include <unistd.h>

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

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

65
/*
66
67
68
 * 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.
69
 */
70
71
#define CHAIN_MAGIC             ISC_MAGIC('0', '-', '0', '-')
#define VALID_CHAIN(chain)      ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
72

73
#define RBT_HASH_SIZE           64
74
75
76

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

80
struct dns_rbt {
Automatic Updater's avatar
Automatic Updater committed
81
82
83
84
85
86
87
88
	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;
89
	void *                  mmap_location;
David Lawrence's avatar
David Lawrence committed
90
91
92
93
94
};

#define RED 0
#define BLACK 1

95
/*
Evan Hunt's avatar
Evan Hunt committed
96
 * This is the header for map-format RBT images.  It is populated,
97
98
99
100
101
102
103
104
105
106
 * 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 */
107
#define HEADER_LENGTH		1024
108
109
110
111

struct file_header {
	char version1[32];
	isc_uint64_t first_node_offset;	/* usually 1024 */
Tinderbox User's avatar
Tinderbox User committed
112
	/*
Evan Hunt's avatar
Evan Hunt committed
113
114
	 * 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
115
116
117
118
119
	 */
	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 */
120
	isc_uint64_t crc;
121
122
123
124
125
126
127
128
129
	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
Tinderbox User's avatar
Tinderbox User committed
130
131
 * 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
132
 * memory.
Tinderbox User's avatar
Tinderbox User committed
133
 * step three: write out the header, adding the information that will be
134
135
136
137
138
139
140
141
142
143
144
145
146
 * 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
Evan Hunt's avatar
Evan Hunt committed
147
write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
148
	     isc_uint64_t crc);
149
150

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

static isc_result_t
156
serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
157
		dns_rbtdatawriter_t datawriter, void *writer_arg,
158
		uintptr_t *where, isc_uint64_t *crc);
159
/*
Tinderbox User's avatar
Tinderbox User committed
160
161
 * 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
162
163
164
165
166
 * relative or not
 */
static inline dns_rbtnode_t *
getparent(dns_rbtnode_t *node, file_header_t *header) {
	char *adjusted_address = (char *)(node->parent);
167
	adjusted_address += node->parent_is_relative * (uintptr_t)header;
Tinderbox User's avatar
Tinderbox User committed
168

169
170
171
172
173
174
	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);
175
	adjusted_address += node->left_is_relative * (uintptr_t)header;
Tinderbox User's avatar
Tinderbox User committed
176

177
178
179
180
181
182
	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);
183
	adjusted_address += node->right_is_relative * (uintptr_t)header;
Tinderbox User's avatar
Tinderbox User committed
184

185
186
187
188
189
190
	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);
191
	adjusted_address += node->down_is_relative * (uintptr_t)header;
Tinderbox User's avatar
Tinderbox User committed
192

193
194
195
196
197
198
	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);
199
	adjusted_address += node->data_is_relative * (uintptr_t)header;
Tinderbox User's avatar
Tinderbox User committed
200

201
202
203
	return ((dns_rbtnode_t *)adjusted_address);
}

204
/*%
205
206
 * Elements of the rbtnode structure.
 */
207
208
209
210
211
212
213
214
215
#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)
216
#define OLDNAMELEN(node)        ((node)->oldnamelen)
217
218
219
220
#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)
221

222
/*%
223
224
225
 * Structure elements from the rbtdb.c, not
 * used as part of the rbt.c algorithms.
 */
226
227
228
#define DIRTY(node)     ((node)->dirty)
#define WILD(node)      ((node)->wild)
#define LOCKNUM(node)   ((node)->locknum)
229

230
/*%
231
232
233
234
235
236
237
238
239
 * 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.
240
 */
241

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

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

249
/*%
250
251
 * Color management.
 */
252
253
254
255
#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)
David Lawrence's avatar
David Lawrence committed
256

257
/*%
258
 * Chain management.
259
260
 *
 * The "ancestors" member of chains were removed, with their job now
Francis Dupont's avatar
Francis Dupont committed
261
 * being wholly handled by parent pointers (which didn't exist, because
262
 * of memory concerns, when chains were first implemented).
263
 */
264
#define ADD_LEVEL(chain, node) \
Automatic Updater's avatar
Automatic Updater committed
265
			(chain)->levels[(chain)->level_count++] = (node)
266

267
/*%
268
269
270
271
272
 * 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.
 */

273
static inline void
274
NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
275
276
277
278
279
280
281
	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;
}
282

283
284
285
286
287
#ifdef DNS_RBT_USEHASH
static isc_result_t
inithash(dns_rbt_t *rbt);
#endif

288
289
290
291
292
#ifdef DEBUG
#define inline
/*
 * A little something to help out in GDB.
 */
293
dns_name_t Name(dns_rbtnode_t *node);
294
dns_name_t
David Lawrence's avatar
David Lawrence committed
295
Name(dns_rbtnode_t *node) {
Automatic Updater's avatar
Automatic Updater committed
296
	dns_name_t name;
297

Automatic Updater's avatar
Automatic Updater committed
298
299
300
	dns_name_init(&name, NULL);
	if (node != NULL)
		NODENAME(node, &name);
301

Automatic Updater's avatar
Automatic Updater committed
302
	return (name);
303
}
David Lawrence's avatar
Major:    
David Lawrence committed
304

305
static void printnodename(dns_rbtnode_t *node);
Evan Hunt's avatar
Evan Hunt committed
306
307
308
309
310
311
312
313
314
315
316
317
318
319

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);
}
320
321
#endif

322
323
static inline dns_rbtnode_t *
find_up(dns_rbtnode_t *node) {
Automatic Updater's avatar
Automatic Updater committed
324
	dns_rbtnode_t *root;
325

Automatic Updater's avatar
Automatic Updater committed
326
327
328
329
330
331
332
	/*
	 * 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. */
333

Automatic Updater's avatar
Automatic Updater committed
334
	return (PARENT(root));
335
336
}

337
338
339
/*
 * Forward declarations.
 */
340
341
static isc_result_t
create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
342

343
#ifdef DNS_RBT_USEHASH
344
static inline void
345
hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
346
static inline void
347
unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
348
349
static void
rehash(dns_rbt_t *rbt, unsigned int newcount);
350
#else
351
#define hash_node(rbt, node, name)
352
#define unhash_node(rbt, node)
353
#define rehash(rbt, newcount)
354
#endif
David Lawrence's avatar
David Lawrence committed
355

356
357
358
359
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);
360

361
static void
362
363
addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
	   dns_rbtnode_t **rootp);
364
365

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

368
369
370
static isc_result_t
treefix(dns_rbt_t *rbt, void *base, size_t size,
	dns_rbtnode_t *n, dns_name_t *name,
371
372
	dns_rbtdatafixer_t datafixer, void *fixer_arg,
	isc_uint64_t *crc);
373
374
375
376
377
378
379
380
381
382
383
384
385

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);

Mark Andrews's avatar
Mark Andrews committed
386
static isc_result_t
387
388
389
390
391
392
393
394
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;
Tinderbox User's avatar
Tinderbox User committed
395

396
397
398
399
400
401
402
403
	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);
Tinderbox User's avatar
Tinderbox User committed
404

405
406
407
408
409
410
411
412
413
414
	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.
 */
Tinderbox User's avatar
Tinderbox User committed
415
static isc_result_t
Evan Hunt's avatar
Evan Hunt committed
416
write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
417
	     isc_uint64_t crc)
Evan Hunt's avatar
Evan Hunt committed
418
{
419
420
	file_header_t header;
	isc_result_t result;
421
	off_t location;
Tinderbox User's avatar
Tinderbox User committed
422

423
424
425
	if (FILE_VERSION[0] == '\0') {
		memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
		snprintf(FILE_VERSION, sizeof(FILE_VERSION),
Evan Hunt's avatar
Evan Hunt committed
426
			 "RBT Image %s %s", dns_major, dns_mapapi);
427
428
429
	}

	memset(&header, 0, sizeof(file_header_t));
430
431
	memmove(header.version1, FILE_VERSION, sizeof(header.version1));
	memmove(header.version2, FILE_VERSION, sizeof(header.version2));
432
433
434
	header.first_node_offset = first_node_offset;
	header.ptrsize = (isc_uint32_t) sizeof(void *);
	header.bigendian = (1 == htonl(1)) ? 1 : 0;
Tinderbox User's avatar
Tinderbox User committed
435

436
437
438
439
#ifdef DNS_RDATASET_FIXED
	header.rdataset_fixed = 1;
#else
	header.rdataset_fixed = 0;
Tinderbox User's avatar
Tinderbox User committed
440
441
#endif

442
443
	header.nodecount = rbt->nodecount;

444
	header.crc = crc;
Evan Hunt's avatar
Evan Hunt committed
445

446
	CHECK(isc_stdio_tell(file, &location));
Evan Hunt's avatar
Evan Hunt committed
447
448
	location = dns_rbt_serialize_align(location);
	CHECK(isc_stdio_seek(file, location, SEEK_SET));
449
450
	CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
	CHECK(fflush(file));
Tinderbox User's avatar
Tinderbox User committed
451

452
453
454
455
456
457
458
	/* Ensure we are always at the end of the file. */
	CHECK(isc_stdio_seek(file, 0, SEEK_END));

 cleanup:
	return (result);
}

Tinderbox User's avatar
Tinderbox User committed
459
static isc_result_t
460
461
serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
	       uintptr_t right, uintptr_t down, uintptr_t parent,
462
	       uintptr_t data, isc_uint64_t *crc)
463
464
{
	dns_rbtnode_t temp_node;
465
	off_t file_position;
466
467
468
	unsigned char *node_data;
	size_t datasize;
	isc_result_t result;
Evan Hunt's avatar
Evan Hunt committed
469
470
471
#ifdef DEBUG
	dns_name_t nodename;
#endif
472
473
474

	INSIST(node != NULL);

475
	CHECK(isc_stdio_tell(file, &file_position));
476
477
478
479
480
481
482
483
484
485
	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;
Tinderbox User's avatar
Tinderbox User committed
486

487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
	/*
	 * 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));

Evan Hunt's avatar
Evan Hunt committed
521
522
523
524
525
526
527
528
529
530
531
#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

532
	isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,
Evan Hunt's avatar
Evan Hunt committed
533
			sizeof(dns_rbtnode_t));
534
	isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);
Evan Hunt's avatar
Evan Hunt committed
535

536
537
538
 cleanup:
	return (result);
}
539

540
static isc_result_t
541
serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
542
		dns_rbtdatawriter_t datawriter, void *writer_arg,
543
		uintptr_t *where, isc_uint64_t *crc)
544
{
545
	uintptr_t left = 0, right = 0, down = 0, data = 0;
546
	off_t location = 0, offset_adjust;
547
	isc_result_t result;
Tinderbox User's avatar
Tinderbox User committed
548

549
550
551
552
553
554
	if (node == NULL) {
		if (where != NULL)
			*where = 0;
		return (ISC_R_SUCCESS);
	}

Evan Hunt's avatar
Evan Hunt committed
555
	/* Reserve space for current node. */
556
	CHECK(isc_stdio_tell(file, &location));
Evan Hunt's avatar
Evan Hunt committed
557
558
559
560
	location = dns_rbt_serialize_align(location);
	CHECK(isc_stdio_seek(file, location, SEEK_SET));

	offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
561
	CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
Tinderbox User's avatar
Tinderbox User committed
562

Evan Hunt's avatar
Evan Hunt committed
563
564
565
566
	/*
	 * Serialize the rest of the tree.
	 *
	 * WARNING: A change in the order (from left, right, down)
567
	 * will break the way the crc hash is computed.
Evan Hunt's avatar
Evan Hunt committed
568
	 */
Evan Hunt's avatar
Evan Hunt committed
569
	CHECK(serialize_nodes(file, getleft(node, NULL), location,
570
			      datawriter, writer_arg, &left, crc));
Evan Hunt's avatar
Evan Hunt committed
571
	CHECK(serialize_nodes(file, getright(node, NULL), location,
572
			      datawriter, writer_arg, &right, crc));
Evan Hunt's avatar
Evan Hunt committed
573
	CHECK(serialize_nodes(file, getdown(node, NULL), location,
574
			      datawriter, writer_arg, &down, crc));
575
576

	if (node->data != NULL) {
577
		off_t ret;
Tinderbox User's avatar
Tinderbox User committed
578

579
		CHECK(isc_stdio_tell(file, &ret));
Evan Hunt's avatar
Evan Hunt committed
580
581
582
583
		ret = dns_rbt_serialize_align(ret);
		CHECK(isc_stdio_seek(file, ret, SEEK_SET));
		data = ret;

584
		datawriter(file, node->data, writer_arg, crc);
585
	}
Tinderbox User's avatar
Tinderbox User committed
586

Evan Hunt's avatar
Evan Hunt committed
587
	/* Seek back to reserved space. */
Evan Hunt's avatar
Evan Hunt committed
588
	CHECK(isc_stdio_seek(file, location, SEEK_SET));
589

Evan Hunt's avatar
Evan Hunt committed
590
	/* Serialize the current node. */
591
	CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
592
593
594
595
596

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

	if (where != NULL)
597
		*where = (uintptr_t) location;
598
599
600
601
602

 cleanup:
	return (result);
}

603
604
605
off_t
dns_rbt_serialize_align(off_t target) {
	off_t offset = target % 8;
606
607
608
609
610
611
612

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

Tinderbox User's avatar
Tinderbox User committed
613
614
isc_result_t
dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
615
		       dns_rbtdatawriter_t datawriter,
616
		       void *writer_arg, off_t *offset)
617
618
{
	isc_result_t result;
619
	off_t header_position, node_position, end_position;
620
	isc_uint64_t crc;
621
622

	REQUIRE(file != NULL);
Tinderbox User's avatar
Tinderbox User committed
623

624
625
	CHECK(isc_file_isplainfilefd(fileno(file)));

626
	isc_crc64_init(&crc);
Evan Hunt's avatar
Evan Hunt committed
627

628
	CHECK(isc_stdio_tell(file, &header_position));
629
630
631
632
633

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

	/* Serialize nodes */
634
	CHECK(isc_stdio_tell(file, &node_position));
635
	CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
636
			      writer_arg, NULL, &crc));
Tinderbox User's avatar
Tinderbox User committed
637

638
	CHECK(isc_stdio_tell(file, &end_position));
639
640
641
642
643
	if (node_position == end_position) {
		CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
		*offset = 0;
		return (ISC_R_SUCCESS);
	}
Tinderbox User's avatar
Tinderbox User committed
644

645
	isc_crc64_final(&crc);
Evan Hunt's avatar
Evan Hunt committed
646
#ifdef DEBUG
647
	hexdump("serializing CRC", &crc, sizeof(crc));
Evan Hunt's avatar
Evan Hunt committed
648
649
#endif

650
651
	/* Serialize header */
	CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
652
	CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
653
654
655
656
657
658
659
660

	/* 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);
}
661

662
663
664
665
666
667
668
669
670
#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,
671
672
	dns_name_t *name, dns_rbtdatafixer_t datafixer,
	void *fixer_arg, isc_uint64_t *crc)
673
{
674
	isc_result_t result = ISC_R_SUCCESS;
675
676
	dns_fixedname_t fixed;
	dns_name_t nodename, *fullname;
Evan Hunt's avatar
Evan Hunt committed
677
678
	unsigned char *node_data;
	dns_rbtnode_t header;
679
	size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
680
681

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

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

688
689
690
691
	dns_name_init(&nodename, NULL);
	NODENAME(n, &nodename);

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

694
695
696
	if (!dns_name_isabsolute(&nodename)) {
		dns_fixedname_init(&fixed);
		fullname = dns_fixedname_name(&fixed);
697
		CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
698
	}
Tinderbox User's avatar
Tinderbox User committed
699

Evan Hunt's avatar
Evan Hunt committed
700
	/* memorize header contents prior to fixup */
701
	memmove(&header, n, sizeof(header));
Evan Hunt's avatar
Evan Hunt committed
702

703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
	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;
723
		CONFIRM(n->down > (dns_rbtnode_t *) n);
724
725
726
727
728
729
730
731
		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;
732
		CONFIRM(n->parent < (dns_rbtnode_t *) n);
733
734
735
736
737
738
739
740
		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;
741
		CONFIRM(n->data > (void *) n);
742
743
	} else
		CONFIRM(n->data == NULL);
Tinderbox User's avatar
Tinderbox User committed
744

745
	hash_node(rbt, n, fullname);
Tinderbox User's avatar
Tinderbox User committed
746

Evan Hunt's avatar
Evan Hunt committed
747
	/* a change in the order (from left, right, down) will break hashing*/
748
	if (n->left != NULL)
749
		CHECK(treefix(rbt, base, filesize, n->left, name,
750
			      datafixer, fixer_arg, crc));
Evan Hunt's avatar
Evan Hunt committed
751
	if (n->right != NULL)
752
		CHECK(treefix(rbt, base, filesize, n->right, name,
753
			      datafixer, fixer_arg, crc));
754
	if (n->down != NULL)
755
		CHECK(treefix(rbt, base, filesize, n->down, fullname,
756
			      datafixer, fixer_arg, crc));
Evan Hunt's avatar
Evan Hunt committed
757
758

	if (datafixer != NULL && n->data != NULL)
759
		CHECK(datafixer(n, base, filesize, fixer_arg, crc));
Evan Hunt's avatar
Evan Hunt committed
760

761
	rbt->nodecount++;
Evan Hunt's avatar
Evan Hunt committed
762
763
764
765
766
767
768
769
770
771
772
	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
773
	isc_crc64_update(crc, (const isc_uint8_t *) &header,
Evan Hunt's avatar
Evan Hunt committed
774
			sizeof(dns_rbtnode_t));
775
	isc_crc64_update(crc, (const isc_uint8_t *) node_data,
Evan Hunt's avatar
Evan Hunt committed
776
			datasize);
777
778
779

 cleanup:
	return (result);
780
781
}

Tinderbox User's avatar
Tinderbox User committed
782
isc_result_t
783
784
dns_rbt_deserialize_tree(void *base_address, size_t filesize,
			 off_t header_offset, isc_mem_t *mctx,
785
786
			 dns_rbtdeleter_t deleter, void *deleter_arg,
			 dns_rbtdatafixer_t datafixer, void *fixer_arg,
787
788
			 dns_rbtnode_t **originp, dns_rbt_t **rbtp)
{
789
	isc_result_t result = ISC_R_SUCCESS;
790
	file_header_t *header;
791
	dns_rbt_t *rbt = NULL;
792
	isc_uint64_t crc;
793
794

	REQUIRE(originp == NULL || *originp == NULL);
795
	REQUIRE(rbtp != NULL && *rbtp == NULL);
Tinderbox User's avatar
Tinderbox User committed
796

797
	isc_crc64_init(&crc);
Evan Hunt's avatar
Evan Hunt committed
798

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

801
	rbt->mmap_location = base_address;
802
803

	header = (file_header_t *)((char *)base_address + header_offset);
Tinderbox User's avatar
Tinderbox User committed
804

805
806
#ifdef DNS_RDATASET_FIXED
	if (header->rdataset_fixed != 1) {
807
808
		result = ISC_R_INVALIDFILE;
		goto cleanup;
809
	}
Tinderbox User's avatar
Tinderbox User committed
810

811
812
#else
	if (header->rdataset_fixed != 0) {
813
814
		result = ISC_R_INVALIDFILE;
		goto cleanup;
815
816
817
818
	}
#endif

	if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
819
820
		result = ISC_R_INVALIDFILE;
		goto cleanup;
821
822
	}
	if (header->bigendian != (1 == htonl(1)) ? 1 : 0) {
823
824
		result = ISC_R_INVALIDFILE;
		goto cleanup;
825
	}
Tinderbox User's avatar
Tinderbox User committed
826

827
	/* Copy other data items from the header into our rbt. */
828
	rbt->root = (dns_rbtnode_t *)((char *)base_address +
829
				header_offset + header->first_node_offset);
830
831
832
833
834
835

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

	CHECK(treefix(rbt, base_address, filesize, rbt->root,
838
		      dns_rootname, datafixer, fixer_arg, &crc));
Evan Hunt's avatar
Evan Hunt committed
839

840
	isc_crc64_final(&crc);
Evan Hunt's avatar
Evan Hunt committed
841
#ifdef DEBUG
842
	hexdump("deserializing CRC", &crc, sizeof(crc));
Evan Hunt's avatar
Evan Hunt committed
843
844
#endif

845
	/* Check file hash */
846
	if (header->crc != crc) {
847
848
		result = ISC_R_INVALIDFILE;
		goto cleanup;
849
	}
850

851
	*rbtp = rbt;
852
	if (originp != NULL)
853
		*originp = rbt->root;
854

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

858
859
860
861
862
863
864
865
 cleanup:
	if (result != ISC_R_SUCCESS) {
		rbt->root = NULL;
		rbt->nodecount = 0;
		dns_rbt_destroy(&rbt);
	}

	return (result);
866
}
867

868
869
870
/*
 * Initialize a red/black tree of trees.
 */
871
isc_result_t
872
dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
Automatic Updater's avatar
Automatic Updater committed
873
	       void *deleter_arg, dns_rbt_t **rbtp)
874
{
875
#ifdef DNS_RBT_USEHASH
Automatic Updater's avatar
Automatic Updater committed
876
	isc_result_t result;
877
#endif
Automatic Updater's avatar
Automatic Updater committed
878
	dns_rbt_t *rbt;
879

Automatic Updater's avatar
Automatic Updater committed
880
881
882
	REQUIRE(mctx != NULL);
	REQUIRE(rbtp != NULL && *rbtp == NULL);
	REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
883

Automatic Updater's avatar
Automatic Updater committed
884
885
886
	rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
	if (rbt == NULL)
		return (ISC_R_NOMEMORY);
887

888
889
	rbt->mctx = NULL;
	isc_mem_attach(mctx, &rbt->mctx);
Automatic Updater's avatar
Automatic Updater committed
890
891
892
893
894
895
	rbt->data_deleter = deleter;
	rbt->deleter_arg = deleter_arg;
	rbt->root = NULL;
	rbt->nodecount = 0;
	rbt->hashtable = NULL;
	rbt->hashsize = 0;
896
	rbt->mmap_location = NULL;
897

898
#ifdef DNS_RBT_USEHASH
Automatic Updater's avatar
Automatic Updater committed
899
900
	result = inithash(rbt);
	if (result != ISC_R_SUCCESS) {
901
		isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
Automatic Updater's avatar
Automatic Updater committed
902
903
		return (result);
	}
904
#endif
905

Automatic Updater's avatar
Automatic Updater committed
906
	rbt->magic = RBT_MAGIC;
907

Automatic Updater's avatar
Automatic Updater committed
908
	*rbtp = rbt;
909

Automatic Updater's avatar
Automatic Updater committed
910
	return (ISC_R_SUCCESS);
911
912
913
}

/*
914
 * Deallocate a red/black tree of trees.
915
916
917
 */
void
dns_rbt_destroy(dns_rbt_t **rbtp) {
Automatic Updater's avatar
Automatic Updater committed
918
	RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
919
920
921
922
}

isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
Automatic Updater's avatar
Automatic Updater committed
923
	dns_rbt_t *rbt;
924

Automatic Updater's avatar
Automatic Updater committed
925
	REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
926

Automatic Updater's avatar
Automatic Updater committed
927
	rbt = *rbtp;
928

929
	deletetreeflat(rbt, quantum, &rbt->root);
Automatic Updater's avatar
Automatic Updater committed
930
931
	if (rbt->root != NULL)
		return (ISC_R_QUOTA);
David Lawrence's avatar
David Lawrence committed
932

Automatic Updater's avatar
Automatic Updater committed
933
	INSIST(rbt->nodecount == 0);
Tinderbox User's avatar
Tinderbox User committed
934

935
	rbt->mmap_location = NULL;
936

Automatic Updater's avatar
Automatic Updater committed
937
938
939
	if (rbt->hashtable != NULL)
		isc_mem_put(rbt->mctx, rbt->hashtable,
			    rbt->hashsize * sizeof(dns_rbtnode_t *));
940

Automatic Updater's avatar
Automatic Updater committed
941
	rbt->magic = 0;
942

943
	isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
Automatic Updater's avatar
Automatic Updater committed
944
945
	*rbtp = NULL;
	return (ISC_R_SUCCESS);
946
947
}

948
949
unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt) {
Evan Hunt's avatar
Evan Hunt committed
950

Automatic Updater's avatar
Automatic Updater committed
951
	REQUIRE(VALID_RBT(rbt));
Evan Hunt's avatar
Evan Hunt committed
952

Automatic Updater's avatar
Automatic Updater committed
953
	return (rbt->nodecount);
954
955
}

956
957
unsigned int
dns_rbt_hashsize(dns_rbt_t *rbt) {
Evan Hunt's avatar
Evan Hunt committed
958

959
	REQUIRE(VALID_RBT(rbt));
Evan Hunt's avatar
Evan Hunt committed
960

961
962
963
	return (rbt->hashsize);
}

964
static inline isc_result_t