[thirdparty/pdns.git] / pdns / syncres.hh

#ifndef PDNS_SYNCRES_HH
#define PDNS_SYNCRES_HH
#include <string>
#include "dns.hh"
#include "qtype.hh"
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <iostream>
#include <utility>
#include "misc.hh"
#include "lwres.hh"
#include <boost/utility.hpp>
#include "sstuff.hh"
#include "recursor_cache.hh"
#include <boost/tuple/tuple.hpp>
#include <boost/optional.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include "mtasker.hh"
#include "iputils.hh"

void primeHints(void);

struct NegCacheEntry
{
  string d_name;
  QType d_qtype;
  string d_qname;
  uint32_t d_ttd;
};


template<class Thing> class Throttle
{
public:
  Throttle()
  {
    d_limit=3;
    d_ttl=60;
    d_last_clean=time(0);
  }
  bool shouldThrottle(time_t now, const Thing& t)
  {
    if(now > d_last_clean + 300 ) {
      d_last_clean=now;
      for(typename cont_t::iterator i=d_cont.begin();i!=d_cont.end();) {
	if( i->second.ttd < now) {
	  d_cont.erase(i++);
	}
	else
	  ++i;
      }
    }

    typename cont_t::iterator i=d_cont.find(t);
    if(i==d_cont.end())
      return false;
    if(now > i->second.ttd || i->second.count-- < 0) {
      d_cont.erase(i);
    }

    return true; // still listed, still blocked
  }
  void throttle(time_t now, const Thing& t, unsigned int ttl=0, unsigned int tries=0) 
  {
    typename cont_t::iterator i=d_cont.find(t);
    entry e={ now+(ttl ? ttl : d_ttl), tries ? tries : d_limit};

    if(i==d_cont.end()) {
      d_cont[t]=e;
    } 
    else if(i->second.ttd > e.ttd || (i->second.count) < e.count) 
      d_cont[t]=e;
  }
  
  unsigned int size()
  {
    return (unsigned int)d_cont.size();
  }
private:
  int d_limit;
  int d_ttl;
  time_t d_last_clean;
  struct entry 
  {
    time_t ttd;
    int count;
  };
  typedef map<Thing,entry> cont_t;
  cont_t d_cont;
};


/** Class that implements a decaying EWMA.
    This class keeps an exponentially weighted moving average which, additionally, decays over time.
    The decaying is only done on get.
*/
class DecayingEwma
{
public:
  DecayingEwma() :  d_val(0.0) 
  {
    d_needinit=true;
    d_lastget=d_last;
  }

  DecayingEwma(const DecayingEwma& orig) : d_last(orig.d_last),  d_lastget(orig.d_lastget), d_val(orig.d_val), d_needinit(orig.d_needinit)
  {
  }

  struct timeval getOrMakeTime(struct timeval* tv)
  {
    if(tv)
      return *tv;
    else {
      struct timeval ret;
      Utility::gettimeofday(&ret, 0);
      return ret;
    }
  }

  void submit(int val, struct timeval*tv = 0)
  {
    struct timeval now=getOrMakeTime(tv);

    if(d_needinit) {
      d_last=now;
      d_needinit=false;
    }

    float diff= makeFloat(d_last - now);

    d_last=now;
    double factor=exp(diff)/2.0; // might be '0.5', or 0.0001
    d_val=(float)((1-factor)*val+ (float)factor*d_val); 
  }

  double get(struct timeval*tv = 0)
  {
    struct timeval now=getOrMakeTime(tv);
    float diff=makeFloat(d_lastget-now);
    d_lastget=now;
    float factor=exp(diff/60.0f); // is 1.0 or less
    return d_val*=factor;
  }

  bool stale(time_t limit) const
  {
    return limit > d_lastget.tv_sec;
  }

private:
  struct timeval d_last;          // stores time
  struct timeval d_lastget;       // stores time
  float d_val;
  bool d_needinit;
};


class PulseRate
{
public:
  PulseRate() :  d_val(0.0) 
  {
    Utility::gettimeofday(&d_last, 0);
  }

  PulseRate(const PulseRate& orig) : d_last(orig.d_last), d_val(orig.d_val)
  {
  }

  void pulse(const struct timeval& now)
  {
    //    cout<<"about to submit: "<< 1000.0*makeFloat(now - d_last)<<"\n";
    submit((int)(1000.0*(makeFloat(now-d_last))), now);
  }

  optional<float> get(struct timeval& now, unsigned int limit) const
  {
    optional<float> ret;
    float diff=makeFloat(now - d_last);
    if(diff < limit)
      ret=d_val;
    return ret;
  }

  bool stale(time_t limit) const
  {
    return limit > d_last.tv_sec;
  }

private:
  void submit(int val, const struct timeval& now)
  {
    float diff= makeFloat(d_last - now);

    d_last=now;
    double factor=exp(diff/2.0)/2.0; // might be '0.5', or 0.0001
    d_val=(float)((1-factor)*val+ (float)factor*d_val); 
  }

  PulseRate& operator=(const PulseRate&);
  struct timeval d_last;          // stores time
  float d_val;
};


class SyncRes
{
public:
  explicit SyncRes(const struct timeval& now) :  d_outqueries(0), d_tcpoutqueries(0), d_throttledqueries(0), d_timeouts(0), d_unreachables(0),
						 d_now(now),
						 d_cacheonly(false), d_nocache(false) { }
  int beginResolve(const string &qname, const QType &qtype, uint16_t qclass, vector<DNSResourceRecord>&ret);
  void setId(int id)
  {
    if(s_log)
      d_prefix="["+itoa(id)+"] ";
  }
  static void setLog(bool log)
  {
    s_log=log;
  }
  void setCacheOnly(bool state=true)
  {
    d_cacheonly=state;
  }
  void setNoCache(bool state=true)
  {
    d_nocache=state;
  }
  static unsigned int s_queries;
  static unsigned int s_outgoingtimeouts;
  static unsigned int s_throttledqueries;
  static unsigned int s_outqueries;
  static unsigned int s_tcpoutqueries;
  static unsigned int s_nodelegated;
  static unsigned int s_unreachables;
  static bool s_doIPv6;
  unsigned int d_outqueries;
  unsigned int d_tcpoutqueries;
  unsigned int d_throttledqueries;
  unsigned int d_timeouts;
  unsigned int d_unreachables;

  //  typedef map<string,NegCacheEntry> negcache_t;

  typedef multi_index_container <
    NegCacheEntry,
    indexed_by <
       ordered_unique<
           composite_key<
                 NegCacheEntry,
                    member<NegCacheEntry, string, &NegCacheEntry::d_name>,
                    member<NegCacheEntry, QType, &NegCacheEntry::d_qtype>
           >,
           composite_key_compare<CIStringCompare, std::less<QType> >
       >,
       ordered_non_unique<
           member<NegCacheEntry, uint32_t, &NegCacheEntry::d_ttd>
       >
    >
  >negcache_t;
  static negcache_t s_negcache;    

  //! This represents a number of decaying Ewmas, used to store performance per namerserver-name. 
  /** Modelled to work mostly like the underlying DecayingEwma. After you've called get,
      d_best is filled out with the best address for this collection */
  struct DecayingEwmaCollection
  {
    void submit(const ComboAddress& remote, int usecs, struct timeval* now) 
    {
      collection_t::iterator pos;
      for(pos=d_collection.begin(); pos != d_collection.end(); ++pos)
	if(pos->first==remote)
	  break;
      if(pos!=d_collection.end()) {
	pos->second.submit(usecs, now);
      }
      else {
	DecayingEwma de;
	de.submit(usecs, now);
	d_collection.push_back(make_pair(remote, de));
      }
    }

    double get(struct timeval* now)
    {
      if(d_collection.empty())
	return 0;
      double ret=numeric_limits<double>::max();
      double tmp;
      for(collection_t::iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos) {
	if((tmp=pos->second.get()) < ret) {
	  ret=tmp;
	  d_best=pos->first;
	}
      }
      
      return ret;
    }
    
    bool stale(time_t limit) const
    {
      for(collection_t::const_iterator pos=d_collection.begin(); pos != d_collection.end(); ++pos) 
	if(!pos->second.stale(limit))
	  return false;
      return true;
    }

    typedef vector<pair<ComboAddress, DecayingEwma> > collection_t;
    collection_t d_collection;
    ComboAddress d_best;
  };

  typedef map<string, DecayingEwmaCollection , CIStringCompare> nsspeeds_t;
  static nsspeeds_t s_nsSpeeds;

  struct AuthDomain
  {
    string d_server;
    typedef multi_index_container <
      DNSResourceRecord,
      indexed_by < 
        ordered_non_unique< 
          composite_key< DNSResourceRecord,
		         member<DNSResourceRecord, string, &DNSResourceRecord::qname>,
		         member<DNSResourceRecord, QType, &DNSResourceRecord::qtype>
                       >,
          composite_key_compare<CIStringCompare, std::less<QType> >
        >
      >
    > records_t;
    records_t d_records;       
  };
  

  typedef map<string, AuthDomain, CIStringCompare> domainmap_t;
  static domainmap_t s_domainmap;

  typedef Throttle<tuple<ComboAddress,string,uint16_t> > throttle_t;
  static throttle_t s_throttle;
  struct timeval d_now;
  static unsigned int s_maxnegttl;
  static string s_serverID;
private:
  struct GetBestNSAnswer;
  int doResolveAt(set<string, CIStringCompare> nameservers, string auth, const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret,
		  int depth, set<GetBestNSAnswer>&beenthere);
  int doResolve(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, set<GetBestNSAnswer>& beenthere);
  bool doOOBResolve(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
  domainmap_t::const_iterator getBestAuthZone(string* qname);
  bool doCNAMECacheCheck(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
  bool doCacheCheck(const string &qname, const QType &qtype, vector<DNSResourceRecord>&ret, int depth, int &res);
  void getBestNSFromCache(const string &qname, set<DNSResourceRecord>&bestns, int depth, set<GetBestNSAnswer>& beenthere);
  void addCruft(const string &qname, vector<DNSResourceRecord>& ret);
  string getBestNSNamesFromCache(const string &qname,set<string, CIStringCompare>& nsset, int depth, set<GetBestNSAnswer>&beenthere);
  void addAuthorityRecords(const string& qname, vector<DNSResourceRecord>& ret, int depth);

  inline vector<string> shuffleInSpeedOrder(set<string, CIStringCompare> &nameservers, const string &prefix);
  bool moreSpecificThan(const string& a, const string &b);
  vector<ComboAddress> getAs(const string &qname, int depth, set<GetBestNSAnswer>& beenthere);

  SyncRes(const SyncRes&);
  SyncRes& operator=(const SyncRes&);


private:
  string d_prefix;
  static bool s_log;
  bool d_cacheonly;
  bool d_nocache;
  LWRes d_lwr;

  struct GetBestNSAnswer
  {
    string qname;
    set<DNSResourceRecord> bestns;
    bool operator<(const GetBestNSAnswer &b) const
    {
      if(qname<b.qname)
	return true;
      if(qname==b.qname)
	return bestns<b.bestns;
      return false;
    }
  };

};
class Socket;
/* external functions, opaque to us */
int asendtcp(const string& data, Socket* sock);
int arecvtcp(string& data, int len, Socket* sock);


struct PacketID
{
  PacketID() : id(0), sock(0), inNeeded(0), outPos(0), nearMisses(0), fd(-1)
  {
    memset(&remote, 0, sizeof(remote));
  }

  uint16_t id;  // wait for a specific id/remote pair
  ComboAddress remote;  // this is the remote
  string domain;             // this is the question 

  Socket* sock;  // or wait for an event on a TCP fd
  int inNeeded; // if this is set, we'll read until inNeeded bytes are read
  string inMSG; // they'll go here

  string outMSG; // the outgoing message that needs to be sent
  string::size_type outPos;    // how far we are along in the outMSG

  mutable uint32_t nearMisses; // number of near misses - host correct, id wrong
  int fd;

  bool operator<(const PacketID& b) const
  {
    int ourSock= sock ? sock->getHandle() : 0;
    int bSock = b.sock ? b.sock->getHandle() : 0;
    if( tie(id, remote, fd, ourSock) <
        tie(b.id, remote, b.fd, bSock))
      return true;
    if( tie(id, remote, fd, ourSock) >
        tie(b.id, remote, b.fd, bSock))
      return false;

    return Utility::strcasecmp(domain.c_str(), b.domain.c_str()) < 0;
  }
};

extern MemRecursorCache RC;
extern MTasker<PacketID,string>* MT;

struct RecursorStats
{
  uint64_t servFails;
  uint64_t nxDomains;
  uint64_t noErrors;
  PulseRate queryrate;
  uint64_t answers0_1, answers1_10, answers10_100, answers100_1000, answersSlow;
  uint64_t avgLatencyUsec;
  uint64_t qcounter;
  uint64_t tcpqcounter;
  uint64_t unauthorizedUDP;
  uint64_t unauthorizedTCP;
  uint64_t tcpClientOverflow;
  uint64_t clientParseError;
  uint64_t serverParseError;
  uint64_t unexpectedCount;
  uint64_t spoofCount;
  uint64_t resourceLimits;
  uint64_t ipv6queries;

  typedef vector<ComboAddress> remotes_t;
  remotes_t remotes;
  int d_remotepos;
  void addRemote(const ComboAddress& remote)
  {
    if(!remotes.size())
      return;

    remotes[(d_remotepos++) % remotes.size()]=remote;
  }
};

extern RecursorStats g_stats;


template<typename Index>
std::pair<typename Index::iterator,bool>
replacing_insert(Index& i,const typename Index::value_type& x)
{
  std::pair<typename Index::iterator,bool> res=i.insert(x);
  if(!res.second)res.second=i.replace(res.first,x);
  return res;
}

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