mesh.c revision 285206
111820Sjulian/* 211820Sjulian * services/mesh.c - deal with mesh of query states and handle events for that. 311820Sjulian * 411820Sjulian * Copyright (c) 2007, NLnet Labs. All rights reserved. 511820Sjulian * 611820Sjulian * This software is open source. 711820Sjulian * 811820Sjulian * Redistribution and use in source and binary forms, with or without 911820Sjulian * modification, are permitted provided that the following conditions 1011820Sjulian * are met: 1111820Sjulian * 1211820Sjulian * Redistributions of source code must retain the above copyright notice, 1311820Sjulian * this list of conditions and the following disclaimer. 1411820Sjulian * 1511820Sjulian * Redistributions in binary form must reproduce the above copyright notice, 1611820Sjulian * this list of conditions and the following disclaimer in the documentation 1711820Sjulian * and/or other materials provided with the distribution. 1811820Sjulian * 1911820Sjulian * Neither the name of the NLNET LABS nor the names of its contributors may 2011820Sjulian * be used to endorse or promote products derived from this software without 2111820Sjulian * specific prior written permission. 2211820Sjulian * 2311820Sjulian * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2411820Sjulian * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2511820Sjulian * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2611820Sjulian * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2711820Sjulian * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2811820Sjulian * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 2911820Sjulian * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 3011820Sjulian * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 3111820Sjulian * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 3211820Sjulian * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 3311820Sjulian * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3411820Sjulian */ 3511820Sjulian 3611820Sjulian/** 3711820Sjulian * \file 3850479Speter * 3911820Sjulian * This file contains functions to assist in dealing with a mesh of 4011820Sjulian * query states. This mesh is supposed to be thread-specific. 4111820Sjulian * It consists of query states (per qname, qtype, qclass) and connections 42122760Strhodes * between query states and the super and subquery states, and replies to 4311820Sjulian * send back to clients. 4411820Sjulian */ 4511820Sjulian#include "config.h" 4611820Sjulian#include "services/mesh.h" 4711820Sjulian#include "services/outbound_list.h" 48122760Strhodes#include "services/cache/dns.h" 4911820Sjulian#include "util/log.h" 5011820Sjulian#include "util/net_help.h" 5111820Sjulian#include "util/module.h" 5211820Sjulian#include "util/regional.h" 5311820Sjulian#include "util/data/msgencode.h" 5411820Sjulian#include "util/timehist.h" 5511820Sjulian#include "util/fptr_wlist.h" 5611820Sjulian#include "util/alloc.h" 5711820Sjulian#include "util/config_file.h" 5811820Sjulian#include "ldns/sbuffer.h" 5911820Sjulian 6011820Sjulian/** subtract timers and the values do not overflow or become negative */ 6111820Sjulianstatic void 6211820Sjuliantimeval_subtract(struct timeval* d, const struct timeval* end, const struct timeval* start) 6311820Sjulian{ 6411820Sjulian#ifndef S_SPLINT_S 6511820Sjulian time_t end_usec = end->tv_usec; 6611820Sjulian d->tv_sec = end->tv_sec - start->tv_sec; 6711820Sjulian if(end_usec < start->tv_usec) { 6811820Sjulian end_usec += 1000000; 6911820Sjulian d->tv_sec--; 7011820Sjulian } 7111820Sjulian d->tv_usec = end_usec - start->tv_usec; 7211820Sjulian#endif 7311820Sjulian} 7411820Sjulian 7511820Sjulian/** add timers and the values do not overflow or become negative */ 7611820Sjulianstatic void 7711820Sjuliantimeval_add(struct timeval* d, const struct timeval* add) 7811820Sjulian{ 7911820Sjulian#ifndef S_SPLINT_S 8011820Sjulian d->tv_sec += add->tv_sec; 8111820Sjulian d->tv_usec += add->tv_usec; 8215248Sjhay if(d->tv_usec > 1000000 ) { 8311820Sjulian d->tv_usec -= 1000000; 8411820Sjulian d->tv_sec++; 8511820Sjulian } 8611820Sjulian#endif 8711820Sjulian} 8827244Sjhay 8927244Sjhay/** divide sum of timers to get average */ 9011820Sjulianstatic void 9111840Sjuliantimeval_divide(struct timeval* avg, const struct timeval* sum, size_t d) 9211820Sjulian{ 9311840Sjulian#ifndef S_SPLINT_S 9411820Sjulian size_t leftover; 9511820Sjulian if(d == 0) { 9611820Sjulian avg->tv_sec = 0; 9715248Sjhay avg->tv_usec = 0; 9827244Sjhay return; 9911820Sjulian } 10011820Sjulian avg->tv_sec = sum->tv_sec / d; 10111820Sjulian avg->tv_usec = sum->tv_usec / d; 10211820Sjulian /* handle fraction from seconds divide */ 10311820Sjulian leftover = sum->tv_sec - avg->tv_sec*d; 10411820Sjulian avg->tv_usec += (leftover*1000000)/d; 10511820Sjulian#endif 10611820Sjulian} 10727244Sjhay 10827244Sjhay/** histogram compare of time values */ 10911820Sjulianstatic int 11011820Sjuliantimeval_smaller(const struct timeval* x, const struct timeval* y) 11111820Sjulian{ 11211820Sjulian#ifndef S_SPLINT_S 11311820Sjulian if(x->tv_sec < y->tv_sec) 11411820Sjulian return 1; 11511820Sjulian else if(x->tv_sec == y->tv_sec) { 11611820Sjulian if(x->tv_usec <= y->tv_usec) 11711820Sjulian return 1; 11811820Sjulian else return 0; 11911820Sjulian } 12011820Sjulian else return 0; 12111820Sjulian#endif 12211820Sjulian} 12311820Sjulian 12411820Sjulianint 12511820Sjulianmesh_state_compare(const void* ap, const void* bp) 12611820Sjulian{ 12711820Sjulian struct mesh_state* a = (struct mesh_state*)ap; 12811820Sjulian struct mesh_state* b = (struct mesh_state*)bp; 12911820Sjulian 13011820Sjulian if(a->s.is_priming && !b->s.is_priming) 13111820Sjulian return -1; 13211820Sjulian if(!a->s.is_priming && b->s.is_priming) 13311820Sjulian return 1; 13411820Sjulian 13511820Sjulian if(a->s.is_valrec && !b->s.is_valrec) 13611820Sjulian return -1; 13711820Sjulian if(!a->s.is_valrec && b->s.is_valrec) 13811820Sjulian return 1; 13911820Sjulian 14011820Sjulian if((a->s.query_flags&BIT_RD) && !(b->s.query_flags&BIT_RD)) 14111820Sjulian return -1; 14211820Sjulian if(!(a->s.query_flags&BIT_RD) && (b->s.query_flags&BIT_RD)) 14311820Sjulian return 1; 14411820Sjulian 14511820Sjulian if((a->s.query_flags&BIT_CD) && !(b->s.query_flags&BIT_CD)) 14611820Sjulian return -1; 14711820Sjulian if(!(a->s.query_flags&BIT_CD) && (b->s.query_flags&BIT_CD)) 14811820Sjulian return 1; 14911820Sjulian 15045988Sjhay return query_info_compare(&a->s.qinfo, &b->s.qinfo); 15145988Sjhay} 15245988Sjhay 15345988Sjhayint 15445988Sjhaymesh_state_ref_compare(const void* ap, const void* bp) 15511820Sjulian{ 15645988Sjhay struct mesh_state_ref* a = (struct mesh_state_ref*)ap; 15711820Sjulian struct mesh_state_ref* b = (struct mesh_state_ref*)bp; 15811820Sjulian return mesh_state_compare(a->s, b->s); 15911820Sjulian} 16011820Sjulian 16111820Sjulianstruct mesh_area* 16211820Sjulianmesh_create(struct module_stack* stack, struct module_env* env) 16311820Sjulian{ 16411820Sjulian struct mesh_area* mesh = calloc(1, sizeof(struct mesh_area)); 16511820Sjulian if(!mesh) { 16611820Sjulian log_err("mesh area alloc: out of memory"); 16711820Sjulian return NULL; 16811820Sjulian } 16911820Sjulian mesh->histogram = timehist_setup(); 17011820Sjulian mesh->qbuf_bak = sldns_buffer_new(env->cfg->msg_buffer_size); 17111820Sjulian if(!mesh->histogram || !mesh->qbuf_bak) { 17211820Sjulian free(mesh); 17311820Sjulian log_err("mesh area alloc: out of memory"); 17411820Sjulian return NULL; 17511820Sjulian } 17611820Sjulian mesh->mods = *stack; 177146076Sjmallett mesh->env = env; 17811820Sjulian rbtree_init(&mesh->run, &mesh_state_compare); 17911820Sjulian rbtree_init(&mesh->all, &mesh_state_compare); 18011820Sjulian mesh->num_reply_addrs = 0; 18111820Sjulian mesh->num_reply_states = 0; 18211820Sjulian mesh->num_detached_states = 0; 18311820Sjulian mesh->num_forever_states = 0; 18411820Sjulian mesh->stats_jostled = 0; 18511820Sjulian mesh->stats_dropped = 0; 18611820Sjulian mesh->max_reply_states = env->cfg->num_queries_per_thread; 18711820Sjulian mesh->max_forever_states = (mesh->max_reply_states+1)/2; 18811820Sjulian#ifndef S_SPLINT_S 18911820Sjulian mesh->jostle_max.tv_sec = (time_t)(env->cfg->jostle_time / 1000); 19011820Sjulian mesh->jostle_max.tv_usec = (time_t)((env->cfg->jostle_time % 1000) 19111820Sjulian *1000); 19211820Sjulian#endif 19311820Sjulian return mesh; 19411820Sjulian} 19511820Sjulian 19611820Sjulian/** help mesh delete delete mesh states */ 19711820Sjulianstatic void 19811820Sjulianmesh_delete_helper(rbnode_t* n) 19911820Sjulian{ 20011820Sjulian struct mesh_state* mstate = (struct mesh_state*)n->key; 20111820Sjulian /* perform a full delete, not only 'cleanup' routine, 20211820Sjulian * because other callbacks expect a clean state in the mesh. 20311820Sjulian * For 're-entrant' calls */ 20411820Sjulian mesh_state_delete(&mstate->s); 20511820Sjulian /* but because these delete the items from the tree, postorder 20611820Sjulian * traversal and rbtree rebalancing do not work together */ 20711820Sjulian} 20811820Sjulian 20911820Sjulianvoid 21011820Sjulianmesh_delete(struct mesh_area* mesh) 21111820Sjulian{ 21211820Sjulian if(!mesh) 21311820Sjulian return; 21411820Sjulian /* free all query states */ 21511820Sjulian while(mesh->all.count) 21627244Sjhay mesh_delete_helper(mesh->all.root); 21711820Sjulian timehist_delete(mesh->histogram); 21811820Sjulian sldns_buffer_free(mesh->qbuf_bak); 21911820Sjulian free(mesh); 22011820Sjulian} 22127244Sjhay 22211820Sjulianvoid 22311820Sjulianmesh_delete_all(struct mesh_area* mesh) 22427244Sjhay{ 22511820Sjulian /* free all query states */ 22611820Sjulian while(mesh->all.count) 22711820Sjulian mesh_delete_helper(mesh->all.root); 22815248Sjhay mesh->stats_dropped += mesh->num_reply_addrs; 22927244Sjhay /* clear mesh area references */ 23027244Sjhay rbtree_init(&mesh->run, &mesh_state_compare); 23127244Sjhay rbtree_init(&mesh->all, &mesh_state_compare); 23227244Sjhay mesh->num_reply_addrs = 0; 23327244Sjhay mesh->num_reply_states = 0; 23427244Sjhay mesh->num_detached_states = 0; 23527244Sjhay mesh->num_forever_states = 0; 23611820Sjulian mesh->forever_first = NULL; 23711820Sjulian mesh->forever_last = NULL; 23811820Sjulian mesh->jostle_first = NULL; 23927244Sjhay mesh->jostle_last = NULL; 24027244Sjhay} 24127244Sjhay 24227244Sjhayint mesh_make_new_space(struct mesh_area* mesh, sldns_buffer* qbuf) 24327244Sjhay{ 24427244Sjhay struct mesh_state* m = mesh->jostle_first; 24511820Sjulian /* free space is available */ 24611820Sjulian if(mesh->num_reply_states < mesh->max_reply_states) 24711820Sjulian return 1; 24811820Sjulian /* try to kick out a jostle-list item */ 24911820Sjulian if(m && m->reply_list && m->list_select == mesh_jostle_list) { 25011820Sjulian /* how old is it? */ 25111820Sjulian struct timeval age; 25211820Sjulian timeval_subtract(&age, mesh->env->now_tv, 25312692Sjulian &m->reply_list->start_time); 25412692Sjulian if(timeval_smaller(&mesh->jostle_max, &age)) { 25512692Sjulian /* its a goner */ 25612692Sjulian log_nametypeclass(VERB_ALGO, "query jostled out to " 25711820Sjulian "make space for a new one", 25811820Sjulian m->s.qinfo.qname, m->s.qinfo.qtype, 25911820Sjulian m->s.qinfo.qclass); 26011820Sjulian /* backup the query */ 26111820Sjulian if(qbuf) sldns_buffer_copy(mesh->qbuf_bak, qbuf); 26211820Sjulian /* notify supers */ 26311820Sjulian if(m->super_set.count > 0) { 26427244Sjhay verbose(VERB_ALGO, "notify supers of failure"); 26527244Sjhay m->s.return_msg = NULL; 26627244Sjhay m->s.return_rcode = LDNS_RCODE_SERVFAIL; 26727244Sjhay mesh_walk_supers(mesh, m); 26827244Sjhay } 26927244Sjhay mesh->stats_jostled ++; 27011820Sjulian mesh_state_delete(&m->s); 27111820Sjulian /* restore the query - note that the qinfo ptr to 27211820Sjulian * the querybuffer is then correct again. */ 27311820Sjulian if(qbuf) sldns_buffer_copy(qbuf, mesh->qbuf_bak); 27411820Sjulian return 1; 27511820Sjulian } 27611820Sjulian } 27711820Sjulian /* no space for new item */ 27811820Sjulian return 0; 279162492Skan} 280162492Skan 28111840Sjulianvoid mesh_new_client(struct mesh_area* mesh, struct query_info* qinfo, 28211820Sjulian uint16_t qflags, struct edns_data* edns, struct comm_reply* rep, 28311820Sjulian uint16_t qid) 28411820Sjulian{ 28511820Sjulian struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 28611820Sjulian int was_detached = 0; 28711820Sjulian int was_noreply = 0; 28811820Sjulian int added = 0; 28911820Sjulian /* does this create a new reply state? */ 29011820Sjulian if(!s || s->list_select == mesh_no_list) { 29111840Sjulian if(!mesh_make_new_space(mesh, rep->c->buffer)) { 29211840Sjulian verbose(VERB_ALGO, "Too many queries. dropping " 29311820Sjulian "incoming query."); 29411820Sjulian comm_point_drop_reply(rep); 29511820Sjulian mesh->stats_dropped ++; 29611840Sjulian return; 29711840Sjulian } 29811820Sjulian /* for this new reply state, the reply address is free, 29911820Sjulian * so the limit of reply addresses does not stop reply states*/ 30011820Sjulian } else { 30111840Sjulian /* protect our memory usage from storing reply addresses */ 30211840Sjulian if(mesh->num_reply_addrs > mesh->max_reply_states*16) { 30311820Sjulian verbose(VERB_ALGO, "Too many requests queued. " 30411820Sjulian "dropping incoming query."); 30511820Sjulian mesh->stats_dropped++; 30611840Sjulian comm_point_drop_reply(rep); 30711820Sjulian return; 30811820Sjulian } 30911820Sjulian } 31011820Sjulian /* see if it already exists, if not, create one */ 31111820Sjulian if(!s) { 31211820Sjulian#ifdef UNBOUND_DEBUG 31311820Sjulian struct rbnode_t* n; 31411820Sjulian#endif 31511820Sjulian s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 31611820Sjulian if(!s) { 31711820Sjulian log_err("mesh_state_create: out of memory; SERVFAIL"); 31811820Sjulian error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL, 31911820Sjulian qinfo, qid, qflags, edns); 32011820Sjulian comm_point_send_reply(rep); 32111820Sjulian return; 32211820Sjulian } 32311820Sjulian#ifdef UNBOUND_DEBUG 32411820Sjulian n = 32511820Sjulian#else 32611820Sjulian (void) 32711820Sjulian#endif 32811820Sjulian rbtree_insert(&mesh->all, &s->node); 32911820Sjulian log_assert(n != NULL); 33011820Sjulian /* set detached (it is now) */ 33111820Sjulian mesh->num_detached_states++; 33211820Sjulian added = 1; 33311820Sjulian } 33411820Sjulian if(!s->reply_list && !s->cb_list && s->super_set.count == 0) 33511820Sjulian was_detached = 1; 33611820Sjulian if(!s->reply_list && !s->cb_list) 33711820Sjulian was_noreply = 1; 33811820Sjulian /* add reply to s */ 33911820Sjulian if(!mesh_state_add_reply(s, edns, rep, qid, qflags, qinfo->qname)) { 34011820Sjulian log_err("mesh_new_client: out of memory; SERVFAIL"); 34111820Sjulian error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL, 34211840Sjulian qinfo, qid, qflags, edns); 34311820Sjulian comm_point_send_reply(rep); 34411820Sjulian if(added) 34511820Sjulian mesh_state_delete(&s->s); 34611820Sjulian return; 34711820Sjulian } 34811840Sjulian /* update statistics */ 34911820Sjulian if(was_detached) { 35027244Sjhay log_assert(mesh->num_detached_states > 0); 35111840Sjulian mesh->num_detached_states--; 35227244Sjhay } 35327244Sjhay if(was_noreply) { 35427244Sjhay mesh->num_reply_states ++; 35511820Sjulian } 35611820Sjulian mesh->num_reply_addrs++; 35711820Sjulian if(s->list_select == mesh_no_list) { 35811820Sjulian /* move to either the forever or the jostle_list */ 35911820Sjulian if(mesh->num_forever_states < mesh->max_forever_states) { 36011820Sjulian mesh->num_forever_states ++; 36111820Sjulian mesh_list_insert(s, &mesh->forever_first, 36211820Sjulian &mesh->forever_last); 36311820Sjulian s->list_select = mesh_forever_list; 36411820Sjulian } else { 36511820Sjulian mesh_list_insert(s, &mesh->jostle_first, 36611820Sjulian &mesh->jostle_last); 36711820Sjulian s->list_select = mesh_jostle_list; 36811820Sjulian } 36911820Sjulian } 37011820Sjulian if(added) 37111820Sjulian mesh_run(mesh, s, module_event_new, NULL); 37211820Sjulian} 37311820Sjulian 37411820Sjulianint 37511820Sjulianmesh_new_callback(struct mesh_area* mesh, struct query_info* qinfo, 37611820Sjulian uint16_t qflags, struct edns_data* edns, sldns_buffer* buf, 37711820Sjulian uint16_t qid, mesh_cb_func_t cb, void* cb_arg) 37811820Sjulian{ 37911820Sjulian struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 38015248Sjhay int was_detached = 0; 38115248Sjhay int was_noreply = 0; 38227244Sjhay int added = 0; 38327244Sjhay /* there are no limits on the number of callbacks */ 38427244Sjhay 38527244Sjhay /* see if it already exists, if not, create one */ 38627244Sjhay if(!s) { 38727244Sjhay#ifdef UNBOUND_DEBUG 38815248Sjhay struct rbnode_t* n; 38915248Sjhay#endif 39015248Sjhay s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 39115248Sjhay if(!s) { 39250306Sjhay return 0; 39315248Sjhay } 39415248Sjhay#ifdef UNBOUND_DEBUG 39515248Sjhay n = 39615248Sjhay#else 39715248Sjhay (void) 39815248Sjhay#endif 39915248Sjhay rbtree_insert(&mesh->all, &s->node); 40015248Sjhay log_assert(n != NULL); 40115248Sjhay /* set detached (it is now) */ 402 mesh->num_detached_states++; 403 added = 1; 404 } 405 if(!s->reply_list && !s->cb_list && s->super_set.count == 0) 406 was_detached = 1; 407 if(!s->reply_list && !s->cb_list) 408 was_noreply = 1; 409 /* add reply to s */ 410 if(!mesh_state_add_cb(s, edns, buf, cb, cb_arg, qid, qflags)) { 411 if(added) 412 mesh_state_delete(&s->s); 413 return 0; 414 } 415 /* update statistics */ 416 if(was_detached) { 417 log_assert(mesh->num_detached_states > 0); 418 mesh->num_detached_states--; 419 } 420 if(was_noreply) { 421 mesh->num_reply_states ++; 422 } 423 mesh->num_reply_addrs++; 424 if(added) 425 mesh_run(mesh, s, module_event_new, NULL); 426 return 1; 427} 428 429void mesh_new_prefetch(struct mesh_area* mesh, struct query_info* qinfo, 430 uint16_t qflags, time_t leeway) 431{ 432 struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 433#ifdef UNBOUND_DEBUG 434 struct rbnode_t* n; 435#endif 436 /* already exists, and for a different purpose perhaps. 437 * if mesh_no_list, keep it that way. */ 438 if(s) { 439 /* make it ignore the cache from now on */ 440 if(!s->s.blacklist) 441 sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region); 442 if(s->s.prefetch_leeway < leeway) 443 s->s.prefetch_leeway = leeway; 444 return; 445 } 446 if(!mesh_make_new_space(mesh, NULL)) { 447 verbose(VERB_ALGO, "Too many queries. dropped prefetch."); 448 mesh->stats_dropped ++; 449 return; 450 } 451 s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0); 452 if(!s) { 453 log_err("prefetch mesh_state_create: out of memory"); 454 return; 455 } 456#ifdef UNBOUND_DEBUG 457 n = 458#else 459 (void) 460#endif 461 rbtree_insert(&mesh->all, &s->node); 462 log_assert(n != NULL); 463 /* set detached (it is now) */ 464 mesh->num_detached_states++; 465 /* make it ignore the cache */ 466 sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region); 467 s->s.prefetch_leeway = leeway; 468 469 if(s->list_select == mesh_no_list) { 470 /* move to either the forever or the jostle_list */ 471 if(mesh->num_forever_states < mesh->max_forever_states) { 472 mesh->num_forever_states ++; 473 mesh_list_insert(s, &mesh->forever_first, 474 &mesh->forever_last); 475 s->list_select = mesh_forever_list; 476 } else { 477 mesh_list_insert(s, &mesh->jostle_first, 478 &mesh->jostle_last); 479 s->list_select = mesh_jostle_list; 480 } 481 } 482 mesh_run(mesh, s, module_event_new, NULL); 483} 484 485void mesh_report_reply(struct mesh_area* mesh, struct outbound_entry* e, 486 struct comm_reply* reply, int what) 487{ 488 enum module_ev event = module_event_reply; 489 e->qstate->reply = reply; 490 if(what != NETEVENT_NOERROR) { 491 event = module_event_noreply; 492 if(what == NETEVENT_CAPSFAIL) 493 event = module_event_capsfail; 494 } 495 mesh_run(mesh, e->qstate->mesh_info, event, e); 496} 497 498struct mesh_state* 499mesh_state_create(struct module_env* env, struct query_info* qinfo, 500 uint16_t qflags, int prime, int valrec) 501{ 502 struct regional* region = alloc_reg_obtain(env->alloc); 503 struct mesh_state* mstate; 504 int i; 505 if(!region) 506 return NULL; 507 mstate = (struct mesh_state*)regional_alloc(region, 508 sizeof(struct mesh_state)); 509 if(!mstate) { 510 alloc_reg_release(env->alloc, region); 511 return NULL; 512 } 513 memset(mstate, 0, sizeof(*mstate)); 514 mstate->node = *RBTREE_NULL; 515 mstate->run_node = *RBTREE_NULL; 516 mstate->node.key = mstate; 517 mstate->run_node.key = mstate; 518 mstate->reply_list = NULL; 519 mstate->list_select = mesh_no_list; 520 mstate->replies_sent = 0; 521 rbtree_init(&mstate->super_set, &mesh_state_ref_compare); 522 rbtree_init(&mstate->sub_set, &mesh_state_ref_compare); 523 mstate->num_activated = 0; 524 /* init module qstate */ 525 mstate->s.qinfo.qtype = qinfo->qtype; 526 mstate->s.qinfo.qclass = qinfo->qclass; 527 mstate->s.qinfo.qname_len = qinfo->qname_len; 528 mstate->s.qinfo.qname = regional_alloc_init(region, qinfo->qname, 529 qinfo->qname_len); 530 if(!mstate->s.qinfo.qname) { 531 alloc_reg_release(env->alloc, region); 532 return NULL; 533 } 534 /* remove all weird bits from qflags */ 535 mstate->s.query_flags = (qflags & (BIT_RD|BIT_CD)); 536 mstate->s.is_priming = prime; 537 mstate->s.is_valrec = valrec; 538 mstate->s.reply = NULL; 539 mstate->s.region = region; 540 mstate->s.curmod = 0; 541 mstate->s.return_msg = 0; 542 mstate->s.return_rcode = LDNS_RCODE_NOERROR; 543 mstate->s.env = env; 544 mstate->s.mesh_info = mstate; 545 mstate->s.prefetch_leeway = 0; 546 /* init modules */ 547 for(i=0; i<env->mesh->mods.num; i++) { 548 mstate->s.minfo[i] = NULL; 549 mstate->s.ext_state[i] = module_state_initial; 550 } 551 return mstate; 552} 553 554void 555mesh_state_cleanup(struct mesh_state* mstate) 556{ 557 struct mesh_area* mesh; 558 int i; 559 if(!mstate) 560 return; 561 mesh = mstate->s.env->mesh; 562 /* drop unsent replies */ 563 if(!mstate->replies_sent) { 564 struct mesh_reply* rep; 565 struct mesh_cb* cb; 566 for(rep=mstate->reply_list; rep; rep=rep->next) { 567 comm_point_drop_reply(&rep->query_reply); 568 mesh->num_reply_addrs--; 569 } 570 for(cb=mstate->cb_list; cb; cb=cb->next) { 571 fptr_ok(fptr_whitelist_mesh_cb(cb->cb)); 572 (*cb->cb)(cb->cb_arg, LDNS_RCODE_SERVFAIL, NULL, 573 sec_status_unchecked, NULL); 574 mesh->num_reply_addrs--; 575 } 576 } 577 578 /* de-init modules */ 579 for(i=0; i<mesh->mods.num; i++) { 580 fptr_ok(fptr_whitelist_mod_clear(mesh->mods.mod[i]->clear)); 581 (*mesh->mods.mod[i]->clear)(&mstate->s, i); 582 mstate->s.minfo[i] = NULL; 583 mstate->s.ext_state[i] = module_finished; 584 } 585 alloc_reg_release(mstate->s.env->alloc, mstate->s.region); 586} 587 588void 589mesh_state_delete(struct module_qstate* qstate) 590{ 591 struct mesh_area* mesh; 592 struct mesh_state_ref* super, ref; 593 struct mesh_state* mstate; 594 if(!qstate) 595 return; 596 mstate = qstate->mesh_info; 597 mesh = mstate->s.env->mesh; 598 mesh_detach_subs(&mstate->s); 599 if(mstate->list_select == mesh_forever_list) { 600 mesh->num_forever_states --; 601 mesh_list_remove(mstate, &mesh->forever_first, 602 &mesh->forever_last); 603 } else if(mstate->list_select == mesh_jostle_list) { 604 mesh_list_remove(mstate, &mesh->jostle_first, 605 &mesh->jostle_last); 606 } 607 if(!mstate->reply_list && !mstate->cb_list 608 && mstate->super_set.count == 0) { 609 log_assert(mesh->num_detached_states > 0); 610 mesh->num_detached_states--; 611 } 612 if(mstate->reply_list || mstate->cb_list) { 613 log_assert(mesh->num_reply_states > 0); 614 mesh->num_reply_states--; 615 } 616 ref.node.key = &ref; 617 ref.s = mstate; 618 RBTREE_FOR(super, struct mesh_state_ref*, &mstate->super_set) { 619 (void)rbtree_delete(&super->s->sub_set, &ref); 620 } 621 (void)rbtree_delete(&mesh->run, mstate); 622 (void)rbtree_delete(&mesh->all, mstate); 623 mesh_state_cleanup(mstate); 624} 625 626/** helper recursive rbtree find routine */ 627static int 628find_in_subsub(struct mesh_state* m, struct mesh_state* tofind, size_t *c) 629{ 630 struct mesh_state_ref* r; 631 if((*c)++ > MESH_MAX_SUBSUB) 632 return 1; 633 RBTREE_FOR(r, struct mesh_state_ref*, &m->sub_set) { 634 if(r->s == tofind || find_in_subsub(r->s, tofind, c)) 635 return 1; 636 } 637 return 0; 638} 639 640/** find cycle for already looked up mesh_state */ 641static int 642mesh_detect_cycle_found(struct module_qstate* qstate, struct mesh_state* dep_m) 643{ 644 struct mesh_state* cyc_m = qstate->mesh_info; 645 size_t counter = 0; 646 if(!dep_m) 647 return 0; 648 if(dep_m == cyc_m || find_in_subsub(dep_m, cyc_m, &counter)) { 649 if(counter > MESH_MAX_SUBSUB) 650 return 2; 651 return 1; 652 } 653 return 0; 654} 655 656void mesh_detach_subs(struct module_qstate* qstate) 657{ 658 struct mesh_area* mesh = qstate->env->mesh; 659 struct mesh_state_ref* ref, lookup; 660#ifdef UNBOUND_DEBUG 661 struct rbnode_t* n; 662#endif 663 lookup.node.key = &lookup; 664 lookup.s = qstate->mesh_info; 665 RBTREE_FOR(ref, struct mesh_state_ref*, &qstate->mesh_info->sub_set) { 666#ifdef UNBOUND_DEBUG 667 n = 668#else 669 (void) 670#endif 671 rbtree_delete(&ref->s->super_set, &lookup); 672 log_assert(n != NULL); /* must have been present */ 673 if(!ref->s->reply_list && !ref->s->cb_list 674 && ref->s->super_set.count == 0) { 675 mesh->num_detached_states++; 676 log_assert(mesh->num_detached_states + 677 mesh->num_reply_states <= mesh->all.count); 678 } 679 } 680 rbtree_init(&qstate->mesh_info->sub_set, &mesh_state_ref_compare); 681} 682 683int mesh_attach_sub(struct module_qstate* qstate, struct query_info* qinfo, 684 uint16_t qflags, int prime, int valrec, struct module_qstate** newq) 685{ 686 /* find it, if not, create it */ 687 struct mesh_area* mesh = qstate->env->mesh; 688 struct mesh_state* sub = mesh_area_find(mesh, qinfo, qflags, prime, 689 valrec); 690 int was_detached; 691 if(mesh_detect_cycle_found(qstate, sub)) { 692 verbose(VERB_ALGO, "attach failed, cycle detected"); 693 return 0; 694 } 695 if(!sub) { 696#ifdef UNBOUND_DEBUG 697 struct rbnode_t* n; 698#endif 699 /* create a new one */ 700 sub = mesh_state_create(qstate->env, qinfo, qflags, prime, 701 valrec); 702 if(!sub) { 703 log_err("mesh_attach_sub: out of memory"); 704 return 0; 705 } 706#ifdef UNBOUND_DEBUG 707 n = 708#else 709 (void) 710#endif 711 rbtree_insert(&mesh->all, &sub->node); 712 log_assert(n != NULL); 713 /* set detached (it is now) */ 714 mesh->num_detached_states++; 715 /* set new query state to run */ 716#ifdef UNBOUND_DEBUG 717 n = 718#else 719 (void) 720#endif 721 rbtree_insert(&mesh->run, &sub->run_node); 722 log_assert(n != NULL); 723 *newq = &sub->s; 724 } else 725 *newq = NULL; 726 was_detached = (sub->super_set.count == 0); 727 if(!mesh_state_attachment(qstate->mesh_info, sub)) 728 return 0; 729 /* if it was a duplicate attachment, the count was not zero before */ 730 if(!sub->reply_list && !sub->cb_list && was_detached && 731 sub->super_set.count == 1) { 732 /* it used to be detached, before this one got added */ 733 log_assert(mesh->num_detached_states > 0); 734 mesh->num_detached_states--; 735 } 736 /* *newq will be run when inited after the current module stops */ 737 return 1; 738} 739 740int mesh_state_attachment(struct mesh_state* super, struct mesh_state* sub) 741{ 742#ifdef UNBOUND_DEBUG 743 struct rbnode_t* n; 744#endif 745 struct mesh_state_ref* subref; /* points to sub, inserted in super */ 746 struct mesh_state_ref* superref; /* points to super, inserted in sub */ 747 if( !(subref = regional_alloc(super->s.region, 748 sizeof(struct mesh_state_ref))) || 749 !(superref = regional_alloc(sub->s.region, 750 sizeof(struct mesh_state_ref))) ) { 751 log_err("mesh_state_attachment: out of memory"); 752 return 0; 753 } 754 superref->node.key = superref; 755 superref->s = super; 756 subref->node.key = subref; 757 subref->s = sub; 758 if(!rbtree_insert(&sub->super_set, &superref->node)) { 759 /* this should not happen, iterator and validator do not 760 * attach subqueries that are identical. */ 761 /* already attached, we are done, nothing todo. 762 * since superref and subref already allocated in region, 763 * we cannot free them */ 764 return 1; 765 } 766#ifdef UNBOUND_DEBUG 767 n = 768#else 769 (void) 770#endif 771 rbtree_insert(&super->sub_set, &subref->node); 772 log_assert(n != NULL); /* we checked above if statement, the reverse 773 administration should not fail now, unless they are out of sync */ 774 return 1; 775} 776 777/** 778 * callback results to mesh cb entry 779 * @param m: mesh state to send it for. 780 * @param rcode: if not 0, error code. 781 * @param rep: reply to send (or NULL if rcode is set). 782 * @param r: callback entry 783 */ 784static void 785mesh_do_callback(struct mesh_state* m, int rcode, struct reply_info* rep, 786 struct mesh_cb* r) 787{ 788 int secure; 789 char* reason = NULL; 790 /* bogus messages are not made into servfail, sec_status passed 791 * to the callback function */ 792 if(rep && rep->security == sec_status_secure) 793 secure = 1; 794 else secure = 0; 795 if(!rep && rcode == LDNS_RCODE_NOERROR) 796 rcode = LDNS_RCODE_SERVFAIL; 797 if(!rcode && rep->security == sec_status_bogus) { 798 if(!(reason = errinf_to_str(&m->s))) 799 rcode = LDNS_RCODE_SERVFAIL; 800 } 801 /* send the reply */ 802 if(rcode) { 803 fptr_ok(fptr_whitelist_mesh_cb(r->cb)); 804 (*r->cb)(r->cb_arg, rcode, r->buf, sec_status_unchecked, NULL); 805 } else { 806 size_t udp_size = r->edns.udp_size; 807 sldns_buffer_clear(r->buf); 808 r->edns.edns_version = EDNS_ADVERTISED_VERSION; 809 r->edns.udp_size = EDNS_ADVERTISED_SIZE; 810 r->edns.ext_rcode = 0; 811 r->edns.bits &= EDNS_DO; 812 if(!reply_info_answer_encode(&m->s.qinfo, rep, r->qid, 813 r->qflags, r->buf, 0, 1, 814 m->s.env->scratch, udp_size, &r->edns, 815 (int)(r->edns.bits & EDNS_DO), secure)) 816 { 817 fptr_ok(fptr_whitelist_mesh_cb(r->cb)); 818 (*r->cb)(r->cb_arg, LDNS_RCODE_SERVFAIL, r->buf, 819 sec_status_unchecked, NULL); 820 } else { 821 fptr_ok(fptr_whitelist_mesh_cb(r->cb)); 822 (*r->cb)(r->cb_arg, LDNS_RCODE_NOERROR, r->buf, 823 rep->security, reason); 824 } 825 } 826 free(reason); 827 m->s.env->mesh->num_reply_addrs--; 828} 829 830/** 831 * Send reply to mesh reply entry 832 * @param m: mesh state to send it for. 833 * @param rcode: if not 0, error code. 834 * @param rep: reply to send (or NULL if rcode is set). 835 * @param r: reply entry 836 * @param prev: previous reply, already has its answer encoded in buffer. 837 */ 838static void 839mesh_send_reply(struct mesh_state* m, int rcode, struct reply_info* rep, 840 struct mesh_reply* r, struct mesh_reply* prev) 841{ 842 struct timeval end_time; 843 struct timeval duration; 844 int secure; 845 /* examine security status */ 846 if(m->s.env->need_to_validate && (!(r->qflags&BIT_CD) || 847 m->s.env->cfg->ignore_cd) && rep && 848 rep->security <= sec_status_bogus) { 849 rcode = LDNS_RCODE_SERVFAIL; 850 if(m->s.env->cfg->stat_extended) 851 m->s.env->mesh->ans_bogus++; 852 } 853 if(rep && rep->security == sec_status_secure) 854 secure = 1; 855 else secure = 0; 856 if(!rep && rcode == LDNS_RCODE_NOERROR) 857 rcode = LDNS_RCODE_SERVFAIL; 858 /* send the reply */ 859 if(prev && prev->qflags == r->qflags && 860 prev->edns.edns_present == r->edns.edns_present && 861 prev->edns.bits == r->edns.bits && 862 prev->edns.udp_size == r->edns.udp_size) { 863 /* if the previous reply is identical to this one, fix ID */ 864 if(prev->query_reply.c->buffer != r->query_reply.c->buffer) 865 sldns_buffer_copy(r->query_reply.c->buffer, 866 prev->query_reply.c->buffer); 867 sldns_buffer_write_at(r->query_reply.c->buffer, 0, 868 &r->qid, sizeof(uint16_t)); 869 sldns_buffer_write_at(r->query_reply.c->buffer, 12, 870 r->qname, m->s.qinfo.qname_len); 871 comm_point_send_reply(&r->query_reply); 872 } else if(rcode) { 873 m->s.qinfo.qname = r->qname; 874 error_encode(r->query_reply.c->buffer, rcode, &m->s.qinfo, 875 r->qid, r->qflags, &r->edns); 876 comm_point_send_reply(&r->query_reply); 877 } else { 878 size_t udp_size = r->edns.udp_size; 879 r->edns.edns_version = EDNS_ADVERTISED_VERSION; 880 r->edns.udp_size = EDNS_ADVERTISED_SIZE; 881 r->edns.ext_rcode = 0; 882 r->edns.bits &= EDNS_DO; 883 m->s.qinfo.qname = r->qname; 884 if(!reply_info_answer_encode(&m->s.qinfo, rep, r->qid, 885 r->qflags, r->query_reply.c->buffer, 0, 1, 886 m->s.env->scratch, udp_size, &r->edns, 887 (int)(r->edns.bits & EDNS_DO), secure)) 888 { 889 error_encode(r->query_reply.c->buffer, 890 LDNS_RCODE_SERVFAIL, &m->s.qinfo, r->qid, 891 r->qflags, &r->edns); 892 } 893 comm_point_send_reply(&r->query_reply); 894 } 895 /* account */ 896 m->s.env->mesh->num_reply_addrs--; 897 end_time = *m->s.env->now_tv; 898 timeval_subtract(&duration, &end_time, &r->start_time); 899 verbose(VERB_ALGO, "query took " ARG_LL "d.%6.6d sec", 900 (long long)duration.tv_sec, (int)duration.tv_usec); 901 m->s.env->mesh->replies_sent++; 902 timeval_add(&m->s.env->mesh->replies_sum_wait, &duration); 903 timehist_insert(m->s.env->mesh->histogram, &duration); 904 if(m->s.env->cfg->stat_extended) { 905 uint16_t rc = FLAGS_GET_RCODE(sldns_buffer_read_u16_at(r-> 906 query_reply.c->buffer, 2)); 907 if(secure) m->s.env->mesh->ans_secure++; 908 m->s.env->mesh->ans_rcode[ rc ] ++; 909 if(rc == 0 && LDNS_ANCOUNT(sldns_buffer_begin(r-> 910 query_reply.c->buffer)) == 0) 911 m->s.env->mesh->ans_nodata++; 912 } 913} 914 915void mesh_query_done(struct mesh_state* mstate) 916{ 917 struct mesh_reply* r; 918 struct mesh_reply* prev = NULL; 919 struct mesh_cb* c; 920 struct reply_info* rep = (mstate->s.return_msg? 921 mstate->s.return_msg->rep:NULL); 922 for(r = mstate->reply_list; r; r = r->next) { 923 mesh_send_reply(mstate, mstate->s.return_rcode, rep, r, prev); 924 prev = r; 925 } 926 mstate->replies_sent = 1; 927 for(c = mstate->cb_list; c; c = c->next) { 928 mesh_do_callback(mstate, mstate->s.return_rcode, rep, c); 929 } 930} 931 932void mesh_walk_supers(struct mesh_area* mesh, struct mesh_state* mstate) 933{ 934 struct mesh_state_ref* ref; 935 RBTREE_FOR(ref, struct mesh_state_ref*, &mstate->super_set) 936 { 937 /* make super runnable */ 938 (void)rbtree_insert(&mesh->run, &ref->s->run_node); 939 /* callback the function to inform super of result */ 940 fptr_ok(fptr_whitelist_mod_inform_super( 941 mesh->mods.mod[ref->s->s.curmod]->inform_super)); 942 (*mesh->mods.mod[ref->s->s.curmod]->inform_super)(&mstate->s, 943 ref->s->s.curmod, &ref->s->s); 944 } 945} 946 947struct mesh_state* mesh_area_find(struct mesh_area* mesh, 948 struct query_info* qinfo, uint16_t qflags, int prime, int valrec) 949{ 950 struct mesh_state key; 951 struct mesh_state* result; 952 953 key.node.key = &key; 954 key.s.is_priming = prime; 955 key.s.is_valrec = valrec; 956 key.s.qinfo = *qinfo; 957 key.s.query_flags = qflags; 958 959 result = (struct mesh_state*)rbtree_search(&mesh->all, &key); 960 return result; 961} 962 963int mesh_state_add_cb(struct mesh_state* s, struct edns_data* edns, 964 sldns_buffer* buf, mesh_cb_func_t cb, void* cb_arg, 965 uint16_t qid, uint16_t qflags) 966{ 967 struct mesh_cb* r = regional_alloc(s->s.region, 968 sizeof(struct mesh_cb)); 969 if(!r) 970 return 0; 971 r->buf = buf; 972 log_assert(fptr_whitelist_mesh_cb(cb)); /* early failure ifmissing*/ 973 r->cb = cb; 974 r->cb_arg = cb_arg; 975 r->edns = *edns; 976 r->qid = qid; 977 r->qflags = qflags; 978 r->next = s->cb_list; 979 s->cb_list = r; 980 return 1; 981 982} 983 984int mesh_state_add_reply(struct mesh_state* s, struct edns_data* edns, 985 struct comm_reply* rep, uint16_t qid, uint16_t qflags, uint8_t* qname) 986{ 987 struct mesh_reply* r = regional_alloc(s->s.region, 988 sizeof(struct mesh_reply)); 989 if(!r) 990 return 0; 991 r->query_reply = *rep; 992 r->edns = *edns; 993 r->qid = qid; 994 r->qflags = qflags; 995 r->start_time = *s->s.env->now_tv; 996 r->next = s->reply_list; 997 r->qname = regional_alloc_init(s->s.region, qname, 998 s->s.qinfo.qname_len); 999 if(!r->qname) 1000 return 0; 1001 s->reply_list = r; 1002 return 1; 1003 1004} 1005 1006/** 1007 * Continue processing the mesh state at another module. 1008 * Handles module to modules tranfer of control. 1009 * Handles module finished. 1010 * @param mesh: the mesh area. 1011 * @param mstate: currently active mesh state. 1012 * Deleted if finished, calls _done and _supers to 1013 * send replies to clients and inform other mesh states. 1014 * This in turn may create additional runnable mesh states. 1015 * @param s: state at which the current module exited. 1016 * @param ev: the event sent to the module. 1017 * returned is the event to send to the next module. 1018 * @return true if continue processing at the new module. 1019 * false if not continued processing is needed. 1020 */ 1021static int 1022mesh_continue(struct mesh_area* mesh, struct mesh_state* mstate, 1023 enum module_ext_state s, enum module_ev* ev) 1024{ 1025 mstate->num_activated++; 1026 if(mstate->num_activated > MESH_MAX_ACTIVATION) { 1027 /* module is looping. Stop it. */ 1028 log_err("internal error: looping module stopped"); 1029 log_query_info(VERB_QUERY, "pass error for qstate", 1030 &mstate->s.qinfo); 1031 s = module_error; 1032 } 1033 if(s == module_wait_module || s == module_restart_next) { 1034 /* start next module */ 1035 mstate->s.curmod++; 1036 if(mesh->mods.num == mstate->s.curmod) { 1037 log_err("Cannot pass to next module; at last module"); 1038 log_query_info(VERB_QUERY, "pass error for qstate", 1039 &mstate->s.qinfo); 1040 mstate->s.curmod--; 1041 return mesh_continue(mesh, mstate, module_error, ev); 1042 } 1043 if(s == module_restart_next) { 1044 fptr_ok(fptr_whitelist_mod_clear( 1045 mesh->mods.mod[mstate->s.curmod]->clear)); 1046 (*mesh->mods.mod[mstate->s.curmod]->clear) 1047 (&mstate->s, mstate->s.curmod); 1048 mstate->s.minfo[mstate->s.curmod] = NULL; 1049 } 1050 *ev = module_event_pass; 1051 return 1; 1052 } 1053 if(s == module_error && mstate->s.return_rcode == LDNS_RCODE_NOERROR) { 1054 /* error is bad, handle pass back up below */ 1055 mstate->s.return_rcode = LDNS_RCODE_SERVFAIL; 1056 } 1057 if(s == module_error || s == module_finished) { 1058 if(mstate->s.curmod == 0) { 1059 mesh_query_done(mstate); 1060 mesh_walk_supers(mesh, mstate); 1061 mesh_state_delete(&mstate->s); 1062 return 0; 1063 } 1064 /* pass along the locus of control */ 1065 mstate->s.curmod --; 1066 *ev = module_event_moddone; 1067 return 1; 1068 } 1069 return 0; 1070} 1071 1072void mesh_run(struct mesh_area* mesh, struct mesh_state* mstate, 1073 enum module_ev ev, struct outbound_entry* e) 1074{ 1075 enum module_ext_state s; 1076 verbose(VERB_ALGO, "mesh_run: start"); 1077 while(mstate) { 1078 /* run the module */ 1079 fptr_ok(fptr_whitelist_mod_operate( 1080 mesh->mods.mod[mstate->s.curmod]->operate)); 1081 (*mesh->mods.mod[mstate->s.curmod]->operate) 1082 (&mstate->s, ev, mstate->s.curmod, e); 1083 1084 /* examine results */ 1085 mstate->s.reply = NULL; 1086 regional_free_all(mstate->s.env->scratch); 1087 s = mstate->s.ext_state[mstate->s.curmod]; 1088 verbose(VERB_ALGO, "mesh_run: %s module exit state is %s", 1089 mesh->mods.mod[mstate->s.curmod]->name, strextstate(s)); 1090 e = NULL; 1091 if(mesh_continue(mesh, mstate, s, &ev)) 1092 continue; 1093 1094 /* run more modules */ 1095 ev = module_event_pass; 1096 if(mesh->run.count > 0) { 1097 /* pop random element off the runnable tree */ 1098 mstate = (struct mesh_state*)mesh->run.root->key; 1099 (void)rbtree_delete(&mesh->run, mstate); 1100 } else mstate = NULL; 1101 } 1102 if(verbosity >= VERB_ALGO) { 1103 mesh_stats(mesh, "mesh_run: end"); 1104 mesh_log_list(mesh); 1105 } 1106} 1107 1108void 1109mesh_log_list(struct mesh_area* mesh) 1110{ 1111 char buf[30]; 1112 struct mesh_state* m; 1113 int num = 0; 1114 RBTREE_FOR(m, struct mesh_state*, &mesh->all) { 1115 snprintf(buf, sizeof(buf), "%d%s%s%s%s%s%s mod%d %s%s", 1116 num++, (m->s.is_priming)?"p":"", /* prime */ 1117 (m->s.is_valrec)?"v":"", /* prime */ 1118 (m->s.query_flags&BIT_RD)?"RD":"", 1119 (m->s.query_flags&BIT_CD)?"CD":"", 1120 (m->super_set.count==0)?"d":"", /* detached */ 1121 (m->sub_set.count!=0)?"c":"", /* children */ 1122 m->s.curmod, (m->reply_list)?"rep":"", /*hasreply*/ 1123 (m->cb_list)?"cb":"" /* callbacks */ 1124 ); 1125 log_query_info(VERB_ALGO, buf, &m->s.qinfo); 1126 } 1127} 1128 1129void 1130mesh_stats(struct mesh_area* mesh, const char* str) 1131{ 1132 verbose(VERB_DETAIL, "%s %u recursion states (%u with reply, " 1133 "%u detached), %u waiting replies, %u recursion replies " 1134 "sent, %d replies dropped, %d states jostled out", 1135 str, (unsigned)mesh->all.count, 1136 (unsigned)mesh->num_reply_states, 1137 (unsigned)mesh->num_detached_states, 1138 (unsigned)mesh->num_reply_addrs, 1139 (unsigned)mesh->replies_sent, 1140 (unsigned)mesh->stats_dropped, 1141 (unsigned)mesh->stats_jostled); 1142 if(mesh->replies_sent > 0) { 1143 struct timeval avg; 1144 timeval_divide(&avg, &mesh->replies_sum_wait, 1145 mesh->replies_sent); 1146 log_info("average recursion processing time " 1147 ARG_LL "d.%6.6d sec", 1148 (long long)avg.tv_sec, (int)avg.tv_usec); 1149 log_info("histogram of recursion processing times"); 1150 timehist_log(mesh->histogram, "recursions"); 1151 } 1152} 1153 1154void 1155mesh_stats_clear(struct mesh_area* mesh) 1156{ 1157 if(!mesh) 1158 return; 1159 mesh->replies_sent = 0; 1160 mesh->replies_sum_wait.tv_sec = 0; 1161 mesh->replies_sum_wait.tv_usec = 0; 1162 mesh->stats_jostled = 0; 1163 mesh->stats_dropped = 0; 1164 timehist_clear(mesh->histogram); 1165 mesh->ans_secure = 0; 1166 mesh->ans_bogus = 0; 1167 memset(&mesh->ans_rcode[0], 0, sizeof(size_t)*16); 1168 mesh->ans_nodata = 0; 1169} 1170 1171size_t 1172mesh_get_mem(struct mesh_area* mesh) 1173{ 1174 struct mesh_state* m; 1175 size_t s = sizeof(*mesh) + sizeof(struct timehist) + 1176 sizeof(struct th_buck)*mesh->histogram->num + 1177 sizeof(sldns_buffer) + sldns_buffer_capacity(mesh->qbuf_bak); 1178 RBTREE_FOR(m, struct mesh_state*, &mesh->all) { 1179 /* all, including m itself allocated in qstate region */ 1180 s += regional_get_mem(m->s.region); 1181 } 1182 return s; 1183} 1184 1185int 1186mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo, 1187 uint16_t flags, int prime, int valrec) 1188{ 1189 struct mesh_area* mesh = qstate->env->mesh; 1190 struct mesh_state* dep_m = mesh_area_find(mesh, qinfo, flags, prime, 1191 valrec); 1192 return mesh_detect_cycle_found(qstate, dep_m); 1193} 1194 1195void mesh_list_insert(struct mesh_state* m, struct mesh_state** fp, 1196 struct mesh_state** lp) 1197{ 1198 /* insert as last element */ 1199 m->prev = *lp; 1200 m->next = NULL; 1201 if(*lp) 1202 (*lp)->next = m; 1203 else *fp = m; 1204 *lp = m; 1205} 1206 1207void mesh_list_remove(struct mesh_state* m, struct mesh_state** fp, 1208 struct mesh_state** lp) 1209{ 1210 if(m->next) 1211 m->next->prev = m->prev; 1212 else *lp = m->prev; 1213 if(m->prev) 1214 m->prev->next = m->next; 1215 else *fp = m->next; 1216} 1217