From 5def8556c610b6e32f99b28741bd4888ca5757ca Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Fri, 25 May 2007 15:28:20 +0000 Subject: [PATCH] iterator and dns cache work. git-svn-id: file:///svn/unbound/trunk@342 be551aaa-1e26-0410-a405-d3ace91eadb9 --- doc/Changelog | 2 + iterator/iter_utils.c | 2 +- iterator/iterator.c | 384 +++++++++++++++++++++++++++++++++++++++++- iterator/iterator.h | 10 ++ services/cache/dns.c | 117 +++++++++++++ services/cache/dns.h | 28 ++- util/module.c | 11 ++ util/module.h | 7 + util/net_help.c | 13 ++ util/net_help.h | 10 ++ 10 files changed, 578 insertions(+), 6 deletions(-) diff --git a/doc/Changelog b/doc/Changelog index d009617cb..746c84bae 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -5,6 +5,8 @@ - packed rrset key has type and class as easily accessable struct members. They are still kept in network format for fast msg encode. - dns cache find_delegation routine. + - iterator main functions setup. + - dns cache lookup setup. 24 May 2007: Wouter - small changes to prepare for subqueries. diff --git a/iterator/iter_utils.c b/iterator/iter_utils.c index 3b87a14be..9e140ed5d 100644 --- a/iterator/iter_utils.c +++ b/iterator/iter_utils.c @@ -82,7 +82,7 @@ iter_apply_cfg(struct iter_env* iter_env, struct config_file* cfg) return 0; } verbose(VERB_ALGO, "iterator: fwd queries to: %s %d", - cfg->fwd_address, cfg->fwd_port); + cfg->fwd_address, cfg->fwd_port); } return 1; } diff --git a/iterator/iterator.c b/iterator/iterator.c index 19f6f8fca..d70860ce5 100644 --- a/iterator/iterator.c +++ b/iterator/iterator.c @@ -85,6 +85,31 @@ iter_deinit(struct module_env* env, int id) /** new query for iterator */ static int iter_new(struct module_qstate* qstate, int id) +{ + struct iter_qstate* iq = (struct iter_qstate*)region_alloc( + qstate->region, sizeof(struct iter_qstate)); + qstate->minfo[id] = iq; + if(!iq) + return 0; + memset(iq, 0, sizeof(*iq)); + iq->state = INIT_REQUEST_STATE; + iq->final_state = FINISHED_STATE; + iq->prepend_list = NULL; + iq->prepend_last = NULL; + iq->dp = NULL; + iq->current_target = NULL; + iq->num_target_queries = -1; /* default our targetQueries counter. */ + iq->num_current_queries = 0; + iq->query_restart_count = 0; + iq->referral_count = 0; + iq->priming_stub = 0; + outbound_list_init(&iq->outlist); + return 1; +} + +/** new query for iterator in forward mode */ +static int +fwd_new(struct module_qstate* qstate, int id) { struct iter_qstate* iq = (struct iter_qstate*)region_alloc( qstate->region, sizeof(struct iter_qstate)); @@ -98,7 +123,6 @@ iter_new(struct module_qstate* qstate, int id) return 0; memset(iq, 0, sizeof(*iq)); outbound_list_init(&iq->outlist); - iq->num_target_queries = -1; /* default our targetQueries counter. */ if(qstate->qinfo.has_cd) flags |= BIT_CD; e = (*env->send_query)(qstate->qinfo.qname, qstate->qinfo.qnamesize, @@ -147,6 +171,11 @@ perform_forward(struct module_qstate* qstate, enum module_ev event, int id, struct outbound_entry* outbound) { verbose(VERB_ALGO, "iterator: forwarding"); + if(event == module_event_new) { + if(!fwd_new(qstate, id)) + qstate->ext_state[id] = module_error; + return; + } /* it must be a query reply */ if(!outbound) { verbose(VERB_ALGO, "query reply was not serviced"); @@ -166,23 +195,355 @@ perform_forward(struct module_qstate* qstate, enum module_ev event, int id, qstate->ext_state[id] = module_error; } +/** + * Transition to the next state. This can be used to advance a currently + * processing event. It cannot be used to reactivate a forEvent. + * + * @param qstate: query state + * @param iq: iterator query state + * @param nextstate The state to transition to. + * @return true. This is so this can be called as the return value for the + * actual process*State() methods. (Transitioning to the next state + * implies further processing). + */ +static int +next_state(struct module_qstate* qstate, struct iter_qstate* iq, + enum iter_state nextstate) +{ + /* If transitioning to a "response" state, make sure that there is a + * response */ + if(iter_state_is_responsestate(nextstate)) { + if(qstate->reply == NULL) { + log_err("transitioning to response state sans " + "response."); + } + } + iq->state = nextstate; + return 1; +} + +/** + * Transition an event to its final state. Final states always either return + * a result up the module chain, or reactivate a dependent event. Which + * final state to transtion to is set in the module state for the event when + * it was created, and depends on the original purpose of the event. + * + * The response is stored in the qstate->buf buffer. + * + * @param qstate: query state + * @param iq: iterator query state + * @return false. This is so this method can be used as the return value for + * the processState methods. (Transitioning to the final state + */ +static int +final_state(struct module_qstate* qstate, struct iter_qstate* iq) +{ + return next_state(qstate, iq, iq->final_state); +} + +/** + * Return an error to the client + */ +static int +error_response(struct module_qstate* qstate, struct iter_qstate* iq, int rcode) +{ + log_info("err response %s", ldns_lookup_by_id(ldns_rcodes, rcode)? + ldns_lookup_by_id(ldns_rcodes, rcode)->name:"??"); + qinfo_query_encode(qstate->buf, &qstate->qinfo); + LDNS_RCODE_SET(ldns_buffer_begin(qstate->buf), rcode); + LDNS_QR_SET(ldns_buffer_begin(qstate->buf)); + return final_state(qstate, iq); +} + +/** + * Process the initial part of the request handling. This state roughly + * corresponds to resolver algorithms steps 1 (find answer in cache) and 2 + * (find the best servers to ask). + * + * Note that all requests start here, and query restarts revisit this state. + * + * This state either generates: 1) a response, from cache or error, 2) a + * priming event, or 3) forwards the request to the next state (init2, + * generally). + * + * @param qstate: query state. + * @param iq: iterator query state. + * @param ie: iterator shared global environment. + * @return true if the event needs more request processing immediately, + * false if not. + */ +static int +processInitRequest(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + int d; + uint8_t* delname; + size_t delnamelen; + log_nametypeclass("resolving", qstate->qinfo.qname, + qstate->qinfo.qtype, qstate->qinfo.qclass); + /* check effort */ + + /* We enforce a maximum number of query restarts. This is primarily a + * cheap way to prevent CNAME loops. */ + if(iq->query_restart_count > MAX_RESTART_COUNT) { + verbose(VERB_DETAIL, "request has exceeded the maximum number" + " of query restarts with %d", iq->query_restart_count); + return error_response(qstate, iq, LDNS_RCODE_SERVFAIL); + } + + /* We enforce a maximum recursion/dependency depth -- in general, + * this is unnecessary for dependency loops (although it will + * catch those), but it provides a sensible limit to the amount + * of work required to answer a given query. */ + d = module_subreq_depth(qstate); + verbose(VERB_ALGO, "request has dependency depth of %d", d); + if(d > ie->max_dependency_depth) { + verbose(VERB_DETAIL, "request has exceeded the maximum " + "dependency depth with depth of %d", d); + return error_response(qstate, iq, LDNS_RCODE_SERVFAIL); + } + + /* Resolver Algorithm Step 1 -- Look for the answer in local data. */ + + /* This either results in a query restart (CNAME cache response), a + * terminating response (ANSWER), or a cache miss (null). */ + + /* TODO: cache lookup */ + /* lookup qname, qtype qclass */ + + /* TODO: handle positive cache response */ + /* calc response type (from cache msg) */ + /* if cname */ + /* handle cname, overwrite qname, restart */ + /* it is an answer, response, to final state */ + + /* TODO attempt to forward the request */ + + /* TODO attempt to find a covering DNAME in the cache */ + + /* Resolver Algorithm Step 2 -- find the "best" servers. */ + + /* first, adjust for DS queries. To avoid the grandparent problem, + * we just look for the closest set of server to the parent of qname. + */ + delname = qstate->qinfo.qname; + delnamelen = qstate->qinfo.qnamesize; + if(qstate->qinfo.qtype == LDNS_RR_TYPE_DS && delname[0] != 0) { + /* do not adjust root label */ + size_t lablen = delname[0] + 1; + delname += lablen; + delnamelen -= lablen; + } + + /* Lookup the delegation in the cache. If null, then the cache needs + * to be primed for the qclass. */ + iq->dp = dns_cache_find_delegation(qstate->env, delname, delnamelen, + qstate->qinfo.qclass, qstate->region); + + /* If the cache has returned nothing, then we have a root priming + * situation. */ + if(iq->dp == NULL) { + /* Note that the result of this will set a new + * DelegationPoint based on the result of priming. */ + + /* TODO + if(!prime_root(qstate, iq, ie, qstate->qinfo.qclass)) + return error_response(qstate, iq, LDNS_RCODE_SERVFAIL); + */ + + /* priming creates an sends a subordinate query, with + * this query as the parent. So further processing for + * this event will stop until reactivated by the results + * of priming. */ + return false; + } + + /* Reset the RD flag. If this is a query restart, then the RD + * will have been turned off. */ + /* + TODO store original flags and original qinfo + qstate->query_flags |= (qstate->orig_query_flags & BIT_RD); + */ + + /* Otherwise, set the current delegation point and move on to the + * next state. */ + return next_state(qstate, iq, INIT_REQUEST_2_STATE); +} + +#if 0 +/** TODO */ +static int +processInitRequest2(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processInitRequest3(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processQueryTargets(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processQueryResponse(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processPrimeResponse(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processTargetResponse(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} + +/** TODO */ +static int +processFinished(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + return 0; +} +#endif + +/** + * Handle iterator state. + * Handle events. This is the real processing loop for events, responsible + * for moving events through the various states. If a processing method + * returns true, then it will be advanced to the next state. If false, then + * processing will stop. + * + * @param qstate: query state. + * @param ie: iterator shared global environment. + * @param iq: iterator query state. + */ +static void +iter_handle(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + int cont = 1; + while(cont) { + verbose(VERB_ALGO, "iter_handle processing q with state %s", + iter_state_to_string(iq->state)); + switch(iq->state) { + case INIT_REQUEST_STATE: + cont = processInitRequest(qstate, iq, ie); + break; +#if 0 + case INIT_REQUEST_2_STATE: + cont = processInitRequest2(qstate, iq, ie); + break; + case INIT_REQUEST_3_STATE: + cont = processInitRequest3(qstate, iq, ie); + break; + case QUERYTARGETS_STATE: + cont = processQueryTargets(qstate, iq, ie); + break; + case QUERY_RESP_STATE: + cont = processQueryResponse(qstate, iq, ie); + break; + case PRIME_RESP_STATE: + cont = processPrimeResponse(qstate, iq, ie); + break; + case TARGET_RESP_STATE: + cont = processTargetResponse(qstate, iq, ie); + break; + case FINISHED_STATE: + cont = processFinished(qstate, iq, ie); + break; +#endif + default: + log_warn("iterator: invalid state: %d", + iq->state); + cont = 0; + break; + } + } +} + +/** + * This is the primary entry point for processing request events. Note that + * this method should only be used by external modules. + * @param qstate: query state. + * @param ie: iterator shared global environment. + * @param iq: iterator query state. + */ +static void +process_request(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie) +{ + /* external requests start in the INIT state, and finish using the + * FINISHED state. */ + iq->state = INIT_REQUEST_STATE; + iq->final_state = FINISHED_STATE; + verbose(VERB_ALGO, "process_request: new external request event"); + iter_handle(qstate, iq, ie); +} + +/** process authoritative server reply */ +static void +process_response(struct module_qstate* qstate, struct iter_qstate* iq, + struct iter_env* ie, struct outbound_entry* outbound) +{ + verbose(VERB_ALGO, "process_response: new external response event"); + /* TODO outbound: use it for scrubbing and so on */ + iq->state = QUERY_RESP_STATE; + iter_handle(qstate, iq, ie); +} + /** iterator operate on a query */ static void iter_operate(struct module_qstate* qstate, enum module_ev event, int id, struct outbound_entry* outbound) { struct iter_env* ie = (struct iter_env*)qstate->env->modinfo[id]; + struct iter_qstate* iq; verbose(VERB_ALGO, "iterator[module %d] operate: extstate:%s event:%s", id, strextstate(qstate->ext_state[id]), strmodulevent(event)); + if(ie->fwd_addrlen != 0) { + perform_forward(qstate, event, id, outbound); + return; + } + /* perform iterator state machine */ if(event == module_event_new) { - if(!iter_new(qstate, id)) + log_info("iter state machine"); + if(!iter_new(qstate, id)) { qstate->ext_state[id] = module_error; + return; + } + iq = (struct iter_qstate*)qstate->minfo[id]; + process_request(qstate, iq, ie); return; } - if(ie->fwd_addrlen != 0) { - perform_forward(qstate, event, id, outbound); + iq = (struct iter_qstate*)qstate->minfo[id]; + if(event == module_event_reply) { + process_response(qstate, iq, ie, outbound); return; } + /* TODO: uhh */ + log_err("bad event for iterator"); qstate->ext_state[id] = module_error; } @@ -238,3 +599,18 @@ iter_state_to_string(enum iter_state state) return "UNKNOWN ITER STATE"; } } + +int +iter_state_is_responsestate(enum iter_state s) +{ + switch(s) { + case INIT_REQUEST_STATE : + case INIT_REQUEST_2_STATE : + case INIT_REQUEST_3_STATE : + case QUERYTARGETS_STATE : + return 0; + default: + break; + } + return 1; +} diff --git a/iterator/iterator.h b/iterator/iterator.h index bb79b8bb5..5ff8cc3b9 100644 --- a/iterator/iterator.h +++ b/iterator/iterator.h @@ -48,6 +48,9 @@ struct delegpt; struct packed_rrset_list; struct iter_hints; +/** max number of query restarts. Determines max number of CNAME chain. */ +#define MAX_RESTART_COUNT 8 + /** * Global state for the iterator. */ @@ -212,4 +215,11 @@ struct module_func_block* iter_get_funcblock(); */ const char* iter_state_to_string(enum iter_state state); +/** + * See if iterator state is a response state + * @param s: to inspect + * @return true if response state. + */ +int iter_state_is_responsestate(enum iter_state s); + #endif /* ITERATOR_ITERATOR_H */ diff --git a/services/cache/dns.c b/services/cache/dns.c index d82df4a82..8fccb2f30 100644 --- a/services/cache/dns.c +++ b/services/cache/dns.c @@ -46,6 +46,7 @@ #include "util/data/packed_rrset.h" #include "util/module.h" #include "util/net_help.h" +#include "util/region-allocator.h" /** store rrsets in the rrset cache. */ static void @@ -229,3 +230,119 @@ dns_cache_find_delegation(struct module_env* env, uint8_t* qname, delegpt_log(dp); return dp; } + +/** allocate rrset in region - no more locks needed */ +static struct ub_packed_rrset_key* +copy_rrset(struct ub_packed_rrset_key* key, struct region* region) +{ + /* lock, lrutouch rrset in cache */ + return NULL; +} + +/** allocate dns_msg from query_info and reply_info */ +static struct dns_msg* +tomsg(struct msgreply_entry* e, struct reply_info* r, struct region* region) +{ + struct dns_msg* msg = (struct dns_msg*)region_alloc(region, + sizeof(struct dns_msg)); + size_t i; + if(!msg) + return NULL; + memcpy(&msg->qinfo, &e->key, sizeof(struct query_info)); + msg->qinfo.qname = region_alloc_init(region, e->key.qname, + e->key.qnamesize); + if(!msg->qinfo.qname) + return NULL; + /* allocate replyinfo struct and rrset key array separately */ + msg->rep = (struct reply_info*)region_alloc(region, + sizeof(struct reply_info) - sizeof(struct rrset_ref)); + if(!msg->rep) + return NULL; + memcpy(msg->rep, r, + sizeof(struct reply_info) - sizeof(struct rrset_ref)); + msg->rep->rrsets = (struct ub_packed_rrset_key**)region_alloc(region, + msg->rep->rrset_count * sizeof(struct ub_packed_rrset_key*)); + if(!msg->rep->rrsets) + return NULL; + /* try to lock all of the rrsets we need */ + for(i=0; irep->rrset_count; i++) { + msg->rep->rrsets[i] = copy_rrset(r->rrsets[i], region); + if(!msg->rep->rrsets[i]) + return NULL; + } + return msg; +} + +/** allocate dns_msg from CNAME record */ +static struct dns_msg* +cnamemsg(uint8_t* qname, size_t qnamelen, struct ub_packed_rrset_key* rrset, + struct packed_rrset_data* d, struct region* region) +{ + struct dns_msg* msg = (struct dns_msg*)region_alloc(region, + sizeof(struct dns_msg)); + if(!msg) + return NULL; + msg->qinfo.qnamesize = rrset->rk.dname_len; + msg->qinfo.qname = region_alloc_init(region, rrset->rk.dname, + rrset->rk.dname_len); + if(!msg->qinfo.qname) + return NULL; + msg->qinfo.has_cd = (rrset->rk.flags&PACKED_RRSET_CD)?1:0; + msg->qinfo.qtype = LDNS_RR_TYPE_CNAME; + msg->qinfo.qclass = ntohs(rrset->rk.rrset_class); + /* TODO create reply info with the CNAME */ + return NULL; +} + +struct dns_msg* +dns_cache_lookup(struct module_env* env, + uint8_t* qname, size_t qnamelen, uint16_t qtype, uint16_t qclass, + int has_cd, struct region* region) +{ + struct lruhash_entry* e; + struct query_info k; + hashvalue_t h; + uint32_t now = (uint32_t)time(NULL); + struct ub_packed_rrset_key* rrset; + + /* lookup first, this has both NXdomains and ANSWER responses */ + k.qname = qname; + k.qnamesize = qnamelen; + k.qtype = qtype; + k.qclass = qclass; + k.has_cd = has_cd; + h = query_info_hash(&k); + e = slabhash_lookup(env->msg_cache, h, &k, 0); + if(e) { + /* check ttl */ + struct msgreply_entry* key = (struct msgreply_entry*)e->key; + struct reply_info* data = (struct reply_info*)e->data; + if(now <= data->ttl) { + struct dns_msg* msg = tomsg(key, data, region); + lock_rw_unlock(&e->lock); + return msg; + } + lock_rw_unlock(&e->lock); + } + + /* see if we have a CNAME for this domain */ + rrset = rrset_cache_lookup(env->rrset_cache, qname, qnamelen, + LDNS_RR_TYPE_CNAME, qclass, + (uint32_t)(has_cd?PACKED_RRSET_CD:0), now, 0); + if(rrset) { + struct packed_rrset_data* d = (struct packed_rrset_data*) + rrset->entry.data; + if(now <= d->ttl) { + /* construct CNAME response */ + struct dns_msg* msg = cnamemsg(qname, qnamelen, rrset, + d, region); + lock_rw_unlock(&rrset->entry.lock); + return msg; + } + lock_rw_unlock(&rrset->entry.lock); + } + + /* construct DS, DNSKEY messages from rrset cache. TODO */ + + return NULL; +} diff --git a/services/cache/dns.h b/services/cache/dns.h index 4da517071..447d1e275 100644 --- a/services/cache/dns.h +++ b/services/cache/dns.h @@ -42,12 +42,23 @@ #ifndef SERVICES_CACHE_DNS_H #define SERVICES_CACHE_DNS_H #include "util/storage/lruhash.h" +#include "util/data/msgreply.h" struct module_env; struct query_info; struct reply_info; struct region; struct delegpt; +/** + * Region allocated message reply + */ +struct dns_msg { + /** query info */ + struct query_info qinfo; + /** reply info - ptr to packed repinfo structure */ + struct reply_info *rep; +}; + /** * Store message in the cache. Stores in message cache and rrset cache. * Both qinfo and rep should be malloced and are put in the cache. @@ -76,7 +87,22 @@ struct delegpt* dns_cache_find_delegation(struct module_env* env, uint8_t* qname, size_t qnamelen, uint16_t qclass, struct region* region); -/** Find cached message */ +/** + * Find cached message + * @param env: module environment with the DNS cache. + * @param qname: query name. + * @param qnamelen: length of qname. + * @param qtype: query type. + * @param qclass: query class. + * @param has_cd: if true, CD flag is turned on for lookup. + * @param region: where to allocate result. + * @return new response message (alloced in region, rrsets do not have IDs). + * or NULL on error or if not found in cache. + */ +struct dns_msg* dns_cache_lookup(struct module_env* env, + uint8_t* qname, size_t qnamelen, uint16_t qtype, uint16_t qclass, + int has_cd, struct region* region); + /** Find covering DNAME */ #endif /* SERVICES_CACHE_DNS_H */ diff --git a/util/module.c b/util/module.c index f14ca8a5b..37d981512 100644 --- a/util/module.c +++ b/util/module.c @@ -87,3 +87,14 @@ module_subreq_remove(struct module_qstate* sub) p = p->subquery_next; } } + +int +module_subreq_depth(struct module_qstate* sub) +{ + int d = 0; + while(sub->parent) { + d++; + sub = sub->parent; + } + return d; +} diff --git a/util/module.h b/util/module.h index 288606e5c..51806019e 100644 --- a/util/module.h +++ b/util/module.h @@ -275,4 +275,11 @@ const char* strmodulevent(enum module_ev e); */ void module_subreq_remove(struct module_qstate* sub); +/** + * Calculate depth of subrequest + * @param sub: the subrequest. parent point is used. + * @return: depth > 0 for subrequests. + */ +int module_subreq_depth(struct module_qstate* sub); + #endif /* UTIL_MODULE_H */ diff --git a/util/net_help.c b/util/net_help.c index 79b676e27..8f22c5d2b 100644 --- a/util/net_help.c +++ b/util/net_help.c @@ -40,6 +40,7 @@ #include "config.h" #include "util/net_help.h" #include "util/log.h" +#include "util/data/dname.h" #include /** returns true is string addr is an ip6 specced address. */ @@ -176,3 +177,15 @@ ipstrtoaddr(const char* ip, int port, struct sockaddr_storage* addr, } return 1; } + +void +log_nametypeclass(const char* str, uint8_t* name, uint16_t type, + uint16_t dclass) +{ + char buf[LDNS_MAX_DOMAINLEN+1]; + dname_str(name, buf); + log_info("%s <%s %s %s>", str, buf, + ldns_rr_descript(type)?ldns_rr_descript(type)->_name: "??", + ldns_lookup_by_id(ldns_rr_classes, (int)dclass)? + ldns_lookup_by_id(ldns_rr_classes, (int)dclass)->name:"??"); +} diff --git a/util/net_help.h b/util/net_help.h index 85ac3b282..0614989eb 100644 --- a/util/net_help.h +++ b/util/net_help.h @@ -134,4 +134,14 @@ void log_addr(const char* str, struct sockaddr_storage* addr, int ipstrtoaddr(const char* ip, int port, struct sockaddr_storage* addr, socklen_t* addrlen); +/** + * Print string with neat domain name, type and class. + * @param str: string of message. + * @param name: domain name uncompressed wireformat. + * @param type: host format RR type. + * @param dclass: host format RR class. + */ +void log_nametypeclass(const char* str, uint8_t* name, uint16_t type, + uint16_t dclass); + #endif /* NET_HELP_H */ -- 2.47.2