contrib/unbound/services/mesh.h

   1 /*
   2  * services/mesh.h - 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 LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
  27  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * 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
  46 #ifndef SERVICES_MESH_H
  47 #define SERVICES_MESH_H
  48
  49 #include "util/rbtree.h"
  50 #include "util/netevent.h"
  51 #include "util/data/msgparse.h"
  52 #include "util/module.h"
  53 #include "services/modstack.h"
  54 struct mesh_state;
  55 struct mesh_reply;
  56 struct mesh_cb;
  57 struct query_info;
  58 struct reply_info;
  59 struct outbound_entry;
  60 struct timehist;
  61
  62 /**
  63  * Maximum number of mesh state activations. Any more is likely an
  64  * infinite loop in the module. It is then terminated.
  65  */
  66 #define MESH_MAX_ACTIVATION 3000
  67
  68 /**
  69  * Max number of references-to-references-to-references.. search size.
  70  * Any more is treated like 'too large', and the creation of a new
  71  * dependency is failed (so that no loops can be created).
  72  */
  73 #define MESH_MAX_SUBSUB 1024
  74
  75 /**
  76  * Mesh of query states
  77  */
  78 struct mesh_area {
  79         /** active module stack */
  80         struct module_stack mods;
  81         /** environment for new states */
  82         struct module_env* env;
  83
  84         /** set of runnable queries (mesh_state.run_node) */
  85         rbtree_t run;
  86         /** rbtree of all current queries (mesh_state.node)*/
  87         rbtree_t all;
  88
  89         /** count of the total number of mesh_reply entries */
  90         size_t num_reply_addrs;
  91         /** count of the number of mesh_states that have mesh_replies
  92          * Because a state can send results to multiple reply addresses,
  93          * this number must be equal or lower than num_reply_addrs. */
  94         size_t num_reply_states;
  95         /** number of mesh_states that have no mesh_replies, and also
  96          * an empty set of super-states, thus are 'toplevel' or detached
  97          * internal opportunistic queries */
  98         size_t num_detached_states;
  99         /** number of reply states in the forever list */
 100         size_t num_forever_states;
 101
 102         /** max total number of reply states to have */
 103         size_t max_reply_states;
 104         /** max forever number of reply states to have */
 105         size_t max_forever_states;
 106
 107         /** stats, cumulative number of reply states jostled out */
 108         size_t stats_jostled;
 109         /** stats, cumulative number of incoming client msgs dropped */
 110         size_t stats_dropped;
 111         /** number of replies sent */
 112         size_t replies_sent;
 113         /** sum of waiting times for the replies */
 114         struct timeval replies_sum_wait;
 115         /** histogram of time values */
 116         struct timehist* histogram;
 117         /** (extended stats) secure replies */
 118         size_t ans_secure;
 119         /** (extended stats) bogus replies */
 120         size_t ans_bogus;
 121         /** (extended stats) rcodes in replies */
 122         size_t ans_rcode[16];
 123         /** (extended stats) rcode nodata in replies */
 124         size_t ans_nodata;
 125
 126         /** backup of query if other operations recurse and need the
 127          * network buffers */
 128         ldns_buffer* qbuf_bak;
 129
 130         /** double linked list of the run-to-completion query states.
 131          * These are query states with a reply */
 132         struct mesh_state* forever_first;
 133         /** last entry in run forever list */
 134         struct mesh_state* forever_last;
 135
 136         /** double linked list of the query states that can be jostled out
 137          * by new queries if too old.  These are query states with a reply */
 138         struct mesh_state* jostle_first;
 139         /** last entry in jostle list - this is the entry that is newest */
 140         struct mesh_state* jostle_last;
 141         /** timeout for jostling. if age is lower, it does not get jostled. */
 142         struct timeval jostle_max;
 143 };
 144
 145 /**
 146  * A mesh query state
 147  * Unique per qname, qtype, qclass (from the qstate).
 148  * And RD / CD flag; in case a client turns it off.
 149  * And priming queries are different from ordinary queries (because of hints).
 150  *
 151  * The entire structure is allocated in a region, this region is the qstate
 152  * region. All parts (rbtree nodes etc) are also allocated in the region.
 153  */
 154 struct mesh_state {
 155         /** node in mesh_area all tree, key is this struct. Must be first. */
 156         rbnode_t node;
 157         /** node in mesh_area runnable tree, key is this struct */
 158         rbnode_t run_node;
 159         /** the query state. Note that the qinfo and query_flags
 160          * may not change. */
 161         struct module_qstate s;
 162         /** the list of replies to clients for the results */
 163         struct mesh_reply* reply_list;
 164         /** the list of callbacks for the results */
 165         struct mesh_cb* cb_list;
 166         /** set of superstates (that want this state's result)
 167          * contains struct mesh_state_ref* */
 168         rbtree_t super_set;
 169         /** set of substates (that this state needs to continue)
 170          * contains struct mesh_state_ref* */
 171         rbtree_t sub_set;
 172         /** number of activations for the mesh state */
 173         size_t num_activated;
 174
 175         /** previous in linked list for reply states */
 176         struct mesh_state* prev;
 177         /** next in linked list for reply states */
 178         struct mesh_state* next;
 179         /** if this state is in the forever list, jostle list, or neither */
 180         enum mesh_list_select { mesh_no_list, mesh_forever_list,
 181                 mesh_jostle_list } list_select;
 182
 183         /** true if replies have been sent out (at end for alignment) */
 184         uint8_t replies_sent;
 185 };
 186
 187 /**
 188  * Rbtree reference to a mesh_state.
 189  * Used in super_set and sub_set.
 190  */
 191 struct mesh_state_ref {
 192         /** node in rbtree for set, key is this structure */
 193         rbnode_t node;
 194         /** the mesh state */
 195         struct mesh_state* s;
 196 };
 197
 198 /**
 199  * Reply to a client
 200  */
 201 struct mesh_reply {
 202         /** next in reply list */
 203         struct mesh_reply* next;
 204         /** the query reply destination, packet buffer and where to send. */
 205         struct comm_reply query_reply;
 206         /** edns data from query */
 207         struct edns_data edns;
 208         /** the time when request was entered */
 209         struct timeval start_time;
 210         /** id of query, in network byteorder. */
 211         uint16_t qid;
 212         /** flags of query, for reply flags */
 213         uint16_t qflags;
 214         /** qname from this query. len same as mesh qinfo. */
 215         uint8_t* qname;
 216 };
 217
 218 /**
 219  * Mesh result callback func.
 220  * called as func(cb_arg, rcode, buffer_with_reply, security, why_bogus);
 221  */
 222 typedef void (*mesh_cb_func_t)(void*, int, ldns_buffer*, enum sec_status,
 223         char*);
 224
 225 /**
 226  * Callback to result routine
 227  */
 228 struct mesh_cb {
 229         /** next in list */
 230         struct mesh_cb* next;
 231         /** edns data from query */
 232         struct edns_data edns;
 233         /** id of query, in network byteorder. */
 234         uint16_t qid;
 235         /** flags of query, for reply flags */
 236         uint16_t qflags;
 237         /** buffer for reply */
 238         ldns_buffer* buf;
 239
 240         /** callback routine for results. if rcode != 0 buf has message.
 241          * called as cb(cb_arg, rcode, buf, sec_state);
 242          */
 243         mesh_cb_func_t cb;
 244         /** user arg for callback */
 245         void* cb_arg;
 246 };
 247
 248 /* ------------------- Functions for worker -------------------- */
 249
 250 /**
 251  * Allocate mesh, to empty.
 252  * @param stack: module stack to activate, copied (as readonly reference).
 253  * @param env: environment for new queries.
 254  * @return mesh: the new mesh or NULL on error.
 255  */
 256 struct mesh_area* mesh_create(struct module_stack* stack,
 257         struct module_env* env);
 258
 259 /**
 260  * Delete mesh, and all query states and replies in it.
 261  * @param mesh: the mesh to delete.
 262  */
 263 void mesh_delete(struct mesh_area* mesh);
 264
 265 /**
 266  * New query incoming from clients. Create new query state if needed, and
 267  * add mesh_reply to it. Returns error to client on malloc failures.
 268  * Will run the mesh area queries to process if a new query state is created.
 269  *
 270  * @param mesh: the mesh.
 271  * @param qinfo: query from client.
 272  * @param qflags: flags from client query.
 273  * @param edns: edns data from client query.
 274  * @param rep: where to reply to.
 275  * @param qid: query id to reply with.
 276  */
 277 void mesh_new_client(struct mesh_area* mesh, struct query_info* qinfo,
 278         uint16_t qflags, struct edns_data* edns, struct comm_reply* rep,
 279         uint16_t qid);
 280
 281 /**
 282  * New query with callback. Create new query state if needed, and
 283  * add mesh_cb to it.
 284  * Will run the mesh area queries to process if a new query state is created.
 285  *
 286  * @param mesh: the mesh.
 287  * @param qinfo: query from client.
 288  * @param qflags: flags from client query.
 289  * @param edns: edns data from client query.
 290  * @param buf: buffer for reply contents.
 291  * @param qid: query id to reply with.
 292  * @param cb: callback function.
 293  * @param cb_arg: callback user arg.
 294  * @return 0 on error.
 295  */
 296 int mesh_new_callback(struct mesh_area* mesh, struct query_info* qinfo,
 297         uint16_t qflags, struct edns_data* edns, ldns_buffer* buf,
 298         uint16_t qid, mesh_cb_func_t cb, void* cb_arg);
 299
 300 /**
 301  * New prefetch message. Create new query state if needed.
 302  * Will run the mesh area queries to process if a new query state is created.
 303  *
 304  * @param mesh: the mesh.
 305  * @param qinfo: query from client.
 306  * @param qflags: flags from client query.
 307  * @param leeway: TTL leeway what to expire earlier for this update.
 308  */
 309 void mesh_new_prefetch(struct mesh_area* mesh, struct query_info* qinfo,
 310         uint16_t qflags, uint32_t leeway);
 311
 312 /**
 313  * Handle new event from the wire. A serviced query has returned.
 314  * The query state will be made runnable, and the mesh_area will process
 315  * query states until processing is complete.
 316  *
 317  * @param mesh: the query mesh.
 318  * @param e: outbound entry, with query state to run and reply pointer.
 319  * @param reply: the comm point reply info.
 320  * @param what: NETEVENT_* error code (if not 0, what is wrong, TIMEOUT).
 321  */
 322 void mesh_report_reply(struct mesh_area* mesh, struct outbound_entry* e,
 323         struct comm_reply* reply, int what);
 324
 325 /* ------------------- Functions for module environment --------------- */
 326
 327 /**
 328  * Detach-subqueries.
 329  * Remove all sub-query references from this query state.
 330  * Keeps super-references of those sub-queries correct.
 331  * Updates stat items in mesh_area structure.
 332  * @param qstate: used to find mesh state.
 333  */
 334 void mesh_detach_subs(struct module_qstate* qstate);
 335
 336 /**
 337  * Attach subquery.
 338  * Creates it if it does not exist already.
 339  * Keeps sub and super references correct.
 340  * Performs a cycle detection - for double check - and fails if there is one.
 341  * Also fails if the sub-sub-references become too large.
 342  * Updates stat items in mesh_area structure.
 343  * Pass if it is priming query or not.
 344  * return:
 345  *      o if error (malloc) happened.
 346  *      o need to initialise the new state (module init; it is a new state).
 347  *        so that the next run of the query with this module is successful.
 348  *      o no init needed, attachment successful.
 349  *
 350  * @param qstate: the state to find mesh state, and that wants to receive
 351  *      the results from the new subquery.
 352  * @param qinfo: what to query for (copied).
 353  * @param qflags: what flags to use (RD / CD flag or not).
 354  * @param prime: if it is a (stub) priming query.
 355  * @param newq: If the new subquery needs initialisation, it is returned,
 356  *      otherwise NULL is returned.
 357  * @return: false on error, true if success (and init may be needed).
 358  */
 359 int mesh_attach_sub(struct module_qstate* qstate, struct query_info* qinfo,
 360         uint16_t qflags, int prime, struct module_qstate** newq);
 361
 362 /**
 363  * Query state is done, send messages to reply entries.
 364  * Encode messages using reply entry values and the querystate (with original
 365  * qinfo), using given reply_info.
 366  * Pass errcode != 0 if an error reply is needed.
 367  * If no reply entries, nothing is done.
 368  * Must be called before a module can module_finished or return module_error.
 369  * The module must handle the super query states itself as well.
 370  *
 371  * @param mstate: mesh state that is done. return_rcode and return_msg
 372  *      are used for replies.
 373  *      return_rcode: if not 0 (NOERROR) an error is sent back (and
 374  *              return_msg is ignored).
 375  *      return_msg: reply to encode and send back to clients.
 376  */
 377 void mesh_query_done(struct mesh_state* mstate);
 378
 379 /**
 380  * Call inform_super for the super query states that are interested in the
 381  * results from this query state. These can then be changed for error
 382  * or results.
 383  * Called when a module is module_finished or returns module_error.
 384  * The super query states become runnable with event module_event_pass,
 385  * it calls the current module for the super with the inform_super event.
 386  *
 387  * @param mesh: mesh area to add newly runnable modules to.
 388  * @param mstate: the state that has results, used to find mesh state.
 389  */
 390 void mesh_walk_supers(struct mesh_area* mesh, struct mesh_state* mstate);
 391
 392 /**
 393  * Delete mesh state, cleanup and also rbtrees and so on.
 394  * Will detach from all super/subnodes.
 395  * @param qstate: to remove.
 396  */
 397 void mesh_state_delete(struct module_qstate* qstate);
 398
 399 /* ------------------- Functions for mesh -------------------- */
 400
 401 /**
 402  * Create and initialize a new mesh state and its query state
 403  * Does not put the mesh state into rbtrees and so on.
 404  * @param env: module environment to set.
 405  * @param qinfo: query info that the mesh is for.
 406  * @param qflags: flags for query (RD / CD flag).
 407  * @param prime: if true, it is a priming query, set is_priming on mesh state.
 408  * @return: new mesh state or NULL on allocation error.
 409  */
 410 struct mesh_state* mesh_state_create(struct module_env* env,
 411         struct query_info* qinfo, uint16_t qflags, int prime);
 412
 413 /**
 414  * Cleanup a mesh state and its query state. Does not do rbtree or
 415  * reference cleanup.
 416  * @param mstate: mesh state to cleanup. Its pointer may no longer be used
 417  *      afterwards. Cleanup rbtrees before calling this function.
 418  */
 419 void mesh_state_cleanup(struct mesh_state* mstate);
 420
 421 /**
 422  * Delete all mesh states from the mesh.
 423  * @param mesh: the mesh area to clear
 424  */
 425 void mesh_delete_all(struct mesh_area* mesh);
 426
 427 /**
 428  * Find a mesh state in the mesh area. Pass relevant flags.
 429  *
 430  * @param mesh: the mesh area to look in.
 431  * @param qinfo: what query
 432  * @param qflags: if RD / CD bit is set or not.
 433  * @param prime: if it is a priming query.
 434  * @return: mesh state or NULL if not found.
 435  */
 436 struct mesh_state* mesh_area_find(struct mesh_area* mesh,
 437         struct query_info* qinfo, uint16_t qflags, int prime);
 438
 439 /**
 440  * Setup attachment super/sub relation between super and sub mesh state.
 441  * The relation must not be present when calling the function.
 442  * Does not update stat items in mesh_area.
 443  * @param super: super state.
 444  * @param sub: sub state.
 445  * @return: 0 on alloc error.
 446  */
 447 int mesh_state_attachment(struct mesh_state* super, struct mesh_state* sub);
 448
 449 /**
 450  * Create new reply structure and attach it to a mesh state.
 451  * Does not update stat items in mesh area.
 452  * @param s: the mesh state.
 453  * @param edns: edns data for reply (bufsize).
 454  * @param rep: comm point reply info.
 455  * @param qid: ID of reply.
 456  * @param qflags: original query flags.
 457  * @param qname: original query name.
 458  * @return: 0 on alloc error.
 459  */
 460 int mesh_state_add_reply(struct mesh_state* s, struct edns_data* edns,
 461         struct comm_reply* rep, uint16_t qid, uint16_t qflags, uint8_t* qname);
 462
 463 /**
 464  * Create new callback structure and attach it to a mesh state.
 465  * Does not update stat items in mesh area.
 466  * @param s: the mesh state.
 467  * @param edns: edns data for reply (bufsize).
 468  * @param buf: buffer for reply
 469  * @param cb: callback to call with results.
 470  * @param cb_arg: callback user arg.
 471  * @param qid: ID of reply.
 472  * @param qflags: original query flags.
 473  * @return: 0 on alloc error.
 474  */
 475 int mesh_state_add_cb(struct mesh_state* s, struct edns_data* edns,
 476         ldns_buffer* buf, mesh_cb_func_t cb, void* cb_arg, uint16_t qid,
 477         uint16_t qflags);
 478
 479 /**
 480  * Run the mesh. Run all runnable mesh states. Which can create new
 481  * runnable mesh states. Until completion. Automatically called by
 482  * mesh_report_reply and mesh_new_client as needed.
 483  * @param mesh: mesh area.
 484  * @param mstate: first mesh state to run.
 485  * @param ev: event the mstate. Others get event_pass.
 486  * @param e: if a reply, its outbound entry.
 487  */
 488 void mesh_run(struct mesh_area* mesh, struct mesh_state* mstate,
 489         enum module_ev ev, struct outbound_entry* e);
 490
 491 /**
 492  * Print some stats about the mesh to the log.
 493  * @param mesh: the mesh to print it for.
 494  * @param str: descriptive string to go with it.
 495  */
 496 void mesh_stats(struct mesh_area* mesh, const char* str);
 497
 498 /**
 499  * Clear the stats that the mesh keeps (number of queries serviced)
 500  * @param mesh: the mesh
 501  */
 502 void mesh_stats_clear(struct mesh_area* mesh);
 503
 504 /**
 505  * Print all the states in the mesh to the log.
 506  * @param mesh: the mesh to print all states of.
 507  */
 508 void mesh_log_list(struct mesh_area* mesh);
 509
 510 /**
 511  * Calculate memory size in use by mesh and all queries inside it.
 512  * @param mesh: the mesh to examine.
 513  * @return size in bytes.
 514  */
 515 size_t mesh_get_mem(struct mesh_area* mesh);
 516
 517 /**
 518  * Find cycle; see if the given mesh is in the targets sub, or sub-sub, ...
 519  * trees.
 520  * If the sub-sub structure is too large, it returns 'a cycle'=2.
 521  * @param qstate: given mesh querystate.
 522  * @param qinfo: query info for dependency.
 523  * @param flags: query flags of dependency.
 524  * @param prime: if dependency is a priming query or not.
 525  * @return true if the name,type,class exists and the given qstate mesh exists
 526  *      as a dependency of that name. Thus if qstate becomes dependent on
 527  *      name,type,class then a cycle is created, this is return value 1.
 528  *      Too large to search is value 2 (also true).
 529  */
 530 int mesh_detect_cycle(struct module_qstate* qstate, struct query_info* qinfo,
 531         uint16_t flags, int prime);
 532
 533 /** compare two mesh_states */
 534 int mesh_state_compare(const void* ap, const void* bp);
 535
 536 /** compare two mesh references */
 537 int mesh_state_ref_compare(const void* ap, const void* bp);
 538
 539 /**
 540  * Make space for another recursion state for a reply in the mesh
 541  * @param mesh: mesh area
 542  * @param qbuf: query buffer to save if recursion is invoked to make space.
 543  *    This buffer is necessary, because the following sequence in calls
 544  *    can result in an overwrite of the incoming query:
 545  *    delete_other_mesh_query - iter_clean - serviced_delete - waiting
 546  *    udp query is sent - on error callback - callback sends SERVFAIL reply
 547  *    over the same network channel, and shared UDP buffer is overwritten.
 548  *    You can pass NULL if there is no buffer that must be backed up.
 549  * @return false if no space is available.
 550  */
 551 int mesh_make_new_space(struct mesh_area* mesh, ldns_buffer* qbuf);
 552
 553 /**
 554  * Insert mesh state into a double linked list.  Inserted at end.
 555  * @param m: mesh state.
 556  * @param fp: pointer to the first-elem-pointer of the list.
 557  * @param lp: pointer to the last-elem-pointer of the list.
 558  */
 559 void mesh_list_insert(struct mesh_state* m, struct mesh_state** fp,
 560         struct mesh_state** lp);
 561
 562 /**
 563  * Remove mesh state from a double linked list.  Remove from any position.
 564  * @param m: mesh state.
 565  * @param fp: pointer to the first-elem-pointer of the list.
 566  * @param lp: pointer to the last-elem-pointer of the list.
 567  */
 568 void mesh_list_remove(struct mesh_state* m, struct mesh_state** fp,
 569         struct mesh_state** lp);
 570
 571 #endif /* SERVICES_MESH_H */