pdns/packetcache.cc

   1 /*
   2     PowerDNS Versatile Database Driven Nameserver
   3     Copyright (C) 2002 - 2011  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   if(d_doRecursion && p->d.rd) { // wants recursion
  62     if(!d_recursivettl) {
  63       (*d_statnummiss)++;
  64       return 0;
  65     }
  66   }
  67   else { // does not
  68     if(!d_ttl) {
  69       (*d_statnummiss)++;
  70       return 0;
  71     }
  72   }
  73
  74   bool packetMeritsRecursion=d_doRecursion && p->d.rd;
  75   if(ntohs(p->d.qdcount)!=1) // we get confused by packets with more than one question
  76     return 0;
  77
  78   string value;
  79   bool haveSomething;
  80   {
  81     TryReadLock l(&d_mut); // take a readlock here
  82     if(!l.gotIt()) {
  83       S.inc("deferred-cache-lookup");
  84       return 0;
  85     }
  86
  87     uint16_t maxReplyLen = p->d_tcp ? 0xffff : p->getMaxReplyLen();
  88     haveSomething=getEntryLocked(p->qdomain, p->qtype, PacketCache::PACKETCACHE, value, -1, packetMeritsRecursion, maxReplyLen, p->d_dnssecOk, p->hasEDNS());
  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); // for correct case
  96     cached->qdomain=p->qdomain;
  97     cached->qtype=p->qtype;
  98     return 1;
  99   }
 100
 101   //  cerr<<"Packet cache miss for '"<<p->qdomain<<"', merits: "<<packetMeritsRecursion<<endl;
 102   (*d_statnummiss)++;
 103   return 0; // bummer
 104 }
 105
 106 void PacketCache::getTTLS()
 107 {
 108   d_ttl=::arg().asNum("cache-ttl");
 109   d_recursivettl=::arg().asNum("recursive-cache-ttl");
 110
 111   d_doRecursion=::arg().mustDo("recursor");
 112 }
 113
 114
 115 void PacketCache::insert(DNSPacket *q, DNSPacket *r, unsigned int maxttl)
 116 {
 117   if(d_ttl < 0)
 118     getTTLS();
 119
 120   if(ntohs(q->d.qdcount)!=1) {
 121     return; // do not try to cache packets with multiple questions
 122   }
 123
 124   if(q->qclass != QClass::IN) // we only cache the INternet
 125     return;
 126
 127   bool packetMeritsRecursion=d_doRecursion && q->d.rd;
 128   uint16_t maxReplyLen = q->d_tcp ? 0xffff : q->getMaxReplyLen();
 129   unsigned int ourttl = packetMeritsRecursion ? d_recursivettl : d_ttl;
 130   if(maxttl<ourttl)
 131     ourttl=maxttl;
 132   insert(q->qdomain, q->qtype, PacketCache::PACKETCACHE, r->getString(), ourttl, -1, packetMeritsRecursion,
 133     maxReplyLen, q->d_dnssecOk, q->hasEDNS());
 134 }
 135
 136 // universal key appears to be: qname, qtype, kind (packet, query cache), optionally zoneid, meritsRecursion
 137 void PacketCache::insert(const string &qname, const QType& qtype, CacheEntryType cet, const string& value, unsigned int ttl, int zoneID,
 138   bool meritsRecursion, unsigned int maxReplyLen, bool dnssecOk, bool EDNS)
 139 {
 140   if(!((++d_ops) % 300000)) {
 141     cleanup();
 142   }
 143
 144   if(!ttl)
 145     return;
 146
 147   //cerr<<"Inserting qname '"<<qname<<"', cet: "<<(int)cet<<", qtype: "<<qtype.getName()<<", ttl: "<<ttl<<", maxreplylen: "<<maxReplyLen<<", hasEDNS: "<<EDNS<<endl;
 148   CacheEntry val;
 149   val.ttd=time(0)+ttl;
 150   val.qname=qname;
 151   val.qtype=qtype.getCode();
 152   val.value=value;
 153   val.ctype=cet;
 154   val.meritsRecursion=meritsRecursion;
 155   val.maxReplyLen = maxReplyLen;
 156   val.dnssecOk = dnssecOk;
 157   val.zoneID = zoneID;
 158   val.hasEDNS = EDNS;
 159
 160   TryWriteLock l(&d_mut);
 161   if(l.gotIt()) {
 162     bool success;
 163     cmap_t::iterator place;
 164     tie(place, success)=d_map.insert(val);
 165     //    cerr<<"Insert succeeded: "<<success<<endl;
 166     if(!success)
 167       d_map.replace(place, val);
 168
 169   }
 170   else
 171     S.inc("deferred-cache-inserts");
 172 }
 173
 174 /* clears the entire packetcache. */
 175 int PacketCache::purge()
 176 {
 177   WriteLock l(&d_mut);
 178   int delcount=d_map.size();
 179   d_map.clear();
 180   *d_statnumentries=0;
 181   return delcount;
 182 }
 183
 184 /* purges entries from the packetcache. If match ends on a $, it is treated as a suffix */
 185 int PacketCache::purge(const string &match)
 186 {
 187   WriteLock l(&d_mut);
 188   int delcount=0;
 189
 190   /* ok, the suffix delete plan. We want to be able to delete everything that
 191      pertains 'www.powerdns.com' but we also want to be able to delete everything
 192      in the powerdns.com zone, so: 'powerdns.com' and '*.powerdns.com'.
 193
 194      However, we do NOT want to delete 'usepowerdns.com!, nor 'powerdnsiscool.com'
 195
 196      So, at first shot, store in reverse label order:
 197
 198      'be.someotherdomain'
 199      'com.powerdns'
 200      'com.powerdns.images'
 201      'com.powerdns.www'
 202      'com.powerdnsiscool'
 203      'com.usepowerdns.www'
 204
 205      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!)
 206      Then we delete everything that is either equal to 'com.powerdns' or begins with 'com.powerdns.' This trailing dot saves us
 207      from deleting 'com.powerdnsiscool'.
 208
 209      We can stop the process once we reach something that doesn't match.
 210
 211      Ok - fine so far, except it doesn't work! Let's say there *is* no 'com.powerdns' in cache!
 212
 213      In that case our request doesn't find anything.. now what.
 214      lower_bound to the rescue! It finds the place where 'com.powerdns' *would* be.
 215
 216      Ok - next step, can we get away with simply reversing the string?
 217
 218      'moc.sndrewop'
 219      'moc.sndrewop.segami'
 220      'moc.sndrewop.www'
 221      'moc.loocsidnsrewop'
 222      'moc.dnsrewopesu.www'
 223
 224      Ok - next step, can we get away with only reversing the comparison?
 225
 226      'powerdns.com'
 227      'images.powerdns.com'
 228      '   www.powerdns.com'
 229      'powerdnsiscool.com'
 230      'www.userpowerdns.com'
 231
 232   */
 233   if(ends_with(match, "$")) {
 234     string suffix(match);
 235     suffix.resize(suffix.size()-1);
 236
 237     cmap_t::const_iterator iter = d_map.lower_bound(tie(suffix));
 238     cmap_t::const_iterator start=iter;
 239     string dotsuffix = "."+suffix;
 240
 241     for(; iter != d_map.end(); ++iter) {
 242       if(!pdns_iequals(iter->qname, suffix) && !iends_with(iter->qname, dotsuffix)) {
 243         //      cerr<<"Stopping!"<<endl;
 244         break;
 245       }
 246       delcount++;
 247     }
 248     d_map.erase(start, iter);
 249   }
 250   else {
 251     delcount=d_map.count(tie(match));
 252     pair<cmap_t::iterator, cmap_t::iterator> range = d_map.equal_range(tie(match));
 253     d_map.erase(range.first, range.second);
 254   }
 255   *d_statnumentries=d_map.size();
 256   return delcount;
 257 }
 258 // called from ueberbackend
 259 bool PacketCache::getEntry(const string &qname, const QType& qtype, CacheEntryType cet, string& value, int zoneID, bool meritsRecursion,
 260   unsigned int maxReplyLen, bool dnssecOk, bool hasEDNS)
 261 {
 262   if(d_ttl<0)
 263     getTTLS();
 264
 265   if(!((++d_ops) % 300000)) {
 266     cleanup();
 267   }
 268
 269   TryReadLock l(&d_mut); // take a readlock here
 270   if(!l.gotIt()) {
 271     S.inc( "deferred-cache-lookup");
 272     return false;
 273   }
 274
 275   return getEntryLocked(qname, qtype, cet, value, zoneID, meritsRecursion, maxReplyLen, dnssecOk, hasEDNS);
 276 }
 277
 278
 279 bool PacketCache::getEntryLocked(const string &qname, const QType& qtype, CacheEntryType cet, string& value, int zoneID, bool meritsRecursion,
 280   unsigned int maxReplyLen, bool dnssecOK, bool hasEDNS)
 281 {
 282   uint16_t qt = qtype.getCode();
 283   //cerr<<"Lookup for maxReplyLen: "<<maxReplyLen<<endl;
 284   cmap_t::const_iterator i=d_map.find(tie(qname, qt, cet, zoneID, meritsRecursion, maxReplyLen, dnssecOK, hasEDNS));
 285   time_t now=time(0);
 286   bool ret=(i!=d_map.end() && i->ttd > now);
 287   if(ret)
 288     value = i->value;
 289
 290   return ret;
 291 }
 292
 293 map<char,int> PacketCache::getCounts()
 294 {
 295   ReadLock l(&d_mut);
 296
 297   map<char,int>ret;
 298   int recursivePackets=0, nonRecursivePackets=0, queryCacheEntries=0, negQueryCacheEntries=0;
 299
 300   for(cmap_t::const_iterator iter = d_map.begin() ; iter != d_map.end(); ++iter) {
 301     if(iter->ctype == PACKETCACHE)
 302       if(iter->meritsRecursion)
 303         recursivePackets++;
 304       else
 305         nonRecursivePackets++;
 306     else if(iter->ctype == QUERYCACHE) {
 307       if(iter->value.empty())
 308         negQueryCacheEntries++;
 309       else
 310         queryCacheEntries++;
 311     }
 312   }
 313   ret['!']=negQueryCacheEntries;
 314   ret['Q']=queryCacheEntries;
 315   ret['n']=nonRecursivePackets;
 316   ret['r']=recursivePackets;
 317   return ret;
 318 }
 319
 320 int PacketCache::size()
 321 {
 322   ReadLock l(&d_mut);
 323   return d_map.size();
 324 }
 325
 326 /** readlock for figuring out which iterators to delete, upgrade to writelock when actually cleaning */
 327 void PacketCache::cleanup()
 328 {
 329   WriteLock l(&d_mut);
 330
 331   *d_statnumentries=d_map.size();
 332
 333   unsigned int maxCached=::arg().asNum("max-cache-entries");
 334   unsigned int toTrim=0;
 335
 336   unsigned int cacheSize=*d_statnumentries;
 337
 338   if(maxCached && cacheSize > maxCached) {
 339     toTrim = cacheSize - maxCached;
 340   }
 341
 342   unsigned int lookAt=0;
 343   // two modes - if toTrim is 0, just look through 10%  of the cache and nuke everything that is expired
 344   // otherwise, scan first 5*toTrim records, and stop once we've nuked enough
 345   if(toTrim)
 346     lookAt=5*toTrim;
 347   else
 348     lookAt=cacheSize/10;
 349
 350   //  cerr<<"cacheSize: "<<cacheSize<<", lookAt: "<<lookAt<<", toTrim: "<<toTrim<<endl;
 351   time_t now=time(0);
 352
 353   DLOG(L<<"Starting cache clean"<<endl);
 354   if(d_map.empty())
 355     return; // clean
 356
 357   typedef cmap_t::nth_index<1>::type sequence_t;
 358   sequence_t& sidx=d_map.get<1>();
 359   unsigned int erased=0, lookedAt=0;
 360   for(sequence_t::iterator i=sidx.begin(); i != sidx.end(); lookedAt++) {
 361     if(i->ttd < now) {
 362       sidx.erase(i++);
 363       erased++;
 364     }
 365     else
 366       ++i;
 367
 368     if(toTrim && erased > toTrim)
 369       break;
 370
 371     if(lookedAt > lookAt)
 372       break;
 373   }
 374   //  cerr<<"erased: "<<erased<<endl;
 375   *d_statnumentries=d_map.size();
 376   DLOG(L<<"Done with cache clean"<<endl);
 377 }