From e08155e86eab7d11b107848426bb68357830dd9c Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Mon, 4 Jun 2007 09:57:02 +0000 Subject: [PATCH] Random nameserver selection. git-svn-id: file:///svn/unbound/trunk@361 be551aaa-1e26-0410-a405-d3ace91eadb9 --- daemon/worker.c | 1 + doc/Changelog | 3 ++ iterator/iter_utils.c | 102 +++++++++++++++++++++++++++++++----------- util/module.h | 9 ++-- 4 files changed, 84 insertions(+), 31 deletions(-) diff --git a/daemon/worker.c b/daemon/worker.c index f4f493bcd..4af4e7c6b 100644 --- a/daemon/worker.c +++ b/daemon/worker.c @@ -763,6 +763,7 @@ worker_init(struct worker* worker, struct config_file *cfg, worker->env = *worker->daemon->env; worker->env.worker = worker; worker->env.alloc = &worker->alloc; + worker->env.rnd = worker->rndstate; return 1; } diff --git a/doc/Changelog b/doc/Changelog index 697b233d7..25b54b9df 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -1,3 +1,6 @@ +4 June 2007: Wouter + - random selection of equally preferred nameserver targets. + 1 June 2007: Wouter - normalize incoming messages. Like unbound-java, with CNAME chain checked, DNAME checked, CNAME's synthesized, glue checked. diff --git a/iterator/iter_utils.c b/iterator/iter_utils.c index 13cbe9fef..8a3d301ec 100644 --- a/iterator/iter_utils.c +++ b/iterator/iter_utils.c @@ -53,7 +53,8 @@ #include "util/config_file.h" #include "util/region-allocator.h" #include "util/data/msgparse.h" - +#include "util/random.h" + int iter_apply_cfg(struct iter_env* iter_env, struct config_file* cfg) { @@ -97,7 +98,7 @@ iter_apply_cfg(struct iter_env* iter_env, struct config_file* cfg) /** filter out unsuitable targets, return rtt or -1 */ static int iter_filter_unsuitable(struct iter_env* iter_env, struct module_env* env, - struct delegpt_addr* a, uint8_t* name, size_t namelen, time_t now) + uint8_t* name, size_t namelen, time_t now, struct delegpt_addr* a) { int rtt; int lame; @@ -116,43 +117,90 @@ iter_filter_unsuitable(struct iter_env* iter_env, struct module_env* env, return UNKNOWN_SERVER_NICENESS; } -struct delegpt_addr* iter_server_selection(struct iter_env* iter_env, - struct module_env* env, struct delegpt* dp, - uint8_t* name, size_t namelen) +/** filter the addres list, putting best targets at front, + * returns number of best targets (or 0, no suitable targets) */ +static int +iter_filter_order(struct iter_env* iter_env, struct module_env* env, + uint8_t* name, size_t namelen, time_t now, struct delegpt* dp) { - int got_one = 0, got_rtt = 0; - struct delegpt_addr* got = NULL, *got_prev = NULL, *a, *prev = NULL; - time_t now = time(NULL); + int got_num = 0, got_rtt = 0, thisrtt, swap_to_front; + struct delegpt_addr* a, *n, *prev=NULL; - for(a = dp->result_list; a; a = a->next_result) { + a = dp->result_list; + while(a) { /* filter out unsuitable targets */ - int thisrtt = iter_filter_unsuitable(iter_env, env, a, name, - namelen, now); + thisrtt = iter_filter_unsuitable(iter_env, env, name, namelen, + now, a); if(thisrtt == -1) { prev = a; + a = a->next_result; continue; } - if(!got_one) { + /* classify the server address and determine what to do */ + swap_to_front = 0; + if(got_num == 0) { got_rtt = thisrtt; - got = a; - got_prev = prev; - got_one = 1; + got_num = 1; + swap_to_front = 1; + } else if(thisrtt == got_rtt) { + got_num++; + swap_to_front = 1; + } else if(thisrtt < got_rtt) { + got_rtt = thisrtt; + got_num = 1; /* start back at count of 1 */ + swap_to_front = 1; + } + /* swap to front if necessary, or move to next result */ + if(swap_to_front && prev) { + n = a->next_result; + prev->next_result = n; + a->next_result = dp->result_list; + dp->result_list = a; + a = n; } else { - if(thisrtt < got_rtt) { - got_rtt = thisrtt; - got = a; - got_prev = prev; - } + prev = a; + a = a->next_result; } - prev = a; } - if(got) { - /* remove it from list */ - if(got_prev) - got_prev->next_result = got->next_result; - else dp->result_list = got->next_result; + return got_num; +} + +struct delegpt_addr* +iter_server_selection(struct iter_env* iter_env, + struct module_env* env, struct delegpt* dp, + uint8_t* name, size_t namelen) +{ + time_t now = time(NULL); + int sel; + struct delegpt_addr* a, *prev; + int num = iter_filter_order(iter_env, env, name, namelen, now, dp); + + if(num == 0) + return NULL; + if(num == 1) { + a = dp->result_list; + dp->result_list = a->next_result; + return a; } - return got; + /* randomly select a target from the list */ + log_assert(num > 1); + /* we do not need secure random numbers here, but + * we do need it to be threadsafe, so we use this */ + sel = ub_random(env->rnd) % num; + a = dp->result_list; + prev = NULL; + while(sel > 0 && a) { + prev = a; + a = a->next_result; + sel--; + } + if(!a) /* robustness */ + return NULL; + /* remove it from list */ + if(prev) + prev->next_result = a->next_result; + else dp->result_list = a->next_result; + return a; } struct dns_msg* diff --git a/util/module.h b/util/module.h index 51806019e..65fcc9a73 100644 --- a/util/module.h +++ b/util/module.h @@ -53,6 +53,7 @@ struct edns_data; struct region; struct worker; struct module_qstate; +struct ub_randstate; /** Maximum number of modules in operation */ #define MAX_MODULE 2 @@ -116,12 +117,12 @@ struct module_env { struct sockaddr_storage* addr, socklen_t addrlen, struct module_qstate* q); - /** create a subquery. operate should then return with wait_subq */ - - /** allocation service */ - struct alloc_cache* alloc; /** internal data for daemon - worker thread. */ struct worker* worker; + /** allocation service */ + struct alloc_cache* alloc; + /** random table to generate random numbers */ + struct ub_randstate* rnd; /** module specific data. indexed by module id. */ void* modinfo[MAX_MODULE]; }; -- 2.47.2