pdns/packetcache.cc

   1 /*
   2     PowerDNS Versatile Database Driven Nameserver
   3     Copyright (C) 2002 - 2008  PowerDNS.COM BV
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License version 2 as
   7     published by the Free Software Foundation
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program; if not, write to the Free Software
  16     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17 */
  18 #include "utility.hh"
  19 #include "packetcache.hh"
  20 #include "logger.hh"
  21 #include "arguments.hh"
  22 #include "statbag.hh"
  23 #include <map>
  24 #include <boost/algorithm/string.hpp>
  25
  26 extern StatBag S;
  27
  28 PacketCache::PacketCache()
  29 {
  30   pthread_rwlock_init(&d_mut,0);
  31   d_ops = 0;
  32
  33   d_ttl=-1;
  34   d_recursivettl=-1;
  35
  36   S.declare("packetcache-hit");
  37   S.declare("packetcache-miss");
  38   S.declare("packetcache-size");
  39
  40   d_statnumhit=S.getPointer("packetcache-hit");
  41   d_statnummiss=S.getPointer("packetcache-miss");
  42   d_statnumentries=S.getPointer("packetcache-size");
  43 }
  44
  45 PacketCache::~PacketCache()
  46 {
  47   WriteLock l(&d_mut);
  48 }
  49
  50 int PacketCache::get(DNSPacket *p, DNSPacket *cached)
  51 {
  52   extern StatBag S;
  53
  54   if(d_ttl<0)
  55     getTTLS();
  56
  57   if(!((d_ops++) % 300000)) {
  58     cleanup();
  59   }
  60
  61
  62   if(d_doRecursion && p->d.rd) { // wants recursion
  63     if(!d_recursivettl) {
  64       (*d_statnummiss)++;
  65       return 0;
  66     }
  67   }
  68   else { // does not
  69     if(!d_ttl) {
  70       (*d_statnummiss)++;
  71       return 0;
  72     }
  73   }
  74
  75   bool packetMeritsRecursion=d_doRecursion && p->d.rd;
  76   if(ntohs(p->d.qdcount)!=1) // we get confused by packets with more than one question
  77     return 0;
  78
  79   string value;
  80   bool haveSomething;
  81   {
  82     TryReadLock l(&d_mut); // take a readlock here
  83     if(!l.gotIt()) {
  84       S.inc("deferred-cache-lookup");
  85       return 0;
  86     }
  87
  88     haveSomething=getEntryLocked(p->qdomain, p->qtype, PacketCache::PACKETCACHE, value, -1, packetMeritsRecursion);
  89   }
  90   if(haveSomething) {
  91     (*d_statnumhit)++;
  92     if(cached->noparse(value.c_str(), value.size()) < 0) {
  93       return 0;
  94     }
  95     cached->spoofQuestion(p->qdomain); // for correct case
  96     return 1;
  97   }
  98
  99   //  cerr<<"Packet cache miss for '"<<p->qdomain<<"', merits: "<<packetMeritsRecursion<<endl;
 100   (*d_statnummiss)++;
 101   return 0; // bummer
 102 }
 103
 104 void PacketCache::getTTLS()
 105 {
 106   d_ttl=::arg().asNum("cache-ttl");
 107   d_recursivettl=::arg().asNum("recursive-cache-ttl");
 108
 109   d_doRecursion=::arg().mustDo("recursor");
 110 }
 111
 112
 113 void PacketCache::insert(DNSPacket *q, DNSPacket *r)
 114 {
 115   if(d_ttl < 0)
 116     getTTLS();
 117
 118   if(ntohs(q->d.qdcount)!=1) {
 119     return; // do not try to cache packets with multiple questions
 120   }
 121
 122   bool packetMeritsRecursion=d_doRecursion && q->d.rd;
 123
 124   insert(q->qdomain, q->qtype, PacketCache::PACKETCACHE, r->getString(), packetMeritsRecursion ? d_recursivettl : d_ttl, -1, packetMeritsRecursion);
 125 }
 126
 127 // universal key appears to be: qname, qtype, kind (packet, query cache), optionally zoneid, meritsRecursion
 128 void PacketCache::insert(const string &qname, const QType& qtype, CacheEntryType cet, const string& value, unsigned int ttl, int zoneID, bool meritsRecursion)
 129 {
 130   if(!((d_ops++) % 300000)) {
 131     cleanup();
 132   }
 133
 134   if(!ttl)
 135     return;
 136
 137   //  cerr<<"Inserting qname '"<<qname<<"', cet: "<<(int)cet<<", value: '"<< (cet ? value : "PACKET") <<"', qtype: "<<qtype.getName()<<", ttl: "<<ttl<<endl;
 138   CacheEntry val;
 139   val.ttd=time(0)+ttl;
 140   val.qname=qname;
 141   val.qtype=qtype.getCode();
 142   val.value=value;
 143   val.ctype=cet;
 144   val.meritsRecursion=meritsRecursion;
 145
 146   TryWriteLock l(&d_mut);
 147   if(l.gotIt()) {
 148     bool success;
 149     cmap_t::iterator place;
 150     tie(place, success)=d_map.insert(val);
 151     //    cerr<<"Insert succeeded: "<<success<<endl;
 152     if(!success)
 153       d_map.replace(place, val);
 154
 155   }
 156   else
 157     S.inc("deferred-cache-inserts");
 158 }
 159
 160 /** purges entries from the packetcache. If match ends on a $, it is treated as a suffix */
 161 int PacketCache::purge(const vector<string> &matches)
 162 {
 163   WriteLock l(&d_mut);
 164   int delcount=0;
 165
 166   if(matches.empty()) {
 167     delcount = d_map.size();
 168     d_map.clear();
 169     *d_statnumentries=0;
 170     return delcount;
 171   }
 172
 173   /* ok, the suffix delete plan. We want to be able to delete everything that
 174      pertains 'www.powerdns.com' but we also want to be able to delete everything
 175      in the powerdns.com zone, so: 'powerdns.com' and '*.powerdns.com'.
 176
 177      However, we do NOT want to delete 'usepowerdns.com!, nor 'powerdnsiscool.com'
 178
 179      So, at first shot, store in reverse label order:
 180
 181      'be.someotherdomain'
 182      'com.powerdns'
 183      'com.powerdns.images'
 184      'com.powerdns.www'
 185      'com.powerdnsiscool'
 186      'com.usepowerdns.www'
 187
 188      If we get a request to remove 'everything above powerdns.com', we do a search for 'com.powerdns' which is guaranteed to come first (it is shortest!)
 189      Then we delete everything that is either equal to 'com.powerdns' or begins with 'com.powerdns.' This trailing dot saves us
 190      from deleting 'com.powerdnsiscool'.
 191
 192      We can stop the process once we reach something that doesn't match.
 193
 194      Ok - fine so far, except it doesn't work! Let's say there *is* no 'com.powerdns' in cache!
 195
 196      In that case our request doesn't find anything.. now what.
 197      lower_bound to the rescue! It finds the place where 'com.powerdns' *would* be.
 198
 199      Ok - next step, can we get away with simply reversing the string?
 200
 201      'moc.sndrewop'
 202      'moc.sndrewop.segami'
 203      'moc.sndrewop.www'
 204      'moc.loocsidnsrewop'
 205      'moc.dnsrewopesu.www'
 206
 207      Ok - next step, can we get away with only reversing the comparison?
 208
 209      'powerdns.com'
 210      'images.powerdns.com'
 211      '   www.powerdns.com'
 212      'powerdnsiscool.com'
 213      'www.userpowerdns.com'
 214
 215   */
 216   for(vector<string>::const_iterator match = ++matches.begin(); match != matches.end() ; ++match) {
 217     if(ends_with(*match, "$")) {
 218       string suffix(*match);
 219       suffix.resize(suffix.size()-1);
 220
 221       //    cerr<<"Begin dump!"<<endl;
 222       cmap_t::const_iterator iter = d_map.lower_bound(tie(suffix));
 223       cmap_t::const_iterator start=iter;
 224       string dotsuffix = "."+suffix;
 225
 226       for(; iter != d_map.end(); ++iter) {
 227         if(!pdns_iequals(iter->qname, suffix) && !iends_with(iter->qname, dotsuffix)) {
 228           //    cerr<<"Stopping!"<<endl;
 229           break;
 230         }
 231         //      cerr<<"Will erase '"<<iter->qname<<"'\n";
 232
 233         delcount++;
 234       }
 235       //    cerr<<"End dump!"<<endl;
 236       d_map.erase(start, iter);
 237     }
 238     else {
 239       delcount=d_map.count(tie(*match));
 240       pair<cmap_t::iterator, cmap_t::iterator> range = d_map.equal_range(tie(*match));
 241       d_map.erase(range.first, range.second);
 242     }
 243   }
 244   *d_statnumentries=d_map.size();
 245   return delcount;
 246 }
 247
 248 bool PacketCache::getEntry(const string &qname, const QType& qtype, CacheEntryType cet, string& value, int zoneID, bool meritsRecursion)
 249 {
 250   if(d_ttl<0)
 251     getTTLS();
 252
 253   if(!((d_ops++) % 300000)) {
 254     cleanup();
 255   }
 256
 257   TryReadLock l(&d_mut); // take a readlock here
 258   if(!l.gotIt()) {
 259     S.inc( "deferred-cache-lookup");
 260     return false;
 261   }
 262   return getEntryLocked(qname, qtype, cet, value, zoneID, meritsRecursion);
 263 }
 264
 265 bool PacketCache::getEntryLocked(const string &qname, const QType& qtype, CacheEntryType cet, string& value, int zoneID, bool meritsRecursion)
 266 {
 267
 268   uint16_t qt = qtype.getCode();
 269   cmap_t::const_iterator i=d_map.find(tie(qname, qt, cet, zoneID, meritsRecursion));
 270   time_t now=time(0);
 271   bool ret=(i!=d_map.end() && i->ttd > now);
 272   if(ret)
 273     value = i->value;
 274
 275   return ret;
 276 }
 277
 278 map<char,int> PacketCache::getCounts()
 279 {
 280   ReadLock l(&d_mut);
 281
 282   map<char,int>ret;
 283   int recursivePackets=0, nonRecursivePackets=0, queryCacheEntries=0, negQueryCacheEntries=0;
 284
 285   for(cmap_t::const_iterator iter = d_map.begin() ; iter != d_map.end(); ++iter) {
 286     if(iter->ctype == PACKETCACHE)
 287       if(iter->meritsRecursion)
 288         recursivePackets++;
 289       else
 290         nonRecursivePackets++;
 291     else if(iter->ctype == QUERYCACHE) {
 292       if(iter->value.empty())
 293         negQueryCacheEntries++;
 294       else
 295         queryCacheEntries++;
 296     }
 297   }
 298   ret['!']=negQueryCacheEntries;
 299   ret['Q']=queryCacheEntries;
 300   ret['n']=nonRecursivePackets;
 301   ret['r']=recursivePackets;
 302   return ret;
 303 }
 304
 305 int PacketCache::size()
 306 {
 307   ReadLock l(&d_mut);
 308   return d_map.size();
 309 }
 310
 311 /** readlock for figuring out which iterators to delete, upgrade to writelock when actually cleaning */
 312 void PacketCache::cleanup()
 313 {
 314   WriteLock l(&d_mut);
 315
 316   *d_statnumentries=d_map.size();
 317
 318   unsigned int maxCached=::arg().asNum("max-cache-entries");
 319   unsigned int toTrim=0;
 320
 321   unsigned int cacheSize=*d_statnumentries;
 322
 323   if(maxCached && cacheSize > maxCached) {
 324     toTrim = cacheSize - maxCached;
 325   }
 326
 327   unsigned int lookAt=0;
 328   // two modes - if toTrim is 0, just look through 10%  of the cache and nuke everything that is expired
 329   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
 330   if(toTrim)
 331     lookAt=5*toTrim;
 332   else
 333     lookAt=cacheSize/10;
 334
 335   //  cerr<<"cacheSize: "<<cacheSize<<", lookAt: "<<lookAt<<", toTrim: "<<toTrim<<endl;
 336   time_t now=time(0);
 337
 338   DLOG(L<<"Starting cache clean"<<endl);
 339   if(d_map.empty())
 340     return; // clean
 341
 342   typedef cmap_t::nth_index<1>::type sequence_t;
 343   sequence_t& sidx=d_map.get<1>();
 344   unsigned int erased=0, lookedAt=0;
 345   for(sequence_t::iterator i=sidx.begin(); i != sidx.end(); lookedAt++) {
 346     if(i->ttd < now) {
 347       sidx.erase(i++);
 348       erased++;
 349     }
 350     else
 351       ++i;
 352
 353     if(toTrim && erased > toTrim)
 354       break;
 355
 356     if(lookedAt > lookAt)
 357       break;
 358   }
 359   //  cerr<<"erased: "<<erased<<endl;
 360   *d_statnumentries=d_map.size();
 361   DLOG(L<<"Done with cache clean"<<endl);
 362 }