resolver revision c43deb8aacb70124a8016f408c64b80d4c019b68
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonCopyright (C) 1999, 2000 Internet Software Consortium.
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian WellingtonSee COPYRIGHT in the source root or http://www.isc.org/copyright for terms.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews$Id: resolver,v 1.3 2000/07/04 01:24:06 tale Exp $
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian WellingtonMulti-target Resolver
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian Wellington=====================
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian WellingtonDue to IPv6 and other multiple-path resolving needs, the resolver in
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian WellingtonBIND 9 needs to be able to handle more than one simulaneous resolving
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrewstask for any single request.
dafcb997e390efa4423883dafd100c975c4095d6Mark AndrewsFor instance, following an A6 chain could result in multiple "forks"
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrewsfor each network providor.
dafcb997e390efa4423883dafd100c975c4095d6Mark AndrewsResolver Overview
d4ef65050feac78554addf6e16a06c6e2e0bd331Brian Wellington=================
6e8a8077faf96d8da0b6cf738913f5f1f86e4008Mark AndrewsThe resolver core is divided into several parts, each of which has a
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonfairly simple function (with some exceptions) to simplify the problem.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThe most complicated portion is the search algorithm "state machine."
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonFlow of a Request
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellington-----------------
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonQuery Management.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonEach query is associated with a given view. The view-based management
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonallows different clients to be provided with different data based on
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonadministrative requirements.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThis is also the layer where EDNS is handled first. EDNS knowledge is
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonhandled in some ways throughout the resolver, but several constraints
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonneed to be handled if the receiving client cannot handle the EDNS
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonformat. (XXX need more)
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonWhen a client (caller) issues a query, the first thing that happens is
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonthe list of currently outstanding queries is checked. If another query
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonis already being processed for another client, the new request
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonattaches to the running query and shares the result when it
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonIf no outstanding requests for this query exist, a new query context
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark Andrewsis created and an event is passed to an internal "resolver task" for
50105afc551903541608b11851d73278b23579a3Mark AndrewsIn either case, when the internal resolver task completes the request
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonthe waiting clients are sent an event. Note that the calling clients
6e8a8077faf96d8da0b6cf738913f5f1f86e4008Mark Andrewscan remove their request for various reasons, such as a timeout. The
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtoninternal task will continue to work on the request, however. This
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonwill let other clients attach to a query that some work was done for,
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonand it will help to populate the cache in hopes this query will be
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonCalling into the resolver may cause the currently running task to do
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonsome amount of work, rather than handing off to an internal task
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark Andrewsimmediately. This is more efficient (fewer context switches) but the
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonclient's task will not be blocked for any long-term purposes.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThe query management layer is also used for internal queries, from the
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonsearch algorithm state machine. In this case, the "client" is an
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtoninternal resolver task, and all callbacks are within the resolver
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThe next stage in the resolving process is the search algorithm state
cc3aafe737334d444781f8a34ffaf459e075bb9aMark AndrewsSearch Algorithm State Machine.
cc3aafe737334d444781f8a34ffaf459e075bb9aMark AndrewsThis is where the guts of the resolving takes place. The cache is
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonconsulted for an answer, and if deemed good, returned. The
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonauthoritative data is also consulted here.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonMany internal queries may be launched to perform recursive queries on
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonbehalf of clients or the resolver itself. The algorithm is described
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThe output of this stage is either to return to query management with
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonan answer, or to move to the address selection phase.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonAddress Selection.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonGiven that the resolver may have a forwarder list, or may have a
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonnumber of possible IP addresses to consult for more information, some
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonselection of which is the best address to use needs to be performed.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThis layer does this.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonIt will select from a possible set of IP addresses to send a query
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonto. They are ranked in various ways (round-trip time, reliability,
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonand lameness for a given zone are a few) and the best is selected.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonSome state is maintained to allow retransmission in the case of a
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonThe output of this goes to message formatting.
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark AndrewsMessage Formatting.
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark AndrewsThis section will construct a wire message to perform a query.
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark AndrewsThe output of this section is what is transmitted to the wire in the
b0c15bd9792112fb47f6d956e580e4369e92f4e7Mark Andrewsexternal DNS query section.
50105afc551903541608b11851d73278b23579a3Mark AndrewsExternal DNS Query.
50105afc551903541608b11851d73278b23579a3Mark AndrewsThis is where a wire message is transmitted to the "best" socket
50105afc551903541608b11851d73278b23579a3Mark Andrewsaddress. Timeouts are handled here, and timing information is
50105afc551903541608b11851d73278b23579a3Mark Andrewsgathered when requests complete.
50105afc551903541608b11851d73278b23579a3Mark AndrewsReceived Message Handling.
50105afc551903541608b11851d73278b23579a3Mark AndrewsWhen a message arrives from an internal query, the result is evaluated
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonhere. Things like message ID matching the query, query answers
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonquestion, TSIG, DNSSEC, etc are performed here.
cc3aafe737334d444781f8a34ffaf459e075bb9aMark AndrewsCaching and Evaluation of Result.
0b062f4990db5cc6db2fe3398926f71b92a67407Brian WellingtonOnce the message format and envelope are examined, some bits are
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtoncached (including hints that a given rrset has a zero TTL). Other
0b062f4990db5cc6db2fe3398926f71b92a67407Brian Wellingtonbits feed back into the search algorithm state machine to continue
bf7f253e306d0ced8ae24d7a0598773950da11f4Mark Andrews[ XXX need examples? ]