From c86e0c73baf66fb0c8689e061f5155b5ce751c93 Mon Sep 17 00:00:00 2001
From: Remi Gacogne <remi.gacogne@powerdns.com>
Date: Thu, 5 Apr 2018 11:43:52 +0200
Subject: [PATCH] rec: Add a hashed index to the negative cache

---
 pdns/recursordist/negcache.cc | 11 +++++++----
 pdns/recursordist/negcache.hh |  6 +++++-
 2 files changed, 12 insertions(+), 5 deletions(-)

diff --git a/pdns/recursordist/negcache.cc b/pdns/recursordist/negcache.cc
index 7b9d33645a..13fbf619fe 100644
--- a/pdns/recursordist/negcache.cc
+++ b/pdns/recursordist/negcache.cc
@@ -71,21 +71,24 @@ bool NegCache::getRootNXTrust(const DNSName& qname, const struct timeval& now, N
  * \return         true if ne was filled out, false otherwise
  */
 bool NegCache::get(const DNSName& qname, const QType& qtype, const struct timeval& now, NegCacheEntry& ne, bool typeMustMatch) {
-  auto range = d_negcache.equal_range(tie(qname));
-  negcache_t::iterator ni = range.first;
+  const auto& idx = d_negcache.get<2>();
+  auto range = idx.equal_range(qname);
+  auto ni = range.first;
 
   while (ni != range.second) {
     // We have an entry
     if ((!typeMustMatch && ni->d_qtype.getCode() == 0) || ni->d_qtype == qtype) {
       // We match the QType or the whole name is denied
+      auto firstIndexIterator = d_negcache.project<0>(ni);
+
       if((uint32_t) now.tv_sec < ni->d_ttd) {
         // Not expired
         ne = *ni;
-        moveCacheItemToBack(d_negcache, ni);
+        moveCacheItemToBack(d_negcache, firstIndexIterator);
         return true;
       }
       // expired
-      moveCacheItemToFront(d_negcache, ni);
+      moveCacheItemToFront(d_negcache, firstIndexIterator);
     }
     ++ni;
   }
diff --git a/pdns/recursordist/negcache.hh b/pdns/recursordist/negcache.hh
index d1a742da3e..2bc41da620 100644
--- a/pdns/recursordist/negcache.hh
+++ b/pdns/recursordist/negcache.hh
@@ -22,6 +22,7 @@
 #pragma once
 
 #include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
 #include "dnsparser.hh"
 #include "dnsname.hh"
 #include "dns.hh"
@@ -90,7 +91,10 @@ class NegCache : public boost::noncopyable {
             CanonDNSNameCompare, std::less<QType>
           >
         >,
-        sequenced<>
+        sequenced<>,
+        hashed_non_unique <
+          member<NegCacheEntry, DNSName, &NegCacheEntry::d_name>
+        >
       >
     > negcache_t;
 
-- 
2.47.2