addrtree – radix tree for edns subnet cache. More...

#include "config.h"
#include "util/log.h"
#include "util/data/msgreply.h"
#include "util/module.h"
#include "addrtree.h"

Functions
static struct addredge *	edge_create (struct addrnode node, const addrkey_t addr, addrlen_t addrlen, struct addrnode *parent_node, int parent_index)
	Create a new edge. More...

static struct addrnode *	node_create (struct addrtree tree, void elem, addrlen_t scope, time_t ttl)
	Create a new node. More...

static size_t	node_size (const struct addrtree tree, const struct addrnode n)
	Size in bytes of node and parent edge. More...

struct addrtree *	addrtree_create (addrlen_t max_depth, void(delfunc)(void , void ), size_t(sizefunc)(void ), void env, uint32_t max_node_count)
	Create a new tree. More...

static void	clean_node (struct addrtree tree, struct addrnode node)
	Scrub a node clean of elem. More...

static void	lru_pop (struct addrtree tree, struct addrnode node)
	Remove specified node from LRU list.

static void	lru_push (struct addrtree tree, struct addrnode node)
	Add node to LRU list as most recently used.

static void	lru_update (struct addrtree tree, struct addrnode node)
	Move node to the end of LRU list.

static void	purge_node (struct addrtree tree, struct addrnode node)
	Purge a node from the tree. More...

static void	lru_cleanup (struct addrtree *tree)
	If a limit is set remove old nodes while above that limit. More...

size_t	addrtree_size (const struct addrtree *tree)
	Size of tree in bytes. More...

void	addrtree_delete (struct addrtree *tree)
	Free tree and all nodes below. More...

static int	getbit (const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
	Get N'th bit from address. More...

static int	cmpbit (const addrkey_t key1, const addrkey_t key2, addrlen_t n)
	Test for equality on N'th bit. More...

static addrlen_t	bits_common (const addrkey_t s1, addrlen_t l1, const addrkey_t s2, addrlen_t l2, addrlen_t skip)
	Common number of bits in prefix. More...

static int	issub (const addrkey_t s1, addrlen_t l1, const addrkey_t s2, addrlen_t l2, addrlen_t skip)
	Tests if s1 is a substring of s2. More...

void	addrtree_insert (struct addrtree tree, const addrkey_t addr, addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, time_t now, int only_match_scope_zero)
	Insert an element in the tree. More...

struct addrnode *	addrtree_find (struct addrtree tree, const addrkey_t addr, addrlen_t sourcemask, time_t now)
	Find a node containing an element in the tree. More...

int	unittest_wrapper_addrtree_cmpbit (const addrkey_t key1, const addrkey_t key2, addrlen_t n)
	Wrappers for static functions to unit test.

addrlen_t	unittest_wrapper_addrtree_bits_common (const addrkey_t s1, addrlen_t l1, const addrkey_t s2, addrlen_t l2, addrlen_t skip)

int	unittest_wrapper_addrtree_getbit (const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)

int	unittest_wrapper_addrtree_issub (const addrkey_t s1, addrlen_t l1, const addrkey_t s2, addrlen_t l2, addrlen_t skip)

Detailed Description

addrtree – radix tree for edns subnet cache.

Function Documentation

◆ edge_create()

static struct addredge* edge_create	(	struct addrnode *	node,
		const addrkey_t *	addr,
		addrlen_t	addrlen,
		struct addrnode *	parent_node,
		int	parent_index
	)

static

Create a new edge.

Parameters

node	Child node this edge will connect to.
addr	full key to this edge.
addrlen	length of relevant part of key for this node
parent_node	Parent node for node
parent_index	Index of child node at parent node

Returns: new addredge or NULL on failure

References addredge::len, addredge::node, addredge::parent_index, and addredge::parent_node.

Referenced by addrtree_insert().

◆ node_create()

static struct addrnode* node_create	(	struct addrtree *	tree,
		void *	elem,
		addrlen_t	scope,
		time_t	ttl
	)

static

Create a new node.

Parameters

tree	Tree the node lives in.
elem	Element to store at this node
scope	Scopemask from server reply
ttl	Element is valid up to this time. Absolute, seconds

Returns: new addrnode or NULL on failure

References addrnode::edge, addrnode::elem, addrnode::next, addrtree::node_count, addrnode::only_match_scope_zero, addrnode::parent_edge, addrnode::prev, addrnode::scope, and addrnode::ttl.

Referenced by addrtree_create(), and addrtree_insert().

◆ node_size()

static size_t node_size	(	const struct addrtree *	tree,
		const struct addrnode *	n
	)

inlinestatic

Size in bytes of node and parent edge.

Parameters

tree	tree the node lives in
n	node which size must be calculated

Returns: size in bytes.

References addrnode::elem, addredge::len, addrnode::parent_edge, and addrtree::sizefunc.

Referenced by addrtree_delete(), addrtree_insert(), and purge_node().

◆ addrtree_create()

struct addrtree* addrtree_create	(	addrlen_t	max_depth,
		void()(void , void *)	delfunc,
		size_t()(void )	sizefunc,
		void *	env,
		uint32_t	max_node_count
	)

Create a new tree.

Parameters

max_depth	Tree will cap keys to this length.
delfunc	f(element, env) delete element.
sizefunc	f(element) returning the size of element.
env	Module environment for alloc information.
max_node_count	Maximum size of this data structure in nodes. 0 for unlimited.

Returns: new addrtree or NULL on failure.

References addrtree::delfunc, addrtree::env, addrtree::first, addrtree::last, log_assert, addrtree::max_depth, addrtree::max_node_count, addrtree::node_count, node_create(), addrtree::size_bytes, and addrtree::sizefunc.

◆ clean_node()

static void clean_node	(	struct addrtree *	tree,
		struct addrnode *	node
	)

static

Scrub a node clean of elem.

Parameters

tree	tree the node lives in.
node	node to be cleaned.

References addrtree::delfunc, addrnode::elem, addrtree::env, addrnode::only_match_scope_zero, addrtree::size_bytes, and addrtree::sizefunc.

Referenced by addrtree_delete(), addrtree_insert(), and purge_node().

◆ purge_node()

static void purge_node	(	struct addrtree *	tree,
		struct addrnode *	node
	)

static

Purge a node from the tree.

Node and parentedge are cleaned and free'd.

Parameters

tree	Tree the node lives in.
node	Node to be freed

References clean_node(), addrnode::edge, lru_pop(), addredge::node, addrtree::node_count, node_size(), addrnode::parent_edge, addredge::parent_index, addredge::parent_node, addrtree::size_bytes, and addredge::str.

Referenced by addrtree_insert(), and lru_cleanup().

◆ lru_cleanup()

static void lru_cleanup ( struct addrtree * tree )

static

If a limit is set remove old nodes while above that limit.

Parameters

tree	Tree to be cleaned up.

Don't remove this node, it is either the root or we can't do without it because it has 2 children

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

References addrnode::edge, addrnode::elem, addrtree::first, lru_update(), addrtree::max_node_count, addrtree::node_count, addrnode::parent_edge, addredge::parent_node, and purge_node().

Referenced by addrtree_insert().

◆ addrtree_size()

size_t addrtree_size ( const struct addrtree * tree )

inline

Size of tree in bytes.

Parameters

tree Tree.

Returns: size of tree in bytes.

References addrtree::size_bytes.

Referenced by addrtree_delete().

◆ addrtree_delete()

void addrtree_delete ( struct addrtree * tree )

Free tree and all nodes below.

Parameters

tree	Tree to be freed.

References addrtree_size(), clean_node(), addrtree::first, log_assert, addrnode::next, node_size(), addrnode::parent_edge, addrtree::size_bytes, and addredge::str.

◆ getbit()

static int getbit	(	const addrkey_t *	addr,
		addrlen_t	addrlen,
		addrlen_t	n
	)

static

Get N'th bit from address.

Parameters

addr	address to inspect
addrlen	length of addr in bits
n	index of bit to test. Must be in range [0, addrlen)

Returns: 0 or 1

References log_assert.

Referenced by addrtree_find(), and addrtree_insert().

◆ cmpbit()

static int cmpbit	(	const addrkey_t *	key1,
		const addrkey_t *	key2,
		addrlen_t	n
	)

inlinestatic

Test for equality on N'th bit.

Returns: 0 for equal, 1 otherwise

Referenced by bits_common(), and unittest_wrapper_addrtree_cmpbit().

◆ bits_common()

static addrlen_t bits_common	(	const addrkey_t *	s1,
		addrlen_t	l1,
		const addrkey_t *	s2,
		addrlen_t	l2,
		addrlen_t	skip
	)

static

Common number of bits in prefix.

Parameters

s1	first prefix.
l1	length of s1 in bits.
s2	second prefix.
l2	length of s2 in bits.
skip	nr of bits already checked.

Returns: common number of bits.

References cmpbit(), and log_assert.

Referenced by addrtree_insert(), and issub().

◆ issub()

static int issub	(	const addrkey_t *	s1,
		addrlen_t	l1,
		const addrkey_t *	s2,
		addrlen_t	l2,
		addrlen_t	skip
	)

static

Tests if s1 is a substring of s2.

Parameters

s1	first prefix.
l1	length of s1 in bits.
s2	second prefix.
l2	length of s2 in bits.
skip	nr of bits already checked.

Returns: 1 for substring, 0 otherwise

References bits_common().

Referenced by addrtree_find().

◆ addrtree_insert()

void addrtree_insert	(	struct addrtree *	tree,
		const addrkey_t *	addr,
		addrlen_t	sourcemask,
		addrlen_t	scope,
		void *	elem,
		time_t	ttl,
		time_t	now,
		int	only_match_scope_zero
	)

Insert an element in the tree.

Failures are silent. Sourcemask and scope might be changed according to local policy. Caller should no longer access elem, it could be free'd now or later during future inserts.

Parameters

tree	Tree insert elem in.
addr	key for element lookup.
sourcemask	Length of addr in bits.
scope	Number of significant bits in addr.
elem	data to store in the tree.
ttl	elem is valid up to this time, seconds.
only_match_scope_zero	set for when query /0 has scope /0 answer.
now	Current time in seconds.

References bits_common(), clean_node(), addrnode::edge, edge_create(), addrnode::elem, getbit(), addredge::len, log_assert, lru_cleanup(), lru_push(), addrtree::max_depth, addredge::node, addrtree::node_count, node_create(), node_size(), addrnode::only_match_scope_zero, addredge::parent_index, addredge::parent_node, purge_node(), addrnode::scope, addrtree::size_bytes, addrtree::sizefunc, addredge::str, and addrnode::ttl.

◆ addrtree_find()

struct addrnode* addrtree_find	(	struct addrtree *	tree,
		const addrkey_t *	addr,
		addrlen_t	sourcemask,
		time_t	now
	)

Find a node containing an element in the tree.

Parameters

tree	Tree to search.
addr	key for element lookup.
sourcemask	Length of addr in bits.
now	Current time in seconds.

Returns: addrnode or NULL on miss.

References addrnode::edge, addrnode::elem, getbit(), issub(), addredge::len, log_assert, lru_update(), addredge::node, addrnode::only_match_scope_zero, addrnode::scope, addredge::str, and addrnode::ttl.

Functions

Detailed Description

Function Documentation

◆ edge_create()

◆ node_create()

◆ node_size()

◆ addrtree_create()

◆ clean_node()

◆ purge_node()

◆ lru_cleanup()

◆ addrtree_size()

◆ addrtree_delete()

◆ getbit()

◆ cmpbit()

◆ bits_common()

◆ issub()

◆ addrtree_insert()

◆ addrtree_find()