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