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