pdns/syncres.hh

   1 #ifndef PDNS_SYNCRES_HH
   2 #define PDNS_SYNCRES_HH
   3 #include <string>
   4 #include "dns.hh"
   5 #include "qtype.hh"
   6 #include <vector>
   7 #include <set>
   8 #include <map>
   9 #include <cmath>
  10 #include <iostream>
  11 #include <utility>
  12 #include "misc.hh"
  13 #include "lwres.hh"
  14 #include <boost/utility.hpp>
  15 #include "sstuff.hh"
  16 #include "recursor_cache.hh"
  17 #include <boost/tuple/tuple.hpp>
  18 #include <boost/optional.hpp>
  19 #include <boost/tuple/tuple_comparison.hpp>
  20 #include "mtasker.hh"
  21 #include "iputils.hh"
  22
  23 void primeHints(void);
  24
  25 struct NegCacheEntry
  26 {
  27   string d_name;
  28   QType d_qtype;
  29   string d_qname;
  30   uint32_t d_ttd;
  31 };
  32
  33
  34 template<class Thing> class Throttle
  35 {
  36 public:
  37   Throttle()
  38   {
  39     d_limit=3;
  40     d_ttl=60;
  41     d_last_clean=time(0);
  42   }
  43   bool shouldThrottle(time_t now, const Thing& t)
  44   {
  45     if(now > d_last_clean + 300 ) {
  46       d_last_clean=now;
  47       for(typename cont_t::iterator i=d_cont.begin();i!=d_cont.end();) {
  48         if( i->second.ttd < now) {
  49           d_cont.erase(i++);
  50         }
  51         else
  52           ++i;
  53       }
  54     }
  55
  56     typename cont_t::iterator i=d_cont.find(t);
  57     if(i==d_cont.end())
  58       return false;
  59     if(now > i->second.ttd || i->second.count-- < 0) {
  60       d_cont.erase(i);
  61     }
  62
  63     return true; // still listed, still blocked
  64   }
  65   void throttle(time_t now, const Thing& t, unsigned int ttl=0, unsigned int tries=0)
  66   {
  67     typename cont_t::iterator i=d_cont.find(t);
  68     entry e={ now+(ttl ? ttl : d_ttl), tries ? tries : d_limit};
  69
  70     if(i==d_cont.end()) {
  71       d_cont[t]=e;
  72     }
  73     else if(i->second.ttd > e.ttd || (i->second.count) < e.count)
  74       d_cont[t]=e;
  75   }
  76
  77   unsigned int size()
  78   {
  79     return (unsigned int)d_cont.size();
  80   }
  81 private:
  82   int d_limit;
  83   int d_ttl;
  84   time_t d_last_clean;
  85   struct entry
  86   {
  87     time_t ttd;
  88     int count;
  89   };
  90   typedef map<Thing,entry> cont_t;
  91   cont_t d_cont;
  92 };
  93
  94
  95 /** Class that implements a decaying EWMA.
  96     This class keeps an exponentially weighted moving average which, additionally, decays over time.
  97     The decaying is only done on get.
  98 */
  99 class DecayingEwma
 100 {
 101 public:
 102   DecayingEwma() :  d_val(0.0)
 103   {
 104     d_needinit=true;
 105     d_last.tv_sec = d_last.tv_usec = 0;
 106     d_lastget=d_last;
 107   }
 108
 109   DecayingEwma(const DecayingEwma& orig) : d_last(orig.d_last),  d_lastget(orig.d_lastget), d_val(orig.d_val), d_needinit(orig.d_needinit)
 110   {
 111   }
 112
 113   struct timeval getOrMakeTime(struct timeval* tv)
 114   {
 115     if(tv)
 116       return *tv;
 117     else {
 118       struct timeval ret;
 119       Utility::gettimeofday(&ret, 0);
 120       return ret;
 121     }
 122   }
 123
 124   void submit(int val, struct timeval* tv)
 125   {
 126     struct timeval now=getOrMakeTime(tv);
 127
 128     if(d_needinit) {
 129       d_last=now;
 130       d_needinit=false;
 131     }
 132
 133     float diff= makeFloat(d_last - now);
 134
 135     d_last=now;
 136     double factor=exp(diff)/2.0; // might be '0.5', or 0.0001
 137     d_val=(float)((1-factor)*val+ (float)factor*d_val);
 138   }
 139
 140   double get(struct timeval* tv)
 141   {
 142     struct timeval now=getOrMakeTime(tv);
 143     float diff=makeFloat(d_lastget-now);
 144     d_lastget=now;
 145     float factor=exp(diff/60.0f); // is 1.0 or less
 146     return d_val*=factor;
 147   }
 148
 149   bool stale(time_t limit) const
 150   {
 151     return limit > d_lastget.tv_sec;
 152   }
 153
 154 private:
 155   struct timeval d_last;          // stores time
 156   struct timeval d_lastget;       // stores time
 157   float d_val;
 158   bool d_needinit;
 159 };
 160
 161
 162 class PulseRate
 163 {
 164 public:
 165   PulseRate() :  d_val(0.0)
 166   {
 167     Utility::gettimeofday(&d_last, 0);
 168   }
 169
 170   PulseRate(const PulseRate& orig) : d_last(orig.d_last), d_val(orig.d_val)
 171   {
 172   }
 173
 174   void pulse(const struct timeval& now)
 175   {
 176     //    cout<<"about to submit: "<< 1000.0*makeFloat(now - d_last)<<"\n";
 177     submit((int)(1000.0*(makeFloat(now-d_last))), now);
 178   }
 179
 180   optional<float> get(struct timeval& now, unsigned int limit) const
 181   {
 182     optional<float> ret;
 183     float diff=makeFloat(now - d_last);
 184     if(diff < limit)
 185       ret=d_val;
 186     return ret;
 187   }
 188
 189   bool stale(time_t limit) const
 190   {
 191     return limit > d_last.tv_sec;
 192   }
 193
 194 private:
 195   void submit(int val, const struct timeval& now)
 196   {
 197     float diff= makeFloat(d_last - now);
 198
 199     d_last=now;
 200     double factor=exp(diff/2.0)/2.0; // might be '0.5', or 0.0001
 201     d_val=(float)((1-factor)*val+ (float)factor*d_val);
 202   }
 203
 204   PulseRate& operator=(const PulseRate&);
 205   struct timeval d_last;          // stores time
 206   float d_val;
 207 };
 208
 209
 210 class SyncRes
 211 {
 212 public:
 213   explicit SyncRes(const struct timeval& now) :  d_outqueries(0), d_tcpoutqueries(0), d_throttledqueries(0), d_timeouts(0), d_unreachables(0),
 214                                                  d_now(now),
 215                                                  d_cacheonly(false), d_nocache(false), d_doEDNS0(false) { }
 216   int beginResolve(const string &qname, const QType &qtype, uint16_t qclass, vector<DNSResourceRecord>&ret);
 217   void setId(int id)
 218   {
 219     if(s_log)
 220       d_prefix="["+itoa(id)+"] ";
 221   }
 222   static void setLog(bool log)
 223   {
 224     s_log=log;
 225   }
 226   void setCacheOnly(bool state=true)
 227   {
 228     d_cacheonly=state;
 229   }
 230   void setNoCache(bool state=true)
 231   {
 232     d_nocache=state;
 233   }
 234
 235   void setDoEDNS0(bool state=true)
 236   {
 237     d_doEDNS0=state;
 238   }
 239
 240   static unsigned int s_queries;
 241   static unsigned int s_outgoingtimeouts;
 242   static unsigned int s_throttledqueries;
 243   static unsigned int s_outqueries;
 244   static unsigned int s_tcpoutqueries;
 245   static unsigned int s_nodelegated;
 246   static unsigned int s_unreachables;
 247   static bool s_doIPv6;
 248   unsigned int d_outqueries;
 249   unsigned int d_tcpoutqueries;
 250   unsigned int d_throttledqueries;
 251   unsigned int d_timeouts;
 252   unsigned int d_unreachables;
 253
 254   //  typedef map<string,NegCacheEntry> negcache_t;
 255
 256   typedef multi_index_container <
 257     NegCacheEntry,
 258     indexed_by <
 259        ordered_unique<
 260            composite_key<
 261                  NegCacheEntry,
 262                     member<NegCacheEntry, string, &NegCacheEntry::d_name>,
 263                     member<NegCacheEntry, QType, &NegCacheEntry::d_qtype>
 264            >,
 265            composite_key_compare<CIStringCompare, std::less<QType> >
 266        >,
 267        ordered_non_unique<
 268            member<NegCacheEntry, uint32_t, &NegCacheEntry::d_ttd>
 269        >
 270     >
 271   >negcache_t;
 272   static negcache_t s_negcache;
 273
 274   //! This represents a number of decaying Ewmas, used to store performance per namerserver-name.
 275   /** Modelled to work mostly like the underlying DecayingEwma. After you've called get,
 276       d_best is filled out with the best address for this collection */
 277   struct DecayingEwmaCollection
 278   {
 279     void submit(const ComboAddress& remote, int usecs, struct timeval* now)
 280     {
 281       collection_t::iterator pos;
 282       for(pos=d_collection.begin(); pos != d_collection.end(); ++pos)
 283         if(pos->first==remote)
 284           break;
 285       if(pos!=d_collection.end()) {
 286         pos->second.submit(usecs, now);
 287       }
 288       else {
 289         DecayingEwma de;
 290         de.submit(usecs, now);
 291         d_collection.push_back(make_pair(remote, de));
 292       }
 293     }
 294
 295     double get(struct timeval* now)
 296     {
 297       if(d_collection.empty())
 298         return 0;
 299       double ret=numeric_limits<double>::max();
 300       double tmp;
 301       for(collection_t::iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos) {
 302         if((tmp=pos->second.get(now)) < ret) {
 303           ret=tmp;
 304           d_best=pos->first;
 305         }
 306       }
 307
 308       return ret;
 309     }
 310
 311     bool stale(time_t limit) const
 312     {
 313       for(collection_t::const_iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos)
 314         if(!pos->second.stale(limit))
 315           return false;
 316       return true;
 317     }
 318
 319     typedef vector<pair<ComboAddress, DecayingEwma> > collection_t;
 320     collection_t d_collection;
 321     ComboAddress d_best;
 322   };
 323
 324   typedef map<string, DecayingEwmaCollection , CIStringCompare> nsspeeds_t;
 325   static nsspeeds_t s_nsSpeeds;
 326
 327   struct AuthDomain
 328   {
 329     string d_server;
 330     typedef multi_index_container <
 331       DNSResourceRecord,
 332       indexed_by <
 333         ordered_non_unique<
 334           composite_key< DNSResourceRecord,
 335                          member<DNSResourceRecord, string, &DNSResourceRecord::qname>,
 336                          member<DNSResourceRecord, QType, &DNSResourceRecord::qtype>
 337                        >,
 338           composite_key_compare<CIStringCompare, std::less<QType> >
 339         >
 340       >
 341     > records_t;
 342     records_t d_records;
 343   };
 344
 345
 346   typedef map<string, AuthDomain, CIStringCompare> domainmap_t;
 347   static domainmap_t s_domainmap;
 348
 349   typedef Throttle<tuple<ComboAddress,string,uint16_t> > throttle_t;
 350   static throttle_t s_throttle;
 351   struct timeval d_now;
 352   static unsigned int s_maxnegttl;
 353   static string s_serverID;
 354 private:
 355   struct GetBestNSAnswer;
 356   int doResolveAt(set<string, CIStringCompare> nameservers, string auth, bool flawedNSSet, const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret,
 357                   int depth, set<GetBestNSAnswer>&beenthere);
 358   int doResolve(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, set<GetBestNSAnswer>& beenthere);
 359   bool doOOBResolve(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
 360   domainmap_t::const_iterator getBestAuthZone(string* qname);
 361   bool doCNAMECacheCheck(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
 362   bool doCacheCheck(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
 363   void getBestNSFromCache(const string &qname, set<DNSResourceRecord>&bestns, bool* flawedNSSet, int depth, set<GetBestNSAnswer>& beenthere);
 364   void addCruft(const string &qname, vector<DNSResourceRecord>& ret);
 365   string getBestNSNamesFromCache(const string &qname,set<string, CIStringCompare>& nsset, bool* flawedNSSet, int depth, set<GetBestNSAnswer>&beenthere);
 366   void addAuthorityRecords(const string& qname, vector<DNSResourceRecord>& ret, int depth);
 367
 368   inline vector<string> shuffleInSpeedOrder(set<string, CIStringCompare> &nameservers, const string &prefix);
 369   bool moreSpecificThan(const string& a, const string &b);
 370   vector<ComboAddress> getAs(const string &qname, int depth, set<GetBestNSAnswer>& beenthere);
 371
 372   SyncRes(const SyncRes&);
 373   SyncRes& operator=(const SyncRes&);
 374
 375
 376 private:
 377   string d_prefix;
 378   static bool s_log;
 379   bool d_cacheonly;
 380   bool d_nocache;
 381   bool d_doEDNS0;
 382
 383   struct GetBestNSAnswer
 384   {
 385     string qname;
 386     set<DNSResourceRecord> bestns;
 387     bool operator<(const GetBestNSAnswer &b) const
 388     {
 389       if(qname<b.qname)
 390         return true;
 391       if(qname==b.qname)
 392         return bestns<b.bestns;
 393       return false;
 394     }
 395   };
 396
 397 };
 398 class Socket;
 399 /* external functions, opaque to us */
 400 int asendtcp(const string& data, Socket* sock);
 401 int arecvtcp(string& data, int len, Socket* sock);
 402
 403
 404 struct PacketID
 405 {
 406   PacketID() : id(0), type(0), sock(0), inNeeded(0), outPos(0), nearMisses(0), fd(-1)
 407   {
 408     memset(&remote, 0, sizeof(remote));
 409   }
 410
 411   uint16_t id;  // wait for a specific id/remote pair
 412   ComboAddress remote;  // this is the remote
 413   string domain;             // this is the question
 414   uint16_t type;             // and this is its type
 415
 416   Socket* sock;  // or wait for an event on a TCP fd
 417   int inNeeded; // if this is set, we'll read until inNeeded bytes are read
 418   string inMSG; // they'll go here
 419
 420   string outMSG; // the outgoing message that needs to be sent
 421   string::size_type outPos;    // how far we are along in the outMSG
 422
 423   mutable uint32_t nearMisses; // number of near misses - host correct, id wrong
 424   typedef set<uint16_t > chain_t;
 425   mutable chain_t chain;
 426   int fd;
 427
 428   bool operator<(const PacketID& b) const
 429   {
 430     int ourSock= sock ? sock->getHandle() : 0;
 431     int bSock = b.sock ? b.sock->getHandle() : 0;
 432     if( tie(remote, ourSock, type) < tie(b.remote, bSock, b.type))
 433       return true;
 434     if( tie(remote, ourSock, type) > tie(b.remote, bSock, b.type))
 435       return false;
 436
 437     int cmp=Utility::strcasecmp(domain.c_str(), b.domain.c_str());
 438     if(cmp < 0)
 439       return true;
 440     if(cmp > 0)
 441       return false;
 442
 443     return tie(fd, id) < tie(b.fd, b.id);
 444   }
 445 };
 446
 447 struct PacketIDBirthdayCompare: public binary_function<PacketID, PacketID, bool>
 448 {
 449   bool operator()(const PacketID& a, const PacketID& b) const
 450   {
 451     int ourSock= a.sock ? a.sock->getHandle() : 0;
 452     int bSock = b.sock ? b.sock->getHandle() : 0;
 453     if( tie(a.remote, ourSock, a.type) < tie(b.remote, bSock, b.type))
 454       return true;
 455     if( tie(a.remote, ourSock, a.type) > tie(b.remote, bSock, b.type))
 456       return false;
 457
 458     int cmp=Utility::strcasecmp(a.domain.c_str(), b.domain.c_str());
 459     return cmp < 0;
 460   }
 461 };
 462 extern MemRecursorCache RC;
 463 typedef MTasker<PacketID,string> MT_t;
 464 extern MT_t* MT;
 465
 466 struct RecursorStats
 467 {
 468   uint64_t servFails;
 469   uint64_t nxDomains;
 470   uint64_t noErrors;
 471   PulseRate queryrate;
 472   uint64_t answers0_1, answers1_10, answers10_100, answers100_1000, answersSlow;
 473   uint64_t avgLatencyUsec;
 474   uint64_t qcounter;
 475   uint64_t tcpqcounter;
 476   uint64_t unauthorizedUDP;
 477   uint64_t unauthorizedTCP;
 478   uint64_t tcpClientOverflow;
 479   uint64_t clientParseError;
 480   uint64_t serverParseError;
 481   uint64_t unexpectedCount;
 482   uint64_t spoofCount;
 483   uint64_t resourceLimits;
 484   uint64_t ipv6queries;
 485   uint64_t chainResends;
 486   uint64_t nsSetInvalidations;
 487   uint64_t shunted;
 488   uint64_t noShuntCNAME, noShuntExpired, noShuntSize, noShuntNoMatch, noShuntWrongType, noShuntWrongQuestion;
 489   time_t startupTime;
 490
 491   typedef vector<ComboAddress> remotes_t;
 492   remotes_t remotes;
 493   int d_remotepos;
 494   void addRemote(const ComboAddress& remote)
 495   {
 496     if(!remotes.size())
 497       return;
 498
 499     remotes[(d_remotepos++) % remotes.size()]=remote;
 500   }
 501 };
 502
 503 extern RecursorStats g_stats;
 504
 505
 506 template<typename Index>
 507 std::pair<typename Index::iterator,bool>
 508 replacing_insert(Index& i,const typename Index::value_type& x)
 509 {
 510   std::pair<typename Index::iterator,bool> res=i.insert(x);
 511   if(!res.second)res.second=i.replace(res.first,x);
 512   return res;
 513 }
 514
 515
 516 std::string reloadAuthAndForwards();
 517 #endif