1/*
2 * edns-subnet/addrtree.h -- 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
36/**
37 * \file
38 * The addrtree is a radix tree designed for edns subnet. Most notable
39 * is the addition of 'scope' to a node. Scope is only relevant for
40 * nodes with elem set, it indicates the number of bits the authority
41 * desires.
42 *
43 * For retrieving data one needs an address and address length
44 * (sourcemask). While traversing the tree the first matching node is
45 * returned. A node matches when
46 * 		node.scope<=sourcemask && node.elem!=NULL
47 * 		(This is the most specific answer the authority has.)
48 * or
49 * 		node.sourcemask==sourcemask && node.elem!=NULL
50 * 		(This is the most specific question the client can ask.)
51 *
52 * Insertion needs an address, sourcemask and scope. The length of the
53 * address is capped by min(sourcemask, scope). While traversing the
54 * tree the scope of all visited nodes is updated. This ensures we are
55 * always able to find the most specific answer available.
56 */
57
58#ifndef ADDRTREE_H
59#define ADDRTREE_H
60
61typedef uint8_t addrlen_t;
62typedef uint8_t addrkey_t;
63#define KEYWIDTH 8
64
65struct addrtree {
66	struct addrnode *root;
67	/** Number of elements in the tree (not always equal to number of
68	 * nodes) */
69	uint32_t node_count;
70	/** Maximum number of allowed nodes, will be enforced by LRU list.
71	 * Excluding the root node, 0 for unlimited */
72	uint32_t max_node_count;
73	/** Size of tree in bytes */
74	size_t size_bytes;
75	/** Maximum prefix length we are willing to cache. */
76	addrlen_t max_depth;
77	/** External function to delete elem. Called as
78	 * delfunc(addrnode->elem, addrtree->env) */
79	void (*delfunc)(void *, void *);
80	/** Environment for delfunc */
81	void *env;
82	/** External function returning size of elem. Called as
83	 * sizefunc(addrnode->elem) */
84	size_t (*sizefunc)(void *);
85	/** first node in LRU list, first candidate to go */
86	struct addrnode* first;
87	/** last node in LRU list, last candidate to go */
88	struct addrnode *last;
89};
90
91struct addrnode {
92	/** Payload of node, may be NULL */
93	void *elem;
94	/** Abs time in seconds in which elem is meaningful */
95	time_t ttl;
96	/** Number of significant bits in address. */
97	addrlen_t scope;
98	/** Only use the element for queries for subnet/0. Set if the query
99	 * for /0 was answered with scope 0. For query /x answer scope 0,
100	 * they can match anything and this is false. */
101	int only_match_scope_zero;
102	/** A node can have 0-2 edges, set to NULL for unused */
103	struct addredge *edge[2];
104	/** edge between this node and parent */
105	struct addredge *parent_edge;
106	/** previous node in LRU list */
107	struct addrnode *prev;
108	/** next node in LRU list */
109	struct addrnode *next;
110};
111
112struct addredge {
113	/** address of connected node */
114	addrkey_t *str;
115	/** length in bits of str */
116	addrlen_t len;
117	/** child node this edge is connected to */
118	struct addrnode *node;
119	/** Parent node this ege is connected to */
120	struct addrnode *parent_node;
121	/** Index of this edge in parent_node */
122	int parent_index;
123};
124
125/**
126 * Size of tree in bytes.
127 * @param tree: Tree.
128 * @return size of tree in bytes.
129 */
130size_t addrtree_size(const struct addrtree *tree);
131
132/**
133 * Create a new tree.
134 * @param max_depth: Tree will cap keys to this length.
135 * @param delfunc: f(element, env) delete element.
136 * @param sizefunc: f(element) returning the size of element.
137 * @param env: Module environment for alloc information.
138 * @param max_node_count: Maximum size of this data structure in nodes.
139 * 			0 for unlimited.
140 * @return new addrtree or NULL on failure.
141 */
142struct addrtree *
143addrtree_create(addrlen_t max_depth, void (*delfunc)(void *, void *),
144	size_t (*sizefunc)(void *), void *env, uint32_t max_node_count);
145
146/**
147 * Free tree and all nodes below.
148 * @param tree: Tree to be freed.
149 */
150void addrtree_delete(struct addrtree *tree);
151
152/**
153 * Insert an element in the tree. Failures are silent. Sourcemask and
154 * scope might be changed according to local policy. Caller should no
155 * longer access elem, it could be free'd now or later during future
156 * inserts.
157 *
158 * @param tree: Tree insert elem in.
159 * @param addr: key for element lookup.
160 * @param sourcemask: Length of addr in bits.
161 * @param scope: Number of significant bits in addr.
162 * @param elem: data to store in the tree.
163 * @param ttl: elem is valid up to this time, seconds.
164 * @param only_match_scope_zero: set for when query /0 has scope /0 answer.
165 * @param now: Current time in seconds.
166 */
167void addrtree_insert(struct addrtree *tree, const addrkey_t *addr,
168	addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl,
169	time_t now, int only_match_scope_zero);
170
171/**
172 * Find a node containing an element in the tree.
173 *
174 * @param tree: Tree to search.
175 * @param addr: key for element lookup.
176 * @param sourcemask: Length of addr in bits.
177 * @param now: Current time in seconds.
178 * @return addrnode or NULL on miss.
179 */
180struct addrnode * addrtree_find(struct addrtree *tree,
181	const addrkey_t *addr, addrlen_t sourcemask, time_t now);
182
183/** Wrappers for static functions to unit test */
184int unittest_wrapper_addrtree_cmpbit(const addrkey_t *key1,
185	const addrkey_t *key2, addrlen_t n);
186addrlen_t unittest_wrapper_addrtree_bits_common(const addrkey_t *s1,
187	addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip);
188int unittest_wrapper_addrtree_getbit(const addrkey_t *addr,
189	addrlen_t addrlen, addrlen_t n);
190int unittest_wrapper_addrtree_issub(const addrkey_t *s1, addrlen_t l1,
191	const addrkey_t *s2, addrlen_t l2,  addrlen_t skip);
192#endif /* ADDRTREE_H */
193