1 /* 2 * util/storage/dnstree.c - support for rbtree types suitable for DNS code. 3 * 4 * Copyright (c) 2008, 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 structures combining types and functions to 40 * manipulate those structures that help building DNS lookup trees. 41 */ 42 #include "config.h" 43 #include "util/storage/dnstree.h" 44 #include "util/data/dname.h" 45 #include "util/net_help.h" 46 47 int name_tree_compare(const void* k1, const void* k2) 48 { 49 struct name_tree_node* x = (struct name_tree_node*)k1; 50 struct name_tree_node* y = (struct name_tree_node*)k2; 51 int m; 52 if(x->dclass != y->dclass) { 53 if(x->dclass < y->dclass) 54 return -1; 55 return 1; 56 } 57 return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 58 } 59 60 int addr_tree_compare(const void* k1, const void* k2) 61 { 62 struct addr_tree_node* n1 = (struct addr_tree_node*)k1; 63 struct addr_tree_node* n2 = (struct addr_tree_node*)k2; 64 int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr, 65 n2->addrlen); 66 if(r != 0) return r; 67 if(n1->net < n2->net) 68 return -1; 69 if(n1->net > n2->net) 70 return 1; 71 return 0; 72 } 73 74 void name_tree_init(rbtree_type* tree) 75 { 76 rbtree_init(tree, &name_tree_compare); 77 } 78 79 void addr_tree_init(rbtree_type* tree) 80 { 81 rbtree_init(tree, &addr_tree_compare); 82 } 83 84 int name_tree_insert(rbtree_type* tree, struct name_tree_node* node, 85 uint8_t* name, size_t len, int labs, uint16_t dclass) 86 { 87 node->node.key = node; 88 node->name = name; 89 node->len = len; 90 node->labs = labs; 91 node->dclass = dclass; 92 node->parent = NULL; 93 return rbtree_insert(tree, &node->node) != NULL; 94 } 95 96 int addr_tree_insert(rbtree_type* tree, struct addr_tree_node* node, 97 struct sockaddr_storage* addr, socklen_t addrlen, int net) 98 { 99 node->node.key = node; 100 memcpy(&node->addr, addr, addrlen); 101 node->addrlen = addrlen; 102 node->net = net; 103 node->parent = NULL; 104 return rbtree_insert(tree, &node->node) != NULL; 105 } 106 107 void addr_tree_init_parents(rbtree_type* tree) 108 { 109 struct addr_tree_node* node, *prev = NULL, *p; 110 int m; 111 RBTREE_FOR(node, struct addr_tree_node*, tree) { 112 node->parent = NULL; 113 if(!prev || prev->addrlen != node->addrlen) { 114 prev = node; 115 continue; 116 } 117 m = addr_in_common(&prev->addr, prev->net, &node->addr, 118 node->net, node->addrlen); 119 /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */ 120 /* find the previous, or parent-parent-parent */ 121 for(p = prev; p; p = p->parent) 122 if(p->net <= m) { 123 /* ==: since prev matched m, this is closest*/ 124 /* <: prev matches more, but is not a parent, 125 * this one is a (grand)parent */ 126 node->parent = p; 127 break; 128 } 129 prev = node; 130 } 131 } 132 133 void name_tree_init_parents(rbtree_type* tree) 134 { 135 struct name_tree_node* node, *prev = NULL, *p; 136 int m; 137 RBTREE_FOR(node, struct name_tree_node*, tree) { 138 node->parent = NULL; 139 if(!prev || prev->dclass != node->dclass) { 140 prev = node; 141 continue; 142 } 143 (void)dname_lab_cmp(prev->name, prev->labs, node->name, 144 node->labs, &m); /* we know prev is smaller */ 145 /* sort order like: . com. bla.com. zwb.com. net. */ 146 /* find the previous, or parent-parent-parent */ 147 for(p = prev; p; p = p->parent) 148 if(p->labs <= m) { 149 /* ==: since prev matched m, this is closest*/ 150 /* <: prev matches more, but is not a parent, 151 * this one is a (grand)parent */ 152 node->parent = p; 153 break; 154 } 155 prev = node; 156 } 157 } 158 159 struct name_tree_node* name_tree_find(rbtree_type* tree, uint8_t* name, 160 size_t len, int labs, uint16_t dclass) 161 { 162 struct name_tree_node key; 163 key.node.key = &key; 164 key.name = name; 165 key.len = len; 166 key.labs = labs; 167 key.dclass = dclass; 168 return (struct name_tree_node*)rbtree_search(tree, &key); 169 } 170 171 struct name_tree_node* name_tree_lookup(rbtree_type* tree, uint8_t* name, 172 size_t len, int labs, uint16_t dclass) 173 { 174 rbnode_type* res = NULL; 175 struct name_tree_node *result; 176 struct name_tree_node key; 177 key.node.key = &key; 178 key.name = name; 179 key.len = len; 180 key.labs = labs; 181 key.dclass = dclass; 182 if(rbtree_find_less_equal(tree, &key, &res)) { 183 /* exact */ 184 result = (struct name_tree_node*)res; 185 } else { 186 /* smaller element (or no element) */ 187 int m; 188 result = (struct name_tree_node*)res; 189 if(!result || result->dclass != dclass) 190 return NULL; 191 /* count number of labels matched */ 192 (void)dname_lab_cmp(result->name, result->labs, key.name, 193 key.labs, &m); 194 while(result) { /* go up until qname is subdomain of stub */ 195 if(result->labs <= m) 196 break; 197 result = result->parent; 198 } 199 } 200 return result; 201 } 202 203 struct addr_tree_node* addr_tree_lookup(rbtree_type* tree, 204 struct sockaddr_storage* addr, socklen_t addrlen) 205 { 206 rbnode_type* res = NULL; 207 struct addr_tree_node* result; 208 struct addr_tree_node key; 209 key.node.key = &key; 210 memcpy(&key.addr, addr, addrlen); 211 key.addrlen = addrlen; 212 key.net = (addr_is_ip6(addr, addrlen)?128:32); 213 if(rbtree_find_less_equal(tree, &key, &res)) { 214 /* exact */ 215 return (struct addr_tree_node*)res; 216 } else { 217 /* smaller element (or no element) */ 218 int m; 219 result = (struct addr_tree_node*)res; 220 if(!result || result->addrlen != addrlen) 221 return 0; 222 /* count number of bits matched */ 223 m = addr_in_common(&result->addr, result->net, addr, 224 key.net, addrlen); 225 while(result) { /* go up until addr is inside netblock */ 226 if(result->net <= m) 227 break; 228 result = result->parent; 229 } 230 } 231 return result; 232 } 233 234 struct addr_tree_node* addr_tree_find(rbtree_type* tree, 235 struct sockaddr_storage* addr, socklen_t addrlen, int net) 236 { 237 rbnode_type* res = NULL; 238 struct addr_tree_node key; 239 key.node.key = &key; 240 memcpy(&key.addr, addr, addrlen); 241 key.addrlen = addrlen; 242 key.net = net; 243 res = rbtree_search(tree, &key); 244 return (struct addr_tree_node*)res; 245 } 246 247 int 248 name_tree_next_root(rbtree_type* tree, uint16_t* dclass) 249 { 250 struct name_tree_node key; 251 rbnode_type* n; 252 struct name_tree_node* p; 253 if(*dclass == 0) { 254 /* first root item is first item in tree */ 255 n = rbtree_first(tree); 256 if(n == RBTREE_NULL) 257 return 0; 258 p = (struct name_tree_node*)n; 259 if(dname_is_root(p->name)) { 260 *dclass = p->dclass; 261 return 1; 262 } 263 /* root not first item? search for higher items */ 264 *dclass = p->dclass + 1; 265 return name_tree_next_root(tree, dclass); 266 } 267 /* find class n in tree, we may get a direct hit, or if we don't 268 * this is the last item of the previous class so rbtree_next() takes 269 * us to the next root (if any) */ 270 key.node.key = &key; 271 key.name = (uint8_t*)"\000"; 272 key.len = 1; 273 key.labs = 0; 274 key.dclass = *dclass; 275 n = NULL; 276 if(rbtree_find_less_equal(tree, &key, &n)) { 277 /* exact */ 278 return 1; 279 } else { 280 /* smaller element */ 281 if(!n || n == RBTREE_NULL) 282 return 0; /* nothing found */ 283 n = rbtree_next(n); 284 if(n == RBTREE_NULL) 285 return 0; /* no higher */ 286 p = (struct name_tree_node*)n; 287 if(dname_is_root(p->name)) { 288 *dclass = p->dclass; 289 return 1; 290 } 291 /* not a root node, return next higher item */ 292 *dclass = p->dclass+1; 293 return name_tree_next_root(tree, dclass); 294 } 295 } 296