pdns/recursor_cache.hh

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of version 2 of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * In addition, for the avoidance of any doubt, permission is granted to
  10  * link this program with OpenSSL and to (re)distribute the binaries
  11  * produced as the result of such linking.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22 #pragma once
  23 #include <string>
  24 #include <set>
  25 #include <mutex>
  26 #include "dns.hh"
  27 #include "qtype.hh"
  28 #include "misc.hh"
  29 #include "dnsname.hh"
  30 #include <iostream>
  31 #include "dnsrecords.hh"
  32 #include <boost/utility.hpp>
  33 #include <boost/multi_index_container.hpp>
  34 #include <boost/multi_index/ordered_index.hpp>
  35 #include <boost/multi_index/hashed_index.hpp>
  36 #include <boost/tuple/tuple_comparison.hpp>
  37 #include <boost/multi_index/key_extractors.hpp>
  38 #include <boost/multi_index/sequenced_index.hpp>
  39 #include <boost/version.hpp>
  40 #include "iputils.hh"
  41 #include "validate.hh"
  42 #undef max
  43
  44 #include "namespaces.hh"
  45 using namespace ::boost::multi_index;
  46
  47 class MemRecursorCache : public boost::noncopyable //  : public RecursorCache
  48 {
  49 public:
  50   MemRecursorCache(size_t mapsCount = 1024);
  51   ~MemRecursorCache();
  52
  53   size_t size();
  54   size_t bytes();
  55   pair<uint64_t,uint64_t> stats();
  56   size_t ecsIndexSize();
  57
  58   typedef boost::optional<std::string> OptTag;
  59
  60   int32_t get(time_t, const DNSName &qname, const QType& qt, bool requireAuth, vector<DNSRecord>* res, const ComboAddress& who, const OptTag& routingTag = boost::none, vector<std::shared_ptr<RRSIGRecordContent>>* signatures=nullptr, std::vector<std::shared_ptr<DNSRecord>>* authorityRecs=nullptr, bool* variable=nullptr, vState* state=nullptr, bool* wasAuth=nullptr);
  61
  62   void replace(time_t, const DNSName &qname, const QType& qt,  const vector<DNSRecord>& content, const vector<shared_ptr<RRSIGRecordContent>>& signatures, const std::vector<std::shared_ptr<DNSRecord>>& authorityRecs, bool auth, boost::optional<Netmask> ednsmask=boost::none, const OptTag& routingTag = boost::none, vState state=Indeterminate);
  63
  64   void doPrune(size_t keep);
  65   uint64_t doDump(int fd);
  66
  67   size_t doWipeCache(const DNSName& name, bool sub, uint16_t qtype=0xffff);
  68   bool doAgeCache(time_t now, const DNSName& name, uint16_t qtype, uint32_t newTTL);
  69   bool updateValidationStatus(time_t now, const DNSName &qname, const QType& qt, const ComboAddress& who, const OptTag& routingTag, bool requireAuth, vState newState, boost::optional<time_t> capTTD);
  70
  71   std::atomic<uint64_t> cacheHits{0}, cacheMisses{0};
  72
  73 private:
  74
  75   struct CacheEntry
  76   {
  77     CacheEntry(const boost::tuple<DNSName, uint16_t, OptTag, Netmask>& key, bool auth):
  78       d_qname(key.get<0>()), d_netmask(key.get<3>().getNormalized()), d_rtag(key.get<2>()), d_state(Indeterminate), d_ttd(0), d_qtype(key.get<1>()), d_auth(auth)
  79     {
  80     }
  81
  82     typedef vector<std::shared_ptr<DNSRecordContent>> records_t;
  83     time_t getTTD() const
  84     {
  85       return d_ttd;
  86     }
  87
  88     records_t d_records;
  89     std::vector<std::shared_ptr<RRSIGRecordContent>> d_signatures;
  90     std::vector<std::shared_ptr<DNSRecord>> d_authorityRecs;
  91     DNSName d_qname;
  92     Netmask d_netmask;
  93     OptTag d_rtag;
  94     mutable vState d_state;
  95     mutable time_t d_ttd;
  96     uint16_t d_qtype;
  97     bool d_auth;
  98   };
  99
 100   /* The ECS Index (d_ecsIndex) keeps track of whether there is any ECS-specific
 101      entry for a given (qname,qtype) entry in the cache (d_map), and if so
 102      provides a NetmaskTree of those ECS entries.
 103      This allows figuring out quickly if we should look for an entry
 104      specific to the requestor IP, and if so which entry is the most
 105      specific one.
 106      Keeping the entries in the regular cache is currently necessary
 107      because of the way we manage expired entries (moving them to the
 108      front of the expunge queue to be deleted at a regular interval).
 109   */
 110   class ECSIndexEntry
 111   {
 112   public:
 113     ECSIndexEntry(const DNSName& qname, uint16_t qtype): d_nmt(), d_qname(qname), d_qtype(qtype)
 114     {
 115     }
 116
 117     Netmask lookupBestMatch(const ComboAddress& addr) const
 118     {
 119       const auto best = d_nmt.lookup(addr);
 120       if (best != nullptr) {
 121         return best->first;
 122       }
 123
 124       return Netmask();
 125     }
 126
 127     void addMask(const Netmask& nm) const
 128     {
 129       d_nmt.insert(nm).second = true;
 130     }
 131
 132     void removeNetmask(const Netmask& nm) const
 133     {
 134       d_nmt.erase(nm);
 135     }
 136
 137     bool isEmpty() const
 138     {
 139       return d_nmt.empty();
 140     }
 141
 142     mutable NetmaskTree<bool> d_nmt;
 143     DNSName d_qname;
 144     uint16_t d_qtype;
 145   };
 146
 147   struct HashedTag {};
 148   struct SequencedTag {};
 149   struct NameAndRTagOnlyHashedTag {};
 150   struct OrderedTag {};
 151
 152   typedef multi_index_container<
 153     CacheEntry,
 154     indexed_by <
 155                 ordered_unique<tag<OrderedTag>,
 156                         composite_key<
 157                                 CacheEntry,
 158                                 member<CacheEntry,DNSName,&CacheEntry::d_qname>,
 159                                 member<CacheEntry,uint16_t,&CacheEntry::d_qtype>,
 160                                 member<CacheEntry,OptTag,&CacheEntry::d_rtag>,
 161                                 member<CacheEntry,Netmask,&CacheEntry::d_netmask>
 162                           >,
 163                                composite_key_compare<CanonDNSNameCompare, std::less<uint16_t>, std::less<OptTag>, std::less<Netmask> >
 164                 >,
 165                 sequenced<tag<SequencedTag> >,
 166                 hashed_non_unique<tag<NameAndRTagOnlyHashedTag>,
 167                     composite_key<
 168                       CacheEntry,
 169                       member<CacheEntry,DNSName,&CacheEntry::d_qname>,
 170                       member<CacheEntry,OptTag,&CacheEntry::d_rtag>
 171                     >
 172                 >
 173                >
 174   > cache_t;
 175
 176   typedef MemRecursorCache::cache_t::index<MemRecursorCache::OrderedTag>::type::iterator OrderedTagIterator_t;
 177   typedef MemRecursorCache::cache_t::index<MemRecursorCache::NameAndRTagOnlyHashedTag>::type::iterator NameAndRTagOnlyHashedTagIterator_t;
 178
 179   typedef multi_index_container<
 180     ECSIndexEntry,
 181     indexed_by <
 182       hashed_unique <tag<HashedTag>,
 183         composite_key<
 184           ECSIndexEntry,
 185           member<ECSIndexEntry,DNSName,&ECSIndexEntry::d_qname>,
 186           member<ECSIndexEntry,uint16_t,&ECSIndexEntry::d_qtype>
 187         >
 188       >,
 189       ordered_unique<tag<OrderedTag>,
 190         composite_key<
 191           ECSIndexEntry,
 192           member<ECSIndexEntry,DNSName,&ECSIndexEntry::d_qname>,
 193           member<ECSIndexEntry,uint16_t,&ECSIndexEntry::d_qtype>
 194         >,
 195         composite_key_compare<CanonDNSNameCompare, std::less<uint16_t> >
 196       >
 197     >
 198   > ecsIndex_t;
 199
 200   typedef std::pair<NameAndRTagOnlyHashedTagIterator_t, NameAndRTagOnlyHashedTagIterator_t> Entries;
 201
 202   struct MapCombo
 203   {
 204     MapCombo() {}
 205     MapCombo(const MapCombo &) = delete;
 206     MapCombo & operator=(const MapCombo &) = delete;
 207     cache_t d_map;
 208     ecsIndex_t d_ecsIndex;
 209     DNSName d_cachedqname;
 210     OptTag d_cachedrtag;
 211     Entries d_cachecache;
 212     std::mutex mutex;
 213     bool d_cachecachevalid{false};
 214     std::atomic<uint64_t> d_entriesCount{0};
 215     uint64_t d_contended_count{0};
 216     uint64_t d_acquired_count{0};
 217   };
 218
 219   vector<MapCombo> d_maps;
 220   MapCombo& getMap(const DNSName &qname)
 221   {
 222     return d_maps[qname.hash() % d_maps.size()];
 223   }
 224
 225   bool entryMatches(OrderedTagIterator_t& entry, uint16_t qt, bool requireAuth, const ComboAddress& who);
 226   Entries getEntries(MapCombo& map, const DNSName &qname, const QType& qt, const OptTag& rtag);
 227   cache_t::const_iterator getEntryUsingECSIndex(MapCombo& map, time_t now, const DNSName &qname, uint16_t qtype, bool requireAuth, const ComboAddress& who);
 228   int32_t handleHit(MapCombo& map, OrderedTagIterator_t& entry, const DNSName& qname, vector<DNSRecord>* res, vector<std::shared_ptr<RRSIGRecordContent>>* signatures, std::vector<std::shared_ptr<DNSRecord>>* authorityRecs, bool* variable, vState* state, bool* wasAuth);
 229
 230 public:
 231   struct lock {
 232     lock(MapCombo& map) : m(map.mutex)
 233     {
 234       if (!m.try_lock()) {
 235         m.lock();
 236         map.d_contended_count++;
 237       }
 238       map.d_acquired_count++;
 239     }
 240     ~lock() {
 241       m.unlock();
 242     }
 243   private:
 244     std::mutex &m;
 245   };
 246
 247   void preRemoval(const CacheEntry& entry)
 248   {
 249     if (entry.d_netmask.empty()) {
 250       return;
 251     }
 252
 253     auto key = tie(entry.d_qname, entry.d_qtype);
 254     auto& map = getMap(entry.d_qname);
 255     auto ecsIndexEntry = map.d_ecsIndex.find(key);
 256     if (ecsIndexEntry != map.d_ecsIndex.end()) {
 257       ecsIndexEntry->removeNetmask(entry.d_netmask);
 258       if (ecsIndexEntry->isEmpty()) {
 259         map.d_ecsIndex.erase(ecsIndexEntry);
 260       }
 261     }
 262   }
 263 };
 264
 265 namespace boost {
 266   size_t hash_value(const MemRecursorCache::OptTag& rtag);
 267 }