contrib/unbound/edns-subnet/addrtree.h

   1 /*
   2  * edns-subnet/addrtree.h -- radix tree for edns subnet cache.
   3  *
   4  * Copyright (c) 2013, 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  * The addrtree is a radix tree designed for edns subnet. Most notable
  39  * is the addition of 'scope' to a node. Scope is only relevant for
  40  * nodes with elem set, it indicates the number of bits the authority
  41  * desires.
  42  *
  43  * For retrieving data one needs an address and address length
  44  * (sourcemask). While traversing the tree the first matching node is
  45  * returned. A node matches when
  46  *              node.scope<=sourcemask && node.elem!=NULL
  47  *              (This is the most specific answer the authority has.)
  48  * or
  49  *              node.sourcemask==sourcemask && node.elem!=NULL
  50  *              (This is the most specific question the client can ask.)
  51  *
  52  * Insertion needs an address, sourcemask and scope. The length of the
  53  * address is capped by min(sourcemask, scope). While traversing the
  54  * tree the scope of all visited nodes is updated. This ensures we are
  55  * always able to find the most specific answer available.
  56  */
  57
  58 #ifndef ADDRTREE_H
  59 #define ADDRTREE_H
  60
  61 typedef uint8_t addrlen_t;
  62 typedef uint8_t addrkey_t;
  63 #define KEYWIDTH 8
  64
  65 struct addrtree {
  66         struct addrnode *root;
  67         /** Number of elements in the tree (not always equal to number of
  68          * nodes) */
  69         uint32_t node_count;
  70         /** Maximum number of allowed nodes, will be enforced by LRU list.
  71          * Excluding the root node, 0 for unlimited */
  72         uint32_t max_node_count;
  73         /** Size of tree in bytes */
  74         size_t size_bytes;
  75         /** Maximum prefix length we are willing to cache. */
  76         addrlen_t max_depth;
  77         /** External function to delete elem. Called as
  78          * delfunc(addrnode->elem, addrtree->env) */
  79         void (*delfunc)(void *, void *);
  80         /** Environment for delfunc */
  81         void *env;
  82         /** External function returning size of elem. Called as
  83          * sizefunc(addrnode->elem) */
  84         size_t (*sizefunc)(void *);
  85         /** first node in LRU list, first candidate to go */
  86         struct addrnode* first;
  87         /** last node in LRU list, last candidate to go */
  88         struct addrnode *last;
  89 };
  90
  91 struct addrnode {
  92         /** Payload of node, may be NULL */
  93         void *elem;
  94         /** Abs time in seconds in which elem is meaningful */
  95         time_t ttl;
  96         /** Number of significant bits in address. */
  97         addrlen_t scope;
  98         /** A node can have 0-2 edges, set to NULL for unused */
  99         struct addredge *edge[2];
 100         /** edge between this node and parent */
 101         struct addredge *parent_edge;
 102         /** previous node in LRU list */
 103         struct addrnode *prev;
 104         /** next node in LRU list */
 105         struct addrnode *next;
 106 };
 107
 108 struct addredge {
 109         /** address of connected node */
 110         addrkey_t *str;
 111         /** length in bits of str */
 112         addrlen_t len;
 113         /** child node this edge is connected to */
 114         struct addrnode *node;
 115         /** Parent node this ege is connected to */
 116         struct addrnode *parent_node;
 117         /** Index of this edge in parent_node */
 118         int parent_index;
 119 };
 120
 121 /**
 122  * Size of tree in bytes.
 123  * @param tree: Tree.
 124  * @return size of tree in bytes.
 125  */
 126 size_t addrtree_size(const struct addrtree *tree);
 127
 128 /**
 129  * Create a new tree.
 130  * @param max_depth: Tree will cap keys to this length.
 131  * @param delfunc: f(element, env) delete element.
 132  * @param sizefunc: f(element) returning the size of element.
 133  * @param env: Module environment for alloc information.
 134  * @param max_node_count: Maximum size of this data structure in nodes.
 135  *                      0 for unlimited.
 136  * @return new addrtree or NULL on failure.
 137  */
 138 struct addrtree *
 139 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
 140         size_t (*sizefunc)(void *), void *env, uint32_t max_node_count);
 141
 142 /**
 143  * Free tree and all nodes below.
 144  * @param tree: Tree to be freed.
 145  */
 146 void addrtree_delete(struct addrtree *tree);
 147
 148 /**
 149  * Insert an element in the tree. Failures are silent. Sourcemask and
 150  * scope might be changed according to local policy. Caller should no
 151  * longer access elem, it could be free'd now or later during future
 152  * inserts.
 153  *
 154  * @param tree: Tree insert elem in.
 155  * @param addr: key for element lookup.
 156  * @param sourcemask: Length of addr in bits.
 157  * @param scope: Number of significant bits in addr.
 158  * @param elem: data to store in the tree.
 159  * @param ttl: elem is valid up to this time, seconds.
 160  * @param now: Current time in seconds.
 161  */
 162 void addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
 163         addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
 164         time_t now);
 165
 166 /**
 167  * Find a node containing an element in the tree.
 168  *
 169  * @param tree: Tree to search.
 170  * @param addr: key for element lookup.
 171  * @param sourcemask: Length of addr in bits.
 172  * @param now: Current time in seconds.
 173  * @return addrnode or NULL on miss.
 174  */
 175 struct addrnode * addrtree_find(struct addrtree *tree,
 176         const addrkey_t *addr, addrlen_t sourcemask, time_t now);
 177
 178 /** Wrappers for static functions to unit test */
 179 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1,
 180         const addrkey_t *key2, addrlen_t n);
 181 addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1,
 182         addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip);
 183 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr,
 184         addrlen_t addrlen, addrlen_t n);
 185 int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1,
 186         const addrkey_t *s2, addrlen_t l2,  addrlen_t skip);
 187 #endif /* ADDRTREE_H */