search revision 9c3531d72aeaad6c5f01efe6a1c82023e1379e4d
5cd4555ad444fd391002ae32450572054369fd42Rob AusteinCopyright (C) 1999, 2000 Internet Software Consortium.
5cd4555ad444fd391002ae32450572054369fd42Rob AusteinSee COPYRIGHT in the source root or http://www.isc.org/copyright for terms.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley$Id: search,v 1.6 2000/06/22 21:53:58 tale Exp $
dafcb997e390efa4423883dafd100c975c4095d6Mark AndrewsWhat follows is pseudocode for the zone and cache lookup algorithms, as they
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleywill work in the RBT DB.
dd750c560ae48cf6caeb9a9fe81d33fc4746106dBrian WellingtonNote: These algorithms differ in some respects from those discussed in
dd750c560ae48cf6caeb9a9fe81d33fc4746106dBrian Wellingtonthe RFCs and drafts. I believe these algorithms provide better
dd750c560ae48cf6caeb9a9fe81d33fc4746106dBrian Wellingtonanswers in some cases.
dafcb997e390efa4423883dafd100c975c4095d6Mark AndrewsPreliminary Stuff
dafcb997e390efa4423883dafd100c975c4095d6Mark AndrewsBIND 9 zone databases are versioned, and every search is done in the
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrewscontext of some version. There are a number of ways of implementing
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrewsversioning. The method that's going to be used in the RBT DB is to
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleystore a serial number with every rdataset. All rdatasets added as the
f5d30e2864e048a42c4dc1134993ae7efdb5d6c3Mark Andrewsresult of a single database update have the same serial number. This
2fd58cb8f17e8d268650ae05c2bba94eaf7c7217Automatic Updaterserial number is not related to the SOA serial, since the SOA serial
b5ad6dfea4cc3e7d1d322ac99f1e5a31096837c4Mark Andrewsis under user control and can do weird things. The database serial
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleynumber is a monotonically increasing value. When you go to retrieve
5d924e398ed15c57c506315c7d11125dcc9cb098Jeremy Reedan rdataset, you may encounter many rdatasets of that type at any
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleygiven node. The correct one to return, called the "active rdataset",
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleyhas the greatest serial number less than or equal to the serial number
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleyused for the search. The version whose serial number is being used in
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleythe search is the "target version".
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob HalleyCache databases are not versioned. A search will always return the
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleymost recent value.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob HalleyDKZC == Deepest Known Zone Cut. This is the zone cut closest to the
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleydesired name. In a zone, it's either a delegation out of authoritative
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleydata, or it's the top of the zone.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob HalleyZC == "zone cut", a node not at the zone top which has an active NS
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinrdataset, or a node (including the zone top) with an active DNAME
d6b5e0b0e8a4e3e927f8d47ca82c3e7f42e0f4bbMark AndrewsZone Search Algorithm
2fd58cb8f17e8d268650ae05c2bba94eaf7c7217Automatic Updater Search rdata type (including ANY)
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Search options
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein The search options parameter is a flags variable. Current
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Glue OK If set, then the caller is
f5d30e2864e048a42c4dc1134993ae7efdb5d6c3Mark Andrews wants best match results for
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein the search name, even if it's
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein glue. If not set, the caller
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein will get a delegation if the
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley search name is glue.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Glue Validation Section 7.18 of RFC 2136
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews requires that certain data that
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews is not in the zone and is not
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley glue remain stored in the zone.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley A search can never return this
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont data, but there might be glue
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley mixed in with it. Telling glue
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley from non glue involves some
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews work, especially since the
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley database is versioned. Often,
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley however, the caller will know
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley the name it's looking for is
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 glue, so validation isn't
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley the name of the node
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley rdataset (not bound if querying for ANY)
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Note: The node, name, and rdataset are optional. If the
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley caller doesn't care about them, they won't be set.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Note: there is no EDNS1 "longest match" support in the algorithm yet,
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein though I know how to do it.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley cname_ok = yes
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley search_must_succeed = no
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Search down from the root of the tree. If, while going down, we
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein encounter a zone cut node, then search the rdatasets at the zone
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein cut for active DNAME or NS rdatasets. Note that if we find both
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein an active DNAME rdataset and an active NS rdataset, then the DNAME
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley rdataset has precedence.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley If we found an active DNAME rdataset, the search ends here.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley result = DNS_R_DNAME
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley foundname = name of this node
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley *nodep = this node
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley rdataset is the DNAME
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we found an active NS rdataset
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If finding glue is not OK, or we're not searching for
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein a glue type, then the search ends here.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein result = DNS_R_DELEGATION
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein foundname = name of this node
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews *nodep = this node
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = NS
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews We remember that this node is the ZC.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein We remember this node's name.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein We'll ignore any zone cuts found further down
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Continue the search down.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Partial_Match:
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews If we don't have an exact match to the name
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we're below a zone cut, then we need to return a referral.
0ffaee887ff5674b8c3bb0435ae838f641981706Mark Andrews result = DNS_R_DELEGATION;
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont foundname = ZC name
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = NS
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Else If this zone has any wildcards, then
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Go looking for a wildcard match for this name.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we found one,
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein result = DNS_R_WILDCARD
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein foundname = wildcard node name
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Fall through to searching the wildcard node
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein for the desired type.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein NXDOMAIN (finally!)
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If this is a secure zone then
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Find the greatest predecessor to this node
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein that has at least one active rdataset.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Change the type we're search for to NXT
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley cname_ok = no
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley search_must_succeed = yes
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein result = DNS_R_NXDOMAIN
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein foundname = <empty>
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = <unbound>
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein *nodep = NULL
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we're here, then we've got a node and are now trying to find
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley an active rdataset of the desired type, or, in the case of an ANY
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley query, any active rdataset.
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont If we're beneath a zone cut
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont cname_ok = no
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont If the caller wants us to validate glue, then see if the
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont current name is a valid glue name for the ZC.
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont result = DNS_R_DELEGATION;
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont foundname = ZC name
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont rdataset = NS
8b78c993cb475cc94e88560941b28c37684789d9Francis Dupont If the desired type is KEY, SIG, or NXT, then
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley cname_ok = no
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein foundname = current node name
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein *nodep = current node;
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Search the rdataset list for the desired type. If cname_ok, also
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein look for a CNAME rdataset. While searching, remember the active NXT
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley rdataset if we come across it. We must also determine if there are
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley any active rdatasets at the node.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If there are no active rdatasets at the node, then we've got an
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein exact name match, but the name doesn't exist in the desired version.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein This means we really have a partial match. Goto Partial_Match.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we didn't find the type we were looking for (including a failed
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If (search_must_succeed), then
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley The database is bad, e.g. missing NXT records.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley result = DNS_R_BADDB
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews *nodep = NULL
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews foundname = <empty>
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews Else if we're beneath a zone cut
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews result = DNS_R_DELEGATION
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews foundname = ZC name
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews rdataset = NS
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews result = DNS_R_NXRDATASET
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews If this is a secure zone then
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews If we found an active NXT rdataset
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews rdataset = NXT rdataset
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews result = DNS_R_BADDB
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews *nodep = NULL
0f78f780648806bcb3e374b7dafac73e6c558ea8Mark Andrews foundname = <empty>
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = <unbound>
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein We have found the type we were looking for or we've found a CNAME.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we're not doing any ANY query, didn't find the type we were looking
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein for, but did find a CNAME
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein result = DNS_R_CNAME
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = CNAME
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Else If we're beneath a zone cut
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein result = DNS_R_GLUE
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley result = DNS_R_SUCCESS
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If type is ANY
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = <unbound>
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein rdataset = the type we were looking for
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob HalleyXXX This is now old XXX
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob HalleyNow for the cache lookup algorithm, which is a little different. The
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeincache algorithm takes an optional "zone DKZC". Say a server is
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinauthoritative for vix.com but not rc.vix.com. When it looks up
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinbb.rc.vix.com it will search vix.com and discover the delegation to
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinrc.vix.com. We then want to look in the cache for bb.rc.vix.com, and
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halleyif we don't find it, the authoritative delegation might be the best
268a4475065fe6a8cd7cc707820982cf5e98f430Rob AusteinDKZC (since there might not be anything for rc.vix.com in the cache),
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinso that's why we allow it to be an argument to the cache search
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeinalgorithm. Of course, the cache might have data for rc.vix.com
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austeincached, in which case we should use it and not the DKZC.
268a4475065fe6a8cd7cc707820982cf5e98f430Rob AusteinDKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉Cache Search Algorithm:
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Go down as far as possible remembering every parent node.
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Remember the predecessor too.
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 If some rdataset for name exists
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Look for desired type or CNAME
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 If negative cache entry
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Indicate this and return.
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Indicate it and return.
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Indicate we know nothing about this type at this
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 (Peek at predecessor to see if it has an NXT for the same
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 zone and which covers the QNAME. If so, return it.)
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 Go up until we find a node with a DNAME or a zone cut.
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 XXX DNAME draft says go up until you prove that there are no
13d9b8ce94aee267761cd297a583e280df262d60Tatuya JINMEI 神明達哉 ancestor DNAMEs at all XXX
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If there's a DNAME
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Return a DNAME result with the dname node and node name
561a29af8c54a216e7d30b5b4f6e0d21661654ecMark Andrews XXX what if the zone DKZC is better (i.e. deeper)? XXX
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein We know nothing about this name.
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley XXX DNAME draft says that if we have a zone DKZC, we should
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein use it now. I say use the best DKZC you've got. XXX
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we get all the way to '.' and we don't even have the
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein root NS records
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein If we have a DKZC from authoritative data
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein Return NO_KNOWN_AUTHORITY
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein (this will cause priming of root servers or,
268a4475065fe6a8cd7cc707820982cf5e98f430Rob Austein perhaps, forwarding)
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley If we have a zone DKZC and it's better than the one we found
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley in the cache
6ea1b817e31b89a627e146fe69e23ea0a64c89ecBob Halley Return it (node and name).
5d23a6ac8392b1eeec8effdee47fb725ace1e759Evan Hunt Return the cache DKZC (node and name).