Include dependency graph for ip4_mtrie.c:

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_t *	get_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 u8 *	format_ip4_fib_mtrie_leaf (u8 s, va_list va)

static u8 *	format_ip4_fib_mtrie_ply (u8 s, va_list va)

u8 *	format_ip4_fib_mtrie (u8 s, va_list va)

static clib_error_t *	ip4_mtrie_module_init (vlib_main_t *vm)

Variables
ip4_fib_mtrie_8_ply_t *	ip4_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,            \
              format_ip4_fib_mtrie_leaf(), _l);                           \
                                                                        \
  if (ip4_fib_mtrie_leaf_is_next_ply (_l))                              \
    s = format (s, "\n%U",                                              \
                format_ip4_fib_mtrie_ply(), m, a, (_indent) + 8,          \
                ip4_fib_mtrie_leaf_get_next_ply_index (_l));            \
  s;                                                                    \
})

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;                                                      \
      }                                                                 \
}

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.

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ FORMAT_PLY

◆ IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE

◆ MAP_HUGE_SHIFT

◆ PLY_INIT

◆ PLY_INIT_LEAVES

◆ PLY_X4_SPLAT_INIT

Function Documentation

◆ format_ip4_fib_mtrie()

◆ format_ip4_fib_mtrie_leaf()

◆ format_ip4_fib_mtrie_ply()

◆ get_next_ply_for_leaf()

◆ ip4_fib_mtrie_leaf_get_next_ply_index()

◆ ip4_fib_mtrie_leaf_is_next_ply()

◆ ip4_fib_mtrie_leaf_is_non_empty()

◆ ip4_fib_mtrie_leaf_set_adj_index()

◆ ip4_fib_mtrie_leaf_set_next_ply_index()

◆ ip4_fib_mtrie_memory_usage()

◆ ip4_fib_mtrie_route_add()

◆ ip4_fib_mtrie_route_del()

◆ ip4_mtrie_free()

◆ ip4_mtrie_init()

◆ ip4_mtrie_module_init()

◆ mtrie_ply_memory_usage()

◆ ply_16_init()

◆ ply_8_init()

◆ ply_create()

◆ set_leaf()

◆ set_ply_with_more_specific_leaf()

◆ set_root_leaf()

◆ unset_leaf()

◆ unset_root_leaf()

Variable Documentation

◆ ip4_ply_pool