pdns/recursordist/aggressive_nsec.cc

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of version 2 of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * In addition, for the avoidance of any doubt, permission is granted to
  10  * link this program with OpenSSL and to (re)distribute the binaries
  11  * produced as the result of such linking.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22 #include <cinttypes>
  23 #include <climits>
  24
  25 #include "aggressive_nsec.hh"
  26 #include "cachecleaner.hh"
  27 #include "recursor_cache.hh"
  28 #include "logger.hh"
  29 #include "validate.hh"
  30
  31 std::unique_ptr<AggressiveNSECCache> g_aggressiveNSECCache{nullptr};
  32 uint64_t AggressiveNSECCache::s_nsec3DenialProofMaxCost{0};
  33 uint8_t AggressiveNSECCache::s_maxNSEC3CommonPrefix = AggressiveNSECCache::s_default_maxNSEC3CommonPrefix;
  34
  35 /* this is defined in syncres.hh and we are not importing that here */
  36 extern std::unique_ptr<MemRecursorCache> g_recCache;
  37
  38 std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>> AggressiveNSECCache::getBestZone(const DNSName& zone)
  39 {
  40   std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>> entry{nullptr};
  41   {
  42     auto zones = d_zones.try_read_lock();
  43     if (!zones.owns_lock()) {
  44       return entry;
  45     }
  46
  47     auto got = zones->lookup(zone);
  48     if (got) {
  49       return *got;
  50     }
  51   }
  52   return entry;
  53 }
  54
  55 std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>> AggressiveNSECCache::getZone(const DNSName& zone)
  56 {
  57   {
  58     auto zones = d_zones.read_lock();
  59     auto got = zones->lookup(zone);
  60     if (got && *got) {
  61       auto locked = (*got)->lock();
  62       if (locked->d_zone == zone) {
  63         return *got;
  64       }
  65     }
  66   }
  67
  68   auto entry = std::make_shared<LockGuarded<ZoneEntry>>(zone);
  69
  70   {
  71     auto zones = d_zones.write_lock();
  72     /* it might have been inserted in the mean time */
  73     auto got = zones->lookup(zone);
  74     if (got && *got) {
  75       auto locked = (*got)->lock();
  76       if (locked->d_zone == zone) {
  77         return *got;
  78       }
  79     }
  80     zones->add(zone, std::shared_ptr<LockGuarded<ZoneEntry>>(entry));
  81     return entry;
  82   }
  83 }
  84
  85 void AggressiveNSECCache::updateEntriesCount(SuffixMatchTree<std::shared_ptr<LockGuarded<ZoneEntry>>>& zones)
  86 {
  87   uint64_t counter = 0;
  88   zones.visit([&counter](const SuffixMatchTree<std::shared_ptr<LockGuarded<ZoneEntry>>>& node) {
  89     if (node.d_value) {
  90       counter += node.d_value->lock()->d_entries.size();
  91     }
  92   });
  93   d_entriesCount = counter;
  94 }
  95
  96 void AggressiveNSECCache::removeZoneInfo(const DNSName& zone, bool subzones)
  97 {
  98   auto zones = d_zones.write_lock();
  99
 100   if (subzones) {
 101     zones->remove(zone, true);
 102     updateEntriesCount(*zones);
 103   }
 104   else {
 105     auto got = zones->lookup(zone);
 106     if (!got || !*got) {
 107       return;
 108     }
 109
 110     /* let's increase the ref count of the shared pointer
 111        so we get the lock, remove the zone from the tree,
 112        then release the lock before the entry is deleted */
 113     auto entry = *got;
 114     {
 115       auto locked = (*got)->lock();
 116       if (locked->d_zone != zone) {
 117         return;
 118       }
 119       auto removed = locked->d_entries.size();
 120       zones->remove(zone, false);
 121       d_entriesCount -= removed;
 122     }
 123   }
 124 }
 125
 126 void AggressiveNSECCache::prune(time_t now)
 127 {
 128   uint64_t maxNumberOfEntries = d_maxEntries;
 129   std::vector<DNSName> emptyEntries;
 130   uint64_t erased = 0;
 131
 132   auto zones = d_zones.write_lock();
 133   // To start, just look through 10% of each zone and nuke everything that is expired
 134   zones->visit([now, &erased, &emptyEntries](const SuffixMatchTree<std::shared_ptr<LockGuarded<ZoneEntry>>>& node) {
 135     if (!node.d_value) {
 136       return;
 137     }
 138
 139     auto zoneEntry = node.d_value->lock();
 140     auto& sidx = boost::multi_index::get<ZoneEntry::SequencedTag>(zoneEntry->d_entries);
 141     const auto toLookAtForThisZone = (zoneEntry->d_entries.size() + 9) / 10;
 142     uint64_t lookedAt = 0;
 143     for (auto it = sidx.begin(); it != sidx.end() && lookedAt < toLookAtForThisZone; ++lookedAt) {
 144       if (it->d_ttd <= now) {
 145         it = sidx.erase(it);
 146         ++erased;
 147       }
 148       else {
 149         ++it;
 150       }
 151     }
 152
 153     if (zoneEntry->d_entries.empty()) {
 154       emptyEntries.push_back(zoneEntry->d_zone);
 155     }
 156   });
 157
 158   d_entriesCount -= erased;
 159
 160   // If we are still above try harder by nuking entries from each zone in LRU order
 161   auto entriesCount = d_entriesCount.load();
 162   if (entriesCount > maxNumberOfEntries) {
 163     erased = 0;
 164     uint64_t toErase = entriesCount - maxNumberOfEntries;
 165     zones->visit([&erased, &toErase, &entriesCount, &emptyEntries](const SuffixMatchTree<std::shared_ptr<LockGuarded<ZoneEntry>>>& node) {
 166       if (!node.d_value || entriesCount == 0) {
 167         return;
 168       }
 169       auto zoneEntry = node.d_value->lock();
 170       const auto zoneSize = zoneEntry->d_entries.size();
 171       auto& sidx = boost::multi_index::get<ZoneEntry::SequencedTag>(zoneEntry->d_entries);
 172       const auto toTrimForThisZone = static_cast<uint64_t>(std::round(static_cast<double>(toErase) * static_cast<double>(zoneSize) / static_cast<double>(entriesCount)));
 173       if (entriesCount < zoneSize) {
 174         throw std::runtime_error("Inconsistent agggressive cache " + std::to_string(entriesCount) + " " + std::to_string(zoneSize));
 175       }
 176       // This is comparable to what cachecleaner.hh::pruneMutexCollectionsVector() is doing, look there for an explanation
 177       entriesCount -= zoneSize;
 178       uint64_t trimmedFromThisZone = 0;
 179       for (auto it = sidx.begin(); it != sidx.end() && trimmedFromThisZone < toTrimForThisZone;) {
 180         it = sidx.erase(it);
 181         ++erased;
 182         ++trimmedFromThisZone;
 183         if (--toErase == 0) {
 184           break;
 185         }
 186       }
 187       if (zoneEntry->d_entries.empty()) {
 188         emptyEntries.push_back(zoneEntry->d_zone);
 189       }
 190     });
 191
 192     d_entriesCount -= erased;
 193   }
 194
 195   if (!emptyEntries.empty()) {
 196     for (const auto& entry : emptyEntries) {
 197       zones->remove(entry);
 198     }
 199   }
 200 }
 201
 202 static bool isMinimallyCoveringNSEC(const DNSName& owner, const std::shared_ptr<const NSECRecordContent>& nsec)
 203 {
 204   /* this test only covers Cloudflare's ones (https://blog.cloudflare.com/black-lies/),
 205      we might need to cover more cases described in rfc4470 as well, but the name generation algorithm
 206      is not clearly defined there */
 207   const auto& storage = owner.getStorage();
 208   const auto& nextStorage = nsec->d_next.getStorage();
 209
 210   // is the next name at least two octets long?
 211   if (nextStorage.size() <= 2 || storage.size() != (nextStorage.size() - 2)) {
 212     return false;
 213   }
 214
 215   // does the next name start with a one-octet long label containing a zero, i.e. `\000`?
 216   if (nextStorage.at(0) != 1 || static_cast<uint8_t>(nextStorage.at(1)) != static_cast<uint8_t>(0)) {
 217     return false;
 218   }
 219
 220   // is the rest of the next name identical to the owner name, i.e. is the next name the owner name prefixed by '\000.'?
 221   if (nextStorage.compare(2, nextStorage.size() - 2, storage) != 0) {
 222     return false;
 223   }
 224
 225   return true;
 226 }
 227
 228 static bool commonPrefixIsLong(const string& one, const string& two, size_t bound)
 229 {
 230   size_t length = 0;
 231   const auto minLength = std::min(one.length(), two.length());
 232
 233   for (size_t i = 0; i < minLength; i++) {
 234     const auto byte1 = one.at(i);
 235     const auto byte2 = two.at(i);
 236     // shortcut
 237     if (byte1 == byte2) {
 238       length += CHAR_BIT;
 239       if (length > bound) {
 240         return true;
 241       }
 242       continue;
 243     }
 244     // bytes differ, let's look at the bits
 245     for (ssize_t j = CHAR_BIT - 1; j >= 0; j--) {
 246       const auto bit1 = byte1 & (1 << j);
 247       const auto bit2 = byte2 & (1 << j);
 248       if (bit1 != bit2) {
 249         return length > bound;
 250       }
 251       length++;
 252       if (length > bound) {
 253         return true;
 254       }
 255     }
 256   }
 257   return length > bound;
 258 }
 259
 260 // If the NSEC3 hashes have a long common prefix, they deny only a small subset of all possible hashes
 261 // So don't take the trouble to store those.
 262 bool AggressiveNSECCache::isSmallCoveringNSEC3(const DNSName& owner, const std::string& nextHash)
 263 {
 264   std::string ownerHash(fromBase32Hex(owner.getRawLabel(0)));
 265   // Special case: empty zone, so the single NSEC3 covers everything. Prefix is long but we still want it cached.
 266   if (ownerHash == nextHash) {
 267     return false;
 268   }
 269   return commonPrefixIsLong(ownerHash, nextHash, AggressiveNSECCache::s_maxNSEC3CommonPrefix);
 270 }
 271
 272 void AggressiveNSECCache::insertNSEC(const DNSName& zone, const DNSName& owner, const DNSRecord& record, const std::vector<std::shared_ptr<const RRSIGRecordContent>>& signatures, bool nsec3)
 273 {
 274   if (nsec3 && nsec3Disabled()) {
 275     return;
 276   }
 277   if (signatures.empty()) {
 278     return;
 279   }
 280
 281   std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>> entry = getZone(zone);
 282   {
 283     auto zoneEntry = entry->lock();
 284     if (nsec3 && !zoneEntry->d_nsec3) {
 285       d_entriesCount -= zoneEntry->d_entries.size();
 286       zoneEntry->d_entries.clear();
 287       zoneEntry->d_nsec3 = true;
 288     }
 289
 290     DNSName next;
 291     if (!nsec3) {
 292       auto content = getRR<NSECRecordContent>(record);
 293       if (!content) {
 294         throw std::runtime_error("Error getting the content from a NSEC record");
 295       }
 296
 297       next = content->d_next;
 298       if (next.canonCompare(owner) && next != zone) {
 299         /* not accepting a NSEC whose next domain name is before the owner
 300            unless the next domain name is the apex, sorry */
 301         return;
 302       }
 303
 304       if (isMinimallyCoveringNSEC(owner, content)) {
 305         /* not accepting minimally covering answers since they only deny one name */
 306         return;
 307       }
 308     }
 309     else {
 310       auto content = getRR<NSEC3RecordContent>(record);
 311       if (!content) {
 312         throw std::runtime_error("Error getting the content from a NSEC3 record");
 313       }
 314
 315       if (content->isOptOut()) {
 316         /* doesn't prove anything, sorry */
 317         return;
 318       }
 319
 320       if (g_maxNSEC3Iterations && content->d_iterations > g_maxNSEC3Iterations) {
 321         /* can't use that */
 322         return;
 323       }
 324
 325       if (isSmallCoveringNSEC3(owner, content->d_nexthash)) {
 326         /* not accepting small covering answers since they only deny a small subset */
 327         return;
 328       }
 329
 330       // XXX: Ponder storing everything in raw form, without the zone instead. It still needs to be a DNSName for NSEC, though,
 331       // but doing the conversion on cache hits only might be faster
 332       next = DNSName(toBase32Hex(content->d_nexthash)) + zone;
 333
 334       if (zoneEntry->d_iterations != content->d_iterations || zoneEntry->d_salt != content->d_salt) {
 335         zoneEntry->d_iterations = content->d_iterations;
 336         zoneEntry->d_salt = content->d_salt;
 337
 338         // Clearing the existing entries since we can't use them, and it's likely a rollover
 339         // If it instead is different servers using different parameters, well, too bad.
 340         d_entriesCount -= zoneEntry->d_entries.size();
 341         zoneEntry->d_entries.clear();
 342       }
 343     }
 344
 345     /* the TTL is already a TTD by now */
 346     if (!nsec3 && isWildcardExpanded(owner.countLabels(), *signatures.at(0))) {
 347       DNSName realOwner = getNSECOwnerName(owner, signatures);
 348       auto pair = zoneEntry->d_entries.insert({record.getContent(), signatures, realOwner, next, record.d_ttl});
 349       if (pair.second) {
 350         ++d_entriesCount;
 351       }
 352       else {
 353         zoneEntry->d_entries.replace(pair.first, {record.getContent(), signatures, std::move(realOwner), next, record.d_ttl});
 354       }
 355     }
 356     else {
 357       auto pair = zoneEntry->d_entries.insert({record.getContent(), signatures, owner, next, record.d_ttl});
 358       if (pair.second) {
 359         ++d_entriesCount;
 360       }
 361       else {
 362         zoneEntry->d_entries.replace(pair.first, {record.getContent(), signatures, owner, std::move(next), record.d_ttl});
 363       }
 364     }
 365   }
 366 }
 367
 368 bool AggressiveNSECCache::getNSECBefore(time_t now, std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>>& zone, const DNSName& name, ZoneEntry::CacheEntry& entry)
 369 {
 370   auto zoneEntry = zone->try_lock();
 371   if (!zoneEntry.owns_lock() || zoneEntry->d_entries.empty()) {
 372     return false;
 373   }
 374
 375   auto& idx = zoneEntry->d_entries.get<ZoneEntry::OrderedTag>();
 376   auto it = idx.lower_bound(name);
 377   bool end = false;
 378   bool wrapped = false;
 379
 380   if (it == idx.begin() && it->d_owner != name) {
 381     it = idx.end();
 382     // we know the map is not empty
 383     it--;
 384     // might be that owner > name && name < next
 385     // can't go further, but perhaps we wrapped?
 386     wrapped = true;
 387   }
 388
 389   while (!end && !wrapped && (it == idx.end() || (it->d_owner != name && !it->d_owner.canonCompare(name)))) {
 390     if (it == idx.begin()) {
 391       end = true;
 392       break;
 393     }
 394     else {
 395       it--;
 396     }
 397   }
 398
 399   if (end) {
 400     return false;
 401   }
 402
 403   auto firstIndexIterator = zoneEntry->d_entries.project<ZoneEntry::OrderedTag>(it);
 404   if (it->d_ttd <= now) {
 405     moveCacheItemToFront<ZoneEntry::SequencedTag>(zoneEntry->d_entries, firstIndexIterator);
 406     return false;
 407   }
 408
 409   entry = *it;
 410   moveCacheItemToBack<ZoneEntry::SequencedTag>(zoneEntry->d_entries, firstIndexIterator);
 411   return true;
 412 }
 413
 414 bool AggressiveNSECCache::getNSEC3(time_t now, std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>>& zone, const DNSName& name, ZoneEntry::CacheEntry& entry)
 415 {
 416   auto zoneEntry = zone->try_lock();
 417   if (!zoneEntry.owns_lock() || zoneEntry->d_entries.empty()) {
 418     return false;
 419   }
 420
 421   auto& idx = zoneEntry->d_entries.get<ZoneEntry::HashedTag>();
 422   auto entries = idx.equal_range(name);
 423
 424   for (auto it = entries.first; it != entries.second; ++it) {
 425
 426     if (it->d_owner != name) {
 427       continue;
 428     }
 429
 430     auto firstIndexIterator = zoneEntry->d_entries.project<ZoneEntry::OrderedTag>(it);
 431     if (it->d_ttd <= now) {
 432       moveCacheItemToFront<ZoneEntry::SequencedTag>(zoneEntry->d_entries, firstIndexIterator);
 433       return false;
 434     }
 435
 436     entry = *it;
 437     moveCacheItemToBack<ZoneEntry::SequencedTag>(zoneEntry->d_entries, firstIndexIterator);
 438     return true;
 439   }
 440
 441   return false;
 442 }
 443
 444 static void addToRRSet(const time_t now, std::vector<DNSRecord>& recordSet, std::vector<std::shared_ptr<const RRSIGRecordContent>> signatures, const DNSName& owner, bool doDNSSEC, std::vector<DNSRecord>& ret, DNSResourceRecord::Place place = DNSResourceRecord::AUTHORITY)
 445 {
 446   uint32_t ttl = 0;
 447
 448   for (auto& record : recordSet) {
 449     if (record.d_class != QClass::IN) {
 450       continue;
 451     }
 452
 453     record.d_ttl -= now;
 454     record.d_name = owner;
 455     ttl = record.d_ttl;
 456     record.d_place = place;
 457     ret.push_back(std::move(record));
 458   }
 459
 460   if (doDNSSEC) {
 461     for (auto& signature : signatures) {
 462       DNSRecord dr;
 463       dr.d_type = QType::RRSIG;
 464       dr.d_name = owner;
 465       dr.d_ttl = ttl;
 466       dr.setContent(std::move(signature));
 467       dr.d_place = place;
 468       dr.d_class = QClass::IN;
 469       ret.push_back(std::move(dr));
 470     }
 471   }
 472 }
 473
 474 static void addRecordToRRSet(const DNSName& owner, const QType& type, uint32_t ttl, std::shared_ptr<const DNSRecordContent>& content, std::vector<std::shared_ptr<const RRSIGRecordContent>> signatures, bool doDNSSEC, std::vector<DNSRecord>& ret)
 475 {
 476   DNSRecord nsecRec;
 477   nsecRec.d_type = type.getCode();
 478   nsecRec.d_name = owner;
 479   nsecRec.d_ttl = ttl;
 480   nsecRec.setContent(std::move(content));
 481   nsecRec.d_place = DNSResourceRecord::AUTHORITY;
 482   nsecRec.d_class = QClass::IN;
 483   ret.push_back(std::move(nsecRec));
 484
 485   if (doDNSSEC) {
 486     for (auto& signature : signatures) {
 487       DNSRecord dr;
 488       dr.d_type = QType::RRSIG;
 489       dr.d_name = owner;
 490       dr.d_ttl = ttl;
 491       dr.setContent(std::move(signature));
 492       dr.d_place = DNSResourceRecord::AUTHORITY;
 493       dr.d_class = QClass::IN;
 494       ret.push_back(std::move(dr));
 495     }
 496   }
 497 }
 498
 499 bool AggressiveNSECCache::synthesizeFromNSEC3Wildcard(time_t now, const DNSName& name, const QType& type, std::vector<DNSRecord>& ret, int& res, bool doDNSSEC, ZoneEntry::CacheEntry& nextCloser, const DNSName& wildcardName, const OptLog& log)
 500 {
 501   vState cachedState;
 502
 503   std::vector<DNSRecord> wcSet;
 504   std::vector<std::shared_ptr<const RRSIGRecordContent>> wcSignatures;
 505
 506   if (g_recCache->get(now, wildcardName, type, MemRecursorCache::RequireAuth, &wcSet, ComboAddress("127.0.0.1"), boost::none, doDNSSEC ? &wcSignatures : nullptr, nullptr, nullptr, &cachedState) <= 0 || cachedState != vState::Secure) {
 507     VLOG(log, name << ": Unfortunately we don't have a valid entry for " << wildcardName << ", so we cannot synthesize from that wildcard" << endl);
 508     return false;
 509   }
 510
 511   addToRRSet(now, wcSet, std::move(wcSignatures), name, doDNSSEC, ret, DNSResourceRecord::ANSWER);
 512   /* no need for closest encloser proof, the wildcard is there */
 513   // coverity[store_truncates_time_t]
 514   addRecordToRRSet(nextCloser.d_owner, QType::NSEC3, nextCloser.d_ttd - now, nextCloser.d_record, nextCloser.d_signatures, doDNSSEC, ret);
 515   /* and of course we won't deny the wildcard either */
 516
 517   VLOG(log, name << ": Synthesized valid answer from NSEC3s and wildcard!" << endl);
 518   ++d_nsec3WildcardHits;
 519   res = RCode::NoError;
 520   return true;
 521 }
 522
 523 bool AggressiveNSECCache::synthesizeFromNSECWildcard(time_t now, const DNSName& name, const QType& type, std::vector<DNSRecord>& ret, int& res, bool doDNSSEC, ZoneEntry::CacheEntry& nsec, const DNSName& wildcardName, const OptLog& log)
 524 {
 525   vState cachedState;
 526
 527   std::vector<DNSRecord> wcSet;
 528   std::vector<std::shared_ptr<const RRSIGRecordContent>> wcSignatures;
 529
 530   if (g_recCache->get(now, wildcardName, type, MemRecursorCache::RequireAuth, &wcSet, ComboAddress("127.0.0.1"), boost::none, doDNSSEC ? &wcSignatures : nullptr, nullptr, nullptr, &cachedState) <= 0 || cachedState != vState::Secure) {
 531     VLOG(log, name << ": Unfortunately we don't have a valid entry for " << wildcardName << ", so we cannot synthesize from that wildcard" << endl);
 532     return false;
 533   }
 534
 535   addToRRSet(now, wcSet, std::move(wcSignatures), name, doDNSSEC, ret, DNSResourceRecord::ANSWER);
 536   // coverity[store_truncates_time_t]
 537   addRecordToRRSet(nsec.d_owner, QType::NSEC, nsec.d_ttd - now, nsec.d_record, nsec.d_signatures, doDNSSEC, ret);
 538
 539   VLOG(log, name << ": Synthesized valid answer from NSECs and wildcard!" << endl);
 540   ++d_nsecWildcardHits;
 541   res = RCode::NoError;
 542   return true;
 543 }
 544
 545 bool AggressiveNSECCache::getNSEC3Denial(time_t now, std::shared_ptr<LockGuarded<AggressiveNSECCache::ZoneEntry>>& zoneEntry, std::vector<DNSRecord>& soaSet, std::vector<std::shared_ptr<const RRSIGRecordContent>>& soaSignatures, const DNSName& name, const QType& type, std::vector<DNSRecord>& ret, int& res, bool doDNSSEC, const OptLog& log, pdns::validation::ValidationContext& validationContext)
 546 {
 547   DNSName zone;
 548   std::string salt;
 549   uint16_t iterations;
 550
 551   {
 552     auto entry = zoneEntry->try_lock();
 553     if (!entry.owns_lock()) {
 554       return false;
 555     }
 556     salt = entry->d_salt;
 557     zone = entry->d_zone;
 558     iterations = entry->d_iterations;
 559   }
 560
 561   const auto zoneLabelsCount = zone.countLabels();
 562   if (s_nsec3DenialProofMaxCost != 0) {
 563     const auto worstCaseIterations = getNSEC3DenialProofWorstCaseIterationsCount(name.countLabels() - zoneLabelsCount, iterations, salt.length());
 564     if (worstCaseIterations > s_nsec3DenialProofMaxCost) {
 565       // skip NSEC3 aggressive cache for expensive NSEC3 parameters: "if you want us to take the pain of PRSD away from you, you need to make it cheap for us to do so"
 566       VLOG(log, name << ": Skipping aggressive use of the NSEC3 cache since the zone parameters are too expensive" << endl);
 567       return false;
 568     }
 569   }
 570
 571   auto nameHash = DNSName(toBase32Hex(getHashFromNSEC3(name, iterations, salt, validationContext))) + zone;
 572
 573   ZoneEntry::CacheEntry exactNSEC3;
 574   if (getNSEC3(now, zoneEntry, nameHash, exactNSEC3)) {
 575     VLOG(log, name << ": Found a direct NSEC3 match for " << nameHash);
 576     auto nsec3 = std::dynamic_pointer_cast<const NSEC3RecordContent>(exactNSEC3.d_record);
 577     if (!nsec3 || nsec3->d_iterations != iterations || nsec3->d_salt != salt) {
 578       VLOG_NO_PREFIX(log, " but the content is not valid, or has a different salt or iterations count" << endl);
 579       return false;
 580     }
 581
 582     if (!isTypeDenied(*nsec3, type)) {
 583       VLOG_NO_PREFIX(log, " but the requested type (" << type.toString() << ") does exist" << endl);
 584       return false;
 585     }
 586
 587     const DNSName signer = getSigner(exactNSEC3.d_signatures);
 588     /* here we need to allow an ancestor NSEC3 proving that a DS does not exist as it is an
 589        exact match for the name */
 590     if (type != QType::DS && isNSEC3AncestorDelegation(signer, exactNSEC3.d_owner, *nsec3)) {
 591       /* RFC 6840 section 4.1 "Clarifications on Nonexistence Proofs":
 592          Ancestor delegation NSEC or NSEC3 RRs MUST NOT be used to assume
 593          nonexistence of any RRs below that zone cut, which include all RRs at
 594          that (original) owner name other than DS RRs, and all RRs below that
 595          owner name regardless of type.
 596       */
 597       VLOG_NO_PREFIX(log, " but this is an ancestor delegation NSEC3" << endl);
 598       return false;
 599     }
 600
 601     if (type == QType::DS && !name.isRoot() && signer == name) {
 602       VLOG_NO_PREFIX(log, " but this NSEC3 comes from the child zone and cannot be used to deny a DS");
 603       return false;
 604     }
 605
 606     VLOG(log, ": done!" << endl);
 607     ++d_nsec3Hits;
 608     res = RCode::NoError;
 609     addToRRSet(now, soaSet, soaSignatures, zone, doDNSSEC, ret);
 610     addRecordToRRSet(exactNSEC3.d_owner, QType::NSEC3, exactNSEC3.d_ttd - now, exactNSEC3.d_record, exactNSEC3.d_signatures, doDNSSEC, ret);
 611     return true;
 612   }
 613
 614   VLOG(log, name << ": No direct NSEC3 match found for " << nameHash << ", looking for closest encloser" << endl);
 615   DNSName closestEncloser(name);
 616   bool found = false;
 617   ZoneEntry::CacheEntry closestNSEC3;
 618   auto remainingLabels = closestEncloser.countLabels() - 1;
 619   while (!found && closestEncloser.chopOff() && remainingLabels >= zoneLabelsCount) {
 620     auto closestHash = DNSName(toBase32Hex(getHashFromNSEC3(closestEncloser, iterations, salt, validationContext))) + zone;
 621     remainingLabels--;
 622
 623     if (getNSEC3(now, zoneEntry, closestHash, closestNSEC3)) {
 624       VLOG(log, name << ": Found closest encloser at " << closestEncloser << " (" << closestHash << ")" << endl);
 625
 626       auto nsec3 = std::dynamic_pointer_cast<const NSEC3RecordContent>(closestNSEC3.d_record);
 627       if (!nsec3 || nsec3->d_iterations != iterations || nsec3->d_salt != salt) {
 628         VLOG_NO_PREFIX(log, " but the content is not valid, or has a different salt or iterations count" << endl);
 629         break;
 630       }
 631
 632       const DNSName signer = getSigner(closestNSEC3.d_signatures);
 633       /* This time we do not allow any ancestor NSEC3, as if the closest encloser is a delegation
 634          NS we know nothing about the names in the child zone. */
 635       if (isNSEC3AncestorDelegation(signer, closestNSEC3.d_owner, *nsec3)) {
 636         /* RFC 6840 section 4.1 "Clarifications on Nonexistence Proofs":
 637            Ancestor delegation NSEC or NSEC3 RRs MUST NOT be used to assume
 638            nonexistence of any RRs below that zone cut, which include all RRs at
 639            that (original) owner name other than DS RRs, and all RRs below that
 640            owner name regardless of type.
 641         */
 642         VLOG_NO_PREFIX(log, " but this is an ancestor delegation NSEC3" << endl);
 643         break;
 644       }
 645
 646       if (type == QType::DS && !name.isRoot() && signer == name) {
 647         VLOG_NO_PREFIX(log, " but this NSEC3 comes from the child zone and cannot be used to deny a DS");
 648         return false;
 649       }
 650
 651       found = true;
 652       break;
 653     }
 654   }
 655
 656   if (!found) {
 657     VLOG(log, name << ": Nothing found for the closest encloser in NSEC3 aggressive cache either" << endl);
 658     return false;
 659   }
 660
 661   unsigned int labelIdx = name.countLabels() - closestEncloser.countLabels();
 662   if (labelIdx < 1) {
 663     return false;
 664   }
 665
 666   DNSName nsecFound;
 667   DNSName nextCloser(closestEncloser);
 668   nextCloser.prependRawLabel(name.getRawLabel(labelIdx - 1));
 669   auto nextCloserHash = toBase32Hex(getHashFromNSEC3(nextCloser, iterations, salt, validationContext));
 670   VLOG(log, name << ": Looking for a NSEC3 covering the next closer " << nextCloser << " (" << nextCloserHash << ")" << endl);
 671
 672   ZoneEntry::CacheEntry nextCloserEntry;
 673   if (!getNSECBefore(now, zoneEntry, DNSName(nextCloserHash) + zone, nextCloserEntry)) {
 674     VLOG(log, name << ": Nothing found for the next closer in NSEC3 aggressive cache" << endl);
 675     return false;
 676   }
 677
 678   if (!isCoveredByNSEC3Hash(DNSName(nextCloserHash) + zone, nextCloserEntry.d_owner, nextCloserEntry.d_next)) {
 679     VLOG(log, name << ": No covering record found for the next closer in NSEC3 aggressive cache" << endl);
 680     return false;
 681   }
 682
 683   auto nextCloserNsec3 = std::dynamic_pointer_cast<const NSEC3RecordContent>(nextCloserEntry.d_record);
 684   if (!nextCloserNsec3 || nextCloserNsec3->d_iterations != iterations || nextCloserNsec3->d_salt != salt) {
 685     VLOG(log, name << ": The NSEC3 covering the next closer is not valid, or has a different salt or iterations count, bailing out" << endl);
 686     return false;
 687   }
 688
 689   const DNSName nextCloserSigner = getSigner(nextCloserEntry.d_signatures);
 690   if (type == QType::DS && !name.isRoot() && nextCloserSigner == name) {
 691     VLOG(log, " but this NSEC3 comes from the child zone and cannot be used to deny a DS");
 692     return false;
 693   }
 694
 695   /* An ancestor NSEC3 would be fine here, since it does prove that there is no delegation at the next closer
 696      name (we don't insert opt-out NSEC3s into the cache). */
 697   DNSName wildcard(g_wildcarddnsname + closestEncloser);
 698   auto wcHash = toBase32Hex(getHashFromNSEC3(wildcard, iterations, salt, validationContext));
 699   VLOG(log, name << ": Looking for a NSEC3 covering the wildcard " << wildcard << " (" << wcHash << ")" << endl);
 700
 701   ZoneEntry::CacheEntry wcEntry;
 702   if (!getNSECBefore(now, zoneEntry, DNSName(wcHash) + zone, wcEntry)) {
 703     VLOG(log, name << ": Nothing found for the wildcard in NSEC3 aggressive cache" << endl);
 704     return false;
 705   }
 706
 707   if ((DNSName(wcHash) + zone) == wcEntry.d_owner) {
 708     VLOG(log, name << ": Found an exact match for the wildcard");
 709
 710     auto nsec3 = std::dynamic_pointer_cast<const NSEC3RecordContent>(wcEntry.d_record);
 711     if (!nsec3 || nsec3->d_iterations != iterations || nsec3->d_salt != salt) {
 712       VLOG_NO_PREFIX(log, " but the content is not valid, or has a different salt or iterations count" << endl);
 713       return false;
 714     }
 715
 716     const DNSName wcSigner = getSigner(wcEntry.d_signatures);
 717     /* It's an exact match for the wildcard, so it does exist. If we are looking for a DS
 718        an ancestor NSEC3 is fine, otherwise it does not prove anything. */
 719     if (type != QType::DS && isNSEC3AncestorDelegation(wcSigner, wcEntry.d_owner, *nsec3)) {
 720       /* RFC 6840 section 4.1 "Clarifications on Nonexistence Proofs":
 721          Ancestor delegation NSEC or NSEC3 RRs MUST NOT be used to assume
 722          nonexistence of any RRs below that zone cut, which include all RRs at
 723          that (original) owner name other than DS RRs, and all RRs below that
 724          owner name regardless of type.
 725       */
 726       VLOG_NO_PREFIX(log, " but the NSEC3 covering the wildcard is an ancestor delegation NSEC3, bailing out" << endl);
 727       return false;
 728     }
 729
 730     if (type == QType::DS && !name.isRoot() && wcSigner == name) {
 731       VLOG_NO_PREFIX(log, " but this wildcard NSEC3 comes from the child zone and cannot be used to deny a DS");
 732       return false;
 733     }
 734
 735     if (!isTypeDenied(*nsec3, type)) {
 736       VLOG_NO_PREFIX(log, " but the requested type (" << type.toString() << ") does exist" << endl);
 737       return synthesizeFromNSEC3Wildcard(now, name, type, ret, res, doDNSSEC, nextCloserEntry, wildcard, log);
 738     }
 739
 740     res = RCode::NoError;
 741     VLOG(log, endl);
 742   }
 743   else {
 744     if (!isCoveredByNSEC3Hash(DNSName(wcHash) + zone, wcEntry.d_owner, wcEntry.d_next)) {
 745       VLOG(log, name << ": No covering record found for the wildcard in aggressive cache" << endl);
 746       return false;
 747     }
 748
 749     auto nsec3 = std::dynamic_pointer_cast<const NSEC3RecordContent>(wcEntry.d_record);
 750     if (!nsec3 || nsec3->d_iterations != iterations || nsec3->d_salt != salt) {
 751       VLOG(log, name << ": The content of the NSEC3 covering the wildcard is not valid, or has a different salt or iterations count" << endl);
 752       return false;
 753     }
 754
 755     const DNSName wcSigner = getSigner(wcEntry.d_signatures);
 756     if (type == QType::DS && !name.isRoot() && wcSigner == name) {
 757       VLOG_NO_PREFIX(log, " but this wildcard NSEC3 comes from the child zone and cannot be used to deny a DS");
 758       return false;
 759     }
 760
 761     /* We have a NSEC3 proving that the wildcard does not exist. An ancestor NSEC3 would be fine here, since it does prove
 762        that there is no delegation at the wildcard name (we don't insert opt-out NSEC3s into the cache). */
 763     res = RCode::NXDomain;
 764   }
 765
 766   addToRRSet(now, soaSet, soaSignatures, zone, doDNSSEC, ret);
 767   addRecordToRRSet(closestNSEC3.d_owner, QType::NSEC3, closestNSEC3.d_ttd - now, closestNSEC3.d_record, closestNSEC3.d_signatures, doDNSSEC, ret);
 768
 769   /* no need to include the same NSEC3 twice */
 770   if (nextCloserEntry.d_owner != closestNSEC3.d_owner) {
 771     addRecordToRRSet(nextCloserEntry.d_owner, QType::NSEC3, nextCloserEntry.d_ttd - now, nextCloserEntry.d_record, nextCloserEntry.d_signatures, doDNSSEC, ret);
 772   }
 773   if (wcEntry.d_owner != closestNSEC3.d_owner && wcEntry.d_owner != nextCloserEntry.d_owner) {
 774     // coverity[store_truncates_time_t]
 775     addRecordToRRSet(wcEntry.d_owner, QType::NSEC3, wcEntry.d_ttd - now, wcEntry.d_record, wcEntry.d_signatures, doDNSSEC, ret);
 776   }
 777
 778   VLOG(log, name << ": Found valid NSEC3s covering the requested name and type!" << endl);
 779   ++d_nsec3Hits;
 780   return true;
 781 }
 782
 783 bool AggressiveNSECCache::getDenial(time_t now, const DNSName& name, const QType& type, std::vector<DNSRecord>& ret, int& res, const ComboAddress& who, const boost::optional<std::string>& routingTag, bool doDNSSEC, pdns::validation::ValidationContext& validationContext, const OptLog& log)
 784 {
 785   std::shared_ptr<LockGuarded<ZoneEntry>> zoneEntry;
 786   if (type == QType::DS) {
 787     DNSName parent(name);
 788     parent.chopOff();
 789     zoneEntry = getBestZone(parent);
 790   }
 791   else {
 792     zoneEntry = getBestZone(name);
 793   }
 794
 795   if (!zoneEntry) {
 796     return false;
 797   }
 798
 799   DNSName zone;
 800   bool nsec3;
 801   {
 802     auto entry = zoneEntry->try_lock();
 803     if (!entry.owns_lock()) {
 804       return false;
 805     }
 806     if (entry->d_entries.empty()) {
 807       return false;
 808     }
 809     zone = entry->d_zone;
 810     nsec3 = entry->d_nsec3;
 811   }
 812
 813   vState cachedState;
 814   std::vector<DNSRecord> soaSet;
 815   std::vector<std::shared_ptr<const RRSIGRecordContent>> soaSignatures;
 816   /* we might not actually need the SOA if we find a matching wildcard, but let's not bother for now */
 817   if (g_recCache->get(now, zone, QType::SOA, MemRecursorCache::RequireAuth, &soaSet, who, routingTag, doDNSSEC ? &soaSignatures : nullptr, nullptr, nullptr, &cachedState) <= 0 || cachedState != vState::Secure) {
 818     VLOG(log, name << ": No valid SOA found for " << zone << ", which is the best match for " << name << endl);
 819     return false;
 820   }
 821
 822   if (nsec3) {
 823     return getNSEC3Denial(now, zoneEntry, soaSet, soaSignatures, name, type, ret, res, doDNSSEC, log, validationContext);
 824   }
 825
 826   ZoneEntry::CacheEntry entry;
 827   ZoneEntry::CacheEntry wcEntry;
 828   bool covered = false;
 829   bool needWildcard = false;
 830
 831   VLOG(log, name << ": Looking for a NSEC before " << name);
 832   if (!getNSECBefore(now, zoneEntry, name, entry)) {
 833     VLOG_NO_PREFIX(log, ": nothing found in the aggressive cache" << endl);
 834     return false;
 835   }
 836
 837   auto content = std::dynamic_pointer_cast<const NSECRecordContent>(entry.d_record);
 838   if (!content) {
 839     return false;
 840   }
 841
 842   VLOG_NO_PREFIX(log, ": found a possible NSEC at " << entry.d_owner << " ");
 843   // note that matchesNSEC() takes care of ruling out ancestor NSECs for us
 844   auto denial = matchesNSEC(name, type.getCode(), entry.d_owner, *content, entry.d_signatures, log);
 845   if (denial == dState::NODENIAL || denial == dState::INCONCLUSIVE) {
 846     VLOG_NO_PREFIX(log, " but it does not cover us" << endl);
 847     return false;
 848   }
 849   else if (denial == dState::NXQTYPE) {
 850     covered = true;
 851     VLOG_NO_PREFIX(log, " and it proves that the type does not exist" << endl);
 852     res = RCode::NoError;
 853   }
 854   else if (denial == dState::NXDOMAIN) {
 855     VLOG_NO_PREFIX(log, " and it proves that the name does not exist" << endl);
 856     DNSName closestEncloser = getClosestEncloserFromNSEC(name, entry.d_owner, entry.d_next);
 857     DNSName wc = g_wildcarddnsname + closestEncloser;
 858
 859     VLOG(log, name << ": Now looking for a NSEC before the wildcard " << wc);
 860     if (!getNSECBefore(now, zoneEntry, wc, wcEntry)) {
 861       VLOG_NO_PREFIX(log, ": nothing found in the aggressive cache" << endl);
 862       return false;
 863     }
 864
 865     VLOG_NO_PREFIX(log, ": found a possible NSEC at " << wcEntry.d_owner << " ");
 866
 867     auto nsecContent = std::dynamic_pointer_cast<const NSECRecordContent>(wcEntry.d_record);
 868
 869     denial = matchesNSEC(wc, type.getCode(), wcEntry.d_owner, *nsecContent, wcEntry.d_signatures, log);
 870     if (denial == dState::NODENIAL || denial == dState::INCONCLUSIVE) {
 871
 872       if (wcEntry.d_owner == wc) {
 873         VLOG_NO_PREFIX(log, " proving that the wildcard does exist" << endl);
 874         return synthesizeFromNSECWildcard(now, name, type, ret, res, doDNSSEC, entry, wc, log);
 875       }
 876
 877       VLOG_NO_PREFIX(log, " but it does no cover us" << endl);
 878
 879       return false;
 880     }
 881     else if (denial == dState::NXQTYPE) {
 882       VLOG_NO_PREFIX(log, " and it proves that there is a matching wildcard, but the type does not exist" << endl);
 883       covered = true;
 884       res = RCode::NoError;
 885     }
 886     else if (denial == dState::NXDOMAIN) {
 887       VLOG_NO_PREFIX(log, " and it proves that there is no matching wildcard" << endl);
 888       covered = true;
 889       res = RCode::NXDomain;
 890     }
 891
 892     if (wcEntry.d_owner != wc && wcEntry.d_owner != entry.d_owner) {
 893       needWildcard = true;
 894     }
 895   }
 896
 897   if (!covered) {
 898     return false;
 899   }
 900
 901   ret.reserve(ret.size() + soaSet.size() + soaSignatures.size() + /* NSEC */ 1 + entry.d_signatures.size() + (needWildcard ? (/* NSEC */ 1 + wcEntry.d_signatures.size()) : 0));
 902
 903   addToRRSet(now, soaSet, std::move(soaSignatures), zone, doDNSSEC, ret);
 904   // coverity[store_truncates_time_t]
 905   addRecordToRRSet(entry.d_owner, QType::NSEC, entry.d_ttd - now, entry.d_record, entry.d_signatures, doDNSSEC, ret);
 906
 907   if (needWildcard) {
 908     // coverity[store_truncates_time_t]
 909     addRecordToRRSet(wcEntry.d_owner, QType::NSEC, wcEntry.d_ttd - now, wcEntry.d_record, wcEntry.d_signatures, doDNSSEC, ret);
 910   }
 911
 912   VLOG(log, name << ": Found valid NSECs covering the requested name and type!" << endl);
 913   ++d_nsecHits;
 914   return true;
 915 }
 916
 917 size_t AggressiveNSECCache::dumpToFile(std::unique_ptr<FILE, int (*)(FILE*)>& fp, const struct timeval& now)
 918 {
 919   size_t ret = 0;
 920
 921   auto zones = d_zones.read_lock();
 922   zones->visit([&ret, now, &fp](const SuffixMatchTree<std::shared_ptr<LockGuarded<ZoneEntry>>>& node) {
 923     if (!node.d_value) {
 924       return;
 925     }
 926
 927     auto zone = node.d_value->lock();
 928     fprintf(fp.get(), "; Zone %s\n", zone->d_zone.toString().c_str());
 929
 930     for (const auto& entry : zone->d_entries) {
 931       int64_t ttl = entry.d_ttd - now.tv_sec;
 932       try {
 933         fprintf(fp.get(), "%s %" PRId64 " IN %s %s\n", entry.d_owner.toString().c_str(), ttl, zone->d_nsec3 ? "NSEC3" : "NSEC", entry.d_record->getZoneRepresentation().c_str());
 934         for (const auto& signature : entry.d_signatures) {
 935           fprintf(fp.get(), "- RRSIG %s\n", signature->getZoneRepresentation().c_str());
 936         }
 937         ++ret;
 938       }
 939       catch (const std::exception& e) {
 940         fprintf(fp.get(), "; Error dumping record from zone %s: %s\n", zone->d_zone.toString().c_str(), e.what());
 941       }
 942       catch (...) {
 943         fprintf(fp.get(), "; Error dumping record from zone %s\n", zone->d_zone.toString().c_str());
 944       }
 945     }
 946   });
 947
 948   return ret;
 949 }