xref: /freebsd/contrib/unbound/services/mesh.c (revision 63d1fd5970ec814904aa0f4580b10a0d302d08b2)
1 /*
2  * services/mesh.c - deal with mesh of query states and handle events for that.
3  *
4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
5  *
6  * This software is open source.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  *
15  * Redistributions in binary form must reproduce the above copyright notice,
16  * this list of conditions and the following disclaimer in the documentation
17  * and/or other materials provided with the distribution.
18  *
19  * Neither the name of the NLNET LABS nor the names of its contributors may
20  * be used to endorse or promote products derived from this software without
21  * specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35 
36 /**
37  * \file
38  *
39  * This file contains functions to assist in dealing with a mesh of
40  * query states. This mesh is supposed to be thread-specific.
41  * It consists of query states (per qname, qtype, qclass) and connections
42  * between query states and the super and subquery states, and replies to
43  * send back to clients.
44  */
45 #include "config.h"
46 #include "services/mesh.h"
47 #include "services/outbound_list.h"
48 #include "services/cache/dns.h"
49 #include "util/log.h"
50 #include "util/net_help.h"
51 #include "util/module.h"
52 #include "util/regional.h"
53 #include "util/data/msgencode.h"
54 #include "util/timehist.h"
55 #include "util/fptr_wlist.h"
56 #include "util/alloc.h"
57 #include "util/config_file.h"
58 #include "sldns/sbuffer.h"
59 
60 /** subtract timers and the values do not overflow or become negative */
61 static void
62 timeval_subtract(struct timeval* d, const struct timeval* end, const struct timeval* start)
63 {
64 #ifndef S_SPLINT_S
65 	time_t end_usec = end->tv_usec;
66 	d->tv_sec = end->tv_sec - start->tv_sec;
67 	if(end_usec < start->tv_usec) {
68 		end_usec += 1000000;
69 		d->tv_sec--;
70 	}
71 	d->tv_usec = end_usec - start->tv_usec;
72 #endif
73 }
74 
75 /** add timers and the values do not overflow or become negative */
76 static void
77 timeval_add(struct timeval* d, const struct timeval* add)
78 {
79 #ifndef S_SPLINT_S
80 	d->tv_sec += add->tv_sec;
81 	d->tv_usec += add->tv_usec;
82 	if(d->tv_usec > 1000000 ) {
83 		d->tv_usec -= 1000000;
84 		d->tv_sec++;
85 	}
86 #endif
87 }
88 
89 /** divide sum of timers to get average */
90 static void
91 timeval_divide(struct timeval* avg, const struct timeval* sum, size_t d)
92 {
93 #ifndef S_SPLINT_S
94 	size_t leftover;
95 	if(d == 0) {
96 		avg->tv_sec = 0;
97 		avg->tv_usec = 0;
98 		return;
99 	}
100 	avg->tv_sec = sum->tv_sec / d;
101 	avg->tv_usec = sum->tv_usec / d;
102 	/* handle fraction from seconds divide */
103 	leftover = sum->tv_sec - avg->tv_sec*d;
104 	avg->tv_usec += (leftover*1000000)/d;
105 #endif
106 }
107 
108 /** histogram compare of time values */
109 static int
110 timeval_smaller(const struct timeval* x, const struct timeval* y)
111 {
112 #ifndef S_SPLINT_S
113 	if(x->tv_sec < y->tv_sec)
114 		return 1;
115 	else if(x->tv_sec == y->tv_sec) {
116 		if(x->tv_usec <= y->tv_usec)
117 			return 1;
118 		else	return 0;
119 	}
120 	else	return 0;
121 #endif
122 }
123 
124 int
125 mesh_state_compare(const void* ap, const void* bp)
126 {
127 	struct mesh_state* a = (struct mesh_state*)ap;
128 	struct mesh_state* b = (struct mesh_state*)bp;
129 
130 	if(a->s.is_priming && !b->s.is_priming)
131 		return -1;
132 	if(!a->s.is_priming && b->s.is_priming)
133 		return 1;
134 
135 	if(a->s.is_valrec && !b->s.is_valrec)
136 		return -1;
137 	if(!a->s.is_valrec && b->s.is_valrec)
138 		return 1;
139 
140 	if((a->s.query_flags&BIT_RD) && !(b->s.query_flags&BIT_RD))
141 		return -1;
142 	if(!(a->s.query_flags&BIT_RD) && (b->s.query_flags&BIT_RD))
143 		return 1;
144 
145 	if((a->s.query_flags&BIT_CD) && !(b->s.query_flags&BIT_CD))
146 		return -1;
147 	if(!(a->s.query_flags&BIT_CD) && (b->s.query_flags&BIT_CD))
148 		return 1;
149 
150 	return query_info_compare(&a->s.qinfo, &b->s.qinfo);
151 }
152 
153 int
154 mesh_state_ref_compare(const void* ap, const void* bp)
155 {
156 	struct mesh_state_ref* a = (struct mesh_state_ref*)ap;
157 	struct mesh_state_ref* b = (struct mesh_state_ref*)bp;
158 	return mesh_state_compare(a->s, b->s);
159 }
160 
161 struct mesh_area*
162 mesh_create(struct module_stack* stack, struct module_env* env)
163 {
164 	struct mesh_area* mesh = calloc(1, sizeof(struct mesh_area));
165 	if(!mesh) {
166 		log_err("mesh area alloc: out of memory");
167 		return NULL;
168 	}
169 	mesh->histogram = timehist_setup();
170 	mesh->qbuf_bak = sldns_buffer_new(env->cfg->msg_buffer_size);
171 	if(!mesh->histogram || !mesh->qbuf_bak) {
172 		free(mesh);
173 		log_err("mesh area alloc: out of memory");
174 		return NULL;
175 	}
176 	mesh->mods = *stack;
177 	mesh->env = env;
178 	rbtree_init(&mesh->run, &mesh_state_compare);
179 	rbtree_init(&mesh->all, &mesh_state_compare);
180 	mesh->num_reply_addrs = 0;
181 	mesh->num_reply_states = 0;
182 	mesh->num_detached_states = 0;
183 	mesh->num_forever_states = 0;
184 	mesh->stats_jostled = 0;
185 	mesh->stats_dropped = 0;
186 	mesh->max_reply_states = env->cfg->num_queries_per_thread;
187 	mesh->max_forever_states = (mesh->max_reply_states+1)/2;
188 #ifndef S_SPLINT_S
189 	mesh->jostle_max.tv_sec = (time_t)(env->cfg->jostle_time / 1000);
190 	mesh->jostle_max.tv_usec = (time_t)((env->cfg->jostle_time % 1000)
191 		*1000);
192 #endif
193 	return mesh;
194 }
195 
196 /** help mesh delete delete mesh states */
197 static void
198 mesh_delete_helper(rbnode_t* n)
199 {
200 	struct mesh_state* mstate = (struct mesh_state*)n->key;
201 	/* perform a full delete, not only 'cleanup' routine,
202 	 * because other callbacks expect a clean state in the mesh.
203 	 * For 're-entrant' calls */
204 	mesh_state_delete(&mstate->s);
205 	/* but because these delete the items from the tree, postorder
206 	 * traversal and rbtree rebalancing do not work together */
207 }
208 
209 void
210 mesh_delete(struct mesh_area* mesh)
211 {
212 	if(!mesh)
213 		return;
214 	/* free all query states */
215 	while(mesh->all.count)
216 		mesh_delete_helper(mesh->all.root);
217 	timehist_delete(mesh->histogram);
218 	sldns_buffer_free(mesh->qbuf_bak);
219 	free(mesh);
220 }
221 
222 void
223 mesh_delete_all(struct mesh_area* mesh)
224 {
225 	/* free all query states */
226 	while(mesh->all.count)
227 		mesh_delete_helper(mesh->all.root);
228 	mesh->stats_dropped += mesh->num_reply_addrs;
229 	/* clear mesh area references */
230 	rbtree_init(&mesh->run, &mesh_state_compare);
231 	rbtree_init(&mesh->all, &mesh_state_compare);
232 	mesh->num_reply_addrs = 0;
233 	mesh->num_reply_states = 0;
234 	mesh->num_detached_states = 0;
235 	mesh->num_forever_states = 0;
236 	mesh->forever_first = NULL;
237 	mesh->forever_last = NULL;
238 	mesh->jostle_first = NULL;
239 	mesh->jostle_last = NULL;
240 }
241 
242 int mesh_make_new_space(struct mesh_area* mesh, sldns_buffer* qbuf)
243 {
244 	struct mesh_state* m = mesh->jostle_first;
245 	/* free space is available */
246 	if(mesh->num_reply_states < mesh->max_reply_states)
247 		return 1;
248 	/* try to kick out a jostle-list item */
249 	if(m && m->reply_list && m->list_select == mesh_jostle_list) {
250 		/* how old is it? */
251 		struct timeval age;
252 		timeval_subtract(&age, mesh->env->now_tv,
253 			&m->reply_list->start_time);
254 		if(timeval_smaller(&mesh->jostle_max, &age)) {
255 			/* its a goner */
256 			log_nametypeclass(VERB_ALGO, "query jostled out to "
257 				"make space for a new one",
258 				m->s.qinfo.qname, m->s.qinfo.qtype,
259 				m->s.qinfo.qclass);
260 			/* backup the query */
261 			if(qbuf) sldns_buffer_copy(mesh->qbuf_bak, qbuf);
262 			/* notify supers */
263 			if(m->super_set.count > 0) {
264 				verbose(VERB_ALGO, "notify supers of failure");
265 				m->s.return_msg = NULL;
266 				m->s.return_rcode = LDNS_RCODE_SERVFAIL;
267 				mesh_walk_supers(mesh, m);
268 			}
269 			mesh->stats_jostled ++;
270 			mesh_state_delete(&m->s);
271 			/* restore the query - note that the qinfo ptr to
272 			 * the querybuffer is then correct again. */
273 			if(qbuf) sldns_buffer_copy(qbuf, mesh->qbuf_bak);
274 			return 1;
275 		}
276 	}
277 	/* no space for new item */
278 	return 0;
279 }
280 
281 void mesh_new_client(struct mesh_area* mesh, struct query_info* qinfo,
282         uint16_t qflags, struct edns_data* edns, struct comm_reply* rep,
283         uint16_t qid)
284 {
285 	struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
286 	int was_detached = 0;
287 	int was_noreply = 0;
288 	int added = 0;
289 	/* does this create a new reply state? */
290 	if(!s || s->list_select == mesh_no_list) {
291 		if(!mesh_make_new_space(mesh, rep->c->buffer)) {
292 			verbose(VERB_ALGO, "Too many queries. dropping "
293 				"incoming query.");
294 			comm_point_drop_reply(rep);
295 			mesh->stats_dropped ++;
296 			return;
297 		}
298 		/* for this new reply state, the reply address is free,
299 		 * so the limit of reply addresses does not stop reply states*/
300 	} else {
301 		/* protect our memory usage from storing reply addresses */
302 		if(mesh->num_reply_addrs > mesh->max_reply_states*16) {
303 			verbose(VERB_ALGO, "Too many requests queued. "
304 				"dropping incoming query.");
305 			mesh->stats_dropped++;
306 			comm_point_drop_reply(rep);
307 			return;
308 		}
309 	}
310 	/* see if it already exists, if not, create one */
311 	if(!s) {
312 #ifdef UNBOUND_DEBUG
313 		struct rbnode_t* n;
314 #endif
315 		s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
316 		if(!s) {
317 			log_err("mesh_state_create: out of memory; SERVFAIL");
318 			if(!edns_opt_inplace_reply(edns, mesh->env->scratch))
319 				edns->opt_list = NULL;
320 			error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL,
321 				qinfo, qid, qflags, edns);
322 			comm_point_send_reply(rep);
323 			return;
324 		}
325 #ifdef UNBOUND_DEBUG
326 		n =
327 #else
328 		(void)
329 #endif
330 		rbtree_insert(&mesh->all, &s->node);
331 		log_assert(n != NULL);
332 		/* set detached (it is now) */
333 		mesh->num_detached_states++;
334 		added = 1;
335 	}
336 	if(!s->reply_list && !s->cb_list && s->super_set.count == 0)
337 		was_detached = 1;
338 	if(!s->reply_list && !s->cb_list)
339 		was_noreply = 1;
340 	/* add reply to s */
341 	if(!mesh_state_add_reply(s, edns, rep, qid, qflags, qinfo->qname)) {
342 			log_err("mesh_new_client: out of memory; SERVFAIL");
343 			if(!edns_opt_inplace_reply(edns, mesh->env->scratch))
344 				edns->opt_list = NULL;
345 			error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL,
346 				qinfo, qid, qflags, edns);
347 			comm_point_send_reply(rep);
348 			if(added)
349 				mesh_state_delete(&s->s);
350 			return;
351 	}
352 	/* update statistics */
353 	if(was_detached) {
354 		log_assert(mesh->num_detached_states > 0);
355 		mesh->num_detached_states--;
356 	}
357 	if(was_noreply) {
358 		mesh->num_reply_states ++;
359 	}
360 	mesh->num_reply_addrs++;
361 	if(s->list_select == mesh_no_list) {
362 		/* move to either the forever or the jostle_list */
363 		if(mesh->num_forever_states < mesh->max_forever_states) {
364 			mesh->num_forever_states ++;
365 			mesh_list_insert(s, &mesh->forever_first,
366 				&mesh->forever_last);
367 			s->list_select = mesh_forever_list;
368 		} else {
369 			mesh_list_insert(s, &mesh->jostle_first,
370 				&mesh->jostle_last);
371 			s->list_select = mesh_jostle_list;
372 		}
373 	}
374 	if(added)
375 		mesh_run(mesh, s, module_event_new, NULL);
376 }
377 
378 int
379 mesh_new_callback(struct mesh_area* mesh, struct query_info* qinfo,
380 	uint16_t qflags, struct edns_data* edns, sldns_buffer* buf,
381 	uint16_t qid, mesh_cb_func_t cb, void* cb_arg)
382 {
383 	struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
384 	int was_detached = 0;
385 	int was_noreply = 0;
386 	int added = 0;
387 	/* there are no limits on the number of callbacks */
388 
389 	/* see if it already exists, if not, create one */
390 	if(!s) {
391 #ifdef UNBOUND_DEBUG
392 		struct rbnode_t* n;
393 #endif
394 		s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
395 		if(!s) {
396 			return 0;
397 		}
398 #ifdef UNBOUND_DEBUG
399 		n =
400 #else
401 		(void)
402 #endif
403 		rbtree_insert(&mesh->all, &s->node);
404 		log_assert(n != NULL);
405 		/* set detached (it is now) */
406 		mesh->num_detached_states++;
407 		added = 1;
408 	}
409 	if(!s->reply_list && !s->cb_list && s->super_set.count == 0)
410 		was_detached = 1;
411 	if(!s->reply_list && !s->cb_list)
412 		was_noreply = 1;
413 	/* add reply to s */
414 	if(!mesh_state_add_cb(s, edns, buf, cb, cb_arg, qid, qflags)) {
415 			if(added)
416 				mesh_state_delete(&s->s);
417 			return 0;
418 	}
419 	/* update statistics */
420 	if(was_detached) {
421 		log_assert(mesh->num_detached_states > 0);
422 		mesh->num_detached_states--;
423 	}
424 	if(was_noreply) {
425 		mesh->num_reply_states ++;
426 	}
427 	mesh->num_reply_addrs++;
428 	if(added)
429 		mesh_run(mesh, s, module_event_new, NULL);
430 	return 1;
431 }
432 
433 void mesh_new_prefetch(struct mesh_area* mesh, struct query_info* qinfo,
434         uint16_t qflags, time_t leeway)
435 {
436 	struct mesh_state* s = mesh_area_find(mesh, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
437 #ifdef UNBOUND_DEBUG
438 	struct rbnode_t* n;
439 #endif
440 	/* already exists, and for a different purpose perhaps.
441 	 * if mesh_no_list, keep it that way. */
442 	if(s) {
443 		/* make it ignore the cache from now on */
444 		if(!s->s.blacklist)
445 			sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region);
446 		if(s->s.prefetch_leeway < leeway)
447 			s->s.prefetch_leeway = leeway;
448 		return;
449 	}
450 	if(!mesh_make_new_space(mesh, NULL)) {
451 		verbose(VERB_ALGO, "Too many queries. dropped prefetch.");
452 		mesh->stats_dropped ++;
453 		return;
454 	}
455 	s = mesh_state_create(mesh->env, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
456 	if(!s) {
457 		log_err("prefetch mesh_state_create: out of memory");
458 		return;
459 	}
460 #ifdef UNBOUND_DEBUG
461 	n =
462 #else
463 	(void)
464 #endif
465 	rbtree_insert(&mesh->all, &s->node);
466 	log_assert(n != NULL);
467 	/* set detached (it is now) */
468 	mesh->num_detached_states++;
469 	/* make it ignore the cache */
470 	sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region);
471 	s->s.prefetch_leeway = leeway;
472 
473 	if(s->list_select == mesh_no_list) {
474 		/* move to either the forever or the jostle_list */
475 		if(mesh->num_forever_states < mesh->max_forever_states) {
476 			mesh->num_forever_states ++;
477 			mesh_list_insert(s, &mesh->forever_first,
478 				&mesh->forever_last);
479 			s->list_select = mesh_forever_list;
480 		} else {
481 			mesh_list_insert(s, &mesh->jostle_first,
482 				&mesh->jostle_last);
483 			s->list_select = mesh_jostle_list;
484 		}
485 	}
486 	mesh_run(mesh, s, module_event_new, NULL);
487 }
488 
489 void mesh_report_reply(struct mesh_area* mesh, struct outbound_entry* e,
490         struct comm_reply* reply, int what)
491 {
492 	enum module_ev event = module_event_reply;
493 	e->qstate->reply = reply;
494 	if(what != NETEVENT_NOERROR) {
495 		event = module_event_noreply;
496 		if(what == NETEVENT_CAPSFAIL)
497 			event = module_event_capsfail;
498 	}
499 	mesh_run(mesh, e->qstate->mesh_info, event, e);
500 }
501 
502 struct mesh_state*
503 mesh_state_create(struct module_env* env, struct query_info* qinfo,
504 	uint16_t qflags, int prime, int valrec)
505 {
506 	struct regional* region = alloc_reg_obtain(env->alloc);
507 	struct mesh_state* mstate;
508 	int i;
509 	if(!region)
510 		return NULL;
511 	mstate = (struct mesh_state*)regional_alloc(region,
512 		sizeof(struct mesh_state));
513 	if(!mstate) {
514 		alloc_reg_release(env->alloc, region);
515 		return NULL;
516 	}
517 	memset(mstate, 0, sizeof(*mstate));
518 	mstate->node = *RBTREE_NULL;
519 	mstate->run_node = *RBTREE_NULL;
520 	mstate->node.key = mstate;
521 	mstate->run_node.key = mstate;
522 	mstate->reply_list = NULL;
523 	mstate->list_select = mesh_no_list;
524 	mstate->replies_sent = 0;
525 	rbtree_init(&mstate->super_set, &mesh_state_ref_compare);
526 	rbtree_init(&mstate->sub_set, &mesh_state_ref_compare);
527 	mstate->num_activated = 0;
528 	/* init module qstate */
529 	mstate->s.qinfo.qtype = qinfo->qtype;
530 	mstate->s.qinfo.qclass = qinfo->qclass;
531 	mstate->s.qinfo.qname_len = qinfo->qname_len;
532 	mstate->s.qinfo.qname = regional_alloc_init(region, qinfo->qname,
533 		qinfo->qname_len);
534 	if(!mstate->s.qinfo.qname) {
535 		alloc_reg_release(env->alloc, region);
536 		return NULL;
537 	}
538 	/* remove all weird bits from qflags */
539 	mstate->s.query_flags = (qflags & (BIT_RD|BIT_CD));
540 	mstate->s.is_priming = prime;
541 	mstate->s.is_valrec = valrec;
542 	mstate->s.reply = NULL;
543 	mstate->s.region = region;
544 	mstate->s.curmod = 0;
545 	mstate->s.return_msg = 0;
546 	mstate->s.return_rcode = LDNS_RCODE_NOERROR;
547 	mstate->s.env = env;
548 	mstate->s.mesh_info = mstate;
549 	mstate->s.prefetch_leeway = 0;
550 	/* init modules */
551 	for(i=0; i<env->mesh->mods.num; i++) {
552 		mstate->s.minfo[i] = NULL;
553 		mstate->s.ext_state[i] = module_state_initial;
554 	}
555 	return mstate;
556 }
557 
558 void
559 mesh_state_cleanup(struct mesh_state* mstate)
560 {
561 	struct mesh_area* mesh;
562 	int i;
563 	if(!mstate)
564 		return;
565 	mesh = mstate->s.env->mesh;
566 	/* drop unsent replies */
567 	if(!mstate->replies_sent) {
568 		struct mesh_reply* rep;
569 		struct mesh_cb* cb;
570 		for(rep=mstate->reply_list; rep; rep=rep->next) {
571 			comm_point_drop_reply(&rep->query_reply);
572 			mesh->num_reply_addrs--;
573 		}
574 		for(cb=mstate->cb_list; cb; cb=cb->next) {
575 			fptr_ok(fptr_whitelist_mesh_cb(cb->cb));
576 			(*cb->cb)(cb->cb_arg, LDNS_RCODE_SERVFAIL, NULL,
577 				sec_status_unchecked, NULL);
578 			mesh->num_reply_addrs--;
579 		}
580 	}
581 
582 	/* de-init modules */
583 	for(i=0; i<mesh->mods.num; i++) {
584 		fptr_ok(fptr_whitelist_mod_clear(mesh->mods.mod[i]->clear));
585 		(*mesh->mods.mod[i]->clear)(&mstate->s, i);
586 		mstate->s.minfo[i] = NULL;
587 		mstate->s.ext_state[i] = module_finished;
588 	}
589 	alloc_reg_release(mstate->s.env->alloc, mstate->s.region);
590 }
591 
592 void
593 mesh_state_delete(struct module_qstate* qstate)
594 {
595 	struct mesh_area* mesh;
596 	struct mesh_state_ref* super, ref;
597 	struct mesh_state* mstate;
598 	if(!qstate)
599 		return;
600 	mstate = qstate->mesh_info;
601 	mesh = mstate->s.env->mesh;
602 	mesh_detach_subs(&mstate->s);
603 	if(mstate->list_select == mesh_forever_list) {
604 		mesh->num_forever_states --;
605 		mesh_list_remove(mstate, &mesh->forever_first,
606 			&mesh->forever_last);
607 	} else if(mstate->list_select == mesh_jostle_list) {
608 		mesh_list_remove(mstate, &mesh->jostle_first,
609 			&mesh->jostle_last);
610 	}
611 	if(!mstate->reply_list && !mstate->cb_list
612 		&& mstate->super_set.count == 0) {
613 		log_assert(mesh->num_detached_states > 0);
614 		mesh->num_detached_states--;
615 	}
616 	if(mstate->reply_list || mstate->cb_list) {
617 		log_assert(mesh->num_reply_states > 0);
618 		mesh->num_reply_states--;
619 	}
620 	ref.node.key = &ref;
621 	ref.s = mstate;
622 	RBTREE_FOR(super, struct mesh_state_ref*, &mstate->super_set) {
623 		(void)rbtree_delete(&super->s->sub_set, &ref);
624 	}
625 	(void)rbtree_delete(&mesh->run, mstate);
626 	(void)rbtree_delete(&mesh->all, mstate);
627 	mesh_state_cleanup(mstate);
628 }
629 
630 /** helper recursive rbtree find routine */
631 static int
632 find_in_subsub(struct mesh_state* m, struct mesh_state* tofind, size_t *c)
633 {
634 	struct mesh_state_ref* r;
635 	if((*c)++ > MESH_MAX_SUBSUB)
636 		return 1;
637 	RBTREE_FOR(r, struct mesh_state_ref*, &m->sub_set) {
638 		if(r->s == tofind || find_in_subsub(r->s, tofind, c))
639 			return 1;
640 	}
641 	return 0;
642 }
643 
644 /** find cycle for already looked up mesh_state */
645 static int
646 mesh_detect_cycle_found(struct module_qstate* qstate, struct mesh_state* dep_m)
647 {
648 	struct mesh_state* cyc_m = qstate->mesh_info;
649 	size_t counter = 0;
650 	if(!dep_m)
651 		return 0;
652 	if(dep_m == cyc_m || find_in_subsub(dep_m, cyc_m, &counter)) {
653 		if(counter > MESH_MAX_SUBSUB)
654 			return 2;
655 		return 1;
656 	}
657 	return 0;
658 }
659 
660 void mesh_detach_subs(struct module_qstate* qstate)
661 {
662 	struct mesh_area* mesh = qstate->env->mesh;
663 	struct mesh_state_ref* ref, lookup;
664 #ifdef UNBOUND_DEBUG
665 	struct rbnode_t* n;
666 #endif
667 	lookup.node.key = &lookup;
668 	lookup.s = qstate->mesh_info;
669 	RBTREE_FOR(ref, struct mesh_state_ref*, &qstate->mesh_info->sub_set) {
670 #ifdef UNBOUND_DEBUG
671 		n =
672 #else
673 		(void)
674 #endif
675 		rbtree_delete(&ref->s->super_set, &lookup);
676 		log_assert(n != NULL); /* must have been present */
677 		if(!ref->s->reply_list && !ref->s->cb_list
678 			&& ref->s->super_set.count == 0) {
679 			mesh->num_detached_states++;
680 			log_assert(mesh->num_detached_states +
681 				mesh->num_reply_states <= mesh->all.count);
682 		}
683 	}
684 	rbtree_init(&qstate->mesh_info->sub_set, &mesh_state_ref_compare);
685 }
686 
687 int mesh_attach_sub(struct module_qstate* qstate, struct query_info* qinfo,
688         uint16_t qflags, int prime, int valrec, struct module_qstate** newq)
689 {
690 	/* find it, if not, create it */
691 	struct mesh_area* mesh = qstate->env->mesh;
692 	struct mesh_state* sub = mesh_area_find(mesh, qinfo, qflags, prime,
693 		valrec);
694 	int was_detached;
695 	if(mesh_detect_cycle_found(qstate, sub)) {
696 		verbose(VERB_ALGO, "attach failed, cycle detected");
697 		return 0;
698 	}
699 	if(!sub) {
700 #ifdef UNBOUND_DEBUG
701 		struct rbnode_t* n;
702 #endif
703 		/* create a new one */
704 		sub = mesh_state_create(qstate->env, qinfo, qflags, prime,
705 			valrec);
706 		if(!sub) {
707 			log_err("mesh_attach_sub: out of memory");
708 			return 0;
709 		}
710 #ifdef UNBOUND_DEBUG
711 		n =
712 #else
713 		(void)
714 #endif
715 		rbtree_insert(&mesh->all, &sub->node);
716 		log_assert(n != NULL);
717 		/* set detached (it is now) */
718 		mesh->num_detached_states++;
719 		/* set new query state to run */
720 #ifdef UNBOUND_DEBUG
721 		n =
722 #else
723 		(void)
724 #endif
725 		rbtree_insert(&mesh->run, &sub->run_node);
726 		log_assert(n != NULL);
727 		*newq = &sub->s;
728 	} else
729 		*newq = NULL;
730 	was_detached = (sub->super_set.count == 0);
731 	if(!mesh_state_attachment(qstate->mesh_info, sub))
732 		return 0;
733 	/* if it was a duplicate  attachment, the count was not zero before */
734 	if(!sub->reply_list && !sub->cb_list && was_detached &&
735 		sub->super_set.count == 1) {
736 		/* it used to be detached, before this one got added */
737 		log_assert(mesh->num_detached_states > 0);
738 		mesh->num_detached_states--;
739 	}
740 	/* *newq will be run when inited after the current module stops */
741 	return 1;
742 }
743 
744 int mesh_state_attachment(struct mesh_state* super, struct mesh_state* sub)
745 {
746 #ifdef UNBOUND_DEBUG
747 	struct rbnode_t* n;
748 #endif
749 	struct mesh_state_ref* subref; /* points to sub, inserted in super */
750 	struct mesh_state_ref* superref; /* points to super, inserted in sub */
751 	if( !(subref = regional_alloc(super->s.region,
752 		sizeof(struct mesh_state_ref))) ||
753 		!(superref = regional_alloc(sub->s.region,
754 		sizeof(struct mesh_state_ref))) ) {
755 		log_err("mesh_state_attachment: out of memory");
756 		return 0;
757 	}
758 	superref->node.key = superref;
759 	superref->s = super;
760 	subref->node.key = subref;
761 	subref->s = sub;
762 	if(!rbtree_insert(&sub->super_set, &superref->node)) {
763 		/* this should not happen, iterator and validator do not
764 		 * attach subqueries that are identical. */
765 		/* already attached, we are done, nothing todo.
766 		 * since superref and subref already allocated in region,
767 		 * we cannot free them */
768 		return 1;
769 	}
770 #ifdef UNBOUND_DEBUG
771 	n =
772 #else
773 	(void)
774 #endif
775 	rbtree_insert(&super->sub_set, &subref->node);
776 	log_assert(n != NULL); /* we checked above if statement, the reverse
777 	  administration should not fail now, unless they are out of sync */
778 	return 1;
779 }
780 
781 /**
782  * callback results to mesh cb entry
783  * @param m: mesh state to send it for.
784  * @param rcode: if not 0, error code.
785  * @param rep: reply to send (or NULL if rcode is set).
786  * @param r: callback entry
787  */
788 static void
789 mesh_do_callback(struct mesh_state* m, int rcode, struct reply_info* rep,
790 	struct mesh_cb* r)
791 {
792 	int secure;
793 	char* reason = NULL;
794 	/* bogus messages are not made into servfail, sec_status passed
795 	 * to the callback function */
796 	if(rep && rep->security == sec_status_secure)
797 		secure = 1;
798 	else	secure = 0;
799 	if(!rep && rcode == LDNS_RCODE_NOERROR)
800 		rcode = LDNS_RCODE_SERVFAIL;
801 	if(!rcode && rep->security == sec_status_bogus) {
802 		if(!(reason = errinf_to_str(&m->s)))
803 			rcode = LDNS_RCODE_SERVFAIL;
804 	}
805 	/* send the reply */
806 	if(rcode) {
807 		fptr_ok(fptr_whitelist_mesh_cb(r->cb));
808 		(*r->cb)(r->cb_arg, rcode, r->buf, sec_status_unchecked, NULL);
809 	} else {
810 		size_t udp_size = r->edns.udp_size;
811 		sldns_buffer_clear(r->buf);
812 		r->edns.edns_version = EDNS_ADVERTISED_VERSION;
813 		r->edns.udp_size = EDNS_ADVERTISED_SIZE;
814 		r->edns.ext_rcode = 0;
815 		r->edns.bits &= EDNS_DO;
816 		if(!edns_opt_inplace_reply(&r->edns, m->s.region) ||
817 		   !reply_info_answer_encode(&m->s.qinfo, rep, r->qid,
818 			r->qflags, r->buf, 0, 1,
819 			m->s.env->scratch, udp_size, &r->edns,
820 			(int)(r->edns.bits & EDNS_DO), secure))
821 		{
822 			fptr_ok(fptr_whitelist_mesh_cb(r->cb));
823 			(*r->cb)(r->cb_arg, LDNS_RCODE_SERVFAIL, r->buf,
824 				sec_status_unchecked, NULL);
825 		} else {
826 			fptr_ok(fptr_whitelist_mesh_cb(r->cb));
827 			(*r->cb)(r->cb_arg, LDNS_RCODE_NOERROR, r->buf,
828 				rep->security, reason);
829 		}
830 	}
831 	free(reason);
832 	m->s.env->mesh->num_reply_addrs--;
833 }
834 
835 /**
836  * Send reply to mesh reply entry
837  * @param m: mesh state to send it for.
838  * @param rcode: if not 0, error code.
839  * @param rep: reply to send (or NULL if rcode is set).
840  * @param r: reply entry
841  * @param prev: previous reply, already has its answer encoded in buffer.
842  */
843 static void
844 mesh_send_reply(struct mesh_state* m, int rcode, struct reply_info* rep,
845 	struct mesh_reply* r, struct mesh_reply* prev)
846 {
847 	struct timeval end_time;
848 	struct timeval duration;
849 	int secure;
850 	/* examine security status */
851 	if(m->s.env->need_to_validate && (!(r->qflags&BIT_CD) ||
852 		m->s.env->cfg->ignore_cd) && rep &&
853 		rep->security <= sec_status_bogus) {
854 		rcode = LDNS_RCODE_SERVFAIL;
855 		if(m->s.env->cfg->stat_extended)
856 			m->s.env->mesh->ans_bogus++;
857 	}
858 	if(rep && rep->security == sec_status_secure)
859 		secure = 1;
860 	else	secure = 0;
861 	if(!rep && rcode == LDNS_RCODE_NOERROR)
862 		rcode = LDNS_RCODE_SERVFAIL;
863 	/* send the reply */
864 	if(prev && prev->qflags == r->qflags &&
865 		prev->edns.edns_present == r->edns.edns_present &&
866 		prev->edns.bits == r->edns.bits &&
867 		prev->edns.udp_size == r->edns.udp_size &&
868 		edns_opt_list_compare(prev->edns.opt_list, r->edns.opt_list)
869 		== 0) {
870 		/* if the previous reply is identical to this one, fix ID */
871 		if(prev->query_reply.c->buffer != r->query_reply.c->buffer)
872 			sldns_buffer_copy(r->query_reply.c->buffer,
873 				prev->query_reply.c->buffer);
874 		sldns_buffer_write_at(r->query_reply.c->buffer, 0,
875 			&r->qid, sizeof(uint16_t));
876 		sldns_buffer_write_at(r->query_reply.c->buffer, 12,
877 			r->qname, m->s.qinfo.qname_len);
878 		comm_point_send_reply(&r->query_reply);
879 	} else if(rcode) {
880 		m->s.qinfo.qname = r->qname;
881 		error_encode(r->query_reply.c->buffer, rcode, &m->s.qinfo,
882 			r->qid, r->qflags, &r->edns);
883 		comm_point_send_reply(&r->query_reply);
884 	} else {
885 		size_t udp_size = r->edns.udp_size;
886 		r->edns.edns_version = EDNS_ADVERTISED_VERSION;
887 		r->edns.udp_size = EDNS_ADVERTISED_SIZE;
888 		r->edns.ext_rcode = 0;
889 		r->edns.bits &= EDNS_DO;
890 		m->s.qinfo.qname = r->qname;
891 		if(!edns_opt_inplace_reply(&r->edns, m->s.region) ||
892 		   !reply_info_answer_encode(&m->s.qinfo, rep, r->qid,
893 			r->qflags, r->query_reply.c->buffer, 0, 1,
894 			m->s.env->scratch, udp_size, &r->edns,
895 			(int)(r->edns.bits & EDNS_DO), secure))
896 		{
897 			error_encode(r->query_reply.c->buffer,
898 				LDNS_RCODE_SERVFAIL, &m->s.qinfo, r->qid,
899 				r->qflags, &r->edns);
900 		}
901 		comm_point_send_reply(&r->query_reply);
902 	}
903 	/* account */
904 	m->s.env->mesh->num_reply_addrs--;
905 	end_time = *m->s.env->now_tv;
906 	timeval_subtract(&duration, &end_time, &r->start_time);
907 	verbose(VERB_ALGO, "query took " ARG_LL "d.%6.6d sec",
908 		(long long)duration.tv_sec, (int)duration.tv_usec);
909 	m->s.env->mesh->replies_sent++;
910 	timeval_add(&m->s.env->mesh->replies_sum_wait, &duration);
911 	timehist_insert(m->s.env->mesh->histogram, &duration);
912 	if(m->s.env->cfg->stat_extended) {
913 		uint16_t rc = FLAGS_GET_RCODE(sldns_buffer_read_u16_at(r->
914 			query_reply.c->buffer, 2));
915 		if(secure) m->s.env->mesh->ans_secure++;
916 		m->s.env->mesh->ans_rcode[ rc ] ++;
917 		if(rc == 0 && LDNS_ANCOUNT(sldns_buffer_begin(r->
918 			query_reply.c->buffer)) == 0)
919 			m->s.env->mesh->ans_nodata++;
920 	}
921 }
922 
923 void mesh_query_done(struct mesh_state* mstate)
924 {
925 	struct mesh_reply* r;
926 	struct mesh_reply* prev = NULL;
927 	struct mesh_cb* c;
928 	struct reply_info* rep = (mstate->s.return_msg?
929 		mstate->s.return_msg->rep:NULL);
930 	for(r = mstate->reply_list; r; r = r->next) {
931 		mesh_send_reply(mstate, mstate->s.return_rcode, rep, r, prev);
932 		prev = r;
933 	}
934 	mstate->replies_sent = 1;
935 	for(c = mstate->cb_list; c; c = c->next) {
936 		mesh_do_callback(mstate, mstate->s.return_rcode, rep, c);
937 	}
938 }
939 
940 void mesh_walk_supers(struct mesh_area* mesh, struct mesh_state* mstate)
941 {
942 	struct mesh_state_ref* ref;
943 	RBTREE_FOR(ref, struct mesh_state_ref*, &mstate->super_set)
944 	{
945 		/* make super runnable */
946 		(void)rbtree_insert(&mesh->run, &ref->s->run_node);
947 		/* callback the function to inform super of result */
948 		fptr_ok(fptr_whitelist_mod_inform_super(
949 			mesh->mods.mod[ref->s->s.curmod]->inform_super));
950 		(*mesh->mods.mod[ref->s->s.curmod]->inform_super)(&mstate->s,
951 			ref->s->s.curmod, &ref->s->s);
952 	}
953 }
954 
955 struct mesh_state* mesh_area_find(struct mesh_area* mesh,
956 	struct query_info* qinfo, uint16_t qflags, int prime, int valrec)
957 {
958 	struct mesh_state key;
959 	struct mesh_state* result;
960 
961 	key.node.key = &key;
962 	key.s.is_priming = prime;
963 	key.s.is_valrec = valrec;
964 	key.s.qinfo = *qinfo;
965 	key.s.query_flags = qflags;
966 
967 	result = (struct mesh_state*)rbtree_search(&mesh->all, &key);
968 	return result;
969 }
970 
971 int mesh_state_add_cb(struct mesh_state* s, struct edns_data* edns,
972         sldns_buffer* buf, mesh_cb_func_t cb, void* cb_arg,
973 	uint16_t qid, uint16_t qflags)
974 {
975 	struct mesh_cb* r = regional_alloc(s->s.region,
976 		sizeof(struct mesh_cb));
977 	if(!r)
978 		return 0;
979 	r->buf = buf;
980 	log_assert(fptr_whitelist_mesh_cb(cb)); /* early failure ifmissing*/
981 	r->cb = cb;
982 	r->cb_arg = cb_arg;
983 	r->edns = *edns;
984 	if(edns->opt_list) {
985 		r->edns.opt_list = edns_opt_copy_region(edns->opt_list,
986 			s->s.region);
987 		if(!r->edns.opt_list)
988 			return 0;
989 	}
990 	r->qid = qid;
991 	r->qflags = qflags;
992 	r->next = s->cb_list;
993 	s->cb_list = r;
994 	return 1;
995 
996 }
997 
998 int mesh_state_add_reply(struct mesh_state* s, struct edns_data* edns,
999         struct comm_reply* rep, uint16_t qid, uint16_t qflags, uint8_t* qname)
1000 {
1001 	struct mesh_reply* r = regional_alloc(s->s.region,
1002 		sizeof(struct mesh_reply));
1003 	if(!r)
1004 		return 0;
1005 	r->query_reply = *rep;
1006 	r->edns = *edns;
1007 	if(edns->opt_list) {
1008 		r->edns.opt_list = edns_opt_copy_region(edns->opt_list,
1009 			s->s.region);
1010 		if(!r->edns.opt_list)
1011 			return 0;
1012 	}
1013 	r->qid = qid;
1014 	r->qflags = qflags;
1015 	r->start_time = *s->s.env->now_tv;
1016 	r->next = s->reply_list;
1017 	r->qname = regional_alloc_init(s->s.region, qname,
1018 		s->s.qinfo.qname_len);
1019 	if(!r->qname)
1020 		return 0;
1021 	s->reply_list = r;
1022 	return 1;
1023 }
1024 
1025 /**
1026  * Continue processing the mesh state at another module.
1027  * Handles module to modules tranfer of control.
1028  * Handles module finished.
1029  * @param mesh: the mesh area.
1030  * @param mstate: currently active mesh state.
1031  * 	Deleted if finished, calls _done and _supers to
1032  * 	send replies to clients and inform other mesh states.
1033  * 	This in turn may create additional runnable mesh states.
1034  * @param s: state at which the current module exited.
1035  * @param ev: the event sent to the module.
1036  * 	returned is the event to send to the next module.
1037  * @return true if continue processing at the new module.
1038  * 	false if not continued processing is needed.
1039  */
1040 static int
1041 mesh_continue(struct mesh_area* mesh, struct mesh_state* mstate,
1042 	enum module_ext_state s, enum module_ev* ev)
1043 {
1044 	mstate->num_activated++;
1045 	if(mstate->num_activated > MESH_MAX_ACTIVATION) {
1046 		/* module is looping. Stop it. */
1047 		log_err("internal error: looping module stopped");
1048 		log_query_info(VERB_QUERY, "pass error for qstate",
1049 			&mstate->s.qinfo);
1050 		s = module_error;
1051 	}
1052 	if(s == module_wait_module || s == module_restart_next) {
1053 		/* start next module */
1054 		mstate->s.curmod++;
1055 		if(mesh->mods.num == mstate->s.curmod) {
1056 			log_err("Cannot pass to next module; at last module");
1057 			log_query_info(VERB_QUERY, "pass error for qstate",
1058 				&mstate->s.qinfo);
1059 			mstate->s.curmod--;
1060 			return mesh_continue(mesh, mstate, module_error, ev);
1061 		}
1062 		if(s == module_restart_next) {
1063 			fptr_ok(fptr_whitelist_mod_clear(
1064 				mesh->mods.mod[mstate->s.curmod]->clear));
1065 			(*mesh->mods.mod[mstate->s.curmod]->clear)
1066 				(&mstate->s, mstate->s.curmod);
1067 			mstate->s.minfo[mstate->s.curmod] = NULL;
1068 		}
1069 		*ev = module_event_pass;
1070 		return 1;
1071 	}
1072 	if(s == module_wait_subquery && mstate->sub_set.count == 0) {
1073 		log_err("module cannot wait for subquery, subquery list empty");
1074 		log_query_info(VERB_QUERY, "pass error for qstate",
1075 			&mstate->s.qinfo);
1076 		s = module_error;
1077 	}
1078 	if(s == module_error && mstate->s.return_rcode == LDNS_RCODE_NOERROR) {
1079 		/* error is bad, handle pass back up below */
1080 		mstate->s.return_rcode = LDNS_RCODE_SERVFAIL;
1081 	}
1082 	if(s == module_error || s == module_finished) {
1083 		if(mstate->s.curmod == 0) {
1084 			mesh_query_done(mstate);
1085 			mesh_walk_supers(mesh, mstate);
1086 			mesh_state_delete(&mstate->s);
1087 			return 0;
1088 		}
1089 		/* pass along the locus of control */
1090 		mstate->s.curmod --;
1091 		*ev = module_event_moddone;
1092 		return 1;
1093 	}
1094 	return 0;
1095 }
1096 
1097 void mesh_run(struct mesh_area* mesh, struct mesh_state* mstate,
1098 	enum module_ev ev, struct outbound_entry* e)
1099 {
1100 	enum module_ext_state s;
1101 	verbose(VERB_ALGO, "mesh_run: start");
1102 	while(mstate) {
1103 		/* run the module */
1104 		fptr_ok(fptr_whitelist_mod_operate(
1105 			mesh->mods.mod[mstate->s.curmod]->operate));
1106 		(*mesh->mods.mod[mstate->s.curmod]->operate)
1107 			(&mstate->s, ev, mstate->s.curmod, e);
1108 
1109 		/* examine results */
1110 		mstate->s.reply = NULL;
1111 		regional_free_all(mstate->s.env->scratch);
1112 		s = mstate->s.ext_state[mstate->s.curmod];
1113 		verbose(VERB_ALGO, "mesh_run: %s module exit state is %s",
1114 			mesh->mods.mod[mstate->s.curmod]->name, strextstate(s));
1115 		e = NULL;
1116 		if(mesh_continue(mesh, mstate, s, &ev))
1117 			continue;
1118 
1119 		/* run more modules */
1120 		ev = module_event_pass;
1121 		if(mesh->run.count > 0) {
1122 			/* pop random element off the runnable tree */
1123 			mstate = (struct mesh_state*)mesh->run.root->key;
1124 			(void)rbtree_delete(&mesh->run, mstate);
1125 		} else mstate = NULL;
1126 	}
1127 	if(verbosity >= VERB_ALGO) {
1128 		mesh_stats(mesh, "mesh_run: end");
1129 		mesh_log_list(mesh);
1130 	}
1131 }
1132 
1133 void
1134 mesh_log_list(struct mesh_area* mesh)
1135 {
1136 	char buf[30];
1137 	struct mesh_state* m;
1138 	int num = 0;
1139 	RBTREE_FOR(m, struct mesh_state*, &mesh->all) {
1140 		snprintf(buf, sizeof(buf), "%d%s%s%s%s%s%s mod%d %s%s",
1141 			num++, (m->s.is_priming)?"p":"",  /* prime */
1142 			(m->s.is_valrec)?"v":"",  /* prime */
1143 			(m->s.query_flags&BIT_RD)?"RD":"",
1144 			(m->s.query_flags&BIT_CD)?"CD":"",
1145 			(m->super_set.count==0)?"d":"", /* detached */
1146 			(m->sub_set.count!=0)?"c":"",  /* children */
1147 			m->s.curmod, (m->reply_list)?"rep":"", /*hasreply*/
1148 			(m->cb_list)?"cb":"" /* callbacks */
1149 			);
1150 		log_query_info(VERB_ALGO, buf, &m->s.qinfo);
1151 	}
1152 }
1153 
1154 void
1155 mesh_stats(struct mesh_area* mesh, const char* str)
1156 {
1157 	verbose(VERB_DETAIL, "%s %u recursion states (%u with reply, "
1158 		"%u detached), %u waiting replies, %u recursion replies "
1159 		"sent, %d replies dropped, %d states jostled out",
1160 		str, (unsigned)mesh->all.count,
1161 		(unsigned)mesh->num_reply_states,
1162 		(unsigned)mesh->num_detached_states,
1163 		(unsigned)mesh->num_reply_addrs,
1164 		(unsigned)mesh->replies_sent,
1165 		(unsigned)mesh->stats_dropped,
1166 		(unsigned)mesh->stats_jostled);
1167 	if(mesh->replies_sent > 0) {
1168 		struct timeval avg;
1169 		timeval_divide(&avg, &mesh->replies_sum_wait,
1170 			mesh->replies_sent);
1171 		log_info("average recursion processing time "
1172 			ARG_LL "d.%6.6d sec",
1173 			(long long)avg.tv_sec, (int)avg.tv_usec);
1174 		log_info("histogram of recursion processing times");
1175 		timehist_log(mesh->histogram, "recursions");
1176 	}
1177 }
1178 
1179 void
1180 mesh_stats_clear(struct mesh_area* mesh)
1181 {
1182 	if(!mesh)
1183 		return;
1184 	mesh->replies_sent = 0;
1185 	mesh->replies_sum_wait.tv_sec = 0;
1186 	mesh->replies_sum_wait.tv_usec = 0;
1187 	mesh->stats_jostled = 0;
1188 	mesh->stats_dropped = 0;
1189 	timehist_clear(mesh->histogram);
1190 	mesh->ans_secure = 0;
1191 	mesh->ans_bogus = 0;
1192 	memset(&mesh->ans_rcode[0], 0, sizeof(size_t)*16);
1193 	mesh->ans_nodata = 0;
1194 }
1195 
1196 size_t
1197 mesh_get_mem(struct mesh_area* mesh)
1198 {
1199 	struct mesh_state* m;
1200 	size_t s = sizeof(*mesh) + sizeof(struct timehist) +
1201 		sizeof(struct th_buck)*mesh->histogram->num +
1202 		sizeof(sldns_buffer) + sldns_buffer_capacity(mesh->qbuf_bak);
1203 	RBTREE_FOR(m, struct mesh_state*, &mesh->all) {
1204 		/* all, including m itself allocated in qstate region */
1205 		s += regional_get_mem(m->s.region);
1206 	}
1207 	return s;
1208 }
1209 
1210 int
1211 mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo,
1212 	uint16_t flags, int prime, int valrec)
1213 {
1214 	struct mesh_area* mesh = qstate->env->mesh;
1215 	struct mesh_state* dep_m = mesh_area_find(mesh, qinfo, flags, prime,
1216 		valrec);
1217 	return mesh_detect_cycle_found(qstate, dep_m);
1218 }
1219 
1220 void mesh_list_insert(struct mesh_state* m, struct mesh_state** fp,
1221         struct mesh_state** lp)
1222 {
1223 	/* insert as last element */
1224 	m->prev = *lp;
1225 	m->next = NULL;
1226 	if(*lp)
1227 		(*lp)->next = m;
1228 	else	*fp = m;
1229 	*lp = m;
1230 }
1231 
1232 void mesh_list_remove(struct mesh_state* m, struct mesh_state** fp,
1233         struct mesh_state** lp)
1234 {
1235 	if(m->next)
1236 		m->next->prev = m->prev;
1237 	else	*lp = m->prev;
1238 	if(m->prev)
1239 		m->prev->next = m->next;
1240 	else	*fp = m->next;
1241 }
1242