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