0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsCopyright (C) 1999-2001, 2004, 2016 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsThis Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsLicense, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrewsfile, You can obtain one at http://mozilla.org/MPL/2.0/.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews$Id: search,v 1.10 2004/03/05 05:04:47 marka Exp $
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyWhat follows is pseudocode for the zone and cache lookup algorithms, as they
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleywill work in the RBT DB.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyNote: These algorithms differ in some respects from those discussed in
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halleythe RFCs and drafts. I believe these algorithms provide better
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halleyanswers in some cases.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyPreliminary Stuff
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyBIND 9 zone databases are versioned, and every search is done in the
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleycontext of some version. There are a number of ways of implementing
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyversioning. The method that's going to be used in the RBT DB is to
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleystore a serial number with every rdataset. All rdatasets added as the
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyresult of a single database update have the same serial number. This
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyserial number is not related to the SOA serial, since the SOA serial
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyis under user control and can do weird things. The database serial
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleynumber is a monotonically increasing value. When you go to retrieve
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyan rdataset, you may encounter many rdatasets of that type at any
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleygiven node. The correct one to return, called the "active rdataset",
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyhas the greatest serial number less than or equal to the serial number
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyused for the search. The version whose serial number is being used in
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleythe search is the "target version".
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyCache databases are not versioned. A search will always return the
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleymost recent value.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyDKZC == Deepest Known Zone Cut. This is the zone cut closest to the
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleydesired name. In a zone, it's either a delegation out of authoritative
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleydata, or it's the top of the zone.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob HalleyZC == "zone cut", a node not at the zone top which has an active NS
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halleyrdataset, or a node (including the zone top) with an active DNAME
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David LawrenceZone Search Algorithm
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Search rdata type (including ANY)
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Search options
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley The search options parameter is a flags variable. Current
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Glue OK If set, then the caller is
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley wants best match results for
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley the search name, even if it's
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley glue. If not set, the caller
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley will get a delegation if the
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley search name is glue.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Glue Validation Section 7.18 of RFC 2136
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley requires that certain data that
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley is not in the zone and is not
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley glue remain stored in the zone.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley A search can never return this
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley data, but there might be glue
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley mixed in with it. Telling glue
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley from non glue involves some
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley work, especially since the
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley database is versioned. Often,
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley however, the caller will know
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley the name it's looking for is
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley glue, so validation isn't
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley the name of the node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset (not bound if querying for ANY)
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Note: The node, name, and rdataset are optional. If the
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley caller doesn't care about them, they won't be set.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Note: there is no EDNS1 "longest match" support in the algorithm yet,
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley though I know how to do it.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley cname_ok = yes
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley search_must_succeed = no
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Search down from the root of the tree. If, while going down, we
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley encounter a zone cut node, then search the rdatasets at the zone
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley cut for active DNAME or NS rdatasets. Note that if we find both
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley an active DNAME rdataset and an active NS rdataset, then the DNAME
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset has precedence.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we found an active DNAME rdataset, the search ends here.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_DNAME
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = name of this node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = this node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset is the DNAME
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we found an active NS rdataset
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If finding glue is not OK, or we're not searching for
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley a glue type, then the search ends here.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_DELEGATION
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = name of this node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = this node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = NS
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley We remember that this node is the ZC.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley We remember this node's name.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley We'll ignore any zone cuts found further down
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Continue the search down.
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley Partial_Match:
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we don't have an exact match to the name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we're below a zone cut, then we need to return a referral.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_DELEGATION;
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = ZC name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = NS
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Else If this zone has any wildcards, then
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Go looking for a wildcard match for this name.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we found one,
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_WILDCARD
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = wildcard node name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Fall through to searching the wildcard node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley for the desired type.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley NXDOMAIN (finally!)
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If this is a secure zone then
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Find the greatest predecessor to this node
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley that has at least one active rdataset.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Change the type we're search for to NXT
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley cname_ok = no
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley search_must_succeed = yes
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_NXDOMAIN
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = <empty>
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = <unbound>
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = NULL
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we're here, then we've got a node and are now trying to find
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley an active rdataset of the desired type, or, in the case of an ANY
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley query, any active rdataset.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we're beneath a zone cut
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley cname_ok = no
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If the caller wants us to validate glue, then see if the
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley current name is a valid glue name for the ZC.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_DELEGATION;
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = ZC name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = NS
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley If the desired type is KEY, SIG, or NXT, then
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley cname_ok = no
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = current node name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = current node;
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Search the rdataset list for the desired type. If cname_ok, also
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley look for a CNAME rdataset. While searching, remember the active NXT
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley rdataset if we come across it. We must also determine if there are
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley any active rdatasets at the node.
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley If there are no active rdatasets at the node, then we've got an
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley exact name match, but the name doesn't exist in the desired version.
93106f3c4923865880d6203d035f518cda6c8c1fBob Halley This means we really have a partial match. Goto Partial_Match.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we didn't find the type we were looking for (including a failed
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If (search_must_succeed), then
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley The database is bad, e.g. missing NXT records.
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_BADDB
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = NULL
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = <empty>
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley Else if we're beneath a zone cut
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_DELEGATION
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = ZC name
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = NS
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_NXRDATASET
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If this is a secure zone then
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley If we found an active NXT rdataset
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = NXT rdataset
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_BADDB
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley *nodep = NULL
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley foundname = <empty>
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley rdataset = <unbound>
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley We have found the type we were looking for or we've found a CNAME.
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley If we're not doing any ANY query, didn't find the type we were looking
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley for, but did find a CNAME
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley result = DNS_R_CNAME
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley rdataset = CNAME
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley Else If we're beneath a zone cut
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_GLUE
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob Halley result = DNS_R_SUCCESS
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley If type is ANY
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley rdataset = <unbound>
88f1e866aa6e4e55f7ab535f21da96930289d026Bob Halley rdataset = the type we were looking for
2488942fbb6bcba94345ca3b1b3c7244902212f8Bob HalleyXXX This is now old XXX
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyNow for the cache lookup algorithm, which is a little different. The
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleycache algorithm takes an optional "zone DKZC". Say a server is
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyauthoritative for vix.com but not rc.vix.com. When it looks up
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleybb.rc.vix.com it will search vix.com and discover the delegation to
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyrc.vix.com. We then want to look in the cache for bb.rc.vix.com, and
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyif we don't find it, the authoritative delegation might be the best
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyDKZC (since there might not be anything for rc.vix.com in the cache),
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyso that's why we allow it to be an argument to the cache search
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleyalgorithm. Of course, the cache might have data for rc.vix.com
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halleycached, in which case we should use it and not the DKZC.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyDKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
8301652f71f6cfe594361d4a70dae22ca7cd63efBob HalleyCache Search Algorithm:
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Go down as far as possible remembering every parent node.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Remember the predecessor too.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If some rdataset for name exists
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Look for desired type or CNAME
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If negative cache entry
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Indicate this and return.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Indicate it and return.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Indicate we know nothing about this type at this
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley (Peek at predecessor to see if it has an NXT for the same
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley zone and which covers the QNAME. If so, return it.)
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Go up until we find a node with a DNAME or a zone cut.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley XXX DNAME draft says go up until you prove that there are no
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley ancestor DNAMEs at all XXX
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If there's a DNAME
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Return a DNAME result with the dname node and node name
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley XXX what if the zone DKZC is better (i.e. deeper)? XXX
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley We know nothing about this name.
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley XXX DNAME draft says that if we have a zone DKZC, we should
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley use it now. I say use the best DKZC you've got. XXX
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If we get all the way to '.' and we don't even have the
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley root NS records
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If we have a DKZC from authoritative data
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Return NO_KNOWN_AUTHORITY
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley (this will cause priming of root servers or,
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley perhaps, forwarding)
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley If we have a zone DKZC and it's better than the one we found
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley in the cache
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Return it (node and name).
8301652f71f6cfe594361d4a70dae22ca7cd63efBob Halley Return the cache DKZC (node and name).