rbtdb.c revision 6434457b0b380aa43d7159299776959a00269d65
/*
* Copyright (C) 1999-2001 Internet Software Consortium.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
* DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
* INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT,
* INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
* NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
* WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/* $Id: rbtdb.c,v 1.181 2002/11/12 23:24:45 explorer Exp $ */
/*
* Principal Author: Bob Halley
*/
#include <config.h>
#include <isc/refcount.h>
#include <dns/dbiterator.h>
#include <dns/fixedname.h>
#include <dns/masterdump.h>
#include <dns/rdataset.h>
#include <dns/rdatasetiter.h>
#include <dns/rdataslab.h>
#ifdef DNS_RBTDB_VERSION64
#include "rbtdb64.h"
#else
#include "rbtdb.h"
#endif
#ifdef DNS_RBTDB_VERSION64
#else
#endif
/*
* Note that "impmagic" is not the first four bytes of the struct, so
* ISC_MAGIC_VALID cannot be used.
*/
#ifdef DNS_RBTDB_VERSION64
typedef isc_uint64_t rbtdb_serial_t;
/*
* Make casting easier in symbolic debuggers by using different names
* for the 64 bit version.
*/
#define dns_rbtdb_t dns_rbtdb64_t
#define rdatasetheader_t rdatasetheader64_t
#define rbtdb_version_t rbtdb_version64_t
#else
typedef isc_uint32_t rbtdb_serial_t;
#endif
typedef isc_uint32_t rbtdb_rdatatype_t;
#define RBTDB_RDATATYPE_VALUE(b, e) (((e) << 16) | (b))
#define RBTDB_RDATATYPE_SIGNXT \
#define RBTDB_RDATATYPE_SIGNS \
#define RBTDB_RDATATYPE_SIGCNAME \
#define RBTDB_RDATATYPE_SIGDNAME \
#define RBTDB_RDATATYPE_NXDOMAIN \
typedef struct rdatasetheader {
/*
* Locked by the owning node's lock.
*/
/*
* We don't use the LIST macros, because the LIST structure has
* both head and tail pointers, and is doubly linked.
*/
struct rdatasetheader *next;
/*
* If this is the top header for an rdataset, 'next' points
* to the top header for the next rdataset (i.e., the next type).
* Otherwise, it points up to the header whose down pointer points
* at this header.
*/
struct rdatasetheader *down;
/*
* Points to the header for the next older version of
* this rdataset.
*/
#define RDATASET_ATTR_NONEXISTENT 0x0001
#define RDATASET_ATTR_STALE 0x0002
#define RDATASET_ATTR_IGNORE 0x0004
#define RDATASET_ATTR_RETAIN 0x0008
/*
* XXX
* When the cache will pre-expire data (due to memory low or other
* situations) before the rdataset's TTL has expired, it MUST
* respect the RETAIN bit and not expire the data until its TTL is
* expired.
*/
#define NONEXISTENT(header) \
typedef struct {
/* Locked by lock. */
unsigned int references;
typedef struct rbtdb_changed {
typedef struct rbtdb_version {
/* Not locked */
/* Locked by database lock. */
unsigned int references;
typedef struct {
/* Unlocked. */
unsigned int node_lock_count;
/* Locked by lock. */
unsigned int attributes;
/* Locked by tree_lock. */
} dns_rbtdb_t;
#define RBTDB_ATTR_LOADED 0x01
#define RBTDB_ATTR_LOADING 0x02
/*
* Search Context
*/
typedef struct {
dns_rbtdb_t * rbtdb;
unsigned int options;
/*
* Load Context
*/
typedef struct {
dns_rbtdb_t * rbtdb;
} rbtdb_load_t;
static dns_rdatasetmethods_t rdataset_methods = {
};
static dns_rdatasetitermethods_t rdatasetiter_methods = {
};
typedef struct rbtdb_rdatasetiter {
dns_name_t *name);
dns_name_t *name);
dns_name_t *name);
static dns_dbiteratormethods_t dbiterator_methods = {
};
#define DELETION_BATCH_MAX 64
/*
* If 'paused' is ISC_TRUE, then the tree lock is not being held.
*/
typedef struct rbtdb_dbiterator {
int delete;
/*
* Locking
*
* If a routine is going to lock more than one lock in this module, then
* the locking must be done in the following order:
*
* Tree Lock
*
* Node Lock (Only one from the set may be locked at one time by
* any caller)
*
* Database Lock
*
* Failure to follow this hierarchy can result in deadlock.
*/
/*
* Deleting Nodes
*
* Currently there is no deletion of nodes from the database, except when
* the database is being destroyed.
*
* If node deletion is added in the future, then for zone databases the node
* for the origin of the zone MUST NOT be deleted.
*/
/*
* DB Routines
*/
static void
}
static void
unsigned int i;
sizeof(rbtdb_version_t));
for (i = 0; i < rbtdb->node_lock_count; i++)
}
static inline void
unsigned int i;
/* XXX check for open versions here */
/*
* Even though there are no external direct references, there still
* may be nodes in use.
*/
for (i = 0; i < rbtdb->node_lock_count; i++) {
if (set_exiting)
}
if (want_free)
}
static void
unsigned int refs;
if (refs == 0)
}
static void
if (version->references == 0)
version->references++;
}
static inline rbtdb_version_t *
{
return (NULL);
return (version);
}
static isc_result_t
ISC_TRUE);
rbtdb->next_serial++;
}
return (ISC_R_NOMEMORY);
return (ISC_R_SUCCESS);
}
static void
{
rbtversion->references++;
*targetp = rbtversion;
}
static rbtdb_changed_t *
{
/*
* Caller must be holding the node lock.
*/
node->references++;
} else
return (changed);
}
static inline void
unsigned int size;
else
sizeof(*rdataset));
}
static inline void
/*
* Caller must hold the node lock.
*/
/*
* We set the IGNORE attribute on rdatasets with serial number
* 'serial'. When the reference count goes to zero, these rdatasets
* will be cleaned up; until that time, they will be ignored.
*/
}
}
}
}
if (make_dirty)
}
static inline void
/*
* Caller must be holding the node lock.
*/
do {
}
/*
* If current is nonexistent or stale, we can clean it up.
*/
if ((current->attributes &
(RDATASET_ATTR_NONEXISTENT|RDATASET_ATTR_STALE)) != 0) {
else
} else
}
}
static inline void
{
/*
* Caller must be holding the node lock.
*/
REQUIRE(least_serial != 0);
/*
* First, we clean up any instances of multiple rdatasets
* with the same serial number, or that have the IGNORE
* attribute.
*/
} else
}
/*
* We've now eliminated all IGNORE datasets with the possible
* exception of current, which we now check.
*/
else
/*
* current no longer exists, so we can
* just continue with the loop.
*/
continue;
} else {
/*
* Pull up current->down, making it the new
* current.
*/
else
}
}
/*
* We now try to find the first down node less than the
* least serial.
*/
break;
}
/*
* If there is a such an rdataset, delete it and any older
* versions.
*/
do {
}
/*
* Note. The serial number of 'current' might be less than
* least_serial too, but we cannot delete it because it is
* the most recent version, unless it is a NONEXISTENT
* rdataset.
*/
} else {
/*
* If this is a NONEXISTENT rdataset, we can delete it.
*/
!= 0) {
else
} else
}
}
if (!still_dirty)
}
static inline void
if (node->references == 0) {
}
node->references++;
}
static void
{
unsigned int locknum;
/*
* Caller must be holding the node lock.
*/
else {
if (least_serial == 0) {
/*
* Caller doesn't know the least serial.
* Get it.
*/
}
}
}
/*
* XXXDCL should this only be done for cache zones?
*/
return;
/*
* XXXDCL need to add a deferred delete method for ISC_R_LOCKBUSY.
*/
if (lock != isc_rwlocktype_write) {
/*
* Locking hierarchy notwithstanding, we don't need to free
* the node lock before acquiring the tree write lock because
* we only do a trylock.
*/
if (lock == isc_rwlocktype_read)
result == ISC_R_LOCKBUSY);
} else
if (write_locked) {
char printname[DNS_NAME_FORMATSIZE];
"no_references: delete from rbt: %p %s",
node,
sizeof(printname)));
}
if (result != ISC_R_SUCCESS)
"no_references: dns_rbt_deletenode: %s",
}
/*
* Relock a read lock, or unlock the write lock if no lock was held.
*/
if (lock != isc_rwlocktype_write)
if (write_locked)
if (lock == isc_rwlocktype_read)
}
static inline void
{
/*
* Caller must be holding the database lock.
*/
}
static inline void
/*
* If the changed record is dirty, then
* an update created multiple versions of
* a given rdataset. We keep this list
* until we're the least open version, at
* which point it's safe to get rid of any
* older versions.
*
* If the changed record isn't dirty, then
* we don't need it anymore since we're
* committing and not rolling back.
*
* The caller must be holding the database lock.
*/
changed = next_changed) {
}
}
}
static void
version->references--;
if (version->references == 0) {
if (commit) {
/*
* We're going to become the least open
* version.
*/
&cleanup_list);
} else {
/*
* Some other open version is the
* least version. We can't cleanup
* records that were changed in this
* version because the older versions
* may still be in use by an open
* version.
*
* We can, however, discard the
* changed records for things that
* we've added that didn't exist in
* prior versions.
*/
&cleanup_list);
}
/*
* If the (soon to be former) current version
* isn't being used by anyone, we can clean
* it up.
*/
/*
* Become the current version.
*/
} else {
/*
* We're rolling back this transaction.
*/
}
} else {
/*
* There are no external or internal references
* to this version and it can be cleaned up.
*/
/*
* Find the version with the least serial
* number greater than ours.
*/
if (least_greater == NULL)
/*
* Is this the least open version?
*/
/*
* Yes. Install the new least open
* version.
*/
&cleanup_list);
} else {
/*
* Add any unexecuted cleanups to
* those of the least greater version.
*/
link);
}
}
}
}
if (cleanup_version != NULL)
sizeof(*cleanup_version));
if (!EMPTY(cleanup_list)) {
changed = next_changed) {
rbtnode->references--;
if (rollback)
if (rbtnode->references == 0)
sizeof(*changed));
}
}
}
/*
* Add the necessary magic for the wildcard name 'name'
* to be found in 'rbtdb'.
*
* In order for wildcard matching to work correctly in
* zone_find(), we must ensure that a node for the wildcarding
* level exists in the database, and has its 'find_callback'
* and 'wild' bits set.
*
* E.g. if the wildcard name is "*.sub.example." then we
* must ensure that "sub.example." exists and is marked as
* a wildcard level.
*/
static isc_result_t
unsigned int n;
n = dns_name_countlabels(name);
INSIST(n >= 2);
n--;
return (result);
return (ISC_R_SUCCESS);
}
static isc_result_t
{
unsigned int locknum;
if (result != ISC_R_SUCCESS) {
if (!create) {
if (result == DNS_R_PARTIALMATCH)
return (result);
}
/*
* It would be nice to try to upgrade the lock instead of
* unlocking then relocking.
*/
if (result == ISC_R_SUCCESS) {
#ifdef DNS_RBT_USEHASH
#else
#endif
if (dns_name_iswildcard(name)) {
if (result != ISC_R_SUCCESS) {
return (result);
}
}
} else if (result != ISC_R_EXISTS) {
return (result);
}
}
return (ISC_R_SUCCESS);
}
static isc_result_t
/*
* We only want to remember the topmost zone cut, since it's the one
* that counts, so we'll just continue if we've already found a
* zonecut.
*/
return (DNS_R_CONTINUE);
/*
* Look for an NS or DNAME rdataset active in our version.
*/
dname_header = NULL;
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*/
if (NONEXISTENT(header))
break;
} else
/*
* We've found an NS rdataset that
* isn't at the origin node. We check
* that they're not at the origin node,
* because otherwise we'd erroneously
* treat the zone top as if it were
* a delegation.
*/
}
}
}
}
/*
* Did we find anything?
*/
if (dname_header != NULL) {
/*
* Note that DNAME has precedence over NS if both exist.
*/
}
/*
* We increment the reference count on node to ensure that
* search->zonecut_rdataset will still be valid later.
*/
/*
* Since we've found a zonecut, anything beneath it is
* glue and is not subject to wildcard matching, so we
* may clear search->wild.
*/
/*
* If the caller does not want to find glue, then
* this is the best answer and the search should
* stop now.
*/
} else {
/*
* The search will continue beneath the zone cut.
* This may or may not be the best match. In case it
* is, we need to remember the node name.
*/
}
} else {
/*
* There is no zonecut at this node which is active in this
* version.
*
* If this is a "wild" node and the caller hasn't disabled
* wildcard matching, remember that we've seen a wild node
* in case we need to go searching for wildcard matches
* later on.
*/
}
return (result);
}
static inline void
{
unsigned char *raw;
/*
* Caller must be holding the node lock.
*/
return;
/*
* Reset iterator state.
*/
}
static inline isc_result_t
{
/*
* The caller MUST NOT be holding any node locks.
*/
/*
* If we have to set foundname, we do it before anything else.
* If we were to set foundname after we had set nodep or bound the
* rdataset, then we'd have to undo that work if dns_name_copy()
* failed. By setting foundname first, there's nothing to undo if
* we have trouble.
*/
if (result != ISC_R_SUCCESS)
return (result);
}
/*
* Note that we don't have to increment the node's reference
* count here because we're going to use the reference we
* already have in the search block.
*/
}
}
if (type == dns_rdatatype_dname)
return (DNS_R_DNAME);
return (DNS_R_DELEGATION);
}
static inline isc_boolean_t
{
unsigned char *raw;
/*
* No additional locking is required.
*/
/*
* Valid glue types are A, AAAA, A6. NS is also a valid glue type
* if it occurs at a zone cut, but is not valid below it.
*/
if (type == dns_rdatatype_ns) {
return (ISC_FALSE);
}
} else if (type != dns_rdatatype_a &&
type != dns_rdatatype_aaaa &&
type != dns_rdatatype_a6) {
return (ISC_FALSE);
}
raw += 2;
while (count > 0) {
count--;
raw += 2;
/*
* XXX Until we have rdata structures, we have no choice but
* to directly access the rdata format.
*/
break;
}
}
return (valid);
}
static inline isc_result_t
unsigned int i, j;
/*
* Caller must be holding the tree lock and MUST NOT be holding
* any node locks.
*/
/*
* Examine each ancestor level. If the level's wild bit
* is set, then construct the corresponding wildcard name and
* search for it. If the wildcard node exists, and is active in
* this version, we're done. If not, then we next check to see
* if the ancestor is active in this version. If so, then there
* can be no possible wildcard match and again we're done. If not,
* continue the search.
*/
do {
/*
* First we try to figure out if this node is active in
* the search's version. We do this now, even though we
* may not need the information, because it simplifies the
* locking and code flow.
*/
break;
}
else
else
if (wild) {
/*
* Construct the wildcard name for this level.
*/
j = i;
while (result == ISC_R_SUCCESS && j != 0) {
j--;
&name,
NULL);
}
if (result != ISC_R_SUCCESS)
break;
if (result == ISC_R_SUCCESS) {
/*
* We have found the wildcard node. If it
* is active in the search's version, we're
* done.
*/
break;
}
/*
* The wildcard node is active!
*
* Note: result is still ISC_R_SUCCESS
* so we don't have to set it.
*/
break;
}
} else if (result != ISC_R_NOTFOUND &&
result != DNS_R_PARTIALMATCH) {
/*
* An error has occurred. Bail out.
*/
break;
}
}
if (active) {
/*
* The level node is active. Any wildcarding
* present at higher levels has no
* effect and we're done.
*/
break;
}
if (i > 0) {
i--;
} else
} while (!done);
return (result);
}
static inline isc_result_t
{
do {
if (result != ISC_R_SUCCESS)
return (result);
header = header_next) {
/*
* Look for an active, extant NXT or SIG NXT.
*/
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*/
if ((header->attributes &
RDATASET_ATTR_NONEXISTENT) != 0)
break;
} else
/*
* We now know that there is at least one
* active rdataset at this node.
*/
break;
break;
}
}
}
if (!empty_node) {
{
/*
* We've found the right NXT record.
*
* Note: for this to really be the right
* NXT record, it's essential that the NXT
* records of any nodes obscured by a zone
* cut have been removed; we assume this is
* the case.
*/
if (result == ISC_R_SUCCESS) {
node);
}
rdataset);
node,
}
/*
* This node is active, but has no NXT or
* SIG NXT. That means it's glue or
* other obscured zone data that isn't
* relevant for our search. Treat the
* node as if it were empty and keep looking.
*/
} else {
/*
* We found an active node, but either the
* NXT or the SIG NXT is missing. This
* shouldn't happen.
*/
}
} else {
/*
* This node isn't active. We've got to keep
* looking.
*/
NULL);
}
/*
* If the result is ISC_R_NOMORE, then we got to the beginning of
* the database and didn't find a NXT record. This shouldn't
* happen.
*/
if (result == ISC_R_NOMORE)
return (result);
}
static isc_result_t
{
/*
* We don't care about 'now'.
*/
/*
* If the caller didn't supply a version, attach to the current
* version.
*/
}
/*
* 'wild' will be true iff. we've matched a wildcard.
*/
/*
* Search down from the root of the tree. If, while going down, we
* encounter a callback node, zone_zonecut_callback() will search the
* rdatasets at the zone cut for active DNAME or NS rdatasets.
*/
if (result == DNS_R_PARTIALMATCH) {
goto tree_exit;
}
/*
* At least one of the levels in the search chain
* potentially has a wildcard. For each such level,
* we must see if there's a matching wildcard active
* in the current version.
*/
if (result == ISC_R_SUCCESS) {
if (result != ISC_R_SUCCESS)
goto tree_exit;
goto found;
}
else if (result != ISC_R_NOTFOUND)
goto tree_exit;
}
/*
* If we're here, then the name does not exist, is not
* beneath a zonecut, and there's no matching wildcard.
*/
{
if (result == ISC_R_SUCCESS)
} else
goto tree_exit;
} else if (result != ISC_R_SUCCESS)
goto tree_exit;
/*
* We have found a node whose name is the desired name, or we
* have matched a wildcard.
*/
/*
* If we're beneath a zone cut, we don't want to look for
* CNAMEs because they're not legitimate zone glue.
*/
} else {
/*
* The node may be a zone cut itself. If it might be one,
* make sure we check for it later.
*/
if (node->find_callback &&
}
/*
* Certain DNSSEC types are not subject to CNAME matching
* (RFC 2535, section 2.3.5).
*
* We don't check for SIG, because we don't store SIG records
* directly.
*/
/*
* We now go looking for rdata...
*/
/*
* Look for an active, extant rdataset.
*/
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*/
if ((header->attributes &
RDATASET_ATTR_NONEXISTENT) != 0)
break;
} else
/*
* We now know that there is at least one active
* rdataset at this node.
*/
/*
* Do special zone cut handling, if requested.
*/
if (maybe_zonecut &&
/*
* We increment the reference count on node to
* ensure that search->zonecut_rdataset will
* still be valid later.
*/
&& type != dns_rdatatype_nxt
&& type != dns_rdatatype_key) {
/*
* Glue is not OK, but any answer we
* could return would be glue. Return
* the delegation.
*/
break;
}
break;
}
/*
* If we found a type we were looking for,
* remember it.
*/
type == dns_rdatatype_any ||
cname_ok)) {
/*
* We've found the answer!
*/
cname_ok) {
/*
* We may be finding a CNAME instead
* of the desired type.
*
* If we've already got the CNAME SIG,
* use it, otherwise change sigtype
* so that we find it.
*/
else
sigtype =
}
/*
* If we've got all we need, end the search.
*/
break;
/*
* We've found the SIG rdataset for our
* target type. Remember it.
*/
/*
* If we've got all we need, end the search.
*/
break;
/*
* Remember a NXT rdataset even if we're
* not specifically looking for it, because
* we might need it later.
*/
/*
* If we need the NXT rdataset, we'll also
* need its signature.
*/
} else if (cname_ok &&
/*
* If we get a CNAME match, we'll also need
* its signature.
*/
}
}
}
if (empty_node) {
/*
* We have an exact match for the name, but there are no
* active rdatasets in the desired version. That means that
* this node doesn't exist in the desired version, and that
* we really have a partial match.
*
* If the node is the result of a wildcard match, then
* it must be active in the desired version, and hence
* empty_node should never be true. We INSIST upon it.
*/
goto partial_match;
}
/*
* If we didn't find what we were looking for...
*/
/*
* We were trying to find glue at a node beneath a
* zone cut, but didn't.
*
* Return the delegation.
*/
goto tree_exit;
}
/*
* The desired type doesn't exist.
*/
/*
* The zone is secure but there's no NXT,
* or the NXT has no signature!
*/
goto node_exit;
}
{
/*
* There's no NXT record, and we were told
* to find one.
*/
goto node_exit;
}
}
{
0, rdataset);
nxtsig, 0, sigrdataset);
}
if (wild)
goto node_exit;
}
/*
* We found what we were looking for, or we found a CNAME.
*/
type != dns_rdatatype_any &&
/*
* We weren't doing an ANY query and we found a CNAME instead
* of the type we were looking for, so we need to indicate
* that result to the caller.
*/
/*
* If we're beneath a zone cut, we must indicate that the
* result is glue, unless we're actually at the zone cut
* and the type is NXT or KEY.
*/
if (type == dns_rdatatype_nxt ||
else if (type == dns_rdatatype_any)
else
result = DNS_R_GLUE;
} else
result = DNS_R_GLUE;
/*
* We might have found data that isn't glue, but was occluded
* by a dynamic update. If the caller cares about this, they
* will have told us to validate glue.
*
* XXX We should cache the glue validity state!
*/
if (result == DNS_R_GLUE &&
goto tree_exit;
}
} else {
/*
* An ordinary successful query!
*/
}
if (!at_zonecut)
else
}
if (type != dns_rdatatype_any) {
}
if (wild)
/*
* If we found a zonecut but aren't going to use it, we have to
* let go of it.
*/
if (search.need_cleanup) {
node->references--;
if (node->references == 0)
}
if (close_version)
return (result);
}
static isc_result_t
{
return (ISC_R_NOTIMPLEMENTED);
}
static isc_result_t
/* XXX comment */
/*
* Keep compiler silent.
*/
/*
* Look for a DNAME or SIG DNAME rdataset.
*/
dname_header = NULL;
header_prev = NULL;
/*
* This rdataset is stale. If no one else is
* using the node, we can clean it up right
* now, otherwise we mark it as stale, and
* the node as dirty, so it will get cleaned
* up later.
*/
if (node->references == 0) {
if (header_prev != NULL)
header_prev->next =
else
header);
} else {
header->attributes |=
}
} else
}
if (dname_header != NULL &&
/*
* We increment the reference count on node to ensure that
* search->zonecut_rdataset will still be valid later.
*/
} else
return (result);
}
static inline isc_result_t
{
unsigned int i;
/*
* Caller must be holding the tree lock.
*/
do {
/*
* Look for NS and SIG NS rdatasets.
*/
header_prev = NULL;
header = header_next) {
/*
* This rdataset is stale. If no one else is
* using the node, we can clean it up right
* now, otherwise we mark it as stale, and
* the node as dirty, so it will get cleaned
* up later.
*/
if (node->references == 0) {
if (header_prev != NULL)
header_prev->next =
else
header);
} else {
header->attributes |=
}
} else if ((header->attributes &
RDATASET_ATTR_NONEXISTENT) == 0) {
/*
* We've found an extant rdataset. See if
* we're interested in it.
*/
break;
break;
}
} else
}
/*
* If we have to set foundname, we do it before
* anything else. If we were to set foundname after
* we had set nodep or bound the rdataset, then we'd
* have to undo that work if dns_name_concatenate()
* failed. By setting foundname first, there's
* nothing to undo if we have trouble.
*/
while (result == ISC_R_SUCCESS && i > 0) {
i--;
&name);
result =
&name,
NULL);
}
if (result != ISC_R_SUCCESS) {
goto node_exit;
}
}
}
rdataset);
}
i--;
} else
} while (!done);
return (result);
}
static isc_result_t
{
if (now == 0)
/*
* Search down from the root of the tree. If, while going down, we
* encounter a callback node, cache_zonecut_callback() will search the
* rdatasets at the zone cut for a DNAME rdataset.
*/
if (result == DNS_R_PARTIALMATCH) {
goto tree_exit;
} else {
goto tree_exit;
}
} else if (result != ISC_R_SUCCESS)
goto tree_exit;
/*
* Certain DNSSEC types are not subject to CNAME matching
* (RFC 2535, section 2.3.5).
*
* We don't check for SIG, because we don't store SIG records
* directly.
*/
/*
* We now go looking for rdata...
*/
header_prev = NULL;
/*
* This rdataset is stale. If no one else is using the
* node, we can clean it up right now, otherwise we
* mark it as stale, and the node as dirty, so it will
* get cleaned up later.
*/
if (node->references == 0) {
if (header_prev != NULL)
else
header);
} else {
}
== 0) {
/*
* We now know that there is at least one active
* non-stale rdataset at this node.
*/
/*
* If we found a type we were looking for, remember
* it.
*/
(type == dns_rdatatype_any &&
/*
* We've found the answer.
*/
cname_ok &&
/*
* If we've already got the CNAME SIG,
* use it, otherwise change sigtype
* so that we find it.
*/
else
sigtype =
}
/*
* We've found the SIG rdataset for our
* target type. Remember it.
*/
/*
* We've found a negative cache entry.
*/
/*
* Remember a NS rdataset even if we're
* not specifically looking for it, because
* we might need it later.
*/
/*
* If we need the NS rdataset, we'll also
* need its signature.
*/
} else if (cname_ok &&
/*
* If we get a CNAME match, we'll also need
* its signature.
*/
}
} else
}
if (empty_node) {
/*
* We have an exact match for the name, but there are no
* extant rdatasets. That means that this node doesn't
* meaningfully exist, and that we really have a partial match.
*/
goto find_ns;
}
/*
* If we didn't find what we were looking for...
*/
((options & DNS_DBFIND_GLUEOK) == 0)) ||
((options & DNS_DBFIND_PENDINGOK) == 0))) {
/*
* If there is an NS rdataset at this node, then this is the
* deepest zone cut.
*/
}
rdataset);
goto node_exit;
}
/*
* Go find the deepest zone cut.
*/
goto find_ns;
}
/*
* We found what we were looking for, or we found a CNAME.
*/
}
/*
* We found a negative cache entry.
*/
else
type != dns_rdatatype_any &&
/*
* We weren't doing an ANY query and we found a CNAME instead
* of the type we were looking for, so we need to indicate
* that result to the caller.
*/
} else {
/*
* An ordinary successful query!
*/
}
rdataset);
}
/*
* If we found a zonecut but aren't going to use it, we have to
* let go of it.
*/
if (search.need_cleanup) {
node->references--;
if (node->references == 0)
}
return (result);
}
static isc_result_t
{
unsigned int rbtoptions = DNS_RBTFIND_EMPTYDATA;
if (now == 0)
if ((options & DNS_DBFIND_NOEXACT) != 0)
/*
* Search down from the root of the tree.
*/
if (result == DNS_R_PARTIALMATCH) {
goto tree_exit;
} else if (result != ISC_R_SUCCESS)
goto tree_exit;
/*
* We now go looking for an NS rdataset at the node.
*/
header_prev = NULL;
/*
* This rdataset is stale. If no one else is using the
* node, we can clean it up right now, otherwise we
* mark it as stale, and the node as dirty, so it will
* get cleaned up later.
*/
if (node->references == 0) {
if (header_prev != NULL)
else
header);
} else {
}
== 0) {
/*
* If we found a type we were looking for, remember
* it.
*/
/*
* Remember a NS rdataset even if we're
* not specifically looking for it, because
* we might need it later.
*/
/*
* If we need the NS rdataset, we'll also
* need its signature.
*/
}
} else
}
/*
* No NS records here.
*/
goto find_ns;
}
}
if (result == DNS_R_DELEGATION)
return (result);
}
static void
node->references++;
}
static void
unsigned int locknum;
node->references--;
if (node->references == 0) {
}
if (maybe_free)
}
static isc_result_t
/*
* These are the category and module used by the cache cleaner.
*/
char printname[DNS_NAME_FORMATSIZE];
/*
* Caller must hold a tree lock.
*/
if (now == 0)
/*
* XXXDCL Could stand to have a better policy, like LRU.
*/
/*
* Note that 'log' can be true IFF rbtdb->overmem is also true.
* rbtdb->ovemem can currently only be true for cache databases
* -- hence all of the "overmem cache" log strings.
*/
if (log)
"overmem cache: %s %s",
sizeof(printname)));
}
/*
* We don't check if rbtnode->references == 0 and try
* to free like we do in cache_find(), because
* rbtnode->references must be non-zero. This is so
* because 'node' is an argument to the function.
*/
if (log)
level, "overmem cache: stale %s",
} else if (force_expire) {
} else if (log) {
level, "overmem cache: "
"reprieve by RETAIN() %s",
}
"overmem cache: saved %s", printname);
return (ISC_R_SUCCESS);
}
static void
}
}
static void
do {
if (!first)
"\tserial = %lu, ttl = %u, "
"trust = %u, attributes = %u\n",
}
} else
}
static isc_result_t
{
return (ISC_R_NOMEMORY);
return (ISC_R_SUCCESS);
}
static isc_result_t
{
if (rbtversion == NULL) {
}
now = 0;
if (covers == 0)
else
sigmatchtype = 0;
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*/
if ((header->attributes &
RDATASET_ATTR_NONEXISTENT) != 0)
break;
} else
/*
* We have an active, extant rdataset. If it's a
* type we're looking for, remember it.
*/
break;
break;
}
}
}
}
if (close_version)
return (ISC_R_NOTFOUND);
return (ISC_R_SUCCESS);
}
static isc_result_t
{
if (now == 0)
if (covers == 0)
else
sigmatchtype = 0;
/*
* We don't check if rbtnode->references == 0 and try
* to free like we do in cache_find(), because
* rbtnode->references must be non-zero. This is so
* because 'node' is an argument to the function.
*/
0) {
}
}
}
return (ISC_R_NOTFOUND);
/*
* We found a negative cache entry.
*/
else
}
return (result);
}
static isc_result_t
{
return (ISC_R_NOMEMORY);
now = 0;
if (rbtversion == NULL)
else {
rbtversion->references++;
}
} else {
if (now == 0)
rbtversion = NULL;
}
rbtnode->references++;
return (ISC_R_SUCCESS);
}
static isc_boolean_t
/*
* The caller must hold the node lock.
*/
/*
* Look for CNAME and "other data" rdatasets active in our version.
*/
/*
* Look for an active extant CNAME.
*/
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*/
if (NONEXISTENT(header))
break;
} else
} else {
/*
* Look for active extant "other data".
*
* "Other data" is any rdataset whose type is not
* KEY, SIG KEY, NXT, SIG NXT, or SIG CNAME.
*/
if (rdtype == dns_rdatatype_sig)
if (rdtype != dns_rdatatype_nxt &&
rdtype != dns_rdatatype_key &&
rdtype != dns_rdatatype_cname) {
/*
* We've found a type that isn't
* NXT, KEY, CNAME, or one of their
* signatures. Is it active and extant?
*/
do {
/*
* Is this a "this rdataset
* doesn't exist" record?
*/
if (NONEXISTENT(header))
break;
} else
}
}
}
if (cname && other_data)
return (ISC_TRUE);
return (ISC_FALSE);
}
static isc_result_t
{
unsigned char *merged;
/*
* Add an rdatasetheader_t to a node.
*/
/*
* Caller must be holding the node lock.
*/
if ((options & DNS_DBADD_MERGE) != 0) {
} else
if ((options & DNS_DBADD_FORCE) != 0)
else
/*
* We always add a changed record, even if no changes end up
* being made to this node, because it's harmless and
* simplifies the code.
*/
return (ISC_R_NOMEMORY);
}
}
nxtype = 0;
if (rdtype == 0) {
/*
* We're adding a negative cache entry.
*/
if (covers == dns_rdatatype_any) {
/*
* We're adding an NXDOMAIN negative cache
* entry.
*
* We make all other data stale so that the
* only rdataset that can be found at this
* node is the NXDOMAIN negative cache entry.
*/
topheader->attributes |=
}
goto find_header;
}
} else {
/*
* We're adding something that isn't a
* negative cache entry. Look for an extant
* non-stale NXDOMAIN negative cache entry.
*/
break;
}
/*
* Found one.
*/
/*
* The NXDOMAIN is more trusted.
*/
if (addedrdataset != NULL)
return (DNS_R_UNCHANGED);
}
/*
* The new rdataset is better. Expire the
* NXDOMAIN.
*/
goto find_header;
}
}
}
break;
}
/*
* If header isn't NULL, we've found the right type. There may be
* IGNORE rdatasets between the top of the chain and the first real
* data. We skip over them.
*/
/*
* Deleting an already non-existent rdataset has no effect.
*/
if (header_nx && newheader_nx) {
return (DNS_R_UNCHANGED);
}
/*
* Trying to add an rdataset with lower trust to a cache DB
* has no effect, provided that the cache data isn't stale.
*/
if (addedrdataset != NULL)
return (DNS_R_UNCHANGED);
}
/*
* Don't merge if a nonexistent rdataset is involved.
*/
/*
* If 'merge' is ISC_TRUE, we'll try to create a new rdataset
* that is the union of 'newheader' and 'header'.
*/
if (merge) {
unsigned int flags = 0;
if ((options & DNS_DBADD_EXACT) != 0)
if ((options & DNS_DBADD_EXACTTTL) != 0 &&
if (result == ISC_R_SUCCESS)
(unsigned char *)header,
(unsigned char *)newheader,
(unsigned int)(sizeof(*newheader)),
if (result == ISC_R_SUCCESS) {
/*
* If 'header' has the same serial number as
* we do, we could clean it up now if we knew
* that our caller had no references to it.
* We don't know this, however, so we leave it
* alone. It will get cleaned up when
* clean_zone_node() runs.
*/
} else {
return (result);
}
}
/*
* Don't replace existing NS, A and AAAA RRsets
* in the cache if they are already exist. This
* prevents named being locked to old servers.
*/
!header_nx && !newheader_nx &&
dns_rdataslab_equalx((unsigned char *)header,
(unsigned char *)newheader,
(unsigned int)(sizeof(*newheader)),
/*
* Honour the new ttl if it is less than the
* older one.
*/
if (addedrdataset != NULL)
return (ISC_R_SUCCESS);
}
!header_nx && !newheader_nx &&
dns_rdataslab_equal((unsigned char *)header,
(unsigned char *)newheader,
(unsigned int)(sizeof(*newheader)))) {
/*
* Honour the new ttl if it is less than the
* older one.
*/
if (addedrdataset != NULL)
return (ISC_R_SUCCESS);
}
if (topheader_prev != NULL)
else
if (loading) {
/*
* There are no other references to 'header' when
* loading, so we MAY clean up 'header' now.
* Since we don't generate changed records when
* loading, we MUST clean up 'header' now.
*/
} else {
}
} else {
/*
* No non-IGNORED rdatasets of the given type exist at
* this node.
*/
/*
* If we're trying to delete the type, don't bother.
*/
if (newheader_nx) {
return (DNS_R_UNCHANGED);
}
/*
* We have an list of rdatasets of the given type,
* but they're all marked IGNORE. We simply insert
* the new rdataset at the head of the list.
*
* Ignored rdatasets cannot occur during loading, so
* we INSIST on it.
*/
if (topheader_prev != NULL)
else
} else {
/*
* No rdatasets of the given type exist at the node.
*/
}
}
/*
* Check if the node now contains CNAME and other data.
*/
if (rbtversion != NULL &&
return (DNS_R_CNAMEANDOTHER);
if (addedrdataset != NULL)
return (ISC_R_SUCCESS);
}
static inline isc_boolean_t
{
if (type == dns_rdatatype_dname)
return (ISC_TRUE);
else
return (ISC_FALSE);
} else if (type == dns_rdatatype_dname ||
(type == dns_rdatatype_ns &&
return (ISC_TRUE);
return (ISC_FALSE);
}
static isc_result_t
{
if (rbtversion == NULL) {
if (now == 0)
} else
now = 0;
®ion,
sizeof(rdatasetheader_t));
if (result != ISC_R_SUCCESS)
return (result);
newheader->attributes = 0;
if (rbtversion != NULL) {
now = 0;
} else {
}
/*
* If we're adding a delegation type (e.g. NS or DNAME for a zone,
* just DNAME for the cache), then we need to set the callback bit
* on the node, and to do that we must be holding an exclusive lock
* on the tree.
*/
} else
addedrdataset, now);
if (delegating)
return (result);
}
static isc_result_t
{
unsigned char *subresult;
®ion,
sizeof(rdatasetheader_t));
if (result != ISC_R_SUCCESS)
return (result);
newheader->attributes = 0;
return (ISC_R_NOMEMORY);
}
break;
}
/*
* If header isn't NULL, we've found the right type. There may be
* IGNORE rdatasets between the top of the chain and the first real
* data. We skip over them.
*/
unsigned int flags = 0;
if ((options & DNS_DBSUB_EXACT) != 0) {
}
if (result == ISC_R_SUCCESS)
(unsigned char *)header,
(unsigned char *)newheader,
(unsigned int)(sizeof(*newheader)),
if (result == ISC_R_SUCCESS) {
/*
* We have to set the serial since the rdataslab
* subtraction routine copies the reserved portion of
* header, not newheader.
*/
} else if (result == DNS_R_NXRRSET) {
/*
* This subtraction would remove all of the rdata;
* add a nonexistent header instead.
*/
sizeof(*newheader));
goto unlock;
}
} else {
goto unlock;
}
/*
* If we're here, we want to link newheader in front of
* topheader.
*/
if (topheader_prev != NULL)
else
} else {
/*
* The rdataset doesn't exist, so we don't need to do anything
* to satisfy the deletion request.
*/
if ((options & DNS_DBSUB_EXACT) != 0)
else
}
return (result);
}
static isc_result_t
{
if (type == dns_rdatatype_any)
return (ISC_R_NOTIMPLEMENTED);
return (ISC_R_NOTIMPLEMENTED);
return (ISC_R_NOMEMORY);
if (rbtversion != NULL)
else
return (result);
}
static isc_result_t
/*
* This routine does no node locking. See comments in
* 'load' below for more information on loading and
* locking.
*/
/*
* SOA records are only allowed at top of zone.
*/
return (DNS_R_NOTZONETOP);
if (dns_name_iswildcard(name)) {
/*
* NS record owners cannot legally be wild cards.
*/
return (DNS_R_INVALIDNS);
if (result != ISC_R_SUCCESS)
return (result);
}
return (result);
if (result != ISC_R_EXISTS) {
#ifdef DNS_RBT_USEHASH
#else
#endif
}
®ion,
sizeof(rdatasetheader_t));
if (result != ISC_R_SUCCESS)
return (result);
newheader->attributes = 0;
if (result == ISC_R_SUCCESS &&
else if (result == DNS_R_UNCHANGED)
return (result);
}
static isc_result_t
return (ISC_R_NOMEMORY);
else
== 0);
return (ISC_R_SUCCESS);
}
static isc_boolean_t
if (result == ISC_R_SUCCESS) {
while (result == ISC_R_SUCCESS) {
if (dns_zonekey_iszonekey(&keyrdata)) {
break;
}
}
}
if (!haszonekey)
return (ISC_FALSE);
if (result == ISC_R_SUCCESS) {
if (dns_rdataset_isassociated(&signxtset)) {
}
}
return (hasnxt);
}
static isc_result_t
/*
* If there's a KEY rdataset at the zone origin containing a
* zone key, we consider the zone secure.
*/
return (ISC_R_SUCCESS);
}
static isc_result_t
filename));
}
static void
}
}
static isc_boolean_t
return (secure);
}
static unsigned int
unsigned int count;
return (count);
}
static isc_boolean_t
return (ISC_FALSE);
}
static dns_dbmethods_t zone_methods = {
dump,
};
static dns_dbmethods_t cache_methods = {
dump,
};
#ifdef DNS_RBTDB_VERSION64
#else
#endif
{
int i;
/* Keep the compiler happy. */
return (ISC_R_NOMEMORY);
if (type == dns_dbtype_cache) {
} else if (type == dns_dbtype_stub) {
} else
if (result != ISC_R_SUCCESS) {
"isc_mutex_init() failed: %s",
return (ISC_R_UNEXPECTED);
}
if (result != ISC_R_SUCCESS) {
"isc_rwlock_init() failed: %s",
return (ISC_R_UNEXPECTED);
}
if (rbtdb->node_lock_count == 0)
sizeof(rbtdb_nodelock_t));
for (i = 0; i < (int)(rbtdb->node_lock_count); i++) {
if (result != ISC_R_SUCCESS) {
i--;
while (i >= 0) {
i--;
}
sizeof(rbtdb_nodelock_t));
"isc_mutex_init() failed: %s",
return (ISC_R_UNEXPECTED);
}
}
/*
* Attach to the mctx. The database will persist so long as there
* are references to it, and attaching to the mctx ensures that our
* mctx won't disappear out from under us.
*/
/*
* Make a copy of the origin name.
*/
if (result != ISC_R_SUCCESS) {
return (result);
}
/*
* Make the Red-Black Tree.
*/
if (result != ISC_R_SUCCESS) {
return (result);
}
/*
* In order to set the node callback bit correctly in zone databases,
* we need to know if the node has the origin name of the zone.
* In loading_addrdataset() we could simply compare the new name
* to the origin name, but this is expensive. Also, we don't know the
* node name in addrdataset(), so we need another way of knowing the
* zone's top.
*
* We now explicitly create a node for the zone's origin, and then
* we simply remember the node's address. This is safe, because
* the top-of-zone node can never be deleted, nor can its address
* change.
*/
&rbtdb->origin_node);
if (result != ISC_R_SUCCESS) {
return (result);
}
/*
* We need to give the origin node the right locknum.
*/
#ifdef DNS_RBT_USEHASH
#else
#endif
}
/*
* Misc. Initialization.
*/
rbtdb->attributes = 0;
/*
* Version Initialization.
*/
return (ISC_R_NOMEMORY);
}
return (ISC_R_SUCCESS);
}
/*
* Slabbed Rdataset Methods
*/
static void
}
static isc_result_t
unsigned int count;
if (count == 0) {
return (ISC_R_NOMORE);
}
raw += 2;
/*
* The private4 field is the number of rdata beyond the cursor
* position, so we decrement the total count by one before storing
* it.
*/
count--;
return (ISC_R_SUCCESS);
}
static isc_result_t
unsigned int count;
unsigned int length;
unsigned char *raw;
if (count == 0)
return (ISC_R_NOMORE);
count--;
return (ISC_R_SUCCESS);
}
static void
isc_region_t r;
raw += 2;
}
static void
/*
* Reset iterator state.
*/
}
static unsigned int
unsigned int count;
return (count);
}
/*
* Rdataset Iterator Methods
*/
static void
sizeof(*rbtiterator));
}
static isc_result_t
serial = 1;
} else {
now = 0;
}
do {
/*
* Is this a "this rdataset doesn't exist"
* record? Or is it too old in the cache?
*
* Note: unlike everywhere else, we
* check for now > header->ttl instead
* of now >= header->ttl. This allows
* ANY and SIG queries for 0 TTL
* rdatasets to work.
*/
if (NONEXISTENT(header) ||
break;
} else
break;
}
return (ISC_R_NOMORE);
return (ISC_R_SUCCESS);
}
static isc_result_t
return (ISC_R_NOMORE);
serial = 1;
} else {
now = 0;
}
do {
/*
* Is this a "this rdataset doesn't
* exist" record?
*
* Note: unlike everywhere else, we
* check for now > header->ttl instead
* of now >= header->ttl. This allows
* ANY and SIG queries for 0 TTL
* rdatasets to work.
*/
if ((header->attributes &
RDATASET_ATTR_NONEXISTENT) != 0 ||
break;
} else
break;
}
}
return (ISC_R_NOMORE);
return (ISC_R_SUCCESS);
}
static void
rdataset);
}
/*
* Database Iterator Methods
*/
static inline void
return;
}
static inline void
return;
if (--node->references == 0)
}
static void
int i;
/*
* Note that "%d node of %d in tree" can report things like
* "flush_deletions: 59 nodes of 41 in tree". This means
* That some nodes appear on the deletions list more than
* once. Only the last occurence will actually be deleted.
*/
"flush_deletions: %d nodes of %d in tree",
}
node->references--;
if (node->references == 0)
}
if (was_read_locked) {
} else {
}
}
}
static inline void
}
static void
} else
dns_db_detach(&db);
}
static isc_result_t
origin);
if (result == ISC_R_SUCCESS) {
}
} else {
}
return (result);
}
static isc_result_t
origin);
if (result == ISC_R_SUCCESS) {
}
} else {
}
return (result);
}
static isc_result_t
if (result == ISC_R_SUCCESS) {
if (result == ISC_R_SUCCESS) {
}
} else if (result == DNS_R_PARTIALMATCH)
return (result);
}
static isc_result_t
}
if (result == ISC_R_SUCCESS)
return (result);
}
static isc_result_t
}
if (result == ISC_R_SUCCESS)
return (result);
}
static isc_result_t
{
if (result != ISC_R_SUCCESS)
return (result);
} else
/*
* If the deletion array is full, flush it before trying
* to expire the current node. The current node can't
* fully deleted while the iteration cursor is still on it.
*/
/*
* expirenode() currently always returns success.
*/
node->references++;
}
}
return (result);
}
static isc_result_t
return (ISC_R_SUCCESS);
}
return (ISC_R_SUCCESS);
}
static isc_result_t
}