NLnet Labs Documentation - Unbound - Doxygen

This file contains structures combining types and functions to manipulate those structures that help building DNS lookup trees. More...

#include "util/rbtree.h"

Data Structures
struct	name_tree_node
	Tree of domain names. More...

struct	addr_tree_node
	Tree of IP addresses. More...

Functions
void	name_tree_init (rbtree_type *tree)
	Init a name tree to be empty. More...

int	name_tree_insert (rbtree_type tree, struct name_tree_node node, uint8_t *name, size_t len, int labs, uint16_t dclass)
	insert element into name tree. More...

void	name_tree_init_parents (rbtree_type *tree)
	Initialize parent pointers in name tree. More...

struct name_tree_node *	name_tree_find (rbtree_type tree, uint8_t name, size_t len, int labs, uint16_t dclass)
	Lookup exact match in name tree. More...

struct name_tree_node *	name_tree_lookup (rbtree_type tree, uint8_t name, size_t len, int labs, uint16_t dclass)
	Lookup closest encloser in name tree. More...

int	name_tree_next_root (rbtree_type tree, uint16_t dclass)
	Find next root item in name tree. More...

void	addr_tree_init (rbtree_type *tree)
	Init addr tree to be empty. More...

void	addr_tree_addrport_init (rbtree_type *tree)
	Init addr tree to be empty. More...

int	addr_tree_insert (rbtree_type tree, struct addr_tree_node node, struct sockaddr_storage *addr, socklen_t addrlen, int net)
	insert element into addr tree. More...

void	addr_tree_init_parents (rbtree_type *tree)
	Initialize parent pointers in addr tree. More...

void	addr_tree_init_parents_node (struct addr_tree_node *node)
	Initialize parent pointers in partial addr tree. More...

struct addr_tree_node *	addr_tree_lookup (rbtree_type tree, struct sockaddr_storage addr, socklen_t addrlen)
	Lookup closest encloser in addr tree. More...

struct addr_tree_node *	addr_tree_find (rbtree_type tree, struct sockaddr_storage addr, socklen_t addrlen, int net)
	Find element in addr tree. More...

int	name_tree_compare (const void k1, const void k2)
	compare name tree nodes

int	addr_tree_compare (const void k1, const void k2)
	compare addr tree nodes

int	addr_tree_addrport_compare (const void k1, const void k2)
	compare addr tree nodes (address and port only)

Detailed Description

This file contains structures combining types and functions to manipulate those structures that help building DNS lookup trees.

Function Documentation

◆ name_tree_init()

void name_tree_init ( rbtree_type * tree )

Init a name tree to be empty.

Parameters

tree to init.

References name_tree_compare(), and rbtree_init().

Referenced by dns64_init(), priv_apply_cfg(), priv_create(), and setup_domain_limits().

◆ name_tree_insert()

int name_tree_insert	(	rbtree_type *	tree,
		struct name_tree_node *	node,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)

insert element into name tree.

Parameters

tree	name tree
node	node element (at start of a structure that caller has allocated).
name	name to insert (wireformat) this node has been allocated by the caller and it itself inserted.
len	length of name
labs	labels in name
dclass	class of name

Returns: false on error (duplicate element).

References rbnode_type::key, addr_tree_node::node, rbnode_type::parent, and rbtree_insert().

Referenced by caps_white_apply_cfg(), domain_limit_findcreate(), hints_insert(), and read_names().

◆ name_tree_init_parents()

void name_tree_init_parents ( rbtree_type * tree )

Initialize parent pointers in name tree.

Should be performed after insertions are done, before lookups

Parameters

tree name tree

References name_tree_node::dclass, dname_lab_cmp(), name_tree_node::labs, name_tree_node::name, name_tree_node::node, rbnode_type::parent, name_tree_node::parent, and RBTREE_FOR.

Referenced by caps_white_apply_cfg(), dns64_apply_cfg(), priv_apply_cfg(), and setup_domain_limits().

◆ name_tree_find()

struct name_tree_node* name_tree_find	(	rbtree_type *	tree,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)

Lookup exact match in name tree.

Parameters

tree	name tree
name	wireformat name
len	length of name
labs	labels in name
dclass	class of name

Returns: node or NULL if not found.

References name_tree_node::dclass, rbnode_type::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, and rbtree_search().

Referenced by domain_limit_findcreate(), hints_add_stub(), hints_delete_stub(), and hints_find().

◆ name_tree_lookup()

struct name_tree_node* name_tree_lookup	(	rbtree_type *	tree,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)

Lookup closest encloser in name tree.

Parameters

tree	name tree
name	wireformat name
len	length of name
labs	labels in name
dclass	class of name

Returns: closest enclosing node (could be equal) or NULL if not found.

References name_tree_node::dclass, dname_lab_cmp(), rbnode_type::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, name_tree_node::parent, and rbtree_find_less_equal().

Referenced by dns64_always_synth_for_qname(), hints_lookup_stub(), infra_find_ratelimit(), is_caps_whitelisted(), and priv_lookup_name().

◆ name_tree_next_root()

int name_tree_next_root	(	rbtree_type *	tree,
		uint16_t *	dclass
	)

Find next root item in name tree.

Parameters

tree	the nametree.
dclass	the class to look for next (or higher).

Returns: false if no classes found, true means class put into c.

References name_tree_node::dclass, dname_is_root(), rbnode_type::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, rbtree_find_less_equal(), rbtree_first(), rbtree_next(), and RBTREE_NULL.

Referenced by hints_next_root().

◆ addr_tree_init()

void addr_tree_init ( rbtree_type * tree )

Init addr tree to be empty.

Parameters

tree to init.

References addr_tree_compare(), and rbtree_init().

Referenced by acl_list_apply_cfg(), donotq_apply_cfg(), edns_strings_apply_cfg(), lz_enter_override(), priv_apply_cfg(), priv_create(), respip_set_create(), setup_wait_limits(), and tcl_list_apply_cfg().

◆ addr_tree_addrport_init()

void addr_tree_addrport_init ( rbtree_type * tree )

Init addr tree to be empty.

The comparison function to be used is addr_tree_addrport_compare.

Parameters

tree to init.

References addr_tree_addrport_compare(), and rbtree_init().

Referenced by acl_interface_init().

◆ addr_tree_insert()

int addr_tree_insert	(	rbtree_type *	tree,
		struct addr_tree_node *	node,
		struct sockaddr_storage *	addr,
		socklen_t	addrlen,
		int	net
	)

insert element into addr tree.

Parameters

tree	addr tree
node	node element (at start of a structure that caller has allocated).
addr	to insert (copied).
addrlen	length of addr
net	size of subnet.

Returns: false on error (duplicate element).

References addr_tree_node::addr, addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, rbnode_type::parent, and rbtree_insert().

Referenced by acl_list_insert(), donotq_insert(), lz_enter_override(), read_addrs(), respip_sockaddr_find_or_create(), and tcl_list_insert().

◆ addr_tree_init_parents()

void addr_tree_init_parents ( rbtree_type * tree )

Initialize parent pointers in addr tree.

Should be performed after insertions are done, before lookups

Parameters

tree addr tree

References addr_tree_init_parents_node(), and rbtree_first().

Referenced by acl_list_apply_cfg(), donotq_apply_cfg(), priv_apply_cfg(), respip_sockaddr_delete(), rpz_finish_config(), setup_wait_limits(), and tcl_list_apply_cfg().

◆ addr_tree_init_parents_node()

void addr_tree_init_parents_node ( struct addr_tree_node * node )

Initialize parent pointers in partial addr tree.

Reinitialize pointer for part of tree, used after node deletion

Parameters

node	node to start parent pointer initialization for.

References addr_tree_node::addr, addr_in_common(), addr_tree_node::addrlen, addr_tree_node::net, addr_tree_node::node, rbnode_type::parent, addr_tree_node::parent, rbtree_next(), and RBTREE_NULL.

Referenced by addr_tree_init_parents(), and respip_sockaddr_delete().

◆ addr_tree_lookup()

struct addr_tree_node* addr_tree_lookup	(	rbtree_type *	tree,
		struct sockaddr_storage *	addr,
		socklen_t	addrlen
	)

Lookup closest encloser in addr tree.

Parameters

tree	addr tree
addr	to lookup.
addrlen	length of addr

Returns: closest enclosing node (could be equal) or NULL if not found.

References addr_tree_node::addr, addr_in_common(), addr_is_ip6(), addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, addr_tree_node::parent, and rbtree_find_less_equal().

Referenced by acl_addr_lookup(), donotq_lookup(), edns_string_addr_lookup(), infra_wait_limit_allowed(), priv_lookup_addr(), respip_addr_lookup(), and tcl_addr_lookup().

◆ addr_tree_find()

struct addr_tree_node* addr_tree_find	(	rbtree_type *	tree,
		struct sockaddr_storage *	addr,
		socklen_t	addrlen,
		int	net
	)

Find element in addr tree.

(search a netblock, not a match for an address)

Parameters

tree	addr tree
addr	netblock to lookup.
addrlen	length of addr
net	size of subnet

Returns: addr tree element, or NULL if not found.

References addr_tree_node::addr, addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, and rbtree_search().

Referenced by acl_find_or_create(), respip_sockaddr_find_or_create(), rpz_clientip_remove_trigger_rr(), verify_respip_set_actions(), and verify_rrset().