2 * Copyright (C) 2004-2006 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2003 Internet Software Consortium.
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
18 /* $Id: rbtdb.c,v 1.168.2.11.2.26 2006/03/02 23:18:20 marka Exp $ */
21 * Principal Author: Bob Halley
26 #include <isc/event.h>
28 #include <isc/print.h>
29 #include <isc/mutex.h>
30 #include <isc/random.h>
31 #include <isc/refcount.h>
32 #include <isc/rwlock.h>
33 #include <isc/string.h>
38 #include <dns/dbiterator.h>
39 #include <dns/events.h>
40 #include <dns/fixedname.h>
42 #include <dns/masterdump.h>
44 #include <dns/rdata.h>
45 #include <dns/rdataset.h>
46 #include <dns/rdatasetiter.h>
47 #include <dns/rdataslab.h>
48 #include <dns/result.h>
49 #include <dns/zonekey.h>
51 #ifdef DNS_RBTDB_VERSION64
57 #ifdef DNS_RBTDB_VERSION64
58 #define RBTDB_MAGIC ISC_MAGIC('R', 'B', 'D', '8')
60 #define RBTDB_MAGIC ISC_MAGIC('R', 'B', 'D', '4')
64 * Note that "impmagic" is not the first four bytes of the struct, so
65 * ISC_MAGIC_VALID cannot be used.
67 #define VALID_RBTDB(rbtdb) ((rbtdb) != NULL && \
68 (rbtdb)->common.impmagic == RBTDB_MAGIC)
70 #ifdef DNS_RBTDB_VERSION64
71 typedef isc_uint64_t rbtdb_serial_t;
73 * Make casting easier in symbolic debuggers by using different names
74 * for the 64 bit version.
76 #define dns_rbtdb_t dns_rbtdb64_t
77 #define rdatasetheader_t rdatasetheader64_t
78 #define rbtdb_version_t rbtdb_version64_t
80 typedef isc_uint32_t rbtdb_serial_t;
83 typedef isc_uint32_t rbtdb_rdatatype_t;
85 #define RBTDB_RDATATYPE_BASE(type) ((dns_rdatatype_t)((type) & 0xFFFF))
86 #define RBTDB_RDATATYPE_EXT(type) ((dns_rdatatype_t)((type) >> 16))
87 #define RBTDB_RDATATYPE_VALUE(b, e) (((e) << 16) | (b))
89 #define RBTDB_RDATATYPE_SIGNSEC \
90 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_nsec)
91 #define RBTDB_RDATATYPE_SIGNS \
92 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_ns)
93 #define RBTDB_RDATATYPE_SIGCNAME \
94 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_cname)
95 #define RBTDB_RDATATYPE_SIGDNAME \
96 RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, dns_rdatatype_dname)
97 #define RBTDB_RDATATYPE_NCACHEANY \
98 RBTDB_RDATATYPE_VALUE(0, dns_rdatatype_any)
101 * Allow clients with a virtual time of upto 5 minutes in the past to see
102 * records that would have otherwise have expired.
104 #define RBTDB_VIRTUAL 300
112 typedef struct rdatasetheader {
114 * Locked by the owning node's lock.
116 rbtdb_serial_t serial;
118 rbtdb_rdatatype_t type;
119 isc_uint16_t attributes;
121 struct noqname *noqname;
123 * We don't use the LIST macros, because the LIST structure has
124 * both head and tail pointers, and is doubly linked.
127 struct rdatasetheader *next;
129 * If this is the top header for an rdataset, 'next' points
130 * to the top header for the next rdataset (i.e., the next type).
131 * Otherwise, it points up to the header whose down pointer points
135 struct rdatasetheader *down;
137 * Points to the header for the next older version of
143 * Monotonously increased every time this rdataset is bound so that
144 * it is used as the base of the starting point in DNS responses
145 * when the "cyclic" rrset-order is required. Since the ordering
146 * should not be so crucial, no lock is set for the counter for
147 * performance reasons.
151 #define RDATASET_ATTR_NONEXISTENT 0x0001
152 #define RDATASET_ATTR_STALE 0x0002
153 #define RDATASET_ATTR_IGNORE 0x0004
154 #define RDATASET_ATTR_RETAIN 0x0008
155 #define RDATASET_ATTR_NXDOMAIN 0x0010
159 * When the cache will pre-expire data (due to memory low or other
160 * situations) before the rdataset's TTL has expired, it MUST
161 * respect the RETAIN bit and not expire the data until its TTL is
165 #undef IGNORE /* WIN32 winbase.h defines this. */
167 #define EXISTS(header) \
168 (((header)->attributes & RDATASET_ATTR_NONEXISTENT) == 0)
169 #define NONEXISTENT(header) \
170 (((header)->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
171 #define IGNORE(header) \
172 (((header)->attributes & RDATASET_ATTR_IGNORE) != 0)
173 #define RETAIN(header) \
174 (((header)->attributes & RDATASET_ATTR_RETAIN) != 0)
175 #define NXDOMAIN(header) \
176 (((header)->attributes & RDATASET_ATTR_NXDOMAIN) != 0)
178 #define DEFAULT_NODE_LOCK_COUNT 7 /* Should be prime. */
182 /* Locked by lock. */
183 unsigned int references;
184 isc_boolean_t exiting;
187 typedef struct rbtdb_changed {
188 dns_rbtnode_t * node;
190 ISC_LINK(struct rbtdb_changed) link;
193 typedef ISC_LIST(rbtdb_changed_t) rbtdb_changedlist_t;
195 typedef struct rbtdb_version {
197 rbtdb_serial_t serial;
198 /* Locked by database lock. */
199 isc_boolean_t writer;
200 unsigned int references;
201 isc_boolean_t commit_ok;
202 rbtdb_changedlist_t changed_list;
203 ISC_LINK(struct rbtdb_version) link;
206 typedef ISC_LIST(rbtdb_version_t) rbtdb_versionlist_t;
212 isc_rwlock_t tree_lock;
213 unsigned int node_lock_count;
214 rbtdb_nodelock_t * node_locks;
215 dns_rbtnode_t * origin_node;
216 /* Locked by lock. */
218 isc_refcount_t references;
219 unsigned int attributes;
220 rbtdb_serial_t current_serial;
221 rbtdb_serial_t least_serial;
222 rbtdb_serial_t next_serial;
223 rbtdb_version_t * current_version;
224 rbtdb_version_t * future_version;
225 rbtdb_versionlist_t open_versions;
226 isc_boolean_t overmem;
228 /* Locked by tree_lock. */
230 isc_boolean_t secure;
233 #define RBTDB_ATTR_LOADED 0x01
234 #define RBTDB_ATTR_LOADING 0x02
241 rbtdb_version_t * rbtversion;
242 rbtdb_serial_t serial;
243 unsigned int options;
244 dns_rbtnodechain_t chain;
245 isc_boolean_t copy_name;
246 isc_boolean_t need_cleanup;
248 dns_rbtnode_t * zonecut;
249 rdatasetheader_t * zonecut_rdataset;
250 rdatasetheader_t * zonecut_sigrdataset;
251 dns_fixedname_t zonecut_name;
263 static void rdataset_disassociate(dns_rdataset_t *rdataset);
264 static isc_result_t rdataset_first(dns_rdataset_t *rdataset);
265 static isc_result_t rdataset_next(dns_rdataset_t *rdataset);
266 static void rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata);
267 static void rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target);
268 static unsigned int rdataset_count(dns_rdataset_t *rdataset);
269 static isc_result_t rdataset_getnoqname(dns_rdataset_t *rdataset,
271 dns_rdataset_t *nsec,
272 dns_rdataset_t *nsecsig);
274 static dns_rdatasetmethods_t rdataset_methods = {
275 rdataset_disassociate,
285 static void rdatasetiter_destroy(dns_rdatasetiter_t **iteratorp);
286 static isc_result_t rdatasetiter_first(dns_rdatasetiter_t *iterator);
287 static isc_result_t rdatasetiter_next(dns_rdatasetiter_t *iterator);
288 static void rdatasetiter_current(dns_rdatasetiter_t *iterator,
289 dns_rdataset_t *rdataset);
291 static dns_rdatasetitermethods_t rdatasetiter_methods = {
292 rdatasetiter_destroy,
298 typedef struct rbtdb_rdatasetiter {
299 dns_rdatasetiter_t common;
300 rdatasetheader_t * current;
301 } rbtdb_rdatasetiter_t;
303 static void dbiterator_destroy(dns_dbiterator_t **iteratorp);
304 static isc_result_t dbiterator_first(dns_dbiterator_t *iterator);
305 static isc_result_t dbiterator_last(dns_dbiterator_t *iterator);
306 static isc_result_t dbiterator_seek(dns_dbiterator_t *iterator,
308 static isc_result_t dbiterator_prev(dns_dbiterator_t *iterator);
309 static isc_result_t dbiterator_next(dns_dbiterator_t *iterator);
310 static isc_result_t dbiterator_current(dns_dbiterator_t *iterator,
311 dns_dbnode_t **nodep,
313 static isc_result_t dbiterator_pause(dns_dbiterator_t *iterator);
314 static isc_result_t dbiterator_origin(dns_dbiterator_t *iterator,
317 static dns_dbiteratormethods_t dbiterator_methods = {
329 #define DELETION_BATCH_MAX 64
332 * If 'paused' is ISC_TRUE, then the tree lock is not being held.
334 typedef struct rbtdb_dbiterator {
335 dns_dbiterator_t common;
336 isc_boolean_t paused;
337 isc_boolean_t new_origin;
338 isc_rwlocktype_t tree_locked;
340 dns_fixedname_t name;
341 dns_fixedname_t origin;
342 dns_rbtnodechain_t chain;
344 dns_rbtnode_t *deletions[DELETION_BATCH_MAX];
346 } rbtdb_dbiterator_t;
349 #define IS_STUB(rbtdb) (((rbtdb)->common.attributes & DNS_DBATTR_STUB) != 0)
350 #define IS_CACHE(rbtdb) (((rbtdb)->common.attributes & DNS_DBATTR_CACHE) != 0)
352 static void free_rbtdb(dns_rbtdb_t *rbtdb, isc_boolean_t log,
358 * If a routine is going to lock more than one lock in this module, then
359 * the locking must be done in the following order:
363 * Node Lock (Only one from the set may be locked at one time by
368 * Failure to follow this hierarchy can result in deadlock.
374 * Currently there is no deletion of nodes from the database, except when
375 * the database is being destroyed.
377 * If node deletion is added in the future, then for zone databases the node
378 * for the origin of the zone MUST NOT be deleted.
387 attach(dns_db_t *source, dns_db_t **targetp) {
388 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)source;
390 REQUIRE(VALID_RBTDB(rbtdb));
392 isc_refcount_increment(&rbtdb->references, NULL);
398 free_rbtdb_callback(isc_task_t *task, isc_event_t *event) {
399 dns_rbtdb_t *rbtdb = event->ev_arg;
403 free_rbtdb(rbtdb, ISC_TRUE, event);
407 free_rbtdb(dns_rbtdb_t *rbtdb, isc_boolean_t log, isc_event_t *event) {
409 isc_ondestroy_t ondest;
411 char buf[DNS_NAME_FORMATSIZE];
413 REQUIRE(EMPTY(rbtdb->open_versions));
414 REQUIRE(rbtdb->future_version == NULL);
416 if (rbtdb->current_version != NULL)
417 isc_mem_put(rbtdb->common.mctx, rbtdb->current_version,
418 sizeof(rbtdb_version_t));
420 if (rbtdb->tree != NULL) {
421 result = dns_rbt_destroy2(&rbtdb->tree,
422 (rbtdb->task != NULL) ? 1000 : 0);
423 if (result == ISC_R_QUOTA) {
424 INSIST(rbtdb->task != NULL);
426 event = isc_event_allocate(rbtdb->common.mctx,
428 DNS_EVENT_FREESTORAGE,
431 sizeof(isc_event_t));
434 isc_task_send(rbtdb->task, &event);
437 INSIST(result == ISC_R_SUCCESS && rbtdb->tree == NULL);
440 isc_event_free(&event);
442 if (dns_name_dynamic(&rbtdb->common.origin))
443 dns_name_format(&rbtdb->common.origin, buf,
446 strcpy(buf, "<UNKNOWN>");
447 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
448 DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
449 "done free_rbtdb(%s)", buf);
451 if (dns_name_dynamic(&rbtdb->common.origin))
452 dns_name_free(&rbtdb->common.origin, rbtdb->common.mctx);
453 for (i = 0; i < rbtdb->node_lock_count; i++)
454 DESTROYLOCK(&rbtdb->node_locks[i].lock);
455 isc_mem_put(rbtdb->common.mctx, rbtdb->node_locks,
456 rbtdb->node_lock_count * sizeof(rbtdb_nodelock_t));
457 isc_rwlock_destroy(&rbtdb->tree_lock);
458 isc_refcount_destroy(&rbtdb->references);
459 if (rbtdb->task != NULL)
460 isc_task_detach(&rbtdb->task);
461 DESTROYLOCK(&rbtdb->lock);
462 rbtdb->common.magic = 0;
463 rbtdb->common.impmagic = 0;
464 ondest = rbtdb->common.ondest;
465 isc_mem_putanddetach(&rbtdb->common.mctx, rbtdb, sizeof(*rbtdb));
466 isc_ondestroy_notify(&ondest, rbtdb);
470 maybe_free_rbtdb(dns_rbtdb_t *rbtdb) {
471 isc_boolean_t want_free = ISC_FALSE;
473 unsigned int inactive = 0;
475 /* XXX check for open versions here */
478 * Even though there are no external direct references, there still
479 * may be nodes in use.
481 for (i = 0; i < rbtdb->node_lock_count; i++) {
482 LOCK(&rbtdb->node_locks[i].lock);
483 rbtdb->node_locks[i].exiting = ISC_TRUE;
484 if (rbtdb->node_locks[i].references == 0)
486 UNLOCK(&rbtdb->node_locks[i].lock);
491 rbtdb->active -= inactive;
492 if (rbtdb->active == 0)
493 want_free = ISC_TRUE;
494 UNLOCK(&rbtdb->lock);
496 char buf[DNS_NAME_FORMATSIZE];
497 if (dns_name_dynamic(&rbtdb->common.origin))
498 dns_name_format(&rbtdb->common.origin, buf,
501 strcpy(buf, "<UNKNOWN>");
502 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
503 DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
504 "calling free_rbtdb(%s)", buf);
505 free_rbtdb(rbtdb, ISC_TRUE, NULL);
511 detach(dns_db_t **dbp) {
512 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(*dbp);
515 REQUIRE(VALID_RBTDB(rbtdb));
517 isc_refcount_decrement(&rbtdb->references, &refs);
520 maybe_free_rbtdb(rbtdb);
526 currentversion(dns_db_t *db, dns_dbversion_t **versionp) {
527 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
528 rbtdb_version_t *version;
530 REQUIRE(VALID_RBTDB(rbtdb));
533 version = rbtdb->current_version;
534 if (version->references == 0)
535 PREPEND(rbtdb->open_versions, version, link);
536 version->references++;
537 UNLOCK(&rbtdb->lock);
539 *versionp = (dns_dbversion_t *)version;
542 static inline rbtdb_version_t *
543 allocate_version(isc_mem_t *mctx, rbtdb_serial_t serial,
544 unsigned int references, isc_boolean_t writer)
546 rbtdb_version_t *version;
548 version = isc_mem_get(mctx, sizeof(*version));
551 version->serial = serial;
552 version->references = references;
553 version->writer = writer;
554 version->commit_ok = ISC_FALSE;
555 ISC_LIST_INIT(version->changed_list);
556 ISC_LINK_INIT(version, link);
562 newversion(dns_db_t *db, dns_dbversion_t **versionp) {
563 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
564 rbtdb_version_t *version;
566 REQUIRE(VALID_RBTDB(rbtdb));
567 REQUIRE(versionp != NULL && *versionp == NULL);
568 REQUIRE(rbtdb->future_version == NULL);
571 RUNTIME_CHECK(rbtdb->next_serial != 0); /* XXX Error? */
572 version = allocate_version(rbtdb->common.mctx, rbtdb->next_serial, 1,
574 if (version != NULL) {
575 version->commit_ok = ISC_TRUE;
576 rbtdb->next_serial++;
577 rbtdb->future_version = version;
579 UNLOCK(&rbtdb->lock);
582 return (ISC_R_NOMEMORY);
586 return (ISC_R_SUCCESS);
590 attachversion(dns_db_t *db, dns_dbversion_t *source,
591 dns_dbversion_t **targetp)
593 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
594 rbtdb_version_t *rbtversion = source;
596 REQUIRE(VALID_RBTDB(rbtdb));
600 INSIST(rbtversion->references > 0);
601 rbtversion->references++;
602 INSIST(rbtversion->references != 0);
604 UNLOCK(&rbtdb->lock);
606 *targetp = rbtversion;
609 static rbtdb_changed_t *
610 add_changed(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
613 rbtdb_changed_t *changed;
616 * Caller must be holding the node lock.
619 changed = isc_mem_get(rbtdb->common.mctx, sizeof(*changed));
623 REQUIRE(version->writer);
625 if (changed != NULL) {
626 INSIST(node->references > 0);
628 INSIST(node->references != 0);
629 changed->node = node;
630 changed->dirty = ISC_FALSE;
631 ISC_LIST_INITANDAPPEND(version->changed_list, changed, link);
633 version->commit_ok = ISC_FALSE;
635 UNLOCK(&rbtdb->lock);
641 free_noqname(isc_mem_t *mctx, struct noqname **noqname) {
643 if (dns_name_dynamic(&(*noqname)->name))
644 dns_name_free(&(*noqname)->name, mctx);
645 if ((*noqname)->nsec != NULL)
646 isc_mem_put(mctx, (*noqname)->nsec,
647 dns_rdataslab_size((*noqname)->nsec, 0));
648 if ((*noqname)->nsec != NULL)
649 isc_mem_put(mctx, (*noqname)->nsecsig,
650 dns_rdataslab_size((*noqname)->nsecsig, 0));
651 isc_mem_put(mctx, *noqname, sizeof(**noqname));
656 free_rdataset(isc_mem_t *mctx, rdatasetheader_t *rdataset) {
659 if (rdataset->noqname != NULL)
660 free_noqname(mctx, &rdataset->noqname);
662 if ((rdataset->attributes & RDATASET_ATTR_NONEXISTENT) != 0)
663 size = sizeof(*rdataset);
665 size = dns_rdataslab_size((unsigned char *)rdataset,
667 isc_mem_put(mctx, rdataset, size);
671 rollback_node(dns_rbtnode_t *node, rbtdb_serial_t serial) {
672 rdatasetheader_t *header, *dcurrent;
673 isc_boolean_t make_dirty = ISC_FALSE;
676 * Caller must hold the node lock.
680 * We set the IGNORE attribute on rdatasets with serial number
681 * 'serial'. When the reference count goes to zero, these rdatasets
682 * will be cleaned up; until that time, they will be ignored.
684 for (header = node->data; header != NULL; header = header->next) {
685 if (header->serial == serial) {
686 header->attributes |= RDATASET_ATTR_IGNORE;
687 make_dirty = ISC_TRUE;
689 for (dcurrent = header->down;
691 dcurrent = dcurrent->down) {
692 if (dcurrent->serial == serial) {
693 dcurrent->attributes |= RDATASET_ATTR_IGNORE;
694 make_dirty = ISC_TRUE;
703 clean_cache_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
704 rdatasetheader_t *current, *dcurrent, *top_prev, *top_next, *down_next;
705 isc_mem_t *mctx = rbtdb->common.mctx;
708 * Caller must be holding the node lock.
712 for (current = node->data; current != NULL; current = top_next) {
713 top_next = current->next;
714 dcurrent = current->down;
715 if (dcurrent != NULL) {
717 down_next = dcurrent->down;
718 free_rdataset(mctx, dcurrent);
719 dcurrent = down_next;
720 } while (dcurrent != NULL);
721 current->down = NULL;
724 * If current is nonexistent or stale, we can clean it up.
726 if ((current->attributes &
727 (RDATASET_ATTR_NONEXISTENT|RDATASET_ATTR_STALE)) != 0) {
728 if (top_prev != NULL)
729 top_prev->next = current->next;
731 node->data = current->next;
732 free_rdataset(mctx, current);
740 clean_zone_node(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
741 rbtdb_serial_t least_serial)
743 rdatasetheader_t *current, *dcurrent, *down_next, *dparent;
744 rdatasetheader_t *top_prev, *top_next;
745 isc_mem_t *mctx = rbtdb->common.mctx;
746 isc_boolean_t still_dirty = ISC_FALSE;
749 * Caller must be holding the node lock.
751 REQUIRE(least_serial != 0);
754 for (current = node->data; current != NULL; current = top_next) {
755 top_next = current->next;
758 * First, we clean up any instances of multiple rdatasets
759 * with the same serial number, or that have the IGNORE
763 for (dcurrent = current->down;
765 dcurrent = down_next) {
766 down_next = dcurrent->down;
767 INSIST(dcurrent->serial <= dparent->serial);
768 if (dcurrent->serial == dparent->serial ||
770 if (down_next != NULL)
771 down_next->next = dparent;
772 dparent->down = down_next;
773 free_rdataset(mctx, dcurrent);
779 * We've now eliminated all IGNORE datasets with the possible
780 * exception of current, which we now check.
782 if (IGNORE(current)) {
783 down_next = current->down;
784 if (down_next == NULL) {
785 if (top_prev != NULL)
786 top_prev->next = current->next;
788 node->data = current->next;
789 free_rdataset(mctx, current);
791 * current no longer exists, so we can
792 * just continue with the loop.
797 * Pull up current->down, making it the new
800 if (top_prev != NULL)
801 top_prev->next = down_next;
803 node->data = down_next;
804 down_next->next = top_next;
805 free_rdataset(mctx, current);
811 * We now try to find the first down node less than the
815 for (dcurrent = current->down;
817 dcurrent = down_next) {
818 down_next = dcurrent->down;
819 if (dcurrent->serial < least_serial)
825 * If there is a such an rdataset, delete it and any older
828 if (dcurrent != NULL) {
830 down_next = dcurrent->down;
831 INSIST(dcurrent->serial <= least_serial);
832 free_rdataset(mctx, dcurrent);
833 dcurrent = down_next;
834 } while (dcurrent != NULL);
835 dparent->down = NULL;
839 * Note. The serial number of 'current' might be less than
840 * least_serial too, but we cannot delete it because it is
841 * the most recent version, unless it is a NONEXISTENT
844 if (current->down != NULL) {
845 still_dirty = ISC_TRUE;
849 * If this is a NONEXISTENT rdataset, we can delete it.
851 if (NONEXISTENT(current)) {
852 if (top_prev != NULL)
853 top_prev->next = current->next;
855 node->data = current->next;
856 free_rdataset(mctx, current);
866 new_reference(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node) {
867 if (node->references == 0) {
868 rbtdb->node_locks[node->locknum].references++;
869 INSIST(rbtdb->node_locks[node->locknum].references != 0);
872 INSIST(node->references != 0);
876 no_references(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
877 rbtdb_serial_t least_serial, isc_rwlocktype_t lock)
880 isc_boolean_t write_locked;
881 unsigned int locknum;
884 * Caller must be holding the node lock.
887 REQUIRE(node->references == 0);
891 clean_cache_node(rbtdb, node);
893 if (least_serial == 0) {
895 * Caller doesn't know the least serial.
899 least_serial = rbtdb->least_serial;
900 UNLOCK(&rbtdb->lock);
902 clean_zone_node(rbtdb, node, least_serial);
906 locknum = node->locknum;
908 INSIST(rbtdb->node_locks[locknum].references > 0);
909 rbtdb->node_locks[locknum].references--;
912 * XXXDCL should this only be done for cache zones?
914 if (node->data != NULL || node->down != NULL)
918 * XXXDCL need to add a deferred delete method for ISC_R_LOCKBUSY.
920 if (lock != isc_rwlocktype_write) {
922 * Locking hierarchy notwithstanding, we don't need to free
923 * the node lock before acquiring the tree write lock because
924 * we only do a trylock.
926 if (lock == isc_rwlocktype_read)
927 result = isc_rwlock_tryupgrade(&rbtdb->tree_lock);
929 result = isc_rwlock_trylock(&rbtdb->tree_lock,
930 isc_rwlocktype_write);
931 RUNTIME_CHECK(result == ISC_R_SUCCESS ||
932 result == ISC_R_LOCKBUSY);
934 write_locked = ISC_TF(result == ISC_R_SUCCESS);
936 write_locked = ISC_TRUE;
939 if (isc_log_wouldlog(dns_lctx, ISC_LOG_DEBUG(1))) {
940 char printname[DNS_NAME_FORMATSIZE];
942 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
943 DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
944 "no_references: delete from rbt: %p %s",
946 dns_rbt_formatnodename(node, printname,
950 result = dns_rbt_deletenode(rbtdb->tree, node, ISC_FALSE);
951 if (result != ISC_R_SUCCESS)
952 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
953 DNS_LOGMODULE_CACHE, ISC_LOG_WARNING,
954 "no_references: dns_rbt_deletenode: %s",
955 isc_result_totext(result));
959 * Relock a read lock, or unlock the write lock if no lock was held.
961 if (lock == isc_rwlocktype_none)
963 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
965 if (lock == isc_rwlocktype_read)
967 isc_rwlock_downgrade(&rbtdb->tree_lock);
971 make_least_version(dns_rbtdb_t *rbtdb, rbtdb_version_t *version,
972 rbtdb_changedlist_t *cleanup_list)
975 * Caller must be holding the database lock.
978 rbtdb->least_serial = version->serial;
979 *cleanup_list = version->changed_list;
980 ISC_LIST_INIT(version->changed_list);
984 cleanup_nondirty(rbtdb_version_t *version, rbtdb_changedlist_t *cleanup_list) {
985 rbtdb_changed_t *changed, *next_changed;
988 * If the changed record is dirty, then
989 * an update created multiple versions of
990 * a given rdataset. We keep this list
991 * until we're the least open version, at
992 * which point it's safe to get rid of any
995 * If the changed record isn't dirty, then
996 * we don't need it anymore since we're
997 * committing and not rolling back.
999 * The caller must be holding the database lock.
1001 for (changed = HEAD(version->changed_list);
1003 changed = next_changed) {
1004 next_changed = NEXT(changed, link);
1005 if (!changed->dirty) {
1006 UNLINK(version->changed_list,
1008 APPEND(*cleanup_list,
1014 static isc_boolean_t
1015 iszonesecure(dns_db_t *db, dns_dbnode_t *origin) {
1016 dns_rdataset_t keyset;
1017 dns_rdataset_t nsecset, signsecset;
1018 isc_boolean_t haszonekey = ISC_FALSE;
1019 isc_boolean_t hasnsec = ISC_FALSE;
1020 isc_result_t result;
1022 dns_rdataset_init(&keyset);
1023 result = dns_db_findrdataset(db, origin, NULL, dns_rdatatype_dnskey, 0,
1025 if (result == ISC_R_SUCCESS) {
1026 dns_rdata_t keyrdata = DNS_RDATA_INIT;
1027 result = dns_rdataset_first(&keyset);
1028 while (result == ISC_R_SUCCESS) {
1029 dns_rdataset_current(&keyset, &keyrdata);
1030 if (dns_zonekey_iszonekey(&keyrdata)) {
1031 haszonekey = ISC_TRUE;
1034 result = dns_rdataset_next(&keyset);
1036 dns_rdataset_disassociate(&keyset);
1041 dns_rdataset_init(&nsecset);
1042 dns_rdataset_init(&signsecset);
1043 result = dns_db_findrdataset(db, origin, NULL, dns_rdatatype_nsec, 0,
1044 0, &nsecset, &signsecset);
1045 if (result == ISC_R_SUCCESS) {
1046 if (dns_rdataset_isassociated(&signsecset)) {
1048 dns_rdataset_disassociate(&signsecset);
1050 dns_rdataset_disassociate(&nsecset);
1056 closeversion(dns_db_t *db, dns_dbversion_t **versionp, isc_boolean_t commit) {
1057 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
1058 rbtdb_version_t *version, *cleanup_version, *least_greater;
1059 isc_boolean_t rollback = ISC_FALSE;
1060 rbtdb_changedlist_t cleanup_list;
1061 rbtdb_changed_t *changed, *next_changed;
1062 rbtdb_serial_t serial, least_serial;
1063 dns_rbtnode_t *rbtnode;
1066 REQUIRE(VALID_RBTDB(rbtdb));
1067 version = (rbtdb_version_t *)*versionp;
1069 cleanup_version = NULL;
1070 ISC_LIST_INIT(cleanup_list);
1073 INSIST(version->references > 0);
1074 INSIST(!version->writer || !(commit && version->references > 1));
1075 version->references--;
1076 serial = version->serial;
1077 if (version->references == 0) {
1078 if (version->writer) {
1080 INSIST(version->commit_ok);
1081 INSIST(version == rbtdb->future_version);
1082 if (EMPTY(rbtdb->open_versions)) {
1084 * We're going to become the least open
1087 make_least_version(rbtdb, version,
1091 * Some other open version is the
1092 * least version. We can't cleanup
1093 * records that were changed in this
1094 * version because the older versions
1095 * may still be in use by an open
1098 * We can, however, discard the
1099 * changed records for things that
1100 * we've added that didn't exist in
1103 cleanup_nondirty(version,
1107 * If the (soon to be former) current version
1108 * isn't being used by anyone, we can clean
1111 if (rbtdb->current_version->references == 0) {
1113 rbtdb->current_version;
1114 APPENDLIST(version->changed_list,
1115 cleanup_version->changed_list,
1119 * Become the current version.
1121 version->writer = ISC_FALSE;
1122 rbtdb->current_version = version;
1123 rbtdb->current_serial = version->serial;
1124 rbtdb->future_version = NULL;
1127 * We're rolling back this transaction.
1129 cleanup_list = version->changed_list;
1130 ISC_LIST_INIT(version->changed_list);
1131 rollback = ISC_TRUE;
1132 cleanup_version = version;
1133 rbtdb->future_version = NULL;
1136 if (version != rbtdb->current_version) {
1138 * There are no external or internal references
1139 * to this version and it can be cleaned up.
1141 cleanup_version = version;
1144 * Find the version with the least serial
1145 * number greater than ours.
1147 least_greater = PREV(version, link);
1148 if (least_greater == NULL)
1149 least_greater = rbtdb->current_version;
1151 INSIST(version->serial < least_greater->serial);
1153 * Is this the least open version?
1155 if (version->serial == rbtdb->least_serial) {
1157 * Yes. Install the new least open
1160 make_least_version(rbtdb,
1165 * Add any unexecuted cleanups to
1166 * those of the least greater version.
1168 APPENDLIST(least_greater->changed_list,
1169 version->changed_list,
1172 } else if (version->serial == rbtdb->least_serial)
1173 INSIST(EMPTY(version->changed_list));
1174 UNLINK(rbtdb->open_versions, version, link);
1177 least_serial = rbtdb->least_serial;
1178 UNLOCK(&rbtdb->lock);
1181 * Update the zone's secure status.
1183 if (version->writer && commit && !IS_CACHE(rbtdb))
1184 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
1186 if (cleanup_version != NULL) {
1187 INSIST(EMPTY(cleanup_version->changed_list));
1188 isc_mem_put(rbtdb->common.mctx, cleanup_version,
1189 sizeof(*cleanup_version));
1192 if (!EMPTY(cleanup_list)) {
1193 for (changed = HEAD(cleanup_list);
1195 changed = next_changed) {
1196 next_changed = NEXT(changed, link);
1197 rbtnode = changed->node;
1198 lock = &rbtdb->node_locks[rbtnode->locknum].lock;
1202 INSIST(rbtnode->references > 0);
1203 rbtnode->references--;
1205 rollback_node(rbtnode, serial);
1207 if (rbtnode->references == 0)
1208 no_references(rbtdb, rbtnode, least_serial,
1209 isc_rwlocktype_none);
1213 isc_mem_put(rbtdb->common.mctx, changed,
1222 * Add the necessary magic for the wildcard name 'name'
1223 * to be found in 'rbtdb'.
1225 * In order for wildcard matching to work correctly in
1226 * zone_find(), we must ensure that a node for the wildcarding
1227 * level exists in the database, and has its 'find_callback'
1228 * and 'wild' bits set.
1230 * E.g. if the wildcard name is "*.sub.example." then we
1231 * must ensure that "sub.example." exists and is marked as
1235 add_wildcard_magic(dns_rbtdb_t *rbtdb, dns_name_t *name) {
1236 isc_result_t result;
1237 dns_name_t foundname;
1238 dns_offsets_t offsets;
1240 dns_rbtnode_t *node = NULL;
1242 dns_name_init(&foundname, offsets);
1243 n = dns_name_countlabels(name);
1246 dns_name_getlabelsequence(name, 1, n, &foundname);
1247 result = dns_rbt_addnode(rbtdb->tree, &foundname, &node);
1248 if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
1250 node->find_callback = 1;
1252 return (ISC_R_SUCCESS);
1256 add_empty_wildcards(dns_rbtdb_t *rbtdb, dns_name_t *name) {
1257 isc_result_t result;
1258 dns_name_t foundname;
1259 dns_offsets_t offsets;
1260 unsigned int n, l, i;
1262 dns_name_init(&foundname, offsets);
1263 n = dns_name_countlabels(name);
1264 l = dns_name_countlabels(&rbtdb->common.origin);
1267 dns_rbtnode_t *node = NULL; /* dummy */
1268 dns_name_getlabelsequence(name, n - i, i, &foundname);
1269 if (dns_name_iswildcard(&foundname)) {
1270 result = add_wildcard_magic(rbtdb, &foundname);
1271 if (result != ISC_R_SUCCESS)
1273 result = dns_rbt_addnode(rbtdb->tree, &foundname,
1275 if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
1280 return (ISC_R_SUCCESS);
1284 findnode(dns_db_t *db, dns_name_t *name, isc_boolean_t create,
1285 dns_dbnode_t **nodep)
1287 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
1288 dns_rbtnode_t *node = NULL;
1289 dns_name_t nodename;
1290 unsigned int locknum;
1291 isc_result_t result;
1292 isc_rwlocktype_t locktype = isc_rwlocktype_read;
1294 REQUIRE(VALID_RBTDB(rbtdb));
1296 dns_name_init(&nodename, NULL);
1297 RWLOCK(&rbtdb->tree_lock, locktype);
1298 result = dns_rbt_findnode(rbtdb->tree, name, NULL, &node, NULL,
1299 DNS_RBTFIND_EMPTYDATA, NULL, NULL);
1300 if (result != ISC_R_SUCCESS) {
1301 RWUNLOCK(&rbtdb->tree_lock, locktype);
1303 if (result == DNS_R_PARTIALMATCH)
1304 result = ISC_R_NOTFOUND;
1308 * It would be nice to try to upgrade the lock instead of
1309 * unlocking then relocking.
1311 locktype = isc_rwlocktype_write;
1312 RWLOCK(&rbtdb->tree_lock, locktype);
1314 result = dns_rbt_addnode(rbtdb->tree, name, &node);
1315 if (result == ISC_R_SUCCESS) {
1316 dns_rbt_namefromnode(node, &nodename);
1317 #ifdef DNS_RBT_USEHASH
1318 node->locknum = node->hashval % rbtdb->node_lock_count;
1320 node->locknum = dns_name_hash(&nodename, ISC_TRUE) %
1321 rbtdb->node_lock_count;
1323 add_empty_wildcards(rbtdb, name);
1325 if (dns_name_iswildcard(name)) {
1326 result = add_wildcard_magic(rbtdb, name);
1327 if (result != ISC_R_SUCCESS) {
1328 RWUNLOCK(&rbtdb->tree_lock, locktype);
1332 } else if (result != ISC_R_EXISTS) {
1333 RWUNLOCK(&rbtdb->tree_lock, locktype);
1337 locknum = node->locknum;
1338 LOCK(&rbtdb->node_locks[locknum].lock);
1339 new_reference(rbtdb, node);
1340 UNLOCK(&rbtdb->node_locks[locknum].lock);
1341 RWUNLOCK(&rbtdb->tree_lock, locktype);
1343 *nodep = (dns_dbnode_t *)node;
1345 return (ISC_R_SUCCESS);
1349 zone_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name, void *arg) {
1350 rbtdb_search_t *search = arg;
1351 rdatasetheader_t *header, *header_next;
1352 rdatasetheader_t *dname_header, *sigdname_header, *ns_header;
1353 rdatasetheader_t *found;
1354 isc_result_t result;
1355 dns_rbtnode_t *onode;
1358 * We only want to remember the topmost zone cut, since it's the one
1359 * that counts, so we'll just continue if we've already found a
1362 if (search->zonecut != NULL)
1363 return (DNS_R_CONTINUE);
1366 result = DNS_R_CONTINUE;
1367 onode = search->rbtdb->origin_node;
1369 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1372 * Look for an NS or DNAME rdataset active in our version.
1375 dname_header = NULL;
1376 sigdname_header = NULL;
1377 for (header = node->data; header != NULL; header = header_next) {
1378 header_next = header->next;
1379 if (header->type == dns_rdatatype_ns ||
1380 header->type == dns_rdatatype_dname ||
1381 header->type == RBTDB_RDATATYPE_SIGDNAME) {
1383 if (header->serial <= search->serial &&
1386 * Is this a "this rdataset doesn't
1389 if (NONEXISTENT(header))
1393 header = header->down;
1394 } while (header != NULL);
1395 if (header != NULL) {
1396 if (header->type == dns_rdatatype_dname)
1397 dname_header = header;
1398 else if (header->type ==
1399 RBTDB_RDATATYPE_SIGDNAME)
1400 sigdname_header = header;
1401 else if (node != onode ||
1402 IS_STUB(search->rbtdb)) {
1404 * We've found an NS rdataset that
1405 * isn't at the origin node. We check
1406 * that they're not at the origin node,
1407 * because otherwise we'd erroneously
1408 * treat the zone top as if it were
1418 * Did we find anything?
1420 if (dname_header != NULL) {
1422 * Note that DNAME has precedence over NS if both exist.
1424 found = dname_header;
1425 search->zonecut_sigrdataset = sigdname_header;
1426 } else if (ns_header != NULL) {
1428 search->zonecut_sigrdataset = NULL;
1431 if (found != NULL) {
1433 * We increment the reference count on node to ensure that
1434 * search->zonecut_rdataset will still be valid later.
1436 new_reference(search->rbtdb, node);
1437 search->zonecut = node;
1438 search->zonecut_rdataset = found;
1439 search->need_cleanup = ISC_TRUE;
1441 * Since we've found a zonecut, anything beneath it is
1442 * glue and is not subject to wildcard matching, so we
1443 * may clear search->wild.
1445 search->wild = ISC_FALSE;
1446 if ((search->options & DNS_DBFIND_GLUEOK) == 0) {
1448 * If the caller does not want to find glue, then
1449 * this is the best answer and the search should
1452 result = DNS_R_PARTIALMATCH;
1457 * The search will continue beneath the zone cut.
1458 * This may or may not be the best match. In case it
1459 * is, we need to remember the node name.
1461 zcname = dns_fixedname_name(&search->zonecut_name);
1462 RUNTIME_CHECK(dns_name_copy(name, zcname, NULL) ==
1464 search->copy_name = ISC_TRUE;
1468 * There is no zonecut at this node which is active in this
1471 * If this is a "wild" node and the caller hasn't disabled
1472 * wildcard matching, remember that we've seen a wild node
1473 * in case we need to go searching for wildcard matches
1476 if (node->wild && (search->options & DNS_DBFIND_NOWILD) == 0)
1477 search->wild = ISC_TRUE;
1480 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1486 bind_rdataset(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
1487 rdatasetheader_t *header, isc_stdtime_t now,
1488 dns_rdataset_t *rdataset)
1493 * Caller must be holding the node lock.
1496 if (rdataset == NULL)
1499 new_reference(rbtdb, node);
1501 INSIST(rdataset->methods == NULL); /* We must be disassociated. */
1503 rdataset->methods = &rdataset_methods;
1504 rdataset->rdclass = rbtdb->common.rdclass;
1505 rdataset->type = RBTDB_RDATATYPE_BASE(header->type);
1506 rdataset->covers = RBTDB_RDATATYPE_EXT(header->type);
1507 rdataset->ttl = header->ttl - now;
1508 rdataset->trust = header->trust;
1509 if (NXDOMAIN(header))
1510 rdataset->attributes |= DNS_RDATASETATTR_NXDOMAIN;
1511 rdataset->private1 = rbtdb;
1512 rdataset->private2 = node;
1513 raw = (unsigned char *)header + sizeof(*header);
1514 rdataset->private3 = raw;
1515 rdataset->count = header->count++;
1516 if (header->count == ISC_UINT32_MAX)
1520 * Reset iterator state.
1522 rdataset->privateuint4 = 0;
1523 rdataset->private5 = NULL;
1526 * Add noqname proof.
1528 rdataset->private6 = header->noqname;
1529 if (rdataset->private6 != NULL)
1530 rdataset->attributes |= DNS_RDATASETATTR_NOQNAME;
1533 static inline isc_result_t
1534 setup_delegation(rbtdb_search_t *search, dns_dbnode_t **nodep,
1535 dns_name_t *foundname, dns_rdataset_t *rdataset,
1536 dns_rdataset_t *sigrdataset)
1538 isc_result_t result;
1540 rbtdb_rdatatype_t type;
1541 dns_rbtnode_t *node;
1544 * The caller MUST NOT be holding any node locks.
1547 node = search->zonecut;
1548 type = search->zonecut_rdataset->type;
1551 * If we have to set foundname, we do it before anything else.
1552 * If we were to set foundname after we had set nodep or bound the
1553 * rdataset, then we'd have to undo that work if dns_name_copy()
1554 * failed. By setting foundname first, there's nothing to undo if
1557 if (foundname != NULL && search->copy_name) {
1558 zcname = dns_fixedname_name(&search->zonecut_name);
1559 result = dns_name_copy(zcname, foundname, NULL);
1560 if (result != ISC_R_SUCCESS)
1563 if (nodep != NULL) {
1565 * Note that we don't have to increment the node's reference
1566 * count here because we're going to use the reference we
1567 * already have in the search block.
1570 search->need_cleanup = ISC_FALSE;
1572 if (rdataset != NULL) {
1573 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1574 bind_rdataset(search->rbtdb, node, search->zonecut_rdataset,
1575 search->now, rdataset);
1576 if (sigrdataset != NULL && search->zonecut_sigrdataset != NULL)
1577 bind_rdataset(search->rbtdb, node,
1578 search->zonecut_sigrdataset,
1579 search->now, sigrdataset);
1580 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1583 if (type == dns_rdatatype_dname)
1584 return (DNS_R_DNAME);
1585 return (DNS_R_DELEGATION);
1588 static inline isc_boolean_t
1589 valid_glue(rbtdb_search_t *search, dns_name_t *name, rbtdb_rdatatype_t type,
1590 dns_rbtnode_t *node)
1593 unsigned int count, size;
1595 isc_boolean_t valid = ISC_FALSE;
1596 dns_offsets_t offsets;
1597 isc_region_t region;
1598 rdatasetheader_t *header;
1601 * No additional locking is required.
1605 * Valid glue types are A, AAAA, A6. NS is also a valid glue type
1606 * if it occurs at a zone cut, but is not valid below it.
1608 if (type == dns_rdatatype_ns) {
1609 if (node != search->zonecut) {
1612 } else if (type != dns_rdatatype_a &&
1613 type != dns_rdatatype_aaaa &&
1614 type != dns_rdatatype_a6) {
1618 header = search->zonecut_rdataset;
1619 raw = (unsigned char *)header + sizeof(*header);
1620 count = raw[0] * 256 + raw[1];
1625 size = raw[0] * 256 + raw[1];
1628 region.length = size;
1631 * XXX Until we have rdata structures, we have no choice but
1632 * to directly access the rdata format.
1634 dns_name_init(&ns_name, offsets);
1635 dns_name_fromregion(&ns_name, ®ion);
1636 if (dns_name_compare(&ns_name, name) == 0) {
1645 static inline isc_boolean_t
1646 activeempty(rbtdb_search_t *search, dns_rbtnodechain_t *chain,
1649 dns_fixedname_t fnext;
1650 dns_fixedname_t forigin;
1655 dns_rbtnode_t *node;
1656 isc_result_t result;
1657 isc_boolean_t answer = ISC_FALSE;
1658 rdatasetheader_t *header;
1660 rbtdb = search->rbtdb;
1662 dns_name_init(&prefix, NULL);
1663 dns_fixedname_init(&fnext);
1664 next = dns_fixedname_name(&fnext);
1665 dns_fixedname_init(&forigin);
1666 origin = dns_fixedname_name(&forigin);
1668 result = dns_rbtnodechain_next(chain, NULL, NULL);
1669 while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
1671 result = dns_rbtnodechain_current(chain, &prefix,
1673 if (result != ISC_R_SUCCESS)
1675 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1676 for (header = node->data;
1678 header = header->next) {
1679 if (header->serial <= search->serial &&
1680 !IGNORE(header) && EXISTS(header))
1683 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1686 result = dns_rbtnodechain_next(chain, NULL, NULL);
1688 if (result == ISC_R_SUCCESS)
1689 result = dns_name_concatenate(&prefix, origin, next, NULL);
1690 if (result == ISC_R_SUCCESS && dns_name_issubdomain(next, name))
1695 static inline isc_boolean_t
1696 activeemtpynode(rbtdb_search_t *search, dns_name_t *qname, dns_name_t *wname) {
1697 dns_fixedname_t fnext;
1698 dns_fixedname_t forigin;
1699 dns_fixedname_t fprev;
1707 dns_rbtnode_t *node;
1708 dns_rbtnodechain_t chain;
1709 isc_boolean_t check_next = ISC_TRUE;
1710 isc_boolean_t check_prev = ISC_TRUE;
1711 isc_boolean_t answer = ISC_FALSE;
1712 isc_result_t result;
1713 rdatasetheader_t *header;
1716 rbtdb = search->rbtdb;
1718 dns_name_init(&name, NULL);
1719 dns_name_init(&tname, NULL);
1720 dns_name_init(&rname, NULL);
1721 dns_fixedname_init(&fnext);
1722 next = dns_fixedname_name(&fnext);
1723 dns_fixedname_init(&fprev);
1724 prev = dns_fixedname_name(&fprev);
1725 dns_fixedname_init(&forigin);
1726 origin = dns_fixedname_name(&forigin);
1729 * Find if qname is at or below a empty node.
1730 * Use our own copy of the chain.
1733 chain = search->chain;
1736 result = dns_rbtnodechain_current(&chain, &name,
1738 if (result != ISC_R_SUCCESS)
1740 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1741 for (header = node->data;
1743 header = header->next) {
1744 if (header->serial <= search->serial &&
1745 !IGNORE(header) && EXISTS(header))
1748 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1751 result = dns_rbtnodechain_prev(&chain, NULL, NULL);
1752 } while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN);
1753 if (result == ISC_R_SUCCESS)
1754 result = dns_name_concatenate(&name, origin, prev, NULL);
1755 if (result != ISC_R_SUCCESS)
1756 check_prev = ISC_FALSE;
1758 result = dns_rbtnodechain_next(&chain, NULL, NULL);
1759 while (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
1761 result = dns_rbtnodechain_current(&chain, &name,
1763 if (result != ISC_R_SUCCESS)
1765 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1766 for (header = node->data;
1768 header = header->next) {
1769 if (header->serial <= search->serial &&
1770 !IGNORE(header) && EXISTS(header))
1773 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1776 result = dns_rbtnodechain_next(&chain, NULL, NULL);
1778 if (result == ISC_R_SUCCESS)
1779 result = dns_name_concatenate(&name, origin, next, NULL);
1780 if (result != ISC_R_SUCCESS)
1781 check_next = ISC_FALSE;
1783 dns_name_clone(qname, &rname);
1786 * Remove the wildcard label to find the terminal name.
1788 n = dns_name_countlabels(wname);
1789 dns_name_getlabelsequence(wname, 1, n - 1, &tname);
1792 if ((check_prev && dns_name_issubdomain(prev, &rname)) ||
1793 (check_next && dns_name_issubdomain(next, &rname))) {
1798 * Remove the left hand label.
1800 n = dns_name_countlabels(&rname);
1801 dns_name_getlabelsequence(&rname, 1, n - 1, &rname);
1802 } while (!dns_name_equal(&rname, &tname));
1806 static inline isc_result_t
1807 find_wildcard(rbtdb_search_t *search, dns_rbtnode_t **nodep,
1811 dns_rbtnode_t *node, *level_node, *wnode;
1812 rdatasetheader_t *header;
1813 isc_result_t result = ISC_R_NOTFOUND;
1816 dns_fixedname_t fwname;
1818 isc_boolean_t done, wild, active;
1819 dns_rbtnodechain_t wchain;
1822 * Caller must be holding the tree lock and MUST NOT be holding
1827 * Examine each ancestor level. If the level's wild bit
1828 * is set, then construct the corresponding wildcard name and
1829 * search for it. If the wildcard node exists, and is active in
1830 * this version, we're done. If not, then we next check to see
1831 * if the ancestor is active in this version. If so, then there
1832 * can be no possible wildcard match and again we're done. If not,
1833 * continue the search.
1836 rbtdb = search->rbtdb;
1837 i = search->chain.level_matches;
1841 LOCK(&(rbtdb->node_locks[node->locknum].lock));
1844 * First we try to figure out if this node is active in
1845 * the search's version. We do this now, even though we
1846 * may not need the information, because it simplifies the
1847 * locking and code flow.
1849 for (header = node->data;
1851 header = header->next) {
1852 if (header->serial <= search->serial &&
1853 !IGNORE(header) && EXISTS(header))
1866 UNLOCK(&(rbtdb->node_locks[node->locknum].lock));
1870 * Construct the wildcard name for this level.
1872 dns_name_init(&name, NULL);
1873 dns_rbt_namefromnode(node, &name);
1874 dns_fixedname_init(&fwname);
1875 wname = dns_fixedname_name(&fwname);
1876 result = dns_name_concatenate(dns_wildcardname, &name,
1879 while (result == ISC_R_SUCCESS && j != 0) {
1881 level_node = search->chain.levels[j];
1882 dns_name_init(&name, NULL);
1883 dns_rbt_namefromnode(level_node, &name);
1884 result = dns_name_concatenate(wname,
1889 if (result != ISC_R_SUCCESS)
1893 dns_rbtnodechain_init(&wchain, NULL);
1894 result = dns_rbt_findnode(rbtdb->tree, wname,
1895 NULL, &wnode, &wchain,
1896 DNS_RBTFIND_EMPTYDATA,
1898 if (result == ISC_R_SUCCESS) {
1900 * We have found the wildcard node. If it
1901 * is active in the search's version, we're
1904 LOCK(&(rbtdb->node_locks[wnode->locknum].lock));
1905 for (header = wnode->data;
1907 header = header->next) {
1908 if (header->serial <= search->serial &&
1909 !IGNORE(header) && EXISTS(header))
1912 UNLOCK(&(rbtdb->node_locks[wnode->locknum].lock));
1913 if (header != NULL ||
1914 activeempty(search, &wchain, wname)) {
1915 if (activeemtpynode(search, qname, wname))
1916 return (ISC_R_NOTFOUND);
1918 * The wildcard node is active!
1920 * Note: result is still ISC_R_SUCCESS
1921 * so we don't have to set it.
1926 } else if (result != ISC_R_NOTFOUND &&
1927 result != DNS_R_PARTIALMATCH) {
1929 * An error has occurred. Bail out.
1937 * The level node is active. Any wildcarding
1938 * present at higher levels has no
1939 * effect and we're done.
1941 result = ISC_R_NOTFOUND;
1947 node = search->chain.levels[i];
1955 static inline isc_result_t
1956 find_closest_nsec(rbtdb_search_t *search, dns_dbnode_t **nodep,
1957 dns_name_t *foundname, dns_rdataset_t *rdataset,
1958 dns_rdataset_t *sigrdataset, isc_boolean_t need_sig)
1960 dns_rbtnode_t *node;
1961 rdatasetheader_t *header, *header_next, *found, *foundsig;
1962 isc_boolean_t empty_node;
1963 isc_result_t result;
1964 dns_fixedname_t fname, forigin;
1965 dns_name_t *name, *origin;
1969 dns_fixedname_init(&fname);
1970 name = dns_fixedname_name(&fname);
1971 dns_fixedname_init(&forigin);
1972 origin = dns_fixedname_name(&forigin);
1973 result = dns_rbtnodechain_current(&search->chain, name,
1975 if (result != ISC_R_SUCCESS)
1977 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
1980 empty_node = ISC_TRUE;
1981 for (header = node->data;
1983 header = header_next) {
1984 header_next = header->next;
1986 * Look for an active, extant NSEC or RRSIG NSEC.
1989 if (header->serial <= search->serial &&
1992 * Is this a "this rdataset doesn't
1995 if (NONEXISTENT(header))
1999 header = header->down;
2000 } while (header != NULL);
2001 if (header != NULL) {
2003 * We now know that there is at least one
2004 * active rdataset at this node.
2006 empty_node = ISC_FALSE;
2007 if (header->type == dns_rdatatype_nsec) {
2009 if (foundsig != NULL)
2011 } else if (header->type ==
2012 RBTDB_RDATATYPE_SIGNSEC) {
2020 if (found != NULL &&
2021 (foundsig != NULL || !need_sig))
2024 * We've found the right NSEC record.
2026 * Note: for this to really be the right
2027 * NSEC record, it's essential that the NSEC
2028 * records of any nodes obscured by a zone
2029 * cut have been removed; we assume this is
2032 result = dns_name_concatenate(name, origin,
2034 if (result == ISC_R_SUCCESS) {
2035 if (nodep != NULL) {
2036 new_reference(search->rbtdb,
2040 bind_rdataset(search->rbtdb, node,
2043 if (foundsig != NULL)
2044 bind_rdataset(search->rbtdb,
2050 } else if (found == NULL && foundsig == NULL) {
2052 * This node is active, but has no NSEC or
2053 * RRSIG NSEC. That means it's glue or
2054 * other obscured zone data that isn't
2055 * relevant for our search. Treat the
2056 * node as if it were empty and keep looking.
2058 empty_node = ISC_TRUE;
2059 result = dns_rbtnodechain_prev(&search->chain,
2063 * We found an active node, but either the
2064 * NSEC or the RRSIG NSEC is missing. This
2067 result = DNS_R_BADDB;
2071 * This node isn't active. We've got to keep
2074 result = dns_rbtnodechain_prev(&search->chain, NULL,
2077 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2078 } while (empty_node && result == ISC_R_SUCCESS);
2081 * If the result is ISC_R_NOMORE, then we got to the beginning of
2082 * the database and didn't find a NSEC record. This shouldn't
2085 if (result == ISC_R_NOMORE)
2086 result = DNS_R_BADDB;
2092 zone_find(dns_db_t *db, dns_name_t *name, dns_dbversion_t *version,
2093 dns_rdatatype_t type, unsigned int options, isc_stdtime_t now,
2094 dns_dbnode_t **nodep, dns_name_t *foundname,
2095 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2097 dns_rbtnode_t *node = NULL;
2098 isc_result_t result;
2099 rbtdb_search_t search;
2100 isc_boolean_t cname_ok = ISC_TRUE;
2101 isc_boolean_t close_version = ISC_FALSE;
2102 isc_boolean_t maybe_zonecut = ISC_FALSE;
2103 isc_boolean_t at_zonecut = ISC_FALSE;
2105 isc_boolean_t empty_node;
2107 rdatasetheader_t *header, *header_next, *found, *nsecheader;
2108 rdatasetheader_t *foundsig, *cnamesig, *nsecsig;
2109 rbtdb_rdatatype_t sigtype;
2110 isc_boolean_t active;
2111 dns_rbtnodechain_t chain;
2114 search.rbtdb = (dns_rbtdb_t *)db;
2116 REQUIRE(VALID_RBTDB(search.rbtdb));
2119 * We don't care about 'now'.
2124 * If the caller didn't supply a version, attach to the current
2127 if (version == NULL) {
2128 currentversion(db, &version);
2129 close_version = ISC_TRUE;
2132 search.rbtversion = version;
2133 search.serial = search.rbtversion->serial;
2134 search.options = options;
2135 search.copy_name = ISC_FALSE;
2136 search.need_cleanup = ISC_FALSE;
2137 search.wild = ISC_FALSE;
2138 search.zonecut = NULL;
2139 dns_fixedname_init(&search.zonecut_name);
2140 dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
2144 * 'wild' will be true iff. we've matched a wildcard.
2148 RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2151 * Search down from the root of the tree. If, while going down, we
2152 * encounter a callback node, zone_zonecut_callback() will search the
2153 * rdatasets at the zone cut for active DNAME or NS rdatasets.
2155 result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
2156 &search.chain, DNS_RBTFIND_EMPTYDATA,
2157 zone_zonecut_callback, &search);
2159 if (result == DNS_R_PARTIALMATCH) {
2161 if (search.zonecut != NULL) {
2162 result = setup_delegation(&search, nodep, foundname,
2163 rdataset, sigrdataset);
2169 * At least one of the levels in the search chain
2170 * potentially has a wildcard. For each such level,
2171 * we must see if there's a matching wildcard active
2172 * in the current version.
2174 result = find_wildcard(&search, &node, name);
2175 if (result == ISC_R_SUCCESS) {
2176 result = dns_name_copy(name, foundname, NULL);
2177 if (result != ISC_R_SUCCESS)
2182 else if (result != ISC_R_NOTFOUND)
2186 chain = search.chain;
2187 active = activeempty(&search, &chain, name);
2190 * If we're here, then the name does not exist, is not
2191 * beneath a zonecut, and there's no matching wildcard.
2193 if (search.rbtdb->secure ||
2194 (search.options & DNS_DBFIND_FORCENSEC) != 0)
2196 result = find_closest_nsec(&search, nodep, foundname,
2197 rdataset, sigrdataset,
2198 search.rbtdb->secure);
2199 if (result == ISC_R_SUCCESS)
2200 result = active ? DNS_R_EMPTYNAME :
2203 result = active ? DNS_R_EMPTYNAME : DNS_R_NXDOMAIN;
2205 } else if (result != ISC_R_SUCCESS)
2210 * We have found a node whose name is the desired name, or we
2211 * have matched a wildcard.
2214 if (search.zonecut != NULL) {
2216 * If we're beneath a zone cut, we don't want to look for
2217 * CNAMEs because they're not legitimate zone glue.
2219 cname_ok = ISC_FALSE;
2222 * The node may be a zone cut itself. If it might be one,
2223 * make sure we check for it later.
2225 if (node->find_callback &&
2226 (node != search.rbtdb->origin_node ||
2227 IS_STUB(search.rbtdb)) &&
2228 !dns_rdatatype_atparent(type))
2229 maybe_zonecut = ISC_TRUE;
2233 * Certain DNSSEC types are not subject to CNAME matching
2234 * (RFC4035, section 2.5 and RFC3007).
2236 * We don't check for RRSIG, because we don't store RRSIG records
2239 if (type == dns_rdatatype_key || type == dns_rdatatype_nsec)
2240 cname_ok = ISC_FALSE;
2243 * We now go looking for rdata...
2246 LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2250 sigtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
2254 empty_node = ISC_TRUE;
2255 for (header = node->data; header != NULL; header = header_next) {
2256 header_next = header->next;
2258 * Look for an active, extant rdataset.
2261 if (header->serial <= search.serial &&
2264 * Is this a "this rdataset doesn't
2267 if (NONEXISTENT(header))
2271 header = header->down;
2272 } while (header != NULL);
2273 if (header != NULL) {
2275 * We now know that there is at least one active
2276 * rdataset at this node.
2278 empty_node = ISC_FALSE;
2281 * Do special zone cut handling, if requested.
2283 if (maybe_zonecut &&
2284 header->type == dns_rdatatype_ns) {
2286 * We increment the reference count on node to
2287 * ensure that search->zonecut_rdataset will
2288 * still be valid later.
2290 new_reference(search.rbtdb, node);
2291 search.zonecut = node;
2292 search.zonecut_rdataset = header;
2293 search.zonecut_sigrdataset = NULL;
2294 search.need_cleanup = ISC_TRUE;
2295 maybe_zonecut = ISC_FALSE;
2296 at_zonecut = ISC_TRUE;
2298 * It is not clear if KEY should still be
2299 * allowed at the parent side of the zone
2300 * cut or not. It is needed for RFC3007
2301 * validated updates.
2303 if ((search.options & DNS_DBFIND_GLUEOK) == 0
2304 && type != dns_rdatatype_nsec
2305 && type != dns_rdatatype_key) {
2307 * Glue is not OK, but any answer we
2308 * could return would be glue. Return
2314 if (found != NULL && foundsig != NULL)
2319 * If we found a type we were looking for,
2322 if (header->type == type ||
2323 type == dns_rdatatype_any ||
2324 (header->type == dns_rdatatype_cname &&
2327 * We've found the answer!
2330 if (header->type == dns_rdatatype_cname &&
2333 * We may be finding a CNAME instead
2334 * of the desired type.
2336 * If we've already got the CNAME RRSIG,
2337 * use it, otherwise change sigtype
2338 * so that we find it.
2340 if (cnamesig != NULL)
2341 foundsig = cnamesig;
2344 RBTDB_RDATATYPE_SIGCNAME;
2347 * If we've got all we need, end the search.
2349 if (!maybe_zonecut && foundsig != NULL)
2351 } else if (header->type == sigtype) {
2353 * We've found the RRSIG rdataset for our
2354 * target type. Remember it.
2358 * If we've got all we need, end the search.
2360 if (!maybe_zonecut && found != NULL)
2362 } else if (header->type == dns_rdatatype_nsec) {
2364 * Remember a NSEC rdataset even if we're
2365 * not specifically looking for it, because
2366 * we might need it later.
2368 nsecheader = header;
2369 } else if (header->type == RBTDB_RDATATYPE_SIGNSEC) {
2371 * If we need the NSEC rdataset, we'll also
2372 * need its signature.
2375 } else if (cname_ok &&
2376 header->type == RBTDB_RDATATYPE_SIGCNAME) {
2378 * If we get a CNAME match, we'll also need
2388 * We have an exact match for the name, but there are no
2389 * active rdatasets in the desired version. That means that
2390 * this node doesn't exist in the desired version, and that
2391 * we really have a partial match.
2394 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2400 * If we didn't find what we were looking for...
2402 if (found == NULL) {
2403 if (search.zonecut != NULL) {
2405 * We were trying to find glue at a node beneath a
2406 * zone cut, but didn't.
2408 * Return the delegation.
2410 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2411 result = setup_delegation(&search, nodep, foundname,
2412 rdataset, sigrdataset);
2416 * The desired type doesn't exist.
2418 result = DNS_R_NXRRSET;
2419 if (search.rbtdb->secure &&
2420 (nsecheader == NULL || nsecsig == NULL)) {
2422 * The zone is secure but there's no NSEC,
2423 * or the NSEC has no signature!
2426 result = DNS_R_BADDB;
2430 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2431 result = find_closest_nsec(&search, nodep, foundname,
2432 rdataset, sigrdataset,
2433 search.rbtdb->secure);
2434 if (result == ISC_R_SUCCESS)
2435 result = DNS_R_EMPTYWILD;
2438 if ((search.options & DNS_DBFIND_FORCENSEC) != 0 &&
2442 * There's no NSEC record, and we were told
2445 result = DNS_R_BADDB;
2448 if (nodep != NULL) {
2449 new_reference(search.rbtdb, node);
2452 if (search.rbtdb->secure ||
2453 (search.options & DNS_DBFIND_FORCENSEC) != 0)
2455 bind_rdataset(search.rbtdb, node, nsecheader,
2457 if (nsecsig != NULL)
2458 bind_rdataset(search.rbtdb, node,
2459 nsecsig, 0, sigrdataset);
2462 foundname->attributes |= DNS_NAMEATTR_WILDCARD;
2467 * We found what we were looking for, or we found a CNAME.
2470 if (type != found->type &&
2471 type != dns_rdatatype_any &&
2472 found->type == dns_rdatatype_cname) {
2474 * We weren't doing an ANY query and we found a CNAME instead
2475 * of the type we were looking for, so we need to indicate
2476 * that result to the caller.
2478 result = DNS_R_CNAME;
2479 } else if (search.zonecut != NULL) {
2481 * If we're beneath a zone cut, we must indicate that the
2482 * result is glue, unless we're actually at the zone cut
2483 * and the type is NSEC or KEY.
2485 if (search.zonecut == node) {
2487 * It is not clear if KEY should still be
2488 * allowed at the parent side of the zone
2489 * cut or not. It is needed for RFC3007
2490 * validated updates.
2492 if (type == dns_rdatatype_nsec ||
2493 type == dns_rdatatype_key)
2494 result = ISC_R_SUCCESS;
2495 else if (type == dns_rdatatype_any)
2496 result = DNS_R_ZONECUT;
2498 result = DNS_R_GLUE;
2500 result = DNS_R_GLUE;
2502 * We might have found data that isn't glue, but was occluded
2503 * by a dynamic update. If the caller cares about this, they
2504 * will have told us to validate glue.
2506 * XXX We should cache the glue validity state!
2508 if (result == DNS_R_GLUE &&
2509 (search.options & DNS_DBFIND_VALIDATEGLUE) != 0 &&
2510 !valid_glue(&search, foundname, type, node)) {
2511 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2512 result = setup_delegation(&search, nodep, foundname,
2513 rdataset, sigrdataset);
2518 * An ordinary successful query!
2520 result = ISC_R_SUCCESS;
2523 if (nodep != NULL) {
2525 new_reference(search.rbtdb, node);
2527 search.need_cleanup = ISC_FALSE;
2531 if (type != dns_rdatatype_any) {
2532 bind_rdataset(search.rbtdb, node, found, 0, rdataset);
2533 if (foundsig != NULL)
2534 bind_rdataset(search.rbtdb, node, foundsig, 0,
2539 foundname->attributes |= DNS_NAMEATTR_WILDCARD;
2542 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2545 RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2548 * If we found a zonecut but aren't going to use it, we have to
2551 if (search.need_cleanup) {
2552 node = search.zonecut;
2553 lock = &(search.rbtdb->node_locks[node->locknum].lock);
2556 INSIST(node->references > 0);
2558 if (node->references == 0)
2559 no_references(search.rbtdb, node, 0,
2560 isc_rwlocktype_none);
2566 closeversion(db, &version, ISC_FALSE);
2568 dns_rbtnodechain_reset(&search.chain);
2574 zone_findzonecut(dns_db_t *db, dns_name_t *name, unsigned int options,
2575 isc_stdtime_t now, dns_dbnode_t **nodep,
2576 dns_name_t *foundname,
2577 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2586 UNUSED(sigrdataset);
2588 FATAL_ERROR(__FILE__, __LINE__, "zone_findzonecut() called!");
2590 return (ISC_R_NOTIMPLEMENTED);
2594 cache_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name, void *arg) {
2595 rbtdb_search_t *search = arg;
2596 rdatasetheader_t *header, *header_prev, *header_next;
2597 rdatasetheader_t *dname_header, *sigdname_header;
2598 isc_result_t result;
2602 REQUIRE(search->zonecut == NULL);
2605 * Keep compiler silent.
2609 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2612 * Look for a DNAME or RRSIG DNAME rdataset.
2614 dname_header = NULL;
2615 sigdname_header = NULL;
2617 for (header = node->data; header != NULL; header = header_next) {
2618 header_next = header->next;
2619 if (header->ttl <= search->now) {
2621 * This rdataset is stale. If no one else is
2622 * using the node, we can clean it up right
2623 * now, otherwise we mark it as stale, and
2624 * the node as dirty, so it will get cleaned
2627 if (node->references == 0) {
2628 INSIST(header->down == NULL);
2629 if (header_prev != NULL)
2633 node->data = header->next;
2634 free_rdataset(search->rbtdb->common.mctx,
2637 header->attributes |=
2638 RDATASET_ATTR_STALE;
2640 header_prev = header;
2642 } else if (header->type == dns_rdatatype_dname &&
2644 dname_header = header;
2645 header_prev = header;
2646 } else if (header->type == RBTDB_RDATATYPE_SIGDNAME &&
2648 sigdname_header = header;
2649 header_prev = header;
2651 header_prev = header;
2654 if (dname_header != NULL &&
2655 (dname_header->trust != dns_trust_pending ||
2656 (search->options & DNS_DBFIND_PENDINGOK) != 0)) {
2658 * We increment the reference count on node to ensure that
2659 * search->zonecut_rdataset will still be valid later.
2661 new_reference(search->rbtdb, node);
2662 search->zonecut = node;
2663 search->zonecut_rdataset = dname_header;
2664 search->zonecut_sigrdataset = sigdname_header;
2665 search->need_cleanup = ISC_TRUE;
2666 result = DNS_R_PARTIALMATCH;
2668 result = DNS_R_CONTINUE;
2670 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2675 static inline isc_result_t
2676 find_deepest_zonecut(rbtdb_search_t *search, dns_rbtnode_t *node,
2677 dns_dbnode_t **nodep, dns_name_t *foundname,
2678 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2681 dns_rbtnode_t *level_node;
2682 rdatasetheader_t *header, *header_prev, *header_next;
2683 rdatasetheader_t *found, *foundsig;
2684 isc_result_t result = ISC_R_NOTFOUND;
2690 * Caller must be holding the tree lock.
2693 rbtdb = search->rbtdb;
2694 i = search->chain.level_matches;
2697 LOCK(&(rbtdb->node_locks[node->locknum].lock));
2700 * Look for NS and RRSIG NS rdatasets.
2705 for (header = node->data;
2707 header = header_next) {
2708 header_next = header->next;
2709 if (header->ttl <= search->now) {
2711 * This rdataset is stale. If no one else is
2712 * using the node, we can clean it up right
2713 * now, otherwise we mark it as stale, and
2714 * the node as dirty, so it will get cleaned
2717 if (node->references == 0) {
2718 INSIST(header->down == NULL);
2719 if (header_prev != NULL)
2723 node->data = header->next;
2724 free_rdataset(rbtdb->common.mctx,
2727 header->attributes |=
2728 RDATASET_ATTR_STALE;
2730 header_prev = header;
2732 } else if (EXISTS(header)) {
2734 * We've found an extant rdataset. See if
2735 * we're interested in it.
2737 if (header->type == dns_rdatatype_ns) {
2739 if (foundsig != NULL)
2741 } else if (header->type ==
2742 RBTDB_RDATATYPE_SIGNS) {
2747 header_prev = header;
2749 header_prev = header;
2752 if (found != NULL) {
2754 * If we have to set foundname, we do it before
2755 * anything else. If we were to set foundname after
2756 * we had set nodep or bound the rdataset, then we'd
2757 * have to undo that work if dns_name_concatenate()
2758 * failed. By setting foundname first, there's
2759 * nothing to undo if we have trouble.
2761 if (foundname != NULL) {
2762 dns_name_init(&name, NULL);
2763 dns_rbt_namefromnode(node, &name);
2764 result = dns_name_copy(&name, foundname, NULL);
2765 while (result == ISC_R_SUCCESS && i > 0) {
2767 level_node = search->chain.levels[i];
2768 dns_name_init(&name, NULL);
2769 dns_rbt_namefromnode(level_node,
2772 dns_name_concatenate(foundname,
2777 if (result != ISC_R_SUCCESS) {
2782 result = DNS_R_DELEGATION;
2783 if (nodep != NULL) {
2784 new_reference(search->rbtdb, node);
2787 bind_rdataset(search->rbtdb, node, found, search->now,
2789 if (foundsig != NULL)
2790 bind_rdataset(search->rbtdb, node, foundsig,
2791 search->now, sigrdataset);
2795 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2797 if (found == NULL && i > 0) {
2799 node = search->chain.levels[i];
2809 find_coveringnsec(rbtdb_search_t *search, dns_dbnode_t **nodep,
2810 isc_stdtime_t now, dns_name_t *foundname,
2811 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2813 dns_rbtnode_t *node;
2814 rdatasetheader_t *header, *header_next, *header_prev;
2815 rdatasetheader_t *found, *foundsig;
2816 isc_boolean_t empty_node;
2817 isc_result_t result;
2818 dns_fixedname_t fname, forigin;
2819 dns_name_t *name, *origin;
2820 rbtdb_rdatatype_t matchtype, sigmatchtype;
2822 matchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_nsec, 0);
2823 sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig,
2824 dns_rdatatype_nsec);
2828 dns_fixedname_init(&fname);
2829 name = dns_fixedname_name(&fname);
2830 dns_fixedname_init(&forigin);
2831 origin = dns_fixedname_name(&forigin);
2832 result = dns_rbtnodechain_current(&search->chain, name,
2834 if (result != ISC_R_SUCCESS)
2836 LOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2839 empty_node = ISC_TRUE;
2841 for (header = node->data;
2843 header = header_next) {
2844 header_next = header->next;
2845 if (header->ttl <= now) {
2847 * This rdataset is stale. If no one else is
2848 * using the node, we can clean it up right
2849 * now, otherwise we mark it as stale, and the
2850 * node as dirty, so it will get cleaned up
2853 if (header->ttl > search->now - RBTDB_VIRTUAL)
2854 header_prev = header;
2855 else if (node->references == 0) {
2856 INSIST(header->down == NULL);
2857 if (header_prev != NULL)
2861 node->data = header->next;
2862 free_rdataset(search->rbtdb->common.mctx,
2865 header->attributes |=
2866 RDATASET_ATTR_STALE;
2868 header_prev = header;
2872 if (NONEXISTENT(header) || NXDOMAIN(header)) {
2873 header_prev = header;
2876 empty_node = ISC_FALSE;
2877 if (header->type == matchtype)
2879 else if (header->type == sigmatchtype)
2881 header_prev = header;
2883 if (found != NULL) {
2884 result = dns_name_concatenate(name, origin,
2886 if (result != ISC_R_SUCCESS)
2888 bind_rdataset(search->rbtdb, node, found,
2890 if (foundsig != NULL)
2891 bind_rdataset(search->rbtdb, node, foundsig,
2893 new_reference(search->rbtdb, node);
2895 result = DNS_R_COVERINGNSEC;
2896 } else if (!empty_node) {
2897 result = ISC_R_NOTFOUND;
2899 result = dns_rbtnodechain_prev(&search->chain, NULL,
2902 UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock));
2903 } while (empty_node && result == ISC_R_SUCCESS);
2908 cache_find(dns_db_t *db, dns_name_t *name, dns_dbversion_t *version,
2909 dns_rdatatype_t type, unsigned int options, isc_stdtime_t now,
2910 dns_dbnode_t **nodep, dns_name_t *foundname,
2911 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
2913 dns_rbtnode_t *node = NULL;
2914 isc_result_t result;
2915 rbtdb_search_t search;
2916 isc_boolean_t cname_ok = ISC_TRUE;
2917 isc_boolean_t empty_node;
2919 rdatasetheader_t *header, *header_prev, *header_next;
2920 rdatasetheader_t *found, *nsheader;
2921 rdatasetheader_t *foundsig, *nssig, *cnamesig;
2922 rbtdb_rdatatype_t sigtype, negtype;
2926 search.rbtdb = (dns_rbtdb_t *)db;
2928 REQUIRE(VALID_RBTDB(search.rbtdb));
2929 REQUIRE(version == NULL);
2932 isc_stdtime_get(&now);
2934 search.rbtversion = NULL;
2936 search.options = options;
2937 search.copy_name = ISC_FALSE;
2938 search.need_cleanup = ISC_FALSE;
2939 search.wild = ISC_FALSE;
2940 search.zonecut = NULL;
2941 dns_fixedname_init(&search.zonecut_name);
2942 dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
2945 RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
2948 * Search down from the root of the tree. If, while going down, we
2949 * encounter a callback node, cache_zonecut_callback() will search the
2950 * rdatasets at the zone cut for a DNAME rdataset.
2952 result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
2953 &search.chain, DNS_RBTFIND_EMPTYDATA,
2954 cache_zonecut_callback, &search);
2956 if (result == DNS_R_PARTIALMATCH) {
2957 if ((search.options & DNS_DBFIND_COVERINGNSEC) != 0) {
2958 result = find_coveringnsec(&search, nodep, now,
2959 foundname, rdataset,
2961 if (result == DNS_R_COVERINGNSEC)
2964 if (search.zonecut != NULL) {
2965 result = setup_delegation(&search, nodep, foundname,
2966 rdataset, sigrdataset);
2970 result = find_deepest_zonecut(&search, node, nodep,
2971 foundname, rdataset,
2975 } else if (result != ISC_R_SUCCESS)
2979 * Certain DNSSEC types are not subject to CNAME matching
2980 * (RFC4035, section 2.5 and RFC3007).
2982 * We don't check for RRSIG, because we don't store RRSIG records
2985 if (type == dns_rdatatype_key || type == dns_rdatatype_nsec)
2986 cname_ok = ISC_FALSE;
2989 * We now go looking for rdata...
2992 LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
2996 sigtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
2997 negtype = RBTDB_RDATATYPE_VALUE(0, type);
3001 empty_node = ISC_TRUE;
3003 for (header = node->data; header != NULL; header = header_next) {
3004 header_next = header->next;
3005 if (header->ttl <= now) {
3007 * This rdataset is stale. If no one else is using the
3008 * node, we can clean it up right now, otherwise we
3009 * mark it as stale, and the node as dirty, so it will
3010 * get cleaned up later.
3012 if (header->ttl > now - RBTDB_VIRTUAL)
3013 header_prev = header;
3014 else if (node->references == 0) {
3015 INSIST(header->down == NULL);
3016 if (header_prev != NULL)
3017 header_prev->next = header->next;
3019 node->data = header->next;
3020 free_rdataset(search.rbtdb->common.mctx,
3023 header->attributes |= RDATASET_ATTR_STALE;
3025 header_prev = header;
3027 } else if (EXISTS(header)) {
3029 * We now know that there is at least one active
3030 * non-stale rdataset at this node.
3032 empty_node = ISC_FALSE;
3035 * If we found a type we were looking for, remember
3038 if (header->type == type ||
3039 (type == dns_rdatatype_any &&
3040 RBTDB_RDATATYPE_BASE(header->type) != 0) ||
3041 (cname_ok && header->type ==
3042 dns_rdatatype_cname)) {
3044 * We've found the answer.
3047 if (header->type == dns_rdatatype_cname &&
3051 * If we've already got the CNAME RRSIG,
3052 * use it, otherwise change sigtype
3053 * so that we find it.
3055 if (cnamesig != NULL)
3056 foundsig = cnamesig;
3059 RBTDB_RDATATYPE_SIGCNAME;
3060 foundsig = cnamesig;
3062 } else if (header->type == sigtype) {
3064 * We've found the RRSIG rdataset for our
3065 * target type. Remember it.
3068 } else if (header->type == RBTDB_RDATATYPE_NCACHEANY ||
3069 header->type == negtype) {
3071 * We've found a negative cache entry.
3074 } else if (header->type == dns_rdatatype_ns) {
3076 * Remember a NS rdataset even if we're
3077 * not specifically looking for it, because
3078 * we might need it later.
3081 } else if (header->type == RBTDB_RDATATYPE_SIGNS) {
3083 * If we need the NS rdataset, we'll also
3084 * need its signature.
3087 } else if (cname_ok &&
3088 header->type == RBTDB_RDATATYPE_SIGCNAME) {
3090 * If we get a CNAME match, we'll also need
3095 header_prev = header;
3097 header_prev = header;
3102 * We have an exact match for the name, but there are no
3103 * extant rdatasets. That means that this node doesn't
3104 * meaningfully exist, and that we really have a partial match.
3106 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3111 * If we didn't find what we were looking for...
3113 if (found == NULL ||
3114 (found->trust == dns_trust_glue &&
3115 ((options & DNS_DBFIND_GLUEOK) == 0)) ||
3116 (found->trust == dns_trust_pending &&
3117 ((options & DNS_DBFIND_PENDINGOK) == 0))) {
3119 * If there is an NS rdataset at this node, then this is the
3122 if (nsheader != NULL) {
3123 if (nodep != NULL) {
3124 new_reference(search.rbtdb, node);
3127 bind_rdataset(search.rbtdb, node, nsheader, search.now,
3130 bind_rdataset(search.rbtdb, node, nssig,
3131 search.now, sigrdataset);
3132 result = DNS_R_DELEGATION;
3137 * Go find the deepest zone cut.
3139 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3144 * We found what we were looking for, or we found a CNAME.
3147 if (nodep != NULL) {
3148 new_reference(search.rbtdb, node);
3152 if (RBTDB_RDATATYPE_BASE(found->type) == 0) {
3154 * We found a negative cache entry.
3156 if (NXDOMAIN(found))
3157 result = DNS_R_NCACHENXDOMAIN;
3159 result = DNS_R_NCACHENXRRSET;
3160 } else if (type != found->type &&
3161 type != dns_rdatatype_any &&
3162 found->type == dns_rdatatype_cname) {
3164 * We weren't doing an ANY query and we found a CNAME instead
3165 * of the type we were looking for, so we need to indicate
3166 * that result to the caller.
3168 result = DNS_R_CNAME;
3171 * An ordinary successful query!
3173 result = ISC_R_SUCCESS;
3176 if (type != dns_rdatatype_any || result == DNS_R_NCACHENXDOMAIN ||
3177 result == DNS_R_NCACHENXRRSET) {
3178 bind_rdataset(search.rbtdb, node, found, search.now,
3180 if (foundsig != NULL)
3181 bind_rdataset(search.rbtdb, node, foundsig, search.now,
3186 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3189 RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3192 * If we found a zonecut but aren't going to use it, we have to
3195 if (search.need_cleanup) {
3196 node = search.zonecut;
3197 lock = &(search.rbtdb->node_locks[node->locknum].lock);
3200 INSIST(node->references > 0);
3202 if (node->references == 0)
3203 no_references(search.rbtdb, node, 0,
3204 isc_rwlocktype_none);
3208 dns_rbtnodechain_reset(&search.chain);
3214 cache_findzonecut(dns_db_t *db, dns_name_t *name, unsigned int options,
3215 isc_stdtime_t now, dns_dbnode_t **nodep,
3216 dns_name_t *foundname,
3217 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset)
3219 dns_rbtnode_t *node = NULL;
3220 isc_result_t result;
3221 rbtdb_search_t search;
3222 rdatasetheader_t *header, *header_prev, *header_next;
3223 rdatasetheader_t *found, *foundsig;
3224 unsigned int rbtoptions = DNS_RBTFIND_EMPTYDATA;
3226 search.rbtdb = (dns_rbtdb_t *)db;
3228 REQUIRE(VALID_RBTDB(search.rbtdb));
3231 isc_stdtime_get(&now);
3233 search.rbtversion = NULL;
3235 search.options = options;
3236 search.copy_name = ISC_FALSE;
3237 search.need_cleanup = ISC_FALSE;
3238 search.wild = ISC_FALSE;
3239 search.zonecut = NULL;
3240 dns_fixedname_init(&search.zonecut_name);
3241 dns_rbtnodechain_init(&search.chain, search.rbtdb->common.mctx);
3244 if ((options & DNS_DBFIND_NOEXACT) != 0)
3245 rbtoptions |= DNS_RBTFIND_NOEXACT;
3247 RWLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3250 * Search down from the root of the tree.
3252 result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
3253 &search.chain, rbtoptions, NULL, &search);
3255 if (result == DNS_R_PARTIALMATCH) {
3257 result = find_deepest_zonecut(&search, node, nodep, foundname,
3258 rdataset, sigrdataset);
3260 } else if (result != ISC_R_SUCCESS)
3264 * We now go looking for an NS rdataset at the node.
3267 LOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3272 for (header = node->data; header != NULL; header = header_next) {
3273 header_next = header->next;
3274 if (header->ttl <= now) {
3276 * This rdataset is stale. If no one else is using the
3277 * node, we can clean it up right now, otherwise we
3278 * mark it as stale, and the node as dirty, so it will
3279 * get cleaned up later.
3281 if (header->ttl > now - RBTDB_VIRTUAL)
3282 header_prev = header;
3283 else if (node->references == 0) {
3284 INSIST(header->down == NULL);
3285 if (header_prev != NULL)
3286 header_prev->next = header->next;
3288 node->data = header->next;
3289 free_rdataset(search.rbtdb->common.mctx,
3292 header->attributes |= RDATASET_ATTR_STALE;
3294 header_prev = header;
3296 } else if (EXISTS(header)) {
3298 * If we found a type we were looking for, remember
3301 if (header->type == dns_rdatatype_ns) {
3303 * Remember a NS rdataset even if we're
3304 * not specifically looking for it, because
3305 * we might need it later.
3308 } else if (header->type == RBTDB_RDATATYPE_SIGNS) {
3310 * If we need the NS rdataset, we'll also
3311 * need its signature.
3315 header_prev = header;
3317 header_prev = header;
3320 if (found == NULL) {
3322 * No NS records here.
3324 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3328 if (nodep != NULL) {
3329 new_reference(search.rbtdb, node);
3333 bind_rdataset(search.rbtdb, node, found, search.now, rdataset);
3334 if (foundsig != NULL)
3335 bind_rdataset(search.rbtdb, node, foundsig, search.now,
3338 UNLOCK(&(search.rbtdb->node_locks[node->locknum].lock));
3341 RWUNLOCK(&search.rbtdb->tree_lock, isc_rwlocktype_read);
3343 INSIST(!search.need_cleanup);
3345 dns_rbtnodechain_reset(&search.chain);
3347 if (result == DNS_R_DELEGATION)
3348 result = ISC_R_SUCCESS;
3354 attachnode(dns_db_t *db, dns_dbnode_t *source, dns_dbnode_t **targetp) {
3355 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3356 dns_rbtnode_t *node = (dns_rbtnode_t *)source;
3358 REQUIRE(VALID_RBTDB(rbtdb));
3359 REQUIRE(targetp != NULL && *targetp == NULL);
3361 LOCK(&rbtdb->node_locks[node->locknum].lock);
3362 INSIST(node->references > 0);
3364 INSIST(node->references != 0); /* Catch overflow. */
3365 UNLOCK(&rbtdb->node_locks[node->locknum].lock);
3371 detachnode(dns_db_t *db, dns_dbnode_t **targetp) {
3372 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3373 dns_rbtnode_t *node;
3374 isc_boolean_t want_free = ISC_FALSE;
3375 isc_boolean_t inactive = ISC_FALSE;
3376 unsigned int locknum;
3378 REQUIRE(VALID_RBTDB(rbtdb));
3379 REQUIRE(targetp != NULL && *targetp != NULL);
3381 node = (dns_rbtnode_t *)(*targetp);
3382 locknum = node->locknum;
3384 LOCK(&rbtdb->node_locks[locknum].lock);
3386 INSIST(node->references > 0);
3388 if (node->references == 0) {
3389 no_references(rbtdb, node, 0, isc_rwlocktype_none);
3390 if (rbtdb->node_locks[locknum].references == 0 &&
3391 rbtdb->node_locks[locknum].exiting)
3392 inactive = ISC_TRUE;
3395 UNLOCK(&rbtdb->node_locks[locknum].lock);
3402 if (rbtdb->active == 0)
3403 want_free = ISC_TRUE;
3404 UNLOCK(&rbtdb->lock);
3406 char buf[DNS_NAME_FORMATSIZE];
3407 if (dns_name_dynamic(&rbtdb->common.origin))
3408 dns_name_format(&rbtdb->common.origin, buf,
3411 strcpy(buf, "<UNKNOWN>");
3412 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
3413 DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
3414 "calling free_rbtdb(%s)", buf);
3415 free_rbtdb(rbtdb, ISC_TRUE, NULL);
3421 expirenode(dns_db_t *db, dns_dbnode_t *node, isc_stdtime_t now) {
3422 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3423 dns_rbtnode_t *rbtnode = node;
3424 rdatasetheader_t *header;
3425 isc_boolean_t force_expire = ISC_FALSE;
3427 * These are the category and module used by the cache cleaner.
3429 isc_boolean_t log = ISC_FALSE;
3430 isc_logcategory_t *category = DNS_LOGCATEGORY_DATABASE;
3431 isc_logmodule_t *module = DNS_LOGMODULE_CACHE;
3432 int level = ISC_LOG_DEBUG(2);
3433 char printname[DNS_NAME_FORMATSIZE];
3435 REQUIRE(VALID_RBTDB(rbtdb));
3438 * Caller must hold a tree lock.
3442 isc_stdtime_get(&now);
3444 if (rbtdb->overmem) {
3447 isc_random_get(&val);
3449 * XXXDCL Could stand to have a better policy, like LRU.
3451 force_expire = ISC_TF(rbtnode->down == NULL && val % 4 == 0);
3454 * Note that 'log' can be true IFF rbtdb->overmem is also true.
3455 * rbtdb->ovemem can currently only be true for cache databases
3456 * -- hence all of the "overmem cache" log strings.
3458 log = ISC_TF(isc_log_wouldlog(dns_lctx, level));
3460 isc_log_write(dns_lctx, category, module, level,
3461 "overmem cache: %s %s",
3462 force_expire ? "FORCE" : "check",
3463 dns_rbt_formatnodename(rbtnode,
3465 sizeof(printname)));
3468 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3470 for (header = rbtnode->data; header != NULL; header = header->next)
3471 if (header->ttl <= now - RBTDB_VIRTUAL) {
3473 * We don't check if rbtnode->references == 0 and try
3474 * to free like we do in cache_find(), because
3475 * rbtnode->references must be non-zero. This is so
3476 * because 'node' is an argument to the function.
3478 header->attributes |= RDATASET_ATTR_STALE;
3481 isc_log_write(dns_lctx, category, module,
3482 level, "overmem cache: stale %s",
3484 } else if (force_expire) {
3485 if (! RETAIN(header)) {
3487 header->attributes |= RDATASET_ATTR_STALE;
3490 isc_log_write(dns_lctx, category, module,
3491 level, "overmem cache: "
3492 "reprieve by RETAIN() %s",
3495 } else if (rbtdb->overmem && log)
3496 isc_log_write(dns_lctx, category, module, level,
3497 "overmem cache: saved %s", printname);
3499 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3501 return (ISC_R_SUCCESS);
3505 overmem(dns_db_t *db, isc_boolean_t overmem) {
3506 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3508 if (IS_CACHE(rbtdb)) {
3509 rbtdb->overmem = overmem;
3514 printnode(dns_db_t *db, dns_dbnode_t *node, FILE *out) {
3515 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3516 dns_rbtnode_t *rbtnode = node;
3517 isc_boolean_t first;
3519 REQUIRE(VALID_RBTDB(rbtdb));
3521 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3523 fprintf(out, "node %p, %u references, locknum = %u\n",
3524 rbtnode, rbtnode->references, rbtnode->locknum);
3525 if (rbtnode->data != NULL) {
3526 rdatasetheader_t *current, *top_next;
3528 for (current = rbtnode->data; current != NULL;
3529 current = top_next) {
3530 top_next = current->next;
3532 fprintf(out, "\ttype %u", current->type);
3538 "\tserial = %lu, ttl = %u, "
3539 "trust = %u, attributes = %u\n",
3540 (unsigned long)current->serial,
3543 current->attributes);
3544 current = current->down;
3545 } while (current != NULL);
3548 fprintf(out, "(empty)\n");
3550 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3554 createiterator(dns_db_t *db, isc_boolean_t relative_names,
3555 dns_dbiterator_t **iteratorp)
3557 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3558 rbtdb_dbiterator_t *rbtdbiter;
3560 REQUIRE(VALID_RBTDB(rbtdb));
3562 rbtdbiter = isc_mem_get(rbtdb->common.mctx, sizeof(*rbtdbiter));
3563 if (rbtdbiter == NULL)
3564 return (ISC_R_NOMEMORY);
3566 rbtdbiter->common.methods = &dbiterator_methods;
3567 rbtdbiter->common.db = NULL;
3568 dns_db_attach(db, &rbtdbiter->common.db);
3569 rbtdbiter->common.relative_names = relative_names;
3570 rbtdbiter->common.magic = DNS_DBITERATOR_MAGIC;
3571 rbtdbiter->common.cleaning = ISC_FALSE;
3572 rbtdbiter->paused = ISC_TRUE;
3573 rbtdbiter->tree_locked = isc_rwlocktype_none;
3574 rbtdbiter->result = ISC_R_SUCCESS;
3575 dns_fixedname_init(&rbtdbiter->name);
3576 dns_fixedname_init(&rbtdbiter->origin);
3577 rbtdbiter->node = NULL;
3578 rbtdbiter->delete = 0;
3579 memset(rbtdbiter->deletions, 0, sizeof(rbtdbiter->deletions));
3580 dns_rbtnodechain_init(&rbtdbiter->chain, db->mctx);
3582 *iteratorp = (dns_dbiterator_t *)rbtdbiter;
3584 return (ISC_R_SUCCESS);
3588 zone_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3589 dns_rdatatype_t type, dns_rdatatype_t covers,
3590 isc_stdtime_t now, dns_rdataset_t *rdataset,
3591 dns_rdataset_t *sigrdataset)
3593 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3594 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3595 rdatasetheader_t *header, *header_next, *found, *foundsig;
3596 rbtdb_serial_t serial;
3597 rbtdb_version_t *rbtversion = version;
3598 isc_boolean_t close_version = ISC_FALSE;
3599 rbtdb_rdatatype_t matchtype, sigmatchtype;
3601 REQUIRE(VALID_RBTDB(rbtdb));
3602 REQUIRE(type != dns_rdatatype_any);
3604 if (rbtversion == NULL) {
3605 currentversion(db, (dns_dbversion_t **) (void *)(&rbtversion));
3606 close_version = ISC_TRUE;
3608 serial = rbtversion->serial;
3611 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3615 matchtype = RBTDB_RDATATYPE_VALUE(type, covers);
3617 sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
3621 for (header = rbtnode->data; header != NULL; header = header_next) {
3622 header_next = header->next;
3624 if (header->serial <= serial &&
3627 * Is this a "this rdataset doesn't
3630 if (NONEXISTENT(header))
3634 header = header->down;
3635 } while (header != NULL);
3636 if (header != NULL) {
3638 * We have an active, extant rdataset. If it's a
3639 * type we're looking for, remember it.
3641 if (header->type == matchtype) {
3643 if (foundsig != NULL)
3645 } else if (header->type == sigmatchtype) {
3652 if (found != NULL) {
3653 bind_rdataset(rbtdb, rbtnode, found, now, rdataset);
3654 if (foundsig != NULL)
3655 bind_rdataset(rbtdb, rbtnode, foundsig, now,
3659 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3662 closeversion(db, (dns_dbversion_t **) (void *)(&rbtversion),
3666 return (ISC_R_NOTFOUND);
3668 return (ISC_R_SUCCESS);
3672 cache_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3673 dns_rdatatype_t type, dns_rdatatype_t covers,
3674 isc_stdtime_t now, dns_rdataset_t *rdataset,
3675 dns_rdataset_t *sigrdataset)
3677 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3678 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3679 rdatasetheader_t *header, *header_next, *found, *foundsig;
3680 rbtdb_rdatatype_t matchtype, sigmatchtype, negtype;
3681 isc_result_t result;
3683 REQUIRE(VALID_RBTDB(rbtdb));
3684 REQUIRE(type != dns_rdatatype_any);
3688 result = ISC_R_SUCCESS;
3691 isc_stdtime_get(&now);
3693 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3697 matchtype = RBTDB_RDATATYPE_VALUE(type, covers);
3698 negtype = RBTDB_RDATATYPE_VALUE(0, type);
3700 sigmatchtype = RBTDB_RDATATYPE_VALUE(dns_rdatatype_rrsig, type);
3704 for (header = rbtnode->data; header != NULL; header = header_next) {
3705 header_next = header->next;
3706 if (header->ttl <= now) {
3708 * We don't check if rbtnode->references == 0 and try
3709 * to free like we do in cache_find(), because
3710 * rbtnode->references must be non-zero. This is so
3711 * because 'node' is an argument to the function.
3713 if (header->ttl <= now - RBTDB_VIRTUAL) {
3714 header->attributes |= RDATASET_ATTR_STALE;
3717 } else if (EXISTS(header)) {
3718 if (header->type == matchtype)
3720 else if (header->type == RBTDB_RDATATYPE_NCACHEANY ||
3721 header->type == negtype)
3723 else if (header->type == sigmatchtype)
3727 if (found != NULL) {
3728 bind_rdataset(rbtdb, rbtnode, found, now, rdataset);
3729 if (foundsig != NULL)
3730 bind_rdataset(rbtdb, rbtnode, foundsig, now,
3734 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3737 return (ISC_R_NOTFOUND);
3739 if (RBTDB_RDATATYPE_BASE(found->type) == 0) {
3741 * We found a negative cache entry.
3743 if (NXDOMAIN(found))
3744 result = DNS_R_NCACHENXDOMAIN;
3746 result = DNS_R_NCACHENXRRSET;
3753 allrdatasets(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
3754 isc_stdtime_t now, dns_rdatasetiter_t **iteratorp)
3756 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
3757 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
3758 rbtdb_version_t *rbtversion = version;
3759 rbtdb_rdatasetiter_t *iterator;
3761 REQUIRE(VALID_RBTDB(rbtdb));
3763 iterator = isc_mem_get(rbtdb->common.mctx, sizeof(*iterator));
3764 if (iterator == NULL)
3765 return (ISC_R_NOMEMORY);
3767 if ((db->attributes & DNS_DBATTR_CACHE) == 0) {
3769 if (rbtversion == NULL)
3771 (dns_dbversion_t **) (void *)(&rbtversion));
3774 INSIST(rbtversion->references > 0);
3775 rbtversion->references++;
3776 INSIST(rbtversion->references != 0);
3777 UNLOCK(&rbtdb->lock);
3781 isc_stdtime_get(&now);
3785 iterator->common.magic = DNS_RDATASETITER_MAGIC;
3786 iterator->common.methods = &rdatasetiter_methods;
3787 iterator->common.db = db;
3788 iterator->common.node = node;
3789 iterator->common.version = (dns_dbversion_t *)rbtversion;
3790 iterator->common.now = now;
3792 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3794 INSIST(rbtnode->references > 0);
3795 rbtnode->references++;
3796 INSIST(rbtnode->references != 0);
3797 iterator->current = NULL;
3799 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
3801 *iteratorp = (dns_rdatasetiter_t *)iterator;
3803 return (ISC_R_SUCCESS);
3806 static isc_boolean_t
3807 cname_and_other_data(dns_rbtnode_t *node, rbtdb_serial_t serial) {
3808 rdatasetheader_t *header, *header_next;
3809 isc_boolean_t cname, other_data;
3810 dns_rdatatype_t rdtype;
3813 * The caller must hold the node lock.
3817 * Look for CNAME and "other data" rdatasets active in our version.
3820 other_data = ISC_FALSE;
3821 for (header = node->data; header != NULL; header = header_next) {
3822 header_next = header->next;
3823 if (header->type == dns_rdatatype_cname) {
3825 * Look for an active extant CNAME.
3828 if (header->serial <= serial &&
3831 * Is this a "this rdataset doesn't
3834 if (NONEXISTENT(header))
3838 header = header->down;
3839 } while (header != NULL);
3844 * Look for active extant "other data".
3846 * "Other data" is any rdataset whose type is not
3847 * KEY, RRSIG KEY, NSEC, RRSIG NSEC or RRSIG CNAME.
3849 rdtype = RBTDB_RDATATYPE_BASE(header->type);
3850 if (rdtype == dns_rdatatype_rrsig ||
3851 rdtype == dns_rdatatype_sig)
3852 rdtype = RBTDB_RDATATYPE_EXT(header->type);
3853 if (rdtype != dns_rdatatype_nsec &&
3854 rdtype != dns_rdatatype_key &&
3855 rdtype != dns_rdatatype_cname) {
3857 * We've found a type that isn't
3858 * NSEC, KEY, CNAME, or one of their
3859 * signatures. Is it active and extant?
3862 if (header->serial <= serial &&
3865 * Is this a "this rdataset
3866 * doesn't exist" record?
3868 if (NONEXISTENT(header))
3872 header = header->down;
3873 } while (header != NULL);
3875 other_data = ISC_TRUE;
3880 if (cname && other_data)
3887 add(dns_rbtdb_t *rbtdb, dns_rbtnode_t *rbtnode, rbtdb_version_t *rbtversion,
3888 rdatasetheader_t *newheader, unsigned int options, isc_boolean_t loading,
3889 dns_rdataset_t *addedrdataset, isc_stdtime_t now)
3891 rbtdb_changed_t *changed = NULL;
3892 rdatasetheader_t *topheader, *topheader_prev, *header;
3893 unsigned char *merged;
3894 isc_result_t result;
3895 isc_boolean_t header_nx;
3896 isc_boolean_t newheader_nx;
3897 isc_boolean_t merge;
3898 dns_rdatatype_t rdtype, covers;
3899 rbtdb_rdatatype_t negtype;
3903 * Add an rdatasetheader_t to a node.
3907 * Caller must be holding the node lock.
3910 if ((options & DNS_DBADD_MERGE) != 0) {
3911 REQUIRE(rbtversion != NULL);
3916 if ((options & DNS_DBADD_FORCE) != 0)
3917 trust = dns_trust_ultimate;
3919 trust = newheader->trust;
3921 if (rbtversion != NULL && !loading) {
3923 * We always add a changed record, even if no changes end up
3924 * being made to this node, because it's harmless and
3925 * simplifies the code.
3927 changed = add_changed(rbtdb, rbtversion, rbtnode);
3928 if (changed == NULL) {
3929 free_rdataset(rbtdb->common.mctx, newheader);
3930 return (ISC_R_NOMEMORY);
3934 newheader_nx = NONEXISTENT(newheader) ? ISC_TRUE : ISC_FALSE;
3935 topheader_prev = NULL;
3938 if (rbtversion == NULL && !newheader_nx) {
3939 rdtype = RBTDB_RDATATYPE_BASE(newheader->type);
3942 * We're adding a negative cache entry.
3944 covers = RBTDB_RDATATYPE_EXT(newheader->type);
3945 if (covers == dns_rdatatype_any) {
3947 * We're adding an negative cache entry
3948 * which covers all types (NXDOMAIN,
3949 * NODATA(QTYPE=ANY)).
3951 * We make all other data stale so that the
3952 * only rdataset that can be found at this
3953 * node is the negative cache entry.
3955 for (topheader = rbtnode->data;
3957 topheader = topheader->next) {
3959 topheader->attributes |=
3960 RDATASET_ATTR_STALE;
3965 negtype = RBTDB_RDATATYPE_VALUE(covers, 0);
3968 * We're adding something that isn't a
3969 * negative cache entry. Look for an extant
3970 * non-stale NXDOMAIN/NODATA(QTYPE=ANY) negative
3973 for (topheader = rbtnode->data;
3975 topheader = topheader->next) {
3976 if (topheader->type ==
3977 RBTDB_RDATATYPE_NCACHEANY)
3980 if (topheader != NULL && EXISTS(topheader) &&
3981 topheader->ttl > now) {
3985 if (trust < topheader->trust) {
3987 * The NXDOMAIN/NODATA(QTYPE=ANY)
3990 free_rdataset(rbtdb->common.mctx,
3992 if (addedrdataset != NULL)
3993 bind_rdataset(rbtdb, rbtnode,
3996 return (DNS_R_UNCHANGED);
3999 * The new rdataset is better. Expire the
4000 * NXDOMAIN/NODATA(QTYPE=ANY).
4003 topheader->attributes |= RDATASET_ATTR_STALE;
4008 negtype = RBTDB_RDATATYPE_VALUE(0, rdtype);
4012 for (topheader = rbtnode->data;
4014 topheader = topheader->next) {
4015 if (topheader->type == newheader->type ||
4016 topheader->type == negtype)
4018 topheader_prev = topheader;
4023 * If header isn't NULL, we've found the right type. There may be
4024 * IGNORE rdatasets between the top of the chain and the first real
4025 * data. We skip over them.
4028 while (header != NULL && IGNORE(header))
4029 header = header->down;
4030 if (header != NULL) {
4031 header_nx = NONEXISTENT(header) ? ISC_TRUE : ISC_FALSE;
4034 * Deleting an already non-existent rdataset has no effect.
4036 if (header_nx && newheader_nx) {
4037 free_rdataset(rbtdb->common.mctx, newheader);
4038 return (DNS_R_UNCHANGED);
4042 * Trying to add an rdataset with lower trust to a cache DB
4043 * has no effect, provided that the cache data isn't stale.
4045 if (rbtversion == NULL && trust < header->trust &&
4046 (header->ttl > now || header_nx)) {
4047 free_rdataset(rbtdb->common.mctx, newheader);
4048 if (addedrdataset != NULL)
4049 bind_rdataset(rbtdb, rbtnode, header, now,
4051 return (DNS_R_UNCHANGED);
4055 * Don't merge if a nonexistent rdataset is involved.
4057 if (merge && (header_nx || newheader_nx))
4061 * If 'merge' is ISC_TRUE, we'll try to create a new rdataset
4062 * that is the union of 'newheader' and 'header'.
4065 unsigned int flags = 0;
4066 INSIST(rbtversion->serial >= header->serial);
4068 result = ISC_R_SUCCESS;
4070 if ((options & DNS_DBADD_EXACT) != 0)
4071 flags |= DNS_RDATASLAB_EXACT;
4072 if ((options & DNS_DBADD_EXACTTTL) != 0 &&
4073 newheader->ttl != header->ttl)
4074 result = DNS_R_NOTEXACT;
4075 else if (newheader->ttl != header->ttl)
4076 flags |= DNS_RDATASLAB_FORCE;
4077 if (result == ISC_R_SUCCESS)
4078 result = dns_rdataslab_merge(
4079 (unsigned char *)header,
4080 (unsigned char *)newheader,
4081 (unsigned int)(sizeof(*newheader)),
4083 rbtdb->common.rdclass,
4084 (dns_rdatatype_t)header->type,
4086 if (result == ISC_R_SUCCESS) {
4088 * If 'header' has the same serial number as
4089 * we do, we could clean it up now if we knew
4090 * that our caller had no references to it.
4091 * We don't know this, however, so we leave it
4092 * alone. It will get cleaned up when
4093 * clean_zone_node() runs.
4095 free_rdataset(rbtdb->common.mctx, newheader);
4096 newheader = (rdatasetheader_t *)merged;
4098 free_rdataset(rbtdb->common.mctx, newheader);
4103 * Don't replace existing NS, A and AAAA RRsets
4104 * in the cache if they are already exist. This
4105 * prevents named being locked to old servers.
4106 * Don't lower trust of existing record if the
4109 if (IS_CACHE(rbtdb) && header->ttl > now &&
4110 header->type == dns_rdatatype_ns &&
4111 !header_nx && !newheader_nx &&
4112 header->trust >= newheader->trust &&
4113 dns_rdataslab_equalx((unsigned char *)header,
4114 (unsigned char *)newheader,
4115 (unsigned int)(sizeof(*newheader)),
4116 rbtdb->common.rdclass,
4117 (dns_rdatatype_t)header->type)) {
4119 * Honour the new ttl if it is less than the
4122 if (header->ttl > newheader->ttl)
4123 header->ttl = newheader->ttl;
4124 if (header->noqname == NULL &&
4125 newheader->noqname != NULL) {
4126 header->noqname = newheader->noqname;
4127 newheader->noqname = NULL;
4129 free_rdataset(rbtdb->common.mctx, newheader);
4130 if (addedrdataset != NULL)
4131 bind_rdataset(rbtdb, rbtnode, header, now,
4133 return (ISC_R_SUCCESS);
4135 if (IS_CACHE(rbtdb) && header->ttl > now &&
4136 (header->type == dns_rdatatype_a ||
4137 header->type == dns_rdatatype_aaaa) &&
4138 !header_nx && !newheader_nx &&
4139 header->trust >= newheader->trust &&
4140 dns_rdataslab_equal((unsigned char *)header,
4141 (unsigned char *)newheader,
4142 (unsigned int)(sizeof(*newheader)))) {
4144 * Honour the new ttl if it is less than the
4147 if (header->ttl > newheader->ttl)
4148 header->ttl = newheader->ttl;
4149 if (header->noqname == NULL &&
4150 newheader->noqname != NULL) {
4151 header->noqname = newheader->noqname;
4152 newheader->noqname = NULL;
4154 free_rdataset(rbtdb->common.mctx, newheader);
4155 if (addedrdataset != NULL)
4156 bind_rdataset(rbtdb, rbtnode, header, now,
4158 return (ISC_R_SUCCESS);
4160 INSIST(rbtversion == NULL ||
4161 rbtversion->serial >= topheader->serial);
4162 if (topheader_prev != NULL)
4163 topheader_prev->next = newheader;
4165 rbtnode->data = newheader;
4166 newheader->next = topheader->next;
4169 * There are no other references to 'header' when
4170 * loading, so we MAY clean up 'header' now.
4171 * Since we don't generate changed records when
4172 * loading, we MUST clean up 'header' now.
4174 newheader->down = NULL;
4175 free_rdataset(rbtdb->common.mctx, header);
4177 newheader->down = topheader;
4178 topheader->next = newheader;
4180 if (changed != NULL)
4181 changed->dirty = ISC_TRUE;
4182 if (rbtversion == NULL) {
4184 header->attributes |= RDATASET_ATTR_STALE;
4189 * No non-IGNORED rdatasets of the given type exist at
4194 * If we're trying to delete the type, don't bother.
4197 free_rdataset(rbtdb->common.mctx, newheader);
4198 return (DNS_R_UNCHANGED);
4201 if (topheader != NULL) {
4203 * We have an list of rdatasets of the given type,
4204 * but they're all marked IGNORE. We simply insert
4205 * the new rdataset at the head of the list.
4207 * Ignored rdatasets cannot occur during loading, so
4211 INSIST(rbtversion == NULL ||
4212 rbtversion->serial >= topheader->serial);
4213 if (topheader_prev != NULL)
4214 topheader_prev->next = newheader;
4216 rbtnode->data = newheader;
4217 newheader->next = topheader->next;
4218 newheader->down = topheader;
4219 topheader->next = newheader;
4221 if (changed != NULL)
4222 changed->dirty = ISC_TRUE;
4225 * No rdatasets of the given type exist at the node.
4227 newheader->next = rbtnode->data;
4228 newheader->down = NULL;
4229 rbtnode->data = newheader;
4234 * Check if the node now contains CNAME and other data.
4236 if (rbtversion != NULL &&
4237 cname_and_other_data(rbtnode, rbtversion->serial))
4238 return (DNS_R_CNAMEANDOTHER);
4240 if (addedrdataset != NULL)
4241 bind_rdataset(rbtdb, rbtnode, newheader, now, addedrdataset);
4243 return (ISC_R_SUCCESS);
4246 static inline isc_boolean_t
4247 delegating_type(dns_rbtdb_t *rbtdb, dns_rbtnode_t *node,
4248 rbtdb_rdatatype_t type)
4250 if (IS_CACHE(rbtdb)) {
4251 if (type == dns_rdatatype_dname)
4255 } else if (type == dns_rdatatype_dname ||
4256 (type == dns_rdatatype_ns &&
4257 (node != rbtdb->origin_node || IS_STUB(rbtdb))))
4262 static inline isc_result_t
4263 addnoqname(dns_rbtdb_t *rbtdb, rdatasetheader_t *newheader,
4264 dns_rdataset_t *rdataset)
4266 struct noqname *noqname;
4267 isc_mem_t *mctx = rbtdb->common.mctx;
4269 dns_rdataset_t nsec, nsecsig;
4270 isc_result_t result;
4273 dns_name_init(&name, NULL);
4274 dns_rdataset_init(&nsec);
4275 dns_rdataset_init(&nsecsig);
4277 result = dns_rdataset_getnoqname(rdataset, &name, &nsec, &nsecsig);
4278 RUNTIME_CHECK(result == ISC_R_SUCCESS);
4280 noqname = isc_mem_get(mctx, sizeof(*noqname));
4281 if (noqname == NULL) {
4282 result = ISC_R_NOMEMORY;
4285 dns_name_init(&noqname->name, NULL);
4286 noqname->nsec = NULL;
4287 noqname->nsecsig = NULL;
4288 result = dns_name_dup(&name, mctx, &noqname->name);
4289 if (result != ISC_R_SUCCESS)
4291 result = dns_rdataslab_fromrdataset(&nsec, mctx, &r, 0);
4292 if (result != ISC_R_SUCCESS)
4294 noqname->nsec = r.base;
4295 result = dns_rdataslab_fromrdataset(&nsecsig, mctx, &r, 0);
4296 if (result != ISC_R_SUCCESS)
4298 noqname->nsecsig = r.base;
4299 dns_rdataset_disassociate(&nsec);
4300 dns_rdataset_disassociate(&nsecsig);
4301 newheader->noqname = noqname;
4302 return (ISC_R_SUCCESS);
4305 dns_rdataset_disassociate(&nsec);
4306 dns_rdataset_disassociate(&nsecsig);
4307 free_noqname(mctx, &noqname);
4312 addrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4313 isc_stdtime_t now, dns_rdataset_t *rdataset, unsigned int options,
4314 dns_rdataset_t *addedrdataset)
4316 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4317 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4318 rbtdb_version_t *rbtversion = version;
4319 isc_region_t region;
4320 rdatasetheader_t *newheader;
4321 isc_result_t result;
4322 isc_boolean_t delegating;
4324 REQUIRE(VALID_RBTDB(rbtdb));
4326 if (rbtversion == NULL) {
4328 isc_stdtime_get(&now);
4332 result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4334 sizeof(rdatasetheader_t));
4335 if (result != ISC_R_SUCCESS)
4338 newheader = (rdatasetheader_t *)region.base;
4339 newheader->ttl = rdataset->ttl + now;
4340 newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4342 newheader->attributes = 0;
4343 newheader->noqname = NULL;
4344 newheader->count = 0;
4345 newheader->trust = rdataset->trust;
4346 if (rbtversion != NULL) {
4347 newheader->serial = rbtversion->serial;
4350 newheader->serial = 1;
4351 if ((rdataset->attributes & DNS_RDATASETATTR_NXDOMAIN) != 0)
4352 newheader->attributes |= RDATASET_ATTR_NXDOMAIN;
4353 if ((rdataset->attributes & DNS_RDATASETATTR_NOQNAME) != 0) {
4354 result = addnoqname(rbtdb, newheader, rdataset);
4355 if (result != ISC_R_SUCCESS) {
4356 free_rdataset(rbtdb->common.mctx, newheader);
4363 * If we're adding a delegation type (e.g. NS or DNAME for a zone,
4364 * just DNAME for the cache), then we need to set the callback bit
4365 * on the node, and to do that we must be holding an exclusive lock
4368 if (delegating_type(rbtdb, rbtnode, rdataset->type)) {
4369 delegating = ISC_TRUE;
4370 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
4372 delegating = ISC_FALSE;
4374 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4376 result = add(rbtdb, rbtnode, rbtversion, newheader, options, ISC_FALSE,
4377 addedrdataset, now);
4378 if (result == ISC_R_SUCCESS && delegating)
4379 rbtnode->find_callback = 1;
4381 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4384 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
4387 * Update the zone's secure status. If version is non-NULL
4388 * this is defered until closeversion() is called.
4390 if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4391 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4397 subtractrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4398 dns_rdataset_t *rdataset, unsigned int options,
4399 dns_rdataset_t *newrdataset)
4401 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4402 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4403 rbtdb_version_t *rbtversion = version;
4404 rdatasetheader_t *topheader, *topheader_prev, *header, *newheader;
4405 unsigned char *subresult;
4406 isc_region_t region;
4407 isc_result_t result;
4408 rbtdb_changed_t *changed;
4410 REQUIRE(VALID_RBTDB(rbtdb));
4412 result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4414 sizeof(rdatasetheader_t));
4415 if (result != ISC_R_SUCCESS)
4417 newheader = (rdatasetheader_t *)region.base;
4418 newheader->ttl = rdataset->ttl;
4419 newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4421 newheader->attributes = 0;
4422 newheader->serial = rbtversion->serial;
4423 newheader->trust = 0;
4424 newheader->noqname = NULL;
4425 newheader->count = 0;
4427 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4429 changed = add_changed(rbtdb, rbtversion, rbtnode);
4430 if (changed == NULL) {
4431 free_rdataset(rbtdb->common.mctx, newheader);
4432 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4433 return (ISC_R_NOMEMORY);
4436 topheader_prev = NULL;
4437 for (topheader = rbtnode->data;
4439 topheader = topheader->next) {
4440 if (topheader->type == newheader->type)
4442 topheader_prev = topheader;
4445 * If header isn't NULL, we've found the right type. There may be
4446 * IGNORE rdatasets between the top of the chain and the first real
4447 * data. We skip over them.
4450 while (header != NULL && IGNORE(header))
4451 header = header->down;
4452 if (header != NULL && EXISTS(header)) {
4453 unsigned int flags = 0;
4455 result = ISC_R_SUCCESS;
4456 if ((options & DNS_DBSUB_EXACT) != 0) {
4457 flags |= DNS_RDATASLAB_EXACT;
4458 if (newheader->ttl != header->ttl)
4459 result = DNS_R_NOTEXACT;
4461 if (result == ISC_R_SUCCESS)
4462 result = dns_rdataslab_subtract(
4463 (unsigned char *)header,
4464 (unsigned char *)newheader,
4465 (unsigned int)(sizeof(*newheader)),
4467 rbtdb->common.rdclass,
4468 (dns_rdatatype_t)header->type,
4470 if (result == ISC_R_SUCCESS) {
4471 free_rdataset(rbtdb->common.mctx, newheader);
4472 newheader = (rdatasetheader_t *)subresult;
4474 * We have to set the serial since the rdataslab
4475 * subtraction routine copies the reserved portion of
4476 * header, not newheader.
4478 newheader->serial = rbtversion->serial;
4479 } else if (result == DNS_R_NXRRSET) {
4481 * This subtraction would remove all of the rdata;
4482 * add a nonexistent header instead.
4484 free_rdataset(rbtdb->common.mctx, newheader);
4485 newheader = isc_mem_get(rbtdb->common.mctx,
4486 sizeof(*newheader));
4487 if (newheader == NULL) {
4488 result = ISC_R_NOMEMORY;
4492 newheader->type = topheader->type;
4493 newheader->attributes = RDATASET_ATTR_NONEXISTENT;
4494 newheader->trust = 0;
4495 newheader->serial = rbtversion->serial;
4496 newheader->noqname = NULL;
4497 newheader->count = 0;
4499 free_rdataset(rbtdb->common.mctx, newheader);
4504 * If we're here, we want to link newheader in front of
4507 INSIST(rbtversion->serial >= topheader->serial);
4508 if (topheader_prev != NULL)
4509 topheader_prev->next = newheader;
4511 rbtnode->data = newheader;
4512 newheader->next = topheader->next;
4513 newheader->down = topheader;
4514 topheader->next = newheader;
4516 changed->dirty = ISC_TRUE;
4519 * The rdataset doesn't exist, so we don't need to do anything
4520 * to satisfy the deletion request.
4522 free_rdataset(rbtdb->common.mctx, newheader);
4523 if ((options & DNS_DBSUB_EXACT) != 0)
4524 result = DNS_R_NOTEXACT;
4526 result = DNS_R_UNCHANGED;
4529 if (result == ISC_R_SUCCESS && newrdataset != NULL)
4530 bind_rdataset(rbtdb, rbtnode, newheader, 0, newrdataset);
4533 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4536 * Update the zone's secure status. If version is non-NULL
4537 * this is defered until closeversion() is called.
4539 if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4540 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4546 deleterdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
4547 dns_rdatatype_t type, dns_rdatatype_t covers)
4549 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4550 dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
4551 rbtdb_version_t *rbtversion = version;
4552 isc_result_t result;
4553 rdatasetheader_t *newheader;
4555 REQUIRE(VALID_RBTDB(rbtdb));
4557 if (type == dns_rdatatype_any)
4558 return (ISC_R_NOTIMPLEMENTED);
4559 if (type == dns_rdatatype_rrsig && covers == 0)
4560 return (ISC_R_NOTIMPLEMENTED);
4562 newheader = isc_mem_get(rbtdb->common.mctx, sizeof(*newheader));
4563 if (newheader == NULL)
4564 return (ISC_R_NOMEMORY);
4566 newheader->type = RBTDB_RDATATYPE_VALUE(type, covers);
4567 newheader->attributes = RDATASET_ATTR_NONEXISTENT;
4568 newheader->trust = 0;
4569 newheader->noqname = NULL;
4570 if (rbtversion != NULL)
4571 newheader->serial = rbtversion->serial;
4573 newheader->serial = 0;
4574 newheader->count = 0;
4576 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4578 result = add(rbtdb, rbtnode, rbtversion, newheader, DNS_DBADD_FORCE,
4579 ISC_FALSE, NULL, 0);
4581 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
4584 * Update the zone's secure status. If version is non-NULL
4585 * this is defered until closeversion() is called.
4587 if (result == ISC_R_SUCCESS && version == NULL && !IS_CACHE(rbtdb))
4588 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4594 loading_addrdataset(void *arg, dns_name_t *name, dns_rdataset_t *rdataset) {
4595 rbtdb_load_t *loadctx = arg;
4596 dns_rbtdb_t *rbtdb = loadctx->rbtdb;
4597 dns_rbtnode_t *node;
4598 isc_result_t result;
4599 isc_region_t region;
4600 rdatasetheader_t *newheader;
4603 * This routine does no node locking. See comments in
4604 * 'load' below for more information on loading and
4610 * SOA records are only allowed at top of zone.
4612 if (rdataset->type == dns_rdatatype_soa &&
4613 !IS_CACHE(rbtdb) && !dns_name_equal(name, &rbtdb->common.origin))
4614 return (DNS_R_NOTZONETOP);
4616 add_empty_wildcards(rbtdb, name);
4618 if (dns_name_iswildcard(name)) {
4620 * NS record owners cannot legally be wild cards.
4622 if (rdataset->type == dns_rdatatype_ns)
4623 return (DNS_R_INVALIDNS);
4624 result = add_wildcard_magic(rbtdb, name);
4625 if (result != ISC_R_SUCCESS)
4630 result = dns_rbt_addnode(rbtdb->tree, name, &node);
4631 if (result != ISC_R_SUCCESS && result != ISC_R_EXISTS)
4633 if (result != ISC_R_EXISTS) {
4634 dns_name_t foundname;
4635 dns_name_init(&foundname, NULL);
4636 dns_rbt_namefromnode(node, &foundname);
4637 #ifdef DNS_RBT_USEHASH
4638 node->locknum = node->hashval % rbtdb->node_lock_count;
4640 node->locknum = dns_name_hash(&foundname, ISC_TRUE) %
4641 rbtdb->node_lock_count;
4645 result = dns_rdataslab_fromrdataset(rdataset, rbtdb->common.mctx,
4647 sizeof(rdatasetheader_t));
4648 if (result != ISC_R_SUCCESS)
4650 newheader = (rdatasetheader_t *)region.base;
4651 newheader->ttl = rdataset->ttl + loadctx->now; /* XXX overflow check */
4652 newheader->type = RBTDB_RDATATYPE_VALUE(rdataset->type,
4654 newheader->attributes = 0;
4655 newheader->trust = rdataset->trust;
4656 newheader->serial = 1;
4657 newheader->noqname = NULL;
4658 newheader->count = 0;
4660 result = add(rbtdb, node, rbtdb->current_version, newheader,
4661 DNS_DBADD_MERGE, ISC_TRUE, NULL, 0);
4662 if (result == ISC_R_SUCCESS &&
4663 delegating_type(rbtdb, node, rdataset->type))
4664 node->find_callback = 1;
4665 else if (result == DNS_R_UNCHANGED)
4666 result = ISC_R_SUCCESS;
4672 beginload(dns_db_t *db, dns_addrdatasetfunc_t *addp, dns_dbload_t **dbloadp) {
4673 rbtdb_load_t *loadctx;
4676 rbtdb = (dns_rbtdb_t *)db;
4678 REQUIRE(VALID_RBTDB(rbtdb));
4680 loadctx = isc_mem_get(rbtdb->common.mctx, sizeof(*loadctx));
4681 if (loadctx == NULL)
4682 return (ISC_R_NOMEMORY);
4684 loadctx->rbtdb = rbtdb;
4685 if (IS_CACHE(rbtdb))
4686 isc_stdtime_get(&loadctx->now);
4692 REQUIRE((rbtdb->attributes & (RBTDB_ATTR_LOADED|RBTDB_ATTR_LOADING))
4694 rbtdb->attributes |= RBTDB_ATTR_LOADING;
4696 UNLOCK(&rbtdb->lock);
4698 *addp = loading_addrdataset;
4701 return (ISC_R_SUCCESS);
4705 endload(dns_db_t *db, dns_dbload_t **dbloadp) {
4706 rbtdb_load_t *loadctx;
4707 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
4709 REQUIRE(VALID_RBTDB(rbtdb));
4710 REQUIRE(dbloadp != NULL);
4712 REQUIRE(loadctx->rbtdb == rbtdb);
4716 REQUIRE((rbtdb->attributes & RBTDB_ATTR_LOADING) != 0);
4717 REQUIRE((rbtdb->attributes & RBTDB_ATTR_LOADED) == 0);
4719 rbtdb->attributes &= ~RBTDB_ATTR_LOADING;
4720 rbtdb->attributes |= RBTDB_ATTR_LOADED;
4722 UNLOCK(&rbtdb->lock);
4725 * If there's a KEY rdataset at the zone origin containing a
4726 * zone key, we consider the zone secure.
4728 if (! IS_CACHE(rbtdb))
4729 rbtdb->secure = iszonesecure(db, rbtdb->origin_node);
4733 isc_mem_put(rbtdb->common.mctx, loadctx, sizeof(*loadctx));
4735 return (ISC_R_SUCCESS);
4739 dump(dns_db_t *db, dns_dbversion_t *version, const char *filename) {
4742 rbtdb = (dns_rbtdb_t *)db;
4744 REQUIRE(VALID_RBTDB(rbtdb));
4746 return (dns_master_dump(rbtdb->common.mctx, db, version,
4747 &dns_master_style_default,
4752 delete_callback(void *data, void *arg) {
4753 dns_rbtdb_t *rbtdb = arg;
4754 rdatasetheader_t *current, *next;
4756 for (current = data; current != NULL; current = next) {
4757 next = current->next;
4758 free_rdataset(rbtdb->common.mctx, current);
4762 static isc_boolean_t
4763 issecure(dns_db_t *db) {
4765 isc_boolean_t secure;
4767 rbtdb = (dns_rbtdb_t *)db;
4769 REQUIRE(VALID_RBTDB(rbtdb));
4771 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4772 secure = rbtdb->secure;
4773 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4779 nodecount(dns_db_t *db) {
4783 rbtdb = (dns_rbtdb_t *)db;
4785 REQUIRE(VALID_RBTDB(rbtdb));
4787 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4788 count = dns_rbt_nodecount(rbtdb->tree);
4789 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
4795 settask(dns_db_t *db, isc_task_t *task) {
4798 rbtdb = (dns_rbtdb_t *)db;
4800 REQUIRE(VALID_RBTDB(rbtdb));
4803 if (rbtdb->task != NULL)
4804 isc_task_detach(&rbtdb->task);
4806 isc_task_attach(task, &rbtdb->task);
4807 UNLOCK(&rbtdb->lock);
4810 static isc_boolean_t
4811 ispersistent(dns_db_t *db) {
4816 static dns_dbmethods_t zone_methods = {
4846 static dns_dbmethods_t cache_methods = {
4877 #ifdef DNS_RBTDB_VERSION64
4882 (isc_mem_t *mctx, dns_name_t *origin, dns_dbtype_t type,
4883 dns_rdataclass_t rdclass, unsigned int argc, char *argv[],
4884 void *driverarg, dns_db_t **dbp)
4887 isc_result_t result;
4891 /* Keep the compiler happy. */
4896 rbtdb = isc_mem_get(mctx, sizeof(*rbtdb));
4898 return (ISC_R_NOMEMORY);
4899 memset(rbtdb, '\0', sizeof(*rbtdb));
4900 dns_name_init(&rbtdb->common.origin, NULL);
4901 rbtdb->common.attributes = 0;
4902 if (type == dns_dbtype_cache) {
4903 rbtdb->common.methods = &cache_methods;
4904 rbtdb->common.attributes |= DNS_DBATTR_CACHE;
4905 } else if (type == dns_dbtype_stub) {
4906 rbtdb->common.methods = &zone_methods;
4907 rbtdb->common.attributes |= DNS_DBATTR_STUB;
4909 rbtdb->common.methods = &zone_methods;
4910 rbtdb->common.rdclass = rdclass;
4911 rbtdb->common.mctx = NULL;
4913 result = isc_mutex_init(&rbtdb->lock);
4914 if (result != ISC_R_SUCCESS) {
4915 isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4916 UNEXPECTED_ERROR(__FILE__, __LINE__,
4917 "isc_mutex_init() failed: %s",
4918 isc_result_totext(result));
4919 return (ISC_R_UNEXPECTED);
4922 result = isc_rwlock_init(&rbtdb->tree_lock, 0, 0);
4923 if (result != ISC_R_SUCCESS) {
4924 DESTROYLOCK(&rbtdb->lock);
4925 isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4926 UNEXPECTED_ERROR(__FILE__, __LINE__,
4927 "isc_rwlock_init() failed: %s",
4928 isc_result_totext(result));
4929 return (ISC_R_UNEXPECTED);
4932 INSIST(rbtdb->node_lock_count < (1 << DNS_RBT_LOCKLENGTH));
4934 if (rbtdb->node_lock_count == 0)
4935 rbtdb->node_lock_count = DEFAULT_NODE_LOCK_COUNT;
4936 rbtdb->node_locks = isc_mem_get(mctx, rbtdb->node_lock_count *
4937 sizeof(rbtdb_nodelock_t));
4938 rbtdb->active = rbtdb->node_lock_count;
4939 for (i = 0; i < (int)(rbtdb->node_lock_count); i++) {
4940 result = isc_mutex_init(&rbtdb->node_locks[i].lock);
4941 if (result != ISC_R_SUCCESS) {
4944 DESTROYLOCK(&rbtdb->node_locks[i].lock);
4947 isc_mem_put(mctx, rbtdb->node_locks,
4948 rbtdb->node_lock_count *
4949 sizeof(rbtdb_nodelock_t));
4950 isc_rwlock_destroy(&rbtdb->tree_lock);
4951 DESTROYLOCK(&rbtdb->lock);
4952 isc_mem_put(mctx, rbtdb, sizeof(*rbtdb));
4953 UNEXPECTED_ERROR(__FILE__, __LINE__,
4954 "isc_mutex_init() failed: %s",
4955 isc_result_totext(result));
4956 return (ISC_R_UNEXPECTED);
4958 rbtdb->node_locks[i].references = 0;
4959 rbtdb->node_locks[i].exiting = ISC_FALSE;
4963 * Attach to the mctx. The database will persist so long as there
4964 * are references to it, and attaching to the mctx ensures that our
4965 * mctx won't disappear out from under us.
4967 isc_mem_attach(mctx, &rbtdb->common.mctx);
4970 * Must be initalized before free_rbtdb() is called.
4972 isc_ondestroy_init(&rbtdb->common.ondest);
4975 * Make a copy of the origin name.
4977 result = dns_name_dupwithoffsets(origin, mctx, &rbtdb->common.origin);
4978 if (result != ISC_R_SUCCESS) {
4979 free_rbtdb(rbtdb, ISC_FALSE, NULL);
4984 * Make the Red-Black Tree.
4986 result = dns_rbt_create(mctx, delete_callback, rbtdb, &rbtdb->tree);
4987 if (result != ISC_R_SUCCESS) {
4988 free_rbtdb(rbtdb, ISC_FALSE, NULL);
4992 * In order to set the node callback bit correctly in zone databases,
4993 * we need to know if the node has the origin name of the zone.
4994 * In loading_addrdataset() we could simply compare the new name
4995 * to the origin name, but this is expensive. Also, we don't know the
4996 * node name in addrdataset(), so we need another way of knowing the
4999 * We now explicitly create a node for the zone's origin, and then
5000 * we simply remember the node's address. This is safe, because
5001 * the top-of-zone node can never be deleted, nor can its address
5004 if (! IS_CACHE(rbtdb)) {
5005 rbtdb->origin_node = NULL;
5006 result = dns_rbt_addnode(rbtdb->tree, &rbtdb->common.origin,
5007 &rbtdb->origin_node);
5008 if (result != ISC_R_SUCCESS) {
5009 INSIST(result != ISC_R_EXISTS);
5010 free_rbtdb(rbtdb, ISC_FALSE, NULL);
5014 * We need to give the origin node the right locknum.
5016 dns_name_init(&name, NULL);
5017 dns_rbt_namefromnode(rbtdb->origin_node, &name);
5018 #ifdef DNS_RBT_USEHASH
5019 rbtdb->origin_node->locknum =
5020 rbtdb->origin_node->hashval %
5021 rbtdb->node_lock_count;
5023 rbtdb->origin_node->locknum =
5024 dns_name_hash(&name, ISC_TRUE) %
5025 rbtdb->node_lock_count;
5030 * Misc. Initialization.
5032 isc_refcount_init(&rbtdb->references, 1);
5033 rbtdb->attributes = 0;
5034 rbtdb->secure = ISC_FALSE;
5035 rbtdb->overmem = ISC_FALSE;
5039 * Version Initialization.
5041 rbtdb->current_serial = 1;
5042 rbtdb->least_serial = 1;
5043 rbtdb->next_serial = 2;
5044 rbtdb->current_version = allocate_version(mctx, 1, 0, ISC_FALSE);
5045 if (rbtdb->current_version == NULL) {
5046 free_rbtdb(rbtdb, ISC_FALSE, NULL);
5047 return (ISC_R_NOMEMORY);
5049 rbtdb->future_version = NULL;
5050 ISC_LIST_INIT(rbtdb->open_versions);
5052 rbtdb->common.magic = DNS_DB_MAGIC;
5053 rbtdb->common.impmagic = RBTDB_MAGIC;
5055 *dbp = (dns_db_t *)rbtdb;
5057 return (ISC_R_SUCCESS);
5062 * Slabbed Rdataset Methods
5066 rdataset_disassociate(dns_rdataset_t *rdataset) {
5067 dns_db_t *db = rdataset->private1;
5068 dns_dbnode_t *node = rdataset->private2;
5070 detachnode(db, &node);
5074 rdataset_first(dns_rdataset_t *rdataset) {
5075 unsigned char *raw = rdataset->private3;
5078 count = raw[0] * 256 + raw[1];
5080 rdataset->private5 = NULL;
5081 return (ISC_R_NOMORE);
5085 * The privateuint4 field is the number of rdata beyond the cursor
5086 * position, so we decrement the total count by one before storing
5090 rdataset->privateuint4 = count;
5091 rdataset->private5 = raw;
5093 return (ISC_R_SUCCESS);
5097 rdataset_next(dns_rdataset_t *rdataset) {
5099 unsigned int length;
5102 count = rdataset->privateuint4;
5104 return (ISC_R_NOMORE);
5106 rdataset->privateuint4 = count;
5107 raw = rdataset->private5;
5108 length = raw[0] * 256 + raw[1];
5110 rdataset->private5 = raw;
5112 return (ISC_R_SUCCESS);
5116 rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
5117 unsigned char *raw = rdataset->private5;
5120 REQUIRE(raw != NULL);
5122 r.length = raw[0] * 256 + raw[1];
5125 dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
5129 rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
5130 dns_db_t *db = source->private1;
5131 dns_dbnode_t *node = source->private2;
5132 dns_dbnode_t *cloned_node = NULL;
5134 attachnode(db, node, &cloned_node);
5138 * Reset iterator state.
5140 target->privateuint4 = 0;
5141 target->private5 = NULL;
5145 rdataset_count(dns_rdataset_t *rdataset) {
5146 unsigned char *raw = rdataset->private3;
5149 count = raw[0] * 256 + raw[1];
5155 rdataset_getnoqname(dns_rdataset_t *rdataset, dns_name_t *name,
5156 dns_rdataset_t *nsec, dns_rdataset_t *nsecsig)
5158 dns_db_t *db = rdataset->private1;
5159 dns_dbnode_t *node = rdataset->private2;
5160 dns_dbnode_t *cloned_node;
5161 struct noqname *noqname = rdataset->private6;
5164 attachnode(db, node, &cloned_node);
5165 nsec->methods = &rdataset_methods;
5166 nsec->rdclass = db->rdclass;
5167 nsec->type = dns_rdatatype_nsec;
5169 nsec->ttl = rdataset->ttl;
5170 nsec->trust = rdataset->trust;
5171 nsec->private1 = rdataset->private1;
5172 nsec->private2 = rdataset->private2;
5173 nsec->private3 = noqname->nsec;
5174 nsec->privateuint4 = 0;
5175 nsec->private5 = NULL;
5176 nsec->private6 = NULL;
5179 attachnode(db, node, &cloned_node);
5180 nsecsig->methods = &rdataset_methods;
5181 nsecsig->rdclass = db->rdclass;
5182 nsecsig->type = dns_rdatatype_rrsig;
5183 nsecsig->covers = dns_rdatatype_nsec;
5184 nsecsig->ttl = rdataset->ttl;
5185 nsecsig->trust = rdataset->trust;
5186 nsecsig->private1 = rdataset->private1;
5187 nsecsig->private2 = rdataset->private2;
5188 nsecsig->private3 = noqname->nsecsig;
5189 nsecsig->privateuint4 = 0;
5190 nsecsig->private5 = NULL;
5191 nsec->private6 = NULL;
5193 dns_name_clone(&noqname->name, name);
5195 return (ISC_R_SUCCESS);
5199 * Rdataset Iterator Methods
5203 rdatasetiter_destroy(dns_rdatasetiter_t **iteratorp) {
5204 rbtdb_rdatasetiter_t *rbtiterator;
5206 rbtiterator = (rbtdb_rdatasetiter_t *)(*iteratorp);
5208 if (rbtiterator->common.version != NULL)
5209 closeversion(rbtiterator->common.db,
5210 &rbtiterator->common.version, ISC_FALSE);
5211 detachnode(rbtiterator->common.db, &rbtiterator->common.node);
5212 isc_mem_put(rbtiterator->common.db->mctx, rbtiterator,
5213 sizeof(*rbtiterator));
5219 rdatasetiter_first(dns_rdatasetiter_t *iterator) {
5220 rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5221 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5222 dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5223 rbtdb_version_t *rbtversion = rbtiterator->common.version;
5224 rdatasetheader_t *header, *top_next;
5225 rbtdb_serial_t serial;
5228 if (IS_CACHE(rbtdb)) {
5230 now = rbtiterator->common.now;
5232 serial = rbtversion->serial;
5236 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5238 for (header = rbtnode->data; header != NULL; header = top_next) {
5239 top_next = header->next;
5241 if (header->serial <= serial && !IGNORE(header)) {
5243 * Is this a "this rdataset doesn't exist"
5244 * record? Or is it too old in the cache?
5246 * Note: unlike everywhere else, we
5247 * check for now > header->ttl instead
5248 * of now >= header->ttl. This allows
5249 * ANY and RRSIG queries for 0 TTL
5250 * rdatasets to work.
5252 if (NONEXISTENT(header) ||
5253 (now != 0 && now > header->ttl))
5257 header = header->down;
5258 } while (header != NULL);
5263 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5265 rbtiterator->current = header;
5268 return (ISC_R_NOMORE);
5270 return (ISC_R_SUCCESS);
5274 rdatasetiter_next(dns_rdatasetiter_t *iterator) {
5275 rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5276 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5277 dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5278 rbtdb_version_t *rbtversion = rbtiterator->common.version;
5279 rdatasetheader_t *header, *top_next;
5280 rbtdb_serial_t serial;
5282 rbtdb_rdatatype_t type, negtype;
5283 dns_rdatatype_t rdtype, covers;
5285 header = rbtiterator->current;
5287 return (ISC_R_NOMORE);
5289 if (IS_CACHE(rbtdb)) {
5291 now = rbtiterator->common.now;
5293 serial = rbtversion->serial;
5297 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5299 type = header->type;
5300 rdtype = RBTDB_RDATATYPE_BASE(header->type);
5302 covers = RBTDB_RDATATYPE_EXT(header->type);
5303 negtype = RBTDB_RDATATYPE_VALUE(covers, 0);
5305 negtype = RBTDB_RDATATYPE_VALUE(0, rdtype);
5306 for (header = header->next; header != NULL; header = top_next) {
5307 top_next = header->next;
5309 * If not walking back up the down list.
5311 if (header->type != type && header->type != negtype) {
5313 if (header->serial <= serial &&
5316 * Is this a "this rdataset doesn't
5319 * Note: unlike everywhere else, we
5320 * check for now > header->ttl instead
5321 * of now >= header->ttl. This allows
5322 * ANY and RRSIG queries for 0 TTL
5323 * rdatasets to work.
5325 if ((header->attributes &
5326 RDATASET_ATTR_NONEXISTENT) != 0 ||
5327 (now != 0 && now > header->ttl))
5331 header = header->down;
5332 } while (header != NULL);
5338 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5340 rbtiterator->current = header;
5343 return (ISC_R_NOMORE);
5345 return (ISC_R_SUCCESS);
5349 rdatasetiter_current(dns_rdatasetiter_t *iterator, dns_rdataset_t *rdataset) {
5350 rbtdb_rdatasetiter_t *rbtiterator = (rbtdb_rdatasetiter_t *)iterator;
5351 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)(rbtiterator->common.db);
5352 dns_rbtnode_t *rbtnode = rbtiterator->common.node;
5353 rdatasetheader_t *header;
5355 header = rbtiterator->current;
5356 REQUIRE(header != NULL);
5358 LOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5360 bind_rdataset(rbtdb, rbtnode, header, rbtiterator->common.now,
5363 UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock);
5368 * Database Iterator Methods
5372 reference_iter_node(rbtdb_dbiterator_t *rbtdbiter) {
5373 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5374 dns_rbtnode_t *node = rbtdbiter->node;
5379 INSIST(rbtdbiter->tree_locked != isc_rwlocktype_none);
5380 LOCK(&rbtdb->node_locks[node->locknum].lock);
5381 new_reference(rbtdb, node);
5382 UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5386 dereference_iter_node(rbtdb_dbiterator_t *rbtdbiter) {
5387 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5388 dns_rbtnode_t *node = rbtdbiter->node;
5394 lock = &rbtdb->node_locks[node->locknum].lock;
5396 INSIST(rbtdbiter->node->references > 0);
5397 if (--node->references == 0)
5398 no_references(rbtdb, node, 0, rbtdbiter->tree_locked);
5401 rbtdbiter->node = NULL;
5405 flush_deletions(rbtdb_dbiterator_t *rbtdbiter) {
5406 dns_rbtnode_t *node;
5407 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5408 isc_boolean_t was_read_locked = ISC_FALSE;
5412 if (rbtdbiter->delete != 0) {
5414 * Note that "%d node of %d in tree" can report things like
5415 * "flush_deletions: 59 nodes of 41 in tree". This means
5416 * That some nodes appear on the deletions list more than
5417 * once. Only the last occurence will actually be deleted.
5419 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
5420 DNS_LOGMODULE_CACHE, ISC_LOG_DEBUG(1),
5421 "flush_deletions: %d nodes of %d in tree",
5423 dns_rbt_nodecount(rbtdb->tree));
5425 if (rbtdbiter->tree_locked == isc_rwlocktype_read) {
5426 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5427 was_read_locked = ISC_TRUE;
5429 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
5430 rbtdbiter->tree_locked = isc_rwlocktype_write;
5432 for (i = 0; i < rbtdbiter->delete; i++) {
5433 node = rbtdbiter->deletions[i];
5434 lock = &rbtdb->node_locks[node->locknum].lock;
5437 INSIST(node->references > 0);
5439 if (node->references == 0)
5440 no_references(rbtdb, node, 0,
5441 rbtdbiter->tree_locked);
5445 rbtdbiter->delete = 0;
5447 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_write);
5448 if (was_read_locked) {
5449 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5450 rbtdbiter->tree_locked = isc_rwlocktype_read;
5453 rbtdbiter->tree_locked = isc_rwlocktype_none;
5459 resume_iteration(rbtdb_dbiterator_t *rbtdbiter) {
5460 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5462 REQUIRE(rbtdbiter->paused);
5463 REQUIRE(rbtdbiter->tree_locked == isc_rwlocktype_none);
5465 RWLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5466 rbtdbiter->tree_locked = isc_rwlocktype_read;
5468 rbtdbiter->paused = ISC_FALSE;
5472 dbiterator_destroy(dns_dbiterator_t **iteratorp) {
5473 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)(*iteratorp);
5474 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)rbtdbiter->common.db;
5475 dns_db_t *db = NULL;
5477 if (rbtdbiter->tree_locked == isc_rwlocktype_read) {
5478 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5479 rbtdbiter->tree_locked = isc_rwlocktype_none;
5481 INSIST(rbtdbiter->tree_locked == isc_rwlocktype_none);
5483 dereference_iter_node(rbtdbiter);
5485 flush_deletions(rbtdbiter);
5487 dns_db_attach(rbtdbiter->common.db, &db);
5488 dns_db_detach(&rbtdbiter->common.db);
5490 dns_rbtnodechain_reset(&rbtdbiter->chain);
5491 isc_mem_put(db->mctx, rbtdbiter, sizeof(*rbtdbiter));
5498 dbiterator_first(dns_dbiterator_t *iterator) {
5499 isc_result_t result;
5500 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5501 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5502 dns_name_t *name, *origin;
5504 if (rbtdbiter->result != ISC_R_SUCCESS &&
5505 rbtdbiter->result != ISC_R_NOMORE)
5506 return (rbtdbiter->result);
5508 if (rbtdbiter->paused)
5509 resume_iteration(rbtdbiter);
5511 dereference_iter_node(rbtdbiter);
5513 name = dns_fixedname_name(&rbtdbiter->name);
5514 origin = dns_fixedname_name(&rbtdbiter->origin);
5515 dns_rbtnodechain_reset(&rbtdbiter->chain);
5517 result = dns_rbtnodechain_first(&rbtdbiter->chain, rbtdb->tree, name,
5520 if (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
5521 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5522 NULL, &rbtdbiter->node);
5523 if (result == ISC_R_SUCCESS) {
5524 rbtdbiter->new_origin = ISC_TRUE;
5525 reference_iter_node(rbtdbiter);
5528 INSIST(result == ISC_R_NOTFOUND);
5529 result = ISC_R_NOMORE; /* The tree is empty. */
5532 rbtdbiter->result = result;
5538 dbiterator_last(dns_dbiterator_t *iterator) {
5539 isc_result_t result;
5540 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5541 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5542 dns_name_t *name, *origin;
5544 if (rbtdbiter->result != ISC_R_SUCCESS &&
5545 rbtdbiter->result != ISC_R_NOMORE)
5546 return (rbtdbiter->result);
5548 if (rbtdbiter->paused)
5549 resume_iteration(rbtdbiter);
5551 dereference_iter_node(rbtdbiter);
5553 name = dns_fixedname_name(&rbtdbiter->name);
5554 origin = dns_fixedname_name(&rbtdbiter->origin);
5555 dns_rbtnodechain_reset(&rbtdbiter->chain);
5557 result = dns_rbtnodechain_last(&rbtdbiter->chain, rbtdb->tree, name,
5559 if (result == ISC_R_SUCCESS || result == DNS_R_NEWORIGIN) {
5560 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5561 NULL, &rbtdbiter->node);
5562 if (result == ISC_R_SUCCESS) {
5563 rbtdbiter->new_origin = ISC_TRUE;
5564 reference_iter_node(rbtdbiter);
5567 INSIST(result == ISC_R_NOTFOUND);
5568 result = ISC_R_NOMORE; /* The tree is empty. */
5571 rbtdbiter->result = result;
5577 dbiterator_seek(dns_dbiterator_t *iterator, dns_name_t *name) {
5578 isc_result_t result;
5579 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5580 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5581 dns_name_t *iname, *origin;
5583 if (rbtdbiter->result != ISC_R_SUCCESS &&
5584 rbtdbiter->result != ISC_R_NOMORE)
5585 return (rbtdbiter->result);
5587 if (rbtdbiter->paused)
5588 resume_iteration(rbtdbiter);
5590 dereference_iter_node(rbtdbiter);
5592 iname = dns_fixedname_name(&rbtdbiter->name);
5593 origin = dns_fixedname_name(&rbtdbiter->origin);
5594 dns_rbtnodechain_reset(&rbtdbiter->chain);
5596 result = dns_rbt_findnode(rbtdb->tree, name, NULL, &rbtdbiter->node,
5597 &rbtdbiter->chain, DNS_RBTFIND_EMPTYDATA,
5599 if (result == ISC_R_SUCCESS) {
5600 result = dns_rbtnodechain_current(&rbtdbiter->chain, iname,
5602 if (result == ISC_R_SUCCESS) {
5603 rbtdbiter->new_origin = ISC_TRUE;
5604 reference_iter_node(rbtdbiter);
5607 } else if (result == DNS_R_PARTIALMATCH)
5608 result = ISC_R_NOTFOUND;
5610 rbtdbiter->result = result;
5616 dbiterator_prev(dns_dbiterator_t *iterator) {
5617 isc_result_t result;
5618 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5619 dns_name_t *name, *origin;
5621 REQUIRE(rbtdbiter->node != NULL);
5623 if (rbtdbiter->result != ISC_R_SUCCESS)
5624 return (rbtdbiter->result);
5626 if (rbtdbiter->paused)
5627 resume_iteration(rbtdbiter);
5629 name = dns_fixedname_name(&rbtdbiter->name);
5630 origin = dns_fixedname_name(&rbtdbiter->origin);
5631 result = dns_rbtnodechain_prev(&rbtdbiter->chain, name, origin);
5633 dereference_iter_node(rbtdbiter);
5635 if (result == DNS_R_NEWORIGIN || result == ISC_R_SUCCESS) {
5636 rbtdbiter->new_origin = ISC_TF(result == DNS_R_NEWORIGIN);
5637 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5638 NULL, &rbtdbiter->node);
5641 if (result == ISC_R_SUCCESS)
5642 reference_iter_node(rbtdbiter);
5644 rbtdbiter->result = result;
5650 dbiterator_next(dns_dbiterator_t *iterator) {
5651 isc_result_t result;
5652 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5653 dns_name_t *name, *origin;
5655 REQUIRE(rbtdbiter->node != NULL);
5657 if (rbtdbiter->result != ISC_R_SUCCESS)
5658 return (rbtdbiter->result);
5660 if (rbtdbiter->paused)
5661 resume_iteration(rbtdbiter);
5663 name = dns_fixedname_name(&rbtdbiter->name);
5664 origin = dns_fixedname_name(&rbtdbiter->origin);
5665 result = dns_rbtnodechain_next(&rbtdbiter->chain, name, origin);
5667 dereference_iter_node(rbtdbiter);
5669 if (result == DNS_R_NEWORIGIN || result == ISC_R_SUCCESS) {
5670 rbtdbiter->new_origin = ISC_TF(result == DNS_R_NEWORIGIN);
5671 result = dns_rbtnodechain_current(&rbtdbiter->chain, NULL,
5672 NULL, &rbtdbiter->node);
5674 if (result == ISC_R_SUCCESS)
5675 reference_iter_node(rbtdbiter);
5677 rbtdbiter->result = result;
5683 dbiterator_current(dns_dbiterator_t *iterator, dns_dbnode_t **nodep,
5686 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5687 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5688 dns_rbtnode_t *node = rbtdbiter->node;
5689 isc_result_t result;
5690 dns_name_t *nodename = dns_fixedname_name(&rbtdbiter->name);
5691 dns_name_t *origin = dns_fixedname_name(&rbtdbiter->origin);
5693 REQUIRE(rbtdbiter->result == ISC_R_SUCCESS);
5694 REQUIRE(rbtdbiter->node != NULL);
5696 if (rbtdbiter->paused)
5697 resume_iteration(rbtdbiter);
5700 if (rbtdbiter->common.relative_names)
5702 result = dns_name_concatenate(nodename, origin, name, NULL);
5703 if (result != ISC_R_SUCCESS)
5705 if (rbtdbiter->common.relative_names && rbtdbiter->new_origin)
5706 result = DNS_R_NEWORIGIN;
5708 result = ISC_R_SUCCESS;
5710 LOCK(&rbtdb->node_locks[node->locknum].lock);
5711 new_reference(rbtdb, node);
5712 UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5714 *nodep = rbtdbiter->node;
5716 if (iterator->cleaning && result == ISC_R_SUCCESS) {
5717 isc_result_t expire_result;
5720 * If the deletion array is full, flush it before trying
5721 * to expire the current node. The current node can't
5722 * fully deleted while the iteration cursor is still on it.
5724 if (rbtdbiter->delete == DELETION_BATCH_MAX)
5725 flush_deletions(rbtdbiter);
5727 expire_result = expirenode(iterator->db, *nodep, 0);
5730 * expirenode() currently always returns success.
5732 if (expire_result == ISC_R_SUCCESS && node->down == NULL) {
5733 rbtdbiter->deletions[rbtdbiter->delete++] = node;
5734 LOCK(&rbtdb->node_locks[node->locknum].lock);
5736 UNLOCK(&rbtdb->node_locks[node->locknum].lock);
5744 dbiterator_pause(dns_dbiterator_t *iterator) {
5745 dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)iterator->db;
5746 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5748 if (rbtdbiter->result != ISC_R_SUCCESS &&
5749 rbtdbiter->result != ISC_R_NOMORE)
5750 return (rbtdbiter->result);
5752 if (rbtdbiter->paused)
5753 return (ISC_R_SUCCESS);
5755 rbtdbiter->paused = ISC_TRUE;
5757 if (rbtdbiter->tree_locked != isc_rwlocktype_none) {
5758 INSIST(rbtdbiter->tree_locked == isc_rwlocktype_read);
5759 RWUNLOCK(&rbtdb->tree_lock, isc_rwlocktype_read);
5760 rbtdbiter->tree_locked = isc_rwlocktype_none;
5763 flush_deletions(rbtdbiter);
5765 return (ISC_R_SUCCESS);
5769 dbiterator_origin(dns_dbiterator_t *iterator, dns_name_t *name) {
5770 rbtdb_dbiterator_t *rbtdbiter = (rbtdb_dbiterator_t *)iterator;
5771 dns_name_t *origin = dns_fixedname_name(&rbtdbiter->origin);
5773 if (rbtdbiter->result != ISC_R_SUCCESS)
5774 return (rbtdbiter->result);
5776 return (dns_name_copy(origin, name, NULL));