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