search revision 499b34cea04a46823d003d4c0520c8b03e8513cb
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCopyright (C) 1999-2001 Internet Software Consortium.
1fdd2470b625a58b57d0b155e6caf8c4fc0afe8aAutomatic UpdaterSee COPYRIGHT in the source root or http://isc.org/copyright.html for terms.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein$Id: search,v 1.9 2001/01/09 21:46:53 bwelling Exp $
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinWhat follows is pseudocode for the zone and cache lookup algorithms, as they
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinwill work in the RBT DB.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinNote: These algorithms differ in some respects from those discussed in
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinthe RFCs and drafts. I believe these algorithms provide better
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinanswers in some cases.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinPreliminary Stuff
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinBIND 9 zone databases are versioned, and every search is done in the
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updatercontext of some version. There are a number of ways of implementing
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinversioning. The method that's going to be used in the RBT DB is to
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinstore a serial number with every rdataset. All rdatasets added as the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinresult of a single database update have the same serial number. This
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinserial number is not related to the SOA serial, since the SOA serial
e21a2904f02a03fa06b6db04d348f65fe9c67b2bMark Andrewsis under user control and can do weird things. The database serial
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinnumber is a monotonically increasing value. When you go to retrieve
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinan rdataset, you may encounter many rdatasets of that type at any
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeingiven node. The correct one to return, called the "active rdataset",
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinhas the greatest serial number less than or equal to the serial number
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinused for the search. The version whose serial number is being used in
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinthe search is the "target version".
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCache databases are not versioned. A search will always return the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinmost recent value.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinDKZC == Deepest Known Zone Cut. This is the zone cut closest to the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeindesired name. In a zone, it's either a delegation out of authoritative
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeindata, or it's the top of the zone.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinZC == "zone cut", a node not at the zone top which has an active NS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinrdataset, or a node (including the zone top) with an active DNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinZone Search Algorithm
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Search rdata type (including ANY)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Search options
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein The search options parameter is a flags variable. Current
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater Glue OK If set, then the caller is
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater wants best match results for
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein the search name, even if it's
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein glue. If not set, the caller
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater will get a delegation if the
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater search name is glue.
9c6a5d1f22f972232d7a9fd5c5fa64f10bacbdffAutomatic Updater Glue Validation Section 7.18 of RFC 2136
9c6a5d1f22f972232d7a9fd5c5fa64f10bacbdffAutomatic Updater requires that certain data that
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updater is not in the zone and is not
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein glue remain stored in the zone.
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updater A search can never return this
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updater data, but there might be glue
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein mixed in with it. Telling glue
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein from non glue involves some
9c6a5d1f22f972232d7a9fd5c5fa64f10bacbdffAutomatic Updater work, especially since the
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updater database is versioned. Often,
ac93437301f55ed69bf85883a497a75598c628f9Automatic Updater however, the caller will know
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein the name it's looking for is
cbf7f1435f332b31f51a98611ccbfcd07c42c032Automatic Updater glue, so validation isn't
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein the name of the node
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset (not bound if querying for ANY)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Note: The node, name, and rdataset are optional. If the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein caller doesn't care about them, they won't be set.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Note: there is no EDNS1 "longest match" support in the algorithm yet,
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews though I know how to do it.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein cname_ok = yes
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein search_must_succeed = no
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Search down from the root of the tree. If, while going down, we
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein encounter a zone cut node, then search the rdatasets at the zone
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein cut for active DNAME or NS rdatasets. Note that if we find both
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein an active DNAME rdataset and an active NS rdataset, then the DNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset has precedence.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews If we found an active DNAME rdataset, the search ends here.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews result = DNS_R_DNAME
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater foundname = name of this node
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews *nodep = this node
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews rdataset is the DNAME
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews If we found an active NS rdataset
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If finding glue is not OK, or we're not searching for
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein a glue type, then the search ends here.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_DELEGATION
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = name of this node
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein *nodep = this node
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = NS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein We remember that this node is the ZC.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein We remember this node's name.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein We'll ignore any zone cuts found further down
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews Continue the search down.
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews Partial_Match:
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews If we don't have an exact match to the name
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews If we're below a zone cut, then we need to return a referral.
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews result = DNS_R_DELEGATION;
acb72d5e2c83b597332e3eb0c7d59e1142f1adfdMark Andrews foundname = ZC name
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = NS
38417cbfb1a328c20b5b723b8584a02c57f88897Automatic Updater Else If this zone has any wildcards, then
38417cbfb1a328c20b5b723b8584a02c57f88897Automatic Updater Go looking for a wildcard match for this name.
38417cbfb1a328c20b5b723b8584a02c57f88897Automatic Updater If we found one,
38417cbfb1a328c20b5b723b8584a02c57f88897Automatic Updater result = DNS_R_WILDCARD
38417cbfb1a328c20b5b723b8584a02c57f88897Automatic Updater foundname = wildcard node name
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Fall through to searching the wildcard node
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein for the desired type.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein NXDOMAIN (finally!)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If this is a secure zone then
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Find the greatest predecessor to this node
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein that has at least one active rdataset.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Change the type we're search for to NXT
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein cname_ok = no
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein search_must_succeed = yes
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_NXDOMAIN
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = <empty>
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = <unbound>
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein *nodep = NULL
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we're here, then we've got a node and are now trying to find
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein an active rdataset of the desired type, or, in the case of an ANY
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein query, any active rdataset.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we're beneath a zone cut
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein cname_ok = no
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If the caller wants us to validate glue, then see if the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein current name is a valid glue name for the ZC.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_DELEGATION;
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = ZC name
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = NS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If the desired type is KEY, SIG, or NXT, then
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein cname_ok = no
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = current node name
b05bdb520d83f7ecaad708fe305268c3420be01dMark Andrews *nodep = current node;
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Search the rdataset list for the desired type. If cname_ok, also
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein look for a CNAME rdataset. While searching, remember the active NXT
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset if we come across it. We must also determine if there are
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein any active rdatasets at the node.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If there are no active rdatasets at the node, then we've got an
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein exact name match, but the name doesn't exist in the desired version.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein This means we really have a partial match. Goto Partial_Match.
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews If we didn't find the type we were looking for (including a failed
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If (search_must_succeed), then
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein The database is bad, e.g. missing NXT records.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_BADDB
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein *nodep = NULL
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = <empty>
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Else if we're beneath a zone cut
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_DELEGATION
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = ZC name
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = NS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_NXRDATASET
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If this is a secure zone then
71c66a876ecca77923638d3f94cc0783152b2f03Mark Andrews If we found an active NXT rdataset
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = NXT rdataset
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_BADDB
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein *nodep = NULL
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein foundname = <empty>
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = <unbound>
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein We have found the type we were looking for or we've found a CNAME.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we're not doing any ANY query, didn't find the type we were looking
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein for, but did find a CNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_CNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = CNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Else If we're beneath a zone cut
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_GLUE
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein result = DNS_R_SUCCESS
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If type is ANY
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein rdataset = <unbound>
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrews rdataset = the type we were looking for
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinXXX This is now old XXX
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinNow for the cache lookup algorithm, which is a little different. The
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeincache algorithm takes an optional "zone DKZC". Say a server is
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinauthoritative for vix.com but not rc.vix.com. When it looks up
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinbb.rc.vix.com it will search vix.com and discover the delegation to
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinrc.vix.com. We then want to look in the cache for bb.rc.vix.com, and
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsif we don't find it, the authoritative delegation might be the best
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark AndrewsDKZC (since there might not be anything for rc.vix.com in the cache),
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewsso that's why we allow it to be an argument to the cache search
a1b05dea35aa30b152a47115e18bbe679d3fcf19Mark Andrewsalgorithm. Of course, the cache might have data for rc.vix.com
5a4557e8de2951a2796676b5ec4b6a90caa5be14Mark Andrewscached, in which case we should use it and not the DKZC.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinDKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCache Search Algorithm:
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Go down as far as possible remembering every parent node.
bea931e17b7567f09107f93ab7e25c7f00abeb9cMark Andrews Remember the predecessor too.
58d9e9169e7ab4355a0b0bfc13bc616bc5247dfeAutomatic Updater If some rdataset for name exists
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Look for desired type or CNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If negative cache entry
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Indicate this and return.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Indicate it and return.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Indicate we know nothing about this type at this
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein (Peek at predecessor to see if it has an NXT for the same
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein zone and which covers the QNAME. If so, return it.)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Go up until we find a node with a DNAME or a zone cut.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein XXX DNAME draft says go up until you prove that there are no
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein ancestor DNAMEs at all XXX
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If there's a DNAME
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Return a DNAME result with the dname node and node name
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein XXX what if the zone DKZC is better (i.e. deeper)? XXX
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein We know nothing about this name.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein XXX DNAME draft says that if we have a zone DKZC, we should
2cc6eb92f9443695bc32fa6eed372d983d261a35Automatic Updater use it now. I say use the best DKZC you've got. XXX
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we get all the way to '.' and we don't even have the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein root NS records
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we have a DKZC from authoritative data
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Return NO_KNOWN_AUTHORITY
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein (this will cause priming of root servers or,
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein perhaps, forwarding)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein If we have a zone DKZC and it's better than the one we found
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein in the cache
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Return it (node and name).
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein Return the cache DKZC (node and name).