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_t* tree)
  75 {
  76         rbtree_init(tree, &name_tree_compare);
  77 }
  78
  79 void addr_tree_init(rbtree_t* tree)
  80 {
  81         rbtree_init(tree, &addr_tree_compare);
  82 }
  83
  84 int name_tree_insert(rbtree_t* 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_t* 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_t* 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_t* 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_t* 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_t* tree, uint8_t* name,
 172         size_t len, int labs, uint16_t dclass)
 173 {
 174         rbnode_t* 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_t* tree,
 204         struct sockaddr_storage* addr, socklen_t addrlen)
 205 {
 206         rbnode_t* 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 int
 235 name_tree_next_root(rbtree_t* tree, uint16_t* dclass)
 236 {
 237         struct name_tree_node key;
 238         rbnode_t* n;
 239         struct name_tree_node* p;
 240         if(*dclass == 0) {
 241                 /* first root item is first item in tree */
 242                 n = rbtree_first(tree);
 243                 if(n == RBTREE_NULL)
 244                         return 0;
 245                 p = (struct name_tree_node*)n;
 246                 if(dname_is_root(p->name)) {
 247                         *dclass = p->dclass;
 248                         return 1;
 249                 }
 250                 /* root not first item? search for higher items */
 251                 *dclass = p->dclass + 1;
 252                 return name_tree_next_root(tree, dclass);
 253         }
 254         /* find class n in tree, we may get a direct hit, or if we don't
 255          * this is the last item of the previous class so rbtree_next() takes
 256          * us to the next root (if any) */
 257         key.node.key = &key;
 258         key.name = (uint8_t*)"\000";
 259         key.len = 1;
 260         key.labs = 0;
 261         key.dclass = *dclass;
 262         n = NULL;
 263         if(rbtree_find_less_equal(tree, &key, &n)) {
 264                 /* exact */
 265                 return 1;
 266         } else {
 267                 /* smaller element */
 268                 if(!n || n == RBTREE_NULL)
 269                         return 0; /* nothing found */
 270                 n = rbtree_next(n);
 271                 if(n == RBTREE_NULL)
 272                         return 0; /* no higher */
 273                 p = (struct name_tree_node*)n;
 274                 if(dname_is_root(p->name)) {
 275                         *dclass = p->dclass;
 276                         return 1;
 277                 }
 278                 /* not a root node, return next higher item */
 279                 *dclass = p->dclass+1;
 280                 return name_tree_next_root(tree, dclass);
 281         }
 282 }