FD.io VPP  v20.09-64-g4f7b92f0a
Vector Packet Processing
ip4_mtrie.c File Reference
+ Include dependency graph for ip4_mtrie.c:

Go to the source code of this file.

Data Structures

struct  ip4_fib_mtrie_set_unset_leaf_args_t
 

Macros

#define PLY_X4_SPLAT_INIT(init_x4, init)   init_x4 = u32x4_splat (init);
 
#define PLY_INIT_LEAVES(p)
 
#define PLY_INIT(p, init, prefix_len, ply_base_len)
 
#define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent)
 
#define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE   (32<<20)
 Default heap size for the IPv4 mtries. More...
 
#define MAP_HUGE_SHIFT   26
 

Functions

static u32 ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_8_ply_t *p, u8 dst_byte)
 
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
 
static u32 ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
 
static u32 ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
 
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
 
static void ply_8_init (ip4_fib_mtrie_8_ply_t *p, ip4_fib_mtrie_leaf_t init, uword prefix_len, u32 ply_base_len)
 
static void ply_16_init (ip4_fib_mtrie_16_ply_t *p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
 
static ip4_fib_mtrie_leaf_t ply_create (ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t init_leaf, u32 leaf_prefix_len, u32 ply_base_len)
 
static ip4_fib_mtrie_8_ply_tget_next_ply_for_leaf (ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t l)
 
void ip4_mtrie_free (ip4_fib_mtrie_t *m)
 Free an mtrie, It must be emty when free'd. More...
 
void ip4_mtrie_init (ip4_fib_mtrie_t *m)
 Initialise an mtrie. More...
 
static void set_ply_with_more_specific_leaf (ip4_fib_mtrie_t *m, ip4_fib_mtrie_8_ply_t *ply, ip4_fib_mtrie_leaf_t new_leaf, uword new_leaf_dst_address_bits)
 
static void set_leaf (ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index, u32 dst_address_byte_index)
 
static void set_root_leaf (ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a)
 
static uword unset_leaf (ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a, ip4_fib_mtrie_8_ply_t *old_ply, u32 dst_address_byte_index)
 
static void unset_root_leaf (ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a)
 
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/entry 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/entry to the mtrie More...
 
static uword mtrie_ply_memory_usage (ip4_fib_mtrie_t *m, ip4_fib_mtrie_8_ply_t *p)
 
uword ip4_fib_mtrie_memory_usage (ip4_fib_mtrie_t *m)
 return the memory used by the table More...
 
static u8format_ip4_fib_mtrie_leaf (u8 *s, va_list *va)
 
static u8format_ip4_fib_mtrie_ply (u8 *s, va_list *va)
 
u8format_ip4_fib_mtrie (u8 *s, va_list *va)
 
static clib_error_tip4_mtrie_module_init (vlib_main_t *vm)
 

Variables

ip4_fib_mtrie_8_ply_tip4_ply_pool
 Global pool of IPv4 8bit PLYs. More...
 

Macro Definition Documentation

◆ FORMAT_PLY

#define FORMAT_PLY (   s,
  _p,
  _a,
  _i,
  _base_address,
  _ply_max_len,
  _indent 
)
Value:
({ \
u32 a, ia_length; \
ip4_address_t ia; \
ip4_fib_mtrie_leaf_t _l = p->leaves[(_i)]; \
\
a = (_base_address) + ((_a) << (32 - (_ply_max_len))); \
ia.as_u32 = clib_host_to_net_u32 (a); \
ia_length = (_p)->dst_address_bits_of_leaves[(_i)]; \
s = format (s, "\n%U%U %U", \
format_white_space(), (_indent) + 4, \
format_ip4_address_and_length(), &ia, ia_length, \
\
s = format (s, "\n%U", \
format_ip4_fib_mtrie_ply(), m, a, (_indent) + 8, \
s; \
})
a
Definition: bitmap.h:538
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:129
static u8 * format_ip4_fib_mtrie_leaf(u8 *s, va_list *va)
Definition: ip4_mtrie.c:697
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.c:73
static u32 ip4_fib_mtrie_leaf_get_next_ply_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.c:79
static u8 * format_ip4_fib_mtrie_ply(u8 *s, va_list *va)
Definition: ip4_mtrie.c:730
format_function_t format_ip4_address_and_length
Definition: format.h:74

Definition at line 708 of file ip4_mtrie.c.

◆ IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE

#define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE   (32<<20)

Default heap size for the IPv4 mtries.

Definition at line 792 of file ip4_mtrie.c.

◆ MAP_HUGE_SHIFT

#define MAP_HUGE_SHIFT   26

Definition at line 794 of file ip4_mtrie.c.

◆ PLY_INIT

#define PLY_INIT (   p,
  init,
  prefix_len,
  ply_base_len 
)
Value:
{ \
/* \
* A leaf is 'empty' if it represents a leaf from the covering PLY \
* i.e. if the prefix length of the leaf is less than or equal to \
* the prefix length of the PLY \
*/ \
p->n_non_empty_leafs = (prefix_len > ply_base_len ? \
ARRAY_LEN (p->leaves) : 0); \
clib_memset (p->dst_address_bits_of_leaves, prefix_len, \
sizeof (p->dst_address_bits_of_leaves)); \
p->dst_address_bits_base = ply_base_len; \
\
/* Initialize leaves. */ \
PLY_INIT_LEAVES(p); \
}

Definition at line 140 of file ip4_mtrie.c.

◆ PLY_INIT_LEAVES

#define PLY_INIT_LEAVES (   p)
Value:
{ \
u32 *l; \
for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4) \
{ \
l[0] = init; \
l[1] = init; \
l[2] = init; \
l[3] = init; \
} \
}
for(i=1;i<=collision_buckets;i++)
#define ARRAY_LEN(x)
Definition: clib.h:67
static void init(void)
Definition: client.c:105

Definition at line 126 of file ip4_mtrie.c.

◆ PLY_X4_SPLAT_INIT

#define PLY_X4_SPLAT_INIT (   init_x4,
  init 
)    init_x4 = u32x4_splat (init);

Definition at line 95 of file ip4_mtrie.c.

Function Documentation

◆ format_ip4_fib_mtrie()

u8* format_ip4_fib_mtrie ( u8 s,
va_list *  va 
)

Definition at line 756 of file ip4_mtrie.c.

+ Here is the call graph for this function:

◆ format_ip4_fib_mtrie_leaf()

static u8* format_ip4_fib_mtrie_leaf ( u8 s,
va_list *  va 
)
static

Definition at line 697 of file ip4_mtrie.c.

+ Here is the call graph for this function:

◆ format_ip4_fib_mtrie_ply()

static u8* format_ip4_fib_mtrie_ply ( u8 s,
va_list *  va 
)
static

Definition at line 730 of file ip4_mtrie.c.

+ Here is the call graph for this function:

◆ get_next_ply_for_leaf()

static ip4_fib_mtrie_8_ply_t* get_next_ply_for_leaf ( ip4_fib_mtrie_t m,
ip4_fib_mtrie_leaf_t  l 
)
inlinestatic

Definition at line 191 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_leaf_get_next_ply_index()

static u32 ip4_fib_mtrie_leaf_get_next_ply_index ( ip4_fib_mtrie_leaf_t  n)
inlinestatic

Definition at line 79 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_leaf_is_next_ply()

static u32 ip4_fib_mtrie_leaf_is_next_ply ( ip4_fib_mtrie_leaf_t  n)
inlinestatic

Definition at line 73 of file ip4_mtrie.c.

+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_leaf_is_non_empty()

static u32 ip4_fib_mtrie_leaf_is_non_empty ( ip4_fib_mtrie_8_ply_t p,
u8  dst_byte 
)
inlinestatic

Definition at line 51 of file ip4_mtrie.c.

+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_leaf_set_adj_index()

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index ( u32  adj_index)
inlinestatic

Definition at line 64 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_leaf_set_next_ply_index()

static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index ( u32  i)
inlinestatic

Definition at line 86 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_memory_usage()

uword ip4_fib_mtrie_memory_usage ( ip4_fib_mtrie_t m)

return the memory used by the table

Definition at line 681 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_route_add()

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/entry to the mtrie.

Definition at line 624 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_fib_mtrie_route_del()

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/entry to the mtrie

Definition at line 641 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ip4_mtrie_free()

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:

◆ ip4_mtrie_init()

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:

◆ ip4_mtrie_module_init()

static clib_error_t* ip4_mtrie_module_init ( vlib_main_t vm)
static

Definition at line 798 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ mtrie_ply_memory_usage()

static uword mtrie_ply_memory_usage ( ip4_fib_mtrie_t m,
ip4_fib_mtrie_8_ply_t p 
)
static

Definition at line 664 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ply_16_init()

static void ply_16_init ( ip4_fib_mtrie_16_ply_t p,
ip4_fib_mtrie_leaf_t  init,
uword  prefix_len 
)
static

Definition at line 165 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ ply_8_init()

static void ply_8_init ( ip4_fib_mtrie_8_ply_t p,
ip4_fib_mtrie_leaf_t  init,
uword  prefix_len,
u32  ply_base_len 
)
static

Definition at line 158 of file ip4_mtrie.c.

+ Here is the caller graph for this function:

◆ ply_create()

static ip4_fib_mtrie_leaf_t ply_create ( ip4_fib_mtrie_t m,
ip4_fib_mtrie_leaf_t  init_leaf,
u32  leaf_prefix_len,
u32  ply_base_len 
)
static

Definition at line 174 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ set_leaf()

static void set_leaf ( ip4_fib_mtrie_t m,
const ip4_fib_mtrie_set_unset_leaf_args_t a,
u32  old_ply_index,
u32  dst_address_byte_index 
)
static

Definition at line 265 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ set_ply_with_more_specific_leaf()

static void set_ply_with_more_specific_leaf ( ip4_fib_mtrie_t m,
ip4_fib_mtrie_8_ply_t ply,
ip4_fib_mtrie_leaf_t  new_leaf,
uword  new_leaf_dst_address_bits 
)
static

Definition at line 230 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ set_root_leaf()

static void set_root_leaf ( ip4_fib_mtrie_t m,
const ip4_fib_mtrie_set_unset_leaf_args_t a 
)
static

Definition at line 393 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ unset_leaf()

static uword unset_leaf ( ip4_fib_mtrie_t m,
const ip4_fib_mtrie_set_unset_leaf_args_t a,
ip4_fib_mtrie_8_ply_t old_ply,
u32  dst_address_byte_index 
)
static

Definition at line 505 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ unset_root_leaf()

static void unset_root_leaf ( ip4_fib_mtrie_t m,
const ip4_fib_mtrie_set_unset_leaf_args_t a 
)
static

Definition at line 577 of file ip4_mtrie.c.

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

Variable Documentation

◆ ip4_ply_pool

ip4_fib_mtrie_8_ply_t* ip4_ply_pool

Global pool of IPv4 8bit PLYs.

A global pool of 8bit stride plys.

Definition at line 48 of file ip4_mtrie.c.