From e0a1a5f4faac0fbf760824793559c8de32f7840b Mon Sep 17 00:00:00 2001
From: Remi Gacogne <remi.gacogne@powerdns.com>
Date: Fri, 17 Jan 2020 14:56:27 +0100
Subject: [PATCH] auth: Enforce a strict maximum size for the packet and
 records caches

Before this change, both the query and packet caches in the authoritative
server can exceed their maximum size by a lot, until the next cleaning
cycle.
This is particularly nasty since the current cleaning algorithm will
never remove entries from the cache until they expire, as opposed to
what we do in the recursor, for example, where we nuke the least-recently
used entries, even if they are still valid, when the cache is full.
This commit changes that by removing the least recently inserted or
updated entry from the cache after inserting a new one when the cache
is full, thus enforcing the maximum size more strictly.

Note that this is really the least recently inserted/updated and not
the least recently used one, as is done in the recursor. Having a
proper LRU in the auth would require acquering a write lock for a
simple lookup, instead of a potentially concurrent read-lock at the
moment. We might want to consider changing that at some point, as
a LRU might be fairer and the lock contention might be very small
since the caches are sharded.

(cherry picked from commit d2814f81c77709d628a3fc036aff96ccc8a74c64)
---
 pdns/auth-packetcache.cc | 11 ++++++++++-
 pdns/auth-packetcache.hh |  2 ++
 pdns/auth-querycache.cc  | 10 +++++++++-
 pdns/auth-querycache.hh  |  2 ++
 4 files changed, 23 insertions(+), 2 deletions(-)

diff --git a/pdns/auth-packetcache.cc b/pdns/auth-packetcache.cc
index b67c16d28a..45ac409915 100644
--- a/pdns/auth-packetcache.cc
+++ b/pdns/auth-packetcache.cc
@@ -159,6 +159,7 @@ void AuthPacketCache::insert(DNSPacket *q, DNSPacket *r, unsigned int maxTTL)
         continue;
       }
 
+      moveCacheItemToBack<SequencedTag>(mc.d_map, iter);
       iter->value = entry.value;
       iter->ttd = now + ourttl;
       iter->created = now;
@@ -167,7 +168,15 @@ void AuthPacketCache::insert(DNSPacket *q, DNSPacket *r, unsigned int maxTTL)
 
     /* no existing entry found to refresh */
     mc.d_map.insert(entry);
-    (*d_statnumentries)++;
+
+    if (*d_statnumentries >= d_maxEntries) {
+      /* remove the least recently inserted or replaced entry */
+      auto& sidx = mc.d_map.get<SequencedTag>();
+      sidx.pop_front();
+    }
+    else {
+      (*d_statnumentries)++;
+    }
   }
 }
 
diff --git a/pdns/auth-packetcache.hh b/pdns/auth-packetcache.hh
index 2ba54daaa7..7826ad64b0 100644
--- a/pdns/auth-packetcache.hh
+++ b/pdns/auth-packetcache.hh
@@ -98,6 +98,8 @@ private:
     indexed_by <
       hashed_non_unique<tag<HashTag>, member<CacheEntry,uint32_t,&CacheEntry::hash> >,
       ordered_non_unique<tag<NameTag>, member<CacheEntry,DNSName,&CacheEntry::qname>, CanonDNSNameCompare >,
+      /* Note that this sequence holds 'least recently inserted or replaced', not least recently used.
+         Making it a LRU would require taking a write-lock when fetching from the cache, making the RW-lock inefficient compared to a mutex */
       sequenced<tag<SequencedTag>>
       >
     > cmap_t;
diff --git a/pdns/auth-querycache.cc b/pdns/auth-querycache.cc
index 2e39d2d225..bf5b57a3d5 100644
--- a/pdns/auth-querycache.cc
+++ b/pdns/auth-querycache.cc
@@ -114,9 +114,17 @@ void AuthQueryCache::insert(const DNSName &qname, const QType& qtype, const vect
 
     if (!inserted) {
       mc.d_map.replace(place, val);
+      moveCacheItemToBack<SequencedTag>(mc.d_map, place);
     }
     else {
-      (*d_statnumentries)++;
+      if (*d_statnumentries >= d_maxEntries) {
+        /* remove the least recently inserted or replaced entry */
+        auto& sidx = mc.d_map.get<SequencedTag>();
+        sidx.pop_front();
+      }
+      else {
+        (*d_statnumentries)++;
+      }
     }
   }
 }
diff --git a/pdns/auth-querycache.hh b/pdns/auth-querycache.hh
index 90144a3c85..e8f3a9f47c 100644
--- a/pdns/auth-querycache.hh
+++ b/pdns/auth-querycache.hh
@@ -80,6 +80,8 @@ private:
                                                          member<CacheEntry,uint16_t,&CacheEntry::qtype>,
                                                          member<CacheEntry,int, &CacheEntry::zoneID> > > ,
       ordered_non_unique<tag<NameTag>, member<CacheEntry,DNSName,&CacheEntry::qname>, CanonDNSNameCompare >,
+      /* Note that this sequence holds 'least recently inserted or replaced', not least recently used.
+         Making it a LRU would require taking a write-lock when fetching from the cache, making the RW-lock inefficient compared to a mutex */
       sequenced<tag<SequencedTag>>
                            >
   > cmap_t;
-- 
2.47.2