dnstree.c revision 356345 
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(rbtree_type* 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
133void name_tree_init_parents(rbtree_type* 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
159struct name_tree_node* name_tree_find(rbtree_type* 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
171struct name_tree_node* name_tree_lookup(rbtree_type* tree, uint8_t* name,
172        size_t len, int labs, uint16_t dclass)
173{
174        rbnode_type* 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
203struct addr_tree_node* addr_tree_lookup(rbtree_type* tree,
204        struct sockaddr_storage* addr, socklen_t addrlen)
205{
206        rbnode_type* 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
234struct addr_tree_node* addr_tree_find(rbtree_type* tree,
235        struct sockaddr_storage* addr, socklen_t addrlen, int net)
236{
237        rbnode_type* res = NULL;
238        struct addr_tree_node key;
239        key.node.key = &key;
240        memcpy(&key.addr, addr, addrlen);
241        key.addrlen = addrlen;
242        key.net = net;
243	res = rbtree_search(tree, &key);
244	return (struct addr_tree_node*)res;
245}
246
247int
248name_tree_next_root(rbtree_type* tree, uint16_t* dclass)
249{
250	struct name_tree_node key;
251	rbnode_type* n;
252	struct name_tree_node* p;
253	if(*dclass == 0) {
254		/* first root item is first item in tree */
255		n = rbtree_first(tree);
256		if(n == RBTREE_NULL)
257			return 0;
258		p = (struct name_tree_node*)n;
259		if(dname_is_root(p->name)) {
260			*dclass = p->dclass;
261			return 1;
262		}
263		/* root not first item? search for higher items */
264		*dclass = p->dclass + 1;
265		return name_tree_next_root(tree, dclass);
266	}
267	/* find class n in tree, we may get a direct hit, or if we don't
268	 * this is the last item of the previous class so rbtree_next() takes
269	 * us to the next root (if any) */
270	key.node.key = &key;
271	key.name = (uint8_t*)"\000";
272	key.len = 1;
273	key.labs = 0;
274	key.dclass = *dclass;
275	n = NULL;
276	if(rbtree_find_less_equal(tree, &key, &n)) {
277		/* exact */
278		return 1;
279	} else {
280		/* smaller element */
281		if(!n || n == RBTREE_NULL)
282			return 0; /* nothing found */
283		n = rbtree_next(n);
284		if(n == RBTREE_NULL)
285			return 0; /* no higher */
286		p = (struct name_tree_node*)n;
287		if(dname_is_root(p->name)) {
288			*dclass = p->dclass;
289			return 1;
290		}
291		/* not a root node, return next higher item */
292		*dclass = p->dclass+1;
293		return name_tree_next_root(tree, dclass);
294	}
295}
296