rbtdb.c 118 KB
Newer Older
Bob Halley's avatar
Bob Halley committed
1
/*
Bob Halley's avatar
Bob Halley committed
2
 * Copyright (C) 1999, 2000  Internet Software Consortium.
3
 *
Bob Halley's avatar
Bob Halley committed
4 5 6
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
7
 *
8 9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
 * INTERNET SOFTWARE CONSORTIUM 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.
Bob Halley's avatar
Bob Halley committed
16 17
 */

18
/* $Id: rbtdb.c,v 1.136 2000/12/01 01:22:41 marka Exp $ */
David Lawrence's avatar
David Lawrence committed
19

20 21 22 23
/*
 * Principal Author: Bob Halley
 */

24 25
#include <config.h>

26
#include <isc/mem.h>
27
#include <isc/random.h>
Bob Halley's avatar
Bob Halley committed
28
#include <isc/rwlock.h>
29
#include <isc/string.h>
Michael Graff's avatar
Michael Graff committed
30
#include <isc/util.h>
Bob Halley's avatar
Bob Halley committed
31

32 33
#include <dns/db.h>
#include <dns/dbiterator.h>
34
#include <dns/dnssec.h>
35 36 37
#include <dns/fixedname.h>
#include <dns/masterdump.h>
#include <dns/rbt.h>
38
#include <dns/rdata.h>
Bob Halley's avatar
Bob Halley committed
39 40
#include <dns/rdataset.h>
#include <dns/rdatasetiter.h>
41 42
#include <dns/rdataslab.h>
#include <dns/result.h>
Bob Halley's avatar
Bob Halley committed
43

44 45 46
#ifdef DNS_RBTDB_VERSION64
#include "rbtdb64.h"
#else
Bob Halley's avatar
Bob Halley committed
47
#include "rbtdb.h"
48
#endif
Bob Halley's avatar
Bob Halley committed
49

50 51 52 53 54 55
#ifdef DNS_RBTDB_VERSION64
#define RBTDB_MAGIC			0x52424438U	/* RBD8. */
#else
#define RBTDB_MAGIC			0x52424434U	/* RBD4. */
#endif

Bob Halley's avatar
Bob Halley committed
56 57 58 59
#define VALID_RBTDB(rbtdb)		((rbtdb) != NULL && \
					 (rbtdb)->common.impmagic == \
						RBTDB_MAGIC)

60 61 62 63 64 65
#ifdef DNS_RBTDB_VERSION64
typedef isc_uint64_t			rbtdb_serial_t;
#else
typedef isc_uint32_t			rbtdb_serial_t;
#endif

Bob Halley's avatar
Bob Halley committed
66 67
typedef isc_uint32_t			rbtdb_rdatatype_t;

68 69
#define RBTDB_RDATATYPE_BASE(type)	((dns_rdatatype_t)((type) & 0xFFFF))
#define RBTDB_RDATATYPE_EXT(type)	((dns_rdatatype_t)((type) >> 16))
Bob Halley's avatar
Bob Halley committed
70 71 72 73 74 75 76 77
#define RBTDB_RDATATYPE_VALUE(b, e)	(((e) << 16) | (b))

#define RBTDB_RDATATYPE_SIGNXT \
		RBTDB_RDATATYPE_VALUE(dns_rdatatype_sig, dns_rdatatype_nxt)
#define RBTDB_RDATATYPE_SIGNS \
		RBTDB_RDATATYPE_VALUE(dns_rdatatype_sig, dns_rdatatype_ns)
#define RBTDB_RDATATYPE_SIGCNAME \
		RBTDB_RDATATYPE_VALUE(dns_rdatatype_sig, dns_rdatatype_cname)
Bob Halley's avatar
Bob Halley committed
78 79
#define RBTDB_RDATATYPE_NXDOMAIN \
		RBTDB_RDATATYPE_VALUE(0, dns_rdatatype_any)
Bob Halley's avatar
Bob Halley committed
80

Bob Halley's avatar
Bob Halley committed
81
typedef struct rdatasetheader {
82 83 84
	/*
	 * Locked by the owning node's lock.
	 */
85
	rbtdb_serial_t			serial;
Bob Halley's avatar
Bob Halley committed
86
	dns_ttl_t			ttl;
Bob Halley's avatar
Bob Halley committed
87
	rbtdb_rdatatype_t		type;
88
	isc_uint16_t			attributes;
Bob Halley's avatar
Bob Halley committed
89
	dns_trust_t			trust;
Bob Halley's avatar
Bob Halley committed
90 91
	/*
	 * We don't use the LIST macros, because the LIST structure has
92
	 * both head and tail pointers, and is doubly linked.
Bob Halley's avatar
Bob Halley committed
93 94
	 */
	struct rdatasetheader		*next;
95
	struct rdatasetheader		*down;
Bob Halley's avatar
Bob Halley committed
96 97
} rdatasetheader_t;

Michael Graff's avatar
Michael Graff committed
98 99 100 101 102 103 104 105 106 107 108 109
#define RDATASET_ATTR_NONEXISTENT	0x0001
#define RDATASET_ATTR_STALE		0x0002
#define RDATASET_ATTR_IGNORE		0x0004
#define RDATASET_ATTR_RETAIN		0x0008

/*
 * XXX
 * When the cache will pre-expire data (due to memory low or other
 * situations) before the rdataset's TTL has expired, it MUST
 * respect the RETAIN bit and not expire the data until its TTL is
 * expired.
 */
110

111 112
#undef IGNORE			/* WIN32 winbase.h defines this. */

113 114 115 116 117 118
#define EXISTS(header) \
	(((header)->attributes & RDATASET_ATTR_NONEXISTENT) == 0)
#define NONEXISTENT(header) \
	(((header)->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
#define IGNORE(header) \
	(((header)->attributes & RDATASET_ATTR_IGNORE) != 0)
Michael Graff's avatar
Michael Graff committed
119 120
#define RETAIN(header) \
	(((header)->attributes & RDATASET_ATTR_RETAIN) != 0)
121

Bob Halley's avatar
Bob Halley committed
122
#define DEFAULT_NODE_LOCK_COUNT		7		/* Should be prime. */
Bob Halley's avatar
Bob Halley committed
123 124 125 126

typedef struct {
	isc_mutex_t			lock;
	unsigned int			references;
127
	isc_boolean_t			exiting;
128 129 130 131 132 133 134 135 136 137 138
} rbtdb_nodelock_t;

typedef struct rbtdb_changed {
	dns_rbtnode_t *			node;
	isc_boolean_t			dirty;
	ISC_LINK(struct rbtdb_changed)	link;
} rbtdb_changed_t;

typedef ISC_LIST(rbtdb_changed_t)	rbtdb_changedlist_t;

typedef struct rbtdb_version {
Bob Halley's avatar
Bob Halley committed
139
	/* Not locked */
140
	rbtdb_serial_t			serial;
Bob Halley's avatar
Bob Halley committed
141
	/* Locked by database lock. */
142
	isc_boolean_t			writer;
Bob Halley's avatar
Bob Halley committed
143
	unsigned int			references;
144 145 146 147 148 149
	isc_boolean_t			commit_ok;
	rbtdb_changedlist_t		changed_list;
	ISC_LINK(struct rbtdb_version)	link;
} rbtdb_version_t;

typedef ISC_LIST(rbtdb_version_t)	rbtdb_versionlist_t;
Bob Halley's avatar
Bob Halley committed
150 151

typedef struct {
152
	/* Unlocked. */
Bob Halley's avatar
Bob Halley committed
153 154 155 156
	dns_db_t			common;
	isc_mutex_t			lock;
	isc_rwlock_t			tree_lock;
	unsigned int			node_lock_count;
157
	rbtdb_nodelock_t *	       	node_locks;
158
	dns_rbtnode_t *			origin_node;
159
	/* Locked by lock. */
Bob Halley's avatar
Bob Halley committed
160
	unsigned int			references;
161 162 163 164 165 166 167
	unsigned int			attributes;
	rbtdb_serial_t			current_serial;
	rbtdb_serial_t			least_serial;
	rbtdb_serial_t			next_serial;
	rbtdb_version_t *		current_version;
	rbtdb_version_t *		future_version;
	rbtdb_versionlist_t		open_versions;
168
	isc_boolean_t			overmem;
169
	/* Locked by tree_lock. */
Bob Halley's avatar
Bob Halley committed
170
	dns_rbt_t *			tree;
171
	isc_boolean_t			secure;
Bob Halley's avatar
Bob Halley committed
172 173
} dns_rbtdb_t;

174
#define RBTDB_ATTR_LOADED		0x01
Bob Halley's avatar
Bob Halley committed
175
#define RBTDB_ATTR_LOADING		0x02
176

177 178 179 180 181 182 183 184 185 186 187
/*
 * Search Context
 */
typedef struct {
	dns_rbtdb_t *		rbtdb;
	rbtdb_version_t *	rbtversion;
	rbtdb_serial_t		serial;
	unsigned int		options;
	dns_rbtnodechain_t	chain;
	isc_boolean_t		copy_name;
	isc_boolean_t		need_cleanup;
Bob Halley's avatar
Bob Halley committed
188
	isc_boolean_t		wild;
189 190 191
	dns_rbtnode_t *	       	zonecut;
	rdatasetheader_t *	zonecut_rdataset;
	dns_fixedname_t		zonecut_name;
192
	isc_stdtime_t		now;
193 194
} rbtdb_search_t;

195 196 197 198 199 200 201 202
/*
 * Load Context
 */
typedef struct {
	dns_rbtdb_t *		rbtdb;
	isc_stdtime_t		now;
} rbtdb_load_t;

Bob Halley's avatar
Bob Halley committed
203
static void rdataset_disassociate(dns_rdataset_t *rdataset);
204 205
static isc_result_t rdataset_first(dns_rdataset_t *rdataset);
static isc_result_t rdataset_next(dns_rdataset_t *rdataset);
Bob Halley's avatar
Bob Halley committed
206
static void rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata);
Bob Halley's avatar
Bob Halley committed
207
static void rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target);
Bob Halley's avatar
Bob Halley committed
208
static unsigned int rdataset_count(dns_rdataset_t *rdataset);
209 210

static dns_rdatasetmethods_t rdataset_methods = {
Bob Halley's avatar
Bob Halley committed
211 212 213
	rdataset_disassociate,
	rdataset_first,
	rdataset_next,
Bob Halley's avatar
Bob Halley committed
214
	rdataset_current,
Bob Halley's avatar
Bob Halley committed
215 216
	rdataset_clone,
	rdataset_count
Bob Halley's avatar
Bob Halley committed
217 218 219
};

static void rdatasetiter_destroy(dns_rdatasetiter_t **iteratorp);
220 221
static isc_result_t rdatasetiter_first(dns_rdatasetiter_t *iterator);
static isc_result_t rdatasetiter_next(dns_rdatasetiter_t *iterator);
Bob Halley's avatar
Bob Halley committed
222 223 224 225 226 227 228 229
static void rdatasetiter_current(dns_rdatasetiter_t *iterator,
				 dns_rdataset_t *rdataset);

static dns_rdatasetitermethods_t rdatasetiter_methods = {
	rdatasetiter_destroy,
	rdatasetiter_first,
	rdatasetiter_next,
	rdatasetiter_current
230 231
};

Bob Halley's avatar
Bob Halley committed
232 233 234 235 236
typedef struct rbtdb_rdatasetiter {
	dns_rdatasetiter_t		common;
	rdatasetheader_t *		current;
} rbtdb_rdatasetiter_t;

237
static void		dbiterator_destroy(dns_dbiterator_t **iteratorp);
238 239 240
static isc_result_t	dbiterator_first(dns_dbiterator_t *iterator);
static isc_result_t	dbiterator_last(dns_dbiterator_t *iterator);
static isc_result_t	dbiterator_seek(dns_dbiterator_t *iterator,
241
					dns_name_t *name);
242 243 244
static isc_result_t	dbiterator_prev(dns_dbiterator_t *iterator);
static isc_result_t	dbiterator_next(dns_dbiterator_t *iterator);
static isc_result_t	dbiterator_current(dns_dbiterator_t *iterator,
245 246
					   dns_dbnode_t **nodep,
					   dns_name_t *name);
247 248
static isc_result_t	dbiterator_pause(dns_dbiterator_t *iterator);
static isc_result_t	dbiterator_origin(dns_dbiterator_t *iterator,
249 250 251 252 253
					  dns_name_t *name);

static dns_dbiteratormethods_t dbiterator_methods = {
	dbiterator_destroy,
	dbiterator_first,
254 255 256
	dbiterator_last,
	dbiterator_seek,
	dbiterator_prev,
257 258 259 260 261 262 263 264 265 266
	dbiterator_next,
	dbiterator_current,
	dbiterator_pause,
	dbiterator_origin
};

typedef struct rbtdb_dbiterator {
	dns_dbiterator_t		common;
	isc_boolean_t			paused;
	isc_boolean_t			new_origin;
Bob Halley's avatar
Bob Halley committed
267
	isc_boolean_t			tree_locked;
268
	isc_result_t			result;
269 270 271
	dns_fixedname_t			name;
	dns_fixedname_t			origin;
	dns_rbtnode_t			*node;
Bob Halley's avatar
Bob Halley committed
272
	dns_rbtnodechain_t		chain;
273 274 275
} rbtdb_dbiterator_t;


276 277
#define IS_STUB(rbtdb) (((rbtdb)->common.attributes & DNS_DBATTR_STUB) != 0)

278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
/*
 * Locking
 *
 * If a routine is going to lock more than one lock in this module, then
 * the locking must be done in the following order:
 *
 *	Tree Lock
 *
 *	Node Lock	(Only one from the set may be locked at one time by
 *			 any caller)
 *
 *	Database Lock
 *
 * Failure to follow this hierarchy can result in deadlock.
 */

294 295 296 297 298 299 300 301 302 303 304
/*
 * Deleting Nodes
 *
 * Currently there is no deletion of nodes from the database, except when
 * the database is being destroyed.
 *
 * If node deletion is added in the future, then for zone databases the node
 * for the origin of the zone MUST NOT be deleted.
 */


305 306 307 308
/*
 * DB Routines
 */

Bob Halley's avatar
Bob Halley committed
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
static void
attach(dns_db_t *source, dns_db_t **targetp) {
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)source;

	REQUIRE(VALID_RBTDB(rbtdb));

	LOCK(&rbtdb->lock);
	REQUIRE(rbtdb->references > 0);
	rbtdb->references++;
	UNLOCK(&rbtdb->lock);

	*targetp = source;
}

static void
free_rbtdb(dns_rbtdb_t *rbtdb) {
	unsigned int i;
326
	isc_ondestroy_t ondest;
Bob Halley's avatar
Bob Halley committed
327
	isc_mem_t *mctx;
Bob Halley's avatar
Bob Halley committed
328

329 330
	REQUIRE(EMPTY(rbtdb->open_versions));
	REQUIRE(rbtdb->future_version == NULL);
331

332 333 334 335 336
	if (rbtdb->current_version != NULL)
		isc_mem_put(rbtdb->common.mctx, rbtdb->current_version,
			    sizeof (rbtdb_version_t));
	if (dns_name_dynamic(&rbtdb->common.origin))
		dns_name_free(&rbtdb->common.origin, rbtdb->common.mctx);
Bob Halley's avatar
Bob Halley committed
337 338 339
	if (rbtdb->tree != NULL)
		dns_rbt_destroy(&rbtdb->tree);
	for (i = 0; i < rbtdb->node_lock_count; i++)
340
		DESTROYLOCK(&rbtdb->node_locks[i].lock);
Bob Halley's avatar
Bob Halley committed
341
	isc_mem_put(rbtdb->common.mctx, rbtdb->node_locks,
342
		    rbtdb->node_lock_count * sizeof (rbtdb_nodelock_t));
Bob Halley's avatar
Bob Halley committed
343
	isc_rwlock_destroy(&rbtdb->tree_lock);
344
	DESTROYLOCK(&rbtdb->lock);
Bob Halley's avatar
Bob Halley committed
345 346
	rbtdb->common.magic = 0;
	rbtdb->common.impmagic = 0;
347
	ondest = rbtdb->common.ondest;
Bob Halley's avatar
Bob Halley committed
348 349 350
	mctx = rbtdb->common.mctx;
	isc_mem_put(mctx, rbtdb, sizeof *rbtdb);
	isc_mem_detach(&mctx);
351
	isc_ondestroy_notify(&ondest, rbtdb);
Bob Halley's avatar
Bob Halley committed
352 353
}

354
static inline void
355
maybe_free_rbtdb(dns_rbtdb_t *rbtdb, isc_boolean_t set_exiting) {
Bob Halley's avatar
Bob Halley committed
356 357
	isc_boolean_t want_free = ISC_TRUE;
	unsigned int i;
358

Bob Halley's avatar
Bob Halley committed
359 360 361 362 363 364 365 366
	/* XXX check for open versions here */

	/*
	 * Even though there are no external direct references, there still
	 * may be nodes in use.
	 */
	for (i = 0; i < rbtdb->node_lock_count; i++) {
		LOCK(&rbtdb->node_locks[i].lock);
367 368
		if (set_exiting)
			rbtdb->node_locks[i].exiting = ISC_TRUE;
Bob Halley's avatar
Bob Halley committed
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
		if (rbtdb->node_locks[i].references != 0)
			want_free = ISC_FALSE;
		UNLOCK(&rbtdb->node_locks[i].lock);
	}

	if (want_free)
		free_rbtdb(rbtdb);
}

static void
detach(dns_db_t **dbp) {
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(*dbp);
	isc_boolean_t maybe_free = ISC_FALSE;

	REQUIRE(VALID_RBTDB(rbtdb));

	LOCK(&rbtdb->lock);
	REQUIRE(rbtdb->references > 0);
	rbtdb->references--;
	if (rbtdb->references == 0)
		maybe_free = ISC_TRUE;
	UNLOCK(&rbtdb->lock);

	if (maybe_free)
393
		maybe_free_rbtdb(rbtdb, ISC_TRUE);
Bob Halley's avatar
Bob Halley committed
394

Bob Halley's avatar
Bob Halley committed
395
	*dbp = NULL;
Bob Halley's avatar
Bob Halley committed
396 397 398 399 400
}

static void
currentversion(dns_db_t *db, dns_dbversion_t **versionp) {
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
401
	rbtdb_version_t *version;
Bob Halley's avatar
Bob Halley committed
402 403 404

	REQUIRE(VALID_RBTDB(rbtdb));

405 406 407 408 409 410 411 412 413 414 415
	LOCK(&rbtdb->lock);
	version = rbtdb->current_version;
	if (version->references == 0)
		PREPEND(rbtdb->open_versions, version, link);
	version->references++;
	UNLOCK(&rbtdb->lock);

	*versionp = (dns_dbversion_t *)version;
}

static inline rbtdb_version_t *
416
allocate_version(isc_mem_t *mctx, rbtdb_serial_t serial,
417 418 419 420 421 422 423 424 425 426 427 428 429
		 unsigned int references, isc_boolean_t writer)
{
	rbtdb_version_t *version;

	version = isc_mem_get(mctx, sizeof *version);
	if (version == NULL)
		return (NULL);
	version->serial = serial;
	version->references = references;
	version->writer = writer;
	version->commit_ok = ISC_FALSE;
	ISC_LIST_INIT(version->changed_list);
	ISC_LINK_INIT(version, link);
430

431
	return (version);
Bob Halley's avatar
Bob Halley committed
432 433
}

434
static isc_result_t
Bob Halley's avatar
Bob Halley committed
435 436
newversion(dns_db_t *db, dns_dbversion_t **versionp) {
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
437
	rbtdb_version_t *version;
Bob Halley's avatar
Bob Halley committed
438

Bob Halley's avatar
Bob Halley committed
439
	REQUIRE(VALID_RBTDB(rbtdb));
440 441
	REQUIRE(versionp != NULL && *versionp == NULL);
	REQUIRE(rbtdb->future_version == NULL);
Bob Halley's avatar
Bob Halley committed
442

443 444 445 446 447
	LOCK(&rbtdb->lock);
	RUNTIME_CHECK(rbtdb->next_serial != 0);		/* XXX Error? */
	version = allocate_version(rbtdb->common.mctx, rbtdb->next_serial, 1,
				   ISC_TRUE);
	if (version != NULL) {
448
		version->commit_ok = ISC_TRUE;
449 450 451 452 453 454
		rbtdb->next_serial++;
		rbtdb->future_version = version;
	}
	UNLOCK(&rbtdb->lock);

	if (version == NULL)
455
		return (ISC_R_NOMEMORY);
456

457 458
	*versionp = version;

459
	return (ISC_R_SUCCESS);
460 461
}

462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
static void
attachversion(dns_db_t *db, dns_dbversion_t *source,
	      dns_dbversion_t **targetp)
{
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
	rbtdb_version_t *rbtversion = source;

	REQUIRE(VALID_RBTDB(rbtdb));

	LOCK(&rbtdb->lock);

	INSIST(rbtversion->references > 0);
	rbtversion->references++;
	INSIST(rbtversion->references != 0);

	UNLOCK(&rbtdb->lock);

	*targetp = rbtversion;
}

482 483 484 485 486 487 488 489 490 491 492
static rbtdb_changed_t *
add_changed(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
	    dns_rbtnode_t *node)
{
	rbtdb_changed_t *changed;

	/*
	 * Caller must be holding the node lock.
	 */

	changed = isc_mem_get(rbtdb->common.mctx, sizeof *changed);
Bob Halley's avatar
Bob Halley committed
493 494 495 496 497 498 499 500 501 502 503

	LOCK(&rbtdb->lock);

	REQUIRE(version->writer);

	if (changed != NULL) {
		INSIST(node->references > 0);
		node->references++;
		INSIST(node->references != 0);
		changed->node = node;
		changed->dirty = ISC_FALSE;
504
		ISC_LIST_APPENDUNSAFE(version->changed_list, changed, link);
Bob Halley's avatar
Bob Halley committed
505
	} else
506
		version->commit_ok = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
507 508

	UNLOCK(&rbtdb->lock);
509 510 511 512 513 514 515 516

	return (changed);
}

static inline void
free_rdataset(isc_mem_t *mctx, rdatasetheader_t *rdataset) {
	unsigned int size;

Bob Halley's avatar
Bob Halley committed
517 518 519 520 521
	if ((rdataset->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
		size = sizeof *rdataset;
	else
		size = dns_rdataslab_size((unsigned char *)rdataset,
					  sizeof *rdataset);
522 523 524
	isc_mem_put(mctx, rdataset, size);
}

525
static inline void
526 527
rollback_node(dns_rbtnode_t *node, rbtdb_serial_t serial) {
	rdatasetheader_t *header, *dcurrent;
528
	isc_boolean_t make_dirty = ISC_FALSE;
529 530 531 532 533

	/*
	 * Caller must hold the node lock.
	 */

534 535 536 537 538 539
	/*
	 * We set the IGNORE attribute on rdatasets with serial number
	 * 'serial'.  When the reference count goes to zero, these rdatasets
	 * will be cleaned up; until that time, they will be ignored.
	 */
	for (header = node->data; header != NULL; header = header->next) {
540
		if (header->serial == serial) {
541
			header->attributes |= RDATASET_ATTR_IGNORE;
542 543
			make_dirty = ISC_TRUE;
		}
544 545 546
		for (dcurrent = header->down;
		     dcurrent != NULL;
		     dcurrent = dcurrent->down) {
547
			if (dcurrent->serial == serial) {
548
				dcurrent->attributes |= RDATASET_ATTR_IGNORE;
549 550
				make_dirty = ISC_TRUE;
			}
551 552
		}
	}
553 554
	if (make_dirty)
		node->dirty = 1;
555 556 557 558
}

static inline void
clean_cache_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
559
	rdatasetheader_t *current, *dcurrent, *top_prev, *top_next, *down_next;
560 561 562 563 564 565
	isc_mem_t *mctx = rbtdb->common.mctx;

	/*
	 * Caller must be holding the node lock.
	 */

566
	top_prev = NULL;
567 568 569 570
	for (current = node->data; current != NULL; current = top_next) {
		top_next = current->next;
		dcurrent = current->down;
		if (dcurrent != NULL) {
571
			do {
572 573 574 575 576 577
				down_next = dcurrent->down;
				free_rdataset(mctx, dcurrent);
				dcurrent = down_next;
			} while (dcurrent != NULL);
			current->down = NULL;
		}
578 579 580 581 582
		/*
		 * If current is nonexistent or stale, we can clean it up.
		 */
		if ((current->attributes &
		     (RDATASET_ATTR_NONEXISTENT|RDATASET_ATTR_STALE)) != 0) {
583 584
			if (top_prev != NULL)
				top_prev->next = current->next;
585 586 587
			else
				node->data = current->next;
			free_rdataset(mctx, current);
588 589
		} else
			top_prev = current;
590
	}
591
	node->dirty = 0;
592 593 594 595 596 597
}

static inline void
clean_zone_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
		rbtdb_serial_t least_serial)
{
598 599
	rdatasetheader_t *current, *dcurrent, *down_next, *dparent;
	rdatasetheader_t *top_prev, *top_next;
600 601 602 603 604 605 606 607
	isc_mem_t *mctx = rbtdb->common.mctx;
	isc_boolean_t still_dirty = ISC_FALSE;

	/*
	 * Caller must be holding the node lock.
	 */
	REQUIRE(least_serial != 0);

608
	top_prev = NULL;
609 610
	for (current = node->data; current != NULL; current = top_next) {
		top_next = current->next;
611

612
		/*
613 614 615
		 * First, we clean up any instances of multiple rdatasets
		 * with the same serial number, or that have the IGNORE
		 * attribute.
616 617 618 619
		 */
		dparent = current;
		for (dcurrent = current->down;
		     dcurrent != NULL;
620 621 622
		     dcurrent = down_next) {
			down_next = dcurrent->down;
			INSIST(dcurrent->serial <= dparent->serial);
623 624
			if (dcurrent->serial == dparent->serial ||
			    IGNORE(dcurrent)) {
625 626 627
				if (down_next != NULL)
					down_next->next = dparent;
				dparent->down = down_next;
628 629 630
				free_rdataset(mctx, dcurrent);
			} else
				dparent = dcurrent;
631
		}
632

633
		/*
634
		 * We've now eliminated all IGNORE datasets with the possible
635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664
		 * exception of current, which we now check.
		 */
		if (IGNORE(current)) {
			down_next = current->down;
			if (down_next == NULL) {
				if (top_prev != NULL)
					top_prev->next = current->next;
				else
					node->data = current->next;
				free_rdataset(mctx, current);
				/*
				 * current no longer exists, so we can
				 * just continue with the loop.
				 */
				continue;
			} else {
				/*
				 * Pull up current->down, making it the new
				 * current.
				 */
				if (top_prev != NULL)
					top_prev->next = down_next;
				else
					node->data = down_next;
				down_next->next = top_next;
				free_rdataset(mctx, current);
				current = down_next;
			}
		}

665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692
		/*
		 * We now try to find the first down node less than the
		 * least serial.
		 */
		dparent = current;
		for (dcurrent = current->down;
		     dcurrent != NULL;
		     dcurrent = down_next) {
			down_next = dcurrent->down;
			if (dcurrent->serial < least_serial)
				break;
			dparent = dcurrent;
		}

		/*
		 * If there is a such an rdataset, delete it and any older
		 * versions.
		 */
		if (dcurrent != NULL) {
			do {
				down_next = dcurrent->down;
				INSIST(dcurrent->serial <= least_serial);
				free_rdataset(mctx, dcurrent);
				dcurrent = down_next;
			} while (dcurrent != NULL);
			dparent->down = NULL;
		}

693 694 695
		/*
		 * Note.  The serial number of 'current' might be less than
		 * least_serial too, but we cannot delete it because it is
Bob Halley's avatar
Bob Halley committed
696
		 * the most recent version, unless it is a NONEXISTENT
697
		 * rdataset.
698
		 */
699
		if (current->down != NULL) {
700
			still_dirty = ISC_TRUE;
701 702
			top_prev = current;
		} else {
Bob Halley's avatar
Bob Halley committed
703 704 705 706 707
			/*
			 * If this is a NONEXISTENT rdataset, we can delete it.
			 */
			if ((current->attributes & RDATASET_ATTR_NONEXISTENT)
			    != 0) {
708 709
				if (top_prev != NULL)
					top_prev->next = current->next;
Bob Halley's avatar
Bob Halley committed
710 711 712
				else
					node->data = current->next;
				free_rdataset(mctx, current);
713 714
			} else
				top_prev = current;
Bob Halley's avatar
Bob Halley committed
715
		}
716 717 718 719 720
	}
	if (!still_dirty)
		node->dirty = 0;
}

721 722 723 724 725 726 727 728 729 730
static inline void
new_reference(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
	if (node->references == 0) {
		rbtdb->node_locks[node->locknum].references++;
		INSIST(rbtdb->node_locks[node->locknum].references != 0);
	}
	node->references++;
	INSIST(node->references != 0);
}

731
static void
732 733 734 735 736 737
no_references(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
	      rbtdb_serial_t least_serial)
{
	/*
	 * Caller must be holding the node lock.
	 */
738

739 740
	REQUIRE(node->references == 0);

741 742 743 744 745 746 747 748 749 750 751 752 753 754
	if (node->dirty) {
		if ((rbtdb->common.attributes & DNS_DBATTR_CACHE) != 0)
			clean_cache_node(rbtdb, node);
		else {
			if (least_serial == 0) {
				/*
				 * Caller doesn't know the least serial.
				 * Get it.
				 */
				LOCK(&rbtdb->lock);
				least_serial = rbtdb->least_serial;
				UNLOCK(&rbtdb->lock);
			}
			clean_zone_node(rbtdb, node, least_serial);
755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771
		}
	}

	INSIST(rbtdb->node_locks[node->locknum].references > 0);
	rbtdb->node_locks[node->locknum].references--;
}

static inline void
make_least_version(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
		   rbtdb_changedlist_t *cleanup_list)
{
	/*
	 * Caller must be holding the database lock.
	 */

	rbtdb->least_serial = version->serial;
	*cleanup_list = version->changed_list;
772
	ISC_LIST_INIT(version->changed_list);
773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789
}

static inline void
cleanup_nondirty(rbtdb_version_t *version, rbtdb_changedlist_t *cleanup_list) {
	rbtdb_changed_t *changed, *next_changed;

	/*
	 * If the changed record is dirty, then
	 * an update created multiple versions of
	 * a given rdataset.  We keep this list
	 * until we're the least open version, at
	 * which point it's safe to get rid of any
	 * older versions.
	 *
	 * If the changed record isn't dirty, then
	 * we don't need it anymore since we're
	 * committing and not rolling back.
Bob Halley's avatar
Bob Halley committed
790 791
	 *
	 * The caller must be holding the database lock.
792 793 794 795 796 797 798 799 800 801 802 803
	 */
	for (changed = HEAD(version->changed_list);
	     changed != NULL;
	     changed = next_changed) {
		next_changed = NEXT(changed, link);
		if (!changed->dirty) {
			UNLINK(version->changed_list,
			       changed, link);
			APPEND(*cleanup_list,
			       changed, link);
		}
	}
Bob Halley's avatar
Bob Halley committed
804 805 806
}

static void
Bob Halley's avatar
Bob Halley committed
807
closeversion(dns_db_t *db, dns_dbversion_t **versionp, isc_boolean_t commit) {
Bob Halley's avatar
Bob Halley committed
808
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
809
	rbtdb_version_t *version, *cleanup_version, *least_greater;
810 811 812 813 814
	isc_boolean_t rollback = ISC_FALSE;
	rbtdb_changedlist_t cleanup_list;
	rbtdb_changed_t *changed, *next_changed;
	rbtdb_serial_t serial, least_serial;
	dns_rbtnode_t *rbtnode;
815

816 817
	REQUIRE(VALID_RBTDB(rbtdb));
	version = (rbtdb_version_t *)*versionp;
Bob Halley's avatar
Bob Halley committed
818

819 820
	cleanup_version = NULL;
	ISC_LIST_INIT(cleanup_list);
Bob Halley's avatar
Bob Halley committed
821

822
	LOCK(&rbtdb->lock);
Bob Halley's avatar
Bob Halley committed
823 824
	INSIST(version->references > 0);
	INSIST(!version->writer || !(commit && version->references > 1));
825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866
	version->references--;
	serial = version->serial;
	if (version->references == 0) {
		if (version->writer) {
			if (commit) {
				INSIST(version->commit_ok);
				INSIST(version == rbtdb->future_version);
				if (EMPTY(rbtdb->open_versions)) {
					/*
					 * We're going to become the least open
					 * version.
					 */
					make_least_version(rbtdb, version,
							   &cleanup_list);
				} else {
					/*
					 * Some other open version is the
					 * least version.  We can't cleanup
					 * records that were changed in this
					 * version because the older versions
					 * may still be in use by an open
					 * version.
					 *
					 * We can, however, discard the
					 * changed records for things that
					 * we've added that didn't exist in
					 * prior versions.
					 */
					cleanup_nondirty(version,
							 &cleanup_list);
				}
				/*
				 * If the (soon to be former) current version
				 * isn't being used by anyone, we can clean
				 * it up.
				 */
				if (rbtdb->current_version->references == 0)
					cleanup_version =
						rbtdb->current_version;
				/*
				 * Become the current version.
				 */
867
				version->writer = ISC_FALSE;
868 869 870 871 872 873 874 875 876 877
				rbtdb->current_version = version;
				rbtdb->current_serial = version->serial;
				rbtdb->future_version = NULL;
			} else {
				/*
				 * We're rolling back this transaction.
				 */
				cleanup_list = version->changed_list;
				rollback = ISC_TRUE;
				cleanup_version = version;
878
				rbtdb->future_version = NULL;
879 880 881 882 883 884 885 886
			}
		} else {
			if (version != rbtdb->current_version) {
				/*
				 * There are no external or internal references
				 * to this version and it can be cleaned up.
				 */
				cleanup_version = version;
887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938

				/*
				 * Find the version with the least serial
				 * number greater than ours.
				 */
				least_greater = PREV(version, link);
				if (least_greater == NULL)
					least_greater = rbtdb->current_version;

				/*
				 * Is this the least open version?
				 */
				if (version->serial == rbtdb->least_serial) {
					/*
					 * Yes.  Install the new least open
					 * version.
					 */
					make_least_version(rbtdb,
							   least_greater,
							   &cleanup_list);
				} else {
					/*
					 * Add any unexecuted cleanups to
					 * those of the least greater version.
					 */
					APPENDLIST(least_greater->changed_list,
						   version->changed_list,
						   link);
				}
			}
			UNLINK(rbtdb->open_versions, version, link);
		}
	}
	least_serial = rbtdb->least_serial;
	UNLOCK(&rbtdb->lock);

	if (cleanup_version != NULL)
		isc_mem_put(rbtdb->common.mctx, cleanup_version,
			    sizeof *cleanup_version);

	if (!EMPTY(cleanup_list)) {
		for (changed = HEAD(cleanup_list);
		     changed != NULL;
		     changed = next_changed) {
			next_changed = NEXT(changed, link);
			rbtnode = changed->node;

			LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);

			INSIST(rbtnode->references > 0);
			rbtnode->references--;
			if (rollback)
939
				rollback_node(rbtnode, serial);
940 941 942 943 944 945 946 947 948 949 950 951 952 953

			if (rbtnode->references == 0)
				no_references(rbtdb, rbtnode, least_serial);

			UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);

			isc_mem_put(rbtdb->common.mctx, changed,
				    sizeof *changed);
		}
	}

	*versionp = NULL;
}

954
static isc_result_t
955 956 957 958 959 960 961
findnode(dns_db_t *db, dns_name_t *name, isc_boolean_t create,
	 dns_dbnode_t **nodep)
{
	dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
	dns_rbtnode_t *node = NULL;
	dns_name_t nodename;
	unsigned int locknum;
962
	isc_result_t result;
963 964 965 966 967 968 969
	isc_rwlocktype_t locktype = isc_rwlocktype_read;

	REQUIRE(VALID_RBTDB(rbtdb));

	dns_name_init(&nodename, NULL);
	RWLOCK(&rbtdb->tree_lock, locktype);
	result = dns_rbt_findnode(rbtdb->tree, name, NULL, &node, NULL,
970
				  DNS_RBTFIND_EMPTYDATA, NULL, NULL);
971
	if (result != ISC_R_SUCCESS) {
972 973 974
		RWUNLOCK(&rbtdb->tree_lock, locktype);
		if (!create) {
			if (result == DNS_R_PARTIALMATCH)
975
				result = ISC_R_NOTFOUND;
976 977 978 979 980 981
			return (result);
		}
		/*
		 * It would be nice to try to upgrade the lock instead of
		 * unlocking then relocking.
		 */
982
		locktype = isc_rwlocktype_write;
983
		RWLOCK(&rbtdb->tree_lock, locktype);
984
		node = NULL;
985
		result = dns_rbt_addnode(rbtdb->tree, name, &node);
986
		if (result == ISC_R_SUCCESS) {
987 988 989
			dns_rbt_namefromnode(node, &nodename);
			node->locknum = dns_name_hash(&nodename, ISC_TRUE) %
				rbtdb->node_lock_count;
990
		} else if (result != ISC_R_EXISTS) {
991 992 993 994
			RWUNLOCK(&rbtdb->tree_lock, locktype);
			return (result);
		}
	}
995 996 997 998
	locknum = node->locknum;
	LOCK(&rbtdb->node_locks[locknum].lock);
	new_reference(rbtdb, node);
	UNLOCK(&rbtdb->node_locks[locknum].lock);
999 1000 1001 1002
	RWUNLOCK(&rbtdb->tree_lock, locktype);

	*nodep = (dns_dbnode_t *)node;

1003
	return (ISC_R_SUCCESS);
1004 1005
}

1006
static isc_result_t
1007 1008 1009 1010
zone_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name, void *arg) {
	rbtdb_search_t *search = arg;
	rdatasetheader_t *header, *header_next;
	rdatasetheader_t *found;
1011
	isc_result_t result;
1012
	dns_rbtnode_t *onode;
1013

Bob Halley's avatar
Bob Halley committed
1014 1015 1016 1017 1018
	/*
	 * We only want to remember the topmost zone cut, since it's the one
	 * that counts, so we'll just continue if we've already found a
	 * zonecut.
	 */
1019 1020 1021 1022 1023
	if (search->zonecut != NULL)
		return (DNS_R_CONTINUE);

	found = NULL;
	result = DNS_R_CONTINUE;
1024
	onode = search->rbtdb->origin_node;
1025 1026

	LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1027

1028 1029 1030 1031 1032 1033 1034 1035
	/*
	 * Look for an NS or DNAME rdataset active in our version.
	 */
	for (header = node->data; header != NULL; header = header_next) {
		header_next = header->next;
		if (header->type == dns_rdatatype_ns ||
		    header->type == dns_rdatatype_dname) {
			do {
1036 1037
				if (header->serial <= search->serial &&
				    !IGNORE(header)) {
1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
					/*
					 * Is this a "this rdataset doesn't
					 * exist" record?
					 */
					if ((header->attributes &
					     RDATASET_ATTR_NONEXISTENT) != 0)
						header = NULL;
					break;
				} else
					header = header->down;
			} while (header != NULL);
			if (header != NULL) {
1050 1051 1052 1053 1054 1055 1056
				if (header->type == dns_rdatatype_dname) {
					/*
					 * We don't need to keep looking for
					 * NS records, because the DNAME has
					 * precedence.
					 */
					found = header;
1057
					break;
1058 1059
				} else if (node != onode ||
					   IS_STUB(search->rbtdb)) {
1060 1061 1062 1063 1064 1065 1066 1067 1068 1069
					/*
					 * We've found an NS rdataset that
					 * isn't at the origin node.  We check
					 * that they're not at the origin node,
					 * because otherwise we'd erroneously
					 * treat the zone top as if it were
					 * a delegation.
					 */
					found = header;
				}
1070
			}
1071 1072 1073 1074
		}
	}

	if (found != NULL) {
Bob Halley's avatar
Bob Halley committed
1075 1076 1077 1078
		/*
		 * We increment the reference count on node to ensure that
		 * search->zonecut_rdataset will still be valid later.
		 */
1079 1080 1081 1082
		new_reference(search->rbtdb, node);
		search->zonecut = node;
		search->zonecut_rdataset = found;
		search->need_cleanup = ISC_TRUE;
Bob Halley's avatar
Bob Halley committed
1083 1084 1085 1086 1087 1088
		/*
		 * Since we've found a zonecut, anything beneath it is
		 * glue and is not subject to wildcard matching, so we
		 * may clear search->wild.
		 */
		search->wild = ISC_FALSE;
1089
		if ((search->options & DNS_DBFIND_GLUEOK) == 0) {
1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
			/*
			 * If the caller does not want to find glue, then
			 * this is the best answer and the search should
			 * stop now.
			 */
			result = DNS_R_PARTIALMATCH;
		} else {
			dns_name_t *zcname;

			/*
			 * The search will continue beneath the zone cut.
			 * This may or may not be the best match.  In case it
			 * is, we need to remember the node name.
			 */
			zcname = dns_fixedname_name(&search->zonecut_name);
			RUNTIME_CHECK(dns_name_concatenate(name, NULL, zcname,
							   NULL) ==
1107
				      ISC_R_SUCCESS);
1108 1109
			search->copy_name = ISC_TRUE;
		}
Bob Halley's avatar
Bob Halley committed
1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121
	} else {
		/*
		 * There is no zonecut at this node which is active in this
		 * version.
		 *
		 * If this is a "wild" node and the caller hasn't disabled
		 * wildcard matching, remember that we've seen a wild node
		 * in case we need to go searching for wildcard matches
		 * later on.
		 */
		if (node->wild && (search->options & DNS_DBFIND_NOWILD) == 0)
			search->wild = ISC_TRUE;
1122 1123 1124 1125 1126 1127 1128 1129 1130
	}

	UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));

	return (result);
}

static inline void
bind_rdataset(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
1131 1132
	      rdatasetheader_t *header, isc_stdtime_t now,
	      dns_rdataset_t *rdataset)
1133 1134 1135 1136 1137 1138 1139
{
	unsigned char *raw;

	/*
	 * Caller must be holding the node lock.
	 */