#include "suricata-common.h"
#include "util-debug.h"
#include "util-error.h"
#include "util-ip.h"
#include "util-cidr.h"
#include "util-unittest.h"
#include "util-memcmp.h"
#include "util-print.h"
#include "util-byte.h"
#include "util-radix6-tree.h"
#include "util-radix-tree-common.h"

Include dependency graph for util-radix6-tree.c:

Macros
#define	ADDRESS_BYTES (uint8_t)16

#define	NETMASK_MAX (uint8_t)128

#define	RADIX_TREE_TYPE SCRadix6Tree

#define	RADIX_NODE_TYPE SCRadix6Node

#define	RADIX_TREE_COMPARE_CALLBACK SCRadix6TreeCompareFunc

#define	RADIX_CONFIG_TYPE SCRadix6Config

#define	GET_IPV6(str)

#define	ADD_IPV6(str)

#define	REM_IPV6(str)

#define	ADD_IPV6_MASK(str, cidr)

#define	REM_IPV6_MASK(str, cidr)

Functions
SCRadix6Node *	SCRadix6TreeFindExactMatch (const SCRadix6Tree tree, const uint8_t key, void **user_data)

SCRadix6Node *	SCRadix6TreeFindNetblock (const SCRadix6Tree tree, const uint8_t key, const uint8_t netmask, void **user_data)

SCRadix6Node *	SCRadix6TreeFindBestMatch (const SCRadix6Tree tree, const uint8_t key, void **user_data)

SCRadix6Node *	SCRadix6TreeFindBestMatch2 (const SCRadix6Tree tree, const uint8_t key, void *user_data, uint8_t out_netmask)

SCRadix6Node *	SCRadix6AddKeyIPV6 (SCRadix6Tree tree, const SCRadix6Config config, const uint8_t key_stream, void user)
	Adds a new IPV6 address to the Radix6 tree. More...

SCRadix6Node *	SCRadix6AddKeyIPV6Netblock (SCRadix6Tree tree, const SCRadix6Config config, const uint8_t key_stream, uint8_t netmask, void user)
	Adds a new IPV6 netblock to the Radix6 tree. More...

bool	SCRadix6AddKeyIPV6String (SCRadix6Tree tree, const SCRadix6Config config, const char str, void user)
	Adds a new IPV6/netblock to the Radix6 tree from a string. More...

void	SCRadix6RemoveKeyIPV6 (SCRadix6Tree tree, const SCRadix6Config config, const uint8_t *key_stream)
	Removes an IPV6 address key(not a netblock) from the Radix6 tree. Instead of using this function, we can also used SCRadix6RemoveKeyIPV6Netblock(), by supplying a netmask value of 32. More...

void	SCRadix6RemoveKeyIPV6Netblock (SCRadix6Tree tree, const SCRadix6Config config, const uint8_t *key_stream, uint8_t netmask)
	Removes an IPV6 address netblock key from the tree. More...

void	SCRadix6PrintTree (SCRadix6Tree tree, const SCRadix6Config config)

SCRadix6Tree	SCRadix6TreeInitialize (void)

void	SCRadix6TreeRelease (SCRadix6Tree tree, const SCRadix6Config config)

int	SCRadix6ForEachNode (const SCRadix6Tree tree, SCRadix6ForEachNodeFunc Callback, void data)

bool	SCRadix6CompareTrees (const SCRadix6Tree t1, const SCRadix6Tree t2, SCRadix6TreeCompareFunc Callback)

void	SCRadix6RegisterTests (void)

Detailed Description

Author: Victor Julien victo.nosp@m.r@in.nosp@m.linia.nosp@m.c.ne.nosp@m.t; Anoop Saldanha anoop.nosp@m.sald.nosp@m.anha@.nosp@m.gmai.nosp@m.l.com

Implementation of radix trees

Definition in file util-radix6-tree.c.

Macro Definition Documentation

◆ ADD_IPV6

#define ADD_IPV6 ( str )

Value:

GET_IPV6((str)); \

SCRadix6AddKeyIPV6(&tree, &ut_ip_radix6_config, (uint8_t *)&(sa).sin6_addr, NULL);

Definition at line 436 of file util-radix6-tree.c.

◆ ADD_IPV6_MASK

#define ADD_IPV6_MASK	(	str,
		cidr
	)

Value:

    GET_IPV6((str));                                                                               \
    SCRadix6AddKeyIPV6Netblock(                                                                    \
            &tree, &ut_ip_radix6_config, (uint8_t *)&(sa).sin6_addr, (cidr), NULL);

Definition at line 444 of file util-radix6-tree.c.

◆ ADDRESS_BYTES

#define ADDRESS_BYTES (uint8_t)16

Definition at line 39 of file util-radix6-tree.c.

◆ GET_IPV6

#define GET_IPV6 ( str )

Value:

    SCLogDebug("setting up %s", (str));                                                            \
    memset(&(sa), 0, sizeof((sa)));                                                                \
    FAIL_IF(inet_pton(AF_INET6, (str), &(sa).sin6_addr) <= 0);

Definition at line 431 of file util-radix6-tree.c.

◆ NETMASK_MAX

#define NETMASK_MAX (uint8_t)128

Definition at line 40 of file util-radix6-tree.c.

◆ RADIX_CONFIG_TYPE

#define RADIX_CONFIG_TYPE SCRadix6Config

Definition at line 45 of file util-radix6-tree.c.

◆ RADIX_NODE_TYPE

#define RADIX_NODE_TYPE SCRadix6Node

Definition at line 43 of file util-radix6-tree.c.

◆ RADIX_TREE_COMPARE_CALLBACK

#define RADIX_TREE_COMPARE_CALLBACK SCRadix6TreeCompareFunc

Definition at line 44 of file util-radix6-tree.c.

◆ RADIX_TREE_TYPE

#define RADIX_TREE_TYPE SCRadix6Tree

Definition at line 42 of file util-radix6-tree.c.

◆ REM_IPV6

#define REM_IPV6 ( str )

Value:

GET_IPV6((str)); \

SCRadix6RemoveKeyIPV6(&tree, &ut_ip_radix6_config, (uint8_t *)&(sa).sin6_addr);

Definition at line 440 of file util-radix6-tree.c.

◆ REM_IPV6_MASK

#define REM_IPV6_MASK	(	str,
		cidr
	)

Value:

GET_IPV6((str)); \

SCRadix6RemoveKeyIPV6Netblock(&tree, &ut_ip_radix6_config, (uint8_t *)&(sa).sin6_addr, (cidr));

Definition at line 449 of file util-radix6-tree.c.

Function Documentation

◆ SCRadix6AddKeyIPV6()

SCRadix6Node* SCRadix6AddKeyIPV6	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config,
		const uint8_t *	key_stream,
		void *	user
	)

Adds a new IPV6 address to the Radix6 tree.

Parameters

key_stream	Data that has to be added to the Radix6 tree. In this case a pointer to an IPV6 address
tree	Pointer to the Radix6 tree
user	Pointer to the user data that has to be associated with the key

Return values

node	Pointer to the newly created node

Definition at line 196 of file util-radix6-tree.c.

◆ SCRadix6AddKeyIPV6Netblock()

SCRadix6Node* SCRadix6AddKeyIPV6Netblock	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config,
		const uint8_t *	key_stream,
		uint8_t	netmask,
		void *	user
	)

Adds a new IPV6 netblock to the Radix6 tree.

Parameters

key_stream	Data that has to be added to the Radix6 tree. In this case a pointer to an IPV6 netblock
tree	Pointer to the Radix6 tree
user	Pointer to the user data that has to be associated with the key
netmask	The netmask (cidr) if we are adding a netblock

Return values

node	Pointer to the newly created node

Definition at line 214 of file util-radix6-tree.c.

◆ SCRadix6AddKeyIPV6String()

bool SCRadix6AddKeyIPV6String	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config,
		const char *	str,
		void *	user
	)

Adds a new IPV6/netblock to the Radix6 tree from a string.

Parameters

str	IPV6 string with optional /cidr netmask
tree	Pointer to the Radix6 tree
user	Pointer to the user data that has to be associated with the key

Return values

bool	true if node was added, false otherwise

If the function returns false, sc_errno is set:

SC_EEXIST: Node already exists
SC_EINVAL: Parameter value error
SC_ENOMEM: Memory allocation failed

Definition at line 262 of file util-radix6-tree.c.

References CIDRGetIPv6(), PrintInet(), SC_EINVAL, sc_errno, SCLogWarning, str, StringParseU8RangeCheck(), and strlcpy().

Here is the call graph for this function:

◆ SCRadix6CompareTrees()

bool SCRadix6CompareTrees	(	const SCRadix6Tree *	t1,
		const SCRadix6Tree *	t2,
		SCRadix6TreeCompareFunc	Callback
	)

Definition at line 418 of file util-radix6-tree.c.

◆ SCRadix6ForEachNode()

int SCRadix6ForEachNode	(	const SCRadix6Tree *	tree,
		SCRadix6ForEachNodeFunc	Callback,
		void *	data
	)

Definition at line 411 of file util-radix6-tree.c.

References SCRadix6Tree_::head.

◆ SCRadix6PrintTree()

void SCRadix6PrintTree	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config
	)

Definition at line 355 of file util-radix6-tree.c.

◆ SCRadix6RegisterTests()

void SCRadix6RegisterTests ( void )

Definition at line 946 of file util-radix6-tree.c.

References UtRegisterTest().

Here is the call graph for this function:

◆ SCRadix6RemoveKeyIPV6()

void SCRadix6RemoveKeyIPV6	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config,
		const uint8_t *	key_stream
	)

Removes an IPV6 address key(not a netblock) from the Radix6 tree. Instead of using this function, we can also used SCRadix6RemoveKeyIPV6Netblock(), by supplying a netmask value of 32.

Parameters

key_stream	Data that has to be removed from the Radix6 tree. In this case an IPV6 address
tree	Pointer to the Radix6 tree from which the key has to be removed

Definition at line 335 of file util-radix6-tree.c.

◆ SCRadix6RemoveKeyIPV6Netblock()

void SCRadix6RemoveKeyIPV6Netblock	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config,
		const uint8_t *	key_stream,
		uint8_t	netmask
	)

Removes an IPV6 address netblock key from the tree.

Parameters

key_stream	Data that has to be removed from the tree. In this case an IPV6 address with netmask.
tree	Pointer to the tree from which the key has to be removed

Definition at line 349 of file util-radix6-tree.c.

◆ SCRadix6TreeFindBestMatch()

SCRadix6Node* SCRadix6TreeFindBestMatch	(	const SCRadix6Tree *	tree,
		const uint8_t *	key,
		void **	user_data
	)

Definition at line 173 of file util-radix6-tree.c.

Referenced by IPOnlyMatchPacket(), and SCHInfoGetIPv6HostOSFlavour().

Here is the caller graph for this function:

◆ SCRadix6TreeFindBestMatch2()

SCRadix6Node* SCRadix6TreeFindBestMatch2	(	const SCRadix6Tree *	tree,
		const uint8_t *	key,
		void **	user_data,
		uint8_t *	out_netmask
	)

Definition at line 179 of file util-radix6-tree.c.

◆ SCRadix6TreeFindExactMatch()

SCRadix6Node* SCRadix6TreeFindExactMatch	(	const SCRadix6Tree *	tree,
		const uint8_t *	key,
		void **	user_data
	)

Definition at line 161 of file util-radix6-tree.c.

◆ SCRadix6TreeFindNetblock()

SCRadix6Node* SCRadix6TreeFindNetblock	(	const SCRadix6Tree *	tree,
		const uint8_t *	key,
		const uint8_t	netmask,
		void **	user_data
	)

Definition at line 167 of file util-radix6-tree.c.

◆ SCRadix6TreeInitialize()

SCRadix6Tree SCRadix6TreeInitialize ( void )

Definition at line 360 of file util-radix6-tree.c.

References SC_RADIX6_TREE_INITIALIZER.

Referenced by IPOnlyInit(), and SRepInit().

Here is the caller graph for this function:

◆ SCRadix6TreeRelease()

void SCRadix6TreeRelease	(	SCRadix6Tree *	tree,
		const SCRadix6Config *	config
	)

Definition at line 366 of file util-radix6-tree.c.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ ADD_IPV6

◆ ADD_IPV6_MASK

◆ ADDRESS_BYTES

◆ GET_IPV6

◆ NETMASK_MAX

◆ RADIX_CONFIG_TYPE

◆ RADIX_NODE_TYPE

◆ RADIX_TREE_COMPARE_CALLBACK

◆ RADIX_TREE_TYPE

◆ REM_IPV6

◆ REM_IPV6_MASK

Function Documentation

◆ SCRadix6AddKeyIPV6()

◆ SCRadix6AddKeyIPV6Netblock()

◆ SCRadix6AddKeyIPV6String()

◆ SCRadix6CompareTrees()

◆ SCRadix6ForEachNode()

◆ SCRadix6PrintTree()

◆ SCRadix6RegisterTests()

◆ SCRadix6RemoveKeyIPV6()

◆ SCRadix6RemoveKeyIPV6Netblock()

◆ SCRadix6TreeFindBestMatch()

◆ SCRadix6TreeFindBestMatch2()

◆ SCRadix6TreeFindExactMatch()

◆ SCRadix6TreeFindNetblock()

◆ SCRadix6TreeInitialize()

◆ SCRadix6TreeRelease()