processFindKey(struct module_qstate* qstate, struct val_qstate* vq, int id)
{
	uint8_t* target_key_name, *current_key_name;
	size_t target_key_len;
	int strip_lab;
	struct module_qstate* newq = NULL;

	log_query_info(VERB_ALGO, "validator: FindKey", &vq->qchase);
	/* We know that state.key_entry is not 0 or bad key -- if it were,
	 * then previous processing should have directed this event to 
	 * a different state. 
	 * It could be an isnull key, which signals the DNSKEY failed
	 * with retry and has to be looked up again. */
	log_assert(vq->key_entry && !key_entry_isbad(vq->key_entry));
	if(key_entry_isnull(vq->key_entry)) {
		if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
			vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
			vq->qchase.qclass, BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DNSKEY request");
			return val_error(qstate, id);
		}
		return 0;
	}

	target_key_name = vq->signer_name;
	target_key_len = vq->signer_len;
	if(!target_key_name) {
		target_key_name = vq->qchase.qname;
		target_key_len = vq->qchase.qname_len;
	}

	current_key_name = vq->key_entry->name;

	/* If our current key entry matches our target, then we are done. */
	if(query_dname_compare(target_key_name, current_key_name) == 0) {
		vq->state = VAL_VALIDATE_STATE;
		return 1;
	}

	if(vq->empty_DS_name) {
		/* if the last empty nonterminal/emptyDS name we detected is
		 * below the current key, use that name to make progress
		 * along the chain of trust */
		if(query_dname_compare(target_key_name, 
			vq->empty_DS_name) == 0) {
			/* do not query for empty_DS_name again */
			verbose(VERB_ALGO, "Cannot retrieve DS for signature");
			errinf_ede(qstate, "no signatures", LDNS_EDE_RRSIGS_MISSING);
			errinf_origin(qstate, qstate->reply_origin);
			vq->chase_reply->security = sec_status_bogus;
			update_reason_bogus(vq->chase_reply, LDNS_EDE_RRSIGS_MISSING);
			vq->state = VAL_FINISHED_STATE;
			return 1;
		}
		current_key_name = vq->empty_DS_name;
	}

	log_nametypeclass(VERB_ALGO, "current keyname", current_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);
	log_nametypeclass(VERB_ALGO, "target keyname", target_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);
	/* assert we are walking down the DNS tree */
	if(!dname_subdomain_c(target_key_name, current_key_name)) {
		verbose(VERB_ALGO, "bad signer name");
		vq->chase_reply->security = sec_status_bogus;
		vq->state = VAL_FINISHED_STATE;
		return 1;
	}
	/* so this value is >= -1 */
	strip_lab = dname_count_labels(target_key_name) - 
		dname_count_labels(current_key_name) - 1;
	log_assert(strip_lab >= -1);
	verbose(VERB_ALGO, "striplab %d", strip_lab);
	if(strip_lab > 0) {
		dname_remove_labels(&target_key_name, &target_key_len, 
			strip_lab);
	}
	log_nametypeclass(VERB_ALGO, "next keyname", target_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);

	/* The next step is either to query for the next DS, or to query 
	 * for the next DNSKEY. */
	if(vq->ds_rrset)
		log_nametypeclass(VERB_ALGO, "DS RRset", vq->ds_rrset->rk.dname, LDNS_RR_TYPE_DS, LDNS_RR_CLASS_IN);
	else verbose(VERB_ALGO, "No DS RRset");

	if(vq->ds_rrset && query_dname_compare(vq->ds_rrset->rk.dname,
		vq->key_entry->name) != 0) {
		if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
			vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
			vq->qchase.qclass, BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DNSKEY request");
			return val_error(qstate, id);
		}
		return 0;
	}

	if(!vq->ds_rrset || query_dname_compare(vq->ds_rrset->rk.dname,
		target_key_name) != 0) {
		/* check if there is a cache entry : pick up an NSEC if
		 * there is no DS, check if that NSEC has DS-bit unset, and
		 * thus can disprove the secure delegation we seek.
		 * We can then use that NSEC even in the absence of a SOA
		 * record that would be required by the iterator to supply
		 * a completely protocol-correct response. 
		 * Uses negative cache for NSEC3 lookup of DS responses. */
		/* only if cache not blacklisted, of course */
		struct dns_msg* msg;
		if(!qstate->blacklist && !vq->chain_blacklist &&
			(msg=val_find_DS(qstate->env, target_key_name, 
			target_key_len, vq->qchase.qclass, qstate->region,
			vq->key_entry->name)) ) {
			verbose(VERB_ALGO, "Process cached DS response");
			process_ds_response(qstate, vq, id, LDNS_RCODE_NOERROR,
				msg, &msg->qinfo, NULL);
			return 1; /* continue processing ds-response results */
		}
		if(!generate_request(qstate, id, target_key_name, 
			target_key_len, LDNS_RR_TYPE_DS, vq->qchase.qclass,
			BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DS request");
			return val_error(qstate, id);
		}
		return 0;
	}

	/* Otherwise, it is time to query for the DNSKEY */
	if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
		vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
		vq->qchase.qclass, BIT_CD, &newq, 0)) {
		verbose(VERB_ALGO, "error generating DNSKEY request");
		return val_error(qstate, id);
	}

	return 0;
}
processFindKey(struct module_qstate* qstate, struct val_qstate* vq, int id)
{
	uint8_t* target_key_name, *current_key_name;
	size_t target_key_len;
	int strip_lab;
	struct module_qstate* newq = NULL;

	log_query_info(VERB_ALGO, "validator: FindKey", &vq->qchase);
	 
	log_assert(vq->key_entry && !key_entry_isbad(vq->key_entry));
	if(key_entry_isnull(vq->key_entry)) {
		if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
			vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
			vq->qchase.qclass, BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DNSKEY request");
			return val_error(qstate, id);
		}
		return 0;
	}

	target_key_name = vq->signer_name;
	target_key_len = vq->signer_len;
	if(!target_key_name) {
		target_key_name = vq->qchase.qname;
		target_key_len = vq->qchase.qname_len;
	}

	current_key_name = vq->key_entry->name;

	 
	if(query_dname_compare(target_key_name, current_key_name) == 0) {
		vq->state = VAL_VALIDATE_STATE;
		return 1;
	}

	if(vq->empty_DS_name) {
		 
		if(query_dname_compare(target_key_name, 
			vq->empty_DS_name) == 0) {
			 
			verbose(VERB_ALGO, "Cannot retrieve DS for signature");
			errinf_ede(qstate, "no signatures", LDNS_EDE_RRSIGS_MISSING);
			errinf_origin(qstate, qstate->reply_origin);
			vq->chase_reply->security = sec_status_bogus;
			update_reason_bogus(vq->chase_reply, LDNS_EDE_RRSIGS_MISSING);
			vq->state = VAL_FINISHED_STATE;
			return 1;
		}
		current_key_name = vq->empty_DS_name;
	}

	log_nametypeclass(VERB_ALGO, "current keyname", current_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);
	log_nametypeclass(VERB_ALGO, "target keyname", target_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);
	 
	if(!dname_subdomain_c(target_key_name, current_key_name)) {
		verbose(VERB_ALGO, "bad signer name");
		vq->chase_reply->security = sec_status_bogus;
		vq->state = VAL_FINISHED_STATE;
		return 1;
	}
	 
	strip_lab = dname_count_labels(target_key_name) - 
		dname_count_labels(current_key_name) - 1;
	log_assert(strip_lab >= -1);
	verbose(VERB_ALGO, "striplab %d", strip_lab);
	if(strip_lab > 0) {
		dname_remove_labels(&target_key_name, &target_key_len, 
			strip_lab);
	}
	log_nametypeclass(VERB_ALGO, "next keyname", target_key_name,
		LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN);

	 
	if(vq->ds_rrset)
		log_nametypeclass(VERB_ALGO, "DS RRset", vq->ds_rrset->rk.dname, LDNS_RR_TYPE_DS, LDNS_RR_CLASS_IN);
	else verbose(VERB_ALGO, "No DS RRset");

	if(vq->ds_rrset && query_dname_compare(vq->ds_rrset->rk.dname,
		vq->key_entry->name) != 0) {
		if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
			vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
			vq->qchase.qclass, BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DNSKEY request");
			return val_error(qstate, id);
		}
		return 0;
	}

	if(!vq->ds_rrset || query_dname_compare(vq->ds_rrset->rk.dname,
		target_key_name) != 0) {
		 
		 
		struct dns_msg* msg;
		if(!qstate->blacklist && !vq->chain_blacklist &&
			(msg=val_find_DS(qstate->env, target_key_name, 
			target_key_len, vq->qchase.qclass, qstate->region,
			vq->key_entry->name)) ) {
			verbose(VERB_ALGO, "Process cached DS response");
			process_ds_response(qstate, vq, id, LDNS_RCODE_NOERROR,
				msg, &msg->qinfo, NULL);
			return 1;  
		}
		if(!generate_request(qstate, id, target_key_name, 
			target_key_len, LDNS_RR_TYPE_DS, vq->qchase.qclass,
			BIT_CD, &newq, 0)) {
			verbose(VERB_ALGO, "error generating DS request");
			return val_error(qstate, id);
		}
		return 0;
	}

	 
	if(!generate_request(qstate, id, vq->ds_rrset->rk.dname, 
		vq->ds_rrset->rk.dname_len, LDNS_RR_TYPE_DNSKEY, 
		vq->qchase.qclass, BIT_CD, &newq, 0)) {
		verbose(VERB_ALGO, "error generating DNSKEY request");
		return val_error(qstate, id);
	}

	return 0;
}