BIND 10 trac1198, updated. 63f318aa4405840d77c5e7afcf7c3437c5af241b [1198] Extract out the wildcard matching into a separate method
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Nov 21 18:37:28 UTC 2011
The branch, trac1198 has been updated
via 63f318aa4405840d77c5e7afcf7c3437c5af241b (commit)
via 2e12dd60da03170462efad07173036f973813bd8 (commit)
from 24c2111ed800e95bc62901cd3b2970692a205578 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 63f318aa4405840d77c5e7afcf7c3437c5af241b
Author: Stephen Morris <stephen at isc.org>
Date: Mon Nov 21 18:36:26 2011 +0000
[1198] Extract out the wildcard matching into a separate method
commit 2e12dd60da03170462efad07173036f973813bd8
Author: Stephen Morris <stephen at isc.org>
Date: Mon Nov 21 11:38:12 2011 +0000
[1198] Extracted search for delegation point into a separate method.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/database.cc | 312 ++++++++++++++++++++++++++-----------------
src/lib/datasrc/database.h | 150 ++++++++++++++++++++-
2 files changed, 341 insertions(+), 121 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/database.cc b/src/lib/datasrc/database.cc
index 0e867ba..574a721 100644
--- a/src/lib/datasrc/database.cc
+++ b/src/lib/datasrc/database.cc
@@ -14,6 +14,7 @@
#include <string>
#include <vector>
+#include <iostream>
#include <datasrc/database.h>
#include <datasrc/data_source.h>
@@ -389,55 +390,55 @@ DatabaseClient::Finder::findNSECCover(const Name& name) {
return (RRsetPtr());
}
-ZoneFinder::FindResult
-DatabaseClient::Finder::find(const isc::dns::Name& name,
- const isc::dns::RRType& type,
- isc::dns::RRsetList*,
- const FindOptions options)
-{
- // This variable is used to determine the difference between
- // NXDOMAIN and NXRRSET
- bool records_found = false;
- bool glue_ok((options & FIND_GLUE_OK) != 0);
- const bool dnssec_data((options & FIND_DNSSEC) != 0);
- bool get_cover(false);
+DatabaseClient::Finder::DelegationSearchResult
+DatabaseClient::Finder::findDelegationPoint(const isc::dns::Name& name,
+ const FindOptions options) {
+ // Result of search
isc::dns::RRsetPtr result_rrset;
ZoneFinder::Result result_status = SUCCESS;
- FoundRRsets found;
- logger.debug(DBG_TRACE_DETAILED, DATASRC_DATABASE_FIND_RECORDS)
- .arg(accessor_->getDBName()).arg(name).arg(type);
+
// In case we are in GLUE_OK mode and start matching wildcards,
// we can't do it under NS, so we store it here to check
isc::dns::RRsetPtr first_ns;
+ // Are we searching for glue?
+ bool glue_ok((options & FIND_GLUE_OK) != 0);
+
// First, do we have any kind of delegation (NS/DNAME) here?
const Name origin(getOrigin());
const size_t origin_label_count(origin.getLabelCount());
+
// Number of labels in the last known non-empty domain
size_t last_known(origin_label_count);
const size_t current_label_count(name.getLabelCount());
+
// This is how many labels we remove to get origin
const size_t remove_labels(current_label_count - origin_label_count);
- // Now go trough all superdomains from origin down
- for (int i(remove_labels); i > 0; --i) {
+ // Go through all superdomains from the origin down searching for nodes
+ // that indicate a delegation (NS or DNAME).
+ for (int i = remove_labels; i > 0; --i) {
Name superdomain(name.split(i));
+
+ // Note if this is the origin.
+ bool not_origin = (i != remove_labels);
+
// Look if there's NS or DNAME (but ignore the NS in origin)
- found = getRRsets(superdomain.toText(), DELEGATION_TYPES(),
- i != remove_labels);
+ FoundRRsets found = getRRsets(superdomain.toText(), DELEGATION_TYPES(),
+ not_origin);
if (found.first) {
// It contains some RRs, so it exists.
last_known = superdomain.getLabelCount();
const FoundIterator nsi(found.second.find(RRType::NS()));
const FoundIterator dni(found.second.find(RRType::DNAME()));
+
// In case we are in GLUE_OK mode, we want to store the
// highest encountered NS (but not apex)
- if (glue_ok && !first_ns && i != remove_labels &&
- nsi != found.second.end()) {
+ if (glue_ok && !first_ns && not_origin && nsi != found.second.end()) {
first_ns = nsi->second;
- } else if (!glue_ok && i != remove_labels &&
- nsi != found.second.end()) {
+
+ } else if (!glue_ok && not_origin && nsi != found.second.end()) {
// Do a NS delegation, but ignore NS in glue_ok mode. Ignore
// delegation in apex
LOG_DEBUG(logger, DBG_TRACE_DETAILED,
@@ -447,6 +448,7 @@ DatabaseClient::Finder::find(const isc::dns::Name& name,
result_status = DELEGATION;
// No need to go lower, found
break;
+
} else if (dni != found.second.end()) {
// Very similar with DNAME
LOG_DEBUG(logger, DBG_TRACE_DETAILED,
@@ -463,21 +465,170 @@ DatabaseClient::Finder::find(const isc::dns::Name& name,
}
}
}
+ return (DelegationSearchResult(result_status, result_rrset, first_ns,
+ last_known));
+}
+
+DatabaseClient::Finder::WildcardSearchResult
+DatabaseClient::Finder::findWildcardMatch(const isc::dns::Name& name,
+ const isc::dns::RRType& type,
+ const FindOptions options,
+ isc::dns::RRsetPtr& first_ns,
+ size_t last_known) {
+ // Result of search
+ isc::dns::RRsetPtr result_rrset;
+ ZoneFinder::Result result_status = SUCCESS;
+
+ // Search options
+ const bool dnssec_data((options & FIND_DNSSEC) != 0);
+
+ // Other
+ bool records_found = false; // Distinguish between NXDOMAIN and NXRRSET
+ WantedTypes final_types(FINAL_TYPES());
+ final_types.insert(type);
+
+ // We know that the name is a non-empty terminal, so check for wildcards.
+ // We can start at the last known non-empty domain and work up. We remove
+ // labels one by one and look for the wildcard there, up to the
+ // first non-empty domain.
+ for (size_t i = 1; i <= name.getLabelCount() - last_known; ++i) {
+
+ // Construct the name with *
+ const Name superdomain(name.split(i));
+ const string wildcard("*." + superdomain.toText());
+ const string construct_name(name.toText());
+
+ // TODO What do we do about DNAME here?
+ // The types are the same as with original query
+ FoundRRsets found = getRRsets(wildcard, final_types, true,
+ &construct_name);
+ if (found.first) {
+ if (first_ns) {
+ // In case we are under NS, we don't wildcard-match, but return
+ // delegation
+ result_rrset = first_ns;
+ result_status = DELEGATION;
+ records_found = true;
+
+ LOG_DEBUG(logger, DBG_TRACE_DETAILED,
+ DATASRC_DATABASE_WILDCARD_CANCEL_NS).
+ arg(accessor_->getDBName()).arg(wildcard).
+ arg(first_ns->getName());
+
+ } else if (!hasSubdomains(name.split(i - 1).toText())) {
+
+ // Nothing we added as part of the * can exist directly, as we
+ // go up only to first existing domain, but it could be an empty
+ // non-terminal. In that case, we need to cancel the match.
+
+ records_found = true;
+ const FoundIterator cni(found.second.find(RRType::CNAME()));
+ const FoundIterator nsi(found.second.find(RRType::NS()));
+ const FoundIterator nci(found.second.find(RRType::NSEC()));
+ const FoundIterator wti(found.second.find(type));
+ if (cni != found.second.end() && type != RRType::CNAME()) {
+ result_rrset = cni->second;
+ result_status = WILDCARD_CNAME;
+
+ } else if (nsi != found.second.end()) {
+ result_rrset = nsi->second;
+ result_status = DELEGATION;
+
+ } else if (wti != found.second.end()) {
+ result_rrset = wti->second;
+ result_status = WILDCARD;
+
+ } else {
+ // NXRRSET case in the wildcard
+ result_status = WILDCARD_NXRRSET;
+ if (dnssec_data &&
+ nci != found.second.end()) {
+ // User wants a proof the wildcard doesn't contain it
+ //
+ // However, we need to get the RRset in the name of the
+ // wildcard, not the constructed one, so we walk it
+ // again
+ found = getRRsets(wildcard, NSEC_TYPES(), true);
+ result_rrset =
+ found.second.find(RRType::NSEC())->second;
+ }
+ }
+
+ LOG_DEBUG(logger, DBG_TRACE_DETAILED,
+ DATASRC_DATABASE_WILDCARD).
+ arg(accessor_->getDBName()).arg(wildcard).
+ arg(name);
+ } else {
+ LOG_DEBUG(logger, DBG_TRACE_DETAILED,
+ DATASRC_DATABASE_WILDCARD_CANCEL_SUB).
+ arg(accessor_->getDBName()).arg(wildcard).
+ arg(name).arg(superdomain);
+ }
+ break;
+ } else if (hasSubdomains(wildcard)) {
+ // Empty non-terminal asterisk
+ records_found = true;
+ LOG_DEBUG(logger, DBG_TRACE_DETAILED,
+ DATASRC_DATABASE_WILDCARD_EMPTY).
+ arg(accessor_->getDBName()).arg(wildcard).
+ arg(name);
+ if (dnssec_data) {
+ result_rrset = findNSECCover(Name(wildcard));
+ if (result_rrset) {
+ result_status = WILDCARD_NXRRSET;
+ }
+ }
+ break;
+ }
+ }
+ return (WildcardSearchResult(result_status, result_rrset, records_found));
+}
+
+ZoneFinder::FindResult
+DatabaseClient::Finder::find(const isc::dns::Name& name,
+ const isc::dns::RRType& type,
+ isc::dns::RRsetList*,
+ const FindOptions options)
+{
+ LOG_DEBUG(logger, DBG_TRACE_DETAILED, DATASRC_DATABASE_FIND_RECORDS)
+ .arg(accessor_->getDBName()).arg(name).arg(type);
+
+ bool glue_ok((options & FIND_GLUE_OK) != 0);
+ const bool dnssec_data((options & FIND_DNSSEC) != 0);
+
+ bool records_found = false; // Distinguish between NXDOMAIN and NXRRSET
+ bool get_cover = false;
+ isc::dns::RRsetPtr result_rrset;
+ ZoneFinder::Result result_status = SUCCESS;
+ const Name origin(getOrigin());
+
+ // First stage: go throught all superdomains from the origin down,
+ // searching for nodes that indicate a delegation (NS or DNAME).
+ DelegationSearchResult dresult = findDelegationPoint(name, options);
+ result_status = dresult.code;
+ result_rrset = dresult.rrset;
+
+ // In case we are in GLUE_OK mode and start matching wildcards,
+ // we can't do it under NS, so we store it here to check
+ isc::dns::RRsetPtr first_ns = dresult.first_ns;
+ size_t last_known = dresult.last_known;
if (!result_rrset) { // Only if we didn't find a redirect already
+
// Try getting the final result and extract it
// It is special if there's a CNAME or NS, DNAME is ignored here
// And we don't consider the NS in origin
-
WantedTypes final_types(FINAL_TYPES());
final_types.insert(type);
- found = getRRsets(name.toText(), final_types, name != origin);
+ FoundRRsets found = getRRsets(name.toText(), final_types,
+ name != origin);
records_found = found.first;
// NS records, CNAME record and Wanted Type records
const FoundIterator nsi(found.second.find(RRType::NS()));
const FoundIterator cni(found.second.find(RRType::CNAME()));
const FoundIterator wti(found.second.find(type));
+
if (name != origin && !glue_ok && nsi != found.second.end()) {
// There's a delegation at the exact node.
LOG_DEBUG(logger, DBG_TRACE_DETAILED,
@@ -485,6 +636,7 @@ DatabaseClient::Finder::find(const isc::dns::Name& name,
arg(accessor_->getDBName()).arg(name);
result_status = DELEGATION;
result_rrset = nsi->second;
+
} else if (type != isc::dns::RRType::CNAME() &&
cni != found.second.end()) {
// A CNAME here
@@ -495,19 +647,22 @@ DatabaseClient::Finder::find(const isc::dns::Name& name,
result_rrset->getRdataCount() <<
" rdata at " << name << ", expected 1");
}
+
} else if (wti != found.second.end()) {
// Just get the answer
result_rrset = wti->second;
+
} else if (!records_found) {
// Nothing lives here.
- // But check if something lives below this
- // domain and if so, pretend something is here as well.
+ // But check if something lives below this domain and if so,
+ // pretend something is here as well.
if (hasSubdomains(name.toText())) {
LOG_DEBUG(logger, DBG_TRACE_DETAILED,
DATASRC_DATABASE_FOUND_EMPTY_NONTERMINAL).
arg(accessor_->getDBName()).arg(name);
records_found = true;
get_cover = dnssec_data;
+
} else if ((options & NO_WILDCARD) != 0) {
// If wildcard check is disabled, the search will ultimately
// terminate with NXDOMAIN. If DNSSEC is enabled, flag that
@@ -515,102 +670,19 @@ DatabaseClient::Finder::find(const isc::dns::Name& name,
if (dnssec_data) {
get_cover = true;
}
+
} else {
- // It's not empty non-terminal. So check for wildcards.
+ // It's not an empty non-terminal so check for wildcards.
// We remove labels one by one and look for the wildcard there.
// Go up to first non-empty domain.
- for (size_t i(1); i <= current_label_count - last_known; ++i) {
- // Construct the name with *
- const Name superdomain(name.split(i));
- const string wildcard("*." + superdomain.toText());
- const string construct_name(name.toText());
- // TODO What do we do about DNAME here?
- // The types are the same as with original query
- found = getRRsets(wildcard, final_types, true,
- &construct_name);
- if (found.first) {
- if (first_ns) {
- // In case we are under NS, we don't
- // wildcard-match, but return delegation
- result_rrset = first_ns;
- result_status = DELEGATION;
- records_found = true;
- // We pretend to switch to non-glue_ok mode
- glue_ok = false;
- LOG_DEBUG(logger, DBG_TRACE_DETAILED,
- DATASRC_DATABASE_WILDCARD_CANCEL_NS).
- arg(accessor_->getDBName()).arg(wildcard).
- arg(first_ns->getName());
- } else if (!hasSubdomains(name.split(i - 1).toText()))
- {
- // Nothing we added as part of the * can exist
- // directly, as we go up only to first existing
- // domain, but it could be empty non-terminal. In
- // that case, we need to cancel the match.
- records_found = true;
- const FoundIterator
- cni(found.second.find(RRType::CNAME()));
- const FoundIterator
- nsi(found.second.find(RRType::NS()));
- const FoundIterator
- nci(found.second.find(RRType::NSEC()));
- const FoundIterator wti(found.second.find(type));
- if (cni != found.second.end() &&
- type != RRType::CNAME()) {
- result_rrset = cni->second;
- result_status = WILDCARD_CNAME;
- } else if (nsi != found.second.end()) {
- result_rrset = nsi->second;
- result_status = DELEGATION;
- } else if (wti != found.second.end()) {
- result_rrset = wti->second;
- result_status = WILDCARD;
- } else {
- // NXRRSET case in the wildcard
- result_status = WILDCARD_NXRRSET;
- if (dnssec_data &&
- nci != found.second.end()) {
- // User wants a proof the wildcard doesn't
- // contain it
- //
- // However, we need to get the RRset in the
- // name of the wildcard, not the constructed
- // one, so we walk it again
- found = getRRsets(wildcard, NSEC_TYPES(),
- true);
- result_rrset =
- found.second.find(RRType::NSEC())->
- second;
- }
- }
-
- LOG_DEBUG(logger, DBG_TRACE_DETAILED,
- DATASRC_DATABASE_WILDCARD).
- arg(accessor_->getDBName()).arg(wildcard).
- arg(name);
- } else {
- LOG_DEBUG(logger, DBG_TRACE_DETAILED,
- DATASRC_DATABASE_WILDCARD_CANCEL_SUB).
- arg(accessor_->getDBName()).arg(wildcard).
- arg(name).arg(superdomain);
- }
- break;
- } else if (hasSubdomains(wildcard)) {
- // Empty non-terminal asterisk
- records_found = true;
- LOG_DEBUG(logger, DBG_TRACE_DETAILED,
- DATASRC_DATABASE_WILDCARD_EMPTY).
- arg(accessor_->getDBName()).arg(wildcard).
- arg(name);
- if (dnssec_data) {
- result_rrset = findNSECCover(Name(wildcard));
- if (result_rrset) {
- result_status = WILDCARD_NXRRSET;
- }
- }
- break;
- }
- }
+ WildcardSearchResult wresult = findWildcardMatch(name, type,
+ options,
+ first_ns,
+ last_known);
+ result_status = wresult.code;
+ result_rrset = wresult.rrset;
+ records_found = wresult.records_found;
+
// This is the NXDOMAIN case (nothing found anywhere). If
// they want DNSSEC data, try getting the NSEC record
if (dnssec_data && !records_found) {
diff --git a/src/lib/datasrc/database.h b/src/lib/datasrc/database.h
index 2ac10e7..c069006 100644
--- a/src/lib/datasrc/database.h
+++ b/src/lib/datasrc/database.h
@@ -18,10 +18,11 @@
#include <string>
#include <boost/scoped_ptr.hpp>
+#include <boost/tuple/tuple.hpp>
#include <dns/rrclass.h>
-#include <dns/rrclass.h>
#include <dns/rrset.h>
+#include <dns/rrtype.h>
#include <datasrc/client.h>
@@ -814,6 +815,66 @@ public:
const DatabaseAccessor& getAccessor() const {
return (*accessor_);
}
+
+ /// \brief Search result of \c findDelegationPoint().
+ ///
+ /// This is a tuple combining the result of the search - a status code
+ /// and a pointer to the RRset found - together with additional
+ /// information needed for subsequent processing, an indication of
+ /// the first NS RRset found in the search and the number of labels
+ /// in the last non-empty domain encountered in the search. It is
+ /// used by \c findDelegationPoint().
+ ///
+ /// The last two items are located naturally in the search and although
+ /// not strictly part of the result, they are passed back to avoid
+ /// another (duplicate) search later in the processing.
+ ///
+ /// Note that the code and rrset elements are the same as that in
+ /// the \c ZoneFinder::FindResult struct: this structure could be
+ /// derived from that one, but as it is used just once in the code and
+ /// will never be treated as a \c FindResult, the obscurity involved in
+ /// deriving it from a parent class was deemed not worthwhile.
+ struct DelegationSearchResult {
+ DelegationSearchResult(const ZoneFinder::Result param_code,
+ const isc::dns::RRsetPtr param_rrset,
+ const isc::dns::RRsetPtr param_ns,
+ size_t param_last_known) :
+ code(param_code), rrset(param_rrset),
+ first_ns(param_ns),
+ last_known(param_last_known)
+ {}
+ const ZoneFinder::Result code; ///< Result code
+ const isc::dns::RRsetPtr rrset; ///< Pointer to RRset found
+ const isc::dns::RRsetPtr first_ns; ///< Pointer to first NS found
+ const size_t last_known; ///< No. labels in last non-empty domain
+ };
+
+ /// \brief Search result of \c findWildcard().
+ ///
+ /// This is a tuple combining the result of the search - a status code
+ /// and a pointer to the RRset found - together with additional
+ /// information needed for subsequent processing: if there is not a
+ /// match for the data sought, then whether there is no match for the
+ /// wildcard or where there is a match, but no RRs of the type
+ /// requested.
+ ///
+ /// Note that the code and rrset elements are the same as that in
+ /// the \c ZoneFinder::FindResult struct: this structure could be
+ /// derived from that one, but as it is used just once in the code and
+ /// will never be treated as a \c FindResult, the obscurity involved in
+ /// deriving it from a parent class was deemed not worthwhile.
+ struct WildcardSearchResult {
+ WildcardSearchResult(const ZoneFinder::Result param_code,
+ const isc::dns::RRsetPtr param_rrset,
+ const bool param_found) :
+ code(param_code), rrset(param_rrset),
+ records_found(param_found)
+ {}
+ const ZoneFinder::Result code; ///< Result code
+ const isc::dns::RRsetPtr rrset; ///< Pointer to RRset found
+ const bool records_found; ///< true => NXRRSET
+ };
+
private:
boost::shared_ptr<DatabaseAccessor> accessor_;
const int zone_id_;
@@ -824,6 +885,7 @@ public:
FoundRRsets;
/// \brief Just shortcut for set of types
typedef std::set<dns::RRType> WantedTypes;
+
/**
* \brief Searches database for RRsets of one domain.
*
@@ -854,6 +916,92 @@ public:
FoundRRsets getRRsets(const std::string& name,
const WantedTypes& types, bool check_ns,
const std::string* construct_name = NULL);
+
+ /**
+ * \brief Find delegation point
+ *
+ * Given a name, searches through the superdomains from the origin
+ * down, searching for a point that indicates a delegation (i.e. an
+ * NS record or a DNAME).
+ *
+ * The method operates in two modes, non-glue-ok and glue-ok modes:
+ *
+ * In non-glue-ok mode, the search is made purely for the NS or DNAME
+ * RR. The zone is searched from the origin down looking for one
+ * of these RRTypes (and ignoring the NS records at the zone origin).
+ * A status is returned indicating what is found: DNAME, DELEGATION
+ * of SUCCESS, the last indicating that nothing was found, together
+ * with a pointer to the relevant RR.
+ *
+ * In glue-ok mode, the first NS encountered in the search (apart from
+ * the NS at the zone apex) is remembered but otherwise NS records are
+ * ignored and the search attempts to find a DNAME. The result is
+ * returned in the same format, along with a pointer to the first non-
+ * apex NS (if found).
+ *
+ * \param name The name to find
+ * \param options Options about how to search. See the documentation for
+ * ZoneFinder::FindOptions.
+ *
+ * \return Tuple holding the result of the search - the RRset of the
+ * delegation point and the type of the point (DELEGATION or
+ * DNAME) - and associated information. This latter item
+ * comprises two pieces of data: a pointer to the highest
+ * encountered NS, and the number of labels in the last known
+ * non-empty domain. The associated information is found as
+ * a natural part of the search for the delegation point and
+ * is used later in the find() processing; it is passed back
+ * to avoid the need to perform a second search to obtain it.
+ */
+ DelegationSearchResult
+ findDelegationPoint(const isc::dns::Name& name,
+ const FindOptions options);
+
+ /**
+ * \brief Find wildcard match
+ *
+ * Having found that the name is not an empty non-terminal, this
+ * searches the zone for for wildcards that match the name.
+ *
+ * It searches superdomains of the name from the zone origin down
+ * looking for a wildcard in the zone that matches the name. There
+ * are several cases to consider:
+ *
+ * - If the previous search for a delegation point has found that
+ * there is an NS at the superdomain of the point at which the
+ * wildcard is found, the delegation is returned.
+ * - If there is a match to the name, an appropriate status is
+ * returned (match on requested type, delegation, cname, or just
+ * the indication of a match but no RRs relevant to the query).
+ * - If the match is to an non-empty non-terminal wildcard, a
+ * wildcard NXRRSET is returned.
+ *
+ * Note that if DNSSEC is enabled for the search and the zone uses
+ * NSEC for authenticated denial of existence, the search may
+ * return NSEC records.
+ *
+ * \param name The name to find
+ * \param type The RRType to find
+ * \param options Options about how to search. See the documentation
+ * for ZoneFinder::FindOptions.
+ * \param first_ns A pointer to the first NS found in a search for
+ * the name (will only be non-null in glue-ok mode).
+ * \param last_known the number of labels in the last known non-empty
+ * domain in the name.
+ *
+ * \return Tuple holding the result of the search - the RRset of the
+ * wildcard records matching the name, together with a status
+ * indicating the match type (e.g. CNAME at the wildcard
+ * match, no RRs of the requested type at the wildcard,
+ * success due to an exact match). Also returned if there
+ * is no match is an indication as to whether there was an
+ * NXDOMAIN or an NXRRSET.
+ */
+ WildcardSearchResult
+ findWildcardMatch(const isc::dns::Name& name,
+ const isc::dns::RRType& type, const FindOptions options,
+ isc::dns::RRsetPtr& first_ns, size_t last_known);
+
/**
* \brief Checks if something lives below this domain.
*
More information about the bind10-changes
mailing list