resolver.c

/*
 * Copyright (C) 1999  Internet Software Consortium.
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
 * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 * SOFTWARE.
 */

#include <config.h>

#include <isc/assertions.h>
#include <isc/boolean.h>
#include <isc/error.h>
#include <isc/result.h>
#include <isc/timer.h>
#include <isc/mutex.h>
#include <isc/event.h>
#include <isc/task.h>
#include <isc/stdtime.h>

#include <dns/types.h>
#include <dns/adb.h>
#include <dns/result.h>
#include <dns/name.h>
#include <dns/db.h>
#include <dns/events.h>
#include <dns/message.h>
#include <dns/ncache.h>
#include <dns/dispatch.h>
#include <dns/resolver.h>
#include <dns/rdata.h>
#include <dns/rdataset.h>
#include <dns/tsig.h>
#include <dns/view.h>
#include <dns/log.h>

#include <dst/dst.h>

#include "../isc/util.h"		/* XXX */

#define DNS_RESOLVER_TRACE
#ifdef DNS_RESOLVER_TRACE
#define RTRACE(m)	isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_RESOLVER, \
				      DNS_LOGMODULE_RESOLVER, \
				      ISC_LOG_DEBUG(3), \
				      "res %p: %s", res, (m))
#define RRTRACE(r, m)	isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_RESOLVER, \
				      DNS_LOGMODULE_RESOLVER, \
				      ISC_LOG_DEBUG(3), \
				      "res %p: %s", (r), (m))
#define FCTXTRACE(m)	isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_RESOLVER, \
				      DNS_LOGMODULE_RESOLVER, \
				      ISC_LOG_DEBUG(3), \
				      "fctx %p: %s", fctx, (m))
#define FTRACE(m)	isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_RESOLVER, \
				      DNS_LOGMODULE_RESOLVER, \
				      ISC_LOG_DEBUG(3), \
				      "fetch %p (fctx %p): %s", \
				      fetch, fetch->private, (m))
#define QTRACE(m)	isc_log_write(dns_lctx, \
				      DNS_LOGCATEGORY_RESOLVER, \
				      DNS_LOGMODULE_RESOLVER, \
				      ISC_LOG_DEBUG(3), \
				      "resquery %p (fctx %p): %s", \
				      query, query->fctx, (m))
#else
#define RTRACE(m)
#define RRTRACE(r, m)
#define FCTXTRACE(m)
#define FTRACE(m)
#define QTRACE(m)
#endif


typedef struct fetchctx fetchctx_t;

typedef struct query {
	/* Not locked. */
	unsigned int			magic;
	fetchctx_t *			fctx;
	dns_dispatch_t *		dispatch;
	/* Locked by fctx lock. */
	dns_messageid_t			id;
	dns_dispentry_t *		dispentry;	/* XXX name */
	ISC_LINK(struct query)		link;
	isc_buffer_t			buffer;
	dns_rdata_any_tsig_t		*tsig;
	dns_tsigkey_t			*tsigkey;
	unsigned char			data[512];
} resquery_t;

#define QUERY_MAGIC			0x51212121U	/* Q!!! */
#define VALID_QUERY(query)		((query) != NULL && \
					 (query)->magic == QUERY_MAGIC)

typedef enum {
	fetchstate_init = 0,
	fetchstate_active,
	fetchstate_done
} fetchstate;

struct fetchctx {
	/* Not locked. */
	unsigned int			magic;
	dns_resolver_t *		res;
	dns_name_t			name;
	dns_rdatatype_t			type;
	unsigned int			options;
	isc_task_t *			task;
	unsigned int			bucketnum;
	/* Locked by lock. */
	fetchstate			state;
	isc_boolean_t			want_shutdown;
	unsigned int			references;
	isc_event_t			control_event;
	ISC_LINK(struct fetchctx)	link;
	ISC_LIST(dns_fetchevent_t)	events;
	/* Only changable by event actions running in the context's task */
	dns_name_t			domain;
	dns_rdataset_t			nameservers;
	unsigned int			attributes;
	isc_timer_t *			timer;
	isc_time_t			expires;
	isc_interval_t			interval;
	dns_message_t *			qmessage;
	dns_message_t *			rmessage;
	ISC_LIST(resquery_t)		queries;
	ISC_LIST(dns_adbfind_t)		finds;
	dns_adbfind_t *			find;
	unsigned int			pending;
};

#define FCTX_MAGIC			0x46212121U	/* F!!! */
#define VALID_FCTX(fctx)		((fctx) != NULL && \
					 (fctx)->magic == FCTX_MAGIC)

#define FCTX_ATTR_HAVEANSWER		0x01
#define FCTX_ATTR_GLUING		0x02
#define FCTX_ATTR_ADDRWAIT		0x04
#define FCTX_ATTR_SHUTTINGDOWN		0x08
#define FCTX_ATTR_WANTCACHE		0x10
#define FCTX_ATTR_WANTNCACHE		0x20

#define HAVE_ANSWER(f)		(((f)->attributes & FCTX_ATTR_HAVEANSWER) != \
				 0)
#define GLUING(f)		(((f)->attributes & FCTX_ATTR_GLUING) != \
				 0)
#define ADDRWAIT(f)		(((f)->attributes & FCTX_ATTR_ADDRWAIT) != \
				 0)
#define SHUTTINGDOWN(f)		(((f)->attributes & FCTX_ATTR_SHUTTINGDOWN) \
 				 != 0)
#define WANTCACHE(f)		(((f)->attributes & FCTX_ATTR_WANTCACHE) != 0)
#define WANTNCACHE(f)		(((f)->attributes & FCTX_ATTR_WANTNCACHE) != 0)

struct dns_fetch {
	unsigned int			magic;
	void *				private;
};

#define DNS_FETCH_MAGIC			0x46746368U	/* Ftch */
#define DNS_FETCH_VALID(fetch)		((fetch) != NULL && \
					 (fetch)->magic == DNS_FETCH_MAGIC)

typedef struct fctxbucket {
	isc_task_t *			task;
	isc_mutex_t			lock;
	ISC_LIST(fetchctx_t)		fctxs;
	isc_boolean_t			exiting;
} fctxbucket_t;

struct dns_resolver {
	/* Unlocked */
	unsigned int			magic;
	isc_mem_t *			mctx;
	isc_mutex_t			lock;
	dns_rdataclass_t		rdclass;
	isc_socketmgr_t *		socketmgr;
	isc_timermgr_t *		timermgr;
	dns_view_t *			view;
	/* Locked by lock. */
	unsigned int			references;
	isc_boolean_t			exiting;
	isc_socket_t *			udpsocket4;
	isc_socket_t *			udpsocket6;
	dns_dispatch_t *		dispatch4;
	dns_dispatch_t *		dispatch6;
	unsigned int			nbuckets;
	unsigned int			activebuckets;
	fctxbucket_t *			buckets;
};

#define RES_MAGIC			0x52657321U	/* Res! */
#define VALID_RESOLVER(res)		((res) != NULL && \
					 (res)->magic == RES_MAGIC)


static void destroy(dns_resolver_t *res);
static void empty_bucket(dns_resolver_t *res);
static void resquery_response(isc_task_t *task, isc_event_t *event);
static void fctx_try(fetchctx_t *fctx);
static isc_boolean_t fctx_destroy(fetchctx_t *fctx);

static inline isc_result_t
fctx_starttimer(fetchctx_t *fctx) {
	return (isc_timer_reset(fctx->timer, isc_timertype_once,
				&fctx->expires, &fctx->interval,
				ISC_FALSE));
}

static inline isc_result_t
fctx_stopidletimer(fetchctx_t *fctx) {
	return (isc_timer_reset(fctx->timer, isc_timertype_once,
				&fctx->expires, NULL,
				ISC_FALSE));
}

static inline void
fctx_stoptimer(fetchctx_t *fctx) {
	isc_result_t result;

	/*
	 * We don't return a result if resetting the timer to inactive fails
	 * since there's nothing to be done about it.  Resetting to inactive
	 * should never fail anyway, since the code as currently written
	 * cannot fail in that case.
	 */
	result = isc_timer_reset(fctx->timer, isc_timertype_inactive,
				  NULL, NULL, ISC_TRUE);
	if (result != ISC_R_SUCCESS) {
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_timer_reset(): %s",
				 isc_result_totext(result));
	}
}


static inline void
fctx_cancelquery(resquery_t **queryp, dns_dispatchevent_t **deventp) {
	fetchctx_t *fctx;
	resquery_t *query;

	query = *queryp;
	fctx = query->fctx;

	FCTXTRACE("cancelquery");

	dns_dispatch_removeresponse(query->dispatch, &query->dispentry,
				    deventp);
	ISC_LIST_UNLINK(fctx->queries, query, link);
	query->magic = 0;
	if (query->tsig != NULL)
		dns_rdata_freestruct(query->tsig);
	isc_mem_put(fctx->res->mctx, query, sizeof *query);
	*queryp = NULL;
}

static void
fctx_cancelqueries(fetchctx_t *fctx) {
	resquery_t *query, *next_query;

	FCTXTRACE("cancelqueries");

	for (query = ISC_LIST_HEAD(fctx->queries);
	     query != NULL;
	     query = next_query) {
		next_query = ISC_LIST_NEXT(query, link);
		fctx_cancelquery(&query, NULL);
	}
}

static void
fctx_cleanupfinds(fetchctx_t *fctx) {
	dns_adbfind_t *find, *next_find;

	for (find = ISC_LIST_HEAD(fctx->finds);
	     find != NULL;
	     find = next_find) {
		next_find = ISC_LIST_NEXT(find, publink);
		ISC_LIST_UNLINK(fctx->finds, find, publink);
		dns_adb_destroyfind(&find);
	}
	fctx->find = NULL;
}

static inline void
fctx_stopeverything(fetchctx_t *fctx) {
	FCTXTRACE("stopeverything");
	fctx_cleanupfinds(fctx);
	fctx_cancelqueries(fctx);
	fctx_stoptimer(fctx);
}

static inline void
fctx_sendevents(fetchctx_t *fctx, isc_result_t result) {
	dns_fetchevent_t *event, *next_event;
	isc_task_t *task;

	/*
	 * Caller must be holding the appropriate bucket lock.
	 */
	REQUIRE(fctx->state == fetchstate_done);

	FCTXTRACE("sendevents");

	for (event = ISC_LIST_HEAD(fctx->events);
	     event != NULL;
	     event = next_event) {
		next_event = ISC_LIST_NEXT(event, link);
		task = event->sender;
		event->sender = fctx;
		if (!HAVE_ANSWER(fctx))
			event->result = result;
		isc_task_sendanddetach(&task, (isc_event_t **)&event);
	}
	ISC_LIST_INIT(fctx->events);
}

static void
fctx_done(fetchctx_t *fctx, isc_result_t result) {
	dns_resolver_t *res;

	FCTXTRACE("done");

	res = fctx->res;

	fctx_stopeverything(fctx);

	LOCK(&res->buckets[fctx->bucketnum].lock);

	fctx->state = fetchstate_done;
	fctx_sendevents(fctx, result);

	UNLOCK(&res->buckets[fctx->bucketnum].lock);
}

static void
resquery_senddone(isc_task_t *task, isc_event_t *event) {
	isc_socketevent_t *sevent = (isc_socketevent_t *)event;
	resquery_t *query = event->arg;

	REQUIRE(event->type == ISC_SOCKEVENT_SENDDONE);

	/*
	 * XXXRTH
	 *
	 * Currently we don't wait for the senddone event before retrying
	 * a query.  This means that if we get really behind, we may end
	 * up doing extra work!
	 */

	(void)task;

	if (sevent->result != ISC_R_SUCCESS)
		fctx_cancelquery(&query, NULL);
				 
	isc_event_free(&event);
}

static isc_result_t
fctx_sendquery(fetchctx_t *fctx, isc_sockaddr_t *address) {
	resquery_t *query;
	isc_result_t result;
	dns_rdataset_t *qrdataset;
	dns_name_t *qname;
	isc_region_t r;
	dns_resolver_t *res;
	isc_task_t *task;

	FCTXTRACE("sendquery");

	res = fctx->res;
	task = res->buckets[fctx->bucketnum].task;

	result = fctx_starttimer(fctx);
	if (result != ISC_R_SUCCESS)
		return (result);

	dns_message_reset(fctx->rmessage, DNS_MESSAGE_INTENTPARSE);

	qname = NULL;
	result = dns_message_gettempname(fctx->qmessage, &qname);
	if (result != ISC_R_SUCCESS)
		goto cleanup_temps;
	qrdataset = NULL;
	result = dns_message_gettemprdataset(fctx->qmessage, &qrdataset);
	if (result != ISC_R_SUCCESS)
		goto cleanup_temps;

	query = isc_mem_get(res->mctx, sizeof *query);
	if (query == NULL)
		return (ISC_R_NOMEMORY);
	isc_buffer_init(&query->buffer, query->data, sizeof query->data,
			ISC_BUFFERTYPE_BINARY);
	
	/*
	 * If this is a TCP query, then we need to make a socket and
	 * a dispatch for it here.  Otherwise we use the resolver's
	 * shared dispatch.  We do not attach to the resolver's shared
	 * dispatch if we use it, so the resolver MUST ensure that no
	 * fetches are running before changing the shared dispatch.
	 */
	if ((fctx->options & DNS_FETCHOPT_TCP) != 0) {
		/* XXXRTH */
		result = DNS_R_NOTIMPLEMENTED;
		goto cleanup_query;
	} else {
		switch (isc_sockaddr_pf(address)) {
		case AF_INET:
			query->dispatch = res->dispatch4;
			break;
		case AF_INET6:
			query->dispatch = res->dispatch6;
			break;
		default:
			result = DNS_R_NOTIMPLEMENTED;
			goto cleanup_query;
		}
		/*
		 * We should always have a valid dispatcher here.  If we
		 * don't support a protocol family, then its dispatcher
		 * will be NULL, but we shouldn't be finding addresses for
		 * protocol types we don't support, so the dispatcher
		 * we found should never be NULL.
		 */
		INSIST(query->dispatch != NULL);
	}
	
	/*
	 * Get a query id from the dispatch.
	 */
	query->dispentry = NULL;
	result = dns_dispatch_addresponse(query->dispatch,
					  address,
					  task,
					  resquery_response,
					  query,
					  &query->id,
					  &query->dispentry);
	if (result != ISC_R_SUCCESS)
		goto cleanup_query;
	query->fctx = fctx;
	query->tsig = NULL;
	query->tsigkey = NULL;
	query->magic = QUERY_MAGIC;

	fctx->qmessage->opcode = dns_opcode_query;

	/*
	 * Set up question.
	 */
	dns_name_init(qname, NULL);
	dns_name_clone(&fctx->name, qname);
	dns_rdataset_init(qrdataset);
	dns_rdataset_makequestion(qrdataset, res->rdclass, fctx->type);
	ISC_LIST_APPEND(qname->list, qrdataset, link);
	dns_message_addname(fctx->qmessage, qname, DNS_SECTION_QUESTION);
	if ((fctx->options & DNS_FETCHOPT_RECURSIVE) != 0)
		fctx->qmessage->flags |= DNS_MESSAGEFLAG_RD;
	/*
	 * We don't have to set opcode because it defaults to query.
	 */
	fctx->qmessage->id = query->id;
	/*
	 * XXXRTH  Add TSIG and/or ENDS0 OPT record tailored to the current
	 *         recipient.
	 */

	/*
	 * Convert the question to wire format.
	 */
	result = dns_message_renderbegin(fctx->qmessage, &query->buffer);
	if (result != ISC_R_SUCCESS)
		goto cleanup_message;
	result = dns_message_rendersection(fctx->qmessage,
					   DNS_SECTION_QUESTION, 0, 0);
	if (result != ISC_R_SUCCESS)
		goto cleanup_message;
	result = dns_message_rendersection(fctx->qmessage,
					   DNS_SECTION_ADDITIONAL, 0, 0);
	if (result != ISC_R_SUCCESS)
		goto cleanup_message;
	result = dns_message_renderend(fctx->qmessage);
	if (result != ISC_R_SUCCESS)
		goto cleanup_message;

	if (fctx->qmessage->tsigkey != NULL) {
		query->tsigkey = fctx->qmessage->tsigkey;
		query->tsig = fctx->qmessage->tsig;
		fctx->qmessage->tsig = NULL;
	}

	/*
	 * We're now done with the query message.
	 */
	dns_message_reset(fctx->qmessage, DNS_MESSAGE_INTENTRENDER);

	/*
	 * Send the query!
	 */
	isc_buffer_used(&query->buffer, &r);
	result = isc_socket_sendto(dns_dispatch_getsocket(query->dispatch),
				   &r, task, resquery_senddone,
				   query, address);
	if (result != ISC_R_SUCCESS)
		goto cleanup_message;

	/*
	 * Finally, we've got everything going!
	 */
	ISC_LIST_APPEND(fctx->queries, query, link);

	QTRACE("sent");

	return (ISC_R_SUCCESS);

 cleanup_message:
	dns_message_reset(fctx->qmessage, DNS_MESSAGE_INTENTRENDER);

	/*
	 * Stop the dispatcher from listening.
	 */
	dns_dispatch_removeresponse(query->dispatch,
				    &query->dispentry,
				    NULL);

	/* 
	 * XXXRTH will need to cleanup a nonshared dispatch and TCP socket
	 * here.
	 */

 cleanup_query:
	query->magic = 0;
	isc_mem_put(res->mctx, query, sizeof *query);

 cleanup_temps:
	if (qname != NULL)
		dns_message_puttempname(fctx->qmessage, &qname);
	if (qrdataset != NULL)
		dns_message_puttemprdataset(fctx->qmessage, &qrdataset);

	fctx_stoptimer(fctx);

	return (result);
}

static void
fctx_finddone(isc_task_t *task, isc_event_t *event) {
	fetchctx_t *fctx;
	dns_adbfind_t *find;
	dns_resolver_t *res;
	isc_boolean_t want_try = ISC_FALSE;
	isc_boolean_t want_done = ISC_FALSE;
	isc_boolean_t bucket_empty = ISC_FALSE;
	unsigned int bucketnum;

	find = event->sender;
	fctx = event->arg;
	REQUIRE(VALID_FCTX(fctx));
	res = fctx->res;

	(void)task;

	FCTXTRACE("finddone");

	INSIST(fctx->pending > 0);
	fctx->pending--;

	if (ADDRWAIT(fctx)) {
		/*
		 * The fetch is waiting for a name to be found.
		 */
		fctx->attributes &= ~FCTX_ATTR_ADDRWAIT;
		if (event->type == DNS_EVENT_ADBMOREADDRESSES)
			want_try = ISC_TRUE;
		else if (fctx->pending == 0) {
			/*
			 * We've got nothing else to wait for and don't
			 * know the answer.  There's nothing to do but
			 * fail the fctx.
			 */
			want_done = ISC_TRUE;
		}
	} else if (fctx->pending == 0 && fctx->references == 0 &&
		   SHUTTINGDOWN(fctx)) {
		bucketnum = fctx->bucketnum;
		LOCK(&res->buckets[bucketnum].lock);
		bucket_empty = fctx_destroy(fctx);
		UNLOCK(&res->buckets[bucketnum].lock);
	}

	isc_event_free(&event);
	dns_adb_destroyfind(&find);

	if (want_try)
		fctx_try(fctx);
	else if (want_done)
		fctx_done(fctx, ISC_R_FAILURE);
	else if (bucket_empty)
		empty_bucket(res);
}

static isc_result_t
fctx_getaddresses(fetchctx_t *fctx) {
	dns_rdata_t rdata;
	isc_region_t r;
	dns_name_t name;
	isc_result_t result;
	dns_resolver_t *res;
	isc_stdtime_t now;
	dns_adbfind_t *find;
	unsigned int options;

	FCTXTRACE("getaddresses");

	res = fctx->res;
	options = DNS_ADBFIND_WANTEVENT|DNS_ADBFIND_EMPTYEVENT;
	if (res->dispatch4 != NULL)
		options |= DNS_ADBFIND_INET;
	if (res->dispatch6 != NULL)
		options |= DNS_ADBFIND_INET6;
	result = isc_stdtime_get(&now);
	if (result != ISC_R_SUCCESS)
		return (result);

	fctx_cleanupfinds(fctx);

	result = dns_rdataset_first(&fctx->nameservers);
	while (result == ISC_R_SUCCESS) {
		dns_rdataset_current(&fctx->nameservers, &rdata);
		/*
		 * Extract the name from the NS record.
		 */
		dns_rdata_toregion(&rdata, &r);
		dns_name_init(&name, NULL);
		dns_name_fromregion(&name, &r);
		/*
		 * XXXRTH  If this name is the same as QNAME, remember
		 *         skip it, and remember that we did so so we can
		 *         use an ancestor QDOMAIN if we find no addresses.
		 */
		/*
		 * See what we know about this address.
		 */
		find = NULL;
		result = dns_adb_createfind(res->view->adb,
					    res->buckets[fctx->bucketnum].task,
					    fctx_finddone, fctx, &name,
					    &fctx->domain, options, now,
					    &find);
		if (result != ISC_R_SUCCESS)
			return (result);
		if (!ISC_LIST_EMPTY(find->list)) {
			/*
			 * We have at least some of the addresses for the
			 * name.
			 */
			INSIST((find->options & DNS_ADBFIND_WANTEVENT) == 0);
			/*
			 * XXXRTH  Sort.
			 */
			ISC_LIST_APPEND(fctx->finds, find, publink);
		} else {
			/*
			 * We don't know any of the addresses for this
			 * name.
			 */
			if ((find->options & DNS_ADBFIND_WANTEVENT) != 0) {
				/*
				 * We're looking for them and will get an
				 * event about it later.
				 */
				fctx->pending++;
			} else {
				/*
				 * And ADB isn't going to send us any events
				 * either.  This query loses.
				 */
				dns_adb_destroyfind(&find);
			}
		}
		result = dns_rdataset_next(&fctx->nameservers);
	}
	if (result != DNS_R_NOMORE)
		return (result);

	if (ISC_LIST_EMPTY(fctx->finds) && fctx->pending > 0) {
		/*
		 * We're fetching the addresses, but don't have any yet.
		 * Tell the caller to wait for an answer.
		 */
		result = DNS_R_WAIT;
	} else if (ISC_LIST_EMPTY(fctx->finds)) {
		/*
		 * We've lost completely.  We don't know any addresses, and
		 * the ADB has told us it can't get them.
		 */
		result = ISC_R_FAILURE;
	} else {
		/*
		 * We've found some addresses.  We might still be looking
		 * for more addresses.
		 */

		/*
		 * XXXRTH  Sort.
		 */

		result = ISC_R_SUCCESS;
	}

	return (result);
}

#define FCTX_ADDRINFO_MARK		0x01
#define UNMARKED(a)			(((a)->flags & FCTX_ADDRINFO_MARK) \
					 == 0)

static inline dns_adbaddrinfo_t *
fctx_nextaddress(fetchctx_t *fctx) {
	dns_adbfind_t *find;
	dns_adbaddrinfo_t *addrinfo;
	int count = 0;

	/*
	 * Return the next untried address, if any.
	 */

	/*
	 * Move to the next find.
	 */
	find = fctx->find;
	if (find == NULL)
		find = ISC_LIST_HEAD(fctx->finds);
	else {
		find = ISC_LIST_NEXT(find, publink);
		if (find == NULL)
			find = ISC_LIST_HEAD(fctx->finds);
	}

	/*
	 * Find the first unmarked addrinfo.
	 */
	addrinfo = NULL;
	while (find != fctx->find) {
		count++;
		INSIST(count < 1000);
		for (addrinfo = ISC_LIST_HEAD(find->list);
		     addrinfo != NULL;
		     addrinfo = ISC_LIST_NEXT(addrinfo, publink)) {
			if (UNMARKED(addrinfo)) {
				addrinfo->flags |= FCTX_ADDRINFO_MARK;
				break;
			}
		}
		if (addrinfo != NULL)
			break;
		find = ISC_LIST_NEXT(find, publink);
		if (find != fctx->find && find == NULL)
			find = ISC_LIST_HEAD(fctx->finds);
	}

	fctx->find = find;

	return (addrinfo);
}

static void
fctx_try(fetchctx_t *fctx) {
	isc_result_t result;
	dns_adbaddrinfo_t *addrinfo;

	FCTXTRACE("try");

	REQUIRE(!ADDRWAIT(fctx));

	/*
	 * XXXRTH  We don't try to handle forwarding yet.
	 */

	addrinfo = fctx_nextaddress(fctx);
	if (addrinfo == NULL) {
		/*
		 * We have no more addresses.  Start over.
		 */
		fctx_cancelqueries(fctx);
		result = fctx_getaddresses(fctx);
		if (result == DNS_R_WAIT) {
			/*
			 * Sleep waiting for addresses.
			 */
			FCTXTRACE("addrwait");
			fctx->attributes |= FCTX_ATTR_ADDRWAIT; 
			return;
		} else if (result != ISC_R_SUCCESS) {
			/*
			 * Something bad happened.
			 */
			fctx_done(fctx, result);
			return;
		}

		addrinfo = fctx_nextaddress(fctx);
		/*
		 * fctx_getaddresses() returned success, so at least one
		 * of the find lists should be nonempty.
		 */
		INSIST(addrinfo != NULL);
	}

	/*
	 * XXXRTH  This is the place where a try strategy routine would
	 *         be called to send one or more queries.  Instead, we
	 *	   just send a single query.
	 */

	result = fctx_sendquery(fctx, addrinfo->sockaddr);
	if (result != ISC_R_SUCCESS)
		fctx_done(fctx, result);
}

static isc_boolean_t
fctx_destroy(fetchctx_t *fctx) {
	dns_resolver_t *res;
	unsigned int bucketnum;

	/*
	 * Caller must be holding the bucket lock.
	 */

	REQUIRE(VALID_FCTX(fctx));
	REQUIRE(fctx->state == fetchstate_done);
	REQUIRE(ISC_LIST_EMPTY(fctx->events));
	REQUIRE(ISC_LIST_EMPTY(fctx->queries));
	REQUIRE(ISC_LIST_EMPTY(fctx->finds));
	REQUIRE(fctx->pending == 0);

	FCTXTRACE("destroy");

	res = fctx->res;
	bucketnum = fctx->bucketnum;

	ISC_LIST_UNLINK(res->buckets[bucketnum].fctxs, fctx, link);

	isc_timer_detach(&fctx->timer);
	dns_message_destroy(&fctx->rmessage);
	dns_message_destroy(&fctx->qmessage);
	if (dns_name_countlabels(&fctx->domain) > 0) {
		if (dns_rdataset_isassociated(&fctx->nameservers))
			dns_rdataset_disassociate(&fctx->nameservers);
		dns_name_free(&fctx->domain, res->mctx);
	}
	dns_name_free(&fctx->name, fctx->res->mctx);
	isc_mem_put(res->mctx, fctx, sizeof *fctx);

	if (res->buckets[bucketnum].exiting &&
	    ISC_LIST_EMPTY(res->buckets[bucketnum].fctxs))
		return (ISC_TRUE);

	return (ISC_FALSE);
}

/*
 * Fetch event handlers.
 */

static void
fctx_timeout(isc_task_t *task, isc_event_t *event) {
	fetchctx_t *fctx = event->arg;

	REQUIRE(VALID_FCTX(fctx));

	(void)task;	/* Keep compiler quiet. */

	FCTXTRACE("timeout");

	if (event->type == ISC_TIMEREVENT_LIFE) {
		fctx_done(fctx, DNS_R_TIMEDOUT);
	} else {
		/*
		 * We could cancel the running queries here, or we could let
		 * them keep going.  Right now we choose the latter...
		 */
		fctx->attributes &= ~FCTX_ATTR_ADDRWAIT;
		fctx_try(fctx);
	}

	isc_event_free(&event);
}

static void
fctx_shutdown(isc_task_t *task, isc_event_t *event) {
	fetchctx_t *fctx = event->arg;
	isc_boolean_t bucket_empty = ISC_FALSE;
	dns_resolver_t *res;
	unsigned int bucketnum;

	REQUIRE(VALID_FCTX(fctx));

	res = fctx->res;
	bucketnum = fctx->bucketnum;
	(void)task;	/* Keep compiler quiet. */
	
	FCTXTRACE("shutdown");

	fctx->attributes |= FCTX_ATTR_SHUTTINGDOWN;

	LOCK(&res->buckets[bucketnum].lock);
	
	INSIST(fctx->state == fetchstate_active ||
	       fctx->state == fetchstate_done);
	INSIST(fctx->want_shutdown);

	if (fctx->state != fetchstate_done) {
		fctx_stopeverything(fctx);
		fctx->state = fetchstate_done;
		fctx_sendevents(fctx, ISC_R_CANCELED);
	}

	if (fctx->references == 0 && fctx->pending == 0)
		bucket_empty = fctx_destroy(fctx);

	UNLOCK(&res->buckets[bucketnum].lock);

	if (bucket_empty)
		empty_bucket(res);
}

static void
fctx_start(isc_task_t *task, isc_event_t *event) {
	fetchctx_t *fctx = event->arg;
	isc_boolean_t done = ISC_FALSE, bucket_empty = ISC_FALSE;
	dns_resolver_t *res;
	unsigned int bucketnum;

	REQUIRE(VALID_FCTX(fctx));

	res = fctx->res;
	bucketnum = fctx->bucketnum;
	(void)task;	/* Keep compiler quiet. */

	FCTXTRACE("start");

	LOCK(&res->buckets[bucketnum].lock);

	INSIST(fctx->state == fetchstate_init);
	if (fctx->want_shutdown) {
		/*
		 * We haven't started this fctx yet, and we've been requested
		 * to shut it down.
		 *
		 * The events list should be empty, so we INSIST on it.
		 */
		INSIST(ISC_LIST_EMPTY(fctx->events));
		bucket_empty = fctx_destroy(fctx);
		done = ISC_TRUE;
	} else {
		/*
		 * Normal fctx startup.
		 */
		fctx->state = fetchstate_active;
		/*
		 * Reset the control event for later use in shutting down
		 * the fctx.
		 */
		ISC_EVENT_INIT(event, sizeof *event, 0, NULL,
			       DNS_EVENT_FETCHCONTROL, fctx_shutdown, fctx,
			       (void *)fctx_shutdown, NULL, NULL);
	}

	UNLOCK(&res->buckets[bucketnum].lock);

	if (!done) {
		/*
		 * All is well.  Start working on the fetch.
		 */
		fctx_try(fctx);
	} else if (bucket_empty)
		empty_bucket(res);
}

/*
 * Fetch Creation, Joining, and Cancelation.
 */

static inline isc_result_t
fctx_join(fetchctx_t *fctx, isc_task_t *task, isc_taskaction_t action,
	  void *arg, dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset,
	  dns_fetch_t *fetch)
{
	isc_task_t *clone;
	dns_fetchevent_t *event;

	FCTXTRACE("join");

	/*
	 * We store the task we're going to send this event to in the
	 * sender field.  We'll make the fetch the sender when we actually
	 * send the event.
	 */
	clone = NULL;
	isc_task_attach(task, &clone);
	event = (dns_fetchevent_t *)
		isc_event_allocate(fctx->res->mctx, clone,
				   DNS_EVENT_FETCHDONE,
				   action, arg, sizeof *event);
	if (event == NULL)
		return (ISC_R_NOMEMORY);
	event->result = DNS_R_SERVFAIL;
	event->qtype = fctx->type;
	event->db = NULL;
	event->node = NULL;
	event->rdataset = rdataset;
	event->sigrdataset = sigrdataset;
	event->fetch = fetch;
	dns_fixedname_init(&event->foundname);
	ISC_LIST_APPEND(fctx->events, event, link);

	fctx->references++;

	fetch->magic = DNS_FETCH_MAGIC;
	fetch->private = fctx;
	
	return (ISC_R_SUCCESS);
}

static isc_result_t
fctx_create(dns_resolver_t *res, dns_name_t *name, dns_rdatatype_t type,
	    dns_name_t *domain, dns_rdataset_t *nameservers,
	    unsigned int options, unsigned int bucketnum, fetchctx_t **fctxp)
{
	fetchctx_t *fctx;
	isc_result_t result = ISC_R_SUCCESS;
	isc_result_t iresult;
	isc_interval_t interval;

	/*
	 * Caller must be holding the lock for bucket number 'bucketnum'.
	 */
	REQUIRE(fctxp != NULL && *fctxp == NULL);

	fctx = isc_mem_get(res->mctx, sizeof *fctx);
	if (fctx == NULL)
		return (ISC_R_NOMEMORY);
	FCTXTRACE("create");
	dns_name_init(&fctx->name, NULL);
	result = dns_name_dup(name, res->mctx, &fctx->name);
	if (result != ISC_R_SUCCESS)
		goto cleanup_fetch;
	dns_name_init(&fctx->domain, NULL);
	dns_rdataset_init(&fctx->nameservers);
	if (domain != NULL) {
		result = dns_name_dup(domain, res->mctx, &fctx->domain);
		if (result != ISC_R_SUCCESS)
			goto cleanup_name;
		dns_rdataset_clone(nameservers, &fctx->nameservers);
	}
	fctx->type = type;
	fctx->options = options;
	/*
	 * Note!  We do not attach to the task.  We are relying on the
	 * resolver to ensure that this task doesn't go away while we are
	 * using it.
	 */
	fctx->res = res;
	fctx->references = 0;
	fctx->bucketnum = bucketnum;
	fctx->state = fetchstate_init;
	fctx->want_shutdown = ISC_FALSE;
	ISC_LIST_INIT(fctx->queries);
	ISC_LIST_INIT(fctx->finds);
	fctx->find = NULL;
	fctx->pending = 0;
	fctx->attributes = 0;

	fctx->qmessage = NULL;
	result = dns_message_create(res->mctx, DNS_MESSAGE_INTENTRENDER,
				    &fctx->qmessage);
				    
	if (result != ISC_R_SUCCESS)
		goto cleanup_domain;

	fctx->rmessage = NULL;
	result = dns_message_create(res->mctx, DNS_MESSAGE_INTENTPARSE,
				    &fctx->rmessage);
				    
	if (result != ISC_R_SUCCESS)
		goto cleanup_qmessage;

	/*
	 * Compute an expiration time for the entire fetch.
	 */
	isc_interval_set(&interval, 30, 0);		/* XXXRTH constant */
	iresult = isc_time_nowplusinterval(&fctx->expires, &interval);
	if (iresult != ISC_R_SUCCESS) {
		UNEXPECTED_ERROR(__FILE__, __LINE__,