From f6e76e12e6acfa2ff42ccaefdcfda02be5340d8d Mon Sep 17 00:00:00 2001 From: Remi Gacogne Date: Tue, 2 Mar 2021 17:50:54 +0100 Subject: [PATCH] dnsdist: Clean up expired entries from all the packet cache's shards Otherwise we might remove enough entries from the first shards only and stop there, which means that the other shards might remain full. This might be fine if we clean up often enough since the next cleaning run will start with the remaining shards, but that's sub-optimal when we are often nearly full because it will prevent new entries from being inserted in the shards that are full. --- pdns/dnsdist-cache.cc | 27 ++--- pdns/dnsdist-cache.hh | 2 +- pdns/dnsdist.cc | 3 +- .../dnsdist-lua-bindings-packetcache.cc | 4 +- pdns/test-dnsdistpacketcache_cc.cc | 110 ++++++++++++++++-- 5 files changed, 123 insertions(+), 23 deletions(-) diff --git a/pdns/dnsdist-cache.cc b/pdns/dnsdist-cache.cc index 860322c17a..7dfde45886 100644 --- a/pdns/dnsdist-cache.cc +++ b/pdns/dnsdist-cache.cc @@ -294,27 +294,28 @@ bool DNSDistPacketCache::get(DNSQuestion& dq, uint16_t queryId, uint32_t* keyOut /* Remove expired entries, until the cache has at most upTo entries in it. + If the cache has more than one shard, we will try hard + to make sure that every shard has free space remaining. */ -size_t DNSDistPacketCache::purgeExpired(size_t upTo) +size_t DNSDistPacketCache::purgeExpired(size_t upTo, const time_t now) { - size_t removed = 0; - uint64_t size = getSize(); - - if (size == 0 || upTo >= size) { - return removed; - } - - size_t toRemove = size - upTo; + const size_t maxPerShard = upTo / d_shardCount; + size_t removed = 0; size_t scannedMaps = 0; - const time_t now = time(nullptr); do { uint32_t shardIndex = (d_expungeIndex++ % d_shardCount); + WriteLock w(&d_shards.at(shardIndex).d_lock); - auto& map = d_shards[shardIndex].d_map; + if (d_shards.at(shardIndex).d_entriesCount <= maxPerShard) { + continue; + } + + size_t toRemove = d_shards.at(shardIndex).d_entriesCount - maxPerShard; + auto& map = d_shards.at(shardIndex).d_map; - for(auto it = map.begin(); toRemove > 0 && it != map.end(); ) { + for (auto it = map.begin(); toRemove > 0 && it != map.end(); ) { const CacheValue& value = it->second; if (value.validity <= now) { @@ -329,7 +330,7 @@ size_t DNSDistPacketCache::purgeExpired(size_t upTo) scannedMaps++; } - while (toRemove > 0 && scannedMaps < d_shardCount); + while (scannedMaps < d_shardCount); return removed; } diff --git a/pdns/dnsdist-cache.hh b/pdns/dnsdist-cache.hh index a640326162..c2441a631d 100644 --- a/pdns/dnsdist-cache.hh +++ b/pdns/dnsdist-cache.hh @@ -39,7 +39,7 @@ public: void insert(uint32_t key, const boost::optional& subnet, uint16_t queryFlags, bool dnssecOK, const DNSName& qname, uint16_t qtype, uint16_t qclass, const PacketBuffer& response, bool tcp, uint8_t rcode, boost::optional tempFailureTTL); bool get(DNSQuestion& dq, uint16_t queryId, uint32_t* keyOut, boost::optional& subnet, bool dnssecOK, uint32_t allowExpired = 0, bool skipAging = false); - size_t purgeExpired(size_t upTo=0); + size_t purgeExpired(size_t upTo, const time_t now); size_t expunge(size_t upTo=0); size_t expungeByName(const DNSName& name, uint16_t qtype=QType::ANY, bool suffixMatch=false); bool isFull(); diff --git a/pdns/dnsdist.cc b/pdns/dnsdist.cc index 8aa49a489f..b73a9adfe8 100644 --- a/pdns/dnsdist.cc +++ b/pdns/dnsdist.cc @@ -1645,6 +1645,7 @@ static void maintThread() } } + const time_t now = time(nullptr); for (auto pair : caches) { /* shall we keep expired entries ? */ if (pair.second == true) { @@ -1652,7 +1653,7 @@ static void maintThread() } auto& packetCache = pair.first; size_t upTo = (packetCache->getMaxEntries()* (100 - g_cacheCleaningPercentage)) / 100; - packetCache->purgeExpired(upTo); + packetCache->purgeExpired(upTo, now); } counter = 0; } diff --git a/pdns/dnsdistdist/dnsdist-lua-bindings-packetcache.cc b/pdns/dnsdistdist/dnsdist-lua-bindings-packetcache.cc index 90a102389c..44e5ffb7e8 100644 --- a/pdns/dnsdistdist/dnsdist-lua-bindings-packetcache.cc +++ b/pdns/dnsdistdist/dnsdist-lua-bindings-packetcache.cc @@ -112,7 +112,9 @@ void setupLuaBindingsPacketCache(LuaContext& luaCtx) }); luaCtx.registerFunction::*)(size_t)>("purgeExpired", [](std::shared_ptr& cache, size_t upTo) { if (cache) { - return cache->purgeExpired(upTo); + const time_t now = time(nullptr); + + return cache->purgeExpired(upTo, now); } return static_cast(0); }); diff --git a/pdns/test-dnsdistpacketcache_cc.cc b/pdns/test-dnsdistpacketcache_cc.cc index 4acd98a75d..844179a60a 100644 --- a/pdns/test-dnsdistpacketcache_cc.cc +++ b/pdns/test-dnsdistpacketcache_cc.cc @@ -26,8 +26,9 @@ BOOST_AUTO_TEST_CASE(test_PacketCacheSimple) { size_t skipped=0; ComboAddress remote; bool dnssecOK = false; + const time_t now = time(nullptr); try { - for(counter = 0; counter < 100000; ++counter) { + for (counter = 0; counter < 100000; ++counter) { DNSName a=DNSName(std::to_string(counter))+DNSName(" hello"); BOOST_CHECK_EQUAL(DNSName(a.toString()), a); @@ -71,7 +72,7 @@ BOOST_AUTO_TEST_CASE(test_PacketCacheSimple) { size_t deleted=0; size_t delcounter=0; - for(delcounter=0; delcounter < counter/1000; ++delcounter) { + for (delcounter=0; delcounter < counter/1000; ++delcounter) { DNSName a=DNSName(std::to_string(delcounter))+DNSName(" hello"); PacketBuffer query; GenericDNSPacketWriter pwQ(query, a, QType::A, QClass::IN, 0); @@ -89,9 +90,8 @@ BOOST_AUTO_TEST_CASE(test_PacketCacheSimple) { BOOST_CHECK_EQUAL(PC.getSize(), counter - skipped - deleted); size_t matches=0; - vector entry; size_t expected=counter-skipped-deleted; - for(; delcounter < counter; ++delcounter) { + for (; delcounter < counter; ++delcounter) { DNSName a(DNSName(std::to_string(delcounter))+DNSName(" hello")); PacketBuffer query; GenericDNSPacketWriter pwQ(query, a, QType::A, QClass::IN, 0); @@ -105,7 +105,7 @@ BOOST_AUTO_TEST_CASE(test_PacketCacheSimple) { } /* in the unlikely event that the test took so long that the entries did expire.. */ - auto expired = PC.purgeExpired(); + auto expired = PC.purgeExpired(0, now); BOOST_CHECK_EQUAL(matches + expired, expected); auto remaining = PC.getSize(); @@ -113,7 +113,104 @@ BOOST_AUTO_TEST_CASE(test_PacketCacheSimple) { BOOST_CHECK_EQUAL(PC.getSize(), 0U); BOOST_CHECK_EQUAL(removed, remaining); } - catch(PDNSException& e) { + catch (const PDNSException& e) { + cerr<<"Had error: "< pwQ(query, a, QType::AAAA, QClass::IN, 0); + pwQ.getHeader()->rd = 1; + + PacketBuffer response; + GenericDNSPacketWriter pwR(response, a, QType::AAAA, QClass::IN, 0); + pwR.getHeader()->rd = 1; + pwR.getHeader()->ra = 1; + pwR.getHeader()->qr = 1; + pwR.getHeader()->id = pwQ.getHeader()->id; + pwR.startRecord(a, QType::AAAA, 7200, QClass::IN, DNSResourceRecord::ANSWER); + ComboAddress v6("2001:db8::1"); + pwR.xfrIP6(std::string(reinterpret_cast(v6.sin6.sin6_addr.s6_addr), 16)); + pwR.xfr32BitInt(0x01020304); + pwR.commit(); + + uint32_t key = 0; + boost::optional subnet; + DNSQuestion dq(&a, QType::AAAA, QClass::IN, &remote, &remote, query, false, &queryTime); + bool found = PC.get(dq, 0, &key, subnet, dnssecOK); + BOOST_CHECK_EQUAL(found, false); + BOOST_CHECK(!subnet); + + PC.insert(key, subnet, *(getFlagsFromDNSHeader(dq.getHeader())), dnssecOK, a, QType::AAAA, QClass::IN, response, false, 0, boost::none); + + found = PC.get(dq, pwR.getHeader()->id, &key, subnet, dnssecOK, 0, true); + if (found == true) { + BOOST_CHECK_EQUAL(dq.getData().size(), response.size()); + int match = memcmp(dq.getData().data(), response.data(), dq.getData().size()); + BOOST_CHECK_EQUAL(match, 0); + BOOST_CHECK(!subnet); + } + else { + skipped++; + } + } + + BOOST_CHECK_EQUAL(skipped, PC.getInsertCollisions()); + BOOST_CHECK_EQUAL(PC.getSize(), counter - skipped); + + size_t matches = 0; + for (counter = 0; counter < 100000; ++counter) { + DNSName a(std::to_string(counter) + ".powerdns.com."); + + PacketBuffer query; + GenericDNSPacketWriter pwQ(query, a, QType::AAAA, QClass::IN, 0); + pwQ.getHeader()->rd = 1; + uint32_t key = 0; + boost::optional subnet; + DNSQuestion dq(&a, QType::AAAA, QClass::IN, &remote, &remote, query, false, &queryTime); + if (PC.get(dq, pwQ.getHeader()->id, &key, subnet, dnssecOK)) { + matches++; + } + } + + BOOST_CHECK_EQUAL(matches, counter - skipped); + + auto remaining = PC.getSize(); + + /* no entry should have expired */ + auto expired = PC.purgeExpired(0, now); + BOOST_CHECK_EQUAL(expired, 0U); + + /* but after the TTL .. let's ask for at most 1k entries */ + auto removed = PC.purgeExpired(1000, now + 7200 + 1); + BOOST_CHECK_EQUAL(removed, remaining - 1000U); + BOOST_CHECK_EQUAL(PC.getSize(), 1000U); + + /* now remove everything */ + removed = PC.purgeExpired(0, now + 7200 + 1); + BOOST_CHECK_EQUAL(removed, 1000U); + BOOST_CHECK_EQUAL(PC.getSize(), 0U); + } + catch (const PDNSException& e) { cerr<<"Had error: "< entry; ComboAddress remote; for(unsigned int counter=0; counter < 100000; ++counter) { DNSName a=DNSName("hello ")+DNSName(std::to_string(counter+offset)); -- 2.47.2