From 49a3500d03dea35e46bf08b3d171adcbd3da23ae Mon Sep 17 00:00:00 2001 From: bert hubert Date: Wed, 20 Jan 2016 15:56:17 +0100 Subject: [PATCH] revamp recursor packet cache to be far less clever and simply hash its question case insensitively. Plus add testcases. --- pdns/Makefile.am | 2 + pdns/dns.hh | 83 ------------------ pdns/pdns_recursor.cc | 27 +++--- pdns/recpacketcache.cc | 155 +++++++++++++++++++-------------- pdns/recpacketcache.hh | 45 ++++------ pdns/test-recpacketcache_cc.cc | 70 +++++++++++++++ 6 files changed, 193 insertions(+), 189 deletions(-) create mode 100644 pdns/test-recpacketcache_cc.cc diff --git a/pdns/Makefile.am b/pdns/Makefile.am index 2fae51392..5b5fb0a4a 100644 --- a/pdns/Makefile.am +++ b/pdns/Makefile.am @@ -1070,6 +1070,7 @@ testrunner_SOURCES = \ packetcache.cc \ qtype.cc \ rcpgenerator.cc \ + recpacketcache.cc \ responsestats.cc \ responsestats-auth.cc \ sillyrecords.cc \ @@ -1090,6 +1091,7 @@ testrunner_SOURCES = \ test-nmtree.cc \ test-packetcache_cc.cc \ test-rcpgenerator_cc.cc \ + test-recpacketcache_cc.cc \ test-sha_hh.cc \ test-statbag_cc.cc \ test-zoneparser_tng_cc.cc \ diff --git a/pdns/dns.hh b/pdns/dns.hh index 1125b8d2a..d0beef732 100644 --- a/pdns/dns.hh +++ b/pdns/dns.hh @@ -245,89 +245,6 @@ extern time_t s_starttime; uint32_t hashQuestion(const char* packet, uint16_t len, uint32_t init); -//! compares two dns packets in canonical order, skipping the header, but including the question and the qtype -inline bool dnspacketLessThan(const std::string& a, const std::string& b) -{ - /* BEFORE YOU ATTEMPT TO MERGE THIS WITH DNSNAME::CANONICALCOMPARE! - Please note that that code is subtly different, and for example only has - to deal with a string of labels, and not a trailing packet. Also, the comparison - rules are different since we also have to take into account qname and qtype. - So just grin and bear it. - */ - - if(a.length() <= 12 || b.length() <= 12) - return a.length() < b.length(); - - uint8_t ourpos[64], rhspos[64]; - uint8_t ourcount=0, rhscount=0; - //cout<<"Asked to compare "<=(const unsigned char*)a.c_str() + a.size()) - return true; - - uint16_t aQtype = *(p+1)*256 + *(p+2); - uint16_t aQclass =*(p+3)*256 + *(p+4); - - for(p = (const unsigned char*)b.c_str()+12; p < (const unsigned char*)b.c_str() + b.size() && *p && rhscount < sizeof(rhspos); p+=*p+1) - rhspos[rhscount++]=(p-(const unsigned char*)b.c_str()); - - if(p>=(const unsigned char*)b.c_str() + b.size()) - return false; - - uint16_t bQtype = *(p+1)*256 + *(p+2); - uint16_t bQclass =*(p+3)*256 + *(p+4); - - if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) { - DNSName aname(a.c_str(), a.size(), 12, false, &aQtype, &aQclass); - DNSName bname(b.c_str(), b.size(), 12, false, &bQtype, &bQclass); - - if(aname.slowCanonCompare(bname)) - return true; - if(aname!=bname) - return false; - return boost::tie(aQtype, aQclass) < boost::tie(bQtype, bQclass); - } - for(;;) { - if(ourcount == 0 && rhscount != 0) - return true; - if(ourcount == 0 && rhscount == 0) - break; - if(ourcount !=0 && rhscount == 0) - return false; - ourcount--; - rhscount--; - - bool res=std::lexicographical_compare( - a.c_str() + ourpos[ourcount] + 1, - a.c_str() + ourpos[ourcount] + 1 + *(a.c_str() + ourpos[ourcount]), - b.c_str() + rhspos[rhscount] + 1, - b.c_str() + rhspos[rhscount] + 1 + *(b.c_str() + rhspos[rhscount]), - [](const char& a, const char& b) { - return dns2_tolower(a) < dns2_tolower(b); - }); - - // cout<<"Forward: "< d_tcpConnection; }; @@ -869,8 +871,7 @@ void startDoResolve(void *p) L<d_remote.toStringWithPort()<<" failed with: "<insertResponsePacket(string((const char*)&*packet.begin(), packet.size()), - (edo.d_Z & EDNSOpts::DNSSECOK), // ponder filtering on dnssecmode here + t_packetCache->insertResponsePacket(dc->d_tag, dc->d_mdp.d_qname, dc->d_mdp.d_qtype, dc->d_query, string((const char*)&*packet.begin(), packet.size()), g_now.tv_sec, min(minTTL, (pw.getHeader()->rcode == RCode::ServFail) ? SyncRes::s_packetcacheservfailttl : SyncRes::s_packetcachettl @@ -1135,6 +1136,7 @@ string* doProcessUDPQuestion(const std::string& question, const ComboAddress& fr string response; const struct dnsheader* dh = (struct dnsheader*)question.c_str(); + unsigned int ctag=0; try { uint32_t age; #ifdef MALLOC_TRACE @@ -1148,21 +1150,16 @@ string* doProcessUDPQuestion(const std::string& question, const ComboAddress& fr g_mtracer->clearAllocators(); */ #endif - bool needsDNSSEC=false; - - if(dh->arcount) { + if((*t_pdl)->d_gettag) { unsigned int consumed=0; - DNSName qname(question.c_str(), question.length(), sizeof(dnsheader), false, 0, 0, &consumed); - if(question.size() > (consumed+12+11) && ((question[consumed+12+11]&0x80)==0x80)) - needsDNSSEC=true; + uint16_t qtype=0; + DNSName qname(question.c_str(), question.length(), sizeof(dnsheader), false, &qtype, 0, &consumed); + ctag=(*t_pdl)->gettag(fromaddr, destaddr, qname, qtype); } - - if(!SyncRes::s_nopacketcache && t_packetCache->getResponsePacket(question, needsDNSSEC, g_now.tv_sec, &response, &age)) { - if(!g_quiet) - L<push_back("packetcached"); - + if(!SyncRes::s_nopacketcache && t_packetCache->getResponsePacket(ctag, question, g_now.tv_sec, &response, &age)) { + if(!g_quiet) + L<setSocket(fd); + dc->d_tag=ctag; + dc->d_query = question; dc->setRemote(&fromaddr); dc->setLocal(destaddr); dc->d_tcp=false; diff --git a/pdns/recpacketcache.cc b/pdns/recpacketcache.cc index 8926117f7..d4844ee5a 100644 --- a/pdns/recpacketcache.cc +++ b/pdns/recpacketcache.cc @@ -17,102 +17,132 @@ RecursorPacketCache::RecursorPacketCache() int RecursorPacketCache::doWipePacketCache(const DNSName& name, uint16_t qtype, bool subtree) { - vector packet; - DNSPacketWriter pw(packet, name, 0); - pw.getHeader()->rd=1; - Entry e; - e.d_packet.assign((const char*)&*packet.begin(), packet.size()); - e.d_wantsDNSSEC=false; - // so the idea is, we search for a packet with qtype=0, which is ahead of anything with that name - int count=0; - for(auto iter = d_packetCache.lower_bound(e); iter != d_packetCache.end(); ) { - const struct dnsheader* packet = reinterpret_cast((*iter).d_packet.c_str()); - if(packet->qdcount==0) - break; - uint16_t t; - - DNSName found(iter->d_packet.c_str(), iter->d_packet.size(), 12, false, &t); - // cout<<"At record "<(); + auto range = idx.equal_range(tie(tag,h)); + + if(range.first == range.second) { d_misses++; return false; } - if((uint32_t)now < iter->d_ttd) { // it is fresh! -// cerr<<"Fresh for another "<d_ttd - now<<" seconds!"<d_creation; - uint16_t id; - memcpy(&id, queryPacket.c_str(), 2); - *responsePacket = iter->d_packet; - responsePacket->replace(0, 2, (char*)&id, 2); + for(auto iter = range.first ; iter != range.second ; ++ iter) { + // the possibility is VERY real that we get hits that are not right - birthday paradox + if(!qrMatch(queryPacket, iter->d_packet)) + continue; + if((uint32_t)now < iter->d_ttd) { // it is right, it is fresh! + *age = now - iter->d_creation; + *responsePacket = iter->d_packet; + responsePacket->replace(0, 2, queryPacket.c_str(), 2); - string::size_type i=sizeof(dnsheader); - - for(;;) { - int labellen = (unsigned char)queryPacket[i]; - if(!labellen || i + labellen > responsePacket->size()) break; - i++; - responsePacket->replace(i, labellen, queryPacket, i, labellen); - i = i + labellen; - } - - d_hits++; - moveCacheItemToBack(d_packetCache, iter); + string::size_type i=sizeof(dnsheader); + + for(;;) { + int labellen = (unsigned char)queryPacket[i]; + if(!labellen || i + labellen > responsePacket->size()) break; + i++; + responsePacket->replace(i, labellen, queryPacket, i, labellen); + i = i + labellen; + } - return true; + d_hits++; + moveCacheItemToBack(d_packetCache, iter); + + return true; + } + else { + moveCacheItemToFront(d_packetCache, iter); + d_misses++; + break; + } } - moveCacheItemToFront(d_packetCache, iter); - d_misses++; + return false; } -void RecursorPacketCache::insertResponsePacket(const std::string& responsePacket, bool wantsDNSSEC, time_t now, uint32_t ttl) + +void RecursorPacketCache::insertResponsePacket(unsigned int tag, const DNSName& qname, uint16_t qtype, const std::string& queryPacket, const std::string& responsePacket, time_t now, uint32_t ttl) { - struct Entry e; - e.d_packet = responsePacket; - e.d_wantsDNSSEC = wantsDNSSEC; - e.d_ttd = now+ttl; - e.d_creation = now; - packetCache_t::iterator iter = d_packetCache.find(e); - - if(iter != d_packetCache.end()) { + auto qhash = canHashPacket(queryPacket); + auto& idx = d_packetCache.get(); + auto range = idx.equal_range(tie(tag,qhash)); + auto iter = range.first; + + for( ; iter != range.second ; ++iter) { + if(iter->d_type != qtype) + continue; + // this only happens on insert which is relatively rare and does not need to be super fast + DNSName respname(iter->d_packet.c_str(), iter->d_packet.length(), sizeof(dnsheader), false, 0, 0, 0); + if(qname != respname) + continue; iter->d_packet = responsePacket; iter->d_ttd = now + ttl; iter->d_creation = now; + break; } - else + + if(iter == range.second) { // nothing to refresh + struct Entry e; + e.d_packet = responsePacket; + e.d_name = qname; + e.d_qhash = qhash; + e.d_type = qtype; + e.d_ttd = now+ttl; + e.d_creation = now; + e.d_tag = tag; d_packetCache.insert(e); + } } uint64_t RecursorPacketCache::size() @@ -129,7 +159,6 @@ uint64_t RecursorPacketCache::bytes() return sum; } - void RecursorPacketCache::doPruneTo(unsigned int maxCached) { pruneCollection(d_packetCache, maxCached); diff --git a/pdns/recpacketcache.hh b/pdns/recpacketcache.hh index cc0cb96f8..0d6c1fb34 100644 --- a/pdns/recpacketcache.hh +++ b/pdns/recpacketcache.hh @@ -8,6 +8,7 @@ #include #include #include +#include #include #include @@ -23,8 +24,8 @@ class RecursorPacketCache { public: RecursorPacketCache(); - bool getResponsePacket(const std::string& queryPacket, bool wantsDNSSEC, time_t now, std::string* responsePacket, uint32_t* age); - void insertResponsePacket(const std::string& responsePacket, bool wantsDNSSEC, time_t now, uint32_t ttd); + bool getResponsePacket(unsigned int tag, const std::string& queryPacket, time_t now, std::string* responsePacket, uint32_t* age); + void insertResponsePacket(unsigned int tag, const DNSName& qname, uint16_t qtype, const std::string& queryPacket, const std::string& responsePacket, time_t now, uint32_t ttd); void doPruneTo(unsigned int maxSize=250000); int doWipePacketCache(const DNSName& name, uint16_t qtype=0xffff, bool subtree=false); @@ -34,13 +35,17 @@ public: uint64_t bytes(); private: - + struct HashTag {}; + struct NameTag {}; struct Entry { mutable uint32_t d_ttd; - mutable uint32_t d_creation; + mutable uint32_t d_creation; // so we can 'age' our packets + DNSName d_name; + uint16_t d_type; mutable std::string d_packet; // "I know what I am doing" - bool d_wantsDNSSEC; + uint32_t d_qhash; + uint32_t d_tag; inline bool operator<(const struct Entry& rhs) const; uint32_t getTTD() const @@ -48,35 +53,17 @@ private: return d_ttd; } }; - + uint32_t canHashPacket(const std::string& origPacket); typedef multi_index_container< Entry, indexed_by < - ordered_unique >, - sequenced<> - > + hashed_non_unique, composite_key, member > >, + sequenced<> , + ordered_non_unique, member, CanonDNSNameCompare > + > > packetCache_t; - packetCache_t d_packetCache; + packetCache_t d_packetCache; }; -// needs to take into account: qname, qtype, opcode, rd, qdcount, EDNS size -inline bool RecursorPacketCache::Entry::operator<(const struct RecursorPacketCache::Entry &rhs) const -{ - const struct dnsheader* - dh=(const struct dnsheader*) d_packet.c_str(), - *rhsdh=(const struct dnsheader*)rhs.d_packet.c_str(); - if(std::tie(d_wantsDNSSEC, dh->opcode, dh->rd, dh->qdcount) < - std::tie(rhs.d_wantsDNSSEC, rhsdh->opcode, rhsdh->rd, rhsdh->qdcount)) - return true; - - if(std::tie(d_wantsDNSSEC, dh->opcode, dh->rd, dh->qdcount) > - std::tie(rhs.d_wantsDNSSEC, rhsdh->opcode, rhsdh->rd, rhsdh->qdcount)) - return false; - - return dnspacketLessThan(d_packet, rhs.d_packet); -} - - - #endif diff --git a/pdns/test-recpacketcache_cc.cc b/pdns/test-recpacketcache_cc.cc new file mode 100644 index 000000000..8d723253b --- /dev/null +++ b/pdns/test-recpacketcache_cc.cc @@ -0,0 +1,70 @@ +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_NO_MAIN + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#include +#include "dnswriter.hh" +#include "dnsrecords.hh" +#include "dns_random.hh" +#include "iputils.hh" +#include "recpacketcache.hh" +#include + + +BOOST_AUTO_TEST_SUITE(recpacketcache_cc) + +BOOST_AUTO_TEST_CASE(test_recPacketCacheSimple) { + RecursorPacketCache rpc; + BOOST_CHECK_EQUAL(rpc.size(), 0); + + DNSName qname("www.powerdns.com"); + vector packet; + DNSPacketWriter pw(packet, qname, QType::A); + pw.getHeader()->rd=true; + pw.getHeader()->qr=false; + pw.getHeader()->id=random(); + string qpacket((const char*)&packet[0], packet.size()); + pw.startRecord(qname, QType::A, 3600); + + ARecordContent ar("127.0.0.1"); + ar.toPacket(pw); + pw.commit(); + string rpacket((const char*)&packet[0], packet.size()); + + rpc.insertResponsePacket(0,qname, QType::A, qpacket, rpacket, time(0), 3600); + BOOST_CHECK_EQUAL(rpc.size(), 1); + rpc.doPruneTo(0); + BOOST_CHECK_EQUAL(rpc.size(), 0); + rpc.insertResponsePacket(0,qname, QType::A, qpacket, rpacket, time(0), 3600); + BOOST_CHECK_EQUAL(rpc.size(), 1); + rpc.doWipePacketCache(qname); + BOOST_CHECK_EQUAL(rpc.size(), 0); + + rpc.insertResponsePacket(0,qname, QType::A, qpacket, rpacket, time(0), 3600); + uint32_t age=0; + string fpacket; + bool found = rpc.getResponsePacket(0, qpacket, time(0), &fpacket, &age); + BOOST_CHECK_EQUAL(found, 1); + BOOST_CHECK_EQUAL(fpacket, rpacket); + + packet.clear(); + qname+=DNSName("co.uk"); + DNSPacketWriter pw2(packet, qname, QType::A); + + pw2.getHeader()->rd=true; + pw2.getHeader()->qr=false; + pw2.getHeader()->id=random(); + qpacket.assign((const char*)&packet[0], packet.size()); + found = rpc.getResponsePacket(0, qpacket, time(0), &fpacket, &age); + BOOST_CHECK_EQUAL(found, 0); + + rpc.doWipePacketCache(DNSName("com"), 0xffff, true); + BOOST_CHECK_EQUAL(rpc.size(), 0); + + + +} + +BOOST_AUTO_TEST_SUITE_END() -- 2.40.0