contrib/unbound/services/mesh.c

   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 #include "sldns/wire2str.h"
  60 #include "services/localzone.h"
  61 #include "util/data/dname.h"
  62 #include "respip/respip.h"
  63
  64 /** subtract timers and the values do not overflow or become negative */
  65 static void
  66 timeval_subtract(struct timeval* d, const struct timeval* end, const struct timeval* start)
  67 {
  68 #ifndef S_SPLINT_S
  69         time_t end_usec = end->tv_usec;
  70         d->tv_sec = end->tv_sec - start->tv_sec;
  71         if(end_usec < start->tv_usec) {
  72                 end_usec += 1000000;
  73                 d->tv_sec--;
  74         }
  75         d->tv_usec = end_usec - start->tv_usec;
  76 #endif
  77 }
  78
  79 /** add timers and the values do not overflow or become negative */
  80 static void
  81 timeval_add(struct timeval* d, const struct timeval* add)
  82 {
  83 #ifndef S_SPLINT_S
  84         d->tv_sec += add->tv_sec;
  85         d->tv_usec += add->tv_usec;
  86         if(d->tv_usec > 1000000 ) {
  87                 d->tv_usec -= 1000000;
  88                 d->tv_sec++;
  89         }
  90 #endif
  91 }
  92
  93 /** divide sum of timers to get average */
  94 static void
  95 timeval_divide(struct timeval* avg, const struct timeval* sum, size_t d)
  96 {
  97 #ifndef S_SPLINT_S
  98         size_t leftover;
  99         if(d == 0) {
 100                 avg->tv_sec = 0;
 101                 avg->tv_usec = 0;
 102                 return;
 103         }
 104         avg->tv_sec = sum->tv_sec / d;
 105         avg->tv_usec = sum->tv_usec / d;
 106         /* handle fraction from seconds divide */
 107         leftover = sum->tv_sec - avg->tv_sec*d;
 108         avg->tv_usec += (leftover*1000000)/d;
 109 #endif
 110 }
 111
 112 /** histogram compare of time values */
 113 static int
 114 timeval_smaller(const struct timeval* x, const struct timeval* y)
 115 {
 116 #ifndef S_SPLINT_S
 117         if(x->tv_sec < y->tv_sec)
 118                 return 1;
 119         else if(x->tv_sec == y->tv_sec) {
 120                 if(x->tv_usec <= y->tv_usec)
 121                         return 1;
 122                 else    return 0;
 123         }
 124         else    return 0;
 125 #endif
 126 }
 127
 128 /*
 129  * Compare two response-ip client info entries for the purpose of mesh state
 130  * compare.  It returns 0 if ci_a and ci_b are considered equal; otherwise
 131  * 1 or -1 (they mean 'ci_a is larger/smaller than ci_b', respectively, but
 132  * in practice it should be only used to mean they are different).
 133  * We cannot share the mesh state for two queries if different response-ip
 134  * actions can apply in the end, even if those queries are otherwise identical.
 135  * For this purpose we compare tag lists and tag action lists; they should be
 136  * identical to share the same state.
 137  * For tag data, we don't look into the data content, as it can be
 138  * expensive; unless tag data are not defined for both or they point to the
 139  * exact same data in memory (i.e., they come from the same ACL entry), we
 140  * consider these data different.
 141  * Likewise, if the client info is associated with views, we don't look into
 142  * the views.  They are considered different unless they are exactly the same
 143  * even if the views only differ in the names.
 144  */
 145 static int
 146 client_info_compare(const struct respip_client_info* ci_a,
 147         const struct respip_client_info* ci_b)
 148 {
 149         int cmp;
 150
 151         if(!ci_a && !ci_b)
 152                 return 0;
 153         if(ci_a && !ci_b)
 154                 return -1;
 155         if(!ci_a && ci_b)
 156                 return 1;
 157         if(ci_a->taglen != ci_b->taglen)
 158                 return (ci_a->taglen < ci_b->taglen) ? -1 : 1;
 159         cmp = memcmp(ci_a->taglist, ci_b->taglist, ci_a->taglen);
 160         if(cmp != 0)
 161                 return cmp;
 162         if(ci_a->tag_actions_size != ci_b->tag_actions_size)
 163                 return (ci_a->tag_actions_size < ci_b->tag_actions_size) ?
 164                         -1 : 1;
 165         cmp = memcmp(ci_a->tag_actions, ci_b->tag_actions,
 166                 ci_a->tag_actions_size);
 167         if(cmp != 0)
 168                 return cmp;
 169         if(ci_a->tag_datas != ci_b->tag_datas)
 170                 return ci_a->tag_datas < ci_b->tag_datas ? -1 : 1;
 171         if(ci_a->view != ci_b->view)
 172                 return ci_a->view < ci_b->view ? -1 : 1;
 173         /* For the unbound daemon these should be non-NULL and identical,
 174          * but we check that just in case. */
 175         if(ci_a->respip_set != ci_b->respip_set)
 176                 return ci_a->respip_set < ci_b->respip_set ? -1 : 1;
 177         return 0;
 178 }
 179
 180 int
 181 mesh_state_compare(const void* ap, const void* bp)
 182 {
 183         struct mesh_state* a = (struct mesh_state*)ap;
 184         struct mesh_state* b = (struct mesh_state*)bp;
 185         int cmp;
 186
 187         if(a->unique < b->unique)
 188                 return -1;
 189         if(a->unique > b->unique)
 190                 return 1;
 191
 192         if(a->s.is_priming && !b->s.is_priming)
 193                 return -1;
 194         if(!a->s.is_priming && b->s.is_priming)
 195                 return 1;
 196
 197         if(a->s.is_valrec && !b->s.is_valrec)
 198                 return -1;
 199         if(!a->s.is_valrec && b->s.is_valrec)
 200                 return 1;
 201
 202         if((a->s.query_flags&BIT_RD) && !(b->s.query_flags&BIT_RD))
 203                 return -1;
 204         if(!(a->s.query_flags&BIT_RD) && (b->s.query_flags&BIT_RD))
 205                 return 1;
 206
 207         if((a->s.query_flags&BIT_CD) && !(b->s.query_flags&BIT_CD))
 208                 return -1;
 209         if(!(a->s.query_flags&BIT_CD) && (b->s.query_flags&BIT_CD))
 210                 return 1;
 211
 212         cmp = query_info_compare(&a->s.qinfo, &b->s.qinfo);
 213         if(cmp != 0)
 214                 return cmp;
 215         return client_info_compare(a->s.client_info, b->s.client_info);
 216 }
 217
 218 int
 219 mesh_state_ref_compare(const void* ap, const void* bp)
 220 {
 221         struct mesh_state_ref* a = (struct mesh_state_ref*)ap;
 222         struct mesh_state_ref* b = (struct mesh_state_ref*)bp;
 223         return mesh_state_compare(a->s, b->s);
 224 }
 225
 226 struct mesh_area*
 227 mesh_create(struct module_stack* stack, struct module_env* env)
 228 {
 229         struct mesh_area* mesh = calloc(1, sizeof(struct mesh_area));
 230         if(!mesh) {
 231                 log_err("mesh area alloc: out of memory");
 232                 return NULL;
 233         }
 234         mesh->histogram = timehist_setup();
 235         mesh->qbuf_bak = sldns_buffer_new(env->cfg->msg_buffer_size);
 236         if(!mesh->histogram || !mesh->qbuf_bak) {
 237                 free(mesh);
 238                 log_err("mesh area alloc: out of memory");
 239                 return NULL;
 240         }
 241         mesh->mods = *stack;
 242         mesh->env = env;
 243         rbtree_init(&mesh->run, &mesh_state_compare);
 244         rbtree_init(&mesh->all, &mesh_state_compare);
 245         mesh->num_reply_addrs = 0;
 246         mesh->num_reply_states = 0;
 247         mesh->num_detached_states = 0;
 248         mesh->num_forever_states = 0;
 249         mesh->stats_jostled = 0;
 250         mesh->stats_dropped = 0;
 251         mesh->max_reply_states = env->cfg->num_queries_per_thread;
 252         mesh->max_forever_states = (mesh->max_reply_states+1)/2;
 253 #ifndef S_SPLINT_S
 254         mesh->jostle_max.tv_sec = (time_t)(env->cfg->jostle_time / 1000);
 255         mesh->jostle_max.tv_usec = (time_t)((env->cfg->jostle_time % 1000)
 256                 *1000);
 257 #endif
 258         return mesh;
 259 }
 260
 261 /** help mesh delete delete mesh states */
 262 static void
 263 mesh_delete_helper(rbnode_type* n)
 264 {
 265         struct mesh_state* mstate = (struct mesh_state*)n->key;
 266         /* perform a full delete, not only 'cleanup' routine,
 267          * because other callbacks expect a clean state in the mesh.
 268          * For 're-entrant' calls */
 269         mesh_state_delete(&mstate->s);
 270         /* but because these delete the items from the tree, postorder
 271          * traversal and rbtree rebalancing do not work together */
 272 }
 273
 274 void
 275 mesh_delete(struct mesh_area* mesh)
 276 {
 277         if(!mesh)
 278                 return;
 279         /* free all query states */
 280         while(mesh->all.count)
 281                 mesh_delete_helper(mesh->all.root);
 282         timehist_delete(mesh->histogram);
 283         sldns_buffer_free(mesh->qbuf_bak);
 284         free(mesh);
 285 }
 286
 287 void
 288 mesh_delete_all(struct mesh_area* mesh)
 289 {
 290         /* free all query states */
 291         while(mesh->all.count)
 292                 mesh_delete_helper(mesh->all.root);
 293         mesh->stats_dropped += mesh->num_reply_addrs;
 294         /* clear mesh area references */
 295         rbtree_init(&mesh->run, &mesh_state_compare);
 296         rbtree_init(&mesh->all, &mesh_state_compare);
 297         mesh->num_reply_addrs = 0;
 298         mesh->num_reply_states = 0;
 299         mesh->num_detached_states = 0;
 300         mesh->num_forever_states = 0;
 301         mesh->forever_first = NULL;
 302         mesh->forever_last = NULL;
 303         mesh->jostle_first = NULL;
 304         mesh->jostle_last = NULL;
 305 }
 306
 307 int mesh_make_new_space(struct mesh_area* mesh, sldns_buffer* qbuf)
 308 {
 309         struct mesh_state* m = mesh->jostle_first;
 310         /* free space is available */
 311         if(mesh->num_reply_states < mesh->max_reply_states)
 312                 return 1;
 313         /* try to kick out a jostle-list item */
 314         if(m && m->reply_list && m->list_select == mesh_jostle_list) {
 315                 /* how old is it? */
 316                 struct timeval age;
 317                 timeval_subtract(&age, mesh->env->now_tv,
 318                         &m->reply_list->start_time);
 319                 if(timeval_smaller(&mesh->jostle_max, &age)) {
 320                         /* its a goner */
 321                         log_nametypeclass(VERB_ALGO, "query jostled out to "
 322                                 "make space for a new one",
 323                                 m->s.qinfo.qname, m->s.qinfo.qtype,
 324                                 m->s.qinfo.qclass);
 325                         /* backup the query */
 326                         if(qbuf) sldns_buffer_copy(mesh->qbuf_bak, qbuf);
 327                         /* notify supers */
 328                         if(m->super_set.count > 0) {
 329                                 verbose(VERB_ALGO, "notify supers of failure");
 330                                 m->s.return_msg = NULL;
 331                                 m->s.return_rcode = LDNS_RCODE_SERVFAIL;
 332                                 mesh_walk_supers(mesh, m);
 333                         }
 334                         mesh->stats_jostled ++;
 335                         mesh_state_delete(&m->s);
 336                         /* restore the query - note that the qinfo ptr to
 337                          * the querybuffer is then correct again. */
 338                         if(qbuf) sldns_buffer_copy(qbuf, mesh->qbuf_bak);
 339                         return 1;
 340                 }
 341         }
 342         /* no space for new item */
 343         return 0;
 344 }
 345
 346 void mesh_new_client(struct mesh_area* mesh, struct query_info* qinfo,
 347         struct respip_client_info* cinfo, uint16_t qflags,
 348         struct edns_data* edns, struct comm_reply* rep, uint16_t qid)
 349 {
 350         struct mesh_state* s = NULL;
 351         int unique = unique_mesh_state(edns->opt_list, mesh->env);
 352         int was_detached = 0;
 353         int was_noreply = 0;
 354         int added = 0;
 355         if(!unique)
 356                 s = mesh_area_find(mesh, cinfo, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
 357         /* does this create a new reply state? */
 358         if(!s || s->list_select == mesh_no_list) {
 359                 if(!mesh_make_new_space(mesh, rep->c->buffer)) {
 360                         verbose(VERB_ALGO, "Too many queries. dropping "
 361                                 "incoming query.");
 362                         comm_point_drop_reply(rep);
 363                         mesh->stats_dropped ++;
 364                         return;
 365                 }
 366                 /* for this new reply state, the reply address is free,
 367                  * so the limit of reply addresses does not stop reply states*/
 368         } else {
 369                 /* protect our memory usage from storing reply addresses */
 370                 if(mesh->num_reply_addrs > mesh->max_reply_states*16) {
 371                         verbose(VERB_ALGO, "Too many requests queued. "
 372                                 "dropping incoming query.");
 373                         mesh->stats_dropped++;
 374                         comm_point_drop_reply(rep);
 375                         return;
 376                 }
 377         }
 378         /* see if it already exists, if not, create one */
 379         if(!s) {
 380 #ifdef UNBOUND_DEBUG
 381                 struct rbnode_type* n;
 382 #endif
 383                 s = mesh_state_create(mesh->env, qinfo, cinfo,
 384                         qflags&(BIT_RD|BIT_CD), 0, 0);
 385                 if(!s) {
 386                         log_err("mesh_state_create: out of memory; SERVFAIL");
 387                         if(!inplace_cb_reply_servfail_call(mesh->env, qinfo, NULL, NULL,
 388                                 LDNS_RCODE_SERVFAIL, edns, mesh->env->scratch))
 389                                         edns->opt_list = NULL;
 390                         error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL,
 391                                 qinfo, qid, qflags, edns);
 392                         comm_point_send_reply(rep);
 393                         return;
 394                 }
 395                 if(unique)
 396                         mesh_state_make_unique(s);
 397                 /* copy the edns options we got from the front */
 398                 if(edns->opt_list) {
 399                         s->s.edns_opts_front_in = edns_opt_copy_region(edns->opt_list,
 400                                 s->s.region);
 401                         if(!s->s.edns_opts_front_in) {
 402                                 log_err("mesh_state_create: out of memory; SERVFAIL");
 403                                 if(!inplace_cb_reply_servfail_call(mesh->env, qinfo, NULL,
 404                                         NULL, LDNS_RCODE_SERVFAIL, edns, mesh->env->scratch))
 405                                                 edns->opt_list = NULL;
 406                                 error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL,
 407                                         qinfo, qid, qflags, edns);
 408                                 comm_point_send_reply(rep);
 409                                 return;
 410                         }
 411                 }
 412
 413 #ifdef UNBOUND_DEBUG
 414                 n =
 415 #else
 416                 (void)
 417 #endif
 418                 rbtree_insert(&mesh->all, &s->node);
 419                 log_assert(n != NULL);
 420                 /* set detached (it is now) */
 421                 mesh->num_detached_states++;
 422                 added = 1;
 423         }
 424         if(!s->reply_list && !s->cb_list && s->super_set.count == 0)
 425                 was_detached = 1;
 426         if(!s->reply_list && !s->cb_list)
 427                 was_noreply = 1;
 428         /* add reply to s */
 429         if(!mesh_state_add_reply(s, edns, rep, qid, qflags, qinfo)) {
 430                         log_err("mesh_new_client: out of memory; SERVFAIL");
 431                         if(!inplace_cb_reply_servfail_call(mesh->env, qinfo, &s->s,
 432                                 NULL, LDNS_RCODE_SERVFAIL, edns, mesh->env->scratch))
 433                                         edns->opt_list = NULL;
 434                         error_encode(rep->c->buffer, LDNS_RCODE_SERVFAIL,
 435                                 qinfo, qid, qflags, edns);
 436                         comm_point_send_reply(rep);
 437                         if(added)
 438                                 mesh_state_delete(&s->s);
 439                         return;
 440         }
 441         /* update statistics */
 442         if(was_detached) {
 443                 log_assert(mesh->num_detached_states > 0);
 444                 mesh->num_detached_states--;
 445         }
 446         if(was_noreply) {
 447                 mesh->num_reply_states ++;
 448         }
 449         mesh->num_reply_addrs++;
 450         if(s->list_select == mesh_no_list) {
 451                 /* move to either the forever or the jostle_list */
 452                 if(mesh->num_forever_states < mesh->max_forever_states) {
 453                         mesh->num_forever_states ++;
 454                         mesh_list_insert(s, &mesh->forever_first,
 455                                 &mesh->forever_last);
 456                         s->list_select = mesh_forever_list;
 457                 } else {
 458                         mesh_list_insert(s, &mesh->jostle_first,
 459                                 &mesh->jostle_last);
 460                         s->list_select = mesh_jostle_list;
 461                 }
 462         }
 463         if(added)
 464                 mesh_run(mesh, s, module_event_new, NULL);
 465 }
 466
 467 int
 468 mesh_new_callback(struct mesh_area* mesh, struct query_info* qinfo,
 469         uint16_t qflags, struct edns_data* edns, sldns_buffer* buf,
 470         uint16_t qid, mesh_cb_func_type cb, void* cb_arg)
 471 {
 472         struct mesh_state* s = NULL;
 473         int unique = unique_mesh_state(edns->opt_list, mesh->env);
 474         int was_detached = 0;
 475         int was_noreply = 0;
 476         int added = 0;
 477         if(!unique)
 478                 s = mesh_area_find(mesh, NULL, qinfo, qflags&(BIT_RD|BIT_CD), 0, 0);
 479
 480         /* there are no limits on the number of callbacks */
 481
 482         /* see if it already exists, if not, create one */
 483         if(!s) {
 484 #ifdef UNBOUND_DEBUG
 485                 struct rbnode_type* n;
 486 #endif
 487                 s = mesh_state_create(mesh->env, qinfo, NULL,
 488                         qflags&(BIT_RD|BIT_CD), 0, 0);
 489                 if(!s) {
 490                         return 0;
 491                 }
 492                 if(unique)
 493                         mesh_state_make_unique(s);
 494                 if(edns->opt_list) {
 495                         s->s.edns_opts_front_in = edns_opt_copy_region(edns->opt_list,
 496                                 s->s.region);
 497                         if(!s->s.edns_opts_front_in) {
 498                                 return 0;
 499                         }
 500                 }
 501 #ifdef UNBOUND_DEBUG
 502                 n =
 503 #else
 504                 (void)
 505 #endif
 506                 rbtree_insert(&mesh->all, &s->node);
 507                 log_assert(n != NULL);
 508                 /* set detached (it is now) */
 509                 mesh->num_detached_states++;
 510                 added = 1;
 511         }
 512         if(!s->reply_list && !s->cb_list && s->super_set.count == 0)
 513                 was_detached = 1;
 514         if(!s->reply_list && !s->cb_list)
 515                 was_noreply = 1;
 516         /* add reply to s */
 517         if(!mesh_state_add_cb(s, edns, buf, cb, cb_arg, qid, qflags)) {
 518                         if(added)
 519                                 mesh_state_delete(&s->s);
 520                         return 0;
 521         }
 522         /* update statistics */
 523         if(was_detached) {
 524                 log_assert(mesh->num_detached_states > 0);
 525                 mesh->num_detached_states--;
 526         }
 527         if(was_noreply) {
 528                 mesh->num_reply_states ++;
 529         }
 530         mesh->num_reply_addrs++;
 531         if(added)
 532                 mesh_run(mesh, s, module_event_new, NULL);
 533         return 1;
 534 }
 535
 536 void mesh_new_prefetch(struct mesh_area* mesh, struct query_info* qinfo,
 537         uint16_t qflags, time_t leeway)
 538 {
 539         struct mesh_state* s = mesh_area_find(mesh, NULL, qinfo,
 540                 qflags&(BIT_RD|BIT_CD), 0, 0);
 541 #ifdef UNBOUND_DEBUG
 542         struct rbnode_type* n;
 543 #endif
 544         /* already exists, and for a different purpose perhaps.
 545          * if mesh_no_list, keep it that way. */
 546         if(s) {
 547                 /* make it ignore the cache from now on */
 548                 if(!s->s.blacklist)
 549                         sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region);
 550                 if(s->s.prefetch_leeway < leeway)
 551                         s->s.prefetch_leeway = leeway;
 552                 return;
 553         }
 554         if(!mesh_make_new_space(mesh, NULL)) {
 555                 verbose(VERB_ALGO, "Too many queries. dropped prefetch.");
 556                 mesh->stats_dropped ++;
 557                 return;
 558         }
 559
 560         s = mesh_state_create(mesh->env, qinfo, NULL,
 561                 qflags&(BIT_RD|BIT_CD), 0, 0);
 562         if(!s) {
 563                 log_err("prefetch mesh_state_create: out of memory");
 564                 return;
 565         }
 566 #ifdef UNBOUND_DEBUG
 567         n =
 568 #else
 569         (void)
 570 #endif
 571         rbtree_insert(&mesh->all, &s->node);
 572         log_assert(n != NULL);
 573         /* set detached (it is now) */
 574         mesh->num_detached_states++;
 575         /* make it ignore the cache */
 576         sock_list_insert(&s->s.blacklist, NULL, 0, s->s.region);
 577         s->s.prefetch_leeway = leeway;
 578
 579         if(s->list_select == mesh_no_list) {
 580                 /* move to either the forever or the jostle_list */
 581                 if(mesh->num_forever_states < mesh->max_forever_states) {
 582                         mesh->num_forever_states ++;
 583                         mesh_list_insert(s, &mesh->forever_first,
 584                                 &mesh->forever_last);
 585                         s->list_select = mesh_forever_list;
 586                 } else {
 587                         mesh_list_insert(s, &mesh->jostle_first,
 588                                 &mesh->jostle_last);
 589                         s->list_select = mesh_jostle_list;
 590                 }
 591         }
 592         mesh_run(mesh, s, module_event_new, NULL);
 593 }
 594
 595 void mesh_report_reply(struct mesh_area* mesh, struct outbound_entry* e,
 596         struct comm_reply* reply, int what)
 597 {
 598         enum module_ev event = module_event_reply;
 599         e->qstate->reply = reply;
 600         if(what != NETEVENT_NOERROR) {
 601                 event = module_event_noreply;
 602                 if(what == NETEVENT_CAPSFAIL)
 603                         event = module_event_capsfail;
 604         }
 605         mesh_run(mesh, e->qstate->mesh_info, event, e);
 606 }
 607
 608 struct mesh_state*
 609 mesh_state_create(struct module_env* env, struct query_info* qinfo,
 610         struct respip_client_info* cinfo, uint16_t qflags, int prime,
 611         int valrec)
 612 {
 613         struct regional* region = alloc_reg_obtain(env->alloc);
 614         struct mesh_state* mstate;
 615         int i;
 616         if(!region)
 617                 return NULL;
 618         mstate = (struct mesh_state*)regional_alloc(region,
 619                 sizeof(struct mesh_state));
 620         if(!mstate) {
 621                 alloc_reg_release(env->alloc, region);
 622                 return NULL;
 623         }
 624         memset(mstate, 0, sizeof(*mstate));
 625         mstate->node = *RBTREE_NULL;
 626         mstate->run_node = *RBTREE_NULL;
 627         mstate->node.key = mstate;
 628         mstate->run_node.key = mstate;
 629         mstate->reply_list = NULL;
 630         mstate->list_select = mesh_no_list;
 631         mstate->replies_sent = 0;
 632         rbtree_init(&mstate->super_set, &mesh_state_ref_compare);
 633         rbtree_init(&mstate->sub_set, &mesh_state_ref_compare);
 634         mstate->num_activated = 0;
 635         mstate->unique = NULL;
 636         /* init module qstate */
 637         mstate->s.qinfo.qtype = qinfo->qtype;
 638         mstate->s.qinfo.qclass = qinfo->qclass;
 639         mstate->s.qinfo.local_alias = NULL;
 640         mstate->s.qinfo.qname_len = qinfo->qname_len;
 641         mstate->s.qinfo.qname = regional_alloc_init(region, qinfo->qname,
 642                 qinfo->qname_len);
 643         if(!mstate->s.qinfo.qname) {
 644                 alloc_reg_release(env->alloc, region);
 645                 return NULL;
 646         }
 647         if(cinfo) {
 648                 mstate->s.client_info = regional_alloc_init(region, cinfo,
 649                         sizeof(*cinfo));
 650                 if(!mstate->s.client_info) {
 651                         alloc_reg_release(env->alloc, region);
 652                         return NULL;
 653                 }
 654         }
 655         /* remove all weird bits from qflags */
 656         mstate->s.query_flags = (qflags & (BIT_RD|BIT_CD));
 657         mstate->s.is_priming = prime;
 658         mstate->s.is_valrec = valrec;
 659         mstate->s.reply = NULL;
 660         mstate->s.region = region;
 661         mstate->s.curmod = 0;
 662         mstate->s.return_msg = 0;
 663         mstate->s.return_rcode = LDNS_RCODE_NOERROR;
 664         mstate->s.env = env;
 665         mstate->s.mesh_info = mstate;
 666         mstate->s.prefetch_leeway = 0;
 667         mstate->s.no_cache_lookup = 0;
 668         mstate->s.no_cache_store = 0;
 669         /* init modules */
 670         for(i=0; i<env->mesh->mods.num; i++) {
 671                 mstate->s.minfo[i] = NULL;
 672                 mstate->s.ext_state[i] = module_state_initial;
 673         }
 674         /* init edns option lists */
 675         mstate->s.edns_opts_front_in = NULL;
 676         mstate->s.edns_opts_back_out = NULL;
 677         mstate->s.edns_opts_back_in = NULL;
 678         mstate->s.edns_opts_front_out = NULL;
 679
 680         return mstate;
 681 }
 682
 683 int
 684 mesh_state_is_unique(struct mesh_state* mstate)
 685 {
 686         return mstate->unique != NULL;
 687 }
 688
 689 void
 690 mesh_state_make_unique(struct mesh_state* mstate)
 691 {
 692         mstate->unique = mstate;
 693 }
 694
 695 void
 696 mesh_state_cleanup(struct mesh_state* mstate)
 697 {
 698         struct mesh_area* mesh;
 699         int i;
 700         if(!mstate)
 701                 return;
 702         mesh = mstate->s.env->mesh;
 703         /* drop unsent replies */
 704         if(!mstate->replies_sent) {
 705                 struct mesh_reply* rep;
 706                 struct mesh_cb* cb;
 707                 for(rep=mstate->reply_list; rep; rep=rep->next) {
 708                         comm_point_drop_reply(&rep->query_reply);
 709                         mesh->num_reply_addrs--;
 710                 }
 711                 for(cb=mstate->cb_list; cb; cb=cb->next) {
 712                         fptr_ok(fptr_whitelist_mesh_cb(cb->cb));
 713                         (*cb->cb)(cb->cb_arg, LDNS_RCODE_SERVFAIL, NULL,
 714                                 sec_status_unchecked, NULL);
 715                         mesh->num_reply_addrs--;
 716                 }
 717         }
 718
 719         /* de-init modules */
 720         for(i=0; i<mesh->mods.num; i++) {
 721                 fptr_ok(fptr_whitelist_mod_clear(mesh->mods.mod[i]->clear));
 722                 (*mesh->mods.mod[i]->clear)(&mstate->s, i);
 723                 mstate->s.minfo[i] = NULL;
 724                 mstate->s.ext_state[i] = module_finished;
 725         }
 726         alloc_reg_release(mstate->s.env->alloc, mstate->s.region);
 727 }
 728
 729 void
 730 mesh_state_delete(struct module_qstate* qstate)
 731 {
 732         struct mesh_area* mesh;
 733         struct mesh_state_ref* super, ref;
 734         struct mesh_state* mstate;
 735         if(!qstate)
 736                 return;
 737         mstate = qstate->mesh_info;
 738         mesh = mstate->s.env->mesh;
 739         mesh_detach_subs(&mstate->s);
 740         if(mstate->list_select == mesh_forever_list) {
 741                 mesh->num_forever_states --;
 742                 mesh_list_remove(mstate, &mesh->forever_first,
 743                         &mesh->forever_last);
 744         } else if(mstate->list_select == mesh_jostle_list) {
 745                 mesh_list_remove(mstate, &mesh->jostle_first,
 746                         &mesh->jostle_last);
 747         }
 748         if(!mstate->reply_list && !mstate->cb_list
 749                 && mstate->super_set.count == 0) {
 750                 log_assert(mesh->num_detached_states > 0);
 751                 mesh->num_detached_states--;
 752         }
 753         if(mstate->reply_list || mstate->cb_list) {
 754                 log_assert(mesh->num_reply_states > 0);
 755                 mesh->num_reply_states--;
 756         }
 757         ref.node.key = &ref;
 758         ref.s = mstate;
 759         RBTREE_FOR(super, struct mesh_state_ref*, &mstate->super_set) {
 760                 (void)rbtree_delete(&super->s->sub_set, &ref);
 761         }
 762         (void)rbtree_delete(&mesh->run, mstate);
 763         (void)rbtree_delete(&mesh->all, mstate);
 764         mesh_state_cleanup(mstate);
 765 }
 766
 767 /** helper recursive rbtree find routine */
 768 static int
 769 find_in_subsub(struct mesh_state* m, struct mesh_state* tofind, size_t *c)
 770 {
 771         struct mesh_state_ref* r;
 772         if((*c)++ > MESH_MAX_SUBSUB)
 773                 return 1;
 774         RBTREE_FOR(r, struct mesh_state_ref*, &m->sub_set) {
 775                 if(r->s == tofind || find_in_subsub(r->s, tofind, c))
 776                         return 1;
 777         }
 778         return 0;
 779 }
 780
 781 /** find cycle for already looked up mesh_state */
 782 static int
 783 mesh_detect_cycle_found(struct module_qstate* qstate, struct mesh_state* dep_m)
 784 {
 785         struct mesh_state* cyc_m = qstate->mesh_info;
 786         size_t counter = 0;
 787         if(!dep_m)
 788                 return 0;
 789         if(dep_m == cyc_m || find_in_subsub(dep_m, cyc_m, &counter)) {
 790                 if(counter > MESH_MAX_SUBSUB)
 791                         return 2;
 792                 return 1;
 793         }
 794         return 0;
 795 }
 796
 797 void mesh_detach_subs(struct module_qstate* qstate)
 798 {
 799         struct mesh_area* mesh = qstate->env->mesh;
 800         struct mesh_state_ref* ref, lookup;
 801 #ifdef UNBOUND_DEBUG
 802         struct rbnode_type* n;
 803 #endif
 804         lookup.node.key = &lookup;
 805         lookup.s = qstate->mesh_info;
 806         RBTREE_FOR(ref, struct mesh_state_ref*, &qstate->mesh_info->sub_set) {
 807 #ifdef UNBOUND_DEBUG
 808                 n =
 809 #else
 810                 (void)
 811 #endif
 812                 rbtree_delete(&ref->s->super_set, &lookup);
 813                 log_assert(n != NULL); /* must have been present */
 814                 if(!ref->s->reply_list && !ref->s->cb_list
 815                         && ref->s->super_set.count == 0) {
 816                         mesh->num_detached_states++;
 817                         log_assert(mesh->num_detached_states +
 818                                 mesh->num_reply_states <= mesh->all.count);
 819                 }
 820         }
 821         rbtree_init(&qstate->mesh_info->sub_set, &mesh_state_ref_compare);
 822 }
 823
 824 int mesh_add_sub(struct module_qstate* qstate, struct query_info* qinfo,
 825         uint16_t qflags, int prime, int valrec, struct module_qstate** newq,
 826         struct mesh_state** sub)
 827 {
 828         /* find it, if not, create it */
 829         struct mesh_area* mesh = qstate->env->mesh;
 830         *sub = mesh_area_find(mesh, NULL, qinfo, qflags,
 831                 prime, valrec);
 832         if(mesh_detect_cycle_found(qstate, *sub)) {
 833                 verbose(VERB_ALGO, "attach failed, cycle detected");
 834                 return 0;
 835         }
 836         if(!*sub) {
 837 #ifdef UNBOUND_DEBUG
 838                 struct rbnode_type* n;
 839 #endif
 840                 /* create a new one */
 841                 *sub = mesh_state_create(qstate->env, qinfo, NULL, qflags, prime,
 842                         valrec);
 843                 if(!*sub) {
 844                         log_err("mesh_attach_sub: out of memory");
 845                         return 0;
 846                 }
 847 #ifdef UNBOUND_DEBUG
 848                 n =
 849 #else
 850                 (void)
 851 #endif
 852                 rbtree_insert(&mesh->all, &(*sub)->node);
 853                 log_assert(n != NULL);
 854                 /* set detached (it is now) */
 855                 mesh->num_detached_states++;
 856                 /* set new query state to run */
 857 #ifdef UNBOUND_DEBUG
 858                 n =
 859 #else
 860                 (void)
 861 #endif
 862                 rbtree_insert(&mesh->run, &(*sub)->run_node);
 863                 log_assert(n != NULL);
 864                 *newq = &(*sub)->s;
 865         } else
 866                 *newq = NULL;
 867         return 1;
 868 }
 869
 870 int mesh_attach_sub(struct module_qstate* qstate, struct query_info* qinfo,
 871         uint16_t qflags, int prime, int valrec, struct module_qstate** newq)
 872 {
 873         struct mesh_area* mesh = qstate->env->mesh;
 874         struct mesh_state* sub = NULL;
 875         int was_detached;
 876         if(!mesh_add_sub(qstate, qinfo, qflags, prime, valrec, newq, &sub))
 877                 return 0;
 878         was_detached = (sub->super_set.count == 0);
 879         if(!mesh_state_attachment(qstate->mesh_info, sub))
 880                 return 0;
 881         /* if it was a duplicate  attachment, the count was not zero before */
 882         if(!sub->reply_list && !sub->cb_list && was_detached &&
 883                 sub->super_set.count == 1) {
 884                 /* it used to be detached, before this one got added */
 885                 log_assert(mesh->num_detached_states > 0);
 886                 mesh->num_detached_states--;
 887         }
 888         /* *newq will be run when inited after the current module stops */
 889         return 1;
 890 }
 891
 892 int mesh_state_attachment(struct mesh_state* super, struct mesh_state* sub)
 893 {
 894 #ifdef UNBOUND_DEBUG
 895         struct rbnode_type* n;
 896 #endif
 897         struct mesh_state_ref* subref; /* points to sub, inserted in super */
 898         struct mesh_state_ref* superref; /* points to super, inserted in sub */
 899         if( !(subref = regional_alloc(super->s.region,
 900                 sizeof(struct mesh_state_ref))) ||
 901                 !(superref = regional_alloc(sub->s.region,
 902                 sizeof(struct mesh_state_ref))) ) {
 903                 log_err("mesh_state_attachment: out of memory");
 904                 return 0;
 905         }
 906         superref->node.key = superref;
 907         superref->s = super;
 908         subref->node.key = subref;
 909         subref->s = sub;
 910         if(!rbtree_insert(&sub->super_set, &superref->node)) {
 911                 /* this should not happen, iterator and validator do not
 912                  * attach subqueries that are identical. */
 913                 /* already attached, we are done, nothing todo.
 914                  * since superref and subref already allocated in region,
 915                  * we cannot free them */
 916                 return 1;
 917         }
 918 #ifdef UNBOUND_DEBUG
 919         n =
 920 #else
 921         (void)
 922 #endif
 923         rbtree_insert(&super->sub_set, &subref->node);
 924         log_assert(n != NULL); /* we checked above if statement, the reverse
 925           administration should not fail now, unless they are out of sync */
 926         return 1;
 927 }
 928
 929 /**
 930  * callback results to mesh cb entry
 931  * @param m: mesh state to send it for.
 932  * @param rcode: if not 0, error code.
 933  * @param rep: reply to send (or NULL if rcode is set).
 934  * @param r: callback entry
 935  */
 936 static void
 937 mesh_do_callback(struct mesh_state* m, int rcode, struct reply_info* rep,
 938         struct mesh_cb* r)
 939 {
 940         int secure;
 941         char* reason = NULL;
 942         /* bogus messages are not made into servfail, sec_status passed
 943          * to the callback function */
 944         if(rep && rep->security == sec_status_secure)
 945                 secure = 1;
 946         else    secure = 0;
 947         if(!rep && rcode == LDNS_RCODE_NOERROR)
 948                 rcode = LDNS_RCODE_SERVFAIL;
 949         if(!rcode && rep->security == sec_status_bogus) {
 950                 if(!(reason = errinf_to_str(&m->s)))
 951                         rcode = LDNS_RCODE_SERVFAIL;
 952         }
 953         /* send the reply */
 954         if(rcode) {
 955                 if(rcode == LDNS_RCODE_SERVFAIL) {
 956                         if(!inplace_cb_reply_servfail_call(m->s.env, &m->s.qinfo, &m->s,
 957                                 rep, rcode, &r->edns, m->s.region))
 958                                         r->edns.opt_list = NULL;
 959                 } else {
 960                         if(!inplace_cb_reply_call(m->s.env, &m->s.qinfo, &m->s, rep, rcode,
 961                                 &r->edns, m->s.region))
 962                                         r->edns.opt_list = NULL;
 963                 }
 964                 fptr_ok(fptr_whitelist_mesh_cb(r->cb));
 965                 (*r->cb)(r->cb_arg, rcode, r->buf, sec_status_unchecked, NULL);
 966         } else {
 967                 size_t udp_size = r->edns.udp_size;
 968                 sldns_buffer_clear(r->buf);
 969                 r->edns.edns_version = EDNS_ADVERTISED_VERSION;
 970                 r->edns.udp_size = EDNS_ADVERTISED_SIZE;
 971                 r->edns.ext_rcode = 0;
 972                 r->edns.bits &= EDNS_DO;
 973
 974                 if(!inplace_cb_reply_call(m->s.env, &m->s.qinfo, &m->s, rep,
 975                         LDNS_RCODE_NOERROR, &r->edns, m->s.region) ||
 976                         !reply_info_answer_encode(&m->s.qinfo, rep, r->qid,
 977                         r->qflags, r->buf, 0, 1,
 978                         m->s.env->scratch, udp_size, &r->edns,
 979                         (int)(r->edns.bits & EDNS_DO), secure))
 980                 {
 981                         fptr_ok(fptr_whitelist_mesh_cb(r->cb));
 982                         (*r->cb)(r->cb_arg, LDNS_RCODE_SERVFAIL, r->buf,
 983                                 sec_status_unchecked, NULL);
 984                 } else {
 985                         fptr_ok(fptr_whitelist_mesh_cb(r->cb));
 986                         (*r->cb)(r->cb_arg, LDNS_RCODE_NOERROR, r->buf,
 987                                 rep->security, reason);
 988                 }
 989         }
 990         free(reason);
 991         m->s.env->mesh->num_reply_addrs--;
 992 }
 993
 994 /**
 995  * Send reply to mesh reply entry
 996  * @param m: mesh state to send it for.
 997  * @param rcode: if not 0, error code.
 998  * @param rep: reply to send (or NULL if rcode is set).
 999  * @param r: reply entry
1000  * @param prev: previous reply, already has its answer encoded in buffer.
1001  */
1002 static void
1003 mesh_send_reply(struct mesh_state* m, int rcode, struct reply_info* rep,
1004         struct mesh_reply* r, struct mesh_reply* prev)
1005 {
1006         struct timeval end_time;
1007         struct timeval duration;
1008         int secure;
1009         /* Copy the client's EDNS for later restore, to make sure the edns
1010          * compare is with the correct edns options. */
1011         struct edns_data edns_bak = r->edns;
1012         /* examine security status */
1013         if(m->s.env->need_to_validate && (!(r->qflags&BIT_CD) ||
1014                 m->s.env->cfg->ignore_cd) && rep &&
1015                 rep->security <= sec_status_bogus) {
1016                 rcode = LDNS_RCODE_SERVFAIL;
1017                 if(m->s.env->cfg->stat_extended)
1018                         m->s.env->mesh->ans_bogus++;
1019         }
1020         if(rep && rep->security == sec_status_secure)
1021                 secure = 1;
1022         else    secure = 0;
1023         if(!rep && rcode == LDNS_RCODE_NOERROR)
1024                 rcode = LDNS_RCODE_SERVFAIL;
1025         /* send the reply */
1026         /* We don't reuse the encoded answer if either the previous or current
1027          * response has a local alias.  We could compare the alias records
1028          * and still reuse the previous answer if they are the same, but that
1029          * would be complicated and error prone for the relatively minor case.
1030          * So we err on the side of safety. */
1031         if(prev && prev->qflags == r->qflags &&
1032                 !prev->local_alias && !r->local_alias &&
1033                 prev->edns.edns_present == r->edns.edns_present &&
1034                 prev->edns.bits == r->edns.bits &&
1035                 prev->edns.udp_size == r->edns.udp_size &&
1036                 edns_opt_list_compare(prev->edns.opt_list, r->edns.opt_list)
1037                 == 0) {
1038                 /* if the previous reply is identical to this one, fix ID */
1039                 if(prev->query_reply.c->buffer != r->query_reply.c->buffer)
1040                         sldns_buffer_copy(r->query_reply.c->buffer,
1041                                 prev->query_reply.c->buffer);
1042                 sldns_buffer_write_at(r->query_reply.c->buffer, 0,
1043                         &r->qid, sizeof(uint16_t));
1044                 sldns_buffer_write_at(r->query_reply.c->buffer, 12,
1045                         r->qname, m->s.qinfo.qname_len);
1046                 comm_point_send_reply(&r->query_reply);
1047         } else if(rcode) {
1048                 m->s.qinfo.qname = r->qname;
1049                 m->s.qinfo.local_alias = r->local_alias;
1050                 if(rcode == LDNS_RCODE_SERVFAIL) {
1051                         if(!inplace_cb_reply_servfail_call(m->s.env, &m->s.qinfo, &m->s,
1052                                 rep, rcode, &r->edns, m->s.region))
1053                                         r->edns.opt_list = NULL;
1054                 } else {
1055                         if(!inplace_cb_reply_call(m->s.env, &m->s.qinfo, &m->s, rep, rcode,
1056                                 &r->edns, m->s.region))
1057                                         r->edns.opt_list = NULL;
1058                 }
1059                 error_encode(r->query_reply.c->buffer, rcode, &m->s.qinfo,
1060                         r->qid, r->qflags, &r->edns);
1061                 comm_point_send_reply(&r->query_reply);
1062         } else {
1063                 size_t udp_size = r->edns.udp_size;
1064                 r->edns.edns_version = EDNS_ADVERTISED_VERSION;
1065                 r->edns.udp_size = EDNS_ADVERTISED_SIZE;
1066                 r->edns.ext_rcode = 0;
1067                 r->edns.bits &= EDNS_DO;
1068                 m->s.qinfo.qname = r->qname;
1069                 m->s.qinfo.local_alias = r->local_alias;
1070                 if(!inplace_cb_reply_call(m->s.env, &m->s.qinfo, &m->s, rep,
1071                         LDNS_RCODE_NOERROR, &r->edns, m->s.region) ||
1072                         !reply_info_answer_encode(&m->s.qinfo, rep, r->qid,
1073                         r->qflags, r->query_reply.c->buffer, 0, 1,
1074                         m->s.env->scratch, udp_size, &r->edns,
1075                         (int)(r->edns.bits & EDNS_DO), secure))
1076                 {
1077                         if(!inplace_cb_reply_servfail_call(m->s.env, &m->s.qinfo, &m->s,
1078                         rep, LDNS_RCODE_SERVFAIL, &r->edns, m->s.region))
1079                                 r->edns.opt_list = NULL;
1080                         error_encode(r->query_reply.c->buffer,
1081                                 LDNS_RCODE_SERVFAIL, &m->s.qinfo, r->qid,
1082                                 r->qflags, &r->edns);
1083                 }
1084                 r->edns = edns_bak;
1085                 comm_point_send_reply(&r->query_reply);
1086         }
1087         /* account */
1088         m->s.env->mesh->num_reply_addrs--;
1089         end_time = *m->s.env->now_tv;
1090         timeval_subtract(&duration, &end_time, &r->start_time);
1091         verbose(VERB_ALGO, "query took " ARG_LL "d.%6.6d sec",
1092                 (long long)duration.tv_sec, (int)duration.tv_usec);
1093         m->s.env->mesh->replies_sent++;
1094         timeval_add(&m->s.env->mesh->replies_sum_wait, &duration);
1095         timehist_insert(m->s.env->mesh->histogram, &duration);
1096         if(m->s.env->cfg->stat_extended) {
1097                 uint16_t rc = FLAGS_GET_RCODE(sldns_buffer_read_u16_at(r->
1098                         query_reply.c->buffer, 2));
1099                 if(secure) m->s.env->mesh->ans_secure++;
1100                 m->s.env->mesh->ans_rcode[ rc ] ++;
1101                 if(rc == 0 && LDNS_ANCOUNT(sldns_buffer_begin(r->
1102                         query_reply.c->buffer)) == 0)
1103                         m->s.env->mesh->ans_nodata++;
1104         }
1105         /* Log reply sent */
1106         if(m->s.env->cfg->log_replies) {
1107                 log_reply_info(0, &m->s.qinfo, &r->query_reply.addr,
1108                         r->query_reply.addrlen, duration, 0,
1109                         r->query_reply.c->buffer);
1110         }
1111 }
1112
1113 void mesh_query_done(struct mesh_state* mstate)
1114 {
1115         struct mesh_reply* r;
1116         struct mesh_reply* prev = NULL;
1117         struct mesh_cb* c;
1118         struct reply_info* rep = (mstate->s.return_msg?
1119                 mstate->s.return_msg->rep:NULL);
1120         for(r = mstate->reply_list; r; r = r->next) {
1121                 /* if a response-ip address block has been stored the
1122                  *  information should be logged for each client. */
1123                 if(mstate->s.respip_action_info &&
1124                         mstate->s.respip_action_info->addrinfo) {
1125                         respip_inform_print(mstate->s.respip_action_info->addrinfo,
1126                                 r->qname, mstate->s.qinfo.qtype,
1127                                 mstate->s.qinfo.qclass, r->local_alias,
1128                                 &r->query_reply);
1129                 }
1130
1131                 /* if this query is determined to be dropped during the
1132                  * mesh processing, this is the point to take that action. */
1133                 if(mstate->s.is_drop)
1134                         comm_point_drop_reply(&r->query_reply);
1135                 else {
1136                         mesh_send_reply(mstate, mstate->s.return_rcode, rep,
1137                                 r, prev);
1138                         prev = r;
1139                 }
1140         }
1141         mstate->replies_sent = 1;
1142         for(c = mstate->cb_list; c; c = c->next) {
1143                 mesh_do_callback(mstate, mstate->s.return_rcode, rep, c);
1144         }
1145 }
1146
1147 void mesh_walk_supers(struct mesh_area* mesh, struct mesh_state* mstate)
1148 {
1149         struct mesh_state_ref* ref;
1150         RBTREE_FOR(ref, struct mesh_state_ref*, &mstate->super_set)
1151         {
1152                 /* make super runnable */
1153                 (void)rbtree_insert(&mesh->run, &ref->s->run_node);
1154                 /* callback the function to inform super of result */
1155                 fptr_ok(fptr_whitelist_mod_inform_super(
1156                         mesh->mods.mod[ref->s->s.curmod]->inform_super));
1157                 (*mesh->mods.mod[ref->s->s.curmod]->inform_super)(&mstate->s,
1158                         ref->s->s.curmod, &ref->s->s);
1159         }
1160 }
1161
1162 struct mesh_state* mesh_area_find(struct mesh_area* mesh,
1163         struct respip_client_info* cinfo, struct query_info* qinfo,
1164         uint16_t qflags, int prime, int valrec)
1165 {
1166         struct mesh_state key;
1167         struct mesh_state* result;
1168
1169         key.node.key = &key;
1170         key.s.is_priming = prime;
1171         key.s.is_valrec = valrec;
1172         key.s.qinfo = *qinfo;
1173         key.s.query_flags = qflags;
1174         /* We are searching for a similar mesh state when we DO want to
1175          * aggregate the state. Thus unique is set to NULL. (default when we
1176          * desire aggregation).*/
1177         key.unique = NULL;
1178         key.s.client_info = cinfo;
1179
1180         result = (struct mesh_state*)rbtree_search(&mesh->all, &key);
1181         return result;
1182 }
1183
1184 int mesh_state_add_cb(struct mesh_state* s, struct edns_data* edns,
1185         sldns_buffer* buf, mesh_cb_func_type cb, void* cb_arg,
1186         uint16_t qid, uint16_t qflags)
1187 {
1188         struct mesh_cb* r = regional_alloc(s->s.region,
1189                 sizeof(struct mesh_cb));
1190         if(!r)
1191                 return 0;
1192         r->buf = buf;
1193         log_assert(fptr_whitelist_mesh_cb(cb)); /* early failure ifmissing*/
1194         r->cb = cb;
1195         r->cb_arg = cb_arg;
1196         r->edns = *edns;
1197         if(edns->opt_list) {
1198                 r->edns.opt_list = edns_opt_copy_region(edns->opt_list,
1199                         s->s.region);
1200                 if(!r->edns.opt_list)
1201                         return 0;
1202         }
1203         r->qid = qid;
1204         r->qflags = qflags;
1205         r->next = s->cb_list;
1206         s->cb_list = r;
1207         return 1;
1208
1209 }
1210
1211 int mesh_state_add_reply(struct mesh_state* s, struct edns_data* edns,
1212         struct comm_reply* rep, uint16_t qid, uint16_t qflags,
1213         const struct query_info* qinfo)
1214 {
1215         struct mesh_reply* r = regional_alloc(s->s.region,
1216                 sizeof(struct mesh_reply));
1217         if(!r)
1218                 return 0;
1219         r->query_reply = *rep;
1220         r->edns = *edns;
1221         if(edns->opt_list) {
1222                 r->edns.opt_list = edns_opt_copy_region(edns->opt_list,
1223                         s->s.region);
1224                 if(!r->edns.opt_list)
1225                         return 0;
1226         }
1227         r->qid = qid;
1228         r->qflags = qflags;
1229         r->start_time = *s->s.env->now_tv;
1230         r->next = s->reply_list;
1231         r->qname = regional_alloc_init(s->s.region, qinfo->qname,
1232                 s->s.qinfo.qname_len);
1233         if(!r->qname)
1234                 return 0;
1235
1236         /* Data related to local alias stored in 'qinfo' (if any) is ephemeral
1237          * and can be different for different original queries (even if the
1238          * replaced query name is the same).  So we need to make a deep copy
1239          * and store the copy for each reply info. */
1240         if(qinfo->local_alias) {
1241                 struct packed_rrset_data* d;
1242                 struct packed_rrset_data* dsrc;
1243                 r->local_alias = regional_alloc_zero(s->s.region,
1244                         sizeof(*qinfo->local_alias));
1245                 if(!r->local_alias)
1246                         return 0;
1247                 r->local_alias->rrset = regional_alloc_init(s->s.region,
1248                         qinfo->local_alias->rrset,
1249                         sizeof(*qinfo->local_alias->rrset));
1250                 if(!r->local_alias->rrset)
1251                         return 0;
1252                 dsrc = qinfo->local_alias->rrset->entry.data;
1253
1254                 /* In the current implementation, a local alias must be
1255                  * a single CNAME RR (see worker_handle_request()). */
1256                 log_assert(!qinfo->local_alias->next && dsrc->count == 1 &&
1257                         qinfo->local_alias->rrset->rk.type ==
1258                         htons(LDNS_RR_TYPE_CNAME));
1259                 /* Technically, we should make a local copy for the owner
1260                  * name of the RRset, but in the case of the first (and
1261                  * currently only) local alias RRset, the owner name should
1262                  * point to the qname of the corresponding query, which should
1263                  * be valid throughout the lifetime of this mesh_reply.  So
1264                  * we can skip copying. */
1265                 log_assert(qinfo->local_alias->rrset->rk.dname ==
1266                         sldns_buffer_at(rep->c->buffer, LDNS_HEADER_SIZE));
1267
1268                 d = regional_alloc_init(s->s.region, dsrc,
1269                         sizeof(struct packed_rrset_data)
1270                         + sizeof(size_t) + sizeof(uint8_t*) + sizeof(time_t));
1271                 if(!d)
1272                         return 0;
1273                 r->local_alias->rrset->entry.data = d;
1274                 d->rr_len = (size_t*)((uint8_t*)d +
1275                         sizeof(struct packed_rrset_data));
1276                 d->rr_data = (uint8_t**)&(d->rr_len[1]);
1277                 d->rr_ttl = (time_t*)&(d->rr_data[1]);
1278                 d->rr_len[0] = dsrc->rr_len[0];
1279                 d->rr_ttl[0] = dsrc->rr_ttl[0];
1280                 d->rr_data[0] = regional_alloc_init(s->s.region,
1281                         dsrc->rr_data[0], d->rr_len[0]);
1282                 if(!d->rr_data[0])
1283                         return 0;
1284         } else
1285                 r->local_alias = NULL;
1286
1287         s->reply_list = r;
1288         return 1;
1289 }
1290
1291 /**
1292  * Continue processing the mesh state at another module.
1293  * Handles module to modules tranfer of control.
1294  * Handles module finished.
1295  * @param mesh: the mesh area.
1296  * @param mstate: currently active mesh state.
1297  *      Deleted if finished, calls _done and _supers to
1298  *      send replies to clients and inform other mesh states.
1299  *      This in turn may create additional runnable mesh states.
1300  * @param s: state at which the current module exited.
1301  * @param ev: the event sent to the module.
1302  *      returned is the event to send to the next module.
1303  * @return true if continue processing at the new module.
1304  *      false if not continued processing is needed.
1305  */
1306 static int
1307 mesh_continue(struct mesh_area* mesh, struct mesh_state* mstate,
1308         enum module_ext_state s, enum module_ev* ev)
1309 {
1310         mstate->num_activated++;
1311         if(mstate->num_activated > MESH_MAX_ACTIVATION) {
1312                 /* module is looping. Stop it. */
1313                 log_err("internal error: looping module stopped");
1314                 log_query_info(VERB_QUERY, "pass error for qstate",
1315                         &mstate->s.qinfo);
1316                 s = module_error;
1317         }
1318         if(s == module_wait_module || s == module_restart_next) {
1319                 /* start next module */
1320                 mstate->s.curmod++;
1321                 if(mesh->mods.num == mstate->s.curmod) {
1322                         log_err("Cannot pass to next module; at last module");
1323                         log_query_info(VERB_QUERY, "pass error for qstate",
1324                                 &mstate->s.qinfo);
1325                         mstate->s.curmod--;
1326                         return mesh_continue(mesh, mstate, module_error, ev);
1327                 }
1328                 if(s == module_restart_next) {
1329                         int curmod = mstate->s.curmod;
1330                         for(; mstate->s.curmod < mesh->mods.num;
1331                                 mstate->s.curmod++) {
1332                                 fptr_ok(fptr_whitelist_mod_clear(
1333                                         mesh->mods.mod[mstate->s.curmod]->clear));
1334                                 (*mesh->mods.mod[mstate->s.curmod]->clear)
1335                                         (&mstate->s, mstate->s.curmod);
1336                                 mstate->s.minfo[mstate->s.curmod] = NULL;
1337                         }
1338                         mstate->s.curmod = curmod;
1339                 }
1340                 *ev = module_event_pass;
1341                 return 1;
1342         }
1343         if(s == module_wait_subquery && mstate->sub_set.count == 0) {
1344                 log_err("module cannot wait for subquery, subquery list empty");
1345                 log_query_info(VERB_QUERY, "pass error for qstate",
1346                         &mstate->s.qinfo);
1347                 s = module_error;
1348         }
1349         if(s == module_error && mstate->s.return_rcode == LDNS_RCODE_NOERROR) {
1350                 /* error is bad, handle pass back up below */
1351                 mstate->s.return_rcode = LDNS_RCODE_SERVFAIL;
1352         }
1353         if(s == module_error || s == module_finished) {
1354                 if(mstate->s.curmod == 0) {
1355                         mesh_query_done(mstate);
1356                         mesh_walk_supers(mesh, mstate);
1357                         mesh_state_delete(&mstate->s);
1358                         return 0;
1359                 }
1360                 /* pass along the locus of control */
1361                 mstate->s.curmod --;
1362                 *ev = module_event_moddone;
1363                 return 1;
1364         }
1365         return 0;
1366 }
1367
1368 void mesh_run(struct mesh_area* mesh, struct mesh_state* mstate,
1369         enum module_ev ev, struct outbound_entry* e)
1370 {
1371         enum module_ext_state s;
1372         verbose(VERB_ALGO, "mesh_run: start");
1373         while(mstate) {
1374                 /* run the module */
1375                 fptr_ok(fptr_whitelist_mod_operate(
1376                         mesh->mods.mod[mstate->s.curmod]->operate));
1377                 (*mesh->mods.mod[mstate->s.curmod]->operate)
1378                         (&mstate->s, ev, mstate->s.curmod, e);
1379
1380                 /* examine results */
1381                 mstate->s.reply = NULL;
1382                 regional_free_all(mstate->s.env->scratch);
1383                 s = mstate->s.ext_state[mstate->s.curmod];
1384                 verbose(VERB_ALGO, "mesh_run: %s module exit state is %s",
1385                         mesh->mods.mod[mstate->s.curmod]->name, strextstate(s));
1386                 e = NULL;
1387                 if(mesh_continue(mesh, mstate, s, &ev))
1388                         continue;
1389
1390                 /* run more modules */
1391                 ev = module_event_pass;
1392                 if(mesh->run.count > 0) {
1393                         /* pop random element off the runnable tree */
1394                         mstate = (struct mesh_state*)mesh->run.root->key;
1395                         (void)rbtree_delete(&mesh->run, mstate);
1396                 } else mstate = NULL;
1397         }
1398         if(verbosity >= VERB_ALGO) {
1399                 mesh_stats(mesh, "mesh_run: end");
1400                 mesh_log_list(mesh);
1401         }
1402 }
1403
1404 void
1405 mesh_log_list(struct mesh_area* mesh)
1406 {
1407         char buf[30];
1408         struct mesh_state* m;
1409         int num = 0;
1410         RBTREE_FOR(m, struct mesh_state*, &mesh->all) {
1411                 snprintf(buf, sizeof(buf), "%d%s%s%s%s%s%s mod%d %s%s",
1412                         num++, (m->s.is_priming)?"p":"",  /* prime */
1413                         (m->s.is_valrec)?"v":"",  /* prime */
1414                         (m->s.query_flags&BIT_RD)?"RD":"",
1415                         (m->s.query_flags&BIT_CD)?"CD":"",
1416                         (m->super_set.count==0)?"d":"", /* detached */
1417                         (m->sub_set.count!=0)?"c":"",  /* children */
1418                         m->s.curmod, (m->reply_list)?"rep":"", /*hasreply*/
1419                         (m->cb_list)?"cb":"" /* callbacks */
1420                         );
1421                 log_query_info(VERB_ALGO, buf, &m->s.qinfo);
1422         }
1423 }
1424
1425 void
1426 mesh_stats(struct mesh_area* mesh, const char* str)
1427 {
1428         verbose(VERB_DETAIL, "%s %u recursion states (%u with reply, "
1429                 "%u detached), %u waiting replies, %u recursion replies "
1430                 "sent, %d replies dropped, %d states jostled out",
1431                 str, (unsigned)mesh->all.count,
1432                 (unsigned)mesh->num_reply_states,
1433                 (unsigned)mesh->num_detached_states,
1434                 (unsigned)mesh->num_reply_addrs,
1435                 (unsigned)mesh->replies_sent,
1436                 (unsigned)mesh->stats_dropped,
1437                 (unsigned)mesh->stats_jostled);
1438         if(mesh->replies_sent > 0) {
1439                 struct timeval avg;
1440                 timeval_divide(&avg, &mesh->replies_sum_wait,
1441                         mesh->replies_sent);
1442                 log_info("average recursion processing time "
1443                         ARG_LL "d.%6.6d sec",
1444                         (long long)avg.tv_sec, (int)avg.tv_usec);
1445                 log_info("histogram of recursion processing times");
1446                 timehist_log(mesh->histogram, "recursions");
1447         }
1448 }
1449
1450 void
1451 mesh_stats_clear(struct mesh_area* mesh)
1452 {
1453         if(!mesh)
1454                 return;
1455         mesh->replies_sent = 0;
1456         mesh->replies_sum_wait.tv_sec = 0;
1457         mesh->replies_sum_wait.tv_usec = 0;
1458         mesh->stats_jostled = 0;
1459         mesh->stats_dropped = 0;
1460         timehist_clear(mesh->histogram);
1461         mesh->ans_secure = 0;
1462         mesh->ans_bogus = 0;
1463         memset(&mesh->ans_rcode[0], 0, sizeof(size_t)*16);
1464         mesh->ans_nodata = 0;
1465 }
1466
1467 size_t
1468 mesh_get_mem(struct mesh_area* mesh)
1469 {
1470         struct mesh_state* m;
1471         size_t s = sizeof(*mesh) + sizeof(struct timehist) +
1472                 sizeof(struct th_buck)*mesh->histogram->num +
1473                 sizeof(sldns_buffer) + sldns_buffer_capacity(mesh->qbuf_bak);
1474         RBTREE_FOR(m, struct mesh_state*, &mesh->all) {
1475                 /* all, including m itself allocated in qstate region */
1476                 s += regional_get_mem(m->s.region);
1477         }
1478         return s;
1479 }
1480
1481 int
1482 mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo,
1483         uint16_t flags, int prime, int valrec)
1484 {
1485         struct mesh_area* mesh = qstate->env->mesh;
1486         struct mesh_state* dep_m = NULL;
1487         if(!mesh_state_is_unique(qstate->mesh_info))
1488                 dep_m = mesh_area_find(mesh, NULL, qinfo, flags, prime, valrec);
1489         return mesh_detect_cycle_found(qstate, dep_m);
1490 }
1491
1492 void mesh_list_insert(struct mesh_state* m, struct mesh_state** fp,
1493         struct mesh_state** lp)
1494 {
1495         /* insert as last element */
1496         m->prev = *lp;
1497         m->next = NULL;
1498         if(*lp)
1499                 (*lp)->next = m;
1500         else    *fp = m;
1501         *lp = m;
1502 }
1503
1504 void mesh_list_remove(struct mesh_state* m, struct mesh_state** fp,
1505         struct mesh_state** lp)
1506 {
1507         if(m->next)
1508                 m->next->prev = m->prev;
1509         else    *lp = m->prev;
1510         if(m->prev)
1511                 m->prev->next = m->next;
1512         else    *fp = m->next;
1513 }