From d4fb9752baa5582e61474da4ad82da2022a2211b Mon Sep 17 00:00:00 2001
From: Kees Monshouwer <mind04@monshouwer.org>
Date: Mon, 9 Jun 2014 20:26:13 +0200
Subject: [PATCH] switch from reversed zones to labelReversed in lmdb-backend

---
 modules/lmdbbackend/lmdbbackend.cc |  43 +++++-------
 pdns/dnsbackend.cc                 | 103 +++--------------------------
 pdns/zone2lmdb.cc                  |   2 +-
 3 files changed, 28 insertions(+), 120 deletions(-)

diff --git a/modules/lmdbbackend/lmdbbackend.cc b/modules/lmdbbackend/lmdbbackend.cc
index 080d747dc..37a2f6977 100644
--- a/modules/lmdbbackend/lmdbbackend.cc
+++ b/modules/lmdbbackend/lmdbbackend.cc
@@ -133,7 +133,7 @@ bool LMDBBackend::getDomainMetadata(const string& name, const std::string& kind,
     string key_str, cur_value;
     vector<string> valparts;
 
-    key_str=d_querykey = string( name.rbegin(), name.rend() );
+    key_str=bitFlip(labelReverse(toLower(name)))+"\xff";
     key.mv_data = (char *)key_str.c_str();
     key.mv_size = key_str.length();
 
@@ -268,16 +268,15 @@ bool LMDBBackend::getDirectRRSIGs(const string &signer, const string &qname, con
   return true;
 }
 
-// Get the zone name and value of the requested zone (reversed) OR the entry
-// just before where it should have been
+// Get the zone name of the requested zone (labelReversed) OR the name of the closest parrent zone
 bool LMDBBackend::getAuthZone( string &rev_zone )
 {
     MDB_val key, data;
     // XXX can do this just using char *
 
-    string orig = rev_zone;
-    key.mv_data = (char *)rev_zone.c_str();
-    key.mv_size = rev_zone.length();
+    string key_str=bitFlip(rev_zone+" ");
+    key.mv_data = (char *)key_str.c_str();
+    key.mv_size = key_str.length();
 
     // Release our transaction and cursors in order to get latest data
     mdb_txn_reset( txn );
@@ -290,29 +289,23 @@ bool LMDBBackend::getAuthZone( string &rev_zone )
       mdb_cursor_renew( txn, nsecx_cursor );
     }
 
-    // Find the nearest record, or the last record if none
-    if( mdb_cursor_get(zone_cursor, &key, &data, MDB_SET_RANGE) )
-        mdb_cursor_get(zone_cursor, &key, &data, MDB_LAST);
-
-    rev_zone.assign( (const char *)key.mv_data, key.mv_size );
-
-    /* Only skip this bit if we got an exact hit on the SOA or if the key is a shoter
-     * version of rev_zone. Otherwise we have to go back to the previous record */
-    if( orig.compare( rev_zone ) != 0 ) { // FIXME detect shorter version
-        /* Skip back 1 entry to what should be a substring of what was searched
-         * for (or a totally different entry) */
-        if( mdb_cursor_get(zone_cursor, &key, &data, MDB_PREV) ) {
-            // At beginning of database; therefore didn't actually hit the
-            // record. Return false
-            return false;
-        }
+    // Find the best record
+    if( mdb_cursor_get( zone_cursor, &key, &data, MDB_SET_RANGE ) == 0 && key.mv_size <= key_str.length() ) {
+      // Found a shorter match. Now look if the zones are equal up to key-length-1. If they are check
+      // if position key-length in key_str is a label separator. If all this is true we have a match.
+      if( key_str.compare( 0, key.mv_size-1, (const char *) key.mv_data, key.mv_size-1  ) == 0 && key.mv_size && key_str[key.mv_size-1] == ~' ') {
+        rev_zone.resize( key.mv_size-1 );
+
+        DEBUGLOG("Auth key: " << rev_zone <<endl);
 
-        rev_zone.assign( (const char *)key.mv_data, key.mv_size );
+        return true;
+      }
     }
 
-    DEBUGLOG("Auth key: " << rev_zone <<endl);
+    //reset the cursor the data in it is invallid
+    mdb_cursor_renew( txn, zone_cursor );
 
-    return true;
+    return false;
 }
 
 bool LMDBBackend::getAuthData( SOAData &soa, DNSPacket *p )
diff --git a/pdns/dnsbackend.cc b/pdns/dnsbackend.cc
index 765b250c4..e022edcdf 100644
--- a/pdns/dnsbackend.cc
+++ b/pdns/dnsbackend.cc
@@ -337,48 +337,6 @@ bool DNSBackend::calculateSOASerial(const string& domain, const SOAData& sd, tim
     return true;
 }
 
-/* String a is the query key, string b is the result from the database. Trys to
- * be intelegent and only return matching sections (ie up to the last point at
- * which there were .'s in both strings, however because the - character is
- * legal and < . in ascii it does not guarantee to return a section point.
- */
-inline unsigned int compare_domains( const string &a, const string &b ) {
-    int aLen = a.length(), bLen = b.length(), n = 0, last_dot = 0;
-    const unsigned char *aPtr = (const unsigned char*)a.c_str(),
-            *bPtr = (const unsigned char*)b.c_str();
-
-    while( 1 ) {
-        if( n == aLen ) {
-            if( n == bLen || bPtr[n] <= '.' )
-                return n;
-            else
-                return last_dot;
-        }
-
-        if( n == bLen ) {
-            if( n == aLen || aPtr[n] <= '.' )
-                return n;
-            else
-                return last_dot;
-        }
-
-        if( aPtr[n] != bPtr[n] ) {
-            if( aPtr[n] <= '.' && bPtr[n] <= '.' )
-                return n;
-            else
-                return last_dot;
-        }
-
-        if( aPtr[n] == '.' )        // Therefore bPtr[n] == '.' as from above they are the same
-            last_dot = n;
-
-        n++;
-    }
-
-    // Should never get here
-    return 0;
-}
-
 /* This is a subclass of DNSBackend that, assuming you have your zones reversed
  * and stored in an ordered fashion, will be able to look up SOA's much quicker
  * than the DNSBackend code. The normal case for a SOA that exists is 1 backend
@@ -405,6 +363,11 @@ enum {
 #undef PC
 extern PacketCache PC;
 
+#if 0
+#undef DLOG
+#define DLOG(x) x
+#endif
+
 bool _add_to_negcache( const string &zone ) {
     static int negqueryttl=::arg().asNum("negquery-cache-ttl");
     // add the zone to the negative query cache and return false
@@ -447,63 +410,15 @@ inline int DNSReversedBackend::_getAuth(DNSPacket *p, SOAData *soa, const string
     if( !getAuthZone( foundkey ) )
         return GET_AUTH_NEG_CACHE;
 
-    unsigned int diff_point = compare_domains( querykey, foundkey );
-    DLOG(L<<Logger::Error<<"Queried: " << querykey << " and found record: " <<foundkey << " : diff point is: " << diff_point<<endl);
+    DLOG(L<<Logger::Error<<"Queried: " << querykey << " and found record: " <<foundkey<<endl);
 
     // Got a match from a previous backend that was longer than this - no need
     // to continue.
-    if( best_match_len && best_match_len >= (int)diff_point ) {
+    if( best_match_len && best_match_len >= (int) foundkey.length() ) {
         DLOG(L<<Logger::Error<<"Best match was better from a different client"<<endl);
         return GET_AUTH_NEG_DONTCACHE;
     }
 
-    // If diff_point is 0 then either strings are totally different OR root
-    // zone was returned.
-    if( diff_point == 0 && foundkey.length() != 0 )
-        return GET_AUTH_NEG_CACHE;
-
-    /* If the strings are the same (ie diff_point == querykey.length()) then we
-     * have found the exact record.
-     *
-     * If the strings are the same up to the end of the key we pulled from the
-     * database, then we have found the true SOA for this zone. (the string we
-     * pulled from the database could be longer than the key we searched for,
-     * but if that is the case then it cannot be a sub-key because of the
-     * reliance to get the key at the requested position OR before)
-     *
-     * Otherwise, the strings are different up to a certain point. In this
-     * case, we need to retry the query as we may have the case of a subdomain
-     * in the database eg a.b.com and b.com SOA records. If we then query for
-     * www.b.com we will hit the a.b.com SOA record so we want to trim back to
-     * the . before the difference and retry the query (ie b.com). Note that
-     * because some legal dns characters come *before* the . in ascii if we try
-     * searching for www.a.com our db query may return www-a.com in which case
-     * we retry the search from the point at which the strings differ (ie
-     * a.com)
-     *
-     * To speed up future decisions for subdomains, if the negative cache is
-     * available we will make a note there if the subdomain we queried for does
-     * not exist.
-     */
-    if( diff_point != querykey.length()
-            && diff_point != foundkey.length() ) {
-        // XXX If we found some way of getting the exact domain without having
-        // to try this (ie walk the database btree up until the point where it
-        // differs), we could have a 60% performance improvement in some
-        // situations.
-
-        string shortzone = inZone.substr( inZone.length() - diff_point, string::npos );
-        string shortquerykey = querykey.substr( 0, diff_point );
-        DLOG(L<<Logger::Error<<"Retrying for " << shortzone << " querykey: " << shortquerykey<<endl);
-
-        int ret = _getAuth( p, soa, shortzone, zoneId, shortquerykey, best_match_len );
-
-        if( ret == GET_AUTH_NEG_CACHE )
-            _add_to_negcache( shortzone );
-
-        return ret;
-    }
-
     // Found record successfully now, fill in the data.
     if( getAuthData( *soa, p ) ) {
         /* all the keys are reversed. rather than reversing them again it is
@@ -523,7 +438,7 @@ inline int DNSReversedBackend::_getAuth(DNSPacket *p, SOAData *soa, const string
 bool DNSReversedBackend::getAuth(DNSPacket *p, SOAData *soa, const string &inZone, int *zoneId, const int best_match_len) {
     // Reverse the lowercased query string
     string zone = toLower(inZone);
-    string querykey( zone.rbegin(), zone.rend() );
+    string querykey = labelReverse(zone);
 
     int ret = _getAuth( p, soa, inZone, zoneId, querykey, best_match_len );
 
@@ -559,7 +474,7 @@ bool DNSReversedBackend::getSOA(const string &inZone, SOAData &soa, DNSPacket *p
 {
     // prepare the query string
     string zone = toLower( inZone );
-    string querykey( zone.rbegin(), zone.rend() );
+    string querykey = labelReverse( zone );
 
     if( !_getSOA( querykey, soa, p ) )
         return false;
diff --git a/pdns/zone2lmdb.cc b/pdns/zone2lmdb.cc
index f62ee8f57..5693fbae1 100644
--- a/pdns/zone2lmdb.cc
+++ b/pdns/zone2lmdb.cc
@@ -164,7 +164,7 @@ void emitData(string zone, ZoneParserTNG &zpt){
       mdb_put(txn_zone, data_db, &key, &data, 0);
   }
   if (hasSOA) {
-    string keyStr=(reverse(stripDot(zone)));
+    string keyStr=bitFlip(labelReverse(zone))+"\xff";
     string dataStr=itoa(g_numZones+1)+"\t"+itoa(sd.ttl)+"\t"+serializeSOAData(sd);
 
     if (isPresigned)
-- 
2.40.0