search revision 40f53fa8d9c6a4fc38c0014495e7a42b08f52481
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉Copyright (C) 1999, 2000 Internet Software Consortium.
cbf0854acc9f5d11142dba30b1ab23e0532baaf2Automatic UpdaterSee COPYRIGHT in the source root or http://www.isc.org/copyright for terms.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater$Id: search,v 1.7 2000/08/01 01:18:16 tale Exp $
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉What follows is pseudocode for the zone and cache lookup algorithms, as they
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉will work in the RBT DB.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉Note: These algorithms differ in some respects from those discussed in
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉the RFCs and drafts. I believe these algorithms provide better
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉answers in some cases.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉Preliminary Stuff
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉BIND 9 zone databases are versioned, and every search is done in the
cbf0854acc9f5d11142dba30b1ab23e0532baaf2Automatic Updatercontext of some version. There are a number of ways of implementing
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉versioning. The method that's going to be used in the RBT DB is to
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉store a serial number with every rdataset. All rdatasets added as the
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉result of a single database update have the same serial number. This
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉serial number is not related to the SOA serial, since the SOA serial
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉is under user control and can do weird things. The database serial
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉number is a monotonically increasing value. When you go to retrieve
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉an rdataset, you may encounter many rdatasets of that type at any
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉given node. The correct one to return, called the "active rdataset",
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉has the greatest serial number less than or equal to the serial number
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉used for the search. The version whose serial number is being used in
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉the search is the "target version".
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
a84724de8db9e52857fb11bbcdb195658f9a05b2Michael GraffCache databases are not versioned. A search will always return the
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉most recent value.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉DKZC == Deepest Known Zone Cut. This is the zone cut closest to the
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉desired name. In a zone, it's either a delegation out of authoritative
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉data, or it's the top of the zone.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉ZC == "zone cut", a node not at the zone top which has an active NS
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉rdataset, or a node (including the zone top) with an active DNAME
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉rdataset.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉Zone Search Algorithm
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Inputs:
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Search name
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 Search rdata type (including ANY)
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 Search options
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 The search options parameter is a flags variable. Current
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 flags are
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 Glue OK If set, then the caller is
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 wants best match results for
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 the search name, even if it's
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 glue. If not set, the caller
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 will get a delegation if the
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 search name is glue.
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 Glue Validation Section 7.18 of RFC 2136
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 requires that certain data that
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 is not in the zone and is not
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 glue remain stored in the zone.
1c3ed2a83d176d9023b51b60dfc96c133f678362Tatuya JINMEI 神明達哉 A search can never return this
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 data, but there might be glue
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 mixed in with it. Telling glue
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 from non glue involves some
a84724de8db9e52857fb11bbcdb195658f9a05b2Michael Graff work, especially since the
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 database is versioned. Often,
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 however, the caller will know
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 the name it's looking for is
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 glue, so validation isn't
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 required.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Outputs:
cbf0854acc9f5d11142dba30b1ab23e0532baaf2Automatic Updater result code
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 a node
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 the name of the node
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 rdataset (not bound if querying for ANY)
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Note: The node, name, and rdataset are optional. If the
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 caller doesn't care about them, they won't be set.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Note: there is no EDNS1 "longest match" support in the algorithm yet,
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 though I know how to do it.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 cname_ok = yes
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 search_must_succeed = no
a84724de8db9e52857fb11bbcdb195658f9a05b2Michael Graff
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 Search down from the root of the tree. If, while going down, we
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 encounter a zone cut node, then search the rdatasets at the zone
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 cut for active DNAME or NS rdatasets. Note that if we find both
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 an active DNAME rdataset and an active NS rdataset, then the DNAME
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 rdataset has precedence.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 If we found an active DNAME rdataset, the search ends here.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 result = DNS_R_DNAME
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 foundname = name of this node
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 *nodep = this node
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 rdataset is the DNAME
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 return
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we found an active NS rdataset
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If finding glue is not OK, or we're not searching for
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 a glue type, then the search ends here.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 result = DNS_R_DELEGATION
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = name of this node
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 *nodep = this node
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 rdataset = NS
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 return
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Else
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 We remember that this node is the ZC.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 We remember this node's name.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 We'll ignore any zone cuts found further down
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 the tree.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Continue the search down.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Partial_Match:
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we don't have an exact match to the name
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we're below a zone cut, then we need to return a referral.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 result = DNS_R_DELEGATION;
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = ZC name
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 *nodep = ZC
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 rdataset = NS
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 return
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Else If this zone has any wildcards, then
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Go looking for a wildcard match for this name.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we found one,
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 result = DNS_R_WILDCARD
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = wildcard node name
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Fall through to searching the wildcard node
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 for the desired type.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Else
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 NXDOMAIN (finally!)
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If this is a secure zone then
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Find the greatest predecessor to this node
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 that has at least one active rdataset.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Change the type we're search for to NXT
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 cname_ok = no
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 search_must_succeed = yes
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Else
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 result = DNS_R_NXDOMAIN
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = <empty>
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 rdataset = <unbound>
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 *nodep = NULL
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 return
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we're here, then we've got a node and are now trying to find
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 an active rdataset of the desired type, or, in the case of an ANY
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 query, any active rdataset.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If we're beneath a zone cut
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 cname_ok = no
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If the caller wants us to validate glue, then see if the
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 current name is a valid glue name for the ZC.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If not,
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 result = DNS_R_DELEGATION;
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = ZC name
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 *nodep = ZC
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 rdataset = NS
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 return
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If the desired type is KEY, SIG, or NXT, then
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 cname_ok = no
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 foundname = current node name
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 *nodep = current node;
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 Search the rdataset list for the desired type. If cname_ok, also
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 look for a CNAME rdataset. While searching, remember the active NXT
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 rdataset if we come across it. We must also determine if there are
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 any active rdatasets at the node.
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 If there are no active rdatasets at the node, then we've got an
c528bd698637d84a0081d26a58813607c7f52bb7Tatuya JINMEI 神明達哉 exact name match, but the name doesn't exist in the desired version.
5597be9bb88de138dfec9fa9176708443813925eTatuya JINMEI 神明達哉 This means we really have a partial match. Goto Partial_Match.
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'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
We have found the type we were looking for or we've found a CNAME.
If we're not doing any ANY query, didn't find the type we were looking
for, but did find a CNAME
result = DNS_R_CNAME
rdataset = CNAME
Else If we're beneath a zone cut
result = DNS_R_GLUE
Else
result = DNS_R_SUCCESS
If type is ANY
rdataset = <unbound>
else
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).