contrib/unbound/util/storage/dnstree.c

   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_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
 134 void addr_tree_init_parents(rbtree_type* tree)
 135 {
 136         addr_tree_init_parents_node(
 137                         (struct addr_tree_node*)rbtree_first(tree));
 138 }
 139
 140 void 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
 166 struct 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
 178 struct 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
 210 struct 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
 241 struct 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
 254 int
 255 name_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 }