ip4_mtrie.c File Reference

Include dependency graph for ip4_mtrie.c:

Go to the source code of this file.

Data Structures
struct	ip4_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_mtrie_leaf_is_non_empty (ip4_mtrie_8_ply_t *p, u8 dst_byte)
static ip4_mtrie_leaf_t	ip4_mtrie_leaf_set_adj_index (u32 adj_index)
static u32	ip4_mtrie_leaf_is_next_ply (ip4_mtrie_leaf_t n)
static u32	ip4_mtrie_leaf_get_next_ply_index (ip4_mtrie_leaf_t n)
static ip4_mtrie_leaf_t	ip4_mtrie_leaf_set_next_ply_index (u32 i)
static void	ply_8_init (ip4_mtrie_8_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len, u32 ply_base_len)
static void	ply_16_init (ip4_mtrie_16_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len)
static ip4_mtrie_leaf_t	ply_create (ip4_mtrie_leaf_t init_leaf, u32 leaf_prefix_len, u32 ply_base_len)
static ip4_mtrie_8_ply_t *	get_next_ply_for_leaf (ip4_mtrie_leaf_t l)
void	ip4_mtrie_16_free (ip4_mtrie_16_t *m)
	Free an mtrie, It must be empty when free'd. More...
void	ip4_mtrie_16_init (ip4_mtrie_16_t *m)
	Initialise an mtrie. More...
void	ip4_mtrie_8_free (ip4_mtrie_8_t *m)
void	ip4_mtrie_8_init (ip4_mtrie_8_t *m)
static void	set_ply_with_more_specific_leaf (ip4_mtrie_8_ply_t *ply, ip4_mtrie_leaf_t new_leaf, uword new_leaf_dst_address_bits)
static void	set_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index, u32 dst_address_byte_index)
static void	set_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
static uword	unset_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, ip4_mtrie_8_ply_t *old_ply, u32 dst_address_byte_index)
static void	unset_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
void	ip4_mtrie_16_route_add (ip4_mtrie_16_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_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index)
void	ip4_mtrie_16_route_del (ip4_mtrie_16_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...
void	ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address, u32 dst_address_length, u32 adj_index, u32 cover_address_length, u32 cover_adj_index)
static uword	mtrie_ply_memory_usage (ip4_mtrie_8_ply_t *p)
uword	ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
	return the memory used by the table More...
uword	ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
static u8 *	format_ip4_mtrie_leaf (u8 *s, va_list *va)
static u8 *	format_ip4_mtrie_ply (u8 *s, va_list *va)
u8 *	format_ip4_mtrie_16 (u8 *s, va_list *va)
u8 *	format_ip4_mtrie_8 (u8 *s, va_list *va)
static clib_error_t *	ip4_mtrie_module_init (vlib_main_t *vm)

Variables
ip4_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_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_mtrie_leaf(), _l);                                   \
                                                                              \
    if (ip4_mtrie_leaf_is_next_ply (_l))                                      \
      s = format (s, "\n%U", format_ip4_mtrie_ply(), m, a, (_indent) + 8,       \
                  ip4_mtrie_leaf_get_next_ply_index (_l));                    \
    s;                                                                        \
  })

Definition at line 774 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 886 of file ip4_mtrie.c.

MAP_HUGE_SHIFT

#define MAP_HUGE_SHIFT   26

Definition at line 888 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_mtrie_16()

u8* format_ip4_mtrie_16	(	u8 *	s,
		va_list *	va
	)

Definition at line 820 of file ip4_mtrie.c.

format_ip4_mtrie_8()

u8* format_ip4_mtrie_8	(	u8 *	s,
		va_list *	va
	)

Definition at line 855 of file ip4_mtrie.c.

format_ip4_mtrie_leaf()

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

static

Definition at line 763 of file ip4_mtrie.c.

format_ip4_mtrie_ply()

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

static

Definition at line 794 of file ip4_mtrie.c.

Here is the call graph for this function:

get_next_ply_for_leaf()

static ip4_mtrie_8_ply_t* get_next_ply_for_leaf ( ip4_mtrie_leaf_t  l )

inlinestatic

Definition at line 181 of file ip4_mtrie.c.

ip4_mtrie_16_free()

void ip4_mtrie_16_free

(

ip4_mtrie_16_t *

m

)

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

Definition at line 189 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_init()

void ip4_mtrie_16_init

(

ip4_mtrie_16_t *

m

)

Initialise an mtrie.

Definition at line 205 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_memory_usage()

uword ip4_mtrie_16_memory_usage

(

ip4_mtrie_16_t *

m

)

return the memory used by the table

Definition at line 731 of file ip4_mtrie.c.

ip4_mtrie_16_route_add()

void ip4_mtrie_16_route_add	(	ip4_mtrie_16_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 636 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_16_route_del()

void ip4_mtrie_16_route_del	(	ip4_mtrie_16_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 670 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_free()

void ip4_mtrie_8_free

(

ip4_mtrie_8_t *

m

)

Definition at line 211 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_init()

void ip4_mtrie_8_init

(

ip4_mtrie_8_t *

m

)

Definition at line 231 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_memory_usage()

uword ip4_mtrie_8_memory_usage

(

ip4_mtrie_8_t *

m

)

Definition at line 746 of file ip4_mtrie.c.

ip4_mtrie_8_route_add()

void ip4_mtrie_8_route_add	(	ip4_mtrie_8_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index
	)

Definition at line 652 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_8_route_del()

void ip4_mtrie_8_route_del	(	ip4_mtrie_8_t *	m,
		const ip4_address_t *	dst_address,
		u32	dst_address_length,
		u32	adj_index,
		u32	cover_address_length,
		u32	cover_adj_index
	)

Definition at line 690 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_leaf_get_next_ply_index()

static u32 ip4_mtrie_leaf_get_next_ply_index ( ip4_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_mtrie_leaf_is_next_ply()

static u32 ip4_mtrie_leaf_is_next_ply ( ip4_mtrie_leaf_t  n )

inlinestatic

Definition at line 73 of file ip4_mtrie.c.

Here is the caller graph for this function:

ip4_mtrie_leaf_is_non_empty()

static u32 ip4_mtrie_leaf_is_non_empty ( ip4_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_mtrie_leaf_set_adj_index()

static ip4_mtrie_leaf_t ip4_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:

ip4_mtrie_leaf_set_next_ply_index()

static ip4_mtrie_leaf_t ip4_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:

ip4_mtrie_module_init()

static clib_error_t* ip4_mtrie_module_init ( vlib_main_t *  vm )

static

Definition at line 892 of file ip4_mtrie.c.

Here is the caller graph for this function:

mtrie_ply_memory_usage()

static uword mtrie_ply_memory_usage ( ip4_mtrie_8_ply_t *  p )

static

Definition at line 714 of file ip4_mtrie.c.

ply_16_init()

static void ply_16_init ( ip4_mtrie_16_ply_t *  p, ip4_mtrie_leaf_t  init, uword  prefix_len  )

static

Definition at line 161 of file ip4_mtrie.c.

ply_8_init()

static void ply_8_init ( ip4_mtrie_8_ply_t *  p, ip4_mtrie_leaf_t  init, uword  prefix_len, u32  ply_base_len  )

static

Definition at line 154 of file ip4_mtrie.c.

ply_create()

static ip4_mtrie_leaf_t ply_create ( ip4_mtrie_leaf_t  init_leaf, u32  leaf_prefix_len, u32  ply_base_len  )

static

Definition at line 169 of file ip4_mtrie.c.

set_leaf()

static void set_leaf ( const ip4_mtrie_set_unset_leaf_args_t *  a, u32  old_ply_index, u32  dst_address_byte_index  )

static

Definition at line 284 of file ip4_mtrie.c.

set_ply_with_more_specific_leaf()

static void set_ply_with_more_specific_leaf ( ip4_mtrie_8_ply_t *  ply, ip4_mtrie_leaf_t  new_leaf, uword  new_leaf_dst_address_bits  )

static

Definition at line 251 of file ip4_mtrie.c.

set_root_leaf()

static void set_root_leaf ( ip4_mtrie_16_t *  m, const ip4_mtrie_set_unset_leaf_args_t *  a  )

static

Definition at line 409 of file ip4_mtrie.c.

unset_leaf()

static uword unset_leaf ( const ip4_mtrie_set_unset_leaf_args_t *  a, ip4_mtrie_8_ply_t *  old_ply, u32  dst_address_byte_index  )

static

Definition at line 519 of file ip4_mtrie.c.

unset_root_leaf()

static void unset_root_leaf ( ip4_mtrie_16_t *  m, const ip4_mtrie_set_unset_leaf_args_t *  a  )

static

Definition at line 590 of file ip4_mtrie.c.

Variable Documentation

ip4_ply_pool

ip4_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.