pdns/cachecleaner.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
  24 #include "lock.hh"
  25
  26 // this function can clean any cache that has a getTTD() method on its entries, a preRemoval() method and a 'sequence' index as its second index
  27 // the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end
  28 // on a miss, move it to the beginning
  29 template <typename C, typename T> void pruneCollection(C& container, T& collection, unsigned int maxCached, unsigned int scanFraction=1000)
  30 {
  31   time_t now=time(0);
  32   unsigned int toTrim=0;
  33
  34   unsigned int cacheSize=collection.size();
  35
  36   if(cacheSize > maxCached) {
  37     toTrim = cacheSize - maxCached;
  38   }
  39
  40 //  cout<<"Need to trim "<<toTrim<<" from cache to meet target!\n";
  41
  42   typedef typename T::template nth_index<1>::type sequence_t;
  43   sequence_t& sidx=collection.template get<1>();
  44
  45   unsigned int tried=0, lookAt, erased=0;
  46
  47   // two modes - if toTrim is 0, just look through 1/scanFraction of all records
  48   // and nuke everything that is expired
  49   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
  50   if(toTrim)
  51     lookAt=5*toTrim;
  52   else
  53     lookAt=cacheSize/scanFraction;
  54
  55   typename sequence_t::iterator iter=sidx.begin(), eiter;
  56   for(; iter != sidx.end() && tried < lookAt ; ++tried) {
  57     if(iter->getTTD() < now) {
  58       container.preRemoval(*iter);
  59       sidx.erase(iter++);
  60       erased++;
  61     }
  62     else
  63       ++iter;
  64
  65     if(toTrim && erased >= toTrim)
  66       break;
  67   }
  68
  69   //cout<<"erased "<<erased<<" records based on ttd\n";
  70
  71   if(erased >= toTrim) // done
  72     return;
  73
  74   toTrim -= erased;
  75
  76   //if(toTrim)
  77     // cout<<"Still have "<<toTrim - erased<<" entries left to erase to meet target\n";
  78
  79   eiter=iter=sidx.begin();
  80   std::advance(eiter, toTrim);
  81   // just lob it off from the beginning
  82   for (auto i = iter; ; ) {
  83     if (i == eiter) {
  84       break;
  85     }
  86
  87     container.preRemoval(*i);
  88     sidx.erase(i++);
  89   }
  90 }
  91
  92 // note: this expects iterator from first index, and sequence MUST be second index!
  93 template <typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front)
  94 {
  95   typedef typename T::template nth_index<1>::type sequence_t;
  96   sequence_t& sidx=collection.template get<1>();
  97   typename sequence_t::iterator si=collection.template project<1>(iter);
  98   if(front)
  99     sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue
 100   else
 101     sidx.relocate(sidx.end(), si);  // back
 102 }
 103
 104 template <typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter)
 105 {
 106   moveCacheItemToFrontOrBack(collection, iter, true);
 107 }
 108
 109 template <typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter)
 110 {
 111   moveCacheItemToFrontOrBack(collection, iter, false);
 112 }
 113
 114 template <typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
 115 {
 116   time_t now = time(nullptr);
 117   uint64_t totErased = 0;
 118   uint64_t toTrim = 0;
 119   uint64_t lookAt = 0;
 120
 121   // two modes - if toTrim is 0, just look through 10%  of the cache and nuke everything that is expired
 122   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
 123   if (maxCached && cacheSize > maxCached) {
 124     toTrim = cacheSize - maxCached;
 125     lookAt = 5 * toTrim;
 126   } else {
 127     lookAt = cacheSize / 10;
 128   }
 129
 130   for(auto& mc : maps) {
 131     WriteLock wl(&mc.d_mut);
 132     auto& sidx = boost::multi_index::get<2>(mc.d_map);
 133     uint64_t erased = 0, lookedAt = 0;
 134     for(auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
 135       if(i->ttd < now) {
 136         i = sidx.erase(i);
 137         erased++;
 138       } else {
 139         ++i;
 140       }
 141
 142       if(toTrim && erased > toTrim / maps.size())
 143         break;
 144
 145       if(lookedAt > lookAt / maps.size())
 146         break;
 147     }
 148     totErased += erased;
 149   }
 150
 151   return totErased;
 152 }
 153
 154 template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps)
 155 {
 156   uint64_t delcount=0;
 157
 158   for(auto& mc : maps) {
 159     WriteLock wl(&mc.d_mut);
 160     delcount += mc.d_map.size();
 161     mc.d_map.clear();
 162   }
 163
 164   return delcount;
 165 }
 166
 167 template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match)
 168 {
 169   uint64_t delcount=0;
 170   string prefix(match);
 171   prefix.resize(prefix.size()-1);
 172   DNSName dprefix(prefix);
 173   for(auto& mc : maps) {
 174     WriteLock wl(&mc.d_mut);
 175     auto& idx = boost::multi_index::get<1>(mc.d_map);
 176     auto iter = idx.lower_bound(dprefix);
 177     auto start = iter;
 178
 179     for(; iter != idx.end(); ++iter) {
 180       if(!iter->qname.isPartOf(dprefix)) {
 181         break;
 182       }
 183       delcount++;
 184     }
 185     idx.erase(start, iter);
 186   }
 187
 188   return delcount;
 189 }
 190
 191 template <typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname)
 192 {
 193   uint64_t delcount=0;
 194   WriteLock wl(&mc.d_mut);
 195   auto& idx = boost::multi_index::get<1>(mc.d_map);
 196   auto range = idx.equal_range(qname);
 197   if(range.first != range.second) {
 198     delcount += distance(range.first, range.second);
 199     idx.erase(range.first, range.second);
 200   }
 201
 202   return delcount;
 203 }
 204
 205 template<typename Index>
 206 std::pair<typename Index::iterator,bool>
 207 lruReplacingInsert(Index& i,const typename Index::value_type& x)
 208 {
 209   std::pair<typename Index::iterator,bool> res = i.insert(x);
 210   if (!res.second) {
 211     moveCacheItemToBack(i, res.first);
 212     res.second = i.replace(res.first, x);
 213   }
 214   return res;
 215 }