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 /** Only use the element for queries for subnet/0. Set if the query 99 * for /0 was answered with scope 0. For query /x answer scope 0, 100 * they can match anything and this is false. */ 101 int only_match_scope_zero; 102 /** A node can have 0-2 edges, set to NULL for unused */ 103 struct addredge *edge[2]; 104 /** edge between this node and parent */ 105 struct addredge *parent_edge; 106 /** previous node in LRU list */ 107 struct addrnode *prev; 108 /** next node in LRU list */ 109 struct addrnode *next; 110 }; 111 112 struct addredge { 113 /** address of connected node */ 114 addrkey_t *str; 115 /** length in bits of str */ 116 addrlen_t len; 117 /** child node this edge is connected to */ 118 struct addrnode *node; 119 /** Parent node this ege is connected to */ 120 struct addrnode *parent_node; 121 /** Index of this edge in parent_node */ 122 int parent_index; 123 }; 124 125 /** 126 * Size of tree in bytes. 127 * @param tree: Tree. 128 * @return size of tree in bytes. 129 */ 130 size_t addrtree_size(const struct addrtree *tree); 131 132 /** 133 * Create a new tree. 134 * @param max_depth: Tree will cap keys to this length. 135 * @param delfunc: f(element, env) delete element. 136 * @param sizefunc: f(element) returning the size of element. 137 * @param env: Module environment for alloc information. 138 * @param max_node_count: Maximum size of this data structure in nodes. 139 * 0 for unlimited. 140 * @return new addrtree or NULL on failure. 141 */ 142 struct addrtree * 143 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *), 144 size_t (*sizefunc)(void *), void *env, uint32_t max_node_count); 145 146 /** 147 * Free tree and all nodes below. 148 * @param tree: Tree to be freed. 149 */ 150 void addrtree_delete(struct addrtree *tree); 151 152 /** 153 * Insert an element in the tree. Failures are silent. Sourcemask and 154 * scope might be changed according to local policy. Caller should no 155 * longer access elem, it could be free'd now or later during future 156 * inserts. 157 * 158 * @param tree: Tree insert elem in. 159 * @param addr: key for element lookup. 160 * @param sourcemask: Length of addr in bits. 161 * @param scope: Number of significant bits in addr. 162 * @param elem: data to store in the tree. 163 * @param ttl: elem is valid up to this time, seconds. 164 * @param only_match_scope_zero: set for when query /0 has scope /0 answer. 165 * @param now: Current time in seconds. 166 */ 167 void addrtree_insert(struct addrtree *tree, const addrkey_t *addr, 168 addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, 169 time_t now, int only_match_scope_zero); 170 171 /** 172 * Find a node containing an element in the tree. 173 * 174 * @param tree: Tree to search. 175 * @param addr: key for element lookup. 176 * @param sourcemask: Length of addr in bits. 177 * @param now: Current time in seconds. 178 * @return addrnode or NULL on miss. 179 */ 180 struct addrnode * addrtree_find(struct addrtree *tree, 181 const addrkey_t *addr, addrlen_t sourcemask, time_t now); 182 183 /** Wrappers for static functions to unit test */ 184 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1, 185 const addrkey_t *key2, addrlen_t n); 186 addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1, 187 addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip); 188 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr, 189 addrlen_t addrlen, addrlen_t n); 190 int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1, 191 const addrkey_t *s2, addrlen_t l2, addrlen_t skip); 192 #endif /* ADDRTREE_H */ 193