diff options
Diffstat (limited to 'edns-subnet/addrtree.c')
| -rw-r--r-- | edns-subnet/addrtree.c | 531 |
1 files changed, 531 insertions, 0 deletions
diff --git a/edns-subnet/addrtree.c b/edns-subnet/addrtree.c new file mode 100644 index 000000000000..69ace60549bf --- /dev/null +++ b/edns-subnet/addrtree.c @@ -0,0 +1,531 @@ +/* + * edns-subnet/addrtree.c -- radix tree for edns subnet cache. + * + * Copyright (c) 2013, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED + * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +/** \file + * addrtree -- radix tree for edns subnet cache. + */ + +#include "config.h" +#include "util/log.h" +#include "util/data/msgreply.h" +#include "util/module.h" +#include "addrtree.h" + +/** + * Create a new edge + * @param node: Child node this edge will connect to. + * @param addr: full key to this edge. + * @param addrlen: length of relevant part of key for this node + * @param parent_node: Parent node for node + * @param parent_index: Index of child node at parent node + * @return new addredge or NULL on failure + */ +static struct addredge * +edge_create(struct addrnode *node, const addrkey_t *addr, + addrlen_t addrlen, struct addrnode *parent_node, int parent_index) +{ + size_t n; + struct addredge *edge = (struct addredge *)malloc( sizeof (*edge) ); + if (!edge) + return NULL; + edge->node = node; + edge->len = addrlen; + edge->parent_index = parent_index; + edge->parent_node = parent_node; + /* ceil() */ + n = (size_t)((addrlen / KEYWIDTH) + ((addrlen % KEYWIDTH != 0)?1:0)); + edge->str = (addrkey_t *)calloc(n, sizeof (addrkey_t)); + if (!edge->str) { + free(edge); + return NULL; + } + memcpy(edge->str, addr, n * sizeof (addrkey_t)); + /* Only manipulate other objects after successful alloc */ + node->parent_edge = edge; + log_assert(parent_node->edge[parent_index] == NULL); + parent_node->edge[parent_index] = edge; + return edge; +} + +/** + * Create a new node + * @param tree: Tree the node lives in. + * @param elem: Element to store at this node + * @param scope: Scopemask from server reply + * @param ttl: Element is valid up to this time. Absolute, seconds + * @return new addrnode or NULL on failure + */ +static struct addrnode * +node_create(struct addrtree *tree, void *elem, addrlen_t scope, + time_t ttl) +{ + struct addrnode* node = (struct addrnode *)malloc( sizeof (*node) ); + if (!node) + return NULL; + node->elem = elem; + tree->node_count++; + node->scope = scope; + node->ttl = ttl; + node->edge[0] = NULL; + node->edge[1] = NULL; + node->parent_edge = NULL; + node->next = NULL; + node->prev = NULL; + return node; +} + +/** Size in bytes of node and parent edge + * @param tree: tree the node lives in + * @param n: node which size must be calculated + * @return size in bytes. + **/ +static inline size_t +node_size(const struct addrtree *tree, const struct addrnode *n) +{ + return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len + + (n->elem?tree->sizefunc(n->elem):0); +} + +struct addrtree * +addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *), + size_t (*sizefunc)(void *), void *env, unsigned int max_node_count) +{ + struct addrtree *tree; + log_assert(delfunc != NULL); + log_assert(sizefunc != NULL); + tree = (struct addrtree *)calloc(1, sizeof(*tree)); + if (!tree) + return NULL; + tree->root = node_create(tree, NULL, 0, 0); + if (!tree->root) { + free(tree); + return NULL; + } + tree->size_bytes = sizeof *tree + sizeof *tree->root; + tree->first = NULL; + tree->last = NULL; + tree->max_depth = max_depth; + tree->delfunc = delfunc; + tree->sizefunc = sizefunc; + tree->env = env; + tree->node_count = 0; + tree->max_node_count = max_node_count; + return tree; +} + +/** + * Scrub a node clean of elem + * @param tree: tree the node lives in. + * @param node: node to be cleaned. + */ +static void +clean_node(struct addrtree *tree, struct addrnode *node) +{ + if (!node->elem) return; + tree->size_bytes -= tree->sizefunc(node->elem); + tree->delfunc(tree->env, node->elem); + node->elem = NULL; +} + +/** Remove specified node from LRU list */ +static void +lru_pop(struct addrtree *tree, struct addrnode *node) +{ + if (node == tree->first) { + if (!node->next) { /* it is the last as well */ + tree->first = NULL; + tree->last = NULL; + } else { + tree->first = node->next; + tree->first->prev = NULL; + } + } else if (node == tree->last) { /* but not the first */ + tree->last = node->prev; + tree->last->next = NULL; + } else { + node->prev->next = node->next; + node->next->prev = node->prev; + } +} + +/** Add node to LRU list as most recently used. */ +static void +lru_push(struct addrtree *tree, struct addrnode *node) +{ + if (!tree->first) { + tree->first = node; + node->prev = NULL; + } else { + tree->last->next = node; + node->prev = tree->last; + } + tree->last = node; + node->next = NULL; +} + +/** Move node to the end of LRU list */ +static void +lru_update(struct addrtree *tree, struct addrnode *node) +{ + if (tree->root == node) return; + lru_pop(tree, node); + lru_push(tree, node); +} + +/** + * Purge a node from the tree. Node and parentedge are cleaned and + * free'd. + * @param tree: Tree the node lives in. + * @param node: Node to be freed + */ +static void +purge_node(struct addrtree *tree, struct addrnode *node) +{ + struct addredge *parent_edge, *child_edge = NULL; + int index; + int keep = node->edge[0] && node->edge[1]; + + clean_node(tree, node); + parent_edge = node->parent_edge; + if (keep || !parent_edge) return; + tree->node_count--; + index = parent_edge->parent_index; + child_edge = node->edge[!node->edge[0]]; + if (child_edge) { + child_edge->parent_node = parent_edge->parent_node; + child_edge->parent_index = index; + } + parent_edge->parent_node->edge[index] = child_edge; + tree->size_bytes -= node_size(tree, node); + free(parent_edge->str); + free(parent_edge); + lru_pop(tree, node); + free(node); +} + +/** + * If a limit is set remove old nodes while above that limit. + * @param tree: Tree to be cleaned up. + */ +static void +lru_cleanup(struct addrtree *tree) +{ + struct addrnode *n, *p; + int children; + if (tree->max_node_count == 0) return; + while (tree->node_count > tree->max_node_count) { + n = tree->first; + if (!n) break; + children = (n->edge[0] != NULL) + (n->edge[1] != NULL); + /** Don't remove this node, it is either the root or we can't + * do without it because it has 2 children */ + if (children == 2 || !n->parent_edge) { + lru_update(tree, n); + continue; + } + p = n->parent_edge->parent_node; + purge_node(tree, n); + /** Since we removed n, n's parent p is eligible for deletion + * if it is not the root node, caries no data and has only 1 + * child */ + children = (p->edge[0] != NULL) + (p->edge[1] != NULL); + if (!p->elem && children == 1 && p->parent_edge) { + purge_node(tree, p); + } + } +} + +inline size_t +addrtree_size(const struct addrtree *tree) +{ + return tree?tree->size_bytes:0; +} + +void addrtree_delete(struct addrtree *tree) +{ + struct addrnode *n; + if (!tree) return; + clean_node(tree, tree->root); + free(tree->root); + tree->size_bytes -= sizeof(struct addrnode); + while ((n = tree->first)) { + tree->first = n->next; + clean_node(tree, n); + tree->size_bytes -= node_size(tree, n); + free(n->parent_edge->str); + free(n->parent_edge); + free(n); + } + log_assert(sizeof *tree == addrtree_size(tree)); + free(tree); +} + +/** + * Get N'th bit from address + * @param addr: address to inspect + * @param addrlen: length of addr in bits + * @param n: index of bit to test. Must be in range [0, addrlen) + * @return 0 or 1 + */ +static int +getbit(const addrkey_t *addr, addrlen_t addrlen, addrlen_t n) +{ + log_assert(addrlen > n); + return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1; +} + +/** + * Test for equality on N'th bit. + * @return 0 for equal, 1 otherwise + */ +static inline int +cmpbit(const addrkey_t *key1, const addrkey_t *key2, addrlen_t n) +{ + addrkey_t c = key1[n/KEYWIDTH] ^ key2[n/KEYWIDTH]; + return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1; +} + +/** + * Common number of bits in prefix. + * @param s1: first prefix. + * @param l1: length of s1 in bits. + * @param s2: second prefix. + * @param l2: length of s2 in bits. + * @param skip: nr of bits already checked. + * @return common number of bits. + */ +static addrlen_t +bits_common(const addrkey_t *s1, addrlen_t l1, + const addrkey_t *s2, addrlen_t l2, addrlen_t skip) +{ + addrlen_t len, i; + len = (l1 > l2) ? l2 : l1; + log_assert(skip < len); + for (i = skip; i < len; i++) { + if (cmpbit(s1, s2, i)) return i; + } + return len; +} + +/** + * Tests if s1 is a substring of s2 + * @param s1: first prefix. + * @param l1: length of s1 in bits. + * @param s2: second prefix. + * @param l2: length of s2 in bits. + * @param skip: nr of bits already checked. + * @return 1 for substring, 0 otherwise + */ +static int +issub(const addrkey_t *s1, addrlen_t l1, + const addrkey_t *s2, addrlen_t l2, addrlen_t skip) +{ + return bits_common(s1, l1, s2, l2, skip) == l1; +} + +void +addrtree_insert(struct addrtree *tree, const addrkey_t *addr, + addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, + time_t now) +{ + struct addrnode *newnode, *node; + struct addredge *edge; + int index; + addrlen_t common, depth; + + node = tree->root; + log_assert(node != NULL); + + /* Protect our cache against too much fine-grained data */ + if (tree->max_depth < scope) scope = tree->max_depth; + /* Server answer was less specific than question */ + if (scope < sourcemask) sourcemask = scope; + + depth = 0; + while (1) { + log_assert(depth <= sourcemask); + /* Case 1: update existing node */ + if (depth == sourcemask) { + /* update this node's scope and data */ + clean_node(tree, node); + node->ttl = ttl; + node->elem = elem; + node->scope = scope; + tree->size_bytes += tree->sizefunc(elem); + return; + } + index = getbit(addr, sourcemask, depth); + /* Get an edge to an unexpired node */ + edge = node->edge[index]; + while (edge) { + /* Purge all expired nodes on path */ + if (!edge->node->elem || edge->node->ttl >= now) + break; + purge_node(tree, edge->node); + edge = node->edge[index]; + } + /* Case 2: New leafnode */ + if (!edge) { + newnode = node_create(tree, elem, scope, ttl); + if (!newnode) return; + if (!edge_create(newnode, addr, sourcemask, node, + index)) { + clean_node(tree, newnode); + tree->node_count--; + free(newnode); + return; + } + tree->size_bytes += node_size(tree, newnode); + lru_push(tree, newnode); + lru_cleanup(tree); + return; + } + /* Case 3: Traverse edge */ + common = bits_common(edge->str, edge->len, addr, sourcemask, + depth); + if (common == edge->len) { + /* We update the scope of intermediate nodes. Apparently + * the * authority changed its mind. If we would not do + * this we might not be able to reach our new node. */ + node->scope = scope; + depth = edge->len; + node = edge->node; + continue; + } + /* Case 4: split. */ + if (!(newnode = node_create(tree, NULL, 0, 0))) + return; + node->edge[index] = NULL; + if (!edge_create(newnode, addr, common, node, index)) { + node->edge[index] = edge; + clean_node(tree, newnode); + tree->node_count--; + free(newnode); + return; + } + lru_push(tree, newnode); + /* connect existing child to our new node */ + index = getbit(edge->str, edge->len, common); + newnode->edge[index] = edge; + edge->parent_node = newnode; + edge->parent_index = (int)index; + + if (common == sourcemask) { + /* Data is stored in the node */ + newnode->elem = elem; + newnode->scope = scope; + newnode->ttl = ttl; + } + + tree->size_bytes += node_size(tree, newnode); + + if (common != sourcemask) { + /* Data is stored in other leafnode */ + node = newnode; + newnode = node_create(tree, elem, scope, ttl); + if (!edge_create(newnode, addr, sourcemask, node, + index^1)) { + clean_node(tree, newnode); + tree->node_count--; + free(newnode); + return; + } + tree->size_bytes += node_size(tree, newnode); + lru_push(tree, newnode); + } + lru_cleanup(tree); + return; + } +} + +struct addrnode * +addrtree_find(struct addrtree *tree, const addrkey_t *addr, + addrlen_t sourcemask, time_t now) +{ + struct addrnode *node = tree->root; + struct addredge *edge = NULL; + addrlen_t depth = 0; + + log_assert(node != NULL); + while (1) { + /* Current node more specific then question. */ + log_assert(depth <= sourcemask); + /* does this node have data? if yes, see if we have a match */ + if (node->elem && node->ttl >= now) { + /* saved at wrong depth */; + log_assert(node->scope >= depth) + if (depth == node->scope || + (node->scope > sourcemask && + depth == sourcemask)) { + /* Authority indicates it does not have a more + * precise answer or we cannot ask a more + * specific question. */ + lru_update(tree, node); + return node; + } + } + /* This is our final depth, but we haven't found an answer. */ + if (depth == sourcemask) + return NULL; + /* Find an edge to traverse */ + edge = node->edge[getbit(addr, sourcemask, depth)]; + if (!edge || !edge->node) + return NULL; + if (edge->len > sourcemask ) + return NULL; + if (!issub(edge->str, edge->len, addr, sourcemask, depth)) + return NULL; + log_assert(depth < edge->len); + depth = edge->len; + node = edge->node; + } +} + +/** Wrappers for static functions to unit test */ +int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1, + const addrkey_t *key2, addrlen_t n) { + return cmpbit(key1, key2, n); +} +addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1, + addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip) { + return bits_common(s1, l1, s2, l2, skip); +} +int unittest_wrapper_addrtree_getbit(const addrkey_t *addr, + addrlen_t addrlen, addrlen_t n) { + return getbit(addr, addrlen, n); +} +int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1, + const addrkey_t *s2, addrlen_t l2, addrlen_t skip) { + return issub(s1, l1, s2, l2, skip); +} |