1 /*
2 * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
3 *
4 * Copyright (c) 2013, 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 /** \file
36 * addrtree -- radix tree for edns subnet cache.
37 */
38
39 #include "config.h"
40 #include "util/log.h"
41 #include "util/data/msgreply.h"
42 #include "util/module.h"
43 #include "addrtree.h"
44
45 /**
46 * Create a new edge
47 * @param node: Child node this edge will connect to.
48 * @param addr: full key to this edge.
49 * @param addrlen: length of relevant part of key for this node
50 * @param parent_node: Parent node for node
51 * @param parent_index: Index of child node at parent node
52 * @return new addredge or NULL on failure
53 */
54 static struct addredge *
edge_create(struct addrnode * node,const addrkey_t * addr,addrlen_t addrlen,struct addrnode * parent_node,int parent_index)55 edge_create(struct addrnode *node, const addrkey_t *addr,
56 addrlen_t addrlen, struct addrnode *parent_node, int parent_index)
57 {
58 size_t n;
59 struct addredge *edge = (struct addredge *)malloc( sizeof (*edge) );
60 if (!edge)
61 return NULL;
62 edge->node = node;
63 edge->len = addrlen;
64 edge->parent_index = parent_index;
65 edge->parent_node = parent_node;
66 /* ceil() */
67 n = (size_t)((addrlen / KEYWIDTH) + ((addrlen % KEYWIDTH != 0)?1:0));
68 edge->str = (addrkey_t *)calloc(n, sizeof (addrkey_t));
69 if (!edge->str) {
70 free(edge);
71 return NULL;
72 }
73 memcpy(edge->str, addr, n * sizeof (addrkey_t));
74 /* Only manipulate other objects after successful alloc */
75 node->parent_edge = edge;
76 log_assert(parent_node->edge[parent_index] == NULL);
77 parent_node->edge[parent_index] = edge;
78 return edge;
79 }
80
81 /**
82 * Create a new node
83 * @param tree: Tree the node lives in.
84 * @param elem: Element to store at this node
85 * @param scope: Scopemask from server reply
86 * @param ttl: Element is valid up to this time. Absolute, seconds
87 * @return new addrnode or NULL on failure
88 */
89 static struct addrnode *
node_create(struct addrtree * tree,void * elem,addrlen_t scope,time_t ttl)90 node_create(struct addrtree *tree, void *elem, addrlen_t scope,
91 time_t ttl)
92 {
93 struct addrnode* node = (struct addrnode *)malloc( sizeof (*node) );
94 if (!node)
95 return NULL;
96 node->elem = elem;
97 tree->node_count++;
98 node->scope = scope;
99 node->ttl = ttl;
100 node->edge[0] = NULL;
101 node->edge[1] = NULL;
102 node->parent_edge = NULL;
103 node->next = NULL;
104 node->prev = NULL;
105 return node;
106 }
107
108 /** Size in bytes of node and parent edge
109 * @param tree: tree the node lives in
110 * @param n: node which size must be calculated
111 * @return size in bytes.
112 **/
113 static inline size_t
node_size(const struct addrtree * tree,const struct addrnode * n)114 node_size(const struct addrtree *tree, const struct addrnode *n)
115 {
116 return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len +
117 (n->elem?tree->sizefunc(n->elem):0);
118 }
119
120 struct addrtree *
addrtree_create(addrlen_t max_depth,void (* delfunc)(void *,void *),size_t (* sizefunc)(void *),void * env,uint32_t max_node_count)121 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
122 size_t (*sizefunc)(void *), void *env, uint32_t max_node_count)
123 {
124 struct addrtree *tree;
125 log_assert(delfunc != NULL);
126 log_assert(sizefunc != NULL);
127 tree = (struct addrtree *)calloc(1, sizeof(*tree));
128 if (!tree)
129 return NULL;
130 tree->root = node_create(tree, NULL, 0, 0);
131 if (!tree->root) {
132 free(tree);
133 return NULL;
134 }
135 tree->size_bytes = sizeof *tree + sizeof *tree->root;
136 tree->first = NULL;
137 tree->last = NULL;
138 tree->max_depth = max_depth;
139 tree->delfunc = delfunc;
140 tree->sizefunc = sizefunc;
141 tree->env = env;
142 tree->node_count = 0;
143 tree->max_node_count = max_node_count;
144 return tree;
145 }
146
147 /**
148 * Scrub a node clean of elem
149 * @param tree: tree the node lives in.
150 * @param node: node to be cleaned.
151 */
152 static void
clean_node(struct addrtree * tree,struct addrnode * node)153 clean_node(struct addrtree *tree, struct addrnode *node)
154 {
155 if (!node->elem) return;
156 tree->size_bytes -= tree->sizefunc(node->elem);
157 tree->delfunc(tree->env, node->elem);
158 node->elem = NULL;
159 }
160
161 /** Remove specified node from LRU list */
162 static void
lru_pop(struct addrtree * tree,struct addrnode * node)163 lru_pop(struct addrtree *tree, struct addrnode *node)
164 {
165 if (node == tree->first) {
166 if (!node->next) { /* it is the last as well */
167 tree->first = NULL;
168 tree->last = NULL;
169 } else {
170 tree->first = node->next;
171 tree->first->prev = NULL;
172 }
173 } else if (node == tree->last) { /* but not the first */
174 tree->last = node->prev;
175 tree->last->next = NULL;
176 } else {
177 node->prev->next = node->next;
178 node->next->prev = node->prev;
179 }
180 }
181
182 /** Add node to LRU list as most recently used. */
183 static void
lru_push(struct addrtree * tree,struct addrnode * node)184 lru_push(struct addrtree *tree, struct addrnode *node)
185 {
186 if (!tree->first) {
187 tree->first = node;
188 node->prev = NULL;
189 } else {
190 tree->last->next = node;
191 node->prev = tree->last;
192 }
193 tree->last = node;
194 node->next = NULL;
195 }
196
197 /** Move node to the end of LRU list */
198 static void
lru_update(struct addrtree * tree,struct addrnode * node)199 lru_update(struct addrtree *tree, struct addrnode *node)
200 {
201 if (tree->root == node) return;
202 lru_pop(tree, node);
203 lru_push(tree, node);
204 }
205
206 /**
207 * Purge a node from the tree. Node and parentedge are cleaned and
208 * free'd.
209 * @param tree: Tree the node lives in.
210 * @param node: Node to be freed
211 */
212 static void
purge_node(struct addrtree * tree,struct addrnode * node)213 purge_node(struct addrtree *tree, struct addrnode *node)
214 {
215 struct addredge *parent_edge, *child_edge = NULL;
216 int index;
217 int keep = node->edge[0] && node->edge[1];
218
219 clean_node(tree, node);
220 parent_edge = node->parent_edge;
221 if (keep || !parent_edge) return;
222 tree->node_count--;
223 index = parent_edge->parent_index;
224 child_edge = node->edge[!node->edge[0]];
225 if (child_edge) {
226 child_edge->parent_node = parent_edge->parent_node;
227 child_edge->parent_index = index;
228 }
229 parent_edge->parent_node->edge[index] = child_edge;
230 tree->size_bytes -= node_size(tree, node);
231 free(parent_edge->str);
232 free(parent_edge);
233 lru_pop(tree, node);
234 free(node);
235 }
236
237 /**
238 * If a limit is set remove old nodes while above that limit.
239 * @param tree: Tree to be cleaned up.
240 */
241 static void
lru_cleanup(struct addrtree * tree)242 lru_cleanup(struct addrtree *tree)
243 {
244 struct addrnode *n, *p;
245 int children;
246 if (tree->max_node_count == 0) return;
247 while (tree->node_count > tree->max_node_count) {
248 n = tree->first;
249 if (!n) break;
250 children = (n->edge[0] != NULL) + (n->edge[1] != NULL);
251 /** Don't remove this node, it is either the root or we can't
252 * do without it because it has 2 children */
253 if (children == 2 || !n->parent_edge) {
254 lru_update(tree, n);
255 continue;
256 }
257 p = n->parent_edge->parent_node;
258 purge_node(tree, n);
259 /** Since we removed n, n's parent p is eligible for deletion
260 * if it is not the root node, caries no data and has only 1
261 * child */
262 children = (p->edge[0] != NULL) + (p->edge[1] != NULL);
263 if (!p->elem && children == 1 && p->parent_edge) {
264 purge_node(tree, p);
265 }
266 }
267 }
268
269 inline size_t
addrtree_size(const struct addrtree * tree)270 addrtree_size(const struct addrtree *tree)
271 {
272 return tree?tree->size_bytes:0;
273 }
274
addrtree_delete(struct addrtree * tree)275 void addrtree_delete(struct addrtree *tree)
276 {
277 struct addrnode *n;
278 if (!tree) return;
279 clean_node(tree, tree->root);
280 free(tree->root);
281 tree->size_bytes -= sizeof(struct addrnode);
282 while ((n = tree->first)) {
283 tree->first = n->next;
284 clean_node(tree, n);
285 tree->size_bytes -= node_size(tree, n);
286 free(n->parent_edge->str);
287 free(n->parent_edge);
288 free(n);
289 }
290 log_assert(sizeof *tree == addrtree_size(tree));
291 free(tree);
292 }
293
294 /**
295 * Get N'th bit from address
296 * @param addr: address to inspect
297 * @param addrlen: length of addr in bits
298 * @param n: index of bit to test. Must be in range [0, addrlen)
299 * @return 0 or 1
300 */
301 static int
getbit(const addrkey_t * addr,addrlen_t addrlen,addrlen_t n)302 getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
303 {
304 log_assert(addrlen > n);
305 (void)addrlen;
306 return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
307 }
308
309 /**
310 * Test for equality on N'th bit.
311 * @return 0 for equal, 1 otherwise
312 */
313 static inline int
cmpbit(const addrkey_t * key1,const addrkey_t * key2,addrlen_t n)314 cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
315 {
316 addrkey_t c = key1[n/KEYWIDTH] ^ key2[n/KEYWIDTH];
317 return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
318 }
319
320 /**
321 * Common number of bits in prefix.
322 * @param s1: first prefix.
323 * @param l1: length of s1 in bits.
324 * @param s2: second prefix.
325 * @param l2: length of s2 in bits.
326 * @param skip: nr of bits already checked.
327 * @return common number of bits.
328 */
329 static addrlen_t
bits_common(const addrkey_t * s1,addrlen_t l1,const addrkey_t * s2,addrlen_t l2,addrlen_t skip)330 bits_common(const addrkey_t *s1, addrlen_t l1,
331 const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
332 {
333 addrlen_t len, i;
334 len = (l1 > l2) ? l2 : l1;
335 log_assert(skip < len);
336 for (i = skip; i < len; i++) {
337 if (cmpbit(s1, s2, i)) return i;
338 }
339 return len;
340 }
341
342 /**
343 * Tests if s1 is a substring of s2
344 * @param s1: first prefix.
345 * @param l1: length of s1 in bits.
346 * @param s2: second prefix.
347 * @param l2: length of s2 in bits.
348 * @param skip: nr of bits already checked.
349 * @return 1 for substring, 0 otherwise
350 */
351 static int
issub(const addrkey_t * s1,addrlen_t l1,const addrkey_t * s2,addrlen_t l2,addrlen_t skip)352 issub(const addrkey_t *s1, addrlen_t l1,
353 const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
354 {
355 return bits_common(s1, l1, s2, l2, skip) == l1;
356 }
357
358 void
addrtree_insert(struct addrtree * tree,const addrkey_t * addr,addrlen_t sourcemask,addrlen_t scope,void * elem,time_t ttl,time_t now)359 addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
360 addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
361 time_t now)
362 {
363 struct addrnode *newnode, *node;
364 struct addredge *edge;
365 int index;
366 addrlen_t common, depth;
367
368 node = tree->root;
369 log_assert(node != NULL);
370
371 /* Protect our cache against too much fine-grained data */
372 if (tree->max_depth < scope) scope = tree->max_depth;
373 /* Server answer was less specific than question */
374 if (scope < sourcemask) sourcemask = scope;
375
376 depth = 0;
377 while (1) {
378 log_assert(depth <= sourcemask);
379 /* Case 1: update existing node */
380 if (depth == sourcemask) {
381 /* update this node's scope and data */
382 clean_node(tree, node);
383 node->ttl = ttl;
384 node->elem = elem;
385 node->scope = scope;
386 tree->size_bytes += tree->sizefunc(elem);
387 return;
388 }
389 index = getbit(addr, sourcemask, depth);
390 /* Get an edge to an unexpired node */
391 edge = node->edge[index];
392 while (edge) {
393 /* Purge all expired nodes on path */
394 if (!edge->node->elem || edge->node->ttl >= now)
395 break;
396 purge_node(tree, edge->node);
397 edge = node->edge[index];
398 }
399 /* Case 2: New leafnode */
400 if (!edge) {
401 newnode = node_create(tree, elem, scope, ttl);
402 if (!newnode) return;
403 if (!edge_create(newnode, addr, sourcemask, node,
404 index)) {
405 clean_node(tree, newnode);
406 tree->node_count--;
407 free(newnode);
408 return;
409 }
410 tree->size_bytes += node_size(tree, newnode);
411 lru_push(tree, newnode);
412 lru_cleanup(tree);
413 return;
414 }
415 /* Case 3: Traverse edge */
416 common = bits_common(edge->str, edge->len, addr, sourcemask,
417 depth);
418 if (common == edge->len) {
419 /* We update the scope of intermediate nodes. Apparently
420 * the * authority changed its mind. If we would not do
421 * this we might not be able to reach our new node. */
422 node->scope = scope;
423 depth = edge->len;
424 node = edge->node;
425 continue;
426 }
427 /* Case 4: split. */
428 if (!(newnode = node_create(tree, NULL, 0, 0)))
429 return;
430 node->edge[index] = NULL;
431 if (!edge_create(newnode, addr, common, node, index)) {
432 node->edge[index] = edge;
433 clean_node(tree, newnode);
434 tree->node_count--;
435 free(newnode);
436 return;
437 }
438 lru_push(tree, newnode);
439 /* connect existing child to our new node */
440 index = getbit(edge->str, edge->len, common);
441 newnode->edge[index] = edge;
442 edge->parent_node = newnode;
443 edge->parent_index = (int)index;
444
445 if (common == sourcemask) {
446 /* Data is stored in the node */
447 newnode->elem = elem;
448 newnode->scope = scope;
449 newnode->ttl = ttl;
450 }
451
452 tree->size_bytes += node_size(tree, newnode);
453
454 if (common != sourcemask) {
455 /* Data is stored in other leafnode */
456 node = newnode;
457 newnode = node_create(tree, elem, scope, ttl);
458 if (!edge_create(newnode, addr, sourcemask, node,
459 index^1)) {
460 clean_node(tree, newnode);
461 tree->node_count--;
462 free(newnode);
463 return;
464 }
465 tree->size_bytes += node_size(tree, newnode);
466 lru_push(tree, newnode);
467 }
468 lru_cleanup(tree);
469 return;
470 }
471 }
472
473 struct addrnode *
addrtree_find(struct addrtree * tree,const addrkey_t * addr,addrlen_t sourcemask,time_t now)474 addrtree_find(struct addrtree *tree, const addrkey_t *addr,
475 addrlen_t sourcemask, time_t now)
476 {
477 struct addrnode *node = tree->root;
478 struct addredge *edge = NULL;
479 addrlen_t depth = 0;
480
481 log_assert(node != NULL);
482 while (1) {
483 /* Current node more specific then question. */
484 log_assert(depth <= sourcemask);
485 /* does this node have data? if yes, see if we have a match */
486 if (node->elem && node->ttl >= now) {
487 /* saved at wrong depth */;
488 log_assert(node->scope >= depth);
489 if (depth == node->scope ||
490 (node->scope > sourcemask &&
491 depth == sourcemask)) {
492 /* Authority indicates it does not have a more
493 * precise answer or we cannot ask a more
494 * specific question. */
495 lru_update(tree, node);
496 return node;
497 }
498 }
499 /* This is our final depth, but we haven't found an answer. */
500 if (depth == sourcemask)
501 return NULL;
502 /* Find an edge to traverse */
503 edge = node->edge[getbit(addr, sourcemask, depth)];
504 if (!edge || !edge->node)
505 return NULL;
506 if (edge->len > sourcemask )
507 return NULL;
508 if (!issub(edge->str, edge->len, addr, sourcemask, depth))
509 return NULL;
510 log_assert(depth < edge->len);
511 depth = edge->len;
512 node = edge->node;
513 }
514 }
515
516 /** Wrappers for static functions to unit test */
unittest_wrapper_addrtree_cmpbit(const addrkey_t * key1,const addrkey_t * key2,addrlen_t n)517 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1,
518 const addrkey_t *key2, addrlen_t n) {
519 return cmpbit(key1, key2, n);
520 }
unittest_wrapper_addrtree_bits_common(const addrkey_t * s1,addrlen_t l1,const addrkey_t * s2,addrlen_t l2,addrlen_t skip)521 addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1,
522 addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip) {
523 return bits_common(s1, l1, s2, l2, skip);
524 }
unittest_wrapper_addrtree_getbit(const addrkey_t * addr,addrlen_t addrlen,addrlen_t n)525 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr,
526 addrlen_t addrlen, addrlen_t n) {
527 return getbit(addr, addrlen, n);
528 }
unittest_wrapper_addrtree_issub(const addrkey_t * s1,addrlen_t l1,const addrkey_t * s2,addrlen_t l2,addrlen_t skip)529 int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1,
530 const addrkey_t *s2, addrlen_t l2, addrlen_t skip) {
531 return issub(s1, l1, s2, l2, skip);
532 }
533