resolver revision 499b34cea04a46823d003d4c0520c8b03e8513cb
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaCopyright (C) 1999-2001 Internet Software Consortium.
ce8d7a0627c0f246376cccd980463f8250a6a97ebjhSee COPYRIGHT in the source root or http://isc.org/copyright.html for terms.
6ded37e63424e43b00ca7c9055d355e071d6a444rbb$Id: resolver,v 1.5 2001/01/09 21:46:52 bwelling Exp $
9022fa73d4ac101553e7c36a1457ead52a73333borlikowskiMulti-target Resolver
9022fa73d4ac101553e7c36a1457ead52a73333borlikowski=====================
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaDue to IPv6 and other multiple-path resolving needs, the resolver in
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaBIND 9 needs to be able to handle more than one simulaneous resolving
6ca0e6973c8176100f4a426444823ae5e777e28fsaschatask for any single request.
a3658aa5c00f07bf898d46fdddae880c52424872saschaFor instance, following an A6 chain could result in multiple "forks"
6687a315a676cbcb8063a8477a579876d82ab327gsteinfor each network providor.
5f69f46ccdf50afd8f0a23f134746e6066185e89rbbResolver Overview
0b483bc2a16712efe6aa95e06a57ec2c1cb956c7sascha=================
150d51d42d77924d8b84d2f34299fb5ffc952679rbbThe resolver core is divided into several parts, each of which has a
9832ee60b23ca2a3faa403bbe88720815969a9fefieldingfairly simple function (with some exceptions) to simplify the problem.
9832ee60b23ca2a3faa403bbe88720815969a9fefieldingThe most complicated portion is the search algorithm "state machine."
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaFlow of a Request
2795c373a9fb112dc77576c1dfc23119f02d598amanoj-----------------
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaQuery Management.
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaEach query is associated with a given view. The view-based management
7bfe076b680e6e591add6cdc754ce9a6910682a2saschaallows different clients to be provided with different data based on
e87c4996d79ea15965d675b90c6e718369b58c3arbbadministrative requirements.
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaThis is also the layer where EDNS is handled first. EDNS knowledge is
6ca0e6973c8176100f4a426444823ae5e777e28fsaschahandled in some ways throughout the resolver, but several constraints
e87c4996d79ea15965d675b90c6e718369b58c3arbbneed to be handled if the receiving client cannot handle the EDNS
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaformat. (XXX need more)
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaWhen a client (caller) issues a query, the first thing that happens is
6ca0e6973c8176100f4a426444823ae5e777e28fsaschathe list of currently outstanding queries is checked. If another query
e87c4996d79ea15965d675b90c6e718369b58c3arbbis already being processed for another client, the new request
46a06e5f359747d9b673ea77fcef89a851192e18rbbattaches to the running query and shares the result when it
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaIf no outstanding requests for this query exist, a new query context
6ca0e6973c8176100f4a426444823ae5e777e28fsaschais created and an event is passed to an internal "resolver task" for
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaIn either case, when the internal resolver task completes the request
e87c4996d79ea15965d675b90c6e718369b58c3arbbthe waiting clients are sent an event. Note that the calling clients
de2aecd8da21eeae4394088cca196dfcb491de84rbbcan remove their request for various reasons, such as a timeout. The
e9daa0fae0dc3382ad7497e548d89ff8b8ece9e8beninternal task will continue to work on the request, however. This
26d4668b602c703d63655271b1caaa420bf7a572rbbwill let other clients attach to a query that some work was done for,
c42624831a198453add77c4040ffdb490ae354f5orlikowskiand it will help to populate the cache in hopes this query will be
759f4a24d09e28c4eaca9f97311b497fc15cb5c7benCalling into the resolver may cause the currently running task to do
759f4a24d09e28c4eaca9f97311b497fc15cb5c7bensome amount of work, rather than handing off to an internal task
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaimmediately. This is more efficient (fewer context switches) but the
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaclient's task will not be blocked for any long-term purposes.
f2bf28198a285815ec536b7e370629bb68a0bb17rbbThe query management layer is also used for internal queries, from the
e92413835484581e88cfcda16f5c6615d2544614rbbsearch algorithm state machine. In this case, the "client" is an
f2bf28198a285815ec536b7e370629bb68a0bb17rbbinternal resolver task, and all callbacks are within the resolver
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaThe next stage in the resolving process is the search algorithm state
f2bf28198a285815ec536b7e370629bb68a0bb17rbbSearch Algorithm State Machine.
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaThis is where the guts of the resolving takes place. The cache is
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaconsulted for an answer, and if deemed good, returned. The
7bfe076b680e6e591add6cdc754ce9a6910682a2saschaauthoritative data is also consulted here.
f2bf28198a285815ec536b7e370629bb68a0bb17rbbMany internal queries may be launched to perform recursive queries on
2a67190265146d3e80b1b0c9ef04f181c8db7f64rbbbehalf of clients or the resolver itself. The algorithm is described
7bfe076b680e6e591add6cdc754ce9a6910682a2saschaThe output of this stage is either to return to query management with
87193a6150fcb830b68d79fdbb3f068cb3724677saschaan answer, or to move to the address selection phase.
87193a6150fcb830b68d79fdbb3f068cb3724677saschaAddress Selection.
87193a6150fcb830b68d79fdbb3f068cb3724677saschaGiven that the resolver may have a forwarder list, or may have a
26f3a893a0221238d498d03cc19c11c0373f61d6rbbnumber of possible IP addresses to consult for more information, some
26f3a893a0221238d498d03cc19c11c0373f61d6rbbselection of which is the best address to use needs to be performed.
f8bdb98352f4ed1a5dba2471bc9486ef26d2ceberbbThis layer does this.
f8bdb98352f4ed1a5dba2471bc9486ef26d2ceberbbIt will select from a possible set of IP addresses to send a query
f8bdb98352f4ed1a5dba2471bc9486ef26d2ceberbbto. They are ranked in various ways (round-trip time, reliability,
f8bdb98352f4ed1a5dba2471bc9486ef26d2ceberbband lameness for a given zone are a few) and the best is selected.
0b483bc2a16712efe6aa95e06a57ec2c1cb956c7saschaSome state is maintained to allow retransmission in the case of a
6cb7893a671cebe32dd0455ba79781a4834e141egregamesThe output of this goes to message formatting.
6cb7893a671cebe32dd0455ba79781a4834e141egregamesMessage Formatting.
6cb7893a671cebe32dd0455ba79781a4834e141egregamesThis section will construct a wire message to perform a query.
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaThe output of this section is what is transmitted to the wire in the
6ca0e6973c8176100f4a426444823ae5e777e28fsaschaexternal DNS query section.
bbd84c2a95afbca61ef7897e2fb8e897e4682f9drbbExternal DNS Query.
156e4036ec6e4b5d858025a1af72403c0eb15d9adreidThis is where a wire message is transmitted to the "best" socket
156e4036ec6e4b5d858025a1af72403c0eb15d9adreidaddress. Timeouts are handled here, and timing information is
1e8d4cfede0bad3a1a33e3b2eef0ba6754746f72rbbgathered when requests complete.
7e73041858979fd162c849cc2e7447beb51eedf8rbbReceived Message Handling.
7e73041858979fd162c849cc2e7447beb51eedf8rbbWhen a message arrives from an internal query, the result is evaluated
1e8d4cfede0bad3a1a33e3b2eef0ba6754746f72rbbhere. Things like message ID matching the query, query answers
7e73041858979fd162c849cc2e7447beb51eedf8rbbquestion, TSIG, DNSSEC, etc are performed here.
150d51d42d77924d8b84d2f34299fb5ffc952679rbbCaching and Evaluation of Result.
e50587e6b2ff25bdcbe29410be5bf8f4792016eegregamesOnce the message format and envelope are examined, some bits are
b04af690135a10f6a03ecdc208b0db7f106e4ca2gregamescached (including hints that a given rrset has a zero TTL). Other
150d51d42d77924d8b84d2f34299fb5ffc952679rbbbits feed back into the search algorithm state machine to continue
150d51d42d77924d8b84d2f34299fb5ffc952679rbbprocessing.
ce8d7a0627c0f246376cccd980463f8250a6a97ebjh[ XXX need examples? ]