From 3cd01b932e1c85394272ae64fae67ebeda92fb00 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 23:11:59 +0200 Subject: Adding upstream version 1.8.3. Signed-off-by: Daniel Baumann --- cachecleaner.hh | 303 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 303 insertions(+) create mode 100644 cachecleaner.hh (limited to 'cachecleaner.hh') diff --git a/cachecleaner.hh b/cachecleaner.hh new file mode 100644 index 0000000..9ec8e13 --- /dev/null +++ b/cachecleaner.hh @@ -0,0 +1,303 @@ +/* + * This file is part of PowerDNS or dnsdist. + * Copyright -- PowerDNS.COM B.V. and its contributors + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of version 2 of the GNU General Public License as + * published by the Free Software Foundation. + * + * In addition, for the avoidance of any doubt, permission is granted to + * link this program with OpenSSL and to (re)distribute the binaries + * produced as the result of such linking. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ +#pragma once + +#include +#include + +#include "dnsname.hh" +#include "lock.hh" + +// this function can clean any cache that has an isStale() method on its entries, a preRemoval() method and a 'sequence' index as its second index +// the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end +// and optionally, on a miss, move it to the beginning +template +void pruneCollection(T& collection, size_t maxCached, size_t scanFraction = 1000) +{ + const time_t now = time(nullptr); + size_t toTrim = 0; + const size_t cacheSize = collection.size(); + + if (cacheSize > maxCached) { + toTrim = cacheSize - maxCached; + } + + auto& sidx = collection.template get(); + + // two modes - if toTrim is 0, just look through 1/scanFraction of all records + // and nuke everything that is expired + // otherwise, scan first 5*toTrim records, and stop once we've nuked enough + const size_t lookAt = toTrim ? 5 * toTrim : cacheSize / scanFraction; + size_t tried = 0; + size_t erased = 0; + + for (auto iter = sidx.begin(); iter != sidx.end() && tried < lookAt; ++tried) { + if (iter->isStale(now)) { + iter = sidx.erase(iter); + erased++; + } + else { + ++iter; + } + + if (toTrim && erased >= toTrim) { + break; + } + } + + if (erased >= toTrim) { // done + return; + } + + toTrim -= erased; + + // just lob it off from the beginning + auto iter = sidx.begin(); + for (size_t i = 0; i < toTrim && iter != sidx.end(); i++) { + iter = sidx.erase(iter); + } +} + +// note: this expects iterator from first index +template +void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front) +{ + typedef typename T::template index::type sequence_t; + sequence_t& sidx = collection.template get(); + typename sequence_t::iterator si = collection.template project(iter); + if (front) + sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue + else + sidx.relocate(sidx.end(), si); // back +} + +template +void moveCacheItemToFront(T& collection, typename T::iterator& iter) +{ + moveCacheItemToFrontOrBack(collection, iter, true); +} + +template +void moveCacheItemToBack(T& collection, typename T::iterator& iter) +{ + moveCacheItemToFrontOrBack(collection, iter, false); +} + +template +uint64_t pruneLockedCollectionsVector(std::vector& maps) +{ + uint64_t totErased = 0; + time_t now = time(nullptr); + + for (auto& mc : maps) { + auto map = mc.d_map.write_lock(); + + uint64_t lookAt = (map->size() + 9) / 10; // Look at 10% of this shard + uint64_t erased = 0; + + auto& sidx = boost::multi_index::get(*map); + for (auto i = sidx.begin(); i != sidx.end() && lookAt > 0; lookAt--) { + if (i->ttd < now) { + i = sidx.erase(i); + erased++; + } + else { + ++i; + } + } + totErased += erased; + } + + return totErased; +} + +template +uint64_t pruneMutexCollectionsVector(C& container, std::vector& maps, uint64_t maxCached, uint64_t cacheSize) +{ + const time_t now = time(nullptr); + uint64_t totErased = 0; + uint64_t toTrim = 0; + uint64_t lookAt = 0; + + // two modes - if toTrim is 0, just look through 10% of the cache and nuke everything that is expired + // otherwise, scan first max(5*toTrim, 10%) records, and stop once we've nuked enough + if (cacheSize > maxCached) { + toTrim = cacheSize - maxCached; + lookAt = std::max(5 * toTrim, cacheSize / 10); + } + else { + lookAt = cacheSize / 10; + } + + const uint64_t numberOfShards = maps.size(); + if (numberOfShards == 0 || cacheSize == 0) { + return 0; + } + + // first we scan a fraction of the shards for expired entries orderded by LRU + for (auto& content : maps) { + auto shard = content.lock(); + const auto shardSize = shard->d_map.size(); + const uint64_t toScanForThisShard = std::ceil(lookAt * ((1.0 * shardSize) / cacheSize)); + shard->invalidate(); + auto& sidx = boost::multi_index::get(shard->d_map); + uint64_t erased = 0; + uint64_t lookedAt = 0; + for (auto i = sidx.begin(); i != sidx.end(); lookedAt++) { + if (i->isStale(now)) { + container.preRemoval(*shard, *i); + i = sidx.erase(i); + erased++; + --content.d_entriesCount; + } + else { + ++i; + } + + if (lookedAt >= toScanForThisShard) { + break; + } + } + totErased += erased; + } + + if (totErased >= toTrim) { // done + return totErased; + } + + toTrim -= totErased; + + // It was not enough, so we need to remove entries that are not + // expired, still using the LRU index. + + // From here on cacheSize is the total number of entries in the + // shards that still need to be cleaned. When a shard is processed, + // we subtract its original size from cacheSize as we use this value + // to compute the fraction of the next shards to clean. This way + // rounding issues do not cause over or undershoot of the target. + // + // Suppose we have 10 perfectly balanced shards, each filled with + // 100 entries. So cacheSize is 1000. When cleaning 10%, after shard + // 0 we still need to processs 900 entries, spread out of 9 + // shards. So cacheSize becomes 900, and toTrim 90, since we cleaned + // 10 items from shard 0. Our fraction remains 10%. For the last + // shard, we would end up with cacheSize 100, and to clean 10. + // + // When the balance is not perfect, e.g. shard 0 has 54 entries, we + // would clean 5 entries due to rounding, and for the remaining + // shards we start with cacheSize 946 and toTrim 95: the fraction + // becomes slightly larger than 10%, since we "missed" one item in + // shard 0. + + cacheSize -= totErased; + + for (auto& content : maps) { + auto shard = content.lock(); + const auto shardSize = shard->d_map.size(); + + const uint64_t toTrimForThisShard = std::round(static_cast(toTrim) * shardSize / cacheSize); + // See explanation above + cacheSize -= shardSize; + if (toTrimForThisShard == 0) { + continue; + } + shard->invalidate(); + auto& sidx = boost::multi_index::get(shard->d_map); + size_t removed = 0; + for (auto i = sidx.begin(); i != sidx.end() && removed < toTrimForThisShard; removed++) { + container.preRemoval(*shard, *i); + i = sidx.erase(i); + --content.d_entriesCount; + ++totErased; + if (--toTrim == 0) { + return totErased; + } + } + } + return totErased; +} + +template +uint64_t purgeLockedCollectionsVector(std::vector& maps) +{ + uint64_t delcount = 0; + + for (auto& mc : maps) { + auto map = mc.d_map.write_lock(); + delcount += map->size(); + map->clear(); + } + + return delcount; +} + +template +uint64_t purgeLockedCollectionsVector(std::vector& maps, const std::string& match) +{ + uint64_t delcount = 0; + std::string prefix(match); + prefix.resize(prefix.size() - 1); + DNSName dprefix(prefix); + for (auto& mc : maps) { + auto map = mc.d_map.write_lock(); + auto& idx = boost::multi_index::get(*map); + auto iter = idx.lower_bound(dprefix); + auto start = iter; + + for (; iter != idx.end(); ++iter) { + if (!iter->qname.isPartOf(dprefix)) { + break; + } + delcount++; + } + idx.erase(start, iter); + } + + return delcount; +} + +template +uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname) +{ + uint64_t delcount = 0; + auto map = mc.d_map.write_lock(); + auto& idx = boost::multi_index::get(*map); + auto range = idx.equal_range(qname); + if (range.first != range.second) { + delcount += distance(range.first, range.second); + idx.erase(range.first, range.second); + } + + return delcount; +} + +template +bool lruReplacingInsert(Index& i, const typename Index::value_type& x) +{ + auto inserted = i.insert(x); + if (!inserted.second) { + moveCacheItemToBack(i, inserted.first); + i.replace(inserted.first, x); + return false; + } + return true; +} -- cgit v1.2.3