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_mtrie_8_ply_t *ip4_ply_pool;
51 ip4_mtrie_leaf_is_non_empty (ip4_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_mtrie_leaf_t
64 ip4_mtrie_leaf_set_adj_index (u32 adj_index)
67 l = 1 + 2 * adj_index;
68 ASSERT (ip4_mtrie_leaf_get_adj_index (l) == adj_index);
73 ip4_mtrie_leaf_is_next_ply (ip4_mtrie_leaf_t n)
79 ip4_mtrie_leaf_get_next_ply_index (ip4_mtrie_leaf_t n)
81 ASSERT (ip4_mtrie_leaf_is_next_ply (n));
85 always_inline ip4_mtrie_leaf_t
86 ip4_mtrie_leaf_set_next_ply_index (u32 i)
90 ASSERT (ip4_mtrie_leaf_get_next_ply_index (l) == i);
95 ply_8_init (ip4_mtrie_8_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len,
98 p->n_non_empty_leafs = prefix_len > ply_base_len ? ARRAY_LEN (p->leaves) : 0;
99 clib_memset_u8 (p->dst_address_bits_of_leaves, prefix_len,
100 sizeof (p->dst_address_bits_of_leaves));
101 p->dst_address_bits_base = ply_base_len;
103 clib_memset_u32 (p->leaves, init, ARRAY_LEN (p->leaves));
107 ply_16_init (ip4_mtrie_16_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len)
109 clib_memset_u8 (p->dst_address_bits_of_leaves, prefix_len,
110 sizeof (p->dst_address_bits_of_leaves));
111 clib_memset_u32 (p->leaves, init, ARRAY_LEN (p->leaves));
114 static ip4_mtrie_leaf_t
115 ply_create (ip4_mtrie_leaf_t init_leaf, u32 leaf_prefix_len, u32 ply_base_len)
117 ip4_mtrie_8_ply_t *p;
119 u8 need_barrier_sync = pool_get_will_expand (ip4_ply_pool);
120 vlib_main_t *vm = vlib_get_main ();
121 ASSERT (vm->thread_index == 0);
123 if (need_barrier_sync)
124 vlib_worker_thread_barrier_sync (vm);
126 /* Get cache aligned ply. */
127 pool_get_aligned (ip4_ply_pool, p, CLIB_CACHE_LINE_BYTES);
129 ply_8_init (p, init_leaf, leaf_prefix_len, ply_base_len);
130 l = ip4_mtrie_leaf_set_next_ply_index (p - ip4_ply_pool);
132 if (need_barrier_sync)
133 vlib_worker_thread_barrier_release (vm);
138 always_inline ip4_mtrie_8_ply_t *
139 get_next_ply_for_leaf (ip4_mtrie_leaf_t l)
141 uword n = ip4_mtrie_leaf_get_next_ply_index (l);
143 return pool_elt_at_index (ip4_ply_pool, n);
147 ip4_mtrie_16_free (ip4_mtrie_16_t *m)
149 /* the root ply is embedded so there is nothing to do,
150 * the assumption being that the IP4 FIB table has emptied the trie
155 for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
157 ASSERT (!ip4_mtrie_leaf_is_next_ply (m->root_ply.leaves[i]));
163 ip4_mtrie_16_init (ip4_mtrie_16_t *m)
165 ply_16_init (&m->root_ply, IP4_MTRIE_LEAF_EMPTY, 0);
169 ip4_mtrie_8_free (ip4_mtrie_8_t *m)
171 /* the root ply is embedded so there is nothing to do,
172 * the assumption being that the IP4 FIB table has emptied the trie
175 ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
179 for (i = 0; i < ARRAY_LEN (root->leaves); i++)
181 ASSERT (!ip4_mtrie_leaf_is_next_ply (root->leaves[i]));
185 pool_put (ip4_ply_pool, root);
189 ip4_mtrie_8_init (ip4_mtrie_8_t *m)
191 ip4_mtrie_8_ply_t *root;
193 pool_get (ip4_ply_pool, root);
194 m->root_ply = root - ip4_ply_pool;
196 ply_8_init (root, IP4_MTRIE_LEAF_EMPTY, 0, 0);
201 ip4_address_t dst_address;
202 u32 dst_address_length;
204 u32 cover_address_length;
206 } ip4_mtrie_set_unset_leaf_args_t;
209 set_ply_with_more_specific_leaf (ip4_mtrie_8_ply_t *ply,
210 ip4_mtrie_leaf_t new_leaf,
211 uword new_leaf_dst_address_bits)
213 ip4_mtrie_leaf_t old_leaf;
216 ASSERT (ip4_mtrie_leaf_is_terminal (new_leaf));
218 for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
220 old_leaf = ply->leaves[i];
222 /* Recurse into sub plies. */
223 if (!ip4_mtrie_leaf_is_terminal (old_leaf))
225 ip4_mtrie_8_ply_t *sub_ply = get_next_ply_for_leaf (old_leaf);
226 set_ply_with_more_specific_leaf (sub_ply, new_leaf,
227 new_leaf_dst_address_bits);
230 /* Replace less specific terminal leaves with new leaf. */
231 else if (new_leaf_dst_address_bits >=
232 ply->dst_address_bits_of_leaves[i])
234 clib_atomic_store_rel_n (&ply->leaves[i], new_leaf);
235 ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
236 ply->n_non_empty_leafs += ip4_mtrie_leaf_is_non_empty (ply, i);
242 set_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index,
243 u32 dst_address_byte_index)
245 ip4_mtrie_leaf_t old_leaf, new_leaf;
246 i32 n_dst_bits_next_plies;
248 ip4_mtrie_8_ply_t *old_ply;
250 old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
252 ASSERT (a->dst_address_length <= 32);
253 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
255 /* how many bits of the destination address are in the next PLY */
256 n_dst_bits_next_plies =
257 a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
259 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
261 /* Number of bits next plies <= 0 => insert leaves this ply. */
262 if (n_dst_bits_next_plies <= 0)
264 /* The mask length of the address to insert maps to this ply */
265 uword old_leaf_is_terminal;
266 u32 i, n_dst_bits_this_ply;
268 /* The number of bits, and hence slots/buckets, we will fill */
269 n_dst_bits_this_ply = clib_min (8, -n_dst_bits_next_plies);
270 ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
271 pow2_mask (n_dst_bits_this_ply)) == 0);
273 /* Starting at the value of the byte at this section of the v4 address
274 * fill the buckets/slots of the ply */
275 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
277 ip4_mtrie_8_ply_t *new_ply;
279 old_leaf = old_ply->leaves[i];
280 old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
282 if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
284 /* The new leaf is more or equally specific than the one currently
285 * occupying the slot */
286 new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
288 if (old_leaf_is_terminal)
290 /* The current leaf is terminal, we can replace it with
292 old_ply->n_non_empty_leafs -=
293 ip4_mtrie_leaf_is_non_empty (old_ply, i);
295 old_ply->dst_address_bits_of_leaves[i] =
296 a->dst_address_length;
297 clib_atomic_store_rel_n (&old_ply->leaves[i], new_leaf);
299 old_ply->n_non_empty_leafs +=
300 ip4_mtrie_leaf_is_non_empty (old_ply, i);
301 ASSERT (old_ply->n_non_empty_leafs <=
302 ARRAY_LEN (old_ply->leaves));
306 /* Existing leaf points to another ply. We need to place
307 * new_leaf into all more specific slots. */
308 new_ply = get_next_ply_for_leaf (old_leaf);
309 set_ply_with_more_specific_leaf (new_ply, new_leaf,
310 a->dst_address_length);
313 else if (!old_leaf_is_terminal)
315 /* The current leaf is less specific and not termial (i.e. a ply),
316 * recurse on down the trie */
317 new_ply = get_next_ply_for_leaf (old_leaf);
318 set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
322 * the route we are adding is less specific than the leaf currently
323 * occupying this slot. leave it there
329 /* The address to insert requires us to move down at a lower level of
330 * the trie - recurse on down */
331 ip4_mtrie_8_ply_t *new_ply;
334 ply_base_len = 8 * (dst_address_byte_index + 1);
336 old_leaf = old_ply->leaves[dst_byte];
338 if (ip4_mtrie_leaf_is_terminal (old_leaf))
340 /* There is a leaf occupying the slot. Replace it with a new ply */
341 old_ply->n_non_empty_leafs -=
342 ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
344 new_leaf = ply_create (old_leaf,
345 old_ply->dst_address_bits_of_leaves[dst_byte],
347 new_ply = get_next_ply_for_leaf (new_leaf);
349 /* Refetch since ply_create may move pool. */
350 old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
352 clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
353 old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
355 old_ply->n_non_empty_leafs +=
356 ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
357 ASSERT (old_ply->n_non_empty_leafs >= 0);
360 new_ply = get_next_ply_for_leaf (old_leaf);
362 set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
367 set_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
369 ip4_mtrie_leaf_t old_leaf, new_leaf;
370 ip4_mtrie_16_ply_t *old_ply;
371 i32 n_dst_bits_next_plies;
374 old_ply = &m->root_ply;
376 ASSERT (a->dst_address_length <= 32);
378 /* how many bits of the destination address are in the next PLY */
379 n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
381 dst_byte = a->dst_address.as_u16[0];
383 /* Number of bits next plies <= 0 => insert leaves this ply. */
384 if (n_dst_bits_next_plies <= 0)
386 /* The mask length of the address to insert maps to this ply */
387 uword old_leaf_is_terminal;
388 u32 i, n_dst_bits_this_ply;
390 /* The number of bits, and hence slots/buckets, we will fill */
391 n_dst_bits_this_ply = 16 - a->dst_address_length;
392 ASSERT ((clib_host_to_net_u16 (a->dst_address.as_u16[0]) &
393 pow2_mask (n_dst_bits_this_ply)) == 0);
395 /* Starting at the value of the byte at this section of the v4 address
396 * fill the buckets/slots of the ply */
397 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
399 ip4_mtrie_8_ply_t *new_ply;
402 slot = clib_net_to_host_u16 (dst_byte);
404 slot = clib_host_to_net_u16 (slot);
406 old_leaf = old_ply->leaves[slot];
407 old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
409 if (a->dst_address_length >=
410 old_ply->dst_address_bits_of_leaves[slot])
412 /* The new leaf is more or equally specific than the one currently
413 * occupying the slot */
414 new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
416 if (old_leaf_is_terminal)
418 /* The current leaf is terminal, we can replace it with
420 old_ply->dst_address_bits_of_leaves[slot] =
421 a->dst_address_length;
422 clib_atomic_store_rel_n (&old_ply->leaves[slot], new_leaf);
426 /* Existing leaf points to another ply. We need to place
427 * new_leaf into all more specific slots. */
428 new_ply = get_next_ply_for_leaf (old_leaf);
429 set_ply_with_more_specific_leaf (new_ply, new_leaf,
430 a->dst_address_length);
433 else if (!old_leaf_is_terminal)
435 /* The current leaf is less specific and not termial (i.e. a ply),
436 * recurse on down the trie */
437 new_ply = get_next_ply_for_leaf (old_leaf);
438 set_leaf (a, new_ply - ip4_ply_pool, 2);
442 * the route we are adding is less specific than the leaf currently
443 * occupying this slot. leave it there
449 /* The address to insert requires us to move down at a lower level of
450 * the trie - recurse on down */
451 ip4_mtrie_8_ply_t *new_ply;
456 old_leaf = old_ply->leaves[dst_byte];
458 if (ip4_mtrie_leaf_is_terminal (old_leaf))
460 /* There is a leaf occupying the slot. Replace it with a new ply */
461 new_leaf = ply_create (old_leaf,
462 old_ply->dst_address_bits_of_leaves[dst_byte],
464 new_ply = get_next_ply_for_leaf (new_leaf);
466 clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
467 old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
470 new_ply = get_next_ply_for_leaf (old_leaf);
472 set_leaf (a, new_ply - ip4_ply_pool, 2);
477 unset_leaf (const ip4_mtrie_set_unset_leaf_args_t *a,
478 ip4_mtrie_8_ply_t *old_ply, u32 dst_address_byte_index)
480 ip4_mtrie_leaf_t old_leaf, del_leaf;
481 i32 n_dst_bits_next_plies;
482 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
485 ASSERT (a->dst_address_length <= 32);
486 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
488 n_dst_bits_next_plies =
489 a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
491 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
492 if (n_dst_bits_next_plies < 0)
493 dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
495 n_dst_bits_this_ply =
496 n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
497 n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
499 del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
501 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
503 old_leaf = old_ply->leaves[i];
504 old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
506 if (old_leaf == del_leaf ||
507 (!old_leaf_is_terminal &&
508 unset_leaf (a, get_next_ply_for_leaf (old_leaf),
509 dst_address_byte_index + 1)))
511 old_ply->n_non_empty_leafs -=
512 ip4_mtrie_leaf_is_non_empty (old_ply, i);
514 clib_atomic_store_rel_n (
516 ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
517 old_ply->dst_address_bits_of_leaves[i] = a->cover_address_length;
519 old_ply->n_non_empty_leafs +=
520 ip4_mtrie_leaf_is_non_empty (old_ply, i);
522 ASSERT (old_ply->n_non_empty_leafs >= 0);
523 if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
525 pool_put (ip4_ply_pool, old_ply);
526 /* Old ply was deleted. */
530 else if (dst_address_byte_index)
533 for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
535 count += ip4_mtrie_leaf_is_non_empty (old_ply, ii);
543 /* Old ply was not deleted. */
548 unset_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
550 ip4_mtrie_leaf_t old_leaf, del_leaf;
551 i32 n_dst_bits_next_plies;
552 i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
554 ip4_mtrie_16_ply_t *old_ply;
556 ASSERT (a->dst_address_length <= 32);
558 old_ply = &m->root_ply;
559 n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
561 dst_byte = a->dst_address.as_u16[0];
563 n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
564 (16 - a->dst_address_length) : 0);
566 del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
568 /* Starting at the value of the byte at this section of the v4 address
569 * fill the buckets/slots of the ply */
570 for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
574 slot = clib_net_to_host_u16 (dst_byte);
576 slot = clib_host_to_net_u16 (slot);
578 old_leaf = old_ply->leaves[slot];
579 old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
581 if (old_leaf == del_leaf ||
582 (!old_leaf_is_terminal &&
583 unset_leaf (a, get_next_ply_for_leaf (old_leaf), 2)))
585 clib_atomic_store_rel_n (
586 &old_ply->leaves[slot],
587 ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
588 old_ply->dst_address_bits_of_leaves[slot] = a->cover_address_length;
594 ip4_mtrie_16_route_add (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
595 u32 dst_address_length, u32 adj_index)
597 ip4_mtrie_set_unset_leaf_args_t a;
598 ip4_main_t *im = &ip4_main;
600 /* Honor dst_address_length. Fib masks are in network byte order */
601 a.dst_address.as_u32 = (dst_address->as_u32 &
602 im->fib_masks[dst_address_length]);
603 a.dst_address_length = dst_address_length;
604 a.adj_index = adj_index;
606 set_root_leaf (m, &a);
610 ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
611 u32 dst_address_length, u32 adj_index)
613 ip4_mtrie_set_unset_leaf_args_t a;
614 ip4_main_t *im = &ip4_main;
616 /* Honor dst_address_length. Fib masks are in network byte order */
617 a.dst_address.as_u32 =
618 (dst_address->as_u32 & im->fib_masks[dst_address_length]);
619 a.dst_address_length = dst_address_length;
620 a.adj_index = adj_index;
622 ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
624 set_leaf (&a, root - ip4_ply_pool, 0);
628 ip4_mtrie_16_route_del (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
629 u32 dst_address_length, u32 adj_index,
630 u32 cover_address_length, u32 cover_adj_index)
632 ip4_mtrie_set_unset_leaf_args_t a;
633 ip4_main_t *im = &ip4_main;
635 /* Honor dst_address_length. Fib masks are in network byte order */
636 a.dst_address.as_u32 = (dst_address->as_u32 &
637 im->fib_masks[dst_address_length]);
638 a.dst_address_length = dst_address_length;
639 a.adj_index = adj_index;
640 a.cover_adj_index = cover_adj_index;
641 a.cover_address_length = cover_address_length;
643 /* the top level ply is never removed */
644 unset_root_leaf (m, &a);
648 ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
649 u32 dst_address_length, u32 adj_index,
650 u32 cover_address_length, u32 cover_adj_index)
652 ip4_main_t *im = &ip4_main;
654 /* Honor dst_address_length. Fib masks are in network byte order */
655 ip4_mtrie_set_unset_leaf_args_t a = {
656 .dst_address.as_u32 =
657 (dst_address->as_u32 & im->fib_masks[dst_address_length]),
658 .dst_address_length = dst_address_length,
659 .adj_index = adj_index,
660 .cover_adj_index = cover_adj_index,
661 .cover_address_length = cover_address_length,
664 /* the top level ply is never removed */
665 ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
667 unset_leaf (&a, root, 0);
670 /* Returns number of bytes of memory used by mtrie. */
672 mtrie_ply_memory_usage (ip4_mtrie_8_ply_t *p)
676 bytes = sizeof (p[0]);
677 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
679 ip4_mtrie_leaf_t l = p->leaves[i];
680 if (ip4_mtrie_leaf_is_next_ply (l))
681 bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
687 /* Returns number of bytes of memory used by mtrie. */
689 ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
694 for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
696 ip4_mtrie_leaf_t l = m->root_ply.leaves[i];
697 if (ip4_mtrie_leaf_is_next_ply (l))
698 bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
704 ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
706 ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
710 for (i = 0; i < ARRAY_LEN (root->leaves); i++)
712 ip4_mtrie_leaf_t l = root->leaves[i];
713 if (ip4_mtrie_leaf_is_next_ply (l))
714 bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
721 format_ip4_mtrie_leaf (u8 *s, va_list *va)
723 ip4_mtrie_leaf_t l = va_arg (*va, ip4_mtrie_leaf_t);
725 if (ip4_mtrie_leaf_is_terminal (l))
726 s = format (s, "lb-index %d", ip4_mtrie_leaf_get_adj_index (l));
728 s = format (s, "next ply %d", ip4_mtrie_leaf_get_next_ply_index (l));
732 #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent) \
736 ip4_mtrie_leaf_t _l = (_p)->leaves[(_i)]; \
738 a = (_base_address) + ((_a) << (32 - (_ply_max_len))); \
739 ia.as_u32 = clib_host_to_net_u32 (a); \
740 ia_length = (_p)->dst_address_bits_of_leaves[(_i)]; \
741 s = format (s, "\n%U%U %U", format_white_space, (_indent) + 4, \
742 format_ip4_address_and_length, &ia, ia_length, \
743 format_ip4_mtrie_leaf, _l); \
745 if (ip4_mtrie_leaf_is_next_ply (_l)) \
746 s = format (s, "\n%U", format_ip4_mtrie_ply, m, a, (_indent) + 8, \
747 ip4_mtrie_leaf_get_next_ply_index (_l)); \
752 format_ip4_mtrie_ply (u8 *s, va_list *va)
754 ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
755 u32 base_address = va_arg (*va, u32);
756 u32 indent = va_arg (*va, u32);
757 u32 ply_index = va_arg (*va, u32);
758 ip4_mtrie_8_ply_t *p;
761 p = pool_elt_at_index (ip4_ply_pool, ply_index);
762 s = format (s, "%Uply index %d, %d non-empty leaves",
763 format_white_space, indent, ply_index, p->n_non_empty_leafs);
765 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
767 if (ip4_mtrie_leaf_is_non_empty (p, i))
769 s = FORMAT_PLY (s, p, i, i, base_address,
770 p->dst_address_bits_base + 8, indent);
778 format_ip4_mtrie_16 (u8 *s, va_list *va)
780 ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
781 int verbose = va_arg (*va, int);
782 ip4_mtrie_16_ply_t *p;
783 u32 base_address = 0;
787 format (s, "16-8-8: %d plies, memory usage %U\n", pool_elts (ip4_ply_pool),
788 format_memory_size, ip4_mtrie_16_memory_usage (m));
793 s = format (s, "root-ply");
796 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
800 slot = clib_host_to_net_u16 (i);
802 if (p->dst_address_bits_of_leaves[slot] > 0)
804 s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
813 format_ip4_mtrie_8 (u8 *s, va_list *va)
815 ip4_mtrie_8_t *m = va_arg (*va, ip4_mtrie_8_t *);
816 int verbose = va_arg (*va, int);
817 ip4_mtrie_8_ply_t *root;
818 u32 base_address = 0;
821 root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
823 s = format (s, "8-8-8-8; %d plies, memory usage %U\n",
824 pool_elts (ip4_ply_pool), format_memory_size,
825 ip4_mtrie_8_memory_usage (m));
829 s = format (s, "root-ply");
831 for (slot = 0; slot < ARRAY_LEN (root->leaves); slot++)
833 if (root->dst_address_bits_of_leaves[slot] > 0)
835 s = FORMAT_PLY (s, root, slot, slot, base_address, 8, 0);
843 /** Default heap size for the IPv4 mtries */
844 #define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE (32<<20)
845 #ifndef MAP_HUGE_SHIFT
846 #define MAP_HUGE_SHIFT 26
849 static clib_error_t *
850 ip4_mtrie_module_init (vlib_main_t * vm)
852 CLIB_UNUSED (ip4_mtrie_8_ply_t * p);
853 clib_error_t *error = NULL;
855 /* Burn one ply so index 0 is taken */
856 pool_get (ip4_ply_pool, p);
861 VLIB_INIT_FUNCTION (ip4_mtrie_module_init);
864 * fd.io coding-style-patch-verification: ON
867 * eval: (c-set-style "gnu")