axa  2.2.0
Farsight Security Advanced Exchange Access (AXA)
axa_trie

Detailed Description

axa_trie contains AXA trie or patricia tree macros, data type definitions and function declarations.

These trie functions use patricia trees to recognize IP addresses and DNS domain names. IP address CIDR blocks or domains, each with a 32-bit value, are added to, looked up in, and deleted from trees. The result of a look-up is an array of 0 or more "hits" or values. Look-ups or reading is done without any locking, except periodically when the readers signal their disinterest in old data.

A successful look-up produces an array of hits for each of the matching CIDR blocks or domains. For example, lookup up "test.example.com" might yield an array consisting of all of the values for the "test.example.com" and "com" nodes in the trie.

IPv4, IPv6, and domain names are.maintained internally in separate three tries that can be viewed as a single trie from the outside.

Data Structures

struct  tval_list
 an array of values for a trie node More...
 
struct  hit
 A single value for a key found in the trie and hints about the source of the data that matched the key. More...
 
struct  hitlist_t
 The successful result of looking up a key is an array of "hits". More...
 
union  trie_key_t
 A trie key. More...
 
struct  trie_node
 The shape of a trie node does not matter except to the trie code and to trie users that manage lists of obsolete nodes for lock-free searching. More...
 
struct  trie_roots_t
 This is the handle on an AXA trie. More...
 

Macros

#define MAX_TRIE_IPV4_PREFIX   64
 IPv4 keys are one 64-bit word. More...
 
#define MAX_TRIE_IPV6_PREFIX   128
 IPv6 keys are two words. More...
 

Typedefs

typedef uint32_t tval_t
 A value at a trie node. More...
 
typedef struct tval_list tval_list_t
 trie value list More...
 
typedef struct hit hit_t
 A single value for a key found in the trie and hints about the source of the data that matched the key. More...
 
typedef struct trie_node trie_node_t
 a trie node More...
 
typedef uint16_t trie_bitlen_t
 valid bits in a trie key More...
 

Enumerations

enum  trie_type_t
 Each externally visible trie consists of one each of these internal types. More...
 

Functions

bool axa_tval_delete (trie_roots_t *roots, tval_list_t **tval_listp, tval_t val)
 Delete a value from an array of trie node values. More...
 
void axa_tval_add (trie_roots_t *roots, tval_list_t **tval_listp, tval_t new, uint padded_len, bool lock_free)
 Add a value to an array of values. More...
 
size_t axa_trie_to_watch (axa_p_watch_t *w, const trie_node_t *node, trie_type_t node_type, bool is_wild)
 Convert the key in a trie node to an AXA watch. More...
 
void axa_trie_node_free (trie_node_t *node)
 Free a trie node including its arrays of values. More...
 
void axa_trie_node_delete (trie_roots_t *roots, trie_type_t trie_type, trie_node_t *node, bool is_wild, tval_t tval)
 Remove a value from an AXA trie node and then delete the node from the trie if it is empty. More...
 
bool axa_trie_watch_add (axa_emsg_t *emsg, trie_roots_t *roots, trie_node_t **node, const axa_p_watch_t *watch, size_t watch_len, tval_t tval)
 Add a watch to an AXA trie. More...
 
void axa_trie_search_su (trie_roots_t *roots, const axa_socku_t *su, hitlist_t **hitlistp, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx)
 Search an AXA trie for an IP address. More...
 
bool axa_trie_search_dom (axa_emsg_t *emsg, trie_roots_t *roots, const uint8_t *name, uint name_len, hitlist_t **hitlistp, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx)
 Search an AXA trie for a DNS domain. More...
 
void axa_tries_free (trie_roots_t *roots)
 Free an AXA trie. More...
 
void axa_hitlist_append (const trie_roots_t *roots, hitlist_t **hitlistp, const tval_list_t *tval_list, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx)
 Append an array of values such as from a trie node to a "hit list". More...
 

Macro Definition Documentation

◆ MAX_TRIE_IPV4_PREFIX

#define MAX_TRIE_IPV4_PREFIX   64

IPv4 keys are one 64-bit word.

◆ MAX_TRIE_IPV6_PREFIX

#define MAX_TRIE_IPV6_PREFIX   128

IPv6 keys are two words.

Typedef Documentation

◆ tval_t

typedef uint32_t tval_t

A value at a trie node.

◆ tval_list_t

typedef struct tval_list tval_list_t

trie value list

◆ hit_t

typedef struct hit hit_t

A single value for a key found in the trie and hints about the source of the data that matched the key.

◆ trie_node_t

typedef struct trie_node trie_node_t

a trie node

◆ trie_bitlen_t

typedef uint16_t trie_bitlen_t

valid bits in a trie key

Enumeration Type Documentation

◆ trie_type_t

Each externally visible trie consists of one each of these internal types.

Enumerator
TRIE_IPV4 

IPv4 addresses.

TRIE_IPV6 

IPv6 addresses.

TRIE_DOM 

DNS domains.

Function Documentation

◆ axa_tval_delete()

bool axa_tval_delete ( trie_roots_t roots,
tval_list_t **  tval_listp,
tval_t  val 
)

Delete a value from an array of trie node values.

Parameters
[in]rootshandle on the trie.
[in]tval_listppointer to array from which the value should be removed
[in]valremove the first instance of this value if present
Return values
trueif an instance of the value was found and removed
falseif an instance of the value was not found

◆ axa_tval_add()

void axa_tval_add ( trie_roots_t roots,
tval_list_t **  tval_listp,
tval_t  new,
uint  padded_len,
bool  lock_free 
)

Add a value to an array of values.

Parameters
[in]rootshandle on the trie.
[in]tval_listppointer to array to which the value should be added
[in]newvalue to add
[in]padded_len0 or new length of the array including optional padding for future additions
[in]lock_freetrue if lock-free searching is supported by the trie.

◆ axa_trie_to_watch()

size_t axa_trie_to_watch ( axa_p_watch_t w,
const trie_node_t node,
trie_type_t  node_type,
bool  is_wild 
)

Convert the key in a trie node to an AXA watch.

Parameters
[out]wexisting watch that will be filled.
[in]nodeconvert the key in this AXA trie node
[in]node_typeTRIE_IPV4, TRIE_IPV6, or TRIE_DOM
[in]is_wildtrue if the resulting watch should be for an IP address CIDR block or a DNS wild card
Returns
overall size of the watch

◆ axa_trie_node_free()

void axa_trie_node_free ( trie_node_t node)

Free a trie node including its arrays of values.

The node must have already been deleted from the trie.

Parameters
[in]nodeto be destroyed

◆ axa_trie_node_delete()

void axa_trie_node_delete ( trie_roots_t roots,
trie_type_t  trie_type,
trie_node_t node,
bool  is_wild,
tval_t  tval 
)

Remove a value from an AXA trie node and then delete the node from the trie if it is empty.

Parameters
[in]rootshandle on the trie
[in]trie_typeTRIE_IPV4, TRIE_IPV6, or TRIE_DOM
[in]nodeto be changed
[in]is_wildtrue if the value is for a CIDR block or DNS wild card
[in]tvalvalue to be removed

◆ axa_trie_watch_add()

bool axa_trie_watch_add ( axa_emsg_t emsg,
trie_roots_t roots,
trie_node_t **  node,
const axa_p_watch_t watch,
size_t  watch_len,
tval_t  tval 
)

Add a watch to an AXA trie.

Create a node with a key derived from the watch if the node does not already exist and then add value to the node.

Parameters
[out]emsgwill contain the reason for a false result.
[in]rootshandle on the trie
[out]nodewill point to the node if not NULL.
[in]watchprovides the IP address or domain name for the key
[in]watch_lenis the length of the watch. It is usually less than sizeof(axa_p_watch_t) because maximum sized domain names are rare.
[in]tvalis the value that will be added to either the "wild" or "exact" array of values in the node.
Return values
trueif no errors were encountered. Node will be set if not NULL
falseerror was was encountered and emsg will contain the reason

◆ axa_trie_search_su()

void axa_trie_search_su ( trie_roots_t roots,
const axa_socku_t su,
hitlist_t **  hitlistp,
axa_nmsg_idx_t  field_idx,
axa_nmsg_idx_t  val_idx 
)

Search an AXA trie for an IP address.

Parameters
[in]rootshandle on the trie
[in]supoints to an axa_socku_t union containing the IP address
[in,out]hitlistpthe array of values in found trie nodes is appended to this array. It is created if *hitlistp is NULL and a value is found. More than one trie node can contribute values; for example a search for 10.2.3.4 can match nodes with keys 10.0.0.0/8, 10.2.0.0/16, and 10.2.3.4.
[in]field_idxis associated with each value added to the hitlistp array to let the caller remember which NMSG value caused each "hit"
[in]val_idxis associated with each value added to the hitlistp array

◆ axa_trie_search_dom()

bool axa_trie_search_dom ( axa_emsg_t emsg,
trie_roots_t roots,
const uint8_t *  name,
uint  name_len,
hitlist_t **  hitlistp,
axa_nmsg_idx_t  field_idx,
axa_nmsg_idx_t  val_idx 
)

Search an AXA trie for a DNS domain.

Parameters
[out]emsgwill contain the reason for a false result.
[in]rootshandle on the trie
[in]namepoints to the domain in wire format
[in]name_lenis the length of the domain
[in,out]hitlistpThe array of values in found trie nodes is appended to this array. It is created if *hitlistp is NULL and a value is found. More than one trie node can contribute values; for example a search for www.example.com can match nodes with keys www.example.com and *.com.
[in]field_idxis associated with each value added to the hit list to let the caller remember which NMSG value caused each "hit"
[in]val_idxis associated with each value added to the hitlistp array
Return values
trueif no errors were encountered.
falseerror such as a bad domain namewas was encountered. emsg will contain the reason.

◆ axa_tries_free()

void axa_tries_free ( trie_roots_t roots)

Free an AXA trie.

Parameters
[in]rootshandle on the trie to be destroyed.

◆ axa_hitlist_append()

void axa_hitlist_append ( const trie_roots_t roots,
hitlist_t **  hitlistp,
const tval_list_t tval_list,
axa_nmsg_idx_t  field_idx,
axa_nmsg_idx_t  val_idx 
)

Append an array of values such as from a trie node to a "hit list".

Parameters
[in]rootshandle on the trie
[in,out]hitlistpis the "hit list" array to which the value list will be added.
[in]tval_listis the list of values
[in]field_idxis associated with each value added to the hit list to let the caller remember which NMSG value caused each "hit".
[in]val_idxis associated with each value added to the hitlistp array