2  * edns-subnet/addrtree.c -- radix tree for edns subnet cache.
8  * Redistribution and use in source and binary forms, with or without
15  * Redistributions in binary form must reproduce the above copyright notice,
16  * this list of conditions and the following disclaimer in the documentation
26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36  * addrtree -- radix tree for edns subnet cache.
62 	edge->node = node;  in edge_create()
63 	edge->len = addrlen;  in edge_create()
64 	edge->parent_index = parent_index;  in edge_create()
65 	edge->parent_node = parent_node;  in edge_create()
68 	edge->str = (addrkey_t *)calloc(n, sizeof (addrkey_t));  in edge_create()
69 	if (!edge->str) {  in edge_create()
73 	memcpy(edge->str, addr, n * sizeof (addrkey_t));  in edge_create()
75 	node->parent_edge = edge;  in edge_create()
76 	log_assert(parent_node->edge[parent_index] == NULL);  in edge_create()
77 	parent_node->edge[parent_index] = edge;  in edge_create()
83  * @param tree: Tree the node lives in.
90 node_create(struct addrtree *tree, void *elem, addrlen_t scope,   in node_create()  argument
96 	node->elem = elem;  in node_create()
97 	tree->node_count++;  in node_create()
98 	node->scope = scope;  in node_create()
99 	node->ttl = ttl;  in node_create()
100 	node->only_match_scope_zero = 0;  in node_create()
101 	node->edge[0] = NULL;  in node_create()
102 	node->edge[1] = NULL;  in node_create()
103 	node->parent_edge = NULL;  in node_create()
104 	node->next = NULL;  in node_create()
105 	node->prev = NULL;  in node_create()
109 /** Size in bytes of node and parent edge
110  * @param tree: tree the node lives in
112  * @return size in bytes.
115 node_size(const struct addrtree *tree, const struct addrnode *n)  in node_size()  argument
117 	return sizeof *n + sizeof *n->parent_edge + n->parent_edge->len +   in node_size()
118 		(n->elem?tree->sizefunc(n->elem):0);  in node_size()
125 	struct addrtree *tree;  in addrtree_create()  local
128 	tree = (struct addrtree *)calloc(1, sizeof(*tree));  in addrtree_create()
129 	if (!tree)  in addrtree_create()
131 	tree->root = node_create(tree, NULL, 0, 0);  in addrtree_create()
132 	if (!tree->root) {  in addrtree_create()
133 		free(tree);  in addrtree_create()
136 	tree->size_bytes = sizeof *tree + sizeof *tree->root;  in addrtree_create()
137 	tree->first = NULL;  in addrtree_create()
138 	tree->last = NULL;  in addrtree_create()
139 	tree->max_depth = max_depth;  in addrtree_create()
140 	tree->delfunc = delfunc;  in addrtree_create()
141 	tree->sizefunc = sizefunc;  in addrtree_create()
142 	tree->env = env;  in addrtree_create()
143 	tree->node_count = 0;  in addrtree_create()
144 	tree->max_node_count = max_node_count;  in addrtree_create()
145 	return tree;  in addrtree_create()
150  * @param tree: tree the node lives in.
154 clean_node(struct addrtree *tree, struct addrnode *node)  in clean_node()  argument
156 	if (!node->elem) return;  in clean_node()
157 	tree->size_bytes -= tree->sizefunc(node->elem);  in clean_node()
158 	tree->delfunc(tree->env, node->elem);  in clean_node()
159 	node->only_match_scope_zero = 0;  in clean_node()
160 	node->elem = NULL;  in clean_node()
165 lru_pop(struct addrtree *tree, struct addrnode *node)  in lru_pop()  argument
167 	if (node == tree->first) {  in lru_pop()
168 		if (!node->next) { /* it is the last as well */  in lru_pop()
169 			tree->first = NULL;  in lru_pop()
170 			tree->last = NULL;  in lru_pop()
172 			tree->first = node->next;  in lru_pop()
173 			tree->first->prev = NULL;  in lru_pop()
175 	} else if (node == tree->last) { /* but not the first */  in lru_pop()
176 		tree->last = node->prev;  in lru_pop()
177 		tree->last->next = NULL;  in lru_pop()
179 		node->prev->next = node->next;  in lru_pop()
180 		node->next->prev = node->prev;  in lru_pop()
186 lru_push(struct addrtree *tree, struct addrnode *node)  in lru_push()  argument
188 	if (!tree->first) {  in lru_push()
189 		tree->first = node;  in lru_push()
190 		node->prev = NULL;  in lru_push()
192 		tree->last->next = node;  in lru_push()
193 		node->prev = tree->last;  in lru_push()
195 	tree->last = node;  in lru_push()
196 	node->next = NULL;  in lru_push()
201 lru_update(struct addrtree *tree, struct addrnode *node)  in lru_update()  argument
203 	if (tree->root == node) return;  in lru_update()
204 	lru_pop(tree, node);  in lru_update()
205 	lru_push(tree, node);  in lru_update()
209  * Purge a node from the tree. Node and parentedge are cleaned and 
211  * @param tree: Tree the node lives in.
215 purge_node(struct addrtree *tree, struct addrnode *node)  in purge_node()  argument
219 	int keep = node->edge[0] && node->edge[1];  in purge_node()
221 	clean_node(tree, node);  in purge_node()
222 	parent_edge = node->parent_edge;  in purge_node()
224 	tree->node_count--;  in purge_node()
225 	index = parent_edge->parent_index;  in purge_node()
226 	child_edge = node->edge[!node->edge[0]];  in purge_node()
228 		child_edge->parent_node  = parent_edge->parent_node;  in purge_node()
229 		child_edge->parent_index = index;  in purge_node()
231 	parent_edge->parent_node->edge[index] = child_edge;  in purge_node()
232 	tree->size_bytes -= node_size(tree, node);  in purge_node()
233 	free(parent_edge->str);  in purge_node()
235 	lru_pop(tree, node);  in purge_node()
241  * @param tree: Tree to be cleaned up.
244 lru_cleanup(struct addrtree *tree)  in lru_cleanup()  argument
248 	if (tree->max_node_count == 0) return;  in lru_cleanup()
249 	while (tree->node_count > tree->max_node_count) {  in lru_cleanup()
250 		n = tree->first;  in lru_cleanup()
252 		children = (n->edge[0] != NULL) + (n->edge[1] != NULL);  in lru_cleanup()
255 		if (children == 2 || !n->parent_edge) {  in lru_cleanup()
256 			lru_update(tree, n);  in lru_cleanup()
259 		p = n->parent_edge->parent_node;  in lru_cleanup()
260 		purge_node(tree, n);  in lru_cleanup()
264 		children = (p->edge[0] != NULL) + (p->edge[1] != NULL);  in lru_cleanup()
265 		if (!p->elem && children == 1 && p->parent_edge) {  in lru_cleanup()
266 			purge_node(tree, p);  in lru_cleanup()
272 addrtree_size(const struct addrtree *tree)  in addrtree_size()  argument
274 	return tree?tree->size_bytes:0;  in addrtree_size()
277 void addrtree_delete(struct addrtree *tree)  in addrtree_delete()  argument
280 	if (!tree) return;  in addrtree_delete()
281 	clean_node(tree, tree->root);  in addrtree_delete()
282 	free(tree->root);  in addrtree_delete()
283 	tree->size_bytes -= sizeof(struct addrnode);  in addrtree_delete()
284 	while ((n = tree->first)) {  in addrtree_delete()
285 		tree->first = n->next;  in addrtree_delete()
286 		clean_node(tree, n);  in addrtree_delete()
287 		tree->size_bytes -= node_size(tree, n);  in addrtree_delete()
288 		free(n->parent_edge->str);  in addrtree_delete()
289 		free(n->parent_edge);  in addrtree_delete()
292 	log_assert(sizeof *tree == addrtree_size(tree));  in addrtree_delete()
293 	free(tree);  in addrtree_delete()
299  * @param addrlen: length of addr in bits
300  * @param n: index of bit to test. Must be in range [0, addrlen)
308 	return (int)(addr[n/KEYWIDTH]>>((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;  in getbit()
319 	return (int)(c >> ((KEYWIDTH-1)-(n%KEYWIDTH))) & 1;  in cmpbit()
323  * Common number of bits in prefix.
325  * @param l1: length of s1 in bits.
327  * @param l2: length of s2 in bits.
347  * @param l1: length of s1 in bits.
349  * @param l2: length of s2 in bits.
361 addrtree_insert(struct addrtree *tree, const addrkey_t *addr,   in addrtree_insert()  argument
370 	node = tree->root;  in addrtree_insert()
373 	/* Protect our cache against too much fine-grained data */  in addrtree_insert()
374 	if (tree->max_depth < scope) scope = tree->max_depth;  in addrtree_insert()
384 			clean_node(tree, node);  in addrtree_insert()
385 			node->ttl = ttl;  in addrtree_insert()
386 			node->only_match_scope_zero = only_match_scope_zero;  in addrtree_insert()
387 			node->elem = elem;  in addrtree_insert()
388 			node->scope = scope;  in addrtree_insert()
389 			tree->size_bytes += tree->sizefunc(elem);  in addrtree_insert()
394 		edge = node->edge[index];  in addrtree_insert()
397 			if (!edge->node->elem || edge->node->ttl >= now)  in addrtree_insert()
399 			purge_node(tree, edge->node);  in addrtree_insert()
400 			edge = node->edge[index];  in addrtree_insert()
404 			newnode = node_create(tree, elem, scope, ttl);  in addrtree_insert()
408 				clean_node(tree, newnode);  in addrtree_insert()
409 				tree->node_count--;  in addrtree_insert()
413 			tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
414 			lru_push(tree, newnode);  in addrtree_insert()
415 			lru_cleanup(tree);  in addrtree_insert()
419 		common = bits_common(edge->str, edge->len, addr, sourcemask,  in addrtree_insert()
421 		if (common == edge->len) {  in addrtree_insert()
425 			node->scope = scope;  in addrtree_insert()
426 			depth = edge->len;  in addrtree_insert()
427 			node = edge->node;  in addrtree_insert()
431 		if (!(newnode = node_create(tree, NULL, 0, 0)))  in addrtree_insert()
433 		node->edge[index] = NULL;  in addrtree_insert()
435 			node->edge[index] = edge;  in addrtree_insert()
436 			clean_node(tree, newnode);  in addrtree_insert()
437 			tree->node_count--;  in addrtree_insert()
441 		lru_push(tree, newnode);  in addrtree_insert()
443 		index = getbit(edge->str, edge->len, common);  in addrtree_insert()
444 		newnode->edge[index] = edge;  in addrtree_insert()
445 		edge->parent_node = newnode;  in addrtree_insert()
446 		edge->parent_index = (int)index;  in addrtree_insert()
449 			/* Data is stored in the node */  in addrtree_insert()
450 			newnode->elem = elem;  in addrtree_insert()
451 			newnode->scope = scope;  in addrtree_insert()
452 			newnode->ttl = ttl;  in addrtree_insert()
453 			newnode->only_match_scope_zero = only_match_scope_zero;  in addrtree_insert()
456 		tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
459 			/* Data is stored in other leafnode */  in addrtree_insert()
461 			newnode = node_create(tree, elem, scope, ttl);  in addrtree_insert()
464 				clean_node(tree, newnode);  in addrtree_insert()
465 				tree->node_count--;  in addrtree_insert()
469 			tree->size_bytes += node_size(tree, newnode);  in addrtree_insert()
470 			lru_push(tree, newnode);  in addrtree_insert()
472 		lru_cleanup(tree);  in addrtree_insert()
478 addrtree_find(struct addrtree *tree, const addrkey_t *addr,   in addrtree_find()  argument
481 	struct addrnode *node = tree->root;  in addrtree_find()
490 		if (node->elem && node->ttl >= now &&  in addrtree_find()
491 			!(sourcemask != 0 && node->only_match_scope_zero)) {  in addrtree_find()
493 			log_assert(node->scope >= depth);  in addrtree_find()
494 			if (depth == node->scope ||  in addrtree_find()
495 				(node->scope > sourcemask &&  in addrtree_find()
500 				lru_update(tree, node);  in addrtree_find()
508 		edge = node->edge[getbit(addr, sourcemask, depth)];  in addrtree_find()
509 		if (!edge || !edge->node)  in addrtree_find()
511 		if (edge->len > sourcemask )  in addrtree_find()
513 		if (!issub(edge->str, edge->len, addr, sourcemask, depth))  in addrtree_find()
515 		log_assert(depth < edge->len);  in addrtree_find()
516 		depth = edge->len;  in addrtree_find()
517 		node = edge->node;  in addrtree_find()