/* $NetBSD: rbt-cachedb.c,v 1.4 2025/07/17 19:01:45 christos Exp $ */ /* * 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #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; } } } }