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

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

Macros
#define	ADDRESS_BYTES (uint8_t)4

#define	NETMASK_MAX (uint8_t)32

#define	RADIX_TREE_TYPE SCRadix4Tree

#define	RADIX_NODE_TYPE SCRadix4Node

#define	RADIX_CONFIG_TYPE SCRadix4Config

#define	RADIX_TREE_COMPARE_CALLBACK SCRadix4TreeCompareFunc

#define	GET_IPV4(str)

#define	ADD_IPV4(str)

#define	REM_IPV4(str)

#define	ADD_IPV4_MASK(str, cidr)

#define	REM_IPV4_MASK(str, cidr)

Functions
SCRadix4Node *	SCRadix4TreeFindExactMatch (const SCRadix4Tree tree, const uint8_t key, void **user_data)

SCRadix4Node *	SCRadix4TreeFindNetblock (const SCRadix4Tree tree, const uint8_t key, const uint8_t netmask, void **user_data)

SCRadix4Node *	SCRadix4TreeFindBestMatch (const SCRadix4Tree tree, const uint8_t key, void **user_data)

SCRadix4Node *	SCRadix4TreeFindBestMatch2 (const SCRadix4Tree tree, const uint8_t key, void *user_data, uint8_t out_netmask)

SCRadix4Tree	SCRadix4TreeInitialize (void)

void	SCRadix4TreeRelease (SCRadix4Tree tree, const SCRadix4Config config)

SCRadix4Node *	SCRadix4AddKeyIPV4 (SCRadix4Tree tree, const SCRadix4Config config, const uint8_t key_stream, void user)
	Adds a new IPV4 address to the Radix4 tree. More...

SCRadix4Node *	SCRadix4AddKeyIPV4Netblock (SCRadix4Tree tree, const SCRadix4Config config, const uint8_t key_stream, uint8_t netmask, void user)
	Adds a new IPV4 netblock to the Radix4 tree. More...

bool	SCRadix4AddKeyIPV4String (SCRadix4Tree tree, const SCRadix4Config config, const char str, void user)
	Adds a new IPV4/netblock to the Radix4 tree from a string. More...

void	SCRadix4RemoveKeyIPV4 (SCRadix4Tree tree, const SCRadix4Config config, const uint8_t *key_stream)
	Removes an IPV4 address key(not a netblock) from the Radix4 tree. Instead of using this function, we can also used SCRadix4RemoveKeyIPV4Netblock(), by supplying a netmask value of 32. More...

void	SCRadix4RemoveKeyIPV4Netblock (SCRadix4Tree tree, const SCRadix4Config config, const uint8_t *key_stream, uint8_t netmask)
	Removes an IPV4 address netblock key from the Radix4 tree. More...

void	SCRadix4PrintTree (SCRadix4Tree tree, const SCRadix4Config config)

int	SCRadix4ForEachNode (const SCRadix4Tree tree, SCRadix4ForEachNodeFunc Callback, void data)

bool	SCRadix4CompareTrees (const SCRadix4Tree t1, const SCRadix4Tree t2, SCRadix4TreeCompareFunc Callback)

void	SCRadix4RegisterTests (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 tree for IPv4

Definition in file util-radix4-tree.c.

Macro Definition Documentation

◆ ADD_IPV4

#define ADD_IPV4 ( str )

Value:

GET_IPV4((str)); \

SCRadix4AddKeyIPV4(&tree, &ut_ip_radix4_config, (uint8_t *)&(sa).sin_addr, NULL);

Definition at line 377 of file util-radix4-tree.c.

◆ ADD_IPV4_MASK

#define ADD_IPV4_MASK	(	str,
		cidr
	)

Value:

    GET_IPV4((str));                                                                               \
    SCRadix4AddKeyIPV4Netblock(                                                                    \
            &tree, &ut_ip_radix4_config, (uint8_t *)&(sa).sin_addr, (cidr), NULL);

Definition at line 385 of file util-radix4-tree.c.

◆ ADDRESS_BYTES

#define ADDRESS_BYTES (uint8_t)4

Definition at line 38 of file util-radix4-tree.c.

◆ GET_IPV4

#define GET_IPV4 ( str )

Value:

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

Definition at line 372 of file util-radix4-tree.c.

◆ NETMASK_MAX

#define NETMASK_MAX (uint8_t)32

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

◆ RADIX_CONFIG_TYPE

#define RADIX_CONFIG_TYPE SCRadix4Config

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

◆ RADIX_NODE_TYPE

#define RADIX_NODE_TYPE SCRadix4Node

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

◆ RADIX_TREE_COMPARE_CALLBACK

#define RADIX_TREE_COMPARE_CALLBACK SCRadix4TreeCompareFunc

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

◆ RADIX_TREE_TYPE

#define RADIX_TREE_TYPE SCRadix4Tree

Definition at line 41 of file util-radix4-tree.c.

◆ REM_IPV4

#define REM_IPV4 ( str )

Value:

GET_IPV4((str)); \

SCRadix4RemoveKeyIPV4(&tree, &ut_ip_radix4_config, (uint8_t *)&(sa).sin_addr);

Definition at line 381 of file util-radix4-tree.c.

◆ REM_IPV4_MASK

#define REM_IPV4_MASK	(	str,
		cidr
	)

Value:

GET_IPV4((str)); \

SCRadix4RemoveKeyIPV4Netblock(&tree, &ut_ip_radix4_config, (uint8_t *)&(sa).sin_addr, (cidr));

Definition at line 390 of file util-radix4-tree.c.

Function Documentation

◆ SCRadix4AddKeyIPV4()

SCRadix4Node* SCRadix4AddKeyIPV4	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config,
		const uint8_t *	key_stream,
		void *	user
	)

Adds a new IPV4 address to the Radix4 tree.

Parameters

key_stream	Data that has to be added to the Radix4 tree. In this case a pointer to an IPV4 address
tree	Pointer to the Radix4 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 188 of file util-radix4-tree.c.

◆ SCRadix4AddKeyIPV4Netblock()

SCRadix4Node* SCRadix4AddKeyIPV4Netblock	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config,
		const uint8_t *	key_stream,
		uint8_t	netmask,
		void *	user
	)

Adds a new IPV4 netblock to the Radix4 tree.

Parameters

key_stream	Data that has to be added to the Radix4 tree. In this case a pointer to an IPV4 netblock
tree	Pointer to the Radix4 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 206 of file util-radix4-tree.c.

◆ SCRadix4AddKeyIPV4String()

bool SCRadix4AddKeyIPV4String	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config,
		const char *	str,
		void *	user
	)

Adds a new IPV4/netblock to the Radix4 tree from a string.

Parameters

str	IPV4 string with optional /cidr netmask
tree	Pointer to the Radix4 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 227 of file util-radix4-tree.c.

References RadixUserData::netmask, SC_EINVAL, sc_errno, str, StringParseU8RangeCheck(), and strlcpy().

Here is the call graph for this function:

◆ SCRadix4CompareTrees()

bool SCRadix4CompareTrees	(	const SCRadix4Tree *	t1,
		const SCRadix4Tree *	t2,
		SCRadix4TreeCompareFunc	Callback
	)

Definition at line 359 of file util-radix4-tree.c.

◆ SCRadix4ForEachNode()

int SCRadix4ForEachNode	(	const SCRadix4Tree *	tree,
		SCRadix4ForEachNodeFunc	Callback,
		void *	data
	)

Definition at line 352 of file util-radix4-tree.c.

References SCRadix4Tree_::head.

◆ SCRadix4PrintTree()

void SCRadix4PrintTree	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config
	)

Definition at line 303 of file util-radix4-tree.c.

◆ SCRadix4RegisterTests()

void SCRadix4RegisterTests ( void )

Definition at line 922 of file util-radix4-tree.c.

References UtRegisterTest().

Here is the call graph for this function:

◆ SCRadix4RemoveKeyIPV4()

void SCRadix4RemoveKeyIPV4	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config,
		const uint8_t *	key_stream
	)

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

Parameters

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

Definition at line 282 of file util-radix4-tree.c.

◆ SCRadix4RemoveKeyIPV4Netblock()

void SCRadix4RemoveKeyIPV4Netblock	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config,
		const uint8_t *	key_stream,
		uint8_t	netmask
	)

Removes an IPV4 address netblock key from the Radix4 tree.

Parameters

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

Definition at line 296 of file util-radix4-tree.c.

References SCLogNotice.

◆ SCRadix4TreeFindBestMatch()

SCRadix4Node* SCRadix4TreeFindBestMatch	(	const SCRadix4Tree *	tree,
		const uint8_t *	key,
		void **	user_data
	)

Definition at line 154 of file util-radix4-tree.c.

Referenced by IPOnlyMatchPacket(), and SCHInfoGetIPv4HostOSFlavour().

Here is the caller graph for this function:

◆ SCRadix4TreeFindBestMatch2()

SCRadix4Node* SCRadix4TreeFindBestMatch2	(	const SCRadix4Tree *	tree,
		const uint8_t *	key,
		void **	user_data,
		uint8_t *	out_netmask
	)

Definition at line 160 of file util-radix4-tree.c.

◆ SCRadix4TreeFindExactMatch()

SCRadix4Node* SCRadix4TreeFindExactMatch	(	const SCRadix4Tree *	tree,
		const uint8_t *	key,
		void **	user_data
	)

Definition at line 142 of file util-radix4-tree.c.

◆ SCRadix4TreeFindNetblock()

SCRadix4Node* SCRadix4TreeFindNetblock	(	const SCRadix4Tree *	tree,
		const uint8_t *	key,
		const uint8_t	netmask,
		void **	user_data
	)

Definition at line 148 of file util-radix4-tree.c.

◆ SCRadix4TreeInitialize()

SCRadix4Tree SCRadix4TreeInitialize ( void )

Definition at line 166 of file util-radix4-tree.c.

References SC_RADIX4_TREE_INITIALIZER.

Referenced by IPOnlyInit(), and SRepInit().

Here is the caller graph for this function:

◆ SCRadix4TreeRelease()

void SCRadix4TreeRelease	(	SCRadix4Tree *	tree,
		const SCRadix4Config *	config
	)

Definition at line 172 of file util-radix4-tree.c.

Referenced by DefragTreeDestroy(), IPOnlyDeinit(), SCHInfoCleanResources(), and SRepDestroy().

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ ADD_IPV4

◆ ADD_IPV4_MASK

◆ ADDRESS_BYTES

◆ GET_IPV4

◆ NETMASK_MAX

◆ RADIX_CONFIG_TYPE

◆ RADIX_NODE_TYPE

◆ RADIX_TREE_COMPARE_CALLBACK

◆ RADIX_TREE_TYPE

◆ REM_IPV4

◆ REM_IPV4_MASK

Function Documentation

◆ SCRadix4AddKeyIPV4()

◆ SCRadix4AddKeyIPV4Netblock()

◆ SCRadix4AddKeyIPV4String()

◆ SCRadix4CompareTrees()

◆ SCRadix4ForEachNode()

◆ SCRadix4PrintTree()

◆ SCRadix4RegisterTests()

◆ SCRadix4RemoveKeyIPV4()

◆ SCRadix4RemoveKeyIPV4Netblock()

◆ SCRadix4TreeFindBestMatch()

◆ SCRadix4TreeFindBestMatch2()

◆ SCRadix4TreeFindExactMatch()

◆ SCRadix4TreeFindNetblock()

◆ SCRadix4TreeInitialize()

◆ SCRadix4TreeRelease()