resolver revision c43deb8aacb70124a8016f408c64b80d4c019b68
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark AndrewsCopyright (C) 1999, 2000 Internet Software Consortium.
ddccd5811feff696ba460dabfb666ce61040f545Andreas GustafssonSee COPYRIGHT in the source root or http://www.isc.org/copyright for terms.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein$Id: resolver,v 1.3 2000/07/04 01:24:06 tale Exp $
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox UserMulti-target Resolver
5347c0fcb04eaea19d9f39795646239f487c6207Tinderbox User=====================
ddccd5811feff696ba460dabfb666ce61040f545Andreas GustafssonDue to IPv6 and other multiple-path resolving needs, the resolver in
d6fa26d0adaec6c910115be34fe7a5a5f402c14fMark AndrewsBIND 9 needs to be able to handle more than one simulaneous resolving
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeintask for any single request.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinFor instance, following an A6 chain could result in multiple "forks"
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox Userfor each network providor.
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox UserResolver Overview
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox User=================
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThe resolver core is divided into several parts, each of which has a
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userfairly simple function (with some exceptions) to simplify the problem.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThe most complicated portion is the search algorithm "state machine."
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserFlow of a Request
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein-----------------
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserQuery Management.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserEach query is associated with a given view. The view-based management
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userallows different clients to be provided with different data based on
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Useradministrative requirements.
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserThis is also the layer where EDNS is handled first. EDNS knowledge is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userhandled in some ways throughout the resolver, but several constraints
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinneed to be handled if the receiving client cannot handle the EDNS
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userformat. (XXX need more)
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinWhen a client (caller) issues a query, the first thing that happens is
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Userthe list of currently outstanding queries is checked. If another query
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox Useris already being processed for another client, the new request
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinattaches to the running query and shares the result when it
7911e6f9de303bca5a3d8b34f4330c8f7cecffaeTinderbox UserIf no outstanding requests for this query exist, a new query context
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox Useris created and an event is passed to an internal "resolver task" for
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinIn either case, when the internal resolver task completes the request
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinthe waiting clients are sent an event. Note that the calling clients
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeincan remove their request for various reasons, such as a timeout. The
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox Userinternal task will continue to work on the request, however. This
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinwill let other clients attach to a query that some work was done for,
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinand it will help to populate the cache in hopes this query will be
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCalling into the resolver may cause the currently running task to do
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinsome amount of work, rather than handing off to an internal task
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinimmediately. This is more efficient (fewer context switches) but the
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox Userclient's task will not be blocked for any long-term purposes.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe query management layer is also used for internal queries, from the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinsearch algorithm state machine. In this case, the "client" is an
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox Userinternal resolver task, and all callbacks are within the resolver
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox UserThe next stage in the resolving process is the search algorithm state
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinSearch Algorithm State Machine.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThis is where the guts of the resolving takes place. The cache is
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinconsulted for an answer, and if deemed good, returned. The
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox Userauthoritative data is also consulted here.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinMany internal queries may be launched to perform recursive queries on
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinbehalf of clients or the resolver itself. The algorithm is described
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this stage is either to return to query management with
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinan answer, or to move to the address selection phase.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinAddress Selection.
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox UserGiven that the resolver may have a forwarder list, or may have a
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinnumber of possible IP addresses to consult for more information, some
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinselection of which is the best address to use needs to be performed.
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox UserThis layer does this.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinIt will select from a possible set of IP addresses to send a query
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinto. They are ranked in various ways (round-trip time, reliability,
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinand lameness for a given zone are a few) and the best is selected.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinSome state is maintained to allow retransmission in the case of a
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this goes to message formatting.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinMessage Formatting.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThis section will construct a wire message to perform a query.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinThe output of this section is what is transmitted to the wire in the
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinexternal DNS query section.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinExternal DNS Query.
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox UserThis is where a wire message is transmitted to the "best" socket
fd2597f75693a2279fdf588bd40dfe2407c42028Tinderbox Useraddress. Timeouts are handled here, and timing information is
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeingathered when requests complete.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinReceived Message Handling.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinWhen a message arrives from an internal query, the result is evaluated
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinhere. Things like message ID matching the query, query answers
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinquestion, TSIG, DNSSEC, etc are performed here.
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob AusteinCaching and Evaluation of Result.
2eeb74d1cf5355dd98f6d507a10086e16bb08c4bTinderbox UserOnce the message format and envelope are examined, some bits are
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeincached (including hints that a given rrset has a zero TTL). Other
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austeinbits feed back into the search algorithm state machine to continue
60e5e10f8d2e2b0c41e8abad38cacd867caa6ab2Rob Austein[ XXX need examples? ]