1238106Sdes/* 2238106Sdes * util/storage/dnstree.c - support for rbtree types suitable for DNS code. 3238106Sdes * 4238106Sdes * Copyright (c) 2008, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains structures combining types and functions to 40238106Sdes * manipulate those structures that help building DNS lookup trees. 41238106Sdes */ 42238106Sdes#include "config.h" 43238106Sdes#include "util/storage/dnstree.h" 44238106Sdes#include "util/data/dname.h" 45238106Sdes#include "util/net_help.h" 46238106Sdes 47238106Sdesint name_tree_compare(const void* k1, const void* k2) 48238106Sdes{ 49238106Sdes struct name_tree_node* x = (struct name_tree_node*)k1; 50238106Sdes struct name_tree_node* y = (struct name_tree_node*)k2; 51238106Sdes int m; 52238106Sdes if(x->dclass != y->dclass) { 53238106Sdes if(x->dclass < y->dclass) 54238106Sdes return -1; 55238106Sdes return 1; 56238106Sdes } 57238106Sdes return dname_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 58238106Sdes} 59238106Sdes 60238106Sdesint addr_tree_compare(const void* k1, const void* k2) 61238106Sdes{ 62238106Sdes struct addr_tree_node* n1 = (struct addr_tree_node*)k1; 63238106Sdes struct addr_tree_node* n2 = (struct addr_tree_node*)k2; 64238106Sdes int r = sockaddr_cmp_addr(&n1->addr, n1->addrlen, &n2->addr, 65238106Sdes n2->addrlen); 66238106Sdes if(r != 0) return r; 67238106Sdes if(n1->net < n2->net) 68238106Sdes return -1; 69238106Sdes if(n1->net > n2->net) 70238106Sdes return 1; 71238106Sdes return 0; 72238106Sdes} 73238106Sdes 74238106Sdesvoid name_tree_init(rbtree_t* tree) 75238106Sdes{ 76238106Sdes rbtree_init(tree, &name_tree_compare); 77238106Sdes} 78238106Sdes 79238106Sdesvoid addr_tree_init(rbtree_t* tree) 80238106Sdes{ 81238106Sdes rbtree_init(tree, &addr_tree_compare); 82238106Sdes} 83238106Sdes 84238106Sdesint name_tree_insert(rbtree_t* tree, struct name_tree_node* node, 85238106Sdes uint8_t* name, size_t len, int labs, uint16_t dclass) 86238106Sdes{ 87238106Sdes node->node.key = node; 88238106Sdes node->name = name; 89238106Sdes node->len = len; 90238106Sdes node->labs = labs; 91238106Sdes node->dclass = dclass; 92238106Sdes node->parent = NULL; 93238106Sdes return rbtree_insert(tree, &node->node) != NULL; 94238106Sdes} 95238106Sdes 96238106Sdesint addr_tree_insert(rbtree_t* tree, struct addr_tree_node* node, 97238106Sdes struct sockaddr_storage* addr, socklen_t addrlen, int net) 98238106Sdes{ 99238106Sdes node->node.key = node; 100238106Sdes memcpy(&node->addr, addr, addrlen); 101238106Sdes node->addrlen = addrlen; 102238106Sdes node->net = net; 103238106Sdes node->parent = NULL; 104238106Sdes return rbtree_insert(tree, &node->node) != NULL; 105238106Sdes} 106238106Sdes 107238106Sdesvoid addr_tree_init_parents(rbtree_t* tree) 108238106Sdes{ 109238106Sdes struct addr_tree_node* node, *prev = NULL, *p; 110238106Sdes int m; 111238106Sdes RBTREE_FOR(node, struct addr_tree_node*, tree) { 112238106Sdes node->parent = NULL; 113238106Sdes if(!prev || prev->addrlen != node->addrlen) { 114238106Sdes prev = node; 115238106Sdes continue; 116238106Sdes } 117238106Sdes m = addr_in_common(&prev->addr, prev->net, &node->addr, 118238106Sdes node->net, node->addrlen); 119238106Sdes /* sort order like: ::/0, 1::/2, 1::/4, ... 2::/2 */ 120238106Sdes /* find the previous, or parent-parent-parent */ 121238106Sdes for(p = prev; p; p = p->parent) 122238106Sdes if(p->net <= m) { 123238106Sdes /* ==: since prev matched m, this is closest*/ 124238106Sdes /* <: prev matches more, but is not a parent, 125238106Sdes * this one is a (grand)parent */ 126238106Sdes node->parent = p; 127238106Sdes break; 128238106Sdes } 129238106Sdes prev = node; 130238106Sdes } 131238106Sdes} 132238106Sdes 133238106Sdesvoid name_tree_init_parents(rbtree_t* tree) 134238106Sdes{ 135238106Sdes struct name_tree_node* node, *prev = NULL, *p; 136238106Sdes int m; 137238106Sdes RBTREE_FOR(node, struct name_tree_node*, tree) { 138238106Sdes node->parent = NULL; 139238106Sdes if(!prev || prev->dclass != node->dclass) { 140238106Sdes prev = node; 141238106Sdes continue; 142238106Sdes } 143238106Sdes (void)dname_lab_cmp(prev->name, prev->labs, node->name, 144238106Sdes node->labs, &m); /* we know prev is smaller */ 145238106Sdes /* sort order like: . com. bla.com. zwb.com. net. */ 146238106Sdes /* find the previous, or parent-parent-parent */ 147238106Sdes for(p = prev; p; p = p->parent) 148238106Sdes if(p->labs <= m) { 149238106Sdes /* ==: since prev matched m, this is closest*/ 150238106Sdes /* <: prev matches more, but is not a parent, 151238106Sdes * this one is a (grand)parent */ 152238106Sdes node->parent = p; 153238106Sdes break; 154238106Sdes } 155238106Sdes prev = node; 156238106Sdes } 157238106Sdes} 158238106Sdes 159238106Sdesstruct name_tree_node* name_tree_find(rbtree_t* tree, uint8_t* name, 160238106Sdes size_t len, int labs, uint16_t dclass) 161238106Sdes{ 162238106Sdes struct name_tree_node key; 163238106Sdes key.node.key = &key; 164238106Sdes key.name = name; 165238106Sdes key.len = len; 166238106Sdes key.labs = labs; 167238106Sdes key.dclass = dclass; 168238106Sdes return (struct name_tree_node*)rbtree_search(tree, &key); 169238106Sdes} 170238106Sdes 171238106Sdesstruct name_tree_node* name_tree_lookup(rbtree_t* tree, uint8_t* name, 172238106Sdes size_t len, int labs, uint16_t dclass) 173238106Sdes{ 174238106Sdes rbnode_t* res = NULL; 175238106Sdes struct name_tree_node *result; 176238106Sdes struct name_tree_node key; 177238106Sdes key.node.key = &key; 178238106Sdes key.name = name; 179238106Sdes key.len = len; 180238106Sdes key.labs = labs; 181238106Sdes key.dclass = dclass; 182238106Sdes if(rbtree_find_less_equal(tree, &key, &res)) { 183238106Sdes /* exact */ 184238106Sdes result = (struct name_tree_node*)res; 185238106Sdes } else { 186238106Sdes /* smaller element (or no element) */ 187238106Sdes int m; 188238106Sdes result = (struct name_tree_node*)res; 189238106Sdes if(!result || result->dclass != dclass) 190238106Sdes return NULL; 191238106Sdes /* count number of labels matched */ 192238106Sdes (void)dname_lab_cmp(result->name, result->labs, key.name, 193238106Sdes key.labs, &m); 194238106Sdes while(result) { /* go up until qname is subdomain of stub */ 195238106Sdes if(result->labs <= m) 196238106Sdes break; 197238106Sdes result = result->parent; 198238106Sdes } 199238106Sdes } 200238106Sdes return result; 201238106Sdes} 202238106Sdes 203238106Sdesstruct addr_tree_node* addr_tree_lookup(rbtree_t* tree, 204238106Sdes struct sockaddr_storage* addr, socklen_t addrlen) 205238106Sdes{ 206238106Sdes rbnode_t* res = NULL; 207238106Sdes struct addr_tree_node* result; 208238106Sdes struct addr_tree_node key; 209238106Sdes key.node.key = &key; 210238106Sdes memcpy(&key.addr, addr, addrlen); 211238106Sdes key.addrlen = addrlen; 212238106Sdes key.net = (addr_is_ip6(addr, addrlen)?128:32); 213238106Sdes if(rbtree_find_less_equal(tree, &key, &res)) { 214238106Sdes /* exact */ 215238106Sdes return (struct addr_tree_node*)res; 216238106Sdes } else { 217238106Sdes /* smaller element (or no element) */ 218238106Sdes int m; 219238106Sdes result = (struct addr_tree_node*)res; 220238106Sdes if(!result || result->addrlen != addrlen) 221238106Sdes return 0; 222238106Sdes /* count number of bits matched */ 223238106Sdes m = addr_in_common(&result->addr, result->net, addr, 224238106Sdes key.net, addrlen); 225238106Sdes while(result) { /* go up until addr is inside netblock */ 226238106Sdes if(result->net <= m) 227238106Sdes break; 228238106Sdes result = result->parent; 229238106Sdes } 230238106Sdes } 231238106Sdes return result; 232238106Sdes} 233238106Sdes 234238106Sdesint 235238106Sdesname_tree_next_root(rbtree_t* tree, uint16_t* dclass) 236238106Sdes{ 237238106Sdes struct name_tree_node key; 238238106Sdes rbnode_t* n; 239238106Sdes struct name_tree_node* p; 240238106Sdes if(*dclass == 0) { 241238106Sdes /* first root item is first item in tree */ 242238106Sdes n = rbtree_first(tree); 243238106Sdes if(n == RBTREE_NULL) 244238106Sdes return 0; 245238106Sdes p = (struct name_tree_node*)n; 246238106Sdes if(dname_is_root(p->name)) { 247238106Sdes *dclass = p->dclass; 248238106Sdes return 1; 249238106Sdes } 250238106Sdes /* root not first item? search for higher items */ 251238106Sdes *dclass = p->dclass + 1; 252238106Sdes return name_tree_next_root(tree, dclass); 253238106Sdes } 254238106Sdes /* find class n in tree, we may get a direct hit, or if we don't 255238106Sdes * this is the last item of the previous class so rbtree_next() takes 256238106Sdes * us to the next root (if any) */ 257238106Sdes key.node.key = &key; 258238106Sdes key.name = (uint8_t*)"\000"; 259238106Sdes key.len = 1; 260238106Sdes key.labs = 0; 261238106Sdes key.dclass = *dclass; 262238106Sdes n = NULL; 263238106Sdes if(rbtree_find_less_equal(tree, &key, &n)) { 264238106Sdes /* exact */ 265238106Sdes return 1; 266238106Sdes } else { 267238106Sdes /* smaller element */ 268238106Sdes if(!n || n == RBTREE_NULL) 269238106Sdes return 0; /* nothing found */ 270238106Sdes n = rbtree_next(n); 271238106Sdes if(n == RBTREE_NULL) 272238106Sdes return 0; /* no higher */ 273238106Sdes p = (struct name_tree_node*)n; 274238106Sdes if(dname_is_root(p->name)) { 275238106Sdes *dclass = p->dclass; 276238106Sdes return 1; 277238106Sdes } 278238106Sdes /* not a root node, return next higher item */ 279238106Sdes *dclass = p->dclass+1; 280238106Sdes return name_tree_next_root(tree, dclass); 281238106Sdes } 282238106Sdes} 283