FD.io VPP  v18.07-34-g55fbdb9
Vector Packet Processing
ip4_mtrie.h File Reference
+ Include dependency graph for ip4_mtrie.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  ip4_fib_mtrie_16_ply_t_
 
struct  ip4_fib_mtrie_8_ply_t_
 One ply of the 4 ply mtrie fib. More...
 
struct  ip4_fib_mtrie_t
 The mutiway-TRIE. More...
 

Macros

#define IP4_FIB_MTRIE_LEAF_EMPTY   (1 + 2*0)
 
#define PLY_16_SIZE   (1<<16)
 the 16 way stride that is the top PLY of the mtrie We do not maintain the count of 'real' leaves in this PLY, since it is never removed. More...
 

Typedefs

typedef u32 ip4_fib_mtrie_leaf_t
 
typedef struct ip4_fib_mtrie_16_ply_t_ ip4_fib_mtrie_16_ply_t
 
typedef struct ip4_fib_mtrie_8_ply_t_ ip4_fib_mtrie_8_ply_t
 One ply of the 4 ply mtrie fib. More...
 

Functions

 STATIC_ASSERT (0==sizeof(ip4_fib_mtrie_8_ply_t)%CLIB_CACHE_LINE_BYTES,"IP4 Mtrie ply cache line")
 
void ip4_mtrie_init (ip4_fib_mtrie_t *m)
 Initialise an mtrie. More...
 
void ip4_mtrie_free (ip4_fib_mtrie_t *m)
 Free an mtrie, It must be emty when free'd. More...
 
void ip4_fib_mtrie_route_add (ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index)
 Add a route/rntry to the mtrie. More...
 
void ip4_fib_mtrie_route_del (ip4_fib_mtrie_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index)
 remove a route/rntry to the mtrie More...
 
uword ip4_fib_mtrie_memory_usage (ip4_fib_mtrie_t *m)
 return the memory used by the table More...
 
static u32 ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
 Is the leaf terminal (i.e. More...
 
static u32 ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
 From the stored slot value extract the LB index value. More...
 
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
 Lookup step. More...
 
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t *m, const ip4_address_t *dst_address)
 Lookup step number 1. More...
 

Variables

format_function_t format_ip4_fib_mtrie
 Format/display the contents of the mtrie. More...
 
ip4_fib_mtrie_8_ply_tip4_ply_pool
 A global pool of 8bit stride plys. More...
 

Macro Definition Documentation

#define IP4_FIB_MTRIE_LEAF_EMPTY   (1 + 2*0)

Definition at line 54 of file ip4_mtrie.h.

#define PLY_16_SIZE   (1<<16)

the 16 way stride that is the top PLY of the mtrie We do not maintain the count of 'real' leaves in this PLY, since it is never removed.

The FIB will destroy the mtrie and the ply once the FIB is destroyed.

Definition at line 62 of file ip4_mtrie.h.

Typedef Documentation

One ply of the 4 ply mtrie fib.

Definition at line 52 of file ip4_mtrie.h.

Function Documentation

static u32 ip4_fib_mtrie_leaf_get_adj_index ( ip4_fib_mtrie_leaf_t  n)
inlinestatic

From the stored slot value extract the LB index value.

Definition at line 192 of file ip4_mtrie.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static u32 ip4_fib_mtrie_leaf_is_terminal ( ip4_fib_mtrie_leaf_t  n)
inlinestatic

Is the leaf terminal (i.e.

an LB index) or non-terminak (i.e. a PLY index)

Definition at line 183 of file ip4_mtrie.h.

+ Here is the caller graph for this function:

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step ( const ip4_fib_mtrie_t m,
ip4_fib_mtrie_leaf_t  current_leaf,
const ip4_address_t dst_address,
u32  dst_address_byte_index 
)
inlinestatic

Lookup step.

Processes 1 byte of 4 byte ip4 address.

Definition at line 202 of file ip4_mtrie.h.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one ( const ip4_fib_mtrie_t m,
const ip4_address_t dst_address 
)
inlinestatic

Lookup step number 1.

Processes 2 bytes of 4 byte ip4 address.

Definition at line 224 of file ip4_mtrie.h.

+ Here is the caller graph for this function:

uword ip4_fib_mtrie_memory_usage ( ip4_fib_mtrie_t m)

return the memory used by the table

Definition at line 690 of file ip4_mtrie.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ip4_fib_mtrie_route_add ( ip4_fib_mtrie_t m,
const ip4_address_t dst_address,
u32  dst_address_length,
u32  adj_index 
)

Add a route/rntry to the mtrie.

Definition at line 633 of file ip4_mtrie.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ip4_fib_mtrie_route_del ( ip4_fib_mtrie_t m,
const ip4_address_t dst_address,
u32  dst_address_length,
u32  adj_index,
u32  cover_address_length,
u32  cover_adj_index 
)

remove a route/rntry to the mtrie

Definition at line 650 of file ip4_mtrie.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ip4_mtrie_free ( ip4_fib_mtrie_t m)

Free an mtrie, It must be emty when free'd.

Definition at line 199 of file ip4_mtrie.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ip4_mtrie_init ( ip4_fib_mtrie_t m)

Initialise an mtrie.

Definition at line 215 of file ip4_mtrie.c.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

STATIC_ASSERT ( = =sizeof(ip4_fib_mtrie_8_ply_t)%CLIB_CACHE_LINE_BYTES,
"IP4 Mtrie ply cache line"   
)

Variable Documentation

format_function_t format_ip4_fib_mtrie

Format/display the contents of the mtrie.

Definition at line 172 of file ip4_mtrie.h.

ip4_fib_mtrie_8_ply_t* ip4_ply_pool

A global pool of 8bit stride plys.

A global pool of 8bit stride plys.

Definition at line 48 of file ip4_mtrie.c.