From 1d7047524ff590531980f9836afdb7de3f8b652c Mon Sep 17 00:00:00 2001
From: Remi Gacogne <remi.gacogne@powerdns.com>
Date: Thu, 18 Apr 2019 10:05:03 +0200
Subject: [PATCH] rec: Move replaced negcache entries to the back of the
 expunge queue

Otherwise they might get expunged very quickly while they just have
been inserted.
---
 pdns/cachecleaner.hh                  | 12 ++++++
 pdns/recursordist/negcache.cc         |  2 +-
 pdns/recursordist/test-negcache_cc.cc | 53 +++++++++++++++++++++++++++
 3 files changed, 66 insertions(+), 1 deletion(-)

diff --git a/pdns/cachecleaner.hh b/pdns/cachecleaner.hh
index 1d80b1740..884029858 100644
--- a/pdns/cachecleaner.hh
+++ b/pdns/cachecleaner.hh
@@ -201,3 +201,15 @@ template <typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName&
 
   return delcount;
 }
+
+template<typename Index>
+std::pair<typename Index::iterator,bool>
+lruReplacingInsert(Index& i,const typename Index::value_type& x)
+{
+  std::pair<typename Index::iterator,bool> res = i.insert(x);
+  if (!res.second) {
+    moveCacheItemToBack(i, res.first);
+    res.second = i.replace(res.first, x);
+  }
+  return res;
+}
diff --git a/pdns/recursordist/negcache.cc b/pdns/recursordist/negcache.cc
index 0f5325c33..f7f5646f4 100644
--- a/pdns/recursordist/negcache.cc
+++ b/pdns/recursordist/negcache.cc
@@ -101,7 +101,7 @@ bool NegCache::get(const DNSName& qname, const QType& qtype, const struct timeva
  * \param ne The NegCacheEntry to add to the cache
  */
 void NegCache::add(const NegCacheEntry& ne) {
-  replacing_insert(d_negcache, ne);
+  lruReplacingInsert(d_negcache, ne);
 }
 
 /*!
diff --git a/pdns/recursordist/test-negcache_cc.cc b/pdns/recursordist/test-negcache_cc.cc
index f5ddec76b..b67874c2e 100644
--- a/pdns/recursordist/test-negcache_cc.cc
+++ b/pdns/recursordist/test-negcache_cc.cc
@@ -264,6 +264,59 @@ BOOST_AUTO_TEST_CASE(test_prune) {
   BOOST_CHECK_EQUAL(cache.size(), 100);
 }
 
+BOOST_AUTO_TEST_CASE(test_prune_valid_entries) {
+  DNSName power1("powerdns.com.");
+  DNSName power2("powerdns-1.com.");
+  DNSName auth("com.");
+
+  struct timeval now;
+  Utility::gettimeofday(&now, 0);
+
+  NegCache cache;
+  NegCache::NegCacheEntry ne;
+
+  /* insert power1 then power2 */
+  ne = genNegCacheEntry(power1, auth, now);
+  cache.add(ne);
+  ne = genNegCacheEntry(power2, auth, now);
+  cache.add(ne);
+
+  BOOST_CHECK_EQUAL(cache.size(), 2);
+
+  /* power2 has been inserted more recently, so it should be
+     removed last */
+  cache.prune(1);
+  BOOST_CHECK_EQUAL(cache.size(), 1);
+
+  const NegCache::NegCacheEntry* got = nullptr;
+  bool ret = cache.get(power2, QType(1), now, &got);
+  BOOST_REQUIRE(ret);
+  BOOST_CHECK_EQUAL(got->d_name, power2);
+  BOOST_CHECK_EQUAL(got->d_auth, auth);
+
+  /* insert power1 back */
+  ne = genNegCacheEntry(power1, auth, now);
+  cache.add(ne);
+  BOOST_CHECK_EQUAL(cache.size(), 2);
+
+  /* replace the entry for power2 */
+  ne = genNegCacheEntry(power2, auth, now);
+  cache.add(ne);
+
+  BOOST_CHECK_EQUAL(cache.size(), 2);
+
+  /* power2 has been updated more recently, so it should be
+     removed last */
+  cache.prune(1);
+
+  BOOST_CHECK_EQUAL(cache.size(), 1);
+  got = nullptr;
+  ret = cache.get(power2, QType(1), now, &got);
+  BOOST_REQUIRE(ret);
+  BOOST_CHECK_EQUAL(got->d_name, power2);
+  BOOST_CHECK_EQUAL(got->d_auth, auth);
+}
+
 BOOST_AUTO_TEST_CASE(test_wipe_single) {
   string qname(".powerdns.com");
   DNSName auth("powerdns.com");
-- 
2.40.0