10139N/ACopyright (C) 1999, 2000 Internet Software Consortium.
12282N/A$Id: search,v 1.8 2000/08/09 04:37:26 tale Exp $
10139N/AWhat follows is pseudocode for the zone and cache lookup algorithms, as they
10139N/ANote: These algorithms differ in some respects from those discussed in
17178N/Athe RFCs and drafts. I believe these algorithms provide better
12282N/ABIND 9 zone databases are versioned, and every search is done in the
10139N/Acontext of some version. There are a number of ways of implementing
10139N/Aversioning. The method that's going to be used in the RBT DB is to
10139N/Astore a serial number with every rdataset. All rdatasets added as the
10139N/Aresult of a single database update have the same serial number. This
10139N/Aserial number is not related to the SOA serial, since the SOA serial
10139N/Ais under user control and can do weird things. The database serial
12773N/Anumber is a monotonically increasing value. When you go to retrieve
15694N/Aan rdataset, you may encounter many rdatasets of that type at any
12773N/Agiven node. The correct one to return, called the "active rdataset",
13483N/Ahas the greatest serial number less than or equal to the serial number
10139N/Aused for the search. The version whose serial number is being used in
10139N/Athe search is the "target version".
10139N/ACache databases are not versioned. A search will always return the
10139N/ADKZC == Deepest Known Zone Cut. This is the zone cut closest to the
10139N/Adesired name. In a zone, it's either a delegation out of authoritative
10139N/Adata, or it's the top of the zone.
10139N/AZC == "zone cut", a node not at the zone top which has an active NS
10139N/Ardataset, or a node (including the zone top) with an active DNAME
10139N/A Search rdata type (including ANY)
10139N/A The search options parameter is a flags variable. Current
10139N/A Glue OK If set, then the caller is
10139N/A Glue Validation Section 7.18 of RFC 2136
10139N/A requires that certain data that
10139N/A glue remain stored in the zone.
10139N/A rdataset (not bound if querying for ANY)
10139N/A Note: The node, name, and rdataset are optional. If the
10139N/A caller doesn't care about them, they won't be set.
10139N/A Note: there is no EDNS1 "longest match" support in the algorithm yet,
12773N/A Search down from the root of the tree. If, while going down, we
12773N/A encounter a zone cut node, then search the rdatasets at the zone
12773N/A cut for active DNAME or NS rdatasets. Note that if we find both
12773N/A an active DNAME rdataset and an active NS rdataset, then the DNAME
10139N/A If we found an active DNAME rdataset, the search ends here.
10139N/A If we found an active NS rdataset
10139N/A If finding glue is not OK, or we're not searching for
10139N/A a glue type, then the search ends here.
10139N/A We remember that this node is the ZC.
10139N/A We'll ignore any zone cuts found further down
10139N/A If we don't have an exact match to the name
10139N/A If we're below a zone cut, then we need to return a referral.
10139N/A Else If this zone has any wildcards, then
10139N/A Go looking for a wildcard match for this name.
10139N/A Fall through to searching the wildcard node
10139N/A Find the greatest predecessor to this node
10139N/A that has at least one active rdataset.
10139N/A Change the type we're search for to NXT
10139N/A If we're here, then we've got a node and are now trying to find
10139N/A an active rdataset of the desired type, or, in the case of an ANY
16697N/A If the caller wants us to validate glue, then see if the
16697N/A current name is a valid glue name for the ZC.
15694N/A If the desired type is KEY, SIG, or NXT, then
13468N/A Search the rdataset list for the desired type. If cname_ok, also
13445N/A look for a CNAME rdataset. While searching, remember the active NXT
13445N/A rdataset if we come across it. We must also determine if there are
12793N/A any active rdatasets at the node.
12628N/A If there are no active rdatasets at the node, then we've got an
12628N/A exact name match, but the name doesn't exist in the desired version.
12436N/A This means we really have a partial match. Goto Partial_Match.
12304N/A If we didn't find the type we were looking for (including a failed
11010N/A Else if we're beneath a zone cut
10344N/A If we found an active NXT rdataset
10139N/A We have found the type we were looking for or we've found a CNAME.
10139N/A If we're not doing any ANY query, didn't find the type we were looking
10139N/A Else If we're beneath a zone cut
10139N/A rdataset = the type we were looking for
10139N/ANow for the cache lookup algorithm, which is a little different. The
10139N/Acache algorithm takes an optional "zone DKZC". Say a server is
10139N/Aif we don't find it, the authoritative delegation might be the best
10139N/Aso that's why we allow it to be an argument to the cache search
10139N/Acached, in which case we should use it and not the DKZC.
10139N/ADKZC A is "better" than DKZC B if DKZC A is a proper subdomain of DKZC
10139N/A Go down as far as possible remembering every parent node.
10139N/A If some rdataset for name exists
10139N/A Indicate we know nothing about this type at this
10139N/A (Peek at predecessor to see if it has an NXT for the same
10139N/A zone and which covers the QNAME. If so, return it.)
10139N/A Go up until we find a node with a DNAME or a zone cut.
10139N/A XXX DNAME draft says go up until you prove that there are no
10139N/A Return a DNAME result with the dname node and node name
10139N/A XXX what if the zone DKZC is better (
i.e. deeper)? XXX
10139N/A We know nothing about this name.
10139N/A XXX DNAME draft says that if we have a zone DKZC, we should
10139N/A use it now. I say use the best DKZC you've got. XXX
10139N/A If we get all the way to '.' and we don't even have the
10139N/A If we have a DKZC from authoritative data
10139N/A (this will cause priming of root servers or,
10139N/A If we have a zone DKZC and it's better than the one we found
10139N/A Return the cache DKZC (node and name).