67 l = 1 + 2 * adj_index;
95 #define PLY_X4_SPLAT_INIT(init_x4, init) \ 96 init_x4 = u32x4_splat (init); 98 #define PLY_X4_SPLAT_INIT(init_x4, init) \ 101 y.as_u32[0] = init; \ 102 y.as_u32[1] = init; \ 103 y.as_u32[2] = init; \ 104 y.as_u32[3] = init; \ 105 init_x4 = y.as_u32x4; \ 109 #ifdef CLIB_HAVE_VEC128 110 #define PLY_INIT_LEAVES(p) \ 114 PLY_X4_SPLAT_INIT(init_x4, init); \ 115 for (l = p->leaves_as_u32x4; \ 116 l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); \ 126 #define PLY_INIT_LEAVES(p) \ 130 for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4) \ 140 #define PLY_INIT(p, init, prefix_len, ply_base_len) \ 147 p->n_non_empty_leafs = (prefix_len > ply_base_len ? \ 148 ARRAY_LEN (p->leaves) : 0); \ 149 clib_memset (p->dst_address_bits_of_leaves, prefix_len, \ 150 sizeof (p->dst_address_bits_of_leaves)); \ 151 p->dst_address_bits_base = ply_base_len; \ 154 PLY_INIT_LEAVES(p); \ 161 PLY_INIT (p, init, prefix_len, ply_base_len);
176 u32 leaf_prefix_len,
u32 ply_base_len)
186 ply_8_init (p, init_leaf, leaf_prefix_len, ply_base_len);
233 uword new_leaf_dst_address_bits)
250 new_leaf_dst_address_bits);
254 else if (new_leaf_dst_address_bits >=
267 u32 old_ply_index,
u32 dst_address_byte_index)
270 i32 n_dst_bits_next_plies;
280 n_dst_bits_next_plies =
286 if (n_dst_bits_next_plies <= 0)
289 uword old_leaf_is_terminal;
290 u32 i, n_dst_bits_this_ply;
293 n_dst_bits_this_ply =
clib_min (8, -n_dst_bits_next_plies);
299 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
312 if (old_leaf_is_terminal)
337 else if (!old_leaf_is_terminal)
342 set_leaf (m, a, new_ply - ip4_ply_pool,
343 dst_address_byte_index + 1);
359 ply_base_len = 8 * (dst_address_byte_index + 1);
361 old_leaf = old_ply->
leaves[dst_byte];
388 set_leaf (m, a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
398 i32 n_dst_bits_next_plies;
411 if (n_dst_bits_next_plies <= 0)
414 uword old_leaf_is_terminal;
415 u32 i, n_dst_bits_this_ply;
424 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
429 slot = clib_net_to_host_u16 (dst_byte);
431 slot = clib_host_to_net_u16 (slot);
443 if (old_leaf_is_terminal)
460 else if (!old_leaf_is_terminal)
465 set_leaf (m, a, new_ply - ip4_ply_pool, 2);
483 old_leaf = old_ply->
leaves[dst_byte];
500 set_leaf (m, a, new_ply - ip4_ply_pool, 2);
510 i32 n_dst_bits_next_plies;
511 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
517 n_dst_bits_next_plies =
521 if (n_dst_bits_next_plies < 0)
522 dst_byte &= ~
pow2_mask (-n_dst_bits_next_plies);
524 n_dst_bits_this_ply =
525 n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
526 n_dst_bits_this_ply =
clib_min (8, n_dst_bits_this_ply);
530 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
535 if (old_leaf == del_leaf
536 || (!old_leaf_is_terminal
538 dst_address_byte_index + 1)))
559 else if (dst_address_byte_index)
581 i32 n_dst_bits_next_plies;
582 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
593 n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
600 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
604 slot = clib_net_to_host_u16 (dst_byte);
606 slot = clib_host_to_net_u16 (slot);
611 if (old_leaf == del_leaf
612 || (!old_leaf_is_terminal
626 u32 dst_address_length,
u32 adj_index)
643 u32 dst_address_length,
645 u32 cover_address_length,
u32 cover_adj_index)
668 bytes =
sizeof (p[0]);
708 #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent) \ 712 ip4_fib_mtrie_leaf_t _l = p->leaves[(_i)]; \ 714 a = (_base_address) + ((_a) << (32 - (_ply_max_len))); \ 715 ia.as_u32 = clib_host_to_net_u32 (a); \ 716 ia_length = (_p)->dst_address_bits_of_leaves[(_i)]; \ 717 s = format (s, "\n%U%U %U", \ 718 format_white_space, (_indent) + 4, \ 719 format_ip4_address_and_length, &ia, ia_length, \ 720 format_ip4_fib_mtrie_leaf, _l); \ 722 if (ip4_fib_mtrie_leaf_is_next_ply (_l)) \ 723 s = format (s, "\n%U", \ 724 format_ip4_fib_mtrie_ply, m, a, (_indent) + 8, \ 725 ip4_fib_mtrie_leaf_get_next_ply_index (_l)); \ 733 u32 base_address = va_arg (*va,
u32);
734 u32 indent = va_arg (*va,
u32);
735 u32 ply_index = va_arg (*va,
u32);
740 s =
format (s,
"%Uply index %d, %d non-empty leaves",
759 int verbose = va_arg (*va,
int);
761 u32 base_address = 0;
764 s =
format (s,
"%d plies, memory usage %U\n",
767 s =
format (s,
"root-ply");
772 s =
format (s,
"root-ply");
779 slot = clib_host_to_net_u16 (i);
783 s =
FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
792 #define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE (32<<20)
static ip4_fib_mtrie_8_ply_t * get_next_ply_for_leaf(ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t l)
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)
#define PLY_INIT_LEAVES(p)
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)
ip4_fib_mtrie_8_ply_t * ip4_ply_pool
Global pool of IPv4 8bit PLYs.
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
ip4_fib_mtrie_leaf_t leaves[256]
static void unset_root_leaf(ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a)
static u32 ip4_fib_mtrie_leaf_is_non_empty(ip4_fib_mtrie_8_ply_t *p, u8 dst_byte)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
u8 dst_address_bits_of_leaves[PLY_16_SIZE]
Prefix length for terminal leaves.
#define IP4_FIB_MTRIE_LEAF_EMPTY
One ply of the 4 ply mtrie fib.
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)
#define VLIB_INIT_FUNCTION(x)
#define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent)
static uword pow2_mask(uword x)
void ip4_mtrie_free(ip4_fib_mtrie_t *m)
Free an mtrie, It must be emty when free'd.
ip4_fib_mtrie_leaf_t leaves[PLY_16_SIZE]
#define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE
Default heap size for the IPv4 mtries.
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.
void ip4_mtrie_init(ip4_fib_mtrie_t *m)
Initialise an mtrie.
static u8 * format_ip4_fib_mtrie_leaf(u8 *s, va_list *va)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
u8 * format_ip4_fib_mtrie(u8 *s, va_list *va)
uword mtrie_heap_size
Heapsize for the Mtries.
static void set_root_leaf(ip4_fib_mtrie_t *m, const ip4_fib_mtrie_set_unset_leaf_args_t *a)
#define pool_put(P, E)
Free an object E in pool P.
static uword mtrie_ply_memory_usage(ip4_fib_mtrie_t *m, ip4_fib_mtrie_8_ply_t *p)
void * mtrie_mheap
The memory heap for the mtries.
ip4_address_t dst_address
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P with alignment A.
u8 dst_address_bits_of_leaves[256]
Prefix length for leaves/ply.
DLMALLOC_EXPORT mspace create_mspace(size_t capacity, int locked)
uword ip4_fib_mtrie_memory_usage(ip4_fib_mtrie_t *m)
return the memory used by the table
sll srl srl sll sra u16x4 i
ip4_fib_mtrie_16_ply_t root_ply
Embed the PLY with the mtrie struct.
static void * clib_mem_set_heap(void *heap)
#define PLY_INIT(p, init, prefix_len, ply_base_len)
static clib_error_t * ip4_mtrie_module_init(vlib_main_t *vm)
i32 n_non_empty_leafs
Number of non-empty leafs (whether terminal or not).
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
#define clib_atomic_store_rel_n(a, b)
i32 dst_address_bits_base
The length of the ply's covering prefix.
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.
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index(u32 adj_index)
ip4_main_t ip4_main
Global ip4 main structure.
static u32 ip4_fib_mtrie_leaf_get_next_ply_index(ip4_fib_mtrie_leaf_t n)
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
#define CLIB_CACHE_LINE_BYTES
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 u8 * format_ip4_fib_mtrie_ply(u8 *s, va_list *va)
static void ply_16_init(ip4_fib_mtrie_16_ply_t *p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
static u32 ip4_fib_mtrie_leaf_is_terminal(ip4_fib_mtrie_leaf_t n)
Is the leaf terminal (i.e.
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 ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index(u32 i)
static uword pool_elts(void *v)
Number of active elements in a pool.