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 <mutex>
  25 #include "lock.hh"
  26
  27 // 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
  28 // the ritual is that the oldest entries are in *front* of the sequence collection, so on a hit, move an item to the end
  29 // on a miss, move it to the beginning
  30 template <typename S, typename C, typename T> void pruneCollection(C& container, T& collection, unsigned int maxCached, unsigned int scanFraction=1000)
  31 {
  32   time_t now=time(0);
  33   unsigned int toTrim=0;
  34
  35   unsigned int cacheSize=collection.size();
  36
  37   if(cacheSize > maxCached) {
  38     toTrim = cacheSize - maxCached;
  39   }
  40
  41 //  cout<<"Need to trim "<<toTrim<<" from cache to meet target!\n";
  42
  43   typedef typename T::template index<S>::type sequence_t;
  44   sequence_t& sidx=collection.template get<S>();
  45
  46   unsigned int tried=0, lookAt, erased=0;
  47
  48   // two modes - if toTrim is 0, just look through 1/scanFraction of all records
  49   // and nuke everything that is expired
  50   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
  51   if(toTrim)
  52     lookAt=5*toTrim;
  53   else
  54     lookAt=cacheSize/scanFraction;
  55
  56   typename sequence_t::iterator iter=sidx.begin(), eiter;
  57   for(; iter != sidx.end() && tried < lookAt ; ++tried) {
  58     if(iter->getTTD() < now) {
  59       container.preRemoval(*iter);
  60       iter = sidx.erase(iter);
  61       erased++;
  62     }
  63     else
  64       ++iter;
  65
  66     if(toTrim && erased >= toTrim)
  67       break;
  68   }
  69
  70   //cout<<"erased "<<erased<<" records based on ttd\n";
  71
  72   if(erased >= toTrim) // done
  73     return;
  74
  75   toTrim -= erased;
  76
  77   //if(toTrim)
  78     // cout<<"Still have "<<toTrim - erased<<" entries left to erase to meet target\n";
  79
  80   eiter=iter=sidx.begin();
  81   std::advance(eiter, toTrim);
  82   // just lob it off from the beginning
  83   for (auto i = iter; ; ) {
  84     if (i == eiter) {
  85       break;
  86     }
  87
  88     container.preRemoval(*i);
  89     sidx.erase(i++);
  90   }
  91 }
  92
  93 // note: this expects iterator from first index
  94 template <typename S, typename T> void moveCacheItemToFrontOrBack(T& collection, typename T::iterator& iter, bool front)
  95 {
  96   typedef typename T::template index<S>::type sequence_t;
  97   sequence_t& sidx=collection.template get<S>();
  98   typename sequence_t::iterator si=collection.template project<S>(iter);
  99   if(front)
 100     sidx.relocate(sidx.begin(), si); // at the beginning of the delete queue
 101   else
 102     sidx.relocate(sidx.end(), si);  // back
 103 }
 104
 105 template <typename S, typename T> void moveCacheItemToFront(T& collection, typename T::iterator& iter)
 106 {
 107   moveCacheItemToFrontOrBack<S>(collection, iter, true);
 108 }
 109
 110 template <typename S, typename T> void moveCacheItemToBack(T& collection, typename T::iterator& iter)
 111 {
 112   moveCacheItemToFrontOrBack<S>(collection, iter, false);
 113 }
 114
 115 template <typename S, typename T> uint64_t pruneLockedCollectionsVector(vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
 116 {
 117   time_t now = time(nullptr);
 118   uint64_t totErased = 0;
 119   uint64_t toTrim = 0;
 120   uint64_t lookAt = 0;
 121
 122   // two modes - if toTrim is 0, just look through 10%  of the cache and nuke everything that is expired
 123   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
 124   if (maxCached && cacheSize > maxCached) {
 125     toTrim = cacheSize - maxCached;
 126     lookAt = 5 * toTrim;
 127   } else {
 128     lookAt = cacheSize / 10;
 129   }
 130
 131   for(auto& mc : maps) {
 132     WriteLock wl(&mc.d_mut);
 133     auto& sidx = boost::multi_index::get<S>(mc.d_map);
 134     uint64_t erased = 0, lookedAt = 0;
 135     for(auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
 136       if (i->ttd < now) {
 137         i = sidx.erase(i);
 138         erased++;
 139       } else {
 140         ++i;
 141       }
 142
 143       if(toTrim && erased > toTrim / maps.size())
 144         break;
 145
 146       if(lookedAt > lookAt / maps.size())
 147         break;
 148     }
 149     totErased += erased;
 150   }
 151
 152   return totErased;
 153 }
 154
 155 template <typename S, typename C, typename T> uint64_t pruneMutexCollectionsVector(C& container, vector<T>& maps, uint64_t maxCached, uint64_t cacheSize)
 156 {
 157   time_t now = time(nullptr);
 158   uint64_t totErased = 0;
 159   uint64_t toTrim = 0;
 160   uint64_t lookAt = 0;
 161
 162   // two modes - if toTrim is 0, just look through 10%  of the cache and nuke everything that is expired
 163   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
 164   if (cacheSize > maxCached) {
 165     toTrim = cacheSize - maxCached;
 166     lookAt = 5 * toTrim;
 167   } else {
 168     lookAt = cacheSize / 10;
 169   }
 170
 171   uint64_t maps_size = maps.size();
 172   if (maps_size == 0)
 173       return 0;
 174
 175   for (auto& mc : maps) {
 176     const typename C::lock l(mc);
 177     mc.d_cachecachevalid = false;
 178     auto& sidx = boost::multi_index::get<S>(mc.d_map);
 179     uint64_t erased = 0, lookedAt = 0;
 180     for (auto i = sidx.begin(); i != sidx.end(); lookedAt++) {
 181       if (i->getTTD() < now) {
 182         container.preRemoval(*i);
 183         i = sidx.erase(i);
 184         erased++;
 185         mc.d_entriesCount--;
 186       } else {
 187         ++i;
 188       }
 189
 190       if (toTrim && erased >= toTrim / maps_size)
 191         break;
 192
 193       if (lookedAt > lookAt / maps_size)
 194         break;
 195     }
 196     totErased += erased;
 197     if (toTrim && totErased >= toTrim)
 198       break;
 199   }
 200
 201   if (totErased >= toTrim) { // done
 202     return totErased;
 203   }
 204
 205   toTrim -= totErased;
 206
 207   while (toTrim > 0) {
 208     size_t pershard = toTrim / maps_size + 1;
 209     for (auto& mc : maps) {
 210       const typename C::lock l(mc);
 211       mc.d_cachecachevalid = false;
 212       auto& sidx = boost::multi_index::get<S>(mc.d_map);
 213       size_t removed = 0;
 214       for (auto i = sidx.begin(); i != sidx.end() && removed < pershard; removed++) {
 215         container.preRemoval(*i);
 216         i = sidx.erase(i);
 217         mc.d_entriesCount--;
 218         totErased++;
 219         toTrim--;
 220         if (toTrim == 0) {
 221           break;
 222         }
 223       }
 224     }
 225   }
 226   return totErased;
 227 }
 228
 229 template <typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps)
 230 {
 231   uint64_t delcount=0;
 232
 233   for(auto& mc : maps) {
 234     WriteLock wl(&mc.d_mut);
 235     delcount += mc.d_map.size();
 236     mc.d_map.clear();
 237   }
 238
 239   return delcount;
 240 }
 241
 242 template <typename N, typename T> uint64_t purgeLockedCollectionsVector(vector<T>& maps, const std::string& match)
 243 {
 244   uint64_t delcount=0;
 245   string prefix(match);
 246   prefix.resize(prefix.size()-1);
 247   DNSName dprefix(prefix);
 248   for(auto& mc : maps) {
 249     WriteLock wl(&mc.d_mut);
 250     auto& idx = boost::multi_index::get<N>(mc.d_map);
 251     auto iter = idx.lower_bound(dprefix);
 252     auto start = iter;
 253
 254     for(; iter != idx.end(); ++iter) {
 255       if(!iter->qname.isPartOf(dprefix)) {
 256         break;
 257       }
 258       delcount++;
 259     }
 260     idx.erase(start, iter);
 261   }
 262
 263   return delcount;
 264 }
 265
 266 template <typename N, typename T> uint64_t purgeExactLockedCollection(T& mc, const DNSName& qname)
 267 {
 268   uint64_t delcount=0;
 269   WriteLock wl(&mc.d_mut);
 270   auto& idx = boost::multi_index::get<N>(mc.d_map);
 271   auto range = idx.equal_range(qname);
 272   if(range.first != range.second) {
 273     delcount += distance(range.first, range.second);
 274     idx.erase(range.first, range.second);
 275   }
 276
 277   return delcount;
 278 }
 279
 280 template<typename S, typename Index>
 281 std::pair<typename Index::iterator,bool>
 282 lruReplacingInsert(Index& i,const typename Index::value_type& x)
 283 {
 284   std::pair<typename Index::iterator,bool> res = i.insert(x);
 285   if (!res.second) {
 286     moveCacheItemToBack<S>(i, res.first);
 287     res.second = i.replace(res.first, x);
 288   }
 289   return res;
 290 }