2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
16 * ip/ip4_fib.h: ip4 mtrie fib
18 * Copyright (c) 2012 Eliot Dresselhaus
20 * Permission is hereby granted, free of charge, to any person obtaining
21 * a copy of this software and associated documentation files (the
22 * "Software"), to deal in the Software without restriction, including
23 * without limitation the rights to use, copy, modify, merge, publish,
24 * distribute, sublicense, and/or sell copies of the Software, and to
25 * permit persons to whom the Software is furnished to do so, subject to
26 * the following conditions:
28 * The above copyright notice and this permission notice shall be
29 * included in all copies or substantial portions of the Software.
31 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
40 #include <vnet/ip/ip.h>
41 #include <vnet/ip/ip4_mtrie.h>
42 #include <vnet/fib/ip4_fib.h>
46 * Global pool of IPv4 8bit PLYs
48 ip4_fib_mtrie_8_ply_t *ip4_ply_pool;
51 ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_8_ply_t * p, u8 dst_byte)
54 * It's 'non-empty' if the length of the leaf stored is greater than the
55 * length of a leaf in the covering ply. i.e. the leaf is more specific
56 * than it's would be cover in the covering ply
58 if (p->dst_address_bits_of_leaves[dst_byte] > p->dst_address_bits_base)
63 always_inline ip4_fib_mtrie_leaf_t
64 ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
66 ip4_fib_mtrie_leaf_t l;
67 l = 1 + 2 * adj_index;
68 ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
73 ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
79 ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
81 ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n));
85 always_inline ip4_fib_mtrie_leaf_t
86 ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
88 ip4_fib_mtrie_leaf_t l;
90 ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i);
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) \
143 * A leaf is 'empty' if it represents a leaf from the covering PLY \
144 * i.e. if the prefix length of the leaf is less than or equal to \
145 * the prefix length of the PLY \
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; \
153 /* Initialize leaves. */ \
154 PLY_INIT_LEAVES(p); \
158 ply_8_init (ip4_fib_mtrie_8_ply_t * p,
159 ip4_fib_mtrie_leaf_t init, uword prefix_len, u32 ply_base_len)
161 PLY_INIT (p, init, prefix_len, ply_base_len);
165 ply_16_init (ip4_fib_mtrie_16_ply_t * p,
166 ip4_fib_mtrie_leaf_t init, uword prefix_len)
168 clib_memset (p->dst_address_bits_of_leaves, prefix_len,
169 sizeof (p->dst_address_bits_of_leaves));
173 static ip4_fib_mtrie_leaf_t
174 ply_create (ip4_fib_mtrie_t * m,
175 ip4_fib_mtrie_leaf_t init_leaf,
176 u32 leaf_prefix_len, u32 ply_base_len)
178 ip4_fib_mtrie_8_ply_t *p;
180 /* Get cache aligned ply. */
182 old_heap = clib_mem_set_heap (ip4_main.mtrie_mheap);
183 pool_get_aligned (ip4_ply_pool, p, CLIB_CACHE_LINE_BYTES);
184 clib_mem_set_heap (old_heap);
186 ply_8_init (p, init_leaf, leaf_prefix_len, ply_base_len);
187 return ip4_fib_mtrie_leaf_set_next_ply_index (p - ip4_ply_pool);
190 always_inline ip4_fib_mtrie_8_ply_t *
191 get_next_ply_for_leaf (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t l)
193 uword n = ip4_fib_mtrie_leaf_get_next_ply_index (l);
195 return pool_elt_at_index (ip4_ply_pool, n);
199 ip4_mtrie_free (ip4_fib_mtrie_t * m)
201 /* the root ply is embedded so there is nothing to do,
202 * the assumption being that the IP4 FIB table has emptied the trie
207 for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
209 ASSERT (!ip4_fib_mtrie_leaf_is_next_ply (m->root_ply.leaves[i]));
215 ip4_mtrie_init (ip4_fib_mtrie_t * m)
217 ply_16_init (&m->root_ply, IP4_FIB_MTRIE_LEAF_EMPTY, 0);
222 ip4_address_t dst_address;
223 u32 dst_address_length;
225 u32 cover_address_length;
227 } ip4_fib_mtrie_set_unset_leaf_args_t;
230 set_ply_with_more_specific_leaf (ip4_fib_mtrie_t * m,
231 ip4_fib_mtrie_8_ply_t * ply,
232 ip4_fib_mtrie_leaf_t new_leaf,
233 uword new_leaf_dst_address_bits)
235 ip4_fib_mtrie_leaf_t old_leaf;
238 ASSERT (ip4_fib_mtrie_leaf_is_terminal (new_leaf));
240 for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
242 old_leaf = ply->leaves[i];
244 /* Recurse into sub plies. */
245 if (!ip4_fib_mtrie_leaf_is_terminal (old_leaf))
247 ip4_fib_mtrie_8_ply_t *sub_ply =
248 get_next_ply_for_leaf (m, old_leaf);
249 set_ply_with_more_specific_leaf (m, sub_ply, new_leaf,
250 new_leaf_dst_address_bits);
253 /* Replace less specific terminal leaves with new leaf. */
254 else if (new_leaf_dst_address_bits >=
255 ply->dst_address_bits_of_leaves[i])
257 clib_atomic_cmp_and_swap (&ply->leaves[i], old_leaf, new_leaf);
258 ASSERT (ply->leaves[i] == new_leaf);
259 ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
260 ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_non_empty (ply, i);
266 set_leaf (ip4_fib_mtrie_t * m,
267 const ip4_fib_mtrie_set_unset_leaf_args_t * a,
268 u32 old_ply_index, u32 dst_address_byte_index)
270 ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
271 i32 n_dst_bits_next_plies;
273 ip4_fib_mtrie_8_ply_t *old_ply;
275 old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
277 ASSERT (a->dst_address_length <= 32);
278 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
280 /* how many bits of the destination address are in the next PLY */
281 n_dst_bits_next_plies =
282 a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
284 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
286 /* Number of bits next plies <= 0 => insert leaves this ply. */
287 if (n_dst_bits_next_plies <= 0)
289 /* The mask length of the address to insert maps to this ply */
290 uword old_leaf_is_terminal;
291 u32 i, n_dst_bits_this_ply;
293 /* The number of bits, and hence slots/buckets, we will fill */
294 n_dst_bits_this_ply = clib_min (8, -n_dst_bits_next_plies);
295 ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
296 pow2_mask (n_dst_bits_this_ply)) == 0);
298 /* Starting at the value of the byte at this section of the v4 address
299 * fill the buckets/slots of the ply */
300 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
302 ip4_fib_mtrie_8_ply_t *new_ply;
304 old_leaf = old_ply->leaves[i];
305 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
307 if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
309 /* The new leaf is more or equally specific than the one currently
310 * occupying the slot */
311 new_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
313 if (old_leaf_is_terminal)
315 /* The current leaf is terminal, we can replace it with
317 old_ply->n_non_empty_leafs -=
318 ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
320 old_ply->dst_address_bits_of_leaves[i] =
321 a->dst_address_length;
322 clib_atomic_cmp_and_swap (&old_ply->leaves[i], old_leaf,
324 ASSERT (old_ply->leaves[i] == new_leaf);
326 old_ply->n_non_empty_leafs +=
327 ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
328 ASSERT (old_ply->n_non_empty_leafs <=
329 ARRAY_LEN (old_ply->leaves));
333 /* Existing leaf points to another ply. We need to place
334 * new_leaf into all more specific slots. */
335 new_ply = get_next_ply_for_leaf (m, old_leaf);
336 set_ply_with_more_specific_leaf (m, new_ply, new_leaf,
337 a->dst_address_length);
340 else if (!old_leaf_is_terminal)
342 /* The current leaf is less specific and not termial (i.e. a ply),
343 * recurse on down the trie */
344 new_ply = get_next_ply_for_leaf (m, old_leaf);
345 set_leaf (m, a, new_ply - ip4_ply_pool,
346 dst_address_byte_index + 1);
350 * the route we are adding is less specific than the leaf currently
351 * occupying this slot. leave it there
357 /* The address to insert requires us to move down at a lower level of
358 * the trie - recurse on down */
359 ip4_fib_mtrie_8_ply_t *new_ply;
362 ply_base_len = 8 * (dst_address_byte_index + 1);
364 old_leaf = old_ply->leaves[dst_byte];
366 if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
368 /* There is a leaf occupying the slot. Replace it with a new ply */
369 old_ply->n_non_empty_leafs -=
370 ip4_fib_mtrie_leaf_is_non_empty (old_ply, dst_byte);
373 ply_create (m, old_leaf,
374 old_ply->dst_address_bits_of_leaves[dst_byte],
376 new_ply = get_next_ply_for_leaf (m, new_leaf);
378 /* Refetch since ply_create may move pool. */
379 old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
381 clib_atomic_cmp_and_swap (&old_ply->leaves[dst_byte], old_leaf,
383 ASSERT (old_ply->leaves[dst_byte] == new_leaf);
384 old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
386 old_ply->n_non_empty_leafs +=
387 ip4_fib_mtrie_leaf_is_non_empty (old_ply, dst_byte);
388 ASSERT (old_ply->n_non_empty_leafs >= 0);
391 new_ply = get_next_ply_for_leaf (m, old_leaf);
393 set_leaf (m, a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
398 set_root_leaf (ip4_fib_mtrie_t * m,
399 const ip4_fib_mtrie_set_unset_leaf_args_t * a)
401 ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
402 ip4_fib_mtrie_16_ply_t *old_ply;
403 i32 n_dst_bits_next_plies;
406 old_ply = &m->root_ply;
408 ASSERT (a->dst_address_length <= 32);
410 /* how many bits of the destination address are in the next PLY */
411 n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
413 dst_byte = a->dst_address.as_u16[0];
415 /* Number of bits next plies <= 0 => insert leaves this ply. */
416 if (n_dst_bits_next_plies <= 0)
418 /* The mask length of the address to insert maps to this ply */
419 uword old_leaf_is_terminal;
420 u32 i, n_dst_bits_this_ply;
422 /* The number of bits, and hence slots/buckets, we will fill */
423 n_dst_bits_this_ply = 16 - a->dst_address_length;
424 ASSERT ((clib_host_to_net_u16 (a->dst_address.as_u16[0]) &
425 pow2_mask (n_dst_bits_this_ply)) == 0);
427 /* Starting at the value of the byte at this section of the v4 address
428 * fill the buckets/slots of the ply */
429 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
431 ip4_fib_mtrie_8_ply_t *new_ply;
434 slot = clib_net_to_host_u16 (dst_byte);
436 slot = clib_host_to_net_u16 (slot);
438 old_leaf = old_ply->leaves[slot];
439 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
441 if (a->dst_address_length >=
442 old_ply->dst_address_bits_of_leaves[slot])
444 /* The new leaf is more or equally specific than the one currently
445 * occupying the slot */
446 new_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
448 if (old_leaf_is_terminal)
450 /* The current leaf is terminal, we can replace it with
452 old_ply->dst_address_bits_of_leaves[slot] =
453 a->dst_address_length;
454 clib_atomic_cmp_and_swap (&old_ply->leaves[slot],
456 ASSERT (old_ply->leaves[slot] == new_leaf);
460 /* Existing leaf points to another ply. We need to place
461 * new_leaf into all more specific slots. */
462 new_ply = get_next_ply_for_leaf (m, old_leaf);
463 set_ply_with_more_specific_leaf (m, new_ply, new_leaf,
464 a->dst_address_length);
467 else if (!old_leaf_is_terminal)
469 /* The current leaf is less specific and not termial (i.e. a ply),
470 * recurse on down the trie */
471 new_ply = get_next_ply_for_leaf (m, old_leaf);
472 set_leaf (m, a, new_ply - ip4_ply_pool, 2);
476 * the route we are adding is less specific than the leaf currently
477 * occupying this slot. leave it there
483 /* The address to insert requires us to move down at a lower level of
484 * the trie - recurse on down */
485 ip4_fib_mtrie_8_ply_t *new_ply;
490 old_leaf = old_ply->leaves[dst_byte];
492 if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
494 /* There is a leaf occupying the slot. Replace it with a new ply */
496 ply_create (m, old_leaf,
497 old_ply->dst_address_bits_of_leaves[dst_byte],
499 new_ply = get_next_ply_for_leaf (m, new_leaf);
501 clib_atomic_cmp_and_swap (&old_ply->leaves[dst_byte], old_leaf,
503 ASSERT (old_ply->leaves[dst_byte] == new_leaf);
504 old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
507 new_ply = get_next_ply_for_leaf (m, old_leaf);
509 set_leaf (m, a, new_ply - ip4_ply_pool, 2);
514 unset_leaf (ip4_fib_mtrie_t * m,
515 const ip4_fib_mtrie_set_unset_leaf_args_t * a,
516 ip4_fib_mtrie_8_ply_t * old_ply, u32 dst_address_byte_index)
518 ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
519 i32 n_dst_bits_next_plies;
520 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
523 ASSERT (a->dst_address_length <= 32);
524 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
526 n_dst_bits_next_plies =
527 a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
529 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
530 if (n_dst_bits_next_plies < 0)
531 dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
533 n_dst_bits_this_ply =
534 n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
535 n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
537 del_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
539 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
541 old_leaf = old_ply->leaves[i];
542 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
544 if (old_leaf == del_leaf
545 || (!old_leaf_is_terminal
546 && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf),
547 dst_address_byte_index + 1)))
549 old_ply->n_non_empty_leafs -=
550 ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
552 clib_atomic_store_rel_n (&old_ply->leaves[i],
553 ip4_fib_mtrie_leaf_set_adj_index
554 (a->cover_adj_index));
555 old_ply->dst_address_bits_of_leaves[i] = a->cover_address_length;
557 old_ply->n_non_empty_leafs +=
558 ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
560 ASSERT (old_ply->n_non_empty_leafs >= 0);
561 if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
563 pool_put (ip4_ply_pool, old_ply);
564 /* Old ply was deleted. */
568 else if (dst_address_byte_index)
571 for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
573 count += ip4_fib_mtrie_leaf_is_non_empty (old_ply, ii);
581 /* Old ply was not deleted. */
586 unset_root_leaf (ip4_fib_mtrie_t * m,
587 const ip4_fib_mtrie_set_unset_leaf_args_t * a)
589 ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
590 i32 n_dst_bits_next_plies;
591 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
593 ip4_fib_mtrie_16_ply_t *old_ply;
595 ASSERT (a->dst_address_length <= 32);
597 old_ply = &m->root_ply;
598 n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
600 dst_byte = a->dst_address.as_u16[0];
602 n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
603 (16 - a->dst_address_length) : 0);
605 del_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
607 /* Starting at the value of the byte at this section of the v4 address
608 * fill the buckets/slots of the ply */
609 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
613 slot = clib_net_to_host_u16 (dst_byte);
615 slot = clib_host_to_net_u16 (slot);
617 old_leaf = old_ply->leaves[slot];
618 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
620 if (old_leaf == del_leaf
621 || (!old_leaf_is_terminal
622 && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf), 2)))
624 clib_atomic_store_rel_n (&old_ply->leaves[slot],
625 ip4_fib_mtrie_leaf_set_adj_index
626 (a->cover_adj_index));
627 old_ply->dst_address_bits_of_leaves[slot] = a->cover_address_length;
633 ip4_fib_mtrie_route_add (ip4_fib_mtrie_t * m,
634 const ip4_address_t * dst_address,
635 u32 dst_address_length, u32 adj_index)
637 ip4_fib_mtrie_set_unset_leaf_args_t a;
638 ip4_main_t *im = &ip4_main;
640 /* Honor dst_address_length. Fib masks are in network byte order */
641 a.dst_address.as_u32 = (dst_address->as_u32 &
642 im->fib_masks[dst_address_length]);
643 a.dst_address_length = dst_address_length;
644 a.adj_index = adj_index;
646 set_root_leaf (m, &a);
650 ip4_fib_mtrie_route_del (ip4_fib_mtrie_t * m,
651 const ip4_address_t * dst_address,
652 u32 dst_address_length,
654 u32 cover_address_length, u32 cover_adj_index)
656 ip4_fib_mtrie_set_unset_leaf_args_t a;
657 ip4_main_t *im = &ip4_main;
659 /* Honor dst_address_length. Fib masks are in network byte order */
660 a.dst_address.as_u32 = (dst_address->as_u32 &
661 im->fib_masks[dst_address_length]);
662 a.dst_address_length = dst_address_length;
663 a.adj_index = adj_index;
664 a.cover_adj_index = cover_adj_index;
665 a.cover_address_length = cover_address_length;
667 /* the top level ply is never removed */
668 unset_root_leaf (m, &a);
671 /* Returns number of bytes of memory used by mtrie. */
673 mtrie_ply_memory_usage (ip4_fib_mtrie_t * m, ip4_fib_mtrie_8_ply_t * p)
677 bytes = sizeof (p[0]);
678 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
680 ip4_fib_mtrie_leaf_t l = p->leaves[i];
681 if (ip4_fib_mtrie_leaf_is_next_ply (l))
682 bytes += mtrie_ply_memory_usage (m, get_next_ply_for_leaf (m, l));
688 /* Returns number of bytes of memory used by mtrie. */
690 ip4_fib_mtrie_memory_usage (ip4_fib_mtrie_t * m)
695 for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
697 ip4_fib_mtrie_leaf_t l = m->root_ply.leaves[i];
698 if (ip4_fib_mtrie_leaf_is_next_ply (l))
699 bytes += mtrie_ply_memory_usage (m, get_next_ply_for_leaf (m, l));
706 format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
708 ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
710 if (ip4_fib_mtrie_leaf_is_terminal (l))
711 s = format (s, "lb-index %d", ip4_fib_mtrie_leaf_get_adj_index (l));
713 s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
717 #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent) \
721 ip4_fib_mtrie_leaf_t _l = p->leaves[(_i)]; \
723 a = (_base_address) + ((_a) << (32 - (_ply_max_len))); \
724 ia.as_u32 = clib_host_to_net_u32 (a); \
725 ia_length = (_p)->dst_address_bits_of_leaves[(_i)]; \
726 s = format (s, "\n%U%U %U", \
727 format_white_space, (_indent) + 4, \
728 format_ip4_address_and_length, &ia, ia_length, \
729 format_ip4_fib_mtrie_leaf, _l); \
731 if (ip4_fib_mtrie_leaf_is_next_ply (_l)) \
732 s = format (s, "\n%U", \
733 format_ip4_fib_mtrie_ply, m, a, (_indent) + 8, \
734 ip4_fib_mtrie_leaf_get_next_ply_index (_l)); \
739 format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
741 ip4_fib_mtrie_t *m = va_arg (*va, ip4_fib_mtrie_t *);
742 u32 base_address = va_arg (*va, u32);
743 u32 indent = va_arg (*va, u32);
744 u32 ply_index = va_arg (*va, u32);
745 ip4_fib_mtrie_8_ply_t *p;
748 p = pool_elt_at_index (ip4_ply_pool, ply_index);
749 s = format (s, "%Uply index %d, %d non-empty leaves",
750 format_white_space, indent, ply_index, p->n_non_empty_leafs);
752 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
754 if (ip4_fib_mtrie_leaf_is_non_empty (p, i))
756 s = FORMAT_PLY (s, p, i, i, base_address,
757 p->dst_address_bits_base + 8, indent);
765 format_ip4_fib_mtrie (u8 * s, va_list * va)
767 ip4_fib_mtrie_t *m = va_arg (*va, ip4_fib_mtrie_t *);
768 int verbose = va_arg (*va, int);
769 ip4_fib_mtrie_16_ply_t *p;
770 u32 base_address = 0;
773 s = format (s, "%d plies, memory usage %U\n",
774 pool_elts (ip4_ply_pool),
775 format_memory_size, ip4_fib_mtrie_memory_usage (m));
776 s = format (s, "root-ply");
781 s = format (s, "root-ply");
784 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
788 slot = clib_host_to_net_u16 (i);
790 if (p->dst_address_bits_of_leaves[slot] > 0)
792 s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
800 /** Default heap size for the IPv4 mtries */
801 #define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE (32<<20)
803 static clib_error_t *
804 ip4_mtrie_module_init (vlib_main_t * vm)
806 CLIB_UNUSED (ip4_fib_mtrie_8_ply_t * p);
807 ip4_main_t *im = &ip4_main;
808 clib_error_t *error = NULL;
811 if (0 == im->mtrie_heap_size)
812 im->mtrie_heap_size = IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE;
813 #if USE_DLMALLOC == 0
814 im->mtrie_mheap = mheap_alloc (0, im->mtrie_heap_size);
816 im->mtrie_mheap = create_mspace (im->mtrie_heap_size, 1 /* locked */ );
819 /* Burn one ply so index 0 is taken */
820 old_heap = clib_mem_set_heap (ip4_main.mtrie_mheap);
821 pool_get (ip4_ply_pool, p);
822 clib_mem_set_heap (old_heap);
827 VLIB_INIT_FUNCTION (ip4_mtrie_module_init);
830 * fd.io coding-style-patch-verification: ON
833 * eval: (c-set-style "gnu")