From b9603c178aaac6abbac9fc1bdf5184cb7efdf7f0 Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Thu, 10 Jun 2010 14:10:17 +0000 Subject: [PATCH] - Fix bug where a long loop could be entered, now cycle detection has a loop-counter and maximum search amount. git-svn-id: file:///svn/unbound/trunk@2144 be551aaa-1e26-0410-a405-d3ace91eadb9 --- doc/Changelog | 4 ++++ iterator/iterator.c | 19 ++++++++-------- services/mesh.c | 53 ++++++++++++++++++++++++++++++--------------- services/mesh.h | 13 ++++++++++- 4 files changed, 61 insertions(+), 28 deletions(-) diff --git a/doc/Changelog b/doc/Changelog index 097a476ae..e29eff2f4 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -1,3 +1,7 @@ +10 June 2010: Wouter + - Fix bug where a long loop could be entered, now cycle detection + has a loop-counter and maximum search amount. + 4 June 2010: Wouter - iana portlist updated. - 1.4.5rc1 tag created. diff --git a/iterator/iterator.c b/iterator/iterator.c index 7c3a67608..f28891a9e 100644 --- a/iterator/iterator.c +++ b/iterator/iterator.c @@ -497,13 +497,6 @@ generate_sub_request(uint8_t* qname, size_t qnamelen, uint16_t qtype, if(!v) qflags |= BIT_CD; - fptr_ok(fptr_whitelist_modenv_detect_cycle( - qstate->env->detect_cycle)); - if((*qstate->env->detect_cycle)(qstate, &qinf, qflags, prime)){ - log_query_info(VERB_DETAIL, "cycle detected", &qinf); - return 0; - } - /* attach subquery, lookup existing or make a new one */ fptr_ok(fptr_whitelist_modenv_attach_sub(qstate->env->attach_sub)); if(!(*qstate->env->attach_sub)(qstate, &qinf, qflags, prime, &subq)) { @@ -1344,16 +1337,24 @@ query_for_targets(struct module_qstate* qstate, struct iter_qstate* iq, /* Send the AAAA request. */ if(!generate_target_query(qstate, iq, id, ns->name, ns->namelen, - LDNS_RR_TYPE_AAAA, iq->qchase.qclass)) + LDNS_RR_TYPE_AAAA, iq->qchase.qclass)) { + *num = query_count; + if(query_count > 0) + qstate->ext_state[id] = module_wait_subquery; return 0; + } query_count++; } /* Send the A request. */ if(!ns->got4) { if(!generate_target_query(qstate, iq, id, ns->name, ns->namelen, - LDNS_RR_TYPE_A, iq->qchase.qclass)) + LDNS_RR_TYPE_A, iq->qchase.qclass)) { + *num = query_count; + if(query_count > 0) + qstate->ext_state[id] = module_wait_subquery; return 0; + } query_count++; } diff --git a/services/mesh.c b/services/mesh.c index ff34016f7..a25f221a0 100644 --- a/services/mesh.c +++ b/services/mesh.c @@ -576,6 +576,36 @@ mesh_state_delete(struct module_qstate* qstate) mesh_state_cleanup(mstate); } +/** helper recursive rbtree find routine */ +static int +find_in_subsub(struct mesh_state* m, struct mesh_state* tofind, size_t *c) +{ + struct mesh_state_ref* r; + if((*c)++ > MESH_MAX_SUBSUB) + return 1; + RBTREE_FOR(r, struct mesh_state_ref*, &m->sub_set) { + if(r->s == tofind || find_in_subsub(r->s, tofind, c)) + return 1; + } + return 0; +} + +/** find cycle for already looked up mesh_state */ +static int +mesh_detect_cycle_found(struct module_qstate* qstate, struct mesh_state* dep_m) +{ + struct mesh_state* cyc_m = qstate->mesh_info; + size_t counter = 0; + if(!dep_m) + return 0; + if(dep_m == cyc_m || find_in_subsub(dep_m, cyc_m, &counter)) { + if(counter > MESH_MAX_SUBSUB) + return 2; + return 1; + } + return 0; +} + void mesh_detach_subs(struct module_qstate* qstate) { struct mesh_area* mesh = qstate->env->mesh; @@ -602,6 +632,10 @@ int mesh_attach_sub(struct module_qstate* qstate, struct query_info* qinfo, /* find it, if not, create it */ struct mesh_area* mesh = qstate->env->mesh; struct mesh_state* sub = mesh_area_find(mesh, qinfo, qflags, prime); + if(mesh_detect_cycle_found(qstate, sub)) { + verbose(VERB_ALGO, "attach failed, cycle detected"); + return 0; + } if(!sub) { struct rbnode_t* n; /* create a new one */ @@ -1057,30 +1091,13 @@ mesh_get_mem(struct mesh_area* mesh) return s; } -/** helper recursive rbtree find routine */ -static int -find_in_subsub(struct mesh_state* m, struct mesh_state* tofind) -{ - struct mesh_state_ref* r; - RBTREE_FOR(r, struct mesh_state_ref*, &m->sub_set) { - if(r->s == tofind || find_in_subsub(r->s, tofind)) - return 1; - } - return 0; -} - int mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo, uint16_t flags, int prime) { struct mesh_area* mesh = qstate->env->mesh; - struct mesh_state* cyc_m = qstate->mesh_info; struct mesh_state* dep_m = mesh_area_find(mesh, qinfo, flags, prime); - if(!dep_m) - return 0; - if(dep_m == cyc_m || find_in_subsub(dep_m, cyc_m)) - return 1; - return 0; + return mesh_detect_cycle_found(qstate, dep_m); } void mesh_list_insert(struct mesh_state* m, struct mesh_state** fp, diff --git a/services/mesh.h b/services/mesh.h index 3999d31f8..f1020a17b 100644 --- a/services/mesh.h +++ b/services/mesh.h @@ -65,6 +65,13 @@ struct timehist; */ #define MESH_MAX_ACTIVATION 1000 +/** + * Max number of references-to-references-to-references.. search size. + * Any more is treated like 'too large', and the creation of a new + * dependency is failed (so that no loops can be created). + */ +#define MESH_MAX_SUBSUB 1024 + /** * Mesh of query states */ @@ -326,6 +333,8 @@ void mesh_detach_subs(struct module_qstate* qstate); * Attach subquery. * Creates it if it does not exist already. * Keeps sub and super references correct. + * Performs a cycle detection - for double check - and fails if there is one. + * Also fails if the sub-sub-references become too large. * Updates stat items in mesh_area structure. * Pass if it is priming query or not. * return: @@ -503,13 +512,15 @@ size_t mesh_get_mem(struct mesh_area* mesh); /** * Find cycle; see if the given mesh is in the targets sub, or sub-sub, ... * trees. + * If the sub-sub structure is too large, it returns 'a cycle'=2. * @param qstate: given mesh querystate. * @param qinfo: query info for dependency. * @param flags: query flags of dependency. * @param prime: if dependency is a priming query or not. * @return true if the name,type,class exists and the given qstate mesh exists * as a dependency of that name. Thus if qstate becomes dependent on - * name,type,class then a cycle is created. + * name,type,class then a cycle is created, this is return value 1. + * Too large to search is value 2 (also true). */ int mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo, uint16_t flags, int prime); -- 2.47.2