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