2 * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
4 * Copyright (c) 2013, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
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.
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.
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.
36 * addrtree -- radix tree for edns subnet cache.
41 #include "util/data/msgreply.h"
42 #include "util/module.h"
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
54 static struct addredge *
55 edge_create(struct addrnode *node, const addrkey_t *addr,
56 addrlen_t addrlen, struct addrnode *parent_node, int parent_index)
59 struct addredge *edge = (struct addredge *)malloc( sizeof (*edge) );
64 edge->parent_index = parent_index;
65 edge->parent_node = parent_node;
67 n = (size_t)((addrlen / KEYWIDTH) + ((addrlen % KEYWIDTH != 0)?1:0));
68 edge->str = (addrkey_t *)calloc(n, sizeof (addrkey_t));
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;
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
89 static struct addrnode *
90 node_create(struct addrtree *tree, void *elem, addrlen_t scope,
93 struct addrnode* node = (struct addrnode *)malloc( sizeof (*node) );
100 node->edge[0] = NULL;
101 node->edge[1] = NULL;
102 node->parent_edge = NULL;
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.
114 node_size(const struct addrtree *tree, const struct addrnode *n)
116 return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len +
117 (n->elem?tree->sizefunc(n->elem):0);
121 addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
122 size_t (*sizefunc)(void *), void *env, unsigned int max_node_count)
124 struct addrtree *tree;
125 log_assert(delfunc != NULL);
126 log_assert(sizefunc != NULL);
127 tree = (struct addrtree *)calloc(1, sizeof(*tree));
130 tree->root = node_create(tree, NULL, 0, 0);
135 tree->size_bytes = sizeof *tree + sizeof *tree->root;
138 tree->max_depth = max_depth;
139 tree->delfunc = delfunc;
140 tree->sizefunc = sizefunc;
142 tree->node_count = 0;
143 tree->max_node_count = max_node_count;
148 * Scrub a node clean of elem
149 * @param tree: tree the node lives in.
150 * @param node: node to be cleaned.
153 clean_node(struct addrtree *tree, struct addrnode *node)
155 if (!node->elem) return;
156 tree->size_bytes -= tree->sizefunc(node->elem);
157 tree->delfunc(tree->env, node->elem);
161 /** Remove specified node from LRU list */
163 lru_pop(struct addrtree *tree, struct addrnode *node)
165 if (node == tree->first) {
166 if (!node->next) { /* it is the last as well */
170 tree->first = node->next;
171 tree->first->prev = NULL;
173 } else if (node == tree->last) { /* but not the first */
174 tree->last = node->prev;
175 tree->last->next = NULL;
177 node->prev->next = node->next;
178 node->next->prev = node->prev;
182 /** Add node to LRU list as most recently used. */
184 lru_push(struct addrtree *tree, struct addrnode *node)
190 tree->last->next = node;
191 node->prev = tree->last;
197 /** Move node to the end of LRU list */
199 lru_update(struct addrtree *tree, struct addrnode *node)
201 if (tree->root == node) return;
203 lru_push(tree, node);
207 * Purge a node from the tree. Node and parentedge are cleaned and
209 * @param tree: Tree the node lives in.
210 * @param node: Node to be freed
213 purge_node(struct addrtree *tree, struct addrnode *node)
215 struct addredge *parent_edge, *child_edge = NULL;
217 int keep = node->edge[0] && node->edge[1];
219 clean_node(tree, node);
220 parent_edge = node->parent_edge;
221 if (keep || !parent_edge) return;
223 index = parent_edge->parent_index;
224 child_edge = node->edge[!node->edge[0]];
226 child_edge->parent_node = parent_edge->parent_node;
227 child_edge->parent_index = index;
229 parent_edge->parent_node->edge[index] = child_edge;
230 tree->size_bytes -= node_size(tree, node);
231 free(parent_edge->str);
238 * If a limit is set remove old nodes while above that limit.
239 * @param tree: Tree to be cleaned up.
242 lru_cleanup(struct addrtree *tree)
244 struct addrnode *n, *p;
246 if (tree->max_node_count == 0) return;
247 while (tree->node_count > tree->max_node_count) {
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) {
257 p = n->parent_edge->parent_node;
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
262 children = (p->edge[0] != NULL) + (p->edge[1] != NULL);
263 if (!p->elem && children == 1 && p->parent_edge) {
270 addrtree_size(const struct addrtree *tree)
272 return tree?tree->size_bytes:0;
275 void addrtree_delete(struct addrtree *tree)
279 clean_node(tree, tree->root);
281 tree->size_bytes -= sizeof(struct addrnode);
282 while ((n = tree->first)) {
283 tree->first = n->next;
285 tree->size_bytes -= node_size(tree, n);
286 free(n->parent_edge->str);
287 free(n->parent_edge);
290 log_assert(sizeof *tree == addrtree_size(tree));
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)
302 getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
304 log_assert(addrlen > n);
306 return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
310 * Test for equality on N'th bit.
311 * @return 0 for equal, 1 otherwise
314 cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
316 addrkey_t c = key1[n/KEYWIDTH] ^ key2[n/KEYWIDTH];
317 return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;
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.
330 bits_common(const addrkey_t *s1, addrlen_t l1,
331 const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
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;
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
352 issub(const addrkey_t *s1, addrlen_t l1,
353 const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
355 return bits_common(s1, l1, s2, l2, skip) == l1;
359 addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
360 addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
363 struct addrnode *newnode, *node;
364 struct addredge *edge;
366 addrlen_t common, depth;
369 log_assert(node != NULL);
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;
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);
386 tree->size_bytes += tree->sizefunc(elem);
389 index = getbit(addr, sourcemask, depth);
390 /* Get an edge to an unexpired node */
391 edge = node->edge[index];
393 /* Purge all expired nodes on path */
394 if (!edge->node->elem || edge->node->ttl >= now)
396 purge_node(tree, edge->node);
397 edge = node->edge[index];
399 /* Case 2: New leafnode */
401 newnode = node_create(tree, elem, scope, ttl);
402 if (!newnode) return;
403 if (!edge_create(newnode, addr, sourcemask, node,
405 clean_node(tree, newnode);
410 tree->size_bytes += node_size(tree, newnode);
411 lru_push(tree, newnode);
415 /* Case 3: Traverse edge */
416 common = bits_common(edge->str, edge->len, addr, sourcemask,
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. */
428 if (!(newnode = node_create(tree, NULL, 0, 0)))
430 node->edge[index] = NULL;
431 if (!edge_create(newnode, addr, common, node, index)) {
432 node->edge[index] = edge;
433 clean_node(tree, newnode);
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;
445 if (common == sourcemask) {
446 /* Data is stored in the node */
447 newnode->elem = elem;
448 newnode->scope = scope;
452 tree->size_bytes += node_size(tree, newnode);
454 if (common != sourcemask) {
455 /* Data is stored in other leafnode */
457 newnode = node_create(tree, elem, scope, ttl);
458 if (!edge_create(newnode, addr, sourcemask, node,
460 clean_node(tree, newnode);
465 tree->size_bytes += node_size(tree, newnode);
466 lru_push(tree, newnode);
474 addrtree_find(struct addrtree *tree, const addrkey_t *addr,
475 addrlen_t sourcemask, time_t now)
477 struct addrnode *node = tree->root;
478 struct addredge *edge = NULL;
481 log_assert(node != NULL);
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);
499 /* This is our final depth, but we haven't found an answer. */
500 if (depth == sourcemask)
502 /* Find an edge to traverse */
503 edge = node->edge[getbit(addr, sourcemask, depth)];
504 if (!edge || !edge->node)
506 if (edge->len > sourcemask )
508 if (!issub(edge->str, edge->len, addr, sourcemask, depth))
510 log_assert(depth < edge->len);
516 /** Wrappers for static functions to unit test */
517 int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1,
518 const addrkey_t *key2, addrlen_t n) {
519 return cmpbit(key1, key2, n);
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);
525 int unittest_wrapper_addrtree_getbit(const addrkey_t *addr,
526 addrlen_t addrlen, addrlen_t n) {
527 return getbit(addr, addrlen, n);
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);