search revision 499b34cea04a46823d003d4c0520c8b03e8513cb
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncCopyright (C) 1999-2001 Internet Software Consortium.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncSee COPYRIGHT in the source root or http://isc.org/copyright.html for terms.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync$Id: search,v 1.9 2001/01/09 21:46:53 bwelling Exp $
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncWhat follows is pseudocode for the zone and cache lookup algorithms, as they
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncwill work in the RBT DB.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncNote: These algorithms differ in some respects from those discussed in
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncthe RFCs and drafts. I believe these algorithms provide better
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncanswers in some cases.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncPreliminary Stuff
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncBIND 9 zone databases are versioned, and every search is done in the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsynccontext of some version. There are a number of ways of implementing
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncversioning. The method that's going to be used in the RBT DB is to
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstore a serial number with every rdataset. All rdatasets added as the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncresult of a single database update have the same serial number. This
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncserial number is not related to the SOA serial, since the SOA serial
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncis under user control and can do weird things. The database serial
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncnumber is a monotonically increasing value. When you go to retrieve
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncan rdataset, you may encounter many rdatasets of that type at any
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncgiven node. The correct one to return, called the "active rdataset",
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsynchas the greatest serial number less than or equal to the serial number
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncused for the search. The version whose serial number is being used in
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncthe search is the "target version".
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncCache databases are not versioned. A search will always return the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncmost recent value.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncDKZC == Deepest Known Zone Cut. This is the zone cut closest to the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncdesired name. In a zone, it's either a delegation out of authoritative
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncdata, or it's the top of the zone.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncZC == "zone cut", a node not at the zone top which has an active NS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncrdataset, or a node (including the zone top) with an active DNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncZone Search Algorithm
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Search name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Search rdata type (including ANY)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Search options
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync The search options parameter is a flags variable. Current
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Glue OK If set, then the caller is
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync wants best match results for
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync the search name, even if it's
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync glue. If not set, the caller
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync will get a delegation if the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync search name is glue.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Glue Validation Section 7.18 of RFC 2136
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync requires that certain data that
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync is not in the zone and is not
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync glue remain stored in the zone.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync A search can never return this
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync data, but there might be glue
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync mixed in with it. Telling glue
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync from non glue involves some
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync work, especially since the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync database is versioned. Often,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync however, the caller will know
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync the name it's looking for is
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync glue, so validation isn't
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result code
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync the name of the node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset (not bound if querying for ANY)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Note: The node, name, and rdataset are optional. If the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync caller doesn't care about them, they won't be set.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Note: there is no EDNS1 "longest match" support in the algorithm yet,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync though I know how to do it.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync cname_ok = yes
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync search_must_succeed = no
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Search down from the root of the tree. If, while going down, we
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync encounter a zone cut node, then search the rdatasets at the zone
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync cut for active DNAME or NS rdatasets. Note that if we find both
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync an active DNAME rdataset and an active NS rdataset, then the DNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset has precedence.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we found an active DNAME rdataset, the search ends here.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_DNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = name of this node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = this node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset is the DNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we found an active NS rdataset
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If finding glue is not OK, or we're not searching for
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync a glue type, then the search ends here.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_DELEGATION
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = name of this node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = this node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = NS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync We remember that this node is the ZC.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync We remember this node's name.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync We'll ignore any zone cuts found further down
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Continue the search down.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Partial_Match:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we don't have an exact match to the name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we're below a zone cut, then we need to return a referral.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_DELEGATION;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = ZC name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = ZC
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = NS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Else If this zone has any wildcards, then
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Go looking for a wildcard match for this name.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we found one,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_WILDCARD
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = wildcard node name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Fall through to searching the wildcard node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for the desired type.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync NXDOMAIN (finally!)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If this is a secure zone then
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Find the greatest predecessor to this node
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync that has at least one active rdataset.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Change the type we're search for to NXT
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync cname_ok = no
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync search_must_succeed = yes
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_NXDOMAIN
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = <empty>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = <unbound>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = NULL
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we're here, then we've got a node and are now trying to find
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync an active rdataset of the desired type, or, in the case of an ANY
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync query, any active rdataset.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we're beneath a zone cut
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync cname_ok = no
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If the caller wants us to validate glue, then see if the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync current name is a valid glue name for the ZC.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_DELEGATION;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = ZC name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = ZC
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = NS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If the desired type is KEY, SIG, or NXT, then
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync cname_ok = no
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = current node name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = current node;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Search the rdataset list for the desired type. If cname_ok, also
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync look for a CNAME rdataset. While searching, remember the active NXT
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset if we come across it. We must also determine if there are
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync any active rdatasets at the node.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If there are no active rdatasets at the node, then we've got an
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync exact name match, but the name doesn't exist in the desired version.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync This means we really have a partial match. Goto Partial_Match.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we didn't find the type we were looking for (including a failed
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ANY search)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If (search_must_succeed), then
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync The database is bad, e.g. missing NXT records.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_BADDB
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = NULL
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = <empty>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Else if we're beneath a zone cut
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_DELEGATION
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = ZC name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = ZC
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = NS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_NXRDATASET
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If this is a secure zone then
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we found an active NXT rdataset
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = NXT rdataset
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_BADDB
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *nodep = NULL
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync foundname = <empty>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = <unbound>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync We have found the type we were looking for or we've found a CNAME.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we're not doing any ANY query, didn't find the type we were looking
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for, but did find a CNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_CNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = CNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Else If we're beneath a zone cut
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_GLUE
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = DNS_R_SUCCESS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If type is ANY
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = <unbound>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync rdataset = the type we were looking for
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncXXX This is now old XXX
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncNow for the cache lookup algorithm, which is a little different. The
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsynccache algorithm takes an optional "zone DKZC". Say a server is
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncauthoritative for vix.com but not rc.vix.com. When it looks up
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncbb.rc.vix.com it will search vix.com and discover the delegation to
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncrc.vix.com. We then want to look in the cache for bb.rc.vix.com, and
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncif we don't find it, the authoritative delegation might be the best
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncDKZC (since there might not be anything for rc.vix.com in the cache),
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncso that's why we allow it to be an argument to the cache search
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncalgorithm. Of course, the cache might have data for rc.vix.com
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsynccached, in which case we should use it and not the DKZC.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncDKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncCache Search Algorithm:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Go down as far as possible remembering every parent node.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Remember the predecessor too.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If some rdataset for name exists
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Look for desired type or CNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If negative cache entry
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Indicate this and return.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Indicate it and return.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Indicate we know nothing about this type at this
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync (Peek at predecessor to see if it has an NXT for the same
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync zone and which covers the QNAME. If so, return it.)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Go up until we find a node with a DNAME or a zone cut.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync XXX DNAME draft says go up until you prove that there are no
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ancestor DNAMEs at all XXX
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If there's a DNAME
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Return a DNAME result with the dname node and node name
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync XXX what if the zone DKZC is better (i.e. deeper)? XXX
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync We know nothing about this name.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync XXX DNAME draft says that if we have a zone DKZC, we should
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync use it now. I say use the best DKZC you've got. XXX
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we get all the way to '.' and we don't even have the
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync root NS records
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we have a DKZC from authoritative data
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Return NO_KNOWN_AUTHORITY
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync (this will cause priming of root servers or,
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync perhaps, forwarding)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync If we have a zone DKZC and it's better than the one we found
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync in the cache
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Return it (node and name).
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Return the cache DKZC (node and name).