xref: /freebsd/contrib/unbound/iterator/iterator.c (revision 5ab1c5846ff41be24b1f6beb0317bf8258cd4409)
1 /*
2  * iterator/iterator.c - iterative resolver DNS query response module
3  *
4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
5  *
6  * This software is open source.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  *
15  * Redistributions in binary form must reproduce the above copyright notice,
16  * this list of conditions and the following disclaimer in the documentation
17  * and/or other materials provided with the distribution.
18  *
19  * Neither the name of the NLNET LABS nor the names of its contributors may
20  * be used to endorse or promote products derived from this software without
21  * specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35 
36 /**
37  * \file
38  *
39  * This file contains a module that performs recursive iterative DNS query
40  * processing.
41  */
42 
43 #include "config.h"
44 #include "iterator/iterator.h"
45 #include "iterator/iter_utils.h"
46 #include "iterator/iter_hints.h"
47 #include "iterator/iter_fwd.h"
48 #include "iterator/iter_donotq.h"
49 #include "iterator/iter_delegpt.h"
50 #include "iterator/iter_resptype.h"
51 #include "iterator/iter_scrub.h"
52 #include "iterator/iter_priv.h"
53 #include "validator/val_neg.h"
54 #include "services/cache/dns.h"
55 #include "services/cache/infra.h"
56 #include "services/authzone.h"
57 #include "util/module.h"
58 #include "util/netevent.h"
59 #include "util/net_help.h"
60 #include "util/regional.h"
61 #include "util/data/dname.h"
62 #include "util/data/msgencode.h"
63 #include "util/fptr_wlist.h"
64 #include "util/config_file.h"
65 #include "util/random.h"
66 #include "sldns/rrdef.h"
67 #include "sldns/wire2str.h"
68 #include "sldns/str2wire.h"
69 #include "sldns/parseutil.h"
70 #include "sldns/sbuffer.h"
71 
72 /* in msec */
73 int UNKNOWN_SERVER_NICENESS = 376;
74 
75 int
76 iter_init(struct module_env* env, int id)
77 {
78 	struct iter_env* iter_env = (struct iter_env*)calloc(1,
79 		sizeof(struct iter_env));
80 	if(!iter_env) {
81 		log_err("malloc failure");
82 		return 0;
83 	}
84 	env->modinfo[id] = (void*)iter_env;
85 
86 	lock_basic_init(&iter_env->queries_ratelimit_lock);
87 	lock_protect(&iter_env->queries_ratelimit_lock,
88 			&iter_env->num_queries_ratelimited,
89 		sizeof(iter_env->num_queries_ratelimited));
90 
91 	if(!iter_apply_cfg(iter_env, env->cfg)) {
92 		log_err("iterator: could not apply configuration settings.");
93 		return 0;
94 	}
95 
96 	return 1;
97 }
98 
99 /** delete caps_whitelist element */
100 static void
101 caps_free(struct rbnode_type* n, void* ATTR_UNUSED(d))
102 {
103 	if(n) {
104 		free(((struct name_tree_node*)n)->name);
105 		free(n);
106 	}
107 }
108 
109 void
110 iter_deinit(struct module_env* env, int id)
111 {
112 	struct iter_env* iter_env;
113 	if(!env || !env->modinfo[id])
114 		return;
115 	iter_env = (struct iter_env*)env->modinfo[id];
116 	lock_basic_destroy(&iter_env->queries_ratelimit_lock);
117 	free(iter_env->target_fetch_policy);
118 	priv_delete(iter_env->priv);
119 	donotq_delete(iter_env->donotq);
120 	if(iter_env->caps_white) {
121 		traverse_postorder(iter_env->caps_white, caps_free, NULL);
122 		free(iter_env->caps_white);
123 	}
124 	free(iter_env);
125 	env->modinfo[id] = NULL;
126 }
127 
128 /** new query for iterator */
129 static int
130 iter_new(struct module_qstate* qstate, int id)
131 {
132 	struct iter_qstate* iq = (struct iter_qstate*)regional_alloc(
133 		qstate->region, sizeof(struct iter_qstate));
134 	qstate->minfo[id] = iq;
135 	if(!iq)
136 		return 0;
137 	memset(iq, 0, sizeof(*iq));
138 	iq->state = INIT_REQUEST_STATE;
139 	iq->final_state = FINISHED_STATE;
140 	iq->an_prepend_list = NULL;
141 	iq->an_prepend_last = NULL;
142 	iq->ns_prepend_list = NULL;
143 	iq->ns_prepend_last = NULL;
144 	iq->dp = NULL;
145 	iq->depth = 0;
146 	iq->num_target_queries = 0;
147 	iq->num_current_queries = 0;
148 	iq->query_restart_count = 0;
149 	iq->referral_count = 0;
150 	iq->sent_count = 0;
151 	iq->ratelimit_ok = 0;
152 	iq->target_count = NULL;
153 	iq->wait_priming_stub = 0;
154 	iq->refetch_glue = 0;
155 	iq->dnssec_expected = 0;
156 	iq->dnssec_lame_query = 0;
157 	iq->chase_flags = qstate->query_flags;
158 	/* Start with the (current) qname. */
159 	iq->qchase = qstate->qinfo;
160 	outbound_list_init(&iq->outlist);
161 	iq->minimise_count = 0;
162 	iq->minimise_timeout_count = 0;
163 	if (qstate->env->cfg->qname_minimisation)
164 		iq->minimisation_state = INIT_MINIMISE_STATE;
165 	else
166 		iq->minimisation_state = DONOT_MINIMISE_STATE;
167 
168 	memset(&iq->qinfo_out, 0, sizeof(struct query_info));
169 	return 1;
170 }
171 
172 /**
173  * Transition to the next state. This can be used to advance a currently
174  * processing event. It cannot be used to reactivate a forEvent.
175  *
176  * @param iq: iterator query state
177  * @param nextstate The state to transition to.
178  * @return true. This is so this can be called as the return value for the
179  *         actual process*State() methods. (Transitioning to the next state
180  *         implies further processing).
181  */
182 static int
183 next_state(struct iter_qstate* iq, enum iter_state nextstate)
184 {
185 	/* If transitioning to a "response" state, make sure that there is a
186 	 * response */
187 	if(iter_state_is_responsestate(nextstate)) {
188 		if(iq->response == NULL) {
189 			log_err("transitioning to response state sans "
190 				"response.");
191 		}
192 	}
193 	iq->state = nextstate;
194 	return 1;
195 }
196 
197 /**
198  * Transition an event to its final state. Final states always either return
199  * a result up the module chain, or reactivate a dependent event. Which
200  * final state to transition to is set in the module state for the event when
201  * it was created, and depends on the original purpose of the event.
202  *
203  * The response is stored in the qstate->buf buffer.
204  *
205  * @param iq: iterator query state
206  * @return false. This is so this method can be used as the return value for
207  *         the processState methods. (Transitioning to the final state
208  */
209 static int
210 final_state(struct iter_qstate* iq)
211 {
212 	return next_state(iq, iq->final_state);
213 }
214 
215 /**
216  * Callback routine to handle errors in parent query states
217  * @param qstate: query state that failed.
218  * @param id: module id.
219  * @param super: super state.
220  */
221 static void
222 error_supers(struct module_qstate* qstate, int id, struct module_qstate* super)
223 {
224 	struct iter_qstate* super_iq = (struct iter_qstate*)super->minfo[id];
225 
226 	if(qstate->qinfo.qtype == LDNS_RR_TYPE_A ||
227 		qstate->qinfo.qtype == LDNS_RR_TYPE_AAAA) {
228 		/* mark address as failed. */
229 		struct delegpt_ns* dpns = NULL;
230 		super_iq->num_target_queries--;
231 		if(super_iq->dp)
232 			dpns = delegpt_find_ns(super_iq->dp,
233 				qstate->qinfo.qname, qstate->qinfo.qname_len);
234 		if(!dpns) {
235 			/* not interested */
236 			/* this can happen, for eg. qname minimisation asked
237 			 * for an NXDOMAIN to be validated, and used qtype
238 			 * A for that, and the error of that, the name, is
239 			 * not listed in super_iq->dp */
240 			verbose(VERB_ALGO, "subq error, but not interested");
241 			log_query_info(VERB_ALGO, "superq", &super->qinfo);
242 			return;
243 		} else {
244 			/* see if the failure did get (parent-lame) info */
245 			if(!cache_fill_missing(super->env, super_iq->qchase.qclass,
246 				super->region, super_iq->dp))
247 				log_err("out of memory adding missing");
248 		}
249 		dpns->resolved = 1; /* mark as failed */
250 	}
251 	if(qstate->qinfo.qtype == LDNS_RR_TYPE_NS) {
252 		/* prime failed to get delegation */
253 		super_iq->dp = NULL;
254 	}
255 	/* evaluate targets again */
256 	super_iq->state = QUERYTARGETS_STATE;
257 	/* super becomes runnable, and will process this change */
258 }
259 
260 /**
261  * Return an error to the client
262  * @param qstate: our query state
263  * @param id: module id
264  * @param rcode: error code (DNS errcode).
265  * @return: 0 for use by caller, to make notation easy, like:
266  * 	return error_response(..).
267  */
268 static int
269 error_response(struct module_qstate* qstate, int id, int rcode)
270 {
271 	verbose(VERB_QUERY, "return error response %s",
272 		sldns_lookup_by_id(sldns_rcodes, rcode)?
273 		sldns_lookup_by_id(sldns_rcodes, rcode)->name:"??");
274 	qstate->return_rcode = rcode;
275 	qstate->return_msg = NULL;
276 	qstate->ext_state[id] = module_finished;
277 	return 0;
278 }
279 
280 /**
281  * Return an error to the client and cache the error code in the
282  * message cache (so per qname, qtype, qclass).
283  * @param qstate: our query state
284  * @param id: module id
285  * @param rcode: error code (DNS errcode).
286  * @return: 0 for use by caller, to make notation easy, like:
287  * 	return error_response(..).
288  */
289 static int
290 error_response_cache(struct module_qstate* qstate, int id, int rcode)
291 {
292 	if(!qstate->no_cache_store) {
293 		/* store in cache */
294 		struct reply_info err;
295 		if(qstate->prefetch_leeway > NORR_TTL) {
296 			verbose(VERB_ALGO, "error response for prefetch in cache");
297 			/* attempt to adjust the cache entry prefetch */
298 			if(dns_cache_prefetch_adjust(qstate->env, &qstate->qinfo,
299 				NORR_TTL, qstate->query_flags))
300 				return error_response(qstate, id, rcode);
301 			/* if that fails (not in cache), fall through to store err */
302 		}
303 		if(qstate->env->cfg->serve_expired) {
304 			/* if serving expired contents, and such content is
305 			 * already available, don't overwrite this servfail */
306 			struct msgreply_entry* msg;
307 			if((msg=msg_cache_lookup(qstate->env,
308 				qstate->qinfo.qname, qstate->qinfo.qname_len,
309 				qstate->qinfo.qtype, qstate->qinfo.qclass,
310 				qstate->query_flags, 0,
311 				qstate->env->cfg->serve_expired_ttl_reset))
312 				!= NULL) {
313 				if(qstate->env->cfg->serve_expired_ttl_reset) {
314 					struct reply_info* rep =
315 						(struct reply_info*)msg->entry.data;
316 					if(rep && *qstate->env->now +
317 						qstate->env->cfg->serve_expired_ttl  >
318 						rep->serve_expired_ttl) {
319 						rep->serve_expired_ttl =
320 							*qstate->env->now +
321 							qstate->env->cfg->serve_expired_ttl;
322 					}
323 				}
324 				lock_rw_unlock(&msg->entry.lock);
325 				return error_response(qstate, id, rcode);
326 			}
327 			/* serving expired contents, but nothing is cached
328 			 * at all, so the servfail cache entry is useful
329 			 * (stops waste of time on this servfail NORR_TTL) */
330 		} else {
331 			/* don't overwrite existing (non-expired) data in
332 			 * cache with a servfail */
333 			struct msgreply_entry* msg;
334 			if((msg=msg_cache_lookup(qstate->env,
335 				qstate->qinfo.qname, qstate->qinfo.qname_len,
336 				qstate->qinfo.qtype, qstate->qinfo.qclass,
337 				qstate->query_flags, *qstate->env->now, 0))
338 				!= NULL) {
339 				struct reply_info* rep = (struct reply_info*)
340 					msg->entry.data;
341 				if(FLAGS_GET_RCODE(rep->flags) ==
342 					LDNS_RCODE_NOERROR ||
343 					FLAGS_GET_RCODE(rep->flags) ==
344 					LDNS_RCODE_NXDOMAIN) {
345 					/* we have a good entry,
346 					 * don't overwrite */
347 					lock_rw_unlock(&msg->entry.lock);
348 					return error_response(qstate, id, rcode);
349 				}
350 				lock_rw_unlock(&msg->entry.lock);
351 			}
352 
353 		}
354 		memset(&err, 0, sizeof(err));
355 		err.flags = (uint16_t)(BIT_QR | BIT_RA);
356 		FLAGS_SET_RCODE(err.flags, rcode);
357 		err.qdcount = 1;
358 		err.ttl = NORR_TTL;
359 		err.prefetch_ttl = PREFETCH_TTL_CALC(err.ttl);
360 		err.serve_expired_ttl = NORR_TTL;
361 		/* do not waste time trying to validate this servfail */
362 		err.security = sec_status_indeterminate;
363 		verbose(VERB_ALGO, "store error response in message cache");
364 		iter_dns_store(qstate->env, &qstate->qinfo, &err, 0, 0, 0, NULL,
365 			qstate->query_flags);
366 	}
367 	return error_response(qstate, id, rcode);
368 }
369 
370 /** check if prepend item is duplicate item */
371 static int
372 prepend_is_duplicate(struct ub_packed_rrset_key** sets, size_t to,
373 	struct ub_packed_rrset_key* dup)
374 {
375 	size_t i;
376 	for(i=0; i<to; i++) {
377 		if(sets[i]->rk.type == dup->rk.type &&
378 			sets[i]->rk.rrset_class == dup->rk.rrset_class &&
379 			sets[i]->rk.dname_len == dup->rk.dname_len &&
380 			query_dname_compare(sets[i]->rk.dname, dup->rk.dname)
381 			== 0)
382 			return 1;
383 	}
384 	return 0;
385 }
386 
387 /** prepend the prepend list in the answer and authority section of dns_msg */
388 static int
389 iter_prepend(struct iter_qstate* iq, struct dns_msg* msg,
390 	struct regional* region)
391 {
392 	struct iter_prep_list* p;
393 	struct ub_packed_rrset_key** sets;
394 	size_t num_an = 0, num_ns = 0;;
395 	for(p = iq->an_prepend_list; p; p = p->next)
396 		num_an++;
397 	for(p = iq->ns_prepend_list; p; p = p->next)
398 		num_ns++;
399 	if(num_an + num_ns == 0)
400 		return 1;
401 	verbose(VERB_ALGO, "prepending %d rrsets", (int)num_an + (int)num_ns);
402 	if(num_an > RR_COUNT_MAX || num_ns > RR_COUNT_MAX ||
403 		msg->rep->rrset_count > RR_COUNT_MAX) return 0; /* overflow */
404 	sets = regional_alloc(region, (num_an+num_ns+msg->rep->rrset_count) *
405 		sizeof(struct ub_packed_rrset_key*));
406 	if(!sets)
407 		return 0;
408 	/* ANSWER section */
409 	num_an = 0;
410 	for(p = iq->an_prepend_list; p; p = p->next) {
411 		sets[num_an++] = p->rrset;
412 	}
413 	memcpy(sets+num_an, msg->rep->rrsets, msg->rep->an_numrrsets *
414 		sizeof(struct ub_packed_rrset_key*));
415 	/* AUTH section */
416 	num_ns = 0;
417 	for(p = iq->ns_prepend_list; p; p = p->next) {
418 		if(prepend_is_duplicate(sets+msg->rep->an_numrrsets+num_an,
419 			num_ns, p->rrset) || prepend_is_duplicate(
420 			msg->rep->rrsets+msg->rep->an_numrrsets,
421 			msg->rep->ns_numrrsets, p->rrset))
422 			continue;
423 		sets[msg->rep->an_numrrsets + num_an + num_ns++] = p->rrset;
424 	}
425 	memcpy(sets + num_an + msg->rep->an_numrrsets + num_ns,
426 		msg->rep->rrsets + msg->rep->an_numrrsets,
427 		(msg->rep->ns_numrrsets + msg->rep->ar_numrrsets) *
428 		sizeof(struct ub_packed_rrset_key*));
429 
430 	/* NXDOMAIN rcode can stay if we prepended DNAME/CNAMEs, because
431 	 * this is what recursors should give. */
432 	msg->rep->rrset_count += num_an + num_ns;
433 	msg->rep->an_numrrsets += num_an;
434 	msg->rep->ns_numrrsets += num_ns;
435 	msg->rep->rrsets = sets;
436 	return 1;
437 }
438 
439 /**
440  * Find rrset in ANSWER prepend list.
441  * to avoid duplicate DNAMEs when a DNAME is traversed twice.
442  * @param iq: iterator query state.
443  * @param rrset: rrset to add.
444  * @return false if not found
445  */
446 static int
447 iter_find_rrset_in_prepend_answer(struct iter_qstate* iq,
448 	struct ub_packed_rrset_key* rrset)
449 {
450 	struct iter_prep_list* p = iq->an_prepend_list;
451 	while(p) {
452 		if(ub_rrset_compare(p->rrset, rrset) == 0 &&
453 			rrsetdata_equal((struct packed_rrset_data*)p->rrset
454 			->entry.data, (struct packed_rrset_data*)rrset
455 			->entry.data))
456 			return 1;
457 		p = p->next;
458 	}
459 	return 0;
460 }
461 
462 /**
463  * Add rrset to ANSWER prepend list
464  * @param qstate: query state.
465  * @param iq: iterator query state.
466  * @param rrset: rrset to add.
467  * @return false on failure (malloc).
468  */
469 static int
470 iter_add_prepend_answer(struct module_qstate* qstate, struct iter_qstate* iq,
471 	struct ub_packed_rrset_key* rrset)
472 {
473 	struct iter_prep_list* p = (struct iter_prep_list*)regional_alloc(
474 		qstate->region, sizeof(struct iter_prep_list));
475 	if(!p)
476 		return 0;
477 	p->rrset = rrset;
478 	p->next = NULL;
479 	/* add at end */
480 	if(iq->an_prepend_last)
481 		iq->an_prepend_last->next = p;
482 	else	iq->an_prepend_list = p;
483 	iq->an_prepend_last = p;
484 	return 1;
485 }
486 
487 /**
488  * Add rrset to AUTHORITY prepend list
489  * @param qstate: query state.
490  * @param iq: iterator query state.
491  * @param rrset: rrset to add.
492  * @return false on failure (malloc).
493  */
494 static int
495 iter_add_prepend_auth(struct module_qstate* qstate, struct iter_qstate* iq,
496 	struct ub_packed_rrset_key* rrset)
497 {
498 	struct iter_prep_list* p = (struct iter_prep_list*)regional_alloc(
499 		qstate->region, sizeof(struct iter_prep_list));
500 	if(!p)
501 		return 0;
502 	p->rrset = rrset;
503 	p->next = NULL;
504 	/* add at end */
505 	if(iq->ns_prepend_last)
506 		iq->ns_prepend_last->next = p;
507 	else	iq->ns_prepend_list = p;
508 	iq->ns_prepend_last = p;
509 	return 1;
510 }
511 
512 /**
513  * Given a CNAME response (defined as a response containing a CNAME or DNAME
514  * that does not answer the request), process the response, modifying the
515  * state as necessary. This follows the CNAME/DNAME chain and returns the
516  * final query name.
517  *
518  * sets the new query name, after following the CNAME/DNAME chain.
519  * @param qstate: query state.
520  * @param iq: iterator query state.
521  * @param msg: the response.
522  * @param mname: returned target new query name.
523  * @param mname_len: length of mname.
524  * @return false on (malloc) error.
525  */
526 static int
527 handle_cname_response(struct module_qstate* qstate, struct iter_qstate* iq,
528         struct dns_msg* msg, uint8_t** mname, size_t* mname_len)
529 {
530 	size_t i;
531 	/* Start with the (current) qname. */
532 	*mname = iq->qchase.qname;
533 	*mname_len = iq->qchase.qname_len;
534 
535 	/* Iterate over the ANSWER rrsets in order, looking for CNAMEs and
536 	 * DNAMES. */
537 	for(i=0; i<msg->rep->an_numrrsets; i++) {
538 		struct ub_packed_rrset_key* r = msg->rep->rrsets[i];
539 		/* If there is a (relevant) DNAME, add it to the list.
540 		 * We always expect there to be CNAME that was generated
541 		 * by this DNAME following, so we don't process the DNAME
542 		 * directly.  */
543 		if(ntohs(r->rk.type) == LDNS_RR_TYPE_DNAME &&
544 			dname_strict_subdomain_c(*mname, r->rk.dname) &&
545 			!iter_find_rrset_in_prepend_answer(iq, r)) {
546 			if(!iter_add_prepend_answer(qstate, iq, r))
547 				return 0;
548 			continue;
549 		}
550 
551 		if(ntohs(r->rk.type) == LDNS_RR_TYPE_CNAME &&
552 			query_dname_compare(*mname, r->rk.dname) == 0 &&
553 			!iter_find_rrset_in_prepend_answer(iq, r)) {
554 			/* Add this relevant CNAME rrset to the prepend list.*/
555 			if(!iter_add_prepend_answer(qstate, iq, r))
556 				return 0;
557 			get_cname_target(r, mname, mname_len);
558 		}
559 
560 		/* Other rrsets in the section are ignored. */
561 	}
562 	/* add authority rrsets to authority prepend, for wildcarded CNAMEs */
563 	for(i=msg->rep->an_numrrsets; i<msg->rep->an_numrrsets +
564 		msg->rep->ns_numrrsets; i++) {
565 		struct ub_packed_rrset_key* r = msg->rep->rrsets[i];
566 		/* only add NSEC/NSEC3, as they may be needed for validation */
567 		if(ntohs(r->rk.type) == LDNS_RR_TYPE_NSEC ||
568 			ntohs(r->rk.type) == LDNS_RR_TYPE_NSEC3) {
569 			if(!iter_add_prepend_auth(qstate, iq, r))
570 				return 0;
571 		}
572 	}
573 	return 1;
574 }
575 
576 /** see if last resort is possible - does config allow queries to parent */
577 static int
578 can_have_last_resort(struct module_env* env, uint8_t* nm, size_t nmlen,
579 	uint16_t qclass, struct delegpt** retdp)
580 {
581 	struct delegpt* fwddp;
582 	struct iter_hints_stub* stub;
583 	int labs = dname_count_labels(nm);
584 	/* do not process a last resort (the parent side) if a stub
585 	 * or forward is configured, because we do not want to go 'above'
586 	 * the configured servers */
587 	if(!dname_is_root(nm) && (stub = (struct iter_hints_stub*)
588 		name_tree_find(&env->hints->tree, nm, nmlen, labs, qclass)) &&
589 		/* has_parent side is turned off for stub_first, where we
590 		 * are allowed to go to the parent */
591 		stub->dp->has_parent_side_NS) {
592 		if(retdp) *retdp = stub->dp;
593 		return 0;
594 	}
595 	if((fwddp = forwards_find(env->fwds, nm, qclass)) &&
596 		/* has_parent_side is turned off for forward_first, where
597 		 * we are allowed to go to the parent */
598 		fwddp->has_parent_side_NS) {
599 		if(retdp) *retdp = fwddp;
600 		return 0;
601 	}
602 	return 1;
603 }
604 
605 /** see if target name is caps-for-id whitelisted */
606 static int
607 is_caps_whitelisted(struct iter_env* ie, struct iter_qstate* iq)
608 {
609 	if(!ie->caps_white) return 0; /* no whitelist, or no capsforid */
610 	return name_tree_lookup(ie->caps_white, iq->qchase.qname,
611 		iq->qchase.qname_len, dname_count_labels(iq->qchase.qname),
612 		iq->qchase.qclass) != NULL;
613 }
614 
615 /** create target count structure for this query */
616 static void
617 target_count_create(struct iter_qstate* iq)
618 {
619 	if(!iq->target_count) {
620 		iq->target_count = (int*)calloc(2, sizeof(int));
621 		/* if calloc fails we simply do not track this number */
622 		if(iq->target_count)
623 			iq->target_count[0] = 1;
624 	}
625 }
626 
627 static void
628 target_count_increase(struct iter_qstate* iq, int num)
629 {
630 	target_count_create(iq);
631 	if(iq->target_count)
632 		iq->target_count[1] += num;
633 }
634 
635 /**
636  * Generate a subrequest.
637  * Generate a local request event. Local events are tied to this module, and
638  * have a corresponding (first tier) event that is waiting for this event to
639  * resolve to continue.
640  *
641  * @param qname The query name for this request.
642  * @param qnamelen length of qname
643  * @param qtype The query type for this request.
644  * @param qclass The query class for this request.
645  * @param qstate The event that is generating this event.
646  * @param id: module id.
647  * @param iq: The iterator state that is generating this event.
648  * @param initial_state The initial response state (normally this
649  *          is QUERY_RESP_STATE, unless it is known that the request won't
650  *          need iterative processing
651  * @param finalstate The final state for the response to this request.
652  * @param subq_ret: if newly allocated, the subquerystate, or NULL if it does
653  * 	not need initialisation.
654  * @param v: if true, validation is done on the subquery.
655  * @return false on error (malloc).
656  */
657 static int
658 generate_sub_request(uint8_t* qname, size_t qnamelen, uint16_t qtype,
659 	uint16_t qclass, struct module_qstate* qstate, int id,
660 	struct iter_qstate* iq, enum iter_state initial_state,
661 	enum iter_state finalstate, struct module_qstate** subq_ret, int v)
662 {
663 	struct module_qstate* subq = NULL;
664 	struct iter_qstate* subiq = NULL;
665 	uint16_t qflags = 0; /* OPCODE QUERY, no flags */
666 	struct query_info qinf;
667 	int prime = (finalstate == PRIME_RESP_STATE)?1:0;
668 	int valrec = 0;
669 	qinf.qname = qname;
670 	qinf.qname_len = qnamelen;
671 	qinf.qtype = qtype;
672 	qinf.qclass = qclass;
673 	qinf.local_alias = NULL;
674 
675 	/* RD should be set only when sending the query back through the INIT
676 	 * state. */
677 	if(initial_state == INIT_REQUEST_STATE)
678 		qflags |= BIT_RD;
679 	/* We set the CD flag so we can send this through the "head" of
680 	 * the resolution chain, which might have a validator. We are
681 	 * uninterested in validating things not on the direct resolution
682 	 * path.  */
683 	if(!v) {
684 		qflags |= BIT_CD;
685 		valrec = 1;
686 	}
687 
688 	/* attach subquery, lookup existing or make a new one */
689 	fptr_ok(fptr_whitelist_modenv_attach_sub(qstate->env->attach_sub));
690 	if(!(*qstate->env->attach_sub)(qstate, &qinf, qflags, prime, valrec,
691 		&subq)) {
692 		return 0;
693 	}
694 	*subq_ret = subq;
695 	if(subq) {
696 		/* initialise the new subquery */
697 		subq->curmod = id;
698 		subq->ext_state[id] = module_state_initial;
699 		subq->minfo[id] = regional_alloc(subq->region,
700 			sizeof(struct iter_qstate));
701 		if(!subq->minfo[id]) {
702 			log_err("init subq: out of memory");
703 			fptr_ok(fptr_whitelist_modenv_kill_sub(
704 				qstate->env->kill_sub));
705 			(*qstate->env->kill_sub)(subq);
706 			return 0;
707 		}
708 		subiq = (struct iter_qstate*)subq->minfo[id];
709 		memset(subiq, 0, sizeof(*subiq));
710 		subiq->num_target_queries = 0;
711 		target_count_create(iq);
712 		subiq->target_count = iq->target_count;
713 		if(iq->target_count)
714 			iq->target_count[0] ++; /* extra reference */
715 		subiq->num_current_queries = 0;
716 		subiq->depth = iq->depth+1;
717 		outbound_list_init(&subiq->outlist);
718 		subiq->state = initial_state;
719 		subiq->final_state = finalstate;
720 		subiq->qchase = subq->qinfo;
721 		subiq->chase_flags = subq->query_flags;
722 		subiq->refetch_glue = 0;
723 		if(qstate->env->cfg->qname_minimisation)
724 			subiq->minimisation_state = INIT_MINIMISE_STATE;
725 		else
726 			subiq->minimisation_state = DONOT_MINIMISE_STATE;
727 		memset(&subiq->qinfo_out, 0, sizeof(struct query_info));
728 	}
729 	return 1;
730 }
731 
732 /**
733  * Generate and send a root priming request.
734  * @param qstate: the qtstate that triggered the need to prime.
735  * @param iq: iterator query state.
736  * @param id: module id.
737  * @param qclass: the class to prime.
738  * @return 0 on failure
739  */
740 static int
741 prime_root(struct module_qstate* qstate, struct iter_qstate* iq, int id,
742 	uint16_t qclass)
743 {
744 	struct delegpt* dp;
745 	struct module_qstate* subq;
746 	verbose(VERB_DETAIL, "priming . %s NS",
747 		sldns_lookup_by_id(sldns_rr_classes, (int)qclass)?
748 		sldns_lookup_by_id(sldns_rr_classes, (int)qclass)->name:"??");
749 	dp = hints_lookup_root(qstate->env->hints, qclass);
750 	if(!dp) {
751 		verbose(VERB_ALGO, "Cannot prime due to lack of hints");
752 		return 0;
753 	}
754 	/* Priming requests start at the QUERYTARGETS state, skipping
755 	 * the normal INIT state logic (which would cause an infloop). */
756 	if(!generate_sub_request((uint8_t*)"\000", 1, LDNS_RR_TYPE_NS,
757 		qclass, qstate, id, iq, QUERYTARGETS_STATE, PRIME_RESP_STATE,
758 		&subq, 0)) {
759 		verbose(VERB_ALGO, "could not prime root");
760 		return 0;
761 	}
762 	if(subq) {
763 		struct iter_qstate* subiq =
764 			(struct iter_qstate*)subq->minfo[id];
765 		/* Set the initial delegation point to the hint.
766 		 * copy dp, it is now part of the root prime query.
767 		 * dp was part of in the fixed hints structure. */
768 		subiq->dp = delegpt_copy(dp, subq->region);
769 		if(!subiq->dp) {
770 			log_err("out of memory priming root, copydp");
771 			fptr_ok(fptr_whitelist_modenv_kill_sub(
772 				qstate->env->kill_sub));
773 			(*qstate->env->kill_sub)(subq);
774 			return 0;
775 		}
776 		/* there should not be any target queries. */
777 		subiq->num_target_queries = 0;
778 		subiq->dnssec_expected = iter_indicates_dnssec(
779 			qstate->env, subiq->dp, NULL, subq->qinfo.qclass);
780 	}
781 
782 	/* this module stops, our submodule starts, and does the query. */
783 	qstate->ext_state[id] = module_wait_subquery;
784 	return 1;
785 }
786 
787 /**
788  * Generate and process a stub priming request. This method tests for the
789  * need to prime a stub zone, so it is safe to call for every request.
790  *
791  * @param qstate: the qtstate that triggered the need to prime.
792  * @param iq: iterator query state.
793  * @param id: module id.
794  * @param qname: request name.
795  * @param qclass: request class.
796  * @return true if a priming subrequest was made, false if not. The will only
797  *         issue a priming request if it detects an unprimed stub.
798  *         Uses value of 2 to signal during stub-prime in root-prime situation
799  *         that a noprime-stub is available and resolution can continue.
800  */
801 static int
802 prime_stub(struct module_qstate* qstate, struct iter_qstate* iq, int id,
803 	uint8_t* qname, uint16_t qclass)
804 {
805 	/* Lookup the stub hint. This will return null if the stub doesn't
806 	 * need to be re-primed. */
807 	struct iter_hints_stub* stub;
808 	struct delegpt* stub_dp;
809 	struct module_qstate* subq;
810 
811 	if(!qname) return 0;
812 	stub = hints_lookup_stub(qstate->env->hints, qname, qclass, iq->dp);
813 	/* The stub (if there is one) does not need priming. */
814 	if(!stub)
815 		return 0;
816 	stub_dp = stub->dp;
817 	/* if we have an auth_zone dp, and stub is equal, don't prime stub
818 	 * yet, unless we want to fallback and avoid the auth_zone */
819 	if(!iq->auth_zone_avoid && iq->dp && iq->dp->auth_dp &&
820 		query_dname_compare(iq->dp->name, stub_dp->name) == 0)
821 		return 0;
822 
823 	/* is it a noprime stub (always use) */
824 	if(stub->noprime) {
825 		int r = 0;
826 		if(iq->dp == NULL) r = 2;
827 		/* copy the dp out of the fixed hints structure, so that
828 		 * it can be changed when servicing this query */
829 		iq->dp = delegpt_copy(stub_dp, qstate->region);
830 		if(!iq->dp) {
831 			log_err("out of memory priming stub");
832 			errinf(qstate, "malloc failure, priming stub");
833 			(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
834 			return 1; /* return 1 to make module stop, with error */
835 		}
836 		log_nametypeclass(VERB_DETAIL, "use stub", stub_dp->name,
837 			LDNS_RR_TYPE_NS, qclass);
838 		return r;
839 	}
840 
841 	/* Otherwise, we need to (re)prime the stub. */
842 	log_nametypeclass(VERB_DETAIL, "priming stub", stub_dp->name,
843 		LDNS_RR_TYPE_NS, qclass);
844 
845 	/* Stub priming events start at the QUERYTARGETS state to avoid the
846 	 * redundant INIT state processing. */
847 	if(!generate_sub_request(stub_dp->name, stub_dp->namelen,
848 		LDNS_RR_TYPE_NS, qclass, qstate, id, iq,
849 		QUERYTARGETS_STATE, PRIME_RESP_STATE, &subq, 0)) {
850 		verbose(VERB_ALGO, "could not prime stub");
851 		errinf(qstate, "could not generate lookup for stub prime");
852 		(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
853 		return 1; /* return 1 to make module stop, with error */
854 	}
855 	if(subq) {
856 		struct iter_qstate* subiq =
857 			(struct iter_qstate*)subq->minfo[id];
858 
859 		/* Set the initial delegation point to the hint. */
860 		/* make copy to avoid use of stub dp by different qs/threads */
861 		subiq->dp = delegpt_copy(stub_dp, subq->region);
862 		if(!subiq->dp) {
863 			log_err("out of memory priming stub, copydp");
864 			fptr_ok(fptr_whitelist_modenv_kill_sub(
865 				qstate->env->kill_sub));
866 			(*qstate->env->kill_sub)(subq);
867 			errinf(qstate, "malloc failure, in stub prime");
868 			(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
869 			return 1; /* return 1 to make module stop, with error */
870 		}
871 		/* there should not be any target queries -- although there
872 		 * wouldn't be anyway, since stub hints never have
873 		 * missing targets. */
874 		subiq->num_target_queries = 0;
875 		subiq->wait_priming_stub = 1;
876 		subiq->dnssec_expected = iter_indicates_dnssec(
877 			qstate->env, subiq->dp, NULL, subq->qinfo.qclass);
878 	}
879 
880 	/* this module stops, our submodule starts, and does the query. */
881 	qstate->ext_state[id] = module_wait_subquery;
882 	return 1;
883 }
884 
885 /**
886  * Generate a delegation point for an auth zone (unless cached dp is better)
887  * false on alloc failure.
888  */
889 static int
890 auth_zone_delegpt(struct module_qstate* qstate, struct iter_qstate* iq,
891 	uint8_t* delname, size_t delnamelen)
892 {
893 	struct auth_zone* z;
894 	if(iq->auth_zone_avoid)
895 		return 1;
896 	if(!delname) {
897 		delname = iq->qchase.qname;
898 		delnamelen = iq->qchase.qname_len;
899 	}
900 	lock_rw_rdlock(&qstate->env->auth_zones->lock);
901 	z = auth_zones_find_zone(qstate->env->auth_zones, delname, delnamelen,
902 		qstate->qinfo.qclass);
903 	if(!z) {
904 		lock_rw_unlock(&qstate->env->auth_zones->lock);
905 		return 1;
906 	}
907 	lock_rw_rdlock(&z->lock);
908 	lock_rw_unlock(&qstate->env->auth_zones->lock);
909 	if(z->for_upstream) {
910 		if(iq->dp && query_dname_compare(z->name, iq->dp->name) == 0
911 			&& iq->dp->auth_dp && qstate->blacklist &&
912 			z->fallback_enabled) {
913 			/* cache is blacklisted and fallback, and we
914 			 * already have an auth_zone dp */
915 			if(verbosity>=VERB_ALGO) {
916 				char buf[255+1];
917 				dname_str(z->name, buf);
918 				verbose(VERB_ALGO, "auth_zone %s "
919 				  "fallback because cache blacklisted",
920 				  buf);
921 			}
922 			lock_rw_unlock(&z->lock);
923 			iq->dp = NULL;
924 			return 1;
925 		}
926 		if(iq->dp==NULL || dname_subdomain_c(z->name, iq->dp->name)) {
927 			struct delegpt* dp;
928 			if(qstate->blacklist && z->fallback_enabled) {
929 				/* cache is blacklisted because of a DNSSEC
930 				 * validation failure, and the zone allows
931 				 * fallback to the internet, query there. */
932 				if(verbosity>=VERB_ALGO) {
933 					char buf[255+1];
934 					dname_str(z->name, buf);
935 					verbose(VERB_ALGO, "auth_zone %s "
936 					  "fallback because cache blacklisted",
937 					  buf);
938 				}
939 				lock_rw_unlock(&z->lock);
940 				return 1;
941 			}
942 			dp = (struct delegpt*)regional_alloc_zero(
943 				qstate->region, sizeof(*dp));
944 			if(!dp) {
945 				log_err("alloc failure");
946 				if(z->fallback_enabled) {
947 					lock_rw_unlock(&z->lock);
948 					return 1; /* just fallback */
949 				}
950 				lock_rw_unlock(&z->lock);
951 				errinf(qstate, "malloc failure");
952 				return 0;
953 			}
954 			dp->name = regional_alloc_init(qstate->region,
955 				z->name, z->namelen);
956 			if(!dp->name) {
957 				log_err("alloc failure");
958 				if(z->fallback_enabled) {
959 					lock_rw_unlock(&z->lock);
960 					return 1; /* just fallback */
961 				}
962 				lock_rw_unlock(&z->lock);
963 				errinf(qstate, "malloc failure");
964 				return 0;
965 			}
966 			dp->namelen = z->namelen;
967 			dp->namelabs = z->namelabs;
968 			dp->auth_dp = 1;
969 			iq->dp = dp;
970 		}
971 	}
972 
973 	lock_rw_unlock(&z->lock);
974 	return 1;
975 }
976 
977 /**
978  * Generate A and AAAA checks for glue that is in-zone for the referral
979  * we just got to obtain authoritative information on the addresses.
980  *
981  * @param qstate: the qtstate that triggered the need to prime.
982  * @param iq: iterator query state.
983  * @param id: module id.
984  */
985 static void
986 generate_a_aaaa_check(struct module_qstate* qstate, struct iter_qstate* iq,
987 	int id)
988 {
989 	struct iter_env* ie = (struct iter_env*)qstate->env->modinfo[id];
990 	struct module_qstate* subq;
991 	size_t i;
992 	struct reply_info* rep = iq->response->rep;
993 	struct ub_packed_rrset_key* s;
994 	log_assert(iq->dp);
995 
996 	if(iq->depth == ie->max_dependency_depth)
997 		return;
998 	/* walk through additional, and check if in-zone,
999 	 * only relevant A, AAAA are left after scrub anyway */
1000 	for(i=rep->an_numrrsets+rep->ns_numrrsets; i<rep->rrset_count; i++) {
1001 		s = rep->rrsets[i];
1002 		/* check *ALL* addresses that are transmitted in additional*/
1003 		/* is it an address ? */
1004 		if( !(ntohs(s->rk.type)==LDNS_RR_TYPE_A ||
1005 			ntohs(s->rk.type)==LDNS_RR_TYPE_AAAA)) {
1006 			continue;
1007 		}
1008 		/* is this query the same as the A/AAAA check for it */
1009 		if(qstate->qinfo.qtype == ntohs(s->rk.type) &&
1010 			qstate->qinfo.qclass == ntohs(s->rk.rrset_class) &&
1011 			query_dname_compare(qstate->qinfo.qname,
1012 				s->rk.dname)==0 &&
1013 			(qstate->query_flags&BIT_RD) &&
1014 			!(qstate->query_flags&BIT_CD))
1015 			continue;
1016 
1017 		/* generate subrequest for it */
1018 		log_nametypeclass(VERB_ALGO, "schedule addr fetch",
1019 			s->rk.dname, ntohs(s->rk.type),
1020 			ntohs(s->rk.rrset_class));
1021 		if(!generate_sub_request(s->rk.dname, s->rk.dname_len,
1022 			ntohs(s->rk.type), ntohs(s->rk.rrset_class),
1023 			qstate, id, iq,
1024 			INIT_REQUEST_STATE, FINISHED_STATE, &subq, 1)) {
1025 			verbose(VERB_ALGO, "could not generate addr check");
1026 			return;
1027 		}
1028 		/* ignore subq - not need for more init */
1029 	}
1030 }
1031 
1032 /**
1033  * Generate a NS check request to obtain authoritative information
1034  * on an NS rrset.
1035  *
1036  * @param qstate: the qtstate that triggered the need to prime.
1037  * @param iq: iterator query state.
1038  * @param id: module id.
1039  */
1040 static void
1041 generate_ns_check(struct module_qstate* qstate, struct iter_qstate* iq, int id)
1042 {
1043 	struct iter_env* ie = (struct iter_env*)qstate->env->modinfo[id];
1044 	struct module_qstate* subq;
1045 	log_assert(iq->dp);
1046 
1047 	if(iq->depth == ie->max_dependency_depth)
1048 		return;
1049 	if(!can_have_last_resort(qstate->env, iq->dp->name, iq->dp->namelen,
1050 		iq->qchase.qclass, NULL))
1051 		return;
1052 	/* is this query the same as the nscheck? */
1053 	if(qstate->qinfo.qtype == LDNS_RR_TYPE_NS &&
1054 		query_dname_compare(iq->dp->name, qstate->qinfo.qname)==0 &&
1055 		(qstate->query_flags&BIT_RD) && !(qstate->query_flags&BIT_CD)){
1056 		/* spawn off A, AAAA queries for in-zone glue to check */
1057 		generate_a_aaaa_check(qstate, iq, id);
1058 		return;
1059 	}
1060 	/* no need to get the NS record for DS, it is above the zonecut */
1061 	if(qstate->qinfo.qtype == LDNS_RR_TYPE_DS)
1062 		return;
1063 
1064 	log_nametypeclass(VERB_ALGO, "schedule ns fetch",
1065 		iq->dp->name, LDNS_RR_TYPE_NS, iq->qchase.qclass);
1066 	if(!generate_sub_request(iq->dp->name, iq->dp->namelen,
1067 		LDNS_RR_TYPE_NS, iq->qchase.qclass, qstate, id, iq,
1068 		INIT_REQUEST_STATE, FINISHED_STATE, &subq, 1)) {
1069 		verbose(VERB_ALGO, "could not generate ns check");
1070 		return;
1071 	}
1072 	if(subq) {
1073 		struct iter_qstate* subiq =
1074 			(struct iter_qstate*)subq->minfo[id];
1075 
1076 		/* make copy to avoid use of stub dp by different qs/threads */
1077 		/* refetch glue to start higher up the tree */
1078 		subiq->refetch_glue = 1;
1079 		subiq->dp = delegpt_copy(iq->dp, subq->region);
1080 		if(!subiq->dp) {
1081 			log_err("out of memory generating ns check, copydp");
1082 			fptr_ok(fptr_whitelist_modenv_kill_sub(
1083 				qstate->env->kill_sub));
1084 			(*qstate->env->kill_sub)(subq);
1085 			return;
1086 		}
1087 	}
1088 }
1089 
1090 /**
1091  * Generate a DNSKEY prefetch query to get the DNSKEY for the DS record we
1092  * just got in a referral (where we have dnssec_expected, thus have trust
1093  * anchors above it).  Note that right after calling this routine the
1094  * iterator detached subqueries (because of following the referral), and thus
1095  * the DNSKEY query becomes detached, its return stored in the cache for
1096  * later lookup by the validator.  This cache lookup by the validator avoids
1097  * the roundtrip incurred by the DNSKEY query.  The DNSKEY query is now
1098  * performed at about the same time the original query is sent to the domain,
1099  * thus the two answers are likely to be returned at about the same time,
1100  * saving a roundtrip from the validated lookup.
1101  *
1102  * @param qstate: the qtstate that triggered the need to prime.
1103  * @param iq: iterator query state.
1104  * @param id: module id.
1105  */
1106 static void
1107 generate_dnskey_prefetch(struct module_qstate* qstate,
1108 	struct iter_qstate* iq, int id)
1109 {
1110 	struct module_qstate* subq;
1111 	log_assert(iq->dp);
1112 
1113 	/* is this query the same as the prefetch? */
1114 	if(qstate->qinfo.qtype == LDNS_RR_TYPE_DNSKEY &&
1115 		query_dname_compare(iq->dp->name, qstate->qinfo.qname)==0 &&
1116 		(qstate->query_flags&BIT_RD) && !(qstate->query_flags&BIT_CD)){
1117 		return;
1118 	}
1119 
1120 	/* if the DNSKEY is in the cache this lookup will stop quickly */
1121 	log_nametypeclass(VERB_ALGO, "schedule dnskey prefetch",
1122 		iq->dp->name, LDNS_RR_TYPE_DNSKEY, iq->qchase.qclass);
1123 	if(!generate_sub_request(iq->dp->name, iq->dp->namelen,
1124 		LDNS_RR_TYPE_DNSKEY, iq->qchase.qclass, qstate, id, iq,
1125 		INIT_REQUEST_STATE, FINISHED_STATE, &subq, 0)) {
1126 		/* we'll be slower, but it'll work */
1127 		verbose(VERB_ALGO, "could not generate dnskey prefetch");
1128 		return;
1129 	}
1130 	if(subq) {
1131 		struct iter_qstate* subiq =
1132 			(struct iter_qstate*)subq->minfo[id];
1133 		/* this qstate has the right delegation for the dnskey lookup*/
1134 		/* make copy to avoid use of stub dp by different qs/threads */
1135 		subiq->dp = delegpt_copy(iq->dp, subq->region);
1136 		/* if !subiq->dp, it'll start from the cache, no problem */
1137 	}
1138 }
1139 
1140 /**
1141  * See if the query needs forwarding.
1142  *
1143  * @param qstate: query state.
1144  * @param iq: iterator query state.
1145  * @return true if the request is forwarded, false if not.
1146  * 	If returns true but, iq->dp is NULL then a malloc failure occurred.
1147  */
1148 static int
1149 forward_request(struct module_qstate* qstate, struct iter_qstate* iq)
1150 {
1151 	struct delegpt* dp;
1152 	uint8_t* delname = iq->qchase.qname;
1153 	size_t delnamelen = iq->qchase.qname_len;
1154 	if(iq->refetch_glue && iq->dp) {
1155 		delname = iq->dp->name;
1156 		delnamelen = iq->dp->namelen;
1157 	}
1158 	/* strip one label off of DS query to lookup higher for it */
1159 	if( (iq->qchase.qtype == LDNS_RR_TYPE_DS || iq->refetch_glue)
1160 		&& !dname_is_root(iq->qchase.qname))
1161 		dname_remove_label(&delname, &delnamelen);
1162 	dp = forwards_lookup(qstate->env->fwds, delname, iq->qchase.qclass);
1163 	if(!dp)
1164 		return 0;
1165 	/* send recursion desired to forward addr */
1166 	iq->chase_flags |= BIT_RD;
1167 	iq->dp = delegpt_copy(dp, qstate->region);
1168 	/* iq->dp checked by caller */
1169 	verbose(VERB_ALGO, "forwarding request");
1170 	return 1;
1171 }
1172 
1173 /**
1174  * Process the initial part of the request handling. This state roughly
1175  * corresponds to resolver algorithms steps 1 (find answer in cache) and 2
1176  * (find the best servers to ask).
1177  *
1178  * Note that all requests start here, and query restarts revisit this state.
1179  *
1180  * This state either generates: 1) a response, from cache or error, 2) a
1181  * priming event, or 3) forwards the request to the next state (init2,
1182  * generally).
1183  *
1184  * @param qstate: query state.
1185  * @param iq: iterator query state.
1186  * @param ie: iterator shared global environment.
1187  * @param id: module id.
1188  * @return true if the event needs more request processing immediately,
1189  *         false if not.
1190  */
1191 static int
1192 processInitRequest(struct module_qstate* qstate, struct iter_qstate* iq,
1193 	struct iter_env* ie, int id)
1194 {
1195 	uint8_t* delname;
1196 	size_t delnamelen;
1197 	struct dns_msg* msg = NULL;
1198 
1199 	log_query_info(VERB_DETAIL, "resolving", &qstate->qinfo);
1200 	/* check effort */
1201 
1202 	/* We enforce a maximum number of query restarts. This is primarily a
1203 	 * cheap way to prevent CNAME loops. */
1204 	if(iq->query_restart_count > MAX_RESTART_COUNT) {
1205 		verbose(VERB_QUERY, "request has exceeded the maximum number"
1206 			" of query restarts with %d", iq->query_restart_count);
1207 		errinf(qstate, "request has exceeded the maximum number "
1208 			"restarts (eg. indirections)");
1209 		if(iq->qchase.qname)
1210 			errinf_dname(qstate, "stop at", iq->qchase.qname);
1211 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1212 	}
1213 
1214 	/* We enforce a maximum recursion/dependency depth -- in general,
1215 	 * this is unnecessary for dependency loops (although it will
1216 	 * catch those), but it provides a sensible limit to the amount
1217 	 * of work required to answer a given query. */
1218 	verbose(VERB_ALGO, "request has dependency depth of %d", iq->depth);
1219 	if(iq->depth > ie->max_dependency_depth) {
1220 		verbose(VERB_QUERY, "request has exceeded the maximum "
1221 			"dependency depth with depth of %d", iq->depth);
1222 		errinf(qstate, "request has exceeded the maximum dependency "
1223 			"depth (eg. nameserver lookup recursion)");
1224 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1225 	}
1226 
1227 	/* If the request is qclass=ANY, setup to generate each class */
1228 	if(qstate->qinfo.qclass == LDNS_RR_CLASS_ANY) {
1229 		iq->qchase.qclass = 0;
1230 		return next_state(iq, COLLECT_CLASS_STATE);
1231 	}
1232 
1233 	/*
1234 	 * If we are restricted by a forward-zone or a stub-zone, we
1235 	 * can't re-fetch glue for this delegation point.
1236 	 * we won’t try to re-fetch glue if the iq->dp is null.
1237 	 */
1238 	if (iq->refetch_glue &&
1239 	        iq->dp &&
1240 	        !can_have_last_resort(qstate->env, iq->dp->name,
1241 	             iq->dp->namelen, iq->qchase.qclass, NULL)) {
1242 	    iq->refetch_glue = 0;
1243 	}
1244 
1245 	/* Resolver Algorithm Step 1 -- Look for the answer in local data. */
1246 
1247 	/* This either results in a query restart (CNAME cache response), a
1248 	 * terminating response (ANSWER), or a cache miss (null). */
1249 
1250 	if (iter_stub_fwd_no_cache(qstate, &iq->qchase)) {
1251 		/* Asked to not query cache. */
1252 		verbose(VERB_ALGO, "no-cache set, going to the network");
1253 		qstate->no_cache_lookup = 1;
1254 		qstate->no_cache_store = 1;
1255 		msg = NULL;
1256 	} else if(qstate->blacklist) {
1257 		/* if cache, or anything else, was blacklisted then
1258 		 * getting older results from cache is a bad idea, no cache */
1259 		verbose(VERB_ALGO, "cache blacklisted, going to the network");
1260 		msg = NULL;
1261 	} else if(!qstate->no_cache_lookup) {
1262 		msg = dns_cache_lookup(qstate->env, iq->qchase.qname,
1263 			iq->qchase.qname_len, iq->qchase.qtype,
1264 			iq->qchase.qclass, qstate->query_flags,
1265 			qstate->region, qstate->env->scratch, 0);
1266 		if(!msg && qstate->env->neg_cache &&
1267 			iter_qname_indicates_dnssec(qstate->env, &iq->qchase)) {
1268 			/* lookup in negative cache; may result in
1269 			 * NOERROR/NODATA or NXDOMAIN answers that need validation */
1270 			msg = val_neg_getmsg(qstate->env->neg_cache, &iq->qchase,
1271 				qstate->region, qstate->env->rrset_cache,
1272 				qstate->env->scratch_buffer,
1273 				*qstate->env->now, 1/*add SOA*/, NULL,
1274 				qstate->env->cfg);
1275 		}
1276 		/* item taken from cache does not match our query name, thus
1277 		 * security needs to be re-examined later */
1278 		if(msg && query_dname_compare(qstate->qinfo.qname,
1279 			iq->qchase.qname) != 0)
1280 			msg->rep->security = sec_status_unchecked;
1281 	}
1282 	if(msg) {
1283 		/* handle positive cache response */
1284 		enum response_type type = response_type_from_cache(msg,
1285 			&iq->qchase);
1286 		if(verbosity >= VERB_ALGO) {
1287 			log_dns_msg("msg from cache lookup", &msg->qinfo,
1288 				msg->rep);
1289 			verbose(VERB_ALGO, "msg ttl is %d, prefetch ttl %d",
1290 				(int)msg->rep->ttl,
1291 				(int)msg->rep->prefetch_ttl);
1292 		}
1293 
1294 		if(type == RESPONSE_TYPE_CNAME) {
1295 			uint8_t* sname = 0;
1296 			size_t slen = 0;
1297 			verbose(VERB_ALGO, "returning CNAME response from "
1298 				"cache");
1299 			if(!handle_cname_response(qstate, iq, msg,
1300 				&sname, &slen)) {
1301 				errinf(qstate, "failed to prepend CNAME "
1302 					"components, malloc failure");
1303 				return error_response(qstate, id,
1304 					LDNS_RCODE_SERVFAIL);
1305 			}
1306 			iq->qchase.qname = sname;
1307 			iq->qchase.qname_len = slen;
1308 			/* This *is* a query restart, even if it is a cheap
1309 			 * one. */
1310 			iq->dp = NULL;
1311 			iq->refetch_glue = 0;
1312 			iq->query_restart_count++;
1313 			iq->sent_count = 0;
1314 			sock_list_insert(&qstate->reply_origin, NULL, 0, qstate->region);
1315 			if(qstate->env->cfg->qname_minimisation)
1316 				iq->minimisation_state = INIT_MINIMISE_STATE;
1317 			return next_state(iq, INIT_REQUEST_STATE);
1318 		}
1319 
1320 		/* if from cache, NULL, else insert 'cache IP' len=0 */
1321 		if(qstate->reply_origin)
1322 			sock_list_insert(&qstate->reply_origin, NULL, 0, qstate->region);
1323 		if(FLAGS_GET_RCODE(msg->rep->flags) == LDNS_RCODE_SERVFAIL)
1324 			errinf(qstate, "SERVFAIL in cache");
1325 		/* it is an answer, response, to final state */
1326 		verbose(VERB_ALGO, "returning answer from cache.");
1327 		iq->response = msg;
1328 		return final_state(iq);
1329 	}
1330 
1331 	/* attempt to forward the request */
1332 	if(forward_request(qstate, iq))
1333 	{
1334 		if(!iq->dp) {
1335 			log_err("alloc failure for forward dp");
1336 			errinf(qstate, "malloc failure for forward zone");
1337 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1338 		}
1339 		iq->refetch_glue = 0;
1340 		iq->minimisation_state = DONOT_MINIMISE_STATE;
1341 		/* the request has been forwarded.
1342 		 * forwarded requests need to be immediately sent to the
1343 		 * next state, QUERYTARGETS. */
1344 		return next_state(iq, QUERYTARGETS_STATE);
1345 	}
1346 
1347 	/* Resolver Algorithm Step 2 -- find the "best" servers. */
1348 
1349 	/* first, adjust for DS queries. To avoid the grandparent problem,
1350 	 * we just look for the closest set of server to the parent of qname.
1351 	 * When re-fetching glue we also need to ask the parent.
1352 	 */
1353 	if(iq->refetch_glue) {
1354 		if(!iq->dp) {
1355 			log_err("internal or malloc fail: no dp for refetch");
1356 			errinf(qstate, "malloc failure, for delegation info");
1357 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1358 		}
1359 		delname = iq->dp->name;
1360 		delnamelen = iq->dp->namelen;
1361 	} else {
1362 		delname = iq->qchase.qname;
1363 		delnamelen = iq->qchase.qname_len;
1364 	}
1365 	if(iq->qchase.qtype == LDNS_RR_TYPE_DS || iq->refetch_glue ||
1366 	   (iq->qchase.qtype == LDNS_RR_TYPE_NS && qstate->prefetch_leeway
1367 	   && can_have_last_resort(qstate->env, delname, delnamelen, iq->qchase.qclass, NULL))) {
1368 		/* remove first label from delname, root goes to hints,
1369 		 * but only to fetch glue, not for qtype=DS. */
1370 		/* also when prefetching an NS record, fetch it again from
1371 		 * its parent, just as if it expired, so that you do not
1372 		 * get stuck on an older nameserver that gives old NSrecords */
1373 		if(dname_is_root(delname) && (iq->refetch_glue ||
1374 			(iq->qchase.qtype == LDNS_RR_TYPE_NS &&
1375 			qstate->prefetch_leeway)))
1376 			delname = NULL; /* go to root priming */
1377 		else 	dname_remove_label(&delname, &delnamelen);
1378 	}
1379 	/* delname is the name to lookup a delegation for. If NULL rootprime */
1380 	while(1) {
1381 
1382 		/* Lookup the delegation in the cache. If null, then the
1383 		 * cache needs to be primed for the qclass. */
1384 		if(delname)
1385 		     iq->dp = dns_cache_find_delegation(qstate->env, delname,
1386 			delnamelen, iq->qchase.qtype, iq->qchase.qclass,
1387 			qstate->region, &iq->deleg_msg,
1388 			*qstate->env->now+qstate->prefetch_leeway);
1389 		else iq->dp = NULL;
1390 
1391 		/* If the cache has returned nothing, then we have a
1392 		 * root priming situation. */
1393 		if(iq->dp == NULL) {
1394 			int r;
1395 			/* if under auth zone, no prime needed */
1396 			if(!auth_zone_delegpt(qstate, iq, delname, delnamelen))
1397 				return error_response(qstate, id,
1398 					LDNS_RCODE_SERVFAIL);
1399 			if(iq->dp) /* use auth zone dp */
1400 				return next_state(iq, INIT_REQUEST_2_STATE);
1401 			/* if there is a stub, then no root prime needed */
1402 			r = prime_stub(qstate, iq, id, delname,
1403 				iq->qchase.qclass);
1404 			if(r == 2)
1405 				break; /* got noprime-stub-zone, continue */
1406 			else if(r)
1407 				return 0; /* stub prime request made */
1408 			if(forwards_lookup_root(qstate->env->fwds,
1409 				iq->qchase.qclass)) {
1410 				/* forward zone root, no root prime needed */
1411 				/* fill in some dp - safety belt */
1412 				iq->dp = hints_lookup_root(qstate->env->hints,
1413 					iq->qchase.qclass);
1414 				if(!iq->dp) {
1415 					log_err("internal error: no hints dp");
1416 					errinf(qstate, "no hints for this class");
1417 					return error_response(qstate, id,
1418 						LDNS_RCODE_SERVFAIL);
1419 				}
1420 				iq->dp = delegpt_copy(iq->dp, qstate->region);
1421 				if(!iq->dp) {
1422 					log_err("out of memory in safety belt");
1423 					errinf(qstate, "malloc failure, in safety belt");
1424 					return error_response(qstate, id,
1425 						LDNS_RCODE_SERVFAIL);
1426 				}
1427 				return next_state(iq, INIT_REQUEST_2_STATE);
1428 			}
1429 			/* Note that the result of this will set a new
1430 			 * DelegationPoint based on the result of priming. */
1431 			if(!prime_root(qstate, iq, id, iq->qchase.qclass))
1432 				return error_response(qstate, id,
1433 					LDNS_RCODE_REFUSED);
1434 
1435 			/* priming creates and sends a subordinate query, with
1436 			 * this query as the parent. So further processing for
1437 			 * this event will stop until reactivated by the
1438 			 * results of priming. */
1439 			return 0;
1440 		}
1441 		if(!iq->ratelimit_ok && qstate->prefetch_leeway)
1442 			iq->ratelimit_ok = 1; /* allow prefetches, this keeps
1443 			otherwise valid data in the cache */
1444 		if(!iq->ratelimit_ok && infra_ratelimit_exceeded(
1445 			qstate->env->infra_cache, iq->dp->name,
1446 			iq->dp->namelen, *qstate->env->now)) {
1447 			/* and increment the rate, so that the rate for time
1448 			 * now will also exceed the rate, keeping cache fresh */
1449 			(void)infra_ratelimit_inc(qstate->env->infra_cache,
1450 				iq->dp->name, iq->dp->namelen,
1451 				*qstate->env->now, &qstate->qinfo,
1452 				qstate->reply);
1453 			/* see if we are passed through with slip factor */
1454 			if(qstate->env->cfg->ratelimit_factor != 0 &&
1455 				ub_random_max(qstate->env->rnd,
1456 				    qstate->env->cfg->ratelimit_factor) == 1) {
1457 				iq->ratelimit_ok = 1;
1458 				log_nametypeclass(VERB_ALGO, "ratelimit allowed through for "
1459 					"delegation point", iq->dp->name,
1460 					LDNS_RR_TYPE_NS, LDNS_RR_CLASS_IN);
1461 			} else {
1462 				lock_basic_lock(&ie->queries_ratelimit_lock);
1463 				ie->num_queries_ratelimited++;
1464 				lock_basic_unlock(&ie->queries_ratelimit_lock);
1465 				log_nametypeclass(VERB_ALGO, "ratelimit exceeded with "
1466 					"delegation point", iq->dp->name,
1467 					LDNS_RR_TYPE_NS, LDNS_RR_CLASS_IN);
1468 				qstate->was_ratelimited = 1;
1469 				errinf(qstate, "query was ratelimited");
1470 				errinf_dname(qstate, "for zone", iq->dp->name);
1471 				return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1472 			}
1473 		}
1474 
1475 		/* see if this dp not useless.
1476 		 * It is useless if:
1477 		 *	o all NS items are required glue.
1478 		 *	  or the query is for NS item that is required glue.
1479 		 *	o no addresses are provided.
1480 		 *	o RD qflag is on.
1481 		 * Instead, go up one level, and try to get even further
1482 		 * If the root was useless, use safety belt information.
1483 		 * Only check cache returns, because replies for servers
1484 		 * could be useless but lead to loops (bumping into the
1485 		 * same server reply) if useless-checked.
1486 		 */
1487 		if(iter_dp_is_useless(&qstate->qinfo, qstate->query_flags,
1488 			iq->dp)) {
1489 			struct delegpt* retdp = NULL;
1490 			if(!can_have_last_resort(qstate->env, iq->dp->name, iq->dp->namelen, iq->qchase.qclass, &retdp)) {
1491 				if(retdp) {
1492 					verbose(VERB_QUERY, "cache has stub "
1493 						"or fwd but no addresses, "
1494 						"fallback to config");
1495 					iq->dp = delegpt_copy(retdp,
1496 						qstate->region);
1497 					if(!iq->dp) {
1498 						log_err("out of memory in "
1499 							"stub/fwd fallback");
1500 						errinf(qstate, "malloc failure, for fallback to config");
1501 						return error_response(qstate,
1502 						    id, LDNS_RCODE_SERVFAIL);
1503 					}
1504 					break;
1505 				}
1506 				verbose(VERB_ALGO, "useless dp "
1507 					"but cannot go up, servfail");
1508 				delegpt_log(VERB_ALGO, iq->dp);
1509 				errinf(qstate, "no useful nameservers, "
1510 					"and cannot go up");
1511 				errinf_dname(qstate, "for zone", iq->dp->name);
1512 				return error_response(qstate, id,
1513 					LDNS_RCODE_SERVFAIL);
1514 			}
1515 			if(dname_is_root(iq->dp->name)) {
1516 				/* use safety belt */
1517 				verbose(VERB_QUERY, "Cache has root NS but "
1518 				"no addresses. Fallback to the safety belt.");
1519 				iq->dp = hints_lookup_root(qstate->env->hints,
1520 					iq->qchase.qclass);
1521 				/* note deleg_msg is from previous lookup,
1522 				 * but RD is on, so it is not used */
1523 				if(!iq->dp) {
1524 					log_err("internal error: no hints dp");
1525 					return error_response(qstate, id,
1526 						LDNS_RCODE_REFUSED);
1527 				}
1528 				iq->dp = delegpt_copy(iq->dp, qstate->region);
1529 				if(!iq->dp) {
1530 					log_err("out of memory in safety belt");
1531 					errinf(qstate, "malloc failure, in safety belt, for root");
1532 					return error_response(qstate, id,
1533 						LDNS_RCODE_SERVFAIL);
1534 				}
1535 				break;
1536 			} else {
1537 				verbose(VERB_ALGO,
1538 					"cache delegation was useless:");
1539 				delegpt_log(VERB_ALGO, iq->dp);
1540 				/* go up */
1541 				delname = iq->dp->name;
1542 				delnamelen = iq->dp->namelen;
1543 				dname_remove_label(&delname, &delnamelen);
1544 			}
1545 		} else break;
1546 	}
1547 
1548 	verbose(VERB_ALGO, "cache delegation returns delegpt");
1549 	delegpt_log(VERB_ALGO, iq->dp);
1550 
1551 	/* Otherwise, set the current delegation point and move on to the
1552 	 * next state. */
1553 	return next_state(iq, INIT_REQUEST_2_STATE);
1554 }
1555 
1556 /**
1557  * Process the second part of the initial request handling. This state
1558  * basically exists so that queries that generate root priming events have
1559  * the same init processing as ones that do not. Request events that reach
1560  * this state must have a valid currentDelegationPoint set.
1561  *
1562  * This part is primarily handling stub zone priming. Events that reach this
1563  * state must have a current delegation point.
1564  *
1565  * @param qstate: query state.
1566  * @param iq: iterator query state.
1567  * @param id: module id.
1568  * @return true if the event needs more request processing immediately,
1569  *         false if not.
1570  */
1571 static int
1572 processInitRequest2(struct module_qstate* qstate, struct iter_qstate* iq,
1573 	int id)
1574 {
1575 	uint8_t* delname;
1576 	size_t delnamelen;
1577 	log_query_info(VERB_QUERY, "resolving (init part 2): ",
1578 		&qstate->qinfo);
1579 
1580 	delname = iq->qchase.qname;
1581 	delnamelen = iq->qchase.qname_len;
1582 	if(iq->refetch_glue) {
1583 		struct iter_hints_stub* stub;
1584 		if(!iq->dp) {
1585 			log_err("internal or malloc fail: no dp for refetch");
1586 			errinf(qstate, "malloc failure, no delegation info");
1587 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1588 		}
1589 		/* Do not send queries above stub, do not set delname to dp if
1590 		 * this is above stub without stub-first. */
1591 		stub = hints_lookup_stub(
1592 			qstate->env->hints, iq->qchase.qname, iq->qchase.qclass,
1593 			iq->dp);
1594 		if(!stub || !stub->dp->has_parent_side_NS ||
1595 			dname_subdomain_c(iq->dp->name, stub->dp->name)) {
1596 			delname = iq->dp->name;
1597 			delnamelen = iq->dp->namelen;
1598 		}
1599 	}
1600 	if(iq->qchase.qtype == LDNS_RR_TYPE_DS || iq->refetch_glue) {
1601 		if(!dname_is_root(delname))
1602 			dname_remove_label(&delname, &delnamelen);
1603 		iq->refetch_glue = 0; /* if CNAME causes restart, no refetch */
1604 	}
1605 
1606 	/* see if we have an auth zone to answer from, improves dp from cache
1607 	 * (if any dp from cache) with auth zone dp, if that is lower */
1608 	if(!auth_zone_delegpt(qstate, iq, delname, delnamelen))
1609 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1610 
1611 	/* Check to see if we need to prime a stub zone. */
1612 	if(prime_stub(qstate, iq, id, delname, iq->qchase.qclass)) {
1613 		/* A priming sub request was made */
1614 		return 0;
1615 	}
1616 
1617 	/* most events just get forwarded to the next state. */
1618 	return next_state(iq, INIT_REQUEST_3_STATE);
1619 }
1620 
1621 /**
1622  * Process the third part of the initial request handling. This state exists
1623  * as a separate state so that queries that generate stub priming events
1624  * will get the tail end of the init process but not repeat the stub priming
1625  * check.
1626  *
1627  * @param qstate: query state.
1628  * @param iq: iterator query state.
1629  * @param id: module id.
1630  * @return true, advancing the event to the QUERYTARGETS_STATE.
1631  */
1632 static int
1633 processInitRequest3(struct module_qstate* qstate, struct iter_qstate* iq,
1634 	int id)
1635 {
1636 	log_query_info(VERB_QUERY, "resolving (init part 3): ",
1637 		&qstate->qinfo);
1638 	/* if the cache reply dp equals a validation anchor or msg has DS,
1639 	 * then DNSSEC RRSIGs are expected in the reply */
1640 	iq->dnssec_expected = iter_indicates_dnssec(qstate->env, iq->dp,
1641 		iq->deleg_msg, iq->qchase.qclass);
1642 
1643 	/* If the RD flag wasn't set, then we just finish with the
1644 	 * cached referral as the response. */
1645 	if(!(qstate->query_flags & BIT_RD) && iq->deleg_msg) {
1646 		iq->response = iq->deleg_msg;
1647 		if(verbosity >= VERB_ALGO && iq->response)
1648 			log_dns_msg("no RD requested, using delegation msg",
1649 				&iq->response->qinfo, iq->response->rep);
1650 		if(qstate->reply_origin)
1651 			sock_list_insert(&qstate->reply_origin, NULL, 0, qstate->region);
1652 		return final_state(iq);
1653 	}
1654 	/* After this point, unset the RD flag -- this query is going to
1655 	 * be sent to an auth. server. */
1656 	iq->chase_flags &= ~BIT_RD;
1657 
1658 	/* if dnssec expected, fetch key for the trust-anchor or cached-DS */
1659 	if(iq->dnssec_expected && qstate->env->cfg->prefetch_key &&
1660 		!(qstate->query_flags&BIT_CD)) {
1661 		generate_dnskey_prefetch(qstate, iq, id);
1662 		fptr_ok(fptr_whitelist_modenv_detach_subs(
1663 			qstate->env->detach_subs));
1664 		(*qstate->env->detach_subs)(qstate);
1665 	}
1666 
1667 	/* Jump to the next state. */
1668 	return next_state(iq, QUERYTARGETS_STATE);
1669 }
1670 
1671 /**
1672  * Given a basic query, generate a parent-side "target" query.
1673  * These are subordinate queries for missing delegation point target addresses,
1674  * for which only the parent of the delegation provides correct IP addresses.
1675  *
1676  * @param qstate: query state.
1677  * @param iq: iterator query state.
1678  * @param id: module id.
1679  * @param name: target qname.
1680  * @param namelen: target qname length.
1681  * @param qtype: target qtype (either A or AAAA).
1682  * @param qclass: target qclass.
1683  * @return true on success, false on failure.
1684  */
1685 static int
1686 generate_parentside_target_query(struct module_qstate* qstate,
1687 	struct iter_qstate* iq, int id, uint8_t* name, size_t namelen,
1688 	uint16_t qtype, uint16_t qclass)
1689 {
1690 	struct module_qstate* subq;
1691 	if(!generate_sub_request(name, namelen, qtype, qclass, qstate,
1692 		id, iq, INIT_REQUEST_STATE, FINISHED_STATE, &subq, 0))
1693 		return 0;
1694 	if(subq) {
1695 		struct iter_qstate* subiq =
1696 			(struct iter_qstate*)subq->minfo[id];
1697 		/* blacklist the cache - we want to fetch parent stuff */
1698 		sock_list_insert(&subq->blacklist, NULL, 0, subq->region);
1699 		subiq->query_for_pside_glue = 1;
1700 		if(dname_subdomain_c(name, iq->dp->name)) {
1701 			subiq->dp = delegpt_copy(iq->dp, subq->region);
1702 			subiq->dnssec_expected = iter_indicates_dnssec(
1703 				qstate->env, subiq->dp, NULL,
1704 				subq->qinfo.qclass);
1705 			subiq->refetch_glue = 1;
1706 		} else {
1707 			subiq->dp = dns_cache_find_delegation(qstate->env,
1708 				name, namelen, qtype, qclass, subq->region,
1709 				&subiq->deleg_msg,
1710 				*qstate->env->now+subq->prefetch_leeway);
1711 			/* if no dp, then it's from root, refetch unneeded */
1712 			if(subiq->dp) {
1713 				subiq->dnssec_expected = iter_indicates_dnssec(
1714 					qstate->env, subiq->dp, NULL,
1715 					subq->qinfo.qclass);
1716 				subiq->refetch_glue = 1;
1717 			}
1718 		}
1719 	}
1720 	log_nametypeclass(VERB_QUERY, "new pside target", name, qtype, qclass);
1721 	return 1;
1722 }
1723 
1724 /**
1725  * Given a basic query, generate a "target" query. These are subordinate
1726  * queries for missing delegation point target addresses.
1727  *
1728  * @param qstate: query state.
1729  * @param iq: iterator query state.
1730  * @param id: module id.
1731  * @param name: target qname.
1732  * @param namelen: target qname length.
1733  * @param qtype: target qtype (either A or AAAA).
1734  * @param qclass: target qclass.
1735  * @return true on success, false on failure.
1736  */
1737 static int
1738 generate_target_query(struct module_qstate* qstate, struct iter_qstate* iq,
1739         int id, uint8_t* name, size_t namelen, uint16_t qtype, uint16_t qclass)
1740 {
1741 	struct module_qstate* subq;
1742 	if(!generate_sub_request(name, namelen, qtype, qclass, qstate,
1743 		id, iq, INIT_REQUEST_STATE, FINISHED_STATE, &subq, 0))
1744 		return 0;
1745 	log_nametypeclass(VERB_QUERY, "new target", name, qtype, qclass);
1746 	return 1;
1747 }
1748 
1749 /**
1750  * Given an event at a certain state, generate zero or more target queries
1751  * for it's current delegation point.
1752  *
1753  * @param qstate: query state.
1754  * @param iq: iterator query state.
1755  * @param ie: iterator shared global environment.
1756  * @param id: module id.
1757  * @param maxtargets: The maximum number of targets to query for.
1758  *	if it is negative, there is no maximum number of targets.
1759  * @param num: returns the number of queries generated and processed,
1760  *	which may be zero if there were no missing targets.
1761  * @return false on error.
1762  */
1763 static int
1764 query_for_targets(struct module_qstate* qstate, struct iter_qstate* iq,
1765         struct iter_env* ie, int id, int maxtargets, int* num)
1766 {
1767 	int query_count = 0;
1768 	struct delegpt_ns* ns;
1769 	int missing;
1770 	int toget = 0;
1771 
1772 	if(iq->depth == ie->max_dependency_depth)
1773 		return 0;
1774 	if(iq->depth > 0 && iq->target_count &&
1775 		iq->target_count[1] > MAX_TARGET_COUNT) {
1776 		char s[LDNS_MAX_DOMAINLEN+1];
1777 		dname_str(qstate->qinfo.qname, s);
1778 		verbose(VERB_QUERY, "request %s has exceeded the maximum "
1779 			"number of glue fetches %d", s, iq->target_count[1]);
1780 		return 0;
1781 	}
1782 
1783 	iter_mark_cycle_targets(qstate, iq->dp);
1784 	missing = (int)delegpt_count_missing_targets(iq->dp);
1785 	log_assert(maxtargets != 0); /* that would not be useful */
1786 
1787 	/* Generate target requests. Basically, any missing targets
1788 	 * are queried for here, regardless if it is necessary to do
1789 	 * so to continue processing. */
1790 	if(maxtargets < 0 || maxtargets > missing)
1791 		toget = missing;
1792 	else	toget = maxtargets;
1793 	if(toget == 0) {
1794 		*num = 0;
1795 		return 1;
1796 	}
1797 	/* select 'toget' items from the total of 'missing' items */
1798 	log_assert(toget <= missing);
1799 
1800 	/* loop over missing targets */
1801 	for(ns = iq->dp->nslist; ns; ns = ns->next) {
1802 		if(ns->resolved)
1803 			continue;
1804 
1805 		/* randomly select this item with probability toget/missing */
1806 		if(!iter_ns_probability(qstate->env->rnd, toget, missing)) {
1807 			/* do not select this one, next; select toget number
1808 			 * of items from a list one less in size */
1809 			missing --;
1810 			continue;
1811 		}
1812 
1813 		if(ie->supports_ipv6 && !ns->got6) {
1814 			/* Send the AAAA request. */
1815 			if(!generate_target_query(qstate, iq, id,
1816 				ns->name, ns->namelen,
1817 				LDNS_RR_TYPE_AAAA, iq->qchase.qclass)) {
1818 				*num = query_count;
1819 				if(query_count > 0)
1820 					qstate->ext_state[id] = module_wait_subquery;
1821 				return 0;
1822 			}
1823 			query_count++;
1824 		}
1825 		/* Send the A request. */
1826 		if(ie->supports_ipv4 && !ns->got4) {
1827 			if(!generate_target_query(qstate, iq, id,
1828 				ns->name, ns->namelen,
1829 				LDNS_RR_TYPE_A, iq->qchase.qclass)) {
1830 				*num = query_count;
1831 				if(query_count > 0)
1832 					qstate->ext_state[id] = module_wait_subquery;
1833 				return 0;
1834 			}
1835 			query_count++;
1836 		}
1837 
1838 		/* mark this target as in progress. */
1839 		ns->resolved = 1;
1840 		missing--;
1841 		toget--;
1842 		if(toget == 0)
1843 			break;
1844 	}
1845 	*num = query_count;
1846 	if(query_count > 0)
1847 		qstate->ext_state[id] = module_wait_subquery;
1848 
1849 	return 1;
1850 }
1851 
1852 /**
1853  * Called by processQueryTargets when it would like extra targets to query
1854  * but it seems to be out of options.  At last resort some less appealing
1855  * options are explored.  If there are no more options, the result is SERVFAIL
1856  *
1857  * @param qstate: query state.
1858  * @param iq: iterator query state.
1859  * @param ie: iterator shared global environment.
1860  * @param id: module id.
1861  * @return true if the event requires more request processing immediately,
1862  *         false if not.
1863  */
1864 static int
1865 processLastResort(struct module_qstate* qstate, struct iter_qstate* iq,
1866 	struct iter_env* ie, int id)
1867 {
1868 	struct delegpt_ns* ns;
1869 	int query_count = 0;
1870 	verbose(VERB_ALGO, "No more query targets, attempting last resort");
1871 	log_assert(iq->dp);
1872 
1873 	if(!can_have_last_resort(qstate->env, iq->dp->name, iq->dp->namelen,
1874 		iq->qchase.qclass, NULL)) {
1875 		/* fail -- no more targets, no more hope of targets, no hope
1876 		 * of a response. */
1877 		errinf(qstate, "all the configured stub or forward servers failed,");
1878 		errinf_dname(qstate, "at zone", iq->dp->name);
1879 		verbose(VERB_QUERY, "configured stub or forward servers failed -- returning SERVFAIL");
1880 		return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
1881 	}
1882 	if(!iq->dp->has_parent_side_NS && dname_is_root(iq->dp->name)) {
1883 		struct delegpt* p = hints_lookup_root(qstate->env->hints,
1884 			iq->qchase.qclass);
1885 		if(p) {
1886 			struct delegpt_addr* a;
1887 			iq->chase_flags &= ~BIT_RD; /* go to authorities */
1888 			for(ns = p->nslist; ns; ns=ns->next) {
1889 				(void)delegpt_add_ns(iq->dp, qstate->region,
1890 					ns->name, ns->lame);
1891 			}
1892 			for(a = p->target_list; a; a=a->next_target) {
1893 				(void)delegpt_add_addr(iq->dp, qstate->region,
1894 					&a->addr, a->addrlen, a->bogus,
1895 					a->lame, a->tls_auth_name);
1896 			}
1897 		}
1898 		iq->dp->has_parent_side_NS = 1;
1899 	} else if(!iq->dp->has_parent_side_NS) {
1900 		if(!iter_lookup_parent_NS_from_cache(qstate->env, iq->dp,
1901 			qstate->region, &qstate->qinfo)
1902 			|| !iq->dp->has_parent_side_NS) {
1903 			/* if: malloc failure in lookup go up to try */
1904 			/* if: no parent NS in cache - go up one level */
1905 			verbose(VERB_ALGO, "try to grab parent NS");
1906 			iq->store_parent_NS = iq->dp;
1907 			iq->chase_flags &= ~BIT_RD; /* go to authorities */
1908 			iq->deleg_msg = NULL;
1909 			iq->refetch_glue = 1;
1910 			iq->query_restart_count++;
1911 			iq->sent_count = 0;
1912 			if(qstate->env->cfg->qname_minimisation)
1913 				iq->minimisation_state = INIT_MINIMISE_STATE;
1914 			return next_state(iq, INIT_REQUEST_STATE);
1915 		}
1916 	}
1917 	/* see if that makes new names available */
1918 	if(!cache_fill_missing(qstate->env, iq->qchase.qclass,
1919 		qstate->region, iq->dp))
1920 		log_err("out of memory in cache_fill_missing");
1921 	if(iq->dp->usable_list) {
1922 		verbose(VERB_ALGO, "try parent-side-name, w. glue from cache");
1923 		return next_state(iq, QUERYTARGETS_STATE);
1924 	}
1925 	/* try to fill out parent glue from cache */
1926 	if(iter_lookup_parent_glue_from_cache(qstate->env, iq->dp,
1927 		qstate->region, &qstate->qinfo)) {
1928 		/* got parent stuff from cache, see if we can continue */
1929 		verbose(VERB_ALGO, "try parent-side glue from cache");
1930 		return next_state(iq, QUERYTARGETS_STATE);
1931 	}
1932 	/* query for an extra name added by the parent-NS record */
1933 	if(delegpt_count_missing_targets(iq->dp) > 0) {
1934 		int qs = 0;
1935 		verbose(VERB_ALGO, "try parent-side target name");
1936 		if(!query_for_targets(qstate, iq, ie, id, 1, &qs)) {
1937 			errinf(qstate, "could not fetch nameserver");
1938 			errinf_dname(qstate, "at zone", iq->dp->name);
1939 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
1940 		}
1941 		iq->num_target_queries += qs;
1942 		target_count_increase(iq, qs);
1943 		if(qs != 0) {
1944 			qstate->ext_state[id] = module_wait_subquery;
1945 			return 0; /* and wait for them */
1946 		}
1947 	}
1948 	if(iq->depth == ie->max_dependency_depth) {
1949 		verbose(VERB_QUERY, "maxdepth and need more nameservers, fail");
1950 		errinf(qstate, "cannot fetch more nameservers because at max dependency depth");
1951 		return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
1952 	}
1953 	if(iq->depth > 0 && iq->target_count &&
1954 		iq->target_count[1] > MAX_TARGET_COUNT) {
1955 		char s[LDNS_MAX_DOMAINLEN+1];
1956 		dname_str(qstate->qinfo.qname, s);
1957 		verbose(VERB_QUERY, "request %s has exceeded the maximum "
1958 			"number of glue fetches %d", s, iq->target_count[1]);
1959 		errinf(qstate, "exceeded the maximum number of glue fetches");
1960 		return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
1961 	}
1962 	/* mark cycle targets for parent-side lookups */
1963 	iter_mark_pside_cycle_targets(qstate, iq->dp);
1964 	/* see if we can issue queries to get nameserver addresses */
1965 	/* this lookup is not randomized, but sequential. */
1966 	for(ns = iq->dp->nslist; ns; ns = ns->next) {
1967 		/* if this nameserver is at a delegation point, but that
1968 		 * delegation point is a stub and we cannot go higher, skip*/
1969 		if( ((ie->supports_ipv6 && !ns->done_pside6) ||
1970 		    (ie->supports_ipv4 && !ns->done_pside4)) &&
1971 		    !can_have_last_resort(qstate->env, ns->name, ns->namelen,
1972 			iq->qchase.qclass, NULL)) {
1973 			log_nametypeclass(VERB_ALGO, "cannot pside lookup ns "
1974 				"because it is also a stub/forward,",
1975 				ns->name, LDNS_RR_TYPE_NS, iq->qchase.qclass);
1976 			if(ie->supports_ipv6) ns->done_pside6 = 1;
1977 			if(ie->supports_ipv4) ns->done_pside4 = 1;
1978 			continue;
1979 		}
1980 		/* query for parent-side A and AAAA for nameservers */
1981 		if(ie->supports_ipv6 && !ns->done_pside6) {
1982 			/* Send the AAAA request. */
1983 			if(!generate_parentside_target_query(qstate, iq, id,
1984 				ns->name, ns->namelen,
1985 				LDNS_RR_TYPE_AAAA, iq->qchase.qclass)) {
1986 				errinf_dname(qstate, "could not generate nameserver AAAA lookup for", ns->name);
1987 				return error_response(qstate, id,
1988 					LDNS_RCODE_SERVFAIL);
1989 			}
1990 			ns->done_pside6 = 1;
1991 			query_count++;
1992 		}
1993 		if(ie->supports_ipv4 && !ns->done_pside4) {
1994 			/* Send the A request. */
1995 			if(!generate_parentside_target_query(qstate, iq, id,
1996 				ns->name, ns->namelen,
1997 				LDNS_RR_TYPE_A, iq->qchase.qclass)) {
1998 				errinf_dname(qstate, "could not generate nameserver A lookup for", ns->name);
1999 				return error_response(qstate, id,
2000 					LDNS_RCODE_SERVFAIL);
2001 			}
2002 			ns->done_pside4 = 1;
2003 			query_count++;
2004 		}
2005 		if(query_count != 0) { /* suspend to await results */
2006 			verbose(VERB_ALGO, "try parent-side glue lookup");
2007 			iq->num_target_queries += query_count;
2008 			target_count_increase(iq, query_count);
2009 			qstate->ext_state[id] = module_wait_subquery;
2010 			return 0;
2011 		}
2012 	}
2013 
2014 	/* if this was a parent-side glue query itself, then store that
2015 	 * failure in cache. */
2016 	if(!qstate->no_cache_store && iq->query_for_pside_glue
2017 		&& !iq->pside_glue)
2018 			iter_store_parentside_neg(qstate->env, &qstate->qinfo,
2019 				iq->deleg_msg?iq->deleg_msg->rep:
2020 				(iq->response?iq->response->rep:NULL));
2021 
2022 	errinf(qstate, "all servers for this domain failed,");
2023 	errinf_dname(qstate, "at zone", iq->dp->name);
2024 	verbose(VERB_QUERY, "out of query targets -- returning SERVFAIL");
2025 	/* fail -- no more targets, no more hope of targets, no hope
2026 	 * of a response. */
2027 	return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
2028 }
2029 
2030 /**
2031  * Try to find the NS record set that will resolve a qtype DS query. Due
2032  * to grandparent/grandchild reasons we did not get a proper lookup right
2033  * away.  We need to create type NS queries until we get the right parent
2034  * for this lookup.  We remove labels from the query to find the right point.
2035  * If we end up at the old dp name, then there is no solution.
2036  *
2037  * @param qstate: query state.
2038  * @param iq: iterator query state.
2039  * @param id: module id.
2040  * @return true if the event requires more immediate processing, false if
2041  *         not. This is generally only true when forwarding the request to
2042  *         the final state (i.e., on answer).
2043  */
2044 static int
2045 processDSNSFind(struct module_qstate* qstate, struct iter_qstate* iq, int id)
2046 {
2047 	struct module_qstate* subq = NULL;
2048 	verbose(VERB_ALGO, "processDSNSFind");
2049 
2050 	if(!iq->dsns_point) {
2051 		/* initialize */
2052 		iq->dsns_point = iq->qchase.qname;
2053 		iq->dsns_point_len = iq->qchase.qname_len;
2054 	}
2055 	/* robustcheck for internal error: we are not underneath the dp */
2056 	if(!dname_subdomain_c(iq->dsns_point, iq->dp->name)) {
2057 		errinf_dname(qstate, "for DS query parent-child nameserver search the query is not under the zone", iq->dp->name);
2058 		return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
2059 	}
2060 
2061 	/* go up one (more) step, until we hit the dp, if so, end */
2062 	dname_remove_label(&iq->dsns_point, &iq->dsns_point_len);
2063 	if(query_dname_compare(iq->dsns_point, iq->dp->name) == 0) {
2064 		/* there was no inbetween nameserver, use the old delegation
2065 		 * point again.  And this time, because dsns_point is nonNULL
2066 		 * we are going to accept the (bad) result */
2067 		iq->state = QUERYTARGETS_STATE;
2068 		return 1;
2069 	}
2070 	iq->state = DSNS_FIND_STATE;
2071 
2072 	/* spawn NS lookup (validation not needed, this is for DS lookup) */
2073 	log_nametypeclass(VERB_ALGO, "fetch nameservers",
2074 		iq->dsns_point, LDNS_RR_TYPE_NS, iq->qchase.qclass);
2075 	if(!generate_sub_request(iq->dsns_point, iq->dsns_point_len,
2076 		LDNS_RR_TYPE_NS, iq->qchase.qclass, qstate, id, iq,
2077 		INIT_REQUEST_STATE, FINISHED_STATE, &subq, 0)) {
2078 		errinf_dname(qstate, "for DS query parent-child nameserver search, could not generate NS lookup for", iq->dsns_point);
2079 		return error_response_cache(qstate, id, LDNS_RCODE_SERVFAIL);
2080 	}
2081 
2082 	return 0;
2083 }
2084 
2085 /**
2086  * This is the request event state where the request will be sent to one of
2087  * its current query targets. This state also handles issuing target lookup
2088  * queries for missing target IP addresses. Queries typically iterate on
2089  * this state, both when they are just trying different targets for a given
2090  * delegation point, and when they change delegation points. This state
2091  * roughly corresponds to RFC 1034 algorithm steps 3 and 4.
2092  *
2093  * @param qstate: query state.
2094  * @param iq: iterator query state.
2095  * @param ie: iterator shared global environment.
2096  * @param id: module id.
2097  * @return true if the event requires more request processing immediately,
2098  *         false if not. This state only returns true when it is generating
2099  *         a SERVFAIL response because the query has hit a dead end.
2100  */
2101 static int
2102 processQueryTargets(struct module_qstate* qstate, struct iter_qstate* iq,
2103 	struct iter_env* ie, int id)
2104 {
2105 	int tf_policy;
2106 	struct delegpt_addr* target;
2107 	struct outbound_entry* outq;
2108 	int auth_fallback = 0;
2109 	uint8_t* qout_orig = NULL;
2110 	size_t qout_orig_len = 0;
2111 
2112 	/* NOTE: a request will encounter this state for each target it
2113 	 * needs to send a query to. That is, at least one per referral,
2114 	 * more if some targets timeout or return throwaway answers. */
2115 
2116 	log_query_info(VERB_QUERY, "processQueryTargets:", &qstate->qinfo);
2117 	verbose(VERB_ALGO, "processQueryTargets: targetqueries %d, "
2118 		"currentqueries %d sentcount %d", iq->num_target_queries,
2119 		iq->num_current_queries, iq->sent_count);
2120 
2121 	/* Make sure that we haven't run away */
2122 	/* FIXME: is this check even necessary? */
2123 	if(iq->referral_count > MAX_REFERRAL_COUNT) {
2124 		verbose(VERB_QUERY, "request has exceeded the maximum "
2125 			"number of referrrals with %d", iq->referral_count);
2126 		errinf(qstate, "exceeded the maximum of referrals");
2127 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2128 	}
2129 	if(iq->sent_count > MAX_SENT_COUNT) {
2130 		verbose(VERB_QUERY, "request has exceeded the maximum "
2131 			"number of sends with %d", iq->sent_count);
2132 		errinf(qstate, "exceeded the maximum number of sends");
2133 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2134 	}
2135 
2136 	/* Make sure we have a delegation point, otherwise priming failed
2137 	 * or another failure occurred */
2138 	if(!iq->dp) {
2139 		verbose(VERB_QUERY, "Failed to get a delegation, giving up");
2140 		errinf(qstate, "failed to get a delegation (eg. prime failure)");
2141 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2142 	}
2143 	if(!ie->supports_ipv6)
2144 		delegpt_no_ipv6(iq->dp);
2145 	if(!ie->supports_ipv4)
2146 		delegpt_no_ipv4(iq->dp);
2147 	delegpt_log(VERB_ALGO, iq->dp);
2148 
2149 	if(iq->num_current_queries>0) {
2150 		/* already busy answering a query, this restart is because
2151 		 * more delegpt addrs became available, wait for existing
2152 		 * query. */
2153 		verbose(VERB_ALGO, "woke up, but wait for outstanding query");
2154 		qstate->ext_state[id] = module_wait_reply;
2155 		return 0;
2156 	}
2157 
2158 	if(iq->minimisation_state == INIT_MINIMISE_STATE
2159 		&& !(iq->chase_flags & BIT_RD)) {
2160 		/* (Re)set qinfo_out to (new) delegation point, except when
2161 		 * qinfo_out is already a subdomain of dp. This happens when
2162 		 * increasing by more than one label at once (QNAMEs with more
2163 		 * than MAX_MINIMISE_COUNT labels). */
2164 		if(!(iq->qinfo_out.qname_len
2165 			&& dname_subdomain_c(iq->qchase.qname,
2166 				iq->qinfo_out.qname)
2167 			&& dname_subdomain_c(iq->qinfo_out.qname,
2168 				iq->dp->name))) {
2169 			iq->qinfo_out.qname = iq->dp->name;
2170 			iq->qinfo_out.qname_len = iq->dp->namelen;
2171 			iq->qinfo_out.qtype = LDNS_RR_TYPE_A;
2172 			iq->qinfo_out.qclass = iq->qchase.qclass;
2173 			iq->qinfo_out.local_alias = NULL;
2174 			iq->minimise_count = 0;
2175 		}
2176 
2177 		iq->minimisation_state = MINIMISE_STATE;
2178 	}
2179 	if(iq->minimisation_state == MINIMISE_STATE) {
2180 		int qchaselabs = dname_count_labels(iq->qchase.qname);
2181 		int labdiff = qchaselabs -
2182 			dname_count_labels(iq->qinfo_out.qname);
2183 
2184 		qout_orig = iq->qinfo_out.qname;
2185 		qout_orig_len = iq->qinfo_out.qname_len;
2186 		iq->qinfo_out.qname = iq->qchase.qname;
2187 		iq->qinfo_out.qname_len = iq->qchase.qname_len;
2188 		iq->minimise_count++;
2189 		iq->minimise_timeout_count = 0;
2190 
2191 		iter_dec_attempts(iq->dp, 1);
2192 
2193 		/* Limit number of iterations for QNAMEs with more
2194 		 * than MAX_MINIMISE_COUNT labels. Send first MINIMISE_ONE_LAB
2195 		 * labels of QNAME always individually.
2196 		 */
2197 		if(qchaselabs > MAX_MINIMISE_COUNT && labdiff > 1 &&
2198 			iq->minimise_count > MINIMISE_ONE_LAB) {
2199 			if(iq->minimise_count < MAX_MINIMISE_COUNT) {
2200 				int multilabs = qchaselabs - 1 -
2201 					MINIMISE_ONE_LAB;
2202 				int extralabs = multilabs /
2203 					MINIMISE_MULTIPLE_LABS;
2204 
2205 				if (MAX_MINIMISE_COUNT - iq->minimise_count >=
2206 					multilabs % MINIMISE_MULTIPLE_LABS)
2207 					/* Default behaviour is to add 1 label
2208 					 * every iteration. Therefore, decrement
2209 					 * the extralabs by 1 */
2210 					extralabs--;
2211 				if (extralabs < labdiff)
2212 					labdiff -= extralabs;
2213 				else
2214 					labdiff = 1;
2215 			}
2216 			/* Last minimised iteration, send all labels with
2217 			 * QTYPE=NS */
2218 			else
2219 				labdiff = 1;
2220 		}
2221 
2222 		if(labdiff > 1) {
2223 			verbose(VERB_QUERY, "removing %d labels", labdiff-1);
2224 			dname_remove_labels(&iq->qinfo_out.qname,
2225 				&iq->qinfo_out.qname_len,
2226 				labdiff-1);
2227 		}
2228 		if(labdiff < 1 || (labdiff < 2
2229 			&& (iq->qchase.qtype == LDNS_RR_TYPE_DS
2230 			|| iq->qchase.qtype == LDNS_RR_TYPE_A)))
2231 			/* Stop minimising this query, resolve "as usual" */
2232 			iq->minimisation_state = DONOT_MINIMISE_STATE;
2233 		else if(!qstate->no_cache_lookup) {
2234 			struct dns_msg* msg = dns_cache_lookup(qstate->env,
2235 				iq->qinfo_out.qname, iq->qinfo_out.qname_len,
2236 				iq->qinfo_out.qtype, iq->qinfo_out.qclass,
2237 				qstate->query_flags, qstate->region,
2238 				qstate->env->scratch, 0);
2239 			if(msg && msg->rep->an_numrrsets == 0
2240 				&& FLAGS_GET_RCODE(msg->rep->flags) ==
2241 				LDNS_RCODE_NOERROR)
2242 				/* no need to send query if it is already
2243 				 * cached as NOERROR/NODATA */
2244 				return 1;
2245 		}
2246 	}
2247 	if(iq->minimisation_state == SKIP_MINIMISE_STATE) {
2248 		if(iq->minimise_timeout_count < MAX_MINIMISE_TIMEOUT_COUNT)
2249 			/* Do not increment qname, continue incrementing next
2250 			 * iteration */
2251 			iq->minimisation_state = MINIMISE_STATE;
2252 		else if(!qstate->env->cfg->qname_minimisation_strict)
2253 			/* Too many time-outs detected for this QNAME and QTYPE.
2254 			 * We give up, disable QNAME minimisation. */
2255 			iq->minimisation_state = DONOT_MINIMISE_STATE;
2256 	}
2257 	if(iq->minimisation_state == DONOT_MINIMISE_STATE)
2258 		iq->qinfo_out = iq->qchase;
2259 
2260 	/* now find an answer to this query */
2261 	/* see if authority zones have an answer */
2262 	/* now we know the dp, we can check the auth zone for locally hosted
2263 	 * contents */
2264 	if(!iq->auth_zone_avoid && qstate->blacklist) {
2265 		if(auth_zones_can_fallback(qstate->env->auth_zones,
2266 			iq->dp->name, iq->dp->namelen, iq->qinfo_out.qclass)) {
2267 			/* if cache is blacklisted and this zone allows us
2268 			 * to fallback to the internet, then do so, and
2269 			 * fetch results from the internet servers */
2270 			iq->auth_zone_avoid = 1;
2271 		}
2272 	}
2273 	if(iq->auth_zone_avoid) {
2274 		iq->auth_zone_avoid = 0;
2275 		auth_fallback = 1;
2276 	} else if(auth_zones_lookup(qstate->env->auth_zones, &iq->qinfo_out,
2277 		qstate->region, &iq->response, &auth_fallback, iq->dp->name,
2278 		iq->dp->namelen)) {
2279 		/* use this as a response to be processed by the iterator */
2280 		if(verbosity >= VERB_ALGO) {
2281 			log_dns_msg("msg from auth zone",
2282 				&iq->response->qinfo, iq->response->rep);
2283 		}
2284 		if((iq->chase_flags&BIT_RD) && !(iq->response->rep->flags&BIT_AA)) {
2285 			verbose(VERB_ALGO, "forwarder, ignoring referral from auth zone");
2286 		} else {
2287 			lock_rw_wrlock(&qstate->env->auth_zones->lock);
2288 			qstate->env->auth_zones->num_query_up++;
2289 			lock_rw_unlock(&qstate->env->auth_zones->lock);
2290 			iq->num_current_queries++;
2291 			iq->chase_to_rd = 0;
2292 			iq->dnssec_lame_query = 0;
2293 			iq->auth_zone_response = 1;
2294 			return next_state(iq, QUERY_RESP_STATE);
2295 		}
2296 	}
2297 	iq->auth_zone_response = 0;
2298 	if(auth_fallback == 0) {
2299 		/* like we got servfail from the auth zone lookup, and
2300 		 * no internet fallback */
2301 		verbose(VERB_ALGO, "auth zone lookup failed, no fallback,"
2302 			" servfail");
2303 		errinf(qstate, "auth zone lookup failed, fallback is off");
2304 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2305 	}
2306 	if(iq->dp->auth_dp) {
2307 		/* we wanted to fallback, but had no delegpt, only the
2308 		 * auth zone generated delegpt, create an actual one */
2309 		iq->auth_zone_avoid = 1;
2310 		return next_state(iq, INIT_REQUEST_STATE);
2311 	}
2312 	/* but mostly, fallback==1 (like, when no such auth zone exists)
2313 	 * and we continue with lookups */
2314 
2315 	tf_policy = 0;
2316 	/* < not <=, because although the array is large enough for <=, the
2317 	 * generated query will immediately be discarded due to depth and
2318 	 * that servfail is cached, which is not good as opportunism goes. */
2319 	if(iq->depth < ie->max_dependency_depth
2320 		&& iq->sent_count < TARGET_FETCH_STOP) {
2321 		tf_policy = ie->target_fetch_policy[iq->depth];
2322 	}
2323 
2324 	/* if in 0x20 fallback get as many targets as possible */
2325 	if(iq->caps_fallback) {
2326 		int extra = 0;
2327 		size_t naddr, nres, navail;
2328 		if(!query_for_targets(qstate, iq, ie, id, -1, &extra)) {
2329 			errinf(qstate, "could not fetch nameservers for 0x20 fallback");
2330 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2331 		}
2332 		iq->num_target_queries += extra;
2333 		target_count_increase(iq, extra);
2334 		if(iq->num_target_queries > 0) {
2335 			/* wait to get all targets, we want to try em */
2336 			verbose(VERB_ALGO, "wait for all targets for fallback");
2337 			qstate->ext_state[id] = module_wait_reply;
2338 			/* undo qname minimise step because we'll get back here
2339 			 * to do it again */
2340 			if(qout_orig && iq->minimise_count > 0) {
2341 				iq->minimise_count--;
2342 				iq->qinfo_out.qname = qout_orig;
2343 				iq->qinfo_out.qname_len = qout_orig_len;
2344 			}
2345 			return 0;
2346 		}
2347 		/* did we do enough fallback queries already? */
2348 		delegpt_count_addr(iq->dp, &naddr, &nres, &navail);
2349 		/* the current caps_server is the number of fallbacks sent.
2350 		 * the original query is one that matched too, so we have
2351 		 * caps_server+1 number of matching queries now */
2352 		if(iq->caps_server+1 >= naddr*3 ||
2353 			iq->caps_server*2+2 >= MAX_SENT_COUNT) {
2354 			/* *2 on sentcount check because ipv6 may fail */
2355 			/* we're done, process the response */
2356 			verbose(VERB_ALGO, "0x20 fallback had %d responses "
2357 				"match for %d wanted, done.",
2358 				(int)iq->caps_server+1, (int)naddr*3);
2359 			iq->response = iq->caps_response;
2360 			iq->caps_fallback = 0;
2361 			iter_dec_attempts(iq->dp, 3); /* space for fallback */
2362 			iq->num_current_queries++; /* RespState decrements it*/
2363 			iq->referral_count++; /* make sure we don't loop */
2364 			iq->sent_count = 0;
2365 			iq->state = QUERY_RESP_STATE;
2366 			return 1;
2367 		}
2368 		verbose(VERB_ALGO, "0x20 fallback number %d",
2369 			(int)iq->caps_server);
2370 
2371 	/* if there is a policy to fetch missing targets
2372 	 * opportunistically, do it. we rely on the fact that once a
2373 	 * query (or queries) for a missing name have been issued,
2374 	 * they will not show up again. */
2375 	} else if(tf_policy != 0) {
2376 		int extra = 0;
2377 		verbose(VERB_ALGO, "attempt to get extra %d targets",
2378 			tf_policy);
2379 		(void)query_for_targets(qstate, iq, ie, id, tf_policy, &extra);
2380 		/* errors ignored, these targets are not strictly necessary for
2381 		 * this result, we do not have to reply with SERVFAIL */
2382 		iq->num_target_queries += extra;
2383 		target_count_increase(iq, extra);
2384 	}
2385 
2386 	/* Add the current set of unused targets to our queue. */
2387 	delegpt_add_unused_targets(iq->dp);
2388 
2389 	/* Select the next usable target, filtering out unsuitable targets. */
2390 	target = iter_server_selection(ie, qstate->env, iq->dp,
2391 		iq->dp->name, iq->dp->namelen, iq->qchase.qtype,
2392 		&iq->dnssec_lame_query, &iq->chase_to_rd,
2393 		iq->num_target_queries, qstate->blacklist,
2394 		qstate->prefetch_leeway);
2395 
2396 	/* If no usable target was selected... */
2397 	if(!target) {
2398 		/* Here we distinguish between three states: generate a new
2399 		 * target query, just wait, or quit (with a SERVFAIL).
2400 		 * We have the following information: number of active
2401 		 * target queries, number of active current queries,
2402 		 * the presence of missing targets at this delegation
2403 		 * point, and the given query target policy. */
2404 
2405 		/* Check for the wait condition. If this is true, then
2406 		 * an action must be taken. */
2407 		if(iq->num_target_queries==0 && iq->num_current_queries==0) {
2408 			/* If there is nothing to wait for, then we need
2409 			 * to distinguish between generating (a) new target
2410 			 * query, or failing. */
2411 			if(delegpt_count_missing_targets(iq->dp) > 0) {
2412 				int qs = 0;
2413 				verbose(VERB_ALGO, "querying for next "
2414 					"missing target");
2415 				if(!query_for_targets(qstate, iq, ie, id,
2416 					1, &qs)) {
2417 					errinf(qstate, "could not fetch nameserver");
2418 					errinf_dname(qstate, "at zone", iq->dp->name);
2419 					return error_response(qstate, id,
2420 						LDNS_RCODE_SERVFAIL);
2421 				}
2422 				if(qs == 0 &&
2423 				   delegpt_count_missing_targets(iq->dp) == 0){
2424 					/* it looked like there were missing
2425 					 * targets, but they did not turn up.
2426 					 * Try the bad choices again (if any),
2427 					 * when we get back here missing==0,
2428 					 * so this is not a loop. */
2429 					return 1;
2430 				}
2431 				iq->num_target_queries += qs;
2432 				target_count_increase(iq, qs);
2433 			}
2434 			/* Since a target query might have been made, we
2435 			 * need to check again. */
2436 			if(iq->num_target_queries == 0) {
2437 				/* if in capsforid fallback, instead of last
2438 				 * resort, we agree with the current reply
2439 				 * we have (if any) (our count of addrs bad)*/
2440 				if(iq->caps_fallback && iq->caps_reply) {
2441 					/* we're done, process the response */
2442 					verbose(VERB_ALGO, "0x20 fallback had %d responses, "
2443 						"but no more servers except "
2444 						"last resort, done.",
2445 						(int)iq->caps_server+1);
2446 					iq->response = iq->caps_response;
2447 					iq->caps_fallback = 0;
2448 					iter_dec_attempts(iq->dp, 3); /* space for fallback */
2449 					iq->num_current_queries++; /* RespState decrements it*/
2450 					iq->referral_count++; /* make sure we don't loop */
2451 					iq->sent_count = 0;
2452 					iq->state = QUERY_RESP_STATE;
2453 					return 1;
2454 				}
2455 				return processLastResort(qstate, iq, ie, id);
2456 			}
2457 		}
2458 
2459 		/* otherwise, we have no current targets, so submerge
2460 		 * until one of the target or direct queries return. */
2461 		if(iq->num_target_queries>0 && iq->num_current_queries>0) {
2462 			verbose(VERB_ALGO, "no current targets -- waiting "
2463 				"for %d targets to resolve or %d outstanding"
2464 				" queries to respond", iq->num_target_queries,
2465 				iq->num_current_queries);
2466 			qstate->ext_state[id] = module_wait_reply;
2467 		} else if(iq->num_target_queries>0) {
2468 			verbose(VERB_ALGO, "no current targets -- waiting "
2469 				"for %d targets to resolve.",
2470 				iq->num_target_queries);
2471 			qstate->ext_state[id] = module_wait_subquery;
2472 		} else {
2473 			verbose(VERB_ALGO, "no current targets -- waiting "
2474 				"for %d outstanding queries to respond.",
2475 				iq->num_current_queries);
2476 			qstate->ext_state[id] = module_wait_reply;
2477 		}
2478 		/* undo qname minimise step because we'll get back here
2479 		 * to do it again */
2480 		if(qout_orig && iq->minimise_count > 0) {
2481 			iq->minimise_count--;
2482 			iq->qinfo_out.qname = qout_orig;
2483 			iq->qinfo_out.qname_len = qout_orig_len;
2484 		}
2485 		return 0;
2486 	}
2487 
2488 	/* if not forwarding, check ratelimits per delegationpoint name */
2489 	if(!(iq->chase_flags & BIT_RD) && !iq->ratelimit_ok) {
2490 		if(!infra_ratelimit_inc(qstate->env->infra_cache, iq->dp->name,
2491 			iq->dp->namelen, *qstate->env->now, &qstate->qinfo,
2492 			qstate->reply)) {
2493 			lock_basic_lock(&ie->queries_ratelimit_lock);
2494 			ie->num_queries_ratelimited++;
2495 			lock_basic_unlock(&ie->queries_ratelimit_lock);
2496 			verbose(VERB_ALGO, "query exceeded ratelimits");
2497 			qstate->was_ratelimited = 1;
2498 			errinf_dname(qstate, "exceeded ratelimit for zone",
2499 				iq->dp->name);
2500 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2501 		}
2502 	}
2503 
2504 	/* We have a valid target. */
2505 	if(verbosity >= VERB_QUERY) {
2506 		log_query_info(VERB_QUERY, "sending query:", &iq->qinfo_out);
2507 		log_name_addr(VERB_QUERY, "sending to target:", iq->dp->name,
2508 			&target->addr, target->addrlen);
2509 		verbose(VERB_ALGO, "dnssec status: %s%s",
2510 			iq->dnssec_expected?"expected": "not expected",
2511 			iq->dnssec_lame_query?" but lame_query anyway": "");
2512 	}
2513 	fptr_ok(fptr_whitelist_modenv_send_query(qstate->env->send_query));
2514 	outq = (*qstate->env->send_query)(&iq->qinfo_out,
2515 		iq->chase_flags | (iq->chase_to_rd?BIT_RD:0),
2516 		/* unset CD if to forwarder(RD set) and not dnssec retry
2517 		 * (blacklist nonempty) and no trust-anchors are configured
2518 		 * above the qname or on the first attempt when dnssec is on */
2519 		EDNS_DO| ((iq->chase_to_rd||(iq->chase_flags&BIT_RD)!=0)&&
2520 		!qstate->blacklist&&(!iter_qname_indicates_dnssec(qstate->env,
2521 		&iq->qinfo_out)||target->attempts==1)?0:BIT_CD),
2522 		iq->dnssec_expected, iq->caps_fallback || is_caps_whitelisted(
2523 		ie, iq), &target->addr, target->addrlen,
2524 		iq->dp->name, iq->dp->namelen,
2525 		(iq->dp->ssl_upstream || qstate->env->cfg->ssl_upstream),
2526 		target->tls_auth_name, qstate);
2527 	if(!outq) {
2528 		log_addr(VERB_DETAIL, "error sending query to auth server",
2529 			&target->addr, target->addrlen);
2530 		if(!(iq->chase_flags & BIT_RD) && !iq->ratelimit_ok)
2531 		    infra_ratelimit_dec(qstate->env->infra_cache, iq->dp->name,
2532 			iq->dp->namelen, *qstate->env->now);
2533 		if(qstate->env->cfg->qname_minimisation)
2534 			iq->minimisation_state = SKIP_MINIMISE_STATE;
2535 		return next_state(iq, QUERYTARGETS_STATE);
2536 	}
2537 	outbound_list_insert(&iq->outlist, outq);
2538 	iq->num_current_queries++;
2539 	iq->sent_count++;
2540 	qstate->ext_state[id] = module_wait_reply;
2541 
2542 	return 0;
2543 }
2544 
2545 /** find NS rrset in given list */
2546 static struct ub_packed_rrset_key*
2547 find_NS(struct reply_info* rep, size_t from, size_t to)
2548 {
2549 	size_t i;
2550 	for(i=from; i<to; i++) {
2551 		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NS)
2552 			return rep->rrsets[i];
2553 	}
2554 	return NULL;
2555 }
2556 
2557 
2558 /**
2559  * Process the query response. All queries end up at this state first. This
2560  * process generally consists of analyzing the response and routing the
2561  * event to the next state (either bouncing it back to a request state, or
2562  * terminating the processing for this event).
2563  *
2564  * @param qstate: query state.
2565  * @param iq: iterator query state.
2566  * @param id: module id.
2567  * @return true if the event requires more immediate processing, false if
2568  *         not. This is generally only true when forwarding the request to
2569  *         the final state (i.e., on answer).
2570  */
2571 static int
2572 processQueryResponse(struct module_qstate* qstate, struct iter_qstate* iq,
2573 	int id)
2574 {
2575 	int dnsseclame = 0;
2576 	enum response_type type;
2577 	iq->num_current_queries--;
2578 
2579 	if(!inplace_cb_query_response_call(qstate->env, qstate, iq->response))
2580 		log_err("unable to call query_response callback");
2581 
2582 	if(iq->response == NULL) {
2583 		/* Don't increment qname when QNAME minimisation is enabled */
2584 		if(qstate->env->cfg->qname_minimisation) {
2585 			iq->minimise_timeout_count++;
2586 			iq->minimisation_state = SKIP_MINIMISE_STATE;
2587 		}
2588 		iq->chase_to_rd = 0;
2589 		iq->dnssec_lame_query = 0;
2590 		verbose(VERB_ALGO, "query response was timeout");
2591 		return next_state(iq, QUERYTARGETS_STATE);
2592 	}
2593 	type = response_type_from_server(
2594 		(int)((iq->chase_flags&BIT_RD) || iq->chase_to_rd),
2595 		iq->response, &iq->qinfo_out, iq->dp);
2596 	iq->chase_to_rd = 0;
2597 	if(type == RESPONSE_TYPE_REFERRAL && (iq->chase_flags&BIT_RD) &&
2598 		!iq->auth_zone_response) {
2599 		/* When forwarding (RD bit is set), we handle referrals
2600 		 * differently. No queries should be sent elsewhere */
2601 		type = RESPONSE_TYPE_ANSWER;
2602 	}
2603 	if(!qstate->env->cfg->disable_dnssec_lame_check && iq->dnssec_expected
2604                 && !iq->dnssec_lame_query &&
2605 		!(iq->chase_flags&BIT_RD)
2606 		&& iq->sent_count < DNSSEC_LAME_DETECT_COUNT
2607 		&& type != RESPONSE_TYPE_LAME
2608 		&& type != RESPONSE_TYPE_REC_LAME
2609 		&& type != RESPONSE_TYPE_THROWAWAY
2610 		&& type != RESPONSE_TYPE_UNTYPED) {
2611 		/* a possible answer, see if it is missing DNSSEC */
2612 		/* but not when forwarding, so we dont mark fwder lame */
2613 		if(!iter_msg_has_dnssec(iq->response)) {
2614 			/* Mark this address as dnsseclame in this dp,
2615 			 * because that will make serverselection disprefer
2616 			 * it, but also, once it is the only final option,
2617 			 * use dnssec-lame-bypass if it needs to query there.*/
2618 			if(qstate->reply) {
2619 				struct delegpt_addr* a = delegpt_find_addr(
2620 					iq->dp, &qstate->reply->addr,
2621 					qstate->reply->addrlen);
2622 				if(a) a->dnsseclame = 1;
2623 			}
2624 			/* test the answer is from the zone we expected,
2625 		 	 * otherwise, (due to parent,child on same server), we
2626 		 	 * might mark the server,zone lame inappropriately */
2627 			if(!iter_msg_from_zone(iq->response, iq->dp, type,
2628 				iq->qchase.qclass))
2629 				qstate->reply = NULL;
2630 			type = RESPONSE_TYPE_LAME;
2631 			dnsseclame = 1;
2632 		}
2633 	} else iq->dnssec_lame_query = 0;
2634 	/* see if referral brings us close to the target */
2635 	if(type == RESPONSE_TYPE_REFERRAL) {
2636 		struct ub_packed_rrset_key* ns = find_NS(
2637 			iq->response->rep, iq->response->rep->an_numrrsets,
2638 			iq->response->rep->an_numrrsets
2639 			+ iq->response->rep->ns_numrrsets);
2640 		if(!ns) ns = find_NS(iq->response->rep, 0,
2641 				iq->response->rep->an_numrrsets);
2642 		if(!ns || !dname_strict_subdomain_c(ns->rk.dname, iq->dp->name)
2643 			|| !dname_subdomain_c(iq->qchase.qname, ns->rk.dname)){
2644 			verbose(VERB_ALGO, "bad referral, throwaway");
2645 			type = RESPONSE_TYPE_THROWAWAY;
2646 		} else
2647 			iter_scrub_ds(iq->response, ns, iq->dp->name);
2648 	} else iter_scrub_ds(iq->response, NULL, NULL);
2649 	if(type == RESPONSE_TYPE_THROWAWAY &&
2650 		FLAGS_GET_RCODE(iq->response->rep->flags) == LDNS_RCODE_YXDOMAIN) {
2651 		/* YXDOMAIN is a permanent error, no need to retry */
2652 		type = RESPONSE_TYPE_ANSWER;
2653 	}
2654 	if(type == RESPONSE_TYPE_CNAME && iq->response->rep->an_numrrsets >= 1
2655 		&& ntohs(iq->response->rep->rrsets[0]->rk.type) == LDNS_RR_TYPE_DNAME) {
2656 		uint8_t* sname = NULL;
2657 		size_t snamelen = 0;
2658 		get_cname_target(iq->response->rep->rrsets[0], &sname,
2659 			&snamelen);
2660 		if(snamelen && dname_subdomain_c(sname, iq->response->rep->rrsets[0]->rk.dname)) {
2661 			/* DNAME to a subdomain loop; do not recurse */
2662 			type = RESPONSE_TYPE_ANSWER;
2663 		}
2664 	} else if(type == RESPONSE_TYPE_CNAME &&
2665 		iq->qchase.qtype == LDNS_RR_TYPE_CNAME &&
2666 		iq->minimisation_state == MINIMISE_STATE &&
2667 		query_dname_compare(iq->qchase.qname, iq->qinfo_out.qname) == 0) {
2668 		/* The minimised query for full QTYPE and hidden QTYPE can be
2669 		 * classified as CNAME response type, even when the original
2670 		 * QTYPE=CNAME. This should be treated as answer response type.
2671 		 */
2672 		type = RESPONSE_TYPE_ANSWER;
2673 	}
2674 
2675 	/* handle each of the type cases */
2676 	if(type == RESPONSE_TYPE_ANSWER) {
2677 		/* ANSWER type responses terminate the query algorithm,
2678 		 * so they sent on their */
2679 		if(verbosity >= VERB_DETAIL) {
2680 			verbose(VERB_DETAIL, "query response was %s",
2681 				FLAGS_GET_RCODE(iq->response->rep->flags)
2682 				==LDNS_RCODE_NXDOMAIN?"NXDOMAIN ANSWER":
2683 				(iq->response->rep->an_numrrsets?"ANSWER":
2684 				"nodata ANSWER"));
2685 		}
2686 		/* if qtype is DS, check we have the right level of answer,
2687 		 * like grandchild answer but we need the middle, reject it */
2688 		if(iq->qchase.qtype == LDNS_RR_TYPE_DS && !iq->dsns_point
2689 			&& !(iq->chase_flags&BIT_RD)
2690 			&& iter_ds_toolow(iq->response, iq->dp)
2691 			&& iter_dp_cangodown(&iq->qchase, iq->dp)) {
2692 			/* close down outstanding requests to be discarded */
2693 			outbound_list_clear(&iq->outlist);
2694 			iq->num_current_queries = 0;
2695 			fptr_ok(fptr_whitelist_modenv_detach_subs(
2696 				qstate->env->detach_subs));
2697 			(*qstate->env->detach_subs)(qstate);
2698 			iq->num_target_queries = 0;
2699 			return processDSNSFind(qstate, iq, id);
2700 		}
2701 		if(!qstate->no_cache_store)
2702 			iter_dns_store(qstate->env, &iq->response->qinfo,
2703 				iq->response->rep, 0, qstate->prefetch_leeway,
2704 				iq->dp&&iq->dp->has_parent_side_NS,
2705 				qstate->region, qstate->query_flags);
2706 		/* close down outstanding requests to be discarded */
2707 		outbound_list_clear(&iq->outlist);
2708 		iq->num_current_queries = 0;
2709 		fptr_ok(fptr_whitelist_modenv_detach_subs(
2710 			qstate->env->detach_subs));
2711 		(*qstate->env->detach_subs)(qstate);
2712 		iq->num_target_queries = 0;
2713 		if(qstate->reply)
2714 			sock_list_insert(&qstate->reply_origin,
2715 				&qstate->reply->addr, qstate->reply->addrlen,
2716 				qstate->region);
2717 		if(iq->minimisation_state != DONOT_MINIMISE_STATE
2718 			&& !(iq->chase_flags & BIT_RD)) {
2719 			if(FLAGS_GET_RCODE(iq->response->rep->flags) !=
2720 				LDNS_RCODE_NOERROR) {
2721 				if(qstate->env->cfg->qname_minimisation_strict) {
2722 					if(FLAGS_GET_RCODE(iq->response->rep->flags) ==
2723 						LDNS_RCODE_NXDOMAIN) {
2724 						iter_scrub_nxdomain(iq->response);
2725 						return final_state(iq);
2726 					}
2727 					return error_response(qstate, id,
2728 						LDNS_RCODE_SERVFAIL);
2729 				}
2730 				/* Best effort qname-minimisation.
2731 				 * Stop minimising and send full query when
2732 				 * RCODE is not NOERROR. */
2733 				iq->minimisation_state = DONOT_MINIMISE_STATE;
2734 			}
2735 			if(FLAGS_GET_RCODE(iq->response->rep->flags) ==
2736 				LDNS_RCODE_NXDOMAIN) {
2737 				/* Stop resolving when NXDOMAIN is DNSSEC
2738 				 * signed. Based on assumption that nameservers
2739 				 * serving signed zones do not return NXDOMAIN
2740 				 * for empty-non-terminals. */
2741 				if(iq->dnssec_expected)
2742 					return final_state(iq);
2743 				/* Make subrequest to validate intermediate
2744 				 * NXDOMAIN if harden-below-nxdomain is
2745 				 * enabled. */
2746 				if(qstate->env->cfg->harden_below_nxdomain) {
2747 					struct module_qstate* subq = NULL;
2748 					log_query_info(VERB_QUERY,
2749 						"schedule NXDOMAIN validation:",
2750 						&iq->response->qinfo);
2751 					if(!generate_sub_request(
2752 						iq->response->qinfo.qname,
2753 						iq->response->qinfo.qname_len,
2754 						iq->response->qinfo.qtype,
2755 						iq->response->qinfo.qclass,
2756 						qstate, id, iq,
2757 						INIT_REQUEST_STATE,
2758 						FINISHED_STATE, &subq, 1))
2759 						verbose(VERB_ALGO,
2760 						"could not validate NXDOMAIN "
2761 						"response");
2762 					outbound_list_clear(&iq->outlist);
2763 					iq->num_current_queries = 0;
2764 					fptr_ok(fptr_whitelist_modenv_detach_subs(
2765 						qstate->env->detach_subs));
2766 					(*qstate->env->detach_subs)(qstate);
2767 					iq->num_target_queries = 0;
2768 				}
2769 			}
2770 			return next_state(iq, QUERYTARGETS_STATE);
2771 		}
2772 		return final_state(iq);
2773 	} else if(type == RESPONSE_TYPE_REFERRAL) {
2774 		/* REFERRAL type responses get a reset of the
2775 		 * delegation point, and back to the QUERYTARGETS_STATE. */
2776 		verbose(VERB_DETAIL, "query response was REFERRAL");
2777 
2778 		if(!(iq->chase_flags & BIT_RD) && !iq->ratelimit_ok) {
2779 			/* we have a referral, no ratelimit, we can send
2780 			 * our queries to the given name */
2781 			infra_ratelimit_dec(qstate->env->infra_cache,
2782 				iq->dp->name, iq->dp->namelen,
2783 				*qstate->env->now);
2784 		}
2785 
2786 		/* if hardened, only store referral if we asked for it */
2787 		if(!qstate->no_cache_store &&
2788 		(!qstate->env->cfg->harden_referral_path ||
2789 		    (  qstate->qinfo.qtype == LDNS_RR_TYPE_NS
2790 			&& (qstate->query_flags&BIT_RD)
2791 			&& !(qstate->query_flags&BIT_CD)
2792 			   /* we know that all other NS rrsets are scrubbed
2793 			    * away, thus on referral only one is left.
2794 			    * see if that equals the query name... */
2795 			&& ( /* auth section, but sometimes in answer section*/
2796 			  reply_find_rrset_section_ns(iq->response->rep,
2797 				iq->qchase.qname, iq->qchase.qname_len,
2798 				LDNS_RR_TYPE_NS, iq->qchase.qclass)
2799 			  || reply_find_rrset_section_an(iq->response->rep,
2800 				iq->qchase.qname, iq->qchase.qname_len,
2801 				LDNS_RR_TYPE_NS, iq->qchase.qclass)
2802 			  )
2803 		    ))) {
2804 			/* Store the referral under the current query */
2805 			/* no prefetch-leeway, since its not the answer */
2806 			iter_dns_store(qstate->env, &iq->response->qinfo,
2807 				iq->response->rep, 1, 0, 0, NULL, 0);
2808 			if(iq->store_parent_NS)
2809 				iter_store_parentside_NS(qstate->env,
2810 					iq->response->rep);
2811 			if(qstate->env->neg_cache)
2812 				val_neg_addreferral(qstate->env->neg_cache,
2813 					iq->response->rep, iq->dp->name);
2814 		}
2815 		/* store parent-side-in-zone-glue, if directly queried for */
2816 		if(!qstate->no_cache_store && iq->query_for_pside_glue
2817 			&& !iq->pside_glue) {
2818 				iq->pside_glue = reply_find_rrset(iq->response->rep,
2819 					iq->qchase.qname, iq->qchase.qname_len,
2820 					iq->qchase.qtype, iq->qchase.qclass);
2821 				if(iq->pside_glue) {
2822 					log_rrset_key(VERB_ALGO, "found parent-side "
2823 						"glue", iq->pside_glue);
2824 					iter_store_parentside_rrset(qstate->env,
2825 						iq->pside_glue);
2826 				}
2827 		}
2828 
2829 		/* Reset the event state, setting the current delegation
2830 		 * point to the referral. */
2831 		iq->deleg_msg = iq->response;
2832 		iq->dp = delegpt_from_message(iq->response, qstate->region);
2833 		if (qstate->env->cfg->qname_minimisation)
2834 			iq->minimisation_state = INIT_MINIMISE_STATE;
2835 		if(!iq->dp) {
2836 			errinf(qstate, "malloc failure, for delegation point");
2837 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2838 		}
2839 		if(!cache_fill_missing(qstate->env, iq->qchase.qclass,
2840 			qstate->region, iq->dp)) {
2841 			errinf(qstate, "malloc failure, copy extra info into delegation point");
2842 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2843 		}
2844 		if(iq->store_parent_NS && query_dname_compare(iq->dp->name,
2845 			iq->store_parent_NS->name) == 0)
2846 			iter_merge_retry_counts(iq->dp, iq->store_parent_NS);
2847 		delegpt_log(VERB_ALGO, iq->dp);
2848 		/* Count this as a referral. */
2849 		iq->referral_count++;
2850 		iq->sent_count = 0;
2851 		/* see if the next dp is a trust anchor, or a DS was sent
2852 		 * along, indicating dnssec is expected for next zone */
2853 		iq->dnssec_expected = iter_indicates_dnssec(qstate->env,
2854 			iq->dp, iq->response, iq->qchase.qclass);
2855 		/* if dnssec, validating then also fetch the key for the DS */
2856 		if(iq->dnssec_expected && qstate->env->cfg->prefetch_key &&
2857 			!(qstate->query_flags&BIT_CD))
2858 			generate_dnskey_prefetch(qstate, iq, id);
2859 
2860 		/* spawn off NS and addr to auth servers for the NS we just
2861 		 * got in the referral. This gets authoritative answer
2862 		 * (answer section trust level) rrset.
2863 		 * right after, we detach the subs, answer goes to cache. */
2864 		if(qstate->env->cfg->harden_referral_path)
2865 			generate_ns_check(qstate, iq, id);
2866 
2867 		/* stop current outstanding queries.
2868 		 * FIXME: should the outstanding queries be waited for and
2869 		 * handled? Say by a subquery that inherits the outbound_entry.
2870 		 */
2871 		outbound_list_clear(&iq->outlist);
2872 		iq->num_current_queries = 0;
2873 		fptr_ok(fptr_whitelist_modenv_detach_subs(
2874 			qstate->env->detach_subs));
2875 		(*qstate->env->detach_subs)(qstate);
2876 		iq->num_target_queries = 0;
2877 		verbose(VERB_ALGO, "cleared outbound list for next round");
2878 		return next_state(iq, QUERYTARGETS_STATE);
2879 	} else if(type == RESPONSE_TYPE_CNAME) {
2880 		uint8_t* sname = NULL;
2881 		size_t snamelen = 0;
2882 		/* CNAME type responses get a query restart (i.e., get a
2883 		 * reset of the query state and go back to INIT_REQUEST_STATE).
2884 		 */
2885 		verbose(VERB_DETAIL, "query response was CNAME");
2886 		if(verbosity >= VERB_ALGO)
2887 			log_dns_msg("cname msg", &iq->response->qinfo,
2888 				iq->response->rep);
2889 		/* if qtype is DS, check we have the right level of answer,
2890 		 * like grandchild answer but we need the middle, reject it */
2891 		if(iq->qchase.qtype == LDNS_RR_TYPE_DS && !iq->dsns_point
2892 			&& !(iq->chase_flags&BIT_RD)
2893 			&& iter_ds_toolow(iq->response, iq->dp)
2894 			&& iter_dp_cangodown(&iq->qchase, iq->dp)) {
2895 			outbound_list_clear(&iq->outlist);
2896 			iq->num_current_queries = 0;
2897 			fptr_ok(fptr_whitelist_modenv_detach_subs(
2898 				qstate->env->detach_subs));
2899 			(*qstate->env->detach_subs)(qstate);
2900 			iq->num_target_queries = 0;
2901 			return processDSNSFind(qstate, iq, id);
2902 		}
2903 		/* Process the CNAME response. */
2904 		if(!handle_cname_response(qstate, iq, iq->response,
2905 			&sname, &snamelen)) {
2906 			errinf(qstate, "malloc failure, CNAME info");
2907 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
2908 		}
2909 		/* cache the CNAME response under the current query */
2910 		/* NOTE : set referral=1, so that rrsets get stored but not
2911 		 * the partial query answer (CNAME only). */
2912 		/* prefetchleeway applied because this updates answer parts */
2913 		if(!qstate->no_cache_store)
2914 			iter_dns_store(qstate->env, &iq->response->qinfo,
2915 				iq->response->rep, 1, qstate->prefetch_leeway,
2916 				iq->dp&&iq->dp->has_parent_side_NS, NULL,
2917 				qstate->query_flags);
2918 		/* set the current request's qname to the new value. */
2919 		iq->qchase.qname = sname;
2920 		iq->qchase.qname_len = snamelen;
2921 		/* Clear the query state, since this is a query restart. */
2922 		iq->deleg_msg = NULL;
2923 		iq->dp = NULL;
2924 		iq->dsns_point = NULL;
2925 		iq->auth_zone_response = 0;
2926 		iq->sent_count = 0;
2927 		if(iq->minimisation_state != MINIMISE_STATE)
2928 			/* Only count as query restart when it is not an extra
2929 			 * query as result of qname minimisation. */
2930 			iq->query_restart_count++;
2931 		if(qstate->env->cfg->qname_minimisation)
2932 			iq->minimisation_state = INIT_MINIMISE_STATE;
2933 
2934 		/* stop current outstanding queries.
2935 		 * FIXME: should the outstanding queries be waited for and
2936 		 * handled? Say by a subquery that inherits the outbound_entry.
2937 		 */
2938 		outbound_list_clear(&iq->outlist);
2939 		iq->num_current_queries = 0;
2940 		fptr_ok(fptr_whitelist_modenv_detach_subs(
2941 			qstate->env->detach_subs));
2942 		(*qstate->env->detach_subs)(qstate);
2943 		iq->num_target_queries = 0;
2944 		if(qstate->reply)
2945 			sock_list_insert(&qstate->reply_origin,
2946 				&qstate->reply->addr, qstate->reply->addrlen,
2947 				qstate->region);
2948 		verbose(VERB_ALGO, "cleared outbound list for query restart");
2949 		/* go to INIT_REQUEST_STATE for new qname. */
2950 		return next_state(iq, INIT_REQUEST_STATE);
2951 	} else if(type == RESPONSE_TYPE_LAME) {
2952 		/* Cache the LAMEness. */
2953 		verbose(VERB_DETAIL, "query response was %sLAME",
2954 			dnsseclame?"DNSSEC ":"");
2955 		if(!dname_subdomain_c(iq->qchase.qname, iq->dp->name)) {
2956 			log_err("mark lame: mismatch in qname and dpname");
2957 			/* throwaway this reply below */
2958 		} else if(qstate->reply) {
2959 			/* need addr for lameness cache, but we may have
2960 			 * gotten this from cache, so test to be sure */
2961 			if(!infra_set_lame(qstate->env->infra_cache,
2962 				&qstate->reply->addr, qstate->reply->addrlen,
2963 				iq->dp->name, iq->dp->namelen,
2964 				*qstate->env->now, dnsseclame, 0,
2965 				iq->qchase.qtype))
2966 				log_err("mark host lame: out of memory");
2967 		}
2968 	} else if(type == RESPONSE_TYPE_REC_LAME) {
2969 		/* Cache the LAMEness. */
2970 		verbose(VERB_DETAIL, "query response REC_LAME: "
2971 			"recursive but not authoritative server");
2972 		if(!dname_subdomain_c(iq->qchase.qname, iq->dp->name)) {
2973 			log_err("mark rec_lame: mismatch in qname and dpname");
2974 			/* throwaway this reply below */
2975 		} else if(qstate->reply) {
2976 			/* need addr for lameness cache, but we may have
2977 			 * gotten this from cache, so test to be sure */
2978 			verbose(VERB_DETAIL, "mark as REC_LAME");
2979 			if(!infra_set_lame(qstate->env->infra_cache,
2980 				&qstate->reply->addr, qstate->reply->addrlen,
2981 				iq->dp->name, iq->dp->namelen,
2982 				*qstate->env->now, 0, 1, iq->qchase.qtype))
2983 				log_err("mark host lame: out of memory");
2984 		}
2985 	} else if(type == RESPONSE_TYPE_THROWAWAY) {
2986 		/* LAME and THROWAWAY responses are handled the same way.
2987 		 * In this case, the event is just sent directly back to
2988 		 * the QUERYTARGETS_STATE without resetting anything,
2989 		 * because, clearly, the next target must be tried. */
2990 		verbose(VERB_DETAIL, "query response was THROWAWAY");
2991 	} else {
2992 		log_warn("A query response came back with an unknown type: %d",
2993 			(int)type);
2994 	}
2995 
2996 	/* LAME, THROWAWAY and "unknown" all end up here.
2997 	 * Recycle to the QUERYTARGETS state to hopefully try a
2998 	 * different target. */
2999 	if (qstate->env->cfg->qname_minimisation &&
3000 		!qstate->env->cfg->qname_minimisation_strict)
3001 		iq->minimisation_state = DONOT_MINIMISE_STATE;
3002 	if(iq->auth_zone_response) {
3003 		/* can we fallback? */
3004 		iq->auth_zone_response = 0;
3005 		if(!auth_zones_can_fallback(qstate->env->auth_zones,
3006 			iq->dp->name, iq->dp->namelen, qstate->qinfo.qclass)) {
3007 			verbose(VERB_ALGO, "auth zone response bad, and no"
3008 				" fallback possible, servfail");
3009 			errinf_dname(qstate, "response is bad, no fallback, "
3010 				"for auth zone", iq->dp->name);
3011 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3012 		}
3013 		verbose(VERB_ALGO, "auth zone response was bad, "
3014 			"fallback enabled");
3015 		iq->auth_zone_avoid = 1;
3016 		if(iq->dp->auth_dp) {
3017 			/* we are using a dp for the auth zone, with no
3018 			 * nameservers, get one first */
3019 			iq->dp = NULL;
3020 			return next_state(iq, INIT_REQUEST_STATE);
3021 		}
3022 	}
3023 	return next_state(iq, QUERYTARGETS_STATE);
3024 }
3025 
3026 /**
3027  * Return priming query results to interested super querystates.
3028  *
3029  * Sets the delegation point and delegation message (not nonRD queries).
3030  * This is a callback from walk_supers.
3031  *
3032  * @param qstate: priming query state that finished.
3033  * @param id: module id.
3034  * @param forq: the qstate for which priming has been done.
3035  */
3036 static void
3037 prime_supers(struct module_qstate* qstate, int id, struct module_qstate* forq)
3038 {
3039 	struct iter_qstate* foriq = (struct iter_qstate*)forq->minfo[id];
3040 	struct delegpt* dp = NULL;
3041 
3042 	log_assert(qstate->is_priming || foriq->wait_priming_stub);
3043 	log_assert(qstate->return_rcode == LDNS_RCODE_NOERROR);
3044 	/* Convert our response to a delegation point */
3045 	dp = delegpt_from_message(qstate->return_msg, forq->region);
3046 	if(!dp) {
3047 		/* if there is no convertable delegation point, then
3048 		 * the ANSWER type was (presumably) a negative answer. */
3049 		verbose(VERB_ALGO, "prime response was not a positive "
3050 			"ANSWER; failing");
3051 		foriq->dp = NULL;
3052 		foriq->state = QUERYTARGETS_STATE;
3053 		return;
3054 	}
3055 
3056 	log_query_info(VERB_DETAIL, "priming successful for", &qstate->qinfo);
3057 	delegpt_log(VERB_ALGO, dp);
3058 	foriq->dp = dp;
3059 	foriq->deleg_msg = dns_copy_msg(qstate->return_msg, forq->region);
3060 	if(!foriq->deleg_msg) {
3061 		log_err("copy prime response: out of memory");
3062 		foriq->dp = NULL;
3063 		foriq->state = QUERYTARGETS_STATE;
3064 		return;
3065 	}
3066 
3067 	/* root priming responses go to init stage 2, priming stub
3068 	 * responses to to stage 3. */
3069 	if(foriq->wait_priming_stub) {
3070 		foriq->state = INIT_REQUEST_3_STATE;
3071 		foriq->wait_priming_stub = 0;
3072 	} else	foriq->state = INIT_REQUEST_2_STATE;
3073 	/* because we are finished, the parent will be reactivated */
3074 }
3075 
3076 /**
3077  * This handles the response to a priming query. This is used to handle both
3078  * root and stub priming responses. This is basically the equivalent of the
3079  * QUERY_RESP_STATE, but will not handle CNAME responses and will treat
3080  * REFERRALs as ANSWERS. It will also update and reactivate the originating
3081  * event.
3082  *
3083  * @param qstate: query state.
3084  * @param id: module id.
3085  * @return true if the event needs more immediate processing, false if not.
3086  *         This state always returns false.
3087  */
3088 static int
3089 processPrimeResponse(struct module_qstate* qstate, int id)
3090 {
3091 	struct iter_qstate* iq = (struct iter_qstate*)qstate->minfo[id];
3092 	enum response_type type;
3093 	iq->response->rep->flags &= ~(BIT_RD|BIT_RA); /* ignore rec-lame */
3094 	type = response_type_from_server(
3095 		(int)((iq->chase_flags&BIT_RD) || iq->chase_to_rd),
3096 		iq->response, &iq->qchase, iq->dp);
3097 	if(type == RESPONSE_TYPE_ANSWER) {
3098 		qstate->return_rcode = LDNS_RCODE_NOERROR;
3099 		qstate->return_msg = iq->response;
3100 	} else {
3101 		errinf(qstate, "prime response did not get an answer");
3102 		errinf_dname(qstate, "for", qstate->qinfo.qname);
3103 		qstate->return_rcode = LDNS_RCODE_SERVFAIL;
3104 		qstate->return_msg = NULL;
3105 	}
3106 
3107 	/* validate the root or stub after priming (if enabled).
3108 	 * This is the same query as the prime query, but with validation.
3109 	 * Now that we are primed, the additional queries that validation
3110 	 * may need can be resolved, such as DLV. */
3111 	if(qstate->env->cfg->harden_referral_path) {
3112 		struct module_qstate* subq = NULL;
3113 		log_nametypeclass(VERB_ALGO, "schedule prime validation",
3114 			qstate->qinfo.qname, qstate->qinfo.qtype,
3115 			qstate->qinfo.qclass);
3116 		if(!generate_sub_request(qstate->qinfo.qname,
3117 			qstate->qinfo.qname_len, qstate->qinfo.qtype,
3118 			qstate->qinfo.qclass, qstate, id, iq,
3119 			INIT_REQUEST_STATE, FINISHED_STATE, &subq, 1)) {
3120 			verbose(VERB_ALGO, "could not generate prime check");
3121 		}
3122 		generate_a_aaaa_check(qstate, iq, id);
3123 	}
3124 
3125 	/* This event is finished. */
3126 	qstate->ext_state[id] = module_finished;
3127 	return 0;
3128 }
3129 
3130 /**
3131  * Do final processing on responses to target queries. Events reach this
3132  * state after the iterative resolution algorithm terminates. This state is
3133  * responsible for reactivating the original event, and housekeeping related
3134  * to received target responses (caching, updating the current delegation
3135  * point, etc).
3136  * Callback from walk_supers for every super state that is interested in
3137  * the results from this query.
3138  *
3139  * @param qstate: query state.
3140  * @param id: module id.
3141  * @param forq: super query state.
3142  */
3143 static void
3144 processTargetResponse(struct module_qstate* qstate, int id,
3145 	struct module_qstate* forq)
3146 {
3147 	struct iter_qstate* iq = (struct iter_qstate*)qstate->minfo[id];
3148 	struct iter_qstate* foriq = (struct iter_qstate*)forq->minfo[id];
3149 	struct ub_packed_rrset_key* rrset;
3150 	struct delegpt_ns* dpns;
3151 	log_assert(qstate->return_rcode == LDNS_RCODE_NOERROR);
3152 
3153 	foriq->state = QUERYTARGETS_STATE;
3154 	log_query_info(VERB_ALGO, "processTargetResponse", &qstate->qinfo);
3155 	log_query_info(VERB_ALGO, "processTargetResponse super", &forq->qinfo);
3156 
3157 	/* Tell the originating event that this target query has finished
3158 	 * (regardless if it succeeded or not). */
3159 	foriq->num_target_queries--;
3160 
3161 	/* check to see if parent event is still interested (in orig name).  */
3162 	if(!foriq->dp) {
3163 		verbose(VERB_ALGO, "subq: parent not interested, was reset");
3164 		return; /* not interested anymore */
3165 	}
3166 	dpns = delegpt_find_ns(foriq->dp, qstate->qinfo.qname,
3167 			qstate->qinfo.qname_len);
3168 	if(!dpns) {
3169 		/* If not interested, just stop processing this event */
3170 		verbose(VERB_ALGO, "subq: parent not interested anymore");
3171 		/* could be because parent was jostled out of the cache,
3172 		   and a new identical query arrived, that does not want it*/
3173 		return;
3174 	}
3175 
3176 	/* if iq->query_for_pside_glue then add the pside_glue (marked lame) */
3177 	if(iq->pside_glue) {
3178 		/* if the pside_glue is NULL, then it could not be found,
3179 		 * the done_pside is already set when created and a cache
3180 		 * entry created in processFinished so nothing to do here */
3181 		log_rrset_key(VERB_ALGO, "add parentside glue to dp",
3182 			iq->pside_glue);
3183 		if(!delegpt_add_rrset(foriq->dp, forq->region,
3184 			iq->pside_glue, 1))
3185 			log_err("out of memory adding pside glue");
3186 	}
3187 
3188 	/* This response is relevant to the current query, so we
3189 	 * add (attempt to add, anyway) this target(s) and reactivate
3190 	 * the original event.
3191 	 * NOTE: we could only look for the AnswerRRset if the
3192 	 * response type was ANSWER. */
3193 	rrset = reply_find_answer_rrset(&iq->qchase, qstate->return_msg->rep);
3194 	if(rrset) {
3195 		/* if CNAMEs have been followed - add new NS to delegpt. */
3196 		/* BTW. RFC 1918 says NS should not have got CNAMEs. Robust. */
3197 		if(!delegpt_find_ns(foriq->dp, rrset->rk.dname,
3198 			rrset->rk.dname_len)) {
3199 			/* if dpns->lame then set newcname ns lame too */
3200 			if(!delegpt_add_ns(foriq->dp, forq->region,
3201 				rrset->rk.dname, dpns->lame))
3202 				log_err("out of memory adding cnamed-ns");
3203 		}
3204 		/* if dpns->lame then set the address(es) lame too */
3205 		if(!delegpt_add_rrset(foriq->dp, forq->region, rrset,
3206 			dpns->lame))
3207 			log_err("out of memory adding targets");
3208 		verbose(VERB_ALGO, "added target response");
3209 		delegpt_log(VERB_ALGO, foriq->dp);
3210 	} else {
3211 		verbose(VERB_ALGO, "iterator TargetResponse failed");
3212 		dpns->resolved = 1; /* fail the target */
3213 	}
3214 }
3215 
3216 /**
3217  * Process response for DS NS Find queries, that attempt to find the delegation
3218  * point where we ask the DS query from.
3219  *
3220  * @param qstate: query state.
3221  * @param id: module id.
3222  * @param forq: super query state.
3223  */
3224 static void
3225 processDSNSResponse(struct module_qstate* qstate, int id,
3226 	struct module_qstate* forq)
3227 {
3228 	struct iter_qstate* foriq = (struct iter_qstate*)forq->minfo[id];
3229 
3230 	/* if the finished (iq->response) query has no NS set: continue
3231 	 * up to look for the right dp; nothing to change, do DPNSstate */
3232 	if(qstate->return_rcode != LDNS_RCODE_NOERROR)
3233 		return; /* seek further */
3234 	/* find the NS RRset (without allowing CNAMEs) */
3235 	if(!reply_find_rrset(qstate->return_msg->rep, qstate->qinfo.qname,
3236 		qstate->qinfo.qname_len, LDNS_RR_TYPE_NS,
3237 		qstate->qinfo.qclass)){
3238 		return; /* seek further */
3239 	}
3240 
3241 	/* else, store as DP and continue at querytargets */
3242 	foriq->state = QUERYTARGETS_STATE;
3243 	foriq->dp = delegpt_from_message(qstate->return_msg, forq->region);
3244 	if(!foriq->dp) {
3245 		log_err("out of memory in dsns dp alloc");
3246 		errinf(qstate, "malloc failure, in DS search");
3247 		return; /* dp==NULL in QUERYTARGETS makes SERVFAIL */
3248 	}
3249 	/* success, go query the querytargets in the new dp (and go down) */
3250 }
3251 
3252 /**
3253  * Process response for qclass=ANY queries for a particular class.
3254  * Append to result or error-exit.
3255  *
3256  * @param qstate: query state.
3257  * @param id: module id.
3258  * @param forq: super query state.
3259  */
3260 static void
3261 processClassResponse(struct module_qstate* qstate, int id,
3262 	struct module_qstate* forq)
3263 {
3264 	struct iter_qstate* foriq = (struct iter_qstate*)forq->minfo[id];
3265 	struct dns_msg* from = qstate->return_msg;
3266 	log_query_info(VERB_ALGO, "processClassResponse", &qstate->qinfo);
3267 	log_query_info(VERB_ALGO, "processClassResponse super", &forq->qinfo);
3268 	if(qstate->return_rcode != LDNS_RCODE_NOERROR) {
3269 		/* cause servfail for qclass ANY query */
3270 		foriq->response = NULL;
3271 		foriq->state = FINISHED_STATE;
3272 		return;
3273 	}
3274 	/* append result */
3275 	if(!foriq->response) {
3276 		/* allocate the response: copy RCODE, sec_state */
3277 		foriq->response = dns_copy_msg(from, forq->region);
3278 		if(!foriq->response) {
3279 			log_err("malloc failed for qclass ANY response");
3280 			foriq->state = FINISHED_STATE;
3281 			return;
3282 		}
3283 		foriq->response->qinfo.qclass = forq->qinfo.qclass;
3284 		/* qclass ANY does not receive the AA flag on replies */
3285 		foriq->response->rep->authoritative = 0;
3286 	} else {
3287 		struct dns_msg* to = foriq->response;
3288 		/* add _from_ this response _to_ existing collection */
3289 		/* if there are records, copy RCODE */
3290 		/* lower sec_state if this message is lower */
3291 		if(from->rep->rrset_count != 0) {
3292 			size_t n = from->rep->rrset_count+to->rep->rrset_count;
3293 			struct ub_packed_rrset_key** dest, **d;
3294 			/* copy appropriate rcode */
3295 			to->rep->flags = from->rep->flags;
3296 			/* copy rrsets */
3297 			if(from->rep->rrset_count > RR_COUNT_MAX ||
3298 				to->rep->rrset_count > RR_COUNT_MAX) {
3299 				log_err("malloc failed (too many rrsets) in collect ANY");
3300 				foriq->state = FINISHED_STATE;
3301 				return; /* integer overflow protection */
3302 			}
3303 			dest = regional_alloc(forq->region, sizeof(dest[0])*n);
3304 			if(!dest) {
3305 				log_err("malloc failed in collect ANY");
3306 				foriq->state = FINISHED_STATE;
3307 				return;
3308 			}
3309 			d = dest;
3310 			/* copy AN */
3311 			memcpy(dest, to->rep->rrsets, to->rep->an_numrrsets
3312 				* sizeof(dest[0]));
3313 			dest += to->rep->an_numrrsets;
3314 			memcpy(dest, from->rep->rrsets, from->rep->an_numrrsets
3315 				* sizeof(dest[0]));
3316 			dest += from->rep->an_numrrsets;
3317 			/* copy NS */
3318 			memcpy(dest, to->rep->rrsets+to->rep->an_numrrsets,
3319 				to->rep->ns_numrrsets * sizeof(dest[0]));
3320 			dest += to->rep->ns_numrrsets;
3321 			memcpy(dest, from->rep->rrsets+from->rep->an_numrrsets,
3322 				from->rep->ns_numrrsets * sizeof(dest[0]));
3323 			dest += from->rep->ns_numrrsets;
3324 			/* copy AR */
3325 			memcpy(dest, to->rep->rrsets+to->rep->an_numrrsets+
3326 				to->rep->ns_numrrsets,
3327 				to->rep->ar_numrrsets * sizeof(dest[0]));
3328 			dest += to->rep->ar_numrrsets;
3329 			memcpy(dest, from->rep->rrsets+from->rep->an_numrrsets+
3330 				from->rep->ns_numrrsets,
3331 				from->rep->ar_numrrsets * sizeof(dest[0]));
3332 			/* update counts */
3333 			to->rep->rrsets = d;
3334 			to->rep->an_numrrsets += from->rep->an_numrrsets;
3335 			to->rep->ns_numrrsets += from->rep->ns_numrrsets;
3336 			to->rep->ar_numrrsets += from->rep->ar_numrrsets;
3337 			to->rep->rrset_count = n;
3338 		}
3339 		if(from->rep->security < to->rep->security) /* lowest sec */
3340 			to->rep->security = from->rep->security;
3341 		if(from->rep->qdcount != 0) /* insert qd if appropriate */
3342 			to->rep->qdcount = from->rep->qdcount;
3343 		if(from->rep->ttl < to->rep->ttl) /* use smallest TTL */
3344 			to->rep->ttl = from->rep->ttl;
3345 		if(from->rep->prefetch_ttl < to->rep->prefetch_ttl)
3346 			to->rep->prefetch_ttl = from->rep->prefetch_ttl;
3347 		if(from->rep->serve_expired_ttl < to->rep->serve_expired_ttl)
3348 			to->rep->serve_expired_ttl = from->rep->serve_expired_ttl;
3349 	}
3350 	/* are we done? */
3351 	foriq->num_current_queries --;
3352 	if(foriq->num_current_queries == 0)
3353 		foriq->state = FINISHED_STATE;
3354 }
3355 
3356 /**
3357  * Collect class ANY responses and make them into one response.  This
3358  * state is started and it creates queries for all classes (that have
3359  * root hints).  The answers are then collected.
3360  *
3361  * @param qstate: query state.
3362  * @param id: module id.
3363  * @return true if the event needs more immediate processing, false if not.
3364  */
3365 static int
3366 processCollectClass(struct module_qstate* qstate, int id)
3367 {
3368 	struct iter_qstate* iq = (struct iter_qstate*)qstate->minfo[id];
3369 	struct module_qstate* subq;
3370 	/* If qchase.qclass == 0 then send out queries for all classes.
3371 	 * Otherwise, do nothing (wait for all answers to arrive and the
3372 	 * processClassResponse to put them together, and that moves us
3373 	 * towards the Finished state when done. */
3374 	if(iq->qchase.qclass == 0) {
3375 		uint16_t c = 0;
3376 		iq->qchase.qclass = LDNS_RR_CLASS_ANY;
3377 		while(iter_get_next_root(qstate->env->hints,
3378 			qstate->env->fwds, &c)) {
3379 			/* generate query for this class */
3380 			log_nametypeclass(VERB_ALGO, "spawn collect query",
3381 				qstate->qinfo.qname, qstate->qinfo.qtype, c);
3382 			if(!generate_sub_request(qstate->qinfo.qname,
3383 				qstate->qinfo.qname_len, qstate->qinfo.qtype,
3384 				c, qstate, id, iq, INIT_REQUEST_STATE,
3385 				FINISHED_STATE, &subq,
3386 				(int)!(qstate->query_flags&BIT_CD))) {
3387 				errinf(qstate, "could not generate class ANY"
3388 					" lookup query");
3389 				return error_response(qstate, id,
3390 					LDNS_RCODE_SERVFAIL);
3391 			}
3392 			/* ignore subq, no special init required */
3393 			iq->num_current_queries ++;
3394 			if(c == 0xffff)
3395 				break;
3396 			else c++;
3397 		}
3398 		/* if no roots are configured at all, return */
3399 		if(iq->num_current_queries == 0) {
3400 			verbose(VERB_ALGO, "No root hints or fwds, giving up "
3401 				"on qclass ANY");
3402 			return error_response(qstate, id, LDNS_RCODE_REFUSED);
3403 		}
3404 		/* return false, wait for queries to return */
3405 	}
3406 	/* if woke up here because of an answer, wait for more answers */
3407 	return 0;
3408 }
3409 
3410 /**
3411  * This handles the final state for first-tier responses (i.e., responses to
3412  * externally generated queries).
3413  *
3414  * @param qstate: query state.
3415  * @param iq: iterator query state.
3416  * @param id: module id.
3417  * @return true if the event needs more processing, false if not. Since this
3418  *         is the final state for an event, it always returns false.
3419  */
3420 static int
3421 processFinished(struct module_qstate* qstate, struct iter_qstate* iq,
3422 	int id)
3423 {
3424 	log_query_info(VERB_QUERY, "finishing processing for",
3425 		&qstate->qinfo);
3426 
3427 	/* store negative cache element for parent side glue. */
3428 	if(!qstate->no_cache_store && iq->query_for_pside_glue
3429 		&& !iq->pside_glue)
3430 			iter_store_parentside_neg(qstate->env, &qstate->qinfo,
3431 				iq->deleg_msg?iq->deleg_msg->rep:
3432 				(iq->response?iq->response->rep:NULL));
3433 	if(!iq->response) {
3434 		verbose(VERB_ALGO, "No response is set, servfail");
3435 		errinf(qstate, "(no response found at query finish)");
3436 		return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3437 	}
3438 
3439 	/* Make sure that the RA flag is set (since the presence of
3440 	 * this module means that recursion is available) */
3441 	iq->response->rep->flags |= BIT_RA;
3442 
3443 	/* Clear the AA flag */
3444 	/* FIXME: does this action go here or in some other module? */
3445 	iq->response->rep->flags &= ~BIT_AA;
3446 
3447 	/* make sure QR flag is on */
3448 	iq->response->rep->flags |= BIT_QR;
3449 
3450 	/* we have finished processing this query */
3451 	qstate->ext_state[id] = module_finished;
3452 
3453 	/* TODO:  we are using a private TTL, trim the response. */
3454 	/* if (mPrivateTTL > 0){IterUtils.setPrivateTTL(resp, mPrivateTTL); } */
3455 
3456 	/* prepend any items we have accumulated */
3457 	if(iq->an_prepend_list || iq->ns_prepend_list) {
3458 		if(!iter_prepend(iq, iq->response, qstate->region)) {
3459 			log_err("prepend rrsets: out of memory");
3460 			return error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3461 		}
3462 		/* reset the query name back */
3463 		iq->response->qinfo = qstate->qinfo;
3464 		/* the security state depends on the combination */
3465 		iq->response->rep->security = sec_status_unchecked;
3466 		/* store message with the finished prepended items,
3467 		 * but only if we did recursion. The nonrecursion referral
3468 		 * from cache does not need to be stored in the msg cache. */
3469 		if(!qstate->no_cache_store && qstate->query_flags&BIT_RD) {
3470 			iter_dns_store(qstate->env, &qstate->qinfo,
3471 				iq->response->rep, 0, qstate->prefetch_leeway,
3472 				iq->dp&&iq->dp->has_parent_side_NS,
3473 				qstate->region, qstate->query_flags);
3474 		}
3475 	}
3476 	qstate->return_rcode = LDNS_RCODE_NOERROR;
3477 	qstate->return_msg = iq->response;
3478 	return 0;
3479 }
3480 
3481 /*
3482  * Return priming query results to interested super querystates.
3483  *
3484  * Sets the delegation point and delegation message (not nonRD queries).
3485  * This is a callback from walk_supers.
3486  *
3487  * @param qstate: query state that finished.
3488  * @param id: module id.
3489  * @param super: the qstate to inform.
3490  */
3491 void
3492 iter_inform_super(struct module_qstate* qstate, int id,
3493 	struct module_qstate* super)
3494 {
3495 	if(!qstate->is_priming && super->qinfo.qclass == LDNS_RR_CLASS_ANY)
3496 		processClassResponse(qstate, id, super);
3497 	else if(super->qinfo.qtype == LDNS_RR_TYPE_DS && ((struct iter_qstate*)
3498 		super->minfo[id])->state == DSNS_FIND_STATE)
3499 		processDSNSResponse(qstate, id, super);
3500 	else if(qstate->return_rcode != LDNS_RCODE_NOERROR)
3501 		error_supers(qstate, id, super);
3502 	else if(qstate->is_priming)
3503 		prime_supers(qstate, id, super);
3504 	else	processTargetResponse(qstate, id, super);
3505 }
3506 
3507 /**
3508  * Handle iterator state.
3509  * Handle events. This is the real processing loop for events, responsible
3510  * for moving events through the various states. If a processing method
3511  * returns true, then it will be advanced to the next state. If false, then
3512  * processing will stop.
3513  *
3514  * @param qstate: query state.
3515  * @param ie: iterator shared global environment.
3516  * @param iq: iterator query state.
3517  * @param id: module id.
3518  */
3519 static void
3520 iter_handle(struct module_qstate* qstate, struct iter_qstate* iq,
3521 	struct iter_env* ie, int id)
3522 {
3523 	int cont = 1;
3524 	while(cont) {
3525 		verbose(VERB_ALGO, "iter_handle processing q with state %s",
3526 			iter_state_to_string(iq->state));
3527 		switch(iq->state) {
3528 			case INIT_REQUEST_STATE:
3529 				cont = processInitRequest(qstate, iq, ie, id);
3530 				break;
3531 			case INIT_REQUEST_2_STATE:
3532 				cont = processInitRequest2(qstate, iq, id);
3533 				break;
3534 			case INIT_REQUEST_3_STATE:
3535 				cont = processInitRequest3(qstate, iq, id);
3536 				break;
3537 			case QUERYTARGETS_STATE:
3538 				cont = processQueryTargets(qstate, iq, ie, id);
3539 				break;
3540 			case QUERY_RESP_STATE:
3541 				cont = processQueryResponse(qstate, iq, id);
3542 				break;
3543 			case PRIME_RESP_STATE:
3544 				cont = processPrimeResponse(qstate, id);
3545 				break;
3546 			case COLLECT_CLASS_STATE:
3547 				cont = processCollectClass(qstate, id);
3548 				break;
3549 			case DSNS_FIND_STATE:
3550 				cont = processDSNSFind(qstate, iq, id);
3551 				break;
3552 			case FINISHED_STATE:
3553 				cont = processFinished(qstate, iq, id);
3554 				break;
3555 			default:
3556 				log_warn("iterator: invalid state: %d",
3557 					iq->state);
3558 				cont = 0;
3559 				break;
3560 		}
3561 	}
3562 }
3563 
3564 /**
3565  * This is the primary entry point for processing request events. Note that
3566  * this method should only be used by external modules.
3567  * @param qstate: query state.
3568  * @param ie: iterator shared global environment.
3569  * @param iq: iterator query state.
3570  * @param id: module id.
3571  */
3572 static void
3573 process_request(struct module_qstate* qstate, struct iter_qstate* iq,
3574 	struct iter_env* ie, int id)
3575 {
3576 	/* external requests start in the INIT state, and finish using the
3577 	 * FINISHED state. */
3578 	iq->state = INIT_REQUEST_STATE;
3579 	iq->final_state = FINISHED_STATE;
3580 	verbose(VERB_ALGO, "process_request: new external request event");
3581 	iter_handle(qstate, iq, ie, id);
3582 }
3583 
3584 /** process authoritative server reply */
3585 static void
3586 process_response(struct module_qstate* qstate, struct iter_qstate* iq,
3587 	struct iter_env* ie, int id, struct outbound_entry* outbound,
3588 	enum module_ev event)
3589 {
3590 	struct msg_parse* prs;
3591 	struct edns_data edns;
3592 	sldns_buffer* pkt;
3593 
3594 	verbose(VERB_ALGO, "process_response: new external response event");
3595 	iq->response = NULL;
3596 	iq->state = QUERY_RESP_STATE;
3597 	if(event == module_event_noreply || event == module_event_error) {
3598 		if(event == module_event_noreply && iq->sent_count >= 3 &&
3599 			qstate->env->cfg->use_caps_bits_for_id &&
3600 			!iq->caps_fallback && !is_caps_whitelisted(ie, iq)) {
3601 			/* start fallback */
3602 			iq->caps_fallback = 1;
3603 			iq->caps_server = 0;
3604 			iq->caps_reply = NULL;
3605 			iq->caps_response = NULL;
3606 			iq->caps_minimisation_state = DONOT_MINIMISE_STATE;
3607 			iq->state = QUERYTARGETS_STATE;
3608 			iq->num_current_queries--;
3609 			/* need fresh attempts for the 0x20 fallback, if
3610 			 * that was the cause for the failure */
3611 			iter_dec_attempts(iq->dp, 3);
3612 			verbose(VERB_DETAIL, "Capsforid: timeouts, starting fallback");
3613 			goto handle_it;
3614 		}
3615 		goto handle_it;
3616 	}
3617 	if( (event != module_event_reply && event != module_event_capsfail)
3618 		|| !qstate->reply) {
3619 		log_err("Bad event combined with response");
3620 		outbound_list_remove(&iq->outlist, outbound);
3621 		errinf(qstate, "module iterator received wrong internal event with a response message");
3622 		(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3623 		return;
3624 	}
3625 
3626 	/* parse message */
3627 	prs = (struct msg_parse*)regional_alloc(qstate->env->scratch,
3628 		sizeof(struct msg_parse));
3629 	if(!prs) {
3630 		log_err("out of memory on incoming message");
3631 		/* like packet got dropped */
3632 		goto handle_it;
3633 	}
3634 	memset(prs, 0, sizeof(*prs));
3635 	memset(&edns, 0, sizeof(edns));
3636 	pkt = qstate->reply->c->buffer;
3637 	sldns_buffer_set_position(pkt, 0);
3638 	if(parse_packet(pkt, prs, qstate->env->scratch) != LDNS_RCODE_NOERROR) {
3639 		verbose(VERB_ALGO, "parse error on reply packet");
3640 		goto handle_it;
3641 	}
3642 	/* edns is not examined, but removed from message to help cache */
3643 	if(parse_extract_edns(prs, &edns, qstate->env->scratch) !=
3644 		LDNS_RCODE_NOERROR)
3645 		goto handle_it;
3646 
3647 	/* Copy the edns options we may got from the back end */
3648 	if(edns.opt_list) {
3649 		qstate->edns_opts_back_in = edns_opt_copy_region(edns.opt_list,
3650 			qstate->region);
3651 		if(!qstate->edns_opts_back_in) {
3652 			log_err("out of memory on incoming message");
3653 			/* like packet got dropped */
3654 			goto handle_it;
3655 		}
3656 		if(!inplace_cb_edns_back_parsed_call(qstate->env, qstate)) {
3657 			log_err("unable to call edns_back_parsed callback");
3658 			goto handle_it;
3659 		}
3660 	}
3661 
3662 	/* remove CD-bit, we asked for in case we handle validation ourself */
3663 	prs->flags &= ~BIT_CD;
3664 
3665 	/* normalize and sanitize: easy to delete items from linked lists */
3666 	if(!scrub_message(pkt, prs, &iq->qinfo_out, iq->dp->name,
3667 		qstate->env->scratch, qstate->env, ie)) {
3668 		/* if 0x20 enabled, start fallback, but we have no message */
3669 		if(event == module_event_capsfail && !iq->caps_fallback) {
3670 			iq->caps_fallback = 1;
3671 			iq->caps_server = 0;
3672 			iq->caps_reply = NULL;
3673 			iq->caps_response = NULL;
3674 			iq->caps_minimisation_state = DONOT_MINIMISE_STATE;
3675 			iq->state = QUERYTARGETS_STATE;
3676 			iq->num_current_queries--;
3677 			verbose(VERB_DETAIL, "Capsforid: scrub failed, starting fallback with no response");
3678 		}
3679 		goto handle_it;
3680 	}
3681 
3682 	/* allocate response dns_msg in region */
3683 	iq->response = dns_alloc_msg(pkt, prs, qstate->region);
3684 	if(!iq->response)
3685 		goto handle_it;
3686 	log_query_info(VERB_DETAIL, "response for", &qstate->qinfo);
3687 	log_name_addr(VERB_DETAIL, "reply from", iq->dp->name,
3688 		&qstate->reply->addr, qstate->reply->addrlen);
3689 	if(verbosity >= VERB_ALGO)
3690 		log_dns_msg("incoming scrubbed packet:", &iq->response->qinfo,
3691 			iq->response->rep);
3692 
3693 	if(event == module_event_capsfail || iq->caps_fallback) {
3694 		if(qstate->env->cfg->qname_minimisation &&
3695 			iq->minimisation_state != DONOT_MINIMISE_STATE) {
3696 			/* Skip QNAME minimisation for next query, since that
3697 			 * one has to match the current query. */
3698 			iq->minimisation_state = SKIP_MINIMISE_STATE;
3699 		}
3700 		/* for fallback we care about main answer, not additionals */
3701 		/* removing that makes comparison more likely to succeed */
3702 		caps_strip_reply(iq->response->rep);
3703 
3704 		if(iq->caps_fallback &&
3705 			iq->caps_minimisation_state != iq->minimisation_state) {
3706 			/* QNAME minimisation state has changed, restart caps
3707 			 * fallback. */
3708 			iq->caps_fallback = 0;
3709 		}
3710 
3711 		if(!iq->caps_fallback) {
3712 			/* start fallback */
3713 			iq->caps_fallback = 1;
3714 			iq->caps_server = 0;
3715 			iq->caps_reply = iq->response->rep;
3716 			iq->caps_response = iq->response;
3717 			iq->caps_minimisation_state = iq->minimisation_state;
3718 			iq->state = QUERYTARGETS_STATE;
3719 			iq->num_current_queries--;
3720 			verbose(VERB_DETAIL, "Capsforid: starting fallback");
3721 			goto handle_it;
3722 		} else {
3723 			/* check if reply is the same, otherwise, fail */
3724 			if(!iq->caps_reply) {
3725 				iq->caps_reply = iq->response->rep;
3726 				iq->caps_response = iq->response;
3727 				iq->caps_server = -1; /*become zero at ++,
3728 				so that we start the full set of trials */
3729 			} else if(caps_failed_rcode(iq->caps_reply) &&
3730 				!caps_failed_rcode(iq->response->rep)) {
3731 				/* prefer to upgrade to non-SERVFAIL */
3732 				iq->caps_reply = iq->response->rep;
3733 				iq->caps_response = iq->response;
3734 			} else if(!caps_failed_rcode(iq->caps_reply) &&
3735 				caps_failed_rcode(iq->response->rep)) {
3736 				/* if we have non-SERVFAIL as answer then
3737 				 * we can ignore SERVFAILs for the equality
3738 				 * comparison */
3739 				/* no instructions here, skip other else */
3740 			} else if(caps_failed_rcode(iq->caps_reply) &&
3741 				caps_failed_rcode(iq->response->rep)) {
3742 				/* failure is same as other failure in fallbk*/
3743 				/* no instructions here, skip other else */
3744 			} else if(!reply_equal(iq->response->rep, iq->caps_reply,
3745 				qstate->env->scratch)) {
3746 				verbose(VERB_DETAIL, "Capsforid fallback: "
3747 					"getting different replies, failed");
3748 				outbound_list_remove(&iq->outlist, outbound);
3749 				errinf(qstate, "0x20 failed, then got different replies in fallback");
3750 				(void)error_response(qstate, id,
3751 					LDNS_RCODE_SERVFAIL);
3752 				return;
3753 			}
3754 			/* continue the fallback procedure at next server */
3755 			iq->caps_server++;
3756 			iq->state = QUERYTARGETS_STATE;
3757 			iq->num_current_queries--;
3758 			verbose(VERB_DETAIL, "Capsforid: reply is equal. "
3759 				"go to next fallback");
3760 			goto handle_it;
3761 		}
3762 	}
3763 	iq->caps_fallback = 0; /* if we were in fallback, 0x20 is OK now */
3764 
3765 handle_it:
3766 	outbound_list_remove(&iq->outlist, outbound);
3767 	iter_handle(qstate, iq, ie, id);
3768 }
3769 
3770 void
3771 iter_operate(struct module_qstate* qstate, enum module_ev event, int id,
3772 	struct outbound_entry* outbound)
3773 {
3774 	struct iter_env* ie = (struct iter_env*)qstate->env->modinfo[id];
3775 	struct iter_qstate* iq = (struct iter_qstate*)qstate->minfo[id];
3776 	verbose(VERB_QUERY, "iterator[module %d] operate: extstate:%s event:%s",
3777 		id, strextstate(qstate->ext_state[id]), strmodulevent(event));
3778 	if(iq) log_query_info(VERB_QUERY, "iterator operate: query",
3779 		&qstate->qinfo);
3780 	if(iq && qstate->qinfo.qname != iq->qchase.qname)
3781 		log_query_info(VERB_QUERY, "iterator operate: chased to",
3782 			&iq->qchase);
3783 
3784 	/* perform iterator state machine */
3785 	if((event == module_event_new || event == module_event_pass) &&
3786 		iq == NULL) {
3787 		if(!iter_new(qstate, id)) {
3788 			errinf(qstate, "malloc failure, new iterator module allocation");
3789 			(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3790 			return;
3791 		}
3792 		iq = (struct iter_qstate*)qstate->minfo[id];
3793 		process_request(qstate, iq, ie, id);
3794 		return;
3795 	}
3796 	if(iq && event == module_event_pass) {
3797 		iter_handle(qstate, iq, ie, id);
3798 		return;
3799 	}
3800 	if(iq && outbound) {
3801 		process_response(qstate, iq, ie, id, outbound, event);
3802 		return;
3803 	}
3804 	if(event == module_event_error) {
3805 		verbose(VERB_ALGO, "got called with event error, giving up");
3806 		errinf(qstate, "iterator module got the error event");
3807 		(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3808 		return;
3809 	}
3810 
3811 	log_err("bad event for iterator");
3812 	errinf(qstate, "iterator module received wrong event");
3813 	(void)error_response(qstate, id, LDNS_RCODE_SERVFAIL);
3814 }
3815 
3816 void
3817 iter_clear(struct module_qstate* qstate, int id)
3818 {
3819 	struct iter_qstate* iq;
3820 	if(!qstate)
3821 		return;
3822 	iq = (struct iter_qstate*)qstate->minfo[id];
3823 	if(iq) {
3824 		outbound_list_clear(&iq->outlist);
3825 		if(iq->target_count && --iq->target_count[0] == 0)
3826 			free(iq->target_count);
3827 		iq->num_current_queries = 0;
3828 	}
3829 	qstate->minfo[id] = NULL;
3830 }
3831 
3832 size_t
3833 iter_get_mem(struct module_env* env, int id)
3834 {
3835 	struct iter_env* ie = (struct iter_env*)env->modinfo[id];
3836 	if(!ie)
3837 		return 0;
3838 	return sizeof(*ie) + sizeof(int)*((size_t)ie->max_dependency_depth+1)
3839 		+ donotq_get_mem(ie->donotq) + priv_get_mem(ie->priv);
3840 }
3841 
3842 /**
3843  * The iterator function block
3844  */
3845 static struct module_func_block iter_block = {
3846 	"iterator",
3847 	&iter_init, &iter_deinit, &iter_operate, &iter_inform_super,
3848 	&iter_clear, &iter_get_mem
3849 };
3850 
3851 struct module_func_block*
3852 iter_get_funcblock(void)
3853 {
3854 	return &iter_block;
3855 }
3856 
3857 const char*
3858 iter_state_to_string(enum iter_state state)
3859 {
3860 	switch (state)
3861 	{
3862 	case INIT_REQUEST_STATE :
3863 		return "INIT REQUEST STATE";
3864 	case INIT_REQUEST_2_STATE :
3865 		return "INIT REQUEST STATE (stage 2)";
3866 	case INIT_REQUEST_3_STATE:
3867 		return "INIT REQUEST STATE (stage 3)";
3868 	case QUERYTARGETS_STATE :
3869 		return "QUERY TARGETS STATE";
3870 	case PRIME_RESP_STATE :
3871 		return "PRIME RESPONSE STATE";
3872 	case COLLECT_CLASS_STATE :
3873 		return "COLLECT CLASS STATE";
3874 	case DSNS_FIND_STATE :
3875 		return "DSNS FIND STATE";
3876 	case QUERY_RESP_STATE :
3877 		return "QUERY RESPONSE STATE";
3878 	case FINISHED_STATE :
3879 		return "FINISHED RESPONSE STATE";
3880 	default :
3881 		return "UNKNOWN ITER STATE";
3882 	}
3883 }
3884 
3885 int
3886 iter_state_is_responsestate(enum iter_state s)
3887 {
3888 	switch(s) {
3889 		case INIT_REQUEST_STATE :
3890 		case INIT_REQUEST_2_STATE :
3891 		case INIT_REQUEST_3_STATE :
3892 		case QUERYTARGETS_STATE :
3893 		case COLLECT_CLASS_STATE :
3894 			return 0;
3895 		default:
3896 			break;
3897 	}
3898 	return 1;
3899 }
3900