search revision 2488942fbb6bcba94345ca3b1b3c7244902212f8
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsWhat follows is pseudocode for the zone and cache lookup algorithms, as they
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewswill work in the RBT DB.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsNote: These algorithms differ in some respects from those discussed in
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsthe RFCs and drafts. I believe these algorithms provide better
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsanswers in some cases.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsPreliminary Stuff
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsBIND 9 zone databases are versioned, and every search is done in the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewscontext of some version. There are a number of ways of implementing
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsversioning. The method that's going to be used in the RBT DB is to
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsstore a serial number with every rdataset. All rdatasets added as the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsresult of a single database update have the same serial number. This
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsserial number is not related to the SOA serial, since the SOA serial
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsis under user control and can do weird things. The database serial
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsnumber is a monotonically increasing value. When you go to retrieve
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsan rdataset, you may encounter many rdatasets of that type at any
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsgiven node. The correct one to return, called the "active rdataset",
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewshas the greatest serial number less than or equal to the serial number
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsused for the search. The version whose serial number is being used in
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsthe search is the "target version".
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsCache databases are not versioned. A search will always return the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsmost recent value.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsDKZC == Deepest Known Zone Cut. This is the zone cut closest to the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsdesired name. In a zone, it's either a delegation out of authoritative
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsdata, or it's the top of the zone.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsZC == "zone cut", a node not at the zone top which has an active NS
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrewsrdataset.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark AndrewsZone Search Algorithm
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Inputs:
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Search name
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Search rdata type (including ANY)
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Search options
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews The search options parameter is a flags variable. Current
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews flags are
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Glue OK If set, then the caller is
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews wants best match results for
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews the search name, even if it's
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews glue. If not set, the caller
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews will get a delegation if the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews search name is glue.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Glue Validation Section 7.18 of RFC 2136
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews requires that certain data that
cc51cd2d2076e33117c60c9effcb8caccde4983bWitold Krecicki is not in the zone and is not
30370d905e9be3be7d9b947fd432bacecbb13bb9Evan Hunt glue remain stored in the zone.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews A search can never return this
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews data, but there might be glue
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews mixed in with it. Telling glue
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews from non glue involves some
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews work, especially since the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews database is versioned. Often,
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews however, the caller will know
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews the name it's looking for is
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews glue, so validation isn't
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews required.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Outputs:
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews result code
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews a node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews the name of the node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews rdataset (not bound if querying for ANY)
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Note: The node, name, and rdataset are optional. If the
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews caller doesn't care about them, they won't be set.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Note: there is no EDNS1 "longest match" support in the algorithm yet,
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews though I know how to do it.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
cc51cd2d2076e33117c60c9effcb8caccde4983bWitold Krecicki
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews cname_ok = yes
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews search_must_succeed = no
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Search down from the root of the tree. If, while going down, we
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews encounter a zone cut node, then search the rdatasets at the zone
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews cut for active DNAME or NS rdatasets. Note that if we find both
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews an active DNAME rdataset and an active NS rdataset, then the DNAME
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews rdataset has precedence.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews If we found an active DNAME rdataset, the search ends here.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews result = DNS_R_DNAME
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews foundname = name of this node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews *nodep = this node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews rdataset is the DNAME
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews return
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews If we found an active NS rdataset
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews If finding glue is not OK, or we're not searching for
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews a glue type, then the search ends here.
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews result = DNS_R_DELEGATION
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews foundname = name of this node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews *nodep = this node
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews rdataset = NS
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews return
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews Else
3b83676e079a799f97ad8b76c057e6ecb0426b1dMark Andrews We remember that this node is the ZC.
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews We remember this node's name.
We'll ignore any zone cuts found further down
the tree.
Continue the search down.
If we don't have an exact match to the name
If we're below a zone cut, then we need to return a referral.
result = DNS_R_DELEGATION;
foundname = ZC name
*nodep = ZC
rdataset = NS
return
Else If this zone has any wildcards, then
Go looking for a wildcard match for this name.
If we found one,
result = DNS_R_WILDCARD
foundname = wildcard node name
Fall through to searching the wildcard node
for the desired type.
Else
NXDOMAIN (finally!)
If this is a secure zone then
Find the greatest predecessor to this node
that has at least one active rdataset.
Change the type we're search for to NXT
cname_ok = no
search_must_succeed = yes
Else
result = DNS_R_NXDOMAIN
foundname = <empty>
rdataset = <unbound>
*nodep = NULL
return
If we're here, then we've got a node and are now trying to find
an active rdataset of the desired type, or, in the case of an ANY
query, any active rdataset.
If we're beneath a zone cut
cname ok = no
If the caller wants us to validate glue, then see if the
current name is a valid glue name for the ZC.
If not,
result = DNS_R_DELEGATION;
foundname = ZC name
*nodep = ZC
rdataset = NS
return
foundname = current node name
*nodep = current node;
Search the rdataset list for the desired type. If cname_ok, also
look for a CNAME rdataset. If type is ANY, then all we care about
is if there is *some* active rdataset at this node. While searching,
remember the active NXT rdataset if we come across it.
If type is ANY and there's at least one active rdataset
result = DNS_R_SUCCESS
rdataset = <unbound>
return
If we didn't find the type we were looking for (including a failed
ANY search)
If (search_must_succeed), then
The database is bad, e.g. missing NXT records.
result = DNS_R_BADDB
*nodep = NULL
foundname = <empty>
Else If we did find a CNAME, then
result = DNS_R_CNAME
rdataset = CNAME
Else if we're beneath a zone cut
result = DNS_R_DELEGATION
foundname = ZC name
*nodep = ZC
rdataset = NS
Else
result = DNS_R_NXRDATASET
If this is a secure zone then
If we found an active NXT rdataset
rdataset = NXT rdataset
Else
result = DNS_R_BADDB
*nodep = NULL
foundname = <empty>
Else
rdataset = <unbound>
return
Amazingly, we have found the type we were looking for!
If we're beneath a zone cut
result = DNS_R_GLUE
else
result = DNS_R_SUCCESS
rdataset = the type we were looking for
XXX This is now old XXX
Now for the cache lookup algorithm, which is a little different. The
cache algorithm takes an optional "zone DKZC". Say a server is
authoritative for vix.com but not rc.vix.com. When it looks up
bb.rc.vix.com it will search vix.com and discover the delegation to
rc.vix.com. We then want to look in the cache for bb.rc.vix.com, and
if we don't find it, the authoritative delegation might be the best
DKZC (since there might not be anything for rc.vix.com in the cache),
so that's why we allow it to be an argument to the cache search
algorithm. Of course, the cache might have data for rc.vix.com
cached, in which case we should use it and not the DKZC.
DKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
B.
Cache Search Algorithm:
Go down as far as possible remembering every parent node.
Remember the predecessor too.
If some rdataset for name exists
Look for desired type or CNAME
If found
If negative cache entry
Indicate this and return.
If CNAME?
Indicate it and return.
Return.
Else
Indicate we know nothing about this type at this
node.
Return.
Else
(Peek at predecessor to see if it has an NXT for the same
zone and which covers the QNAME. If so, return it.)
Go up until we find a node with a DNAME or a zone cut.
XXX DNAME draft says go up until you prove that there are no
ancestor DNAMEs at all XXX
If there's a DNAME
Return a DNAME result with the dname node and node name
XXX what if the zone DKZC is better (i.e. deeper)? XXX
We know nothing about this name.
XXX DNAME draft says that if we have a zone DKZC, we should
use it now. I say use the best DKZC you've got. XXX
If we get all the way to '.' and we don't even have the
root NS records
If we have a DKZC from authoritative data
Return it.
Else
Return NO_KNOWN_AUTHORITY
(this will cause priming of root servers or,
perhaps, forwarding)
If we have a zone DKZC and it's better than the one we found
in the cache
Return it (node and name).
Return the cache DKZC (node and name).