horok/bind9
1
0
Fork 0
Code Activity
bind9/lib/dns/rbt-cachedb.c
Daniel Baumann f66ff7eae6
Adding upstream version 1:9.20.9. 
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
2025-06-21 13:32:37 +02:00

1722 lines
46 KiB
C
Raw Permalink Blame History

/*
* Copyright (C) Internet Systems Consortium, Inc. ("ISC")
*
* SPDX-License-Identifier: MPL-2.0
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, you can obtain one at https://mozilla.org/MPL/2.0/.
*
* See the COPYRIGHT file distributed with this work for additional
* information regarding copyright ownership.
*/
/*! \file */
#include <inttypes.h>
#include <stdbool.h>
#include <sys/mman.h>
#include <isc/ascii.h>
#include <isc/async.h>
#include <isc/atomic.h>
#include <isc/crc64.h>
#include <isc/file.h>
#include <isc/hash.h>
#include <isc/hashmap.h>
#include <isc/heap.h>
#include <isc/hex.h>
#include <isc/loop.h>
#include <isc/mem.h>
#include <isc/mutex.h>
#include <isc/once.h>
#include <isc/random.h>
#include <isc/refcount.h>
#include <isc/result.h>
#include <isc/rwlock.h>
#include <isc/serial.h>
#include <isc/stdio.h>
#include <isc/string.h>
#include <isc/time.h>
#include <isc/urcu.h>
#include <isc/util.h>
#include <dns/callbacks.h>
#include <dns/db.h>
#include <dns/dbiterator.h>
#include <dns/fixedname.h>
#include <dns/log.h>
#include <dns/masterdump.h>
#include <dns/nsec.h>
#include <dns/nsec3.h>
#include <dns/rbt.h>
#include <dns/rdata.h>
#include <dns/rdataset.h>
#include <dns/rdatasetiter.h>
#include <dns/rdataslab.h>
#include <dns/rdatastruct.h>
#include <dns/stats.h>
#include <dns/time.h>
#include <dns/view.h>
#include <dns/zone.h>
#include <dns/zonekey.h>
#include "db_p.h"
#include "rbtdb_p.h"
#define CHECK(op) \
do { \
result = (op); \
if (result != ISC_R_SUCCESS) \
goto failure; \
} while (0)
/*%
* Whether to rate-limit updating the LRU to avoid possible thread contention.
* Updating LRU requires write locking, so we don't do it every time the
* record is touched - only after some time passes.
*/
#ifndef DNS_RBTDB_LIMITLRUUPDATE
#define DNS_RBTDB_LIMITLRUUPDATE 1
#endif
/*% Time after which we update LRU for glue records, 5 minutes */
#define DNS_RBTDB_LRUUPDATE_GLUE 300
/*% Time after which we update LRU for all other records, 10 minutes */
#define DNS_RBTDB_LRUUPDATE_REGULAR 600
#define EXISTS(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_NONEXISTENT) == 0)
#define NONEXISTENT(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_NONEXISTENT) != 0)
#define NXDOMAIN(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_NXDOMAIN) != 0)
#define STALE(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_STALE) != 0)
#define NEGATIVE(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_NEGATIVE) != 0)
#define ZEROTTL(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_ZEROTTL) != 0)
#define ANCIENT(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_ANCIENT) != 0)
#define STATCOUNT(header) \
((atomic_load_acquire(&(header)->attributes) & \
DNS_SLABHEADERATTR_STATCOUNT) != 0)
#define STALE_TTL(header, rbtdb) \
(NXDOMAIN(header) ? 0 : rbtdb->common.serve_stale_ttl)
#define ACTIVE(header, now) \
(((header)->ttl > (now)) || ((header)->ttl == (now) && ZEROTTL(header)))
#define KEEPSTALE(rbtdb) ((rbtdb)->common.serve_stale_ttl > 0)
/*%
* Routines for LRU-based cache management.
*/
/*%
* See if a given cache entry that is being reused needs to be updated
* in the LRU-list. From the LRU management point of view, this function is
* expected to return true for almost all cases. When used with threads,
* however, this may cause a non-negligible performance penalty because a
* writer lock will have to be acquired before updating the list.
* If DNS_RBTDB_LIMITLRUUPDATE is defined to be non 0 at compilation time, this
* function returns true if the entry has not been updated for some period of
* time. We differentiate the NS or glue address case and the others since
* experiments have shown that the former tends to be accessed relatively
* infrequently and the cost of cache miss is higher (e.g., a missing NS records
* may cause external queries at a higher level zone, involving more
* transactions).
*
* Caller must hold the node (read or write) lock.
*/
static bool
need_headerupdate(dns_slabheader_t *header, isc_stdtime_t now) {
if (DNS_SLABHEADER_GETATTR(header, (DNS_SLABHEADERATTR_NONEXISTENT |
DNS_SLABHEADERATTR_ANCIENT |
DNS_SLABHEADERATTR_ZEROTTL)) != 0)
{
return false;
}
#if DNS_RBTDB_LIMITLRUUPDATE
if (header->type == dns_rdatatype_ns ||
(header->trust == dns_trust_glue &&
(header->type == dns_rdatatype_a ||
header->type == dns_rdatatype_aaaa)))
{
/*
* Glue records are updated if at least DNS_RBTDB_LRUUPDATE_GLUE
* seconds have passed since the previous update time.
*/
return header->last_used + DNS_RBTDB_LRUUPDATE_GLUE <= now;
}
/*
* Other records are updated if DNS_RBTDB_LRUUPDATE_REGULAR seconds
* have passed.
*/
return header->last_used + DNS_RBTDB_LRUUPDATE_REGULAR <= now;
#else
UNUSED(now);
return true;
#endif /* if DNS_RBTDB_LIMITLRUUPDATE */
}
/*%
* Update the timestamp of a given cache entry and move it to the head
* of the corresponding LRU list.
*
* Caller must hold the node (write) lock.
*
* Note that the we do NOT touch the heap here, as the TTL has not changed.
*/
static void
update_header(dns_rbtdb_t *rbtdb, dns_slabheader_t *header, isc_stdtime_t now) {
INSIST(IS_CACHE(rbtdb));
/* To be checked: can we really assume this? XXXMLG */
INSIST(ISC_LINK_LINKED(header, link));
ISC_LIST_UNLINK(rbtdb->lru[RBTDB_HEADERNODE(header)->locknum], header,
link);
header->last_used = now;
ISC_LIST_PREPEND(rbtdb->lru[RBTDB_HEADERNODE(header)->locknum], header,
link);
}
/*
* 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
*
* For zone databases the node for the origin of the zone MUST NOT be deleted.
*/
/*
* DB Routines
*/
static void
update_cachestats(dns_rbtdb_t *rbtdb, isc_result_t result) {
INSIST(IS_CACHE(rbtdb));
if (rbtdb->cachestats == NULL) {
return;
}
switch (result) {
case DNS_R_COVERINGNSEC:
isc_stats_increment(rbtdb->cachestats,
dns_cachestatscounter_coveringnsec);
FALLTHROUGH;
case ISC_R_SUCCESS:
case DNS_R_CNAME:
case DNS_R_DNAME:
case DNS_R_DELEGATION:
case DNS_R_NCACHENXDOMAIN:
case DNS_R_NCACHENXRRSET:
isc_stats_increment(rbtdb->cachestats,
dns_cachestatscounter_hits);
break;
default:
isc_stats_increment(rbtdb->cachestats,
dns_cachestatscounter_misses);
}
}
static void
clean_stale_headers(dns_slabheader_t *top) {
dns_slabheader_t *d = NULL, *down_next = NULL;
for (d = top->down; d != NULL; d = down_next) {
down_next = d->down;
dns_slabheader_destroy(&d);
}
top->down = NULL;
}
static isc_result_t
setup_delegation(rbtdb_search_t *search, dns_dbnode_t **nodep,
dns_name_t *foundname, dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
dns_name_t *zcname = NULL;
dns_typepair_t type;
dns_rbtnode_t *node = NULL;
REQUIRE(search != NULL);
REQUIRE(search->zonecut != NULL);
REQUIRE(search->zonecut_header != NULL);
/*
* The caller MUST NOT be holding any node locks.
*/
node = search->zonecut;
type = search->zonecut_header->type;
/*
* 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 (foundname != NULL && search->copy_name) {
zcname = dns_fixedname_name(&search->zonecut_name);
dns_name_copy(zcname, foundname);
}
if (nodep != NULL) {
/*
* 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.
*/
*nodep = node;
search->need_cleanup = false;
}
if (rdataset != NULL) {
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
NODE_RDLOCK(&(search->rbtdb->node_locks[node->locknum].lock),
&nlocktype);
dns__rbtdb_bindrdataset(search->rbtdb, node,
search->zonecut_header, search->now,
isc_rwlocktype_read,
rdataset DNS__DB_FLARG_PASS);
if (sigrdataset != NULL && search->zonecut_sigheader != NULL) {
dns__rbtdb_bindrdataset(
search->rbtdb, node, search->zonecut_sigheader,
search->now, isc_rwlocktype_read,
sigrdataset DNS__DB_FLARG_PASS);
}
NODE_UNLOCK(&(search->rbtdb->node_locks[node->locknum].lock),
&nlocktype);
}
if (type == dns_rdatatype_dname) {
return DNS_R_DNAME;
}
return DNS_R_DELEGATION;
}
static bool
check_stale_header(dns_rbtnode_t *node, dns_slabheader_t *header,
isc_rwlocktype_t *nlocktypep, isc_rwlock_t *lock,
rbtdb_search_t *search, dns_slabheader_t **header_prev) {
if (!ACTIVE(header, search->now)) {
dns_ttl_t stale = header->ttl +
STALE_TTL(header, search->rbtdb);
/*
* If this data is in the stale window keep it and if
* DNS_DBFIND_STALEOK is not set we tell the caller to
* skip this record. We skip the records with ZEROTTL
* (these records should not be cached anyway).
*/
DNS_SLABHEADER_CLRATTR(header, DNS_SLABHEADERATTR_STALE_WINDOW);
if (!ZEROTTL(header) && KEEPSTALE(search->rbtdb) &&
stale > search->now)
{
dns__rbtdb_mark(header, DNS_SLABHEADERATTR_STALE);
*header_prev = header;
/*
* If DNS_DBFIND_STALESTART is set then it means we
* failed to resolve the name during recursion, in
* this case we mark the time in which the refresh
* failed.
*/
if ((search->options & DNS_DBFIND_STALESTART) != 0) {
atomic_store_release(
&header->last_refresh_fail_ts,
search->now);
} else if ((search->options &
DNS_DBFIND_STALEENABLED) != 0 &&
search->now <
(atomic_load_acquire(
&header->last_refresh_fail_ts) +
search->rbtdb->serve_stale_refresh))
{
/*
* If we are within interval between last
* refresh failure time + 'stale-refresh-time',
* then don't skip this stale entry but use it
* instead.
*/
DNS_SLABHEADER_SETATTR(
header,
DNS_SLABHEADERATTR_STALE_WINDOW);
return false;
} else if ((search->options &
DNS_DBFIND_STALETIMEOUT) != 0)
{
/*
* We want stale RRset due to timeout, so we
* don't skip it.
*/
return false;
}
return (search->options & DNS_DBFIND_STALEOK) == 0;
}
/*
* This rdataset is stale. If no one else is using the
* node, we can clean it up right now, otherwise we mark
* it as ancient, and the node as dirty, so it will get
* cleaned up later.
*/
if ((header->ttl < search->now - RBTDB_VIRTUAL) &&
(*nlocktypep == isc_rwlocktype_write ||
NODE_TRYUPGRADE(lock, nlocktypep) == ISC_R_SUCCESS))
{
/*
* We update the node's status only when we can
* get write access; otherwise, we leave others
* to this work. Periodical cleaning will
* eventually take the job as the last resort.
* We won't downgrade the lock, since other
* rdatasets are probably stale, too.
*/
if (isc_refcount_current(&node->references) == 0) {
/*
* header->down can be non-NULL if the
* refcount has just decremented to 0
* but dns__rbtnode_release() has not
* performed clean_cache_node(), in
* which case we need to purge the stale
* headers first.
*/
clean_stale_headers(header);
if (*header_prev != NULL) {
(*header_prev)->next = header->next;
} else {
node->data = header->next;
}
dns_slabheader_destroy(&header);
} else {
dns__rbtdb_mark_ancient(header);
*header_prev = header;
}
} else {
*header_prev = header;
}
return true;
}
return false;
}
static isc_result_t
cache_zonecut_callback(dns_rbtnode_t *node, dns_name_t *name,
void *arg DNS__DB_FLARG) {
rbtdb_search_t *search = arg;
dns_slabheader_t *header = NULL;
dns_slabheader_t *header_prev = NULL, *header_next = NULL;
dns_slabheader_t *dname_header = NULL, *sigdname_header = NULL;
isc_result_t result;
isc_rwlock_t *lock = NULL;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
REQUIRE(search->zonecut == NULL);
/*
* Keep compiler silent.
*/
UNUSED(name);
lock = &(search->rbtdb->node_locks[node->locknum].lock);
NODE_RDLOCK(lock, &nlocktype);
/*
* Look for a DNAME or RRSIG DNAME rdataset.
*/
for (header = node->data; header != NULL; header = header_next) {
header_next = header->next;
if (check_stale_header(node, header, &nlocktype, lock, search,
&header_prev))
{
/* Do nothing. */
} else if (header->type == dns_rdatatype_dname &&
EXISTS(header) && !ANCIENT(header))
{
dname_header = header;
header_prev = header;
} else if (header->type == DNS_SIGTYPE(dns_rdatatype_dname) &&
EXISTS(header) && !ANCIENT(header))
{
sigdname_header = header;
header_prev = header;
} else {
header_prev = header;
}
}
if (dname_header != NULL &&
(!DNS_TRUST_PENDING(dname_header->trust) ||
(search->options & DNS_DBFIND_PENDINGOK) != 0))
{
/*
* We increment the reference count on node to ensure that
* search->zonecut_header will still be valid later.
*/
dns__rbtnode_acquire(search->rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
search->zonecut = node;
search->zonecut_header = dname_header;
search->zonecut_sigheader = sigdname_header;
search->need_cleanup = true;
result = DNS_R_PARTIALMATCH;
} else {
result = DNS_R_CONTINUE;
}
NODE_UNLOCK(lock, &nlocktype);
return result;
}
static isc_result_t
find_deepest_zonecut(rbtdb_search_t *search, dns_rbtnode_t *node,
dns_dbnode_t **nodep, dns_name_t *foundname,
dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
unsigned int i;
isc_result_t result = ISC_R_NOTFOUND;
dns_name_t name;
dns_rbtdb_t *rbtdb = NULL;
bool done;
/*
* Caller must be holding the tree lock.
*/
rbtdb = search->rbtdb;
i = search->chain.level_matches;
done = false;
do {
dns_slabheader_t *header = NULL;
dns_slabheader_t *header_prev = NULL, *header_next = NULL;
dns_slabheader_t *found = NULL, *foundsig = NULL;
isc_rwlock_t *lock = &rbtdb->node_locks[node->locknum].lock;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
NODE_RDLOCK(lock, &nlocktype);
/*
* Look for NS and RRSIG NS rdatasets.
*/
for (header = node->data; header != NULL; header = header_next)
{
header_next = header->next;
if (check_stale_header(node, header, &nlocktype, lock,
search, &header_prev))
{
/* Do nothing. */
} else if (EXISTS(header) && !ANCIENT(header)) {
/*
* We've found an extant rdataset. See if
* we're interested in it.
*/
if (header->type == dns_rdatatype_ns) {
found = header;
if (foundsig != NULL) {
break;
}
} else if (header->type ==
DNS_SIGTYPE(dns_rdatatype_ns))
{
foundsig = header;
if (found != NULL) {
break;
}
}
header_prev = header;
} else {
header_prev = header;
}
}
if (found != NULL) {
/*
* 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.
*/
if (foundname != NULL) {
dns_name_init(&name, NULL);
dns_rbt_namefromnode(node, &name);
dns_name_copy(&name, foundname);
while (i > 0) {
dns_rbtnode_t *level_node =
search->chain.levels[--i];
dns_name_init(&name, NULL);
dns_rbt_namefromnode(level_node, &name);
result = dns_name_concatenate(
foundname, &name, foundname,
NULL);
if (result != ISC_R_SUCCESS) {
if (nodep != NULL) {
*nodep = NULL;
}
goto node_exit;
}
}
}
result = DNS_R_DELEGATION;
if (nodep != NULL) {
dns__rbtnode_acquire(
search->rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
*nodep = node;
}
dns__rbtdb_bindrdataset(search->rbtdb, node, found,
search->now, nlocktype,
rdataset DNS__DB_FLARG_PASS);
if (foundsig != NULL) {
dns__rbtdb_bindrdataset(
search->rbtdb, node, foundsig,
search->now, nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
}
if (need_headerupdate(found, search->now) ||
(foundsig != NULL &&
need_headerupdate(foundsig, search->now)))
{
if (nlocktype != isc_rwlocktype_write) {
NODE_FORCEUPGRADE(lock, &nlocktype);
POST(nlocktype);
}
if (need_headerupdate(found, search->now)) {
update_header(search->rbtdb, found,
search->now);
}
if (foundsig != NULL &&
need_headerupdate(foundsig, search->now))
{
update_header(search->rbtdb, foundsig,
search->now);
}
}
}
node_exit:
NODE_UNLOCK(lock, &nlocktype);
if (found == NULL && i > 0) {
i--;
node = search->chain.levels[i];
} else {
done = true;
}
} while (!done);
return result;
}
/*
* Look for a potentially covering NSEC in the cache where `name`
* is known not to exist. This uses the auxiliary NSEC tree to find
* the potential NSEC owner. If found, we update 'foundname', 'nodep',
* 'rdataset' and 'sigrdataset', and return DNS_R_COVERINGNSEC.
* Otherwise, return ISC_R_NOTFOUND.
*/
static isc_result_t
find_coveringnsec(rbtdb_search_t *search, const dns_name_t *name,
dns_dbnode_t **nodep, isc_stdtime_t now,
dns_name_t *foundname, dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
dns_fixedname_t fprefix, forigin, ftarget, fixed;
dns_name_t *prefix = NULL, *origin = NULL;
dns_name_t *target = NULL, *fname = NULL;
dns_rbtnode_t *node = NULL;
dns_rbtnodechain_t chain;
isc_result_t result;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
isc_rwlock_t *lock = NULL;
dns_typepair_t matchtype, sigmatchtype;
dns_slabheader_t *found = NULL, *foundsig = NULL;
dns_slabheader_t *header = NULL;
dns_slabheader_t *header_next = NULL, *header_prev = NULL;
/*
* Look for the node in the auxilary tree.
*/
dns_rbtnodechain_init(&chain);
target = dns_fixedname_initname(&ftarget);
result = dns_rbt_findnode(search->rbtdb->nsec, name, target, &node,
&chain, DNS_RBTFIND_EMPTYDATA, NULL, NULL);
if (result != DNS_R_PARTIALMATCH) {
dns_rbtnodechain_reset(&chain);
return ISC_R_NOTFOUND;
}
prefix = dns_fixedname_initname(&fprefix);
origin = dns_fixedname_initname(&forigin);
target = dns_fixedname_initname(&ftarget);
fname = dns_fixedname_initname(&fixed);
matchtype = DNS_TYPEPAIR_VALUE(dns_rdatatype_nsec, 0);
sigmatchtype = DNS_SIGTYPE(dns_rdatatype_nsec);
/*
* Extract predecessor from chain.
*/
result = dns_rbtnodechain_current(&chain, prefix, origin, NULL);
dns_rbtnodechain_reset(&chain);
if (result != ISC_R_SUCCESS && result != DNS_R_NEWORIGIN) {
return ISC_R_NOTFOUND;
}
result = dns_name_concatenate(prefix, origin, target, NULL);
if (result != ISC_R_SUCCESS) {
return ISC_R_NOTFOUND;
}
/*
* Lookup the predecessor in the main tree.
*/
node = NULL;
result = dns_rbt_findnode(search->rbtdb->tree, target, fname, &node,
NULL, DNS_RBTFIND_EMPTYDATA, NULL, NULL);
if (result != ISC_R_SUCCESS) {
return ISC_R_NOTFOUND;
}
lock = &(search->rbtdb->node_locks[node->locknum].lock);
NODE_RDLOCK(lock, &nlocktype);
for (header = node->data; header != NULL; header = header_next) {
header_next = header->next;
if (check_stale_header(node, header, &nlocktype, lock, search,
&header_prev))
{
continue;
}
if (NONEXISTENT(header) || DNS_TYPEPAIR_TYPE(header->type) == 0)
{
header_prev = header;
continue;
}
if (header->type == matchtype) {
found = header;
if (foundsig != NULL) {
break;
}
} else if (header->type == sigmatchtype) {
foundsig = header;
if (found != NULL) {
break;
}
}
header_prev = header;
}
if (found != NULL) {
dns__rbtdb_bindrdataset(search->rbtdb, node, found, now,
nlocktype, rdataset DNS__DB_FLARG_PASS);
if (foundsig != NULL) {
dns__rbtdb_bindrdataset(search->rbtdb, node, foundsig,
now, nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
}
dns__rbtnode_acquire(search->rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
dns_name_copy(fname, foundname);
*nodep = node;
result = DNS_R_COVERINGNSEC;
} else {
result = ISC_R_NOTFOUND;
}
NODE_UNLOCK(lock, &nlocktype);
return result;
}
static isc_result_t
cache_find(dns_db_t *db, const dns_name_t *name, dns_dbversion_t *version,
dns_rdatatype_t type, unsigned int options, isc_stdtime_t now,
dns_dbnode_t **nodep, dns_name_t *foundname,
dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
dns_rbtnode_t *node = NULL;
isc_result_t result;
rbtdb_search_t search;
bool cname_ok = true;
bool found_noqname = false;
bool all_negative = true;
bool empty_node;
isc_rwlock_t *lock = NULL;
isc_rwlocktype_t tlocktype = isc_rwlocktype_none;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
dns_slabheader_t *header = NULL;
dns_slabheader_t *header_prev = NULL, *header_next = NULL;
dns_slabheader_t *found = NULL, *nsheader = NULL;
dns_slabheader_t *foundsig = NULL, *nssig = NULL, *cnamesig = NULL;
dns_slabheader_t *update = NULL, *updatesig = NULL;
dns_slabheader_t *nsecheader = NULL, *nsecsig = NULL;
dns_typepair_t sigtype, negtype;
UNUSED(version);
REQUIRE(VALID_RBTDB((dns_rbtdb_t *)db));
REQUIRE(version == NULL);
if (now == 0) {
now = isc_stdtime_now();
}
search = (rbtdb_search_t){
.rbtdb = (dns_rbtdb_t *)db,
.serial = 1,
.options = options,
.now = now,
};
dns_fixedname_init(&search.zonecut_name);
dns_rbtnodechain_init(&search.chain);
TREE_RDLOCK(&search.rbtdb->tree_lock, &tlocktype);
/*
* 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.
*/
result = dns_rbt_findnode(search.rbtdb->tree, name, foundname, &node,
&search.chain, DNS_RBTFIND_EMPTYDATA,
cache_zonecut_callback, &search);
if (result == DNS_R_PARTIALMATCH) {
/*
* If dns_rbt_findnode discovered a covering DNAME skip
* looking for a covering NSEC.
*/
if ((search.options & DNS_DBFIND_COVERINGNSEC) != 0 &&
(search.zonecut_header == NULL ||
search.zonecut_header->type != dns_rdatatype_dname))
{
result = find_coveringnsec(
&search, name, nodep, now, foundname, rdataset,
sigrdataset DNS__DB_FLARG_PASS);
if (result == DNS_R_COVERINGNSEC) {
goto tree_exit;
}
}
if (search.zonecut != NULL) {
result = setup_delegation(
&search, nodep, foundname, rdataset,
sigrdataset DNS__DB_FLARG_PASS);
goto tree_exit;
} else {
find_ns:
result = find_deepest_zonecut(
&search, node, nodep, foundname, rdataset,
sigrdataset DNS__DB_FLARG_PASS);
goto tree_exit;
}
} else if (result != ISC_R_SUCCESS) {
goto tree_exit;
}
/*
* Certain DNSSEC types are not subject to CNAME matching
* (RFC4035, section 2.5 and RFC3007).
*
* We don't check for RRSIG, because we don't store RRSIG records
* directly.
*/
if (type == dns_rdatatype_key || type == dns_rdatatype_nsec) {
cname_ok = false;
}
/*
* We now go looking for rdata...
*/
lock = &(search.rbtdb->node_locks[node->locknum].lock);
NODE_RDLOCK(lock, &nlocktype);
/*
* These pointers need to be reset here in case we did
* 'goto find_ns' from somewhere below.
*/
found = NULL;
foundsig = NULL;
sigtype = DNS_SIGTYPE(type);
negtype = DNS_TYPEPAIR_VALUE(0, type);
nsheader = NULL;
nsecheader = NULL;
nssig = NULL;
nsecsig = NULL;
cnamesig = NULL;
empty_node = true;
header_prev = NULL;
for (header = node->data; header != NULL; header = header_next) {
header_next = header->next;
if (check_stale_header(node, header, &nlocktype, lock, &search,
&header_prev))
{
/* Do nothing. */
} else if (EXISTS(header) && !ANCIENT(header)) {
/*
* We now know that there is at least one active
* non-stale rdataset at this node.
*/
empty_node = false;
if (header->noqname != NULL &&
header->trust == dns_trust_secure)
{
found_noqname = true;
}
if (!NEGATIVE(header)) {
all_negative = false;
}
/*
* If we found a type we were looking for, remember
* it.
*/
if (header->type == type ||
(type == dns_rdatatype_any &&
DNS_TYPEPAIR_TYPE(header->type) != 0) ||
(cname_ok && header->type == dns_rdatatype_cname))
{
/*
* We've found the answer.
*/
found = header;
if (header->type == dns_rdatatype_cname &&
cname_ok)
{
/*
* If we've already got the
* CNAME RRSIG, use it.
*/
if (cnamesig != NULL) {
foundsig = cnamesig;
} else {
sigtype = DNS_SIGTYPE(
dns_rdatatype_cname);
}
}
} else if (header->type == sigtype) {
/*
* We've found the RRSIG rdataset for our
* target type. Remember it.
*/
foundsig = header;
} else if (header->type == RDATATYPE_NCACHEANY ||
header->type == negtype)
{
/*
* We've found a negative cache entry.
*/
found = header;
} else if (header->type == dns_rdatatype_ns) {
/*
* Remember a NS rdataset even if we're
* not specifically looking for it, because
* we might need it later.
*/
nsheader = header;
} else if (header->type ==
DNS_SIGTYPE(dns_rdatatype_ns))
{
/*
* If we need the NS rdataset, we'll also
* need its signature.
*/
nssig = header;
} else if (header->type == dns_rdatatype_nsec) {
nsecheader = header;
} else if (header->type ==
DNS_SIGTYPE(dns_rdatatype_nsec))
{
nsecsig = header;
} else if (cname_ok &&
header->type ==
DNS_SIGTYPE(dns_rdatatype_cname))
{
/*
* If we get a CNAME match, we'll also need
* its signature.
*/
cnamesig = header;
}
header_prev = header;
} else {
header_prev = header;
}
}
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.
*/
NODE_UNLOCK(lock, &nlocktype);
if ((search.options & DNS_DBFIND_COVERINGNSEC) != 0) {
result = find_coveringnsec(
&search, name, nodep, now, foundname, rdataset,
sigrdataset DNS__DB_FLARG_PASS);
if (result == DNS_R_COVERINGNSEC) {
goto tree_exit;
}
}
goto find_ns;
}
/*
* If we didn't find what we were looking for...
*/
if (found == NULL ||
(DNS_TRUST_ADDITIONAL(found->trust) &&
((options & DNS_DBFIND_ADDITIONALOK) == 0)) ||
(found->trust == dns_trust_glue &&
((options & DNS_DBFIND_GLUEOK) == 0)) ||
(DNS_TRUST_PENDING(found->trust) &&
((options & DNS_DBFIND_PENDINGOK) == 0)))
{
/*
* Return covering NODATA NSEC record.
*/
if ((search.options & DNS_DBFIND_COVERINGNSEC) != 0 &&
nsecheader != NULL)
{
if (nodep != NULL) {
dns__rbtnode_acquire(
search.rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
*nodep = node;
}
dns__rbtdb_bindrdataset(search.rbtdb, node, nsecheader,
search.now, nlocktype,
rdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(nsecheader, search.now)) {
update = nsecheader;
}
if (nsecsig != NULL) {
dns__rbtdb_bindrdataset(
search.rbtdb, node, nsecsig, search.now,
nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(nsecsig, search.now)) {
updatesig = nsecsig;
}
}
result = DNS_R_COVERINGNSEC;
goto node_exit;
}
/*
* This name was from a wild card. Look for a covering NSEC.
*/
if (found == NULL && (found_noqname || all_negative) &&
(search.options & DNS_DBFIND_COVERINGNSEC) != 0)
{
NODE_UNLOCK(lock, &nlocktype);
result = find_coveringnsec(
&search, name, nodep, now, foundname, rdataset,
sigrdataset DNS__DB_FLARG_PASS);
if (result == DNS_R_COVERINGNSEC) {
goto tree_exit;
}
goto find_ns;
}
/*
* If there is an NS rdataset at this node, then this is the
* deepest zone cut.
*/
if (nsheader != NULL) {
if (nodep != NULL) {
dns__rbtnode_acquire(
search.rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
*nodep = node;
}
dns__rbtdb_bindrdataset(search.rbtdb, node, nsheader,
search.now, nlocktype,
rdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(nsheader, search.now)) {
update = nsheader;
}
if (nssig != NULL) {
dns__rbtdb_bindrdataset(
search.rbtdb, node, nssig, search.now,
nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(nssig, search.now)) {
updatesig = nssig;
}
}
result = DNS_R_DELEGATION;
goto node_exit;
}
/*
* Go find the deepest zone cut.
*/
NODE_UNLOCK(lock, &nlocktype);
goto find_ns;
}
/*
* We found what we were looking for, or we found a CNAME.
*/
if (nodep != NULL) {
dns__rbtnode_acquire(search.rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
*nodep = node;
}
if (NEGATIVE(found)) {
/*
* We found a negative cache entry.
*/
if (NXDOMAIN(found)) {
result = DNS_R_NCACHENXDOMAIN;
} else {
result = DNS_R_NCACHENXRRSET;
}
} else if (type != found->type && type != dns_rdatatype_any &&
found->type == dns_rdatatype_cname)
{
/*
* 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.
*/
result = DNS_R_CNAME;
} else {
/*
* An ordinary successful query!
*/
result = ISC_R_SUCCESS;
}
if (type != dns_rdatatype_any || result == DNS_R_NCACHENXDOMAIN ||
result == DNS_R_NCACHENXRRSET)
{
dns__rbtdb_bindrdataset(search.rbtdb, node, found, search.now,
nlocktype, rdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(found, search.now)) {
update = found;
}
if (!NEGATIVE(found) && foundsig != NULL) {
dns__rbtdb_bindrdataset(search.rbtdb, node, foundsig,
search.now, nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
if (need_headerupdate(foundsig, search.now)) {
updatesig = foundsig;
}
}
}
node_exit:
if ((update != NULL || updatesig != NULL) &&
nlocktype != isc_rwlocktype_write)
{
NODE_FORCEUPGRADE(lock, &nlocktype);
POST(nlocktype);
}
if (update != NULL && need_headerupdate(update, search.now)) {
update_header(search.rbtdb, update, search.now);
}
if (updatesig != NULL && need_headerupdate(updatesig, search.now)) {
update_header(search.rbtdb, updatesig, search.now);
}
NODE_UNLOCK(lock, &nlocktype);
tree_exit:
TREE_UNLOCK(&search.rbtdb->tree_lock, &tlocktype);
/*
* If we found a zonecut but aren't going to use it, we have to
* let go of it.
*/
if (search.need_cleanup) {
node = search.zonecut;
INSIST(node != NULL);
lock = &(search.rbtdb->node_locks[node->locknum].lock);
NODE_RDLOCK(lock, &nlocktype);
dns__rbtnode_release(search.rbtdb, node, 0, &nlocktype,
&tlocktype, true,
false DNS__DB_FLARG_PASS);
NODE_UNLOCK(lock, &nlocktype);
INSIST(tlocktype == isc_rwlocktype_none);
}
dns_rbtnodechain_reset(&search.chain);
update_cachestats(search.rbtdb, result);
return result;
}
static isc_result_t
cache_findzonecut(dns_db_t *db, const dns_name_t *name, unsigned int options,
isc_stdtime_t now, dns_dbnode_t **nodep,
dns_name_t *foundname, dns_name_t *dcname,
dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
dns_rbtnode_t *node = NULL;
isc_rwlock_t *lock = NULL;
isc_result_t result;
rbtdb_search_t search;
dns_slabheader_t *header = NULL;
dns_slabheader_t *header_prev = NULL, *header_next = NULL;
dns_slabheader_t *found = NULL, *foundsig = NULL;
unsigned int rbtoptions = DNS_RBTFIND_EMPTYDATA;
isc_rwlocktype_t tlocktype = isc_rwlocktype_none;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
bool dcnull = (dcname == NULL);
REQUIRE(VALID_RBTDB((dns_rbtdb_t *)db));
if (now == 0) {
now = isc_stdtime_now();
}
search = (rbtdb_search_t){
.rbtdb = (dns_rbtdb_t *)db,
.serial = 1,
.options = options,
.now = now,
};
dns_fixedname_init(&search.zonecut_name);
dns_rbtnodechain_init(&search.chain);
if (dcnull) {
dcname = foundname;
}
if ((options & DNS_DBFIND_NOEXACT) != 0) {
rbtoptions |= DNS_RBTFIND_NOEXACT;
}
TREE_RDLOCK(&search.rbtdb->tree_lock, &tlocktype);
/*
* Search down from the root of the tree.
*/
result = dns_rbt_findnode(search.rbtdb->tree, name, dcname, &node,
&search.chain, rbtoptions, NULL, &search);
if (result == DNS_R_PARTIALMATCH) {
result = find_deepest_zonecut(&search, node, nodep, foundname,
rdataset,
sigrdataset DNS__DB_FLARG_PASS);
goto tree_exit;
} else if (result != ISC_R_SUCCESS) {
goto tree_exit;
} else if (!dcnull) {
dns_name_copy(dcname, foundname);
}
/*
* We now go looking for an NS rdataset at the node.
*/
lock = &(search.rbtdb->node_locks[node->locknum].lock);
NODE_RDLOCK(lock, &nlocktype);
for (header = node->data; header != NULL; header = header_next) {
header_next = header->next;
bool ns = (header->type == dns_rdatatype_ns ||
header->type == DNS_SIGTYPE(dns_rdatatype_ns));
if (check_stale_header(node, header, &nlocktype, lock, &search,
&header_prev))
{
if (ns) {
/*
* We found a cached NS, but was either
* ancient or it was stale and serve-stale
* is disabled, so this node can't be used
* as a zone cut we know about. Instead we
* bail out and call find_deepest_zonecut()
* below.
*/
break;
}
} else if (EXISTS(header) && !ANCIENT(header)) {
if (header->type == dns_rdatatype_ns) {
found = header;
if (foundsig != NULL) {
break;
}
} else if (header->type ==
DNS_SIGTYPE(dns_rdatatype_ns))
{
foundsig = header;
if (found != NULL) {
break;
}
}
header_prev = header;
} else {
header_prev = header;
}
}
if (found == NULL) {
/*
* No active NS records found. Call find_deepest_zonecut()
* to look for them in nodes above this one.
*/
NODE_UNLOCK(lock, &nlocktype);
result = find_deepest_zonecut(&search, node, nodep, foundname,
rdataset,
sigrdataset DNS__DB_FLARG_PASS);
dns_name_copy(foundname, dcname);
goto tree_exit;
}
if (nodep != NULL) {
dns__rbtnode_acquire(search.rbtdb, node,
nlocktype DNS__DB_FLARG_PASS);
*nodep = node;
}
dns__rbtdb_bindrdataset(search.rbtdb, node, found, search.now,
nlocktype, rdataset DNS__DB_FLARG_PASS);
if (foundsig != NULL) {
dns__rbtdb_bindrdataset(search.rbtdb, node, foundsig,
search.now, nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
}
if (need_headerupdate(found, search.now) ||
(foundsig != NULL && need_headerupdate(foundsig, search.now)))
{
if (nlocktype != isc_rwlocktype_write) {
NODE_FORCEUPGRADE(lock, &nlocktype);
POST(nlocktype);
}
if (need_headerupdate(found, search.now)) {
update_header(search.rbtdb, found, search.now);
}
if (foundsig != NULL && need_headerupdate(foundsig, search.now))
{
update_header(search.rbtdb, foundsig, search.now);
}
}
NODE_UNLOCK(lock, &nlocktype);
tree_exit:
TREE_UNLOCK(&search.rbtdb->tree_lock, &tlocktype);
INSIST(!search.need_cleanup);
dns_rbtnodechain_reset(&search.chain);
if (result == DNS_R_DELEGATION) {
result = ISC_R_SUCCESS;
}
return result;
}
static isc_result_t
cache_findrdataset(dns_db_t *db, dns_dbnode_t *node, dns_dbversion_t *version,
dns_rdatatype_t type, dns_rdatatype_t covers,
isc_stdtime_t now, dns_rdataset_t *rdataset,
dns_rdataset_t *sigrdataset DNS__DB_FLARG) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
dns_slabheader_t *header = NULL, *header_next = NULL;
dns_slabheader_t *found = NULL, *foundsig = NULL;
dns_typepair_t matchtype, sigmatchtype, negtype;
isc_result_t result;
isc_rwlock_t *lock = NULL;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(type != dns_rdatatype_any);
UNUSED(version);
result = ISC_R_SUCCESS;
if (now == 0) {
now = isc_stdtime_now();
}
lock = &rbtdb->node_locks[rbtnode->locknum].lock;
NODE_RDLOCK(lock, &nlocktype);
matchtype = DNS_TYPEPAIR_VALUE(type, covers);
negtype = DNS_TYPEPAIR_VALUE(0, type);
if (covers == 0) {
sigmatchtype = DNS_SIGTYPE(type);
} else {
sigmatchtype = 0;
}
for (header = rbtnode->data; header != NULL; header = header_next) {
header_next = header->next;
if (!ACTIVE(header, now)) {
if ((header->ttl + STALE_TTL(header, rbtdb) <
now - RBTDB_VIRTUAL) &&
(nlocktype == isc_rwlocktype_write ||
NODE_TRYUPGRADE(lock, &nlocktype) ==
ISC_R_SUCCESS))
{
/*
* We update the node's status only when we
* can get write access.
*
* We don't check if refcurrent(rbtnode) == 0
* and try to free like we do in cache_find(),
* because refcurrent(rbtnode) must be
* non-zero. This is so because 'node' is an
* argument to the function.
*/
dns__rbtdb_mark_ancient(header);
}
} else if (EXISTS(header) && !ANCIENT(header)) {
if (header->type == matchtype) {
found = header;
} else if (header->type == RDATATYPE_NCACHEANY ||
header->type == negtype)
{
found = header;
} else if (header->type == sigmatchtype) {
foundsig = header;
}
}
}
if (found != NULL) {
dns__rbtdb_bindrdataset(rbtdb, rbtnode, found, now, nlocktype,
rdataset DNS__DB_FLARG_PASS);
if (!NEGATIVE(found) && foundsig != NULL) {
dns__rbtdb_bindrdataset(rbtdb, rbtnode, foundsig, now,
nlocktype,
sigrdataset DNS__DB_FLARG_PASS);
}
}
NODE_UNLOCK(lock, &nlocktype);
if (found == NULL) {
return ISC_R_NOTFOUND;
}
if (NEGATIVE(found)) {
/*
* We found a negative cache entry.
*/
if (NXDOMAIN(found)) {
result = DNS_R_NCACHENXDOMAIN;
} else {
result = DNS_R_NCACHENXRRSET;
}
}
update_cachestats(rbtdb, result);
return result;
}
static size_t
hashsize(dns_db_t *db) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
size_t size;
isc_rwlocktype_t tlocktype = isc_rwlocktype_none;
REQUIRE(VALID_RBTDB(rbtdb));
TREE_RDLOCK(&rbtdb->tree_lock, &tlocktype);
size = dns_rbt_hashsize(rbtdb->tree);
TREE_UNLOCK(&rbtdb->tree_lock, &tlocktype);
return size;
}
static isc_result_t
setcachestats(dns_db_t *db, isc_stats_t *stats) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb)); /* current restriction */
REQUIRE(stats != NULL);
isc_stats_attach(stats, &rbtdb->cachestats);
return ISC_R_SUCCESS;
}
static dns_stats_t *
getrrsetstats(dns_db_t *db) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb)); /* current restriction */
return rbtdb->rrsetstats;
}
static isc_result_t
setservestalettl(dns_db_t *db, dns_ttl_t ttl) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb));
/* currently no bounds checking. 0 means disable. */
rbtdb->common.serve_stale_ttl = ttl;
return ISC_R_SUCCESS;
}
static isc_result_t
getservestalettl(dns_db_t *db, dns_ttl_t *ttl) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb));
*ttl = rbtdb->common.serve_stale_ttl;
return ISC_R_SUCCESS;
}
static isc_result_t
setservestalerefresh(dns_db_t *db, uint32_t interval) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb));
/* currently no bounds checking. 0 means disable. */
rbtdb->serve_stale_refresh = interval;
return ISC_R_SUCCESS;
}
static isc_result_t
getservestalerefresh(dns_db_t *db, uint32_t *interval) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
REQUIRE(VALID_RBTDB(rbtdb));
REQUIRE(IS_CACHE(rbtdb));
*interval = rbtdb->serve_stale_refresh;
return ISC_R_SUCCESS;
}
static void
expiredata(dns_db_t *db, dns_dbnode_t *node, void *data) {
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)db;
dns_rbtnode_t *rbtnode = (dns_rbtnode_t *)node;
dns_slabheader_t *header = data;
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
isc_rwlocktype_t tlocktype = isc_rwlocktype_none;
NODE_WRLOCK(&rbtdb->node_locks[rbtnode->locknum].lock, &nlocktype);
dns__cacherbt_expireheader(header, &tlocktype,
dns_expire_flush DNS__DB_FILELINE);
NODE_UNLOCK(&rbtdb->node_locks[rbtnode->locknum].lock, &nlocktype);
INSIST(tlocktype == isc_rwlocktype_none);
}
dns_dbmethods_t dns__rbtdb_cachemethods = {
.destroy = dns__rbtdb_destroy,
.currentversion = dns__rbtdb_currentversion,
.newversion = dns__rbtdb_newversion,
.attachversion = dns__rbtdb_attachversion,
.closeversion = dns__rbtdb_closeversion,
.findnode = dns__rbtdb_findnode,
.find = cache_find,
.findzonecut = cache_findzonecut,
.attachnode = dns__rbtdb_attachnode,
.detachnode = dns__rbtdb_detachnode,
.createiterator = dns__rbtdb_createiterator,
.findrdataset = cache_findrdataset,
.allrdatasets = dns__rbtdb_allrdatasets,
.addrdataset = dns__rbtdb_addrdataset,
.subtractrdataset = dns__rbtdb_subtractrdataset,
.deleterdataset = dns__rbtdb_deleterdataset,
.nodecount = dns__rbtdb_nodecount,
.setloop = dns__rbtdb_setloop,
.getoriginnode = dns__rbtdb_getoriginnode,
.getrrsetstats = getrrsetstats,
.setcachestats = setcachestats,
.hashsize = hashsize,
.setservestalettl = setservestalettl,
.getservestalettl = getservestalettl,
.setservestalerefresh = setservestalerefresh,
.getservestalerefresh = getservestalerefresh,
.locknode = dns__rbtdb_locknode,
.unlocknode = dns__rbtdb_unlocknode,
.expiredata = expiredata,
.deletedata = dns__rbtdb_deletedata,
.setmaxrrperset = dns__rbtdb_setmaxrrperset,
.setmaxtypepername = dns__rbtdb_setmaxtypepername,
};
/*
* Caller must hold the node (write) lock.
*/
void
dns__cacherbt_expireheader(dns_slabheader_t *header,
isc_rwlocktype_t *tlocktypep,
dns_expire_t reason DNS__DB_FLARG) {
dns__rbtdb_mark_ancient(header);
if (isc_refcount_current(&RBTDB_HEADERNODE(header)->references) == 0) {
isc_rwlocktype_t nlocktype = isc_rwlocktype_write;
dns_rbtdb_t *rbtdb = (dns_rbtdb_t *)header->db;
/*
* If no one else is using the node, we can clean it up now.
* We first need to gain a new reference to the node to meet a
* requirement of dns__rbtnode_release().
*/
dns__rbtnode_acquire(rbtdb, RBTDB_HEADERNODE(header),
nlocktype DNS__DB_FLARG_PASS);
dns__rbtnode_release(rbtdb, RBTDB_HEADERNODE(header), 0,
&nlocktype, tlocktypep, true,
false DNS__DB_FLARG_PASS);
if (rbtdb->cachestats == NULL) {
return;
}
switch (reason) {
case dns_expire_ttl:
isc_stats_increment(rbtdb->cachestats,
dns_cachestatscounter_deletettl);
break;
case dns_expire_lru:
isc_stats_increment(rbtdb->cachestats,
dns_cachestatscounter_deletelru);
break;
default:
break;
}
}
}
static size_t
rdataset_size(dns_slabheader_t *header) {
if (!NONEXISTENT(header)) {
return dns_rdataslab_size((unsigned char *)header,
sizeof(*header));
}
return sizeof(*header);
}
static size_t
expire_lru_headers(dns_rbtdb_t *rbtdb, unsigned int locknum,
isc_rwlocktype_t *tlocktypep,
size_t purgesize DNS__DB_FLARG) {
dns_slabheader_t *header = NULL;
size_t purged = 0;
for (header = ISC_LIST_TAIL(rbtdb->lru[locknum]);
header != NULL && header->last_used <= rbtdb->last_used &&
purged <= purgesize;
header = ISC_LIST_TAIL(rbtdb->lru[locknum]))
{
size_t header_size = rdataset_size(header);
/*
* Unlink the entry at this point to avoid checking it
* again even if it's currently used someone else and
* cannot be purged at this moment. This entry won't be
* referenced any more (so unlinking is safe) since the
* TTL will be reset to 0.
*/
ISC_LIST_UNLINK(rbtdb->lru[locknum], header, link);
dns__cacherbt_expireheader(header, tlocktypep,
dns_expire_lru DNS__DB_FLARG_PASS);
purged += header_size;
}
return purged;
}
/*%
* Purge some expired and/or stale (i.e. unused for some period) cache entries
* due to an overmem condition. To recover from this condition quickly,
* we clean up entries up to the size of newly added rdata that triggered
* the overmem; this is accessible via newheader.
*
* The LRU lists tails are processed in LRU order to the nearest second.
*
* A write lock on the tree must be held.
*/
void
dns__cacherbt_overmem(dns_rbtdb_t *rbtdb, dns_slabheader_t *newheader,
isc_rwlocktype_t *tlocktypep DNS__DB_FLARG) {
uint32_t locknum_start = rbtdb->lru_sweep++ % rbtdb->node_lock_count;
uint32_t locknum = locknum_start;
/* Size of added data, possible node and possible ENT node. */
size_t purgesize =
rdataset_size(newheader) +
2 * dns__rbtnode_getsize(RBTDB_HEADERNODE(newheader));
size_t purged = 0;
isc_stdtime_t min_last_used = 0;
size_t max_passes = 8;
again:
do {
isc_rwlocktype_t nlocktype = isc_rwlocktype_none;
NODE_WRLOCK(&rbtdb->node_locks[locknum].lock, &nlocktype);
purged += expire_lru_headers(rbtdb, locknum, tlocktypep,
purgesize -
purged DNS__DB_FLARG_PASS);
/*
* Work out the oldest remaining last_used values of the list
* tails as we walk across the array of lru lists.
*/
dns_slabheader_t *header = ISC_LIST_TAIL(rbtdb->lru[locknum]);
if (header != NULL &&
(min_last_used == 0 || header->last_used < min_last_used))
{
min_last_used = header->last_used;
}
NODE_UNLOCK(&rbtdb->node_locks[locknum].lock, &nlocktype);
locknum = (locknum + 1) % rbtdb->node_lock_count;
} while (locknum != locknum_start && purged <= purgesize);
/*
* Update rbtdb->last_used if we have walked all the list tails and have
* not freed the required amount of memory.
*/
if (purged < purgesize) {
if (min_last_used != 0) {
rbtdb->last_used = min_last_used;
if (max_passes-- > 0) {
goto again;
}
}
}
}
View git blame Copy permalink