vnet/vnet/ip/ip4_mtrie.c

   1 /*
   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:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   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.
  14  */
  15 /*
  16  * ip/ip4_fib.h: ip4 mtrie fib
  17  *
  18  * Copyright (c) 2012 Eliot Dresselhaus
  19  *
  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:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  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.
  38  */
  39
  40 #include <vnet/ip/ip.h>
  41
  42 static void
  43 ply_init (ip4_fib_mtrie_ply_t * p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
  44 {
  45   p->n_non_empty_leafs = ip4_fib_mtrie_leaf_is_empty (init) ? 0 : ARRAY_LEN (p->leaves);
  46   memset (p->dst_address_bits_of_leaves, prefix_len, sizeof (p->dst_address_bits_of_leaves));
  47
  48   /* Initialize leaves. */
  49 #ifdef CLIB_HAVE_VEC128
  50   {
  51     u32x4 * l, init_x4;
  52
  53 #ifndef __ALTIVEC__
  54     init_x4 = u32x4_splat (init);
  55 #else
  56     {
  57       u32x4_union_t y;
  58       y.as_u32[0] = init;
  59       y.as_u32[1] = init;
  60       y.as_u32[2] = init;
  61       y.as_u32[3] = init;
  62       init_x4 = y.as_u32x4;
  63     }
  64 #endif
  65
  66     for (l = p->leaves_as_u32x4; l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); l += 4)
  67       {
  68         l[0] = init_x4;
  69         l[1] = init_x4;
  70         l[2] = init_x4;
  71         l[3] = init_x4;
  72       }
  73   }
  74 #else
  75   {
  76     u32 * l;
  77
  78     for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4)
  79       {
  80         l[0] = init;
  81         l[1] = init;
  82         l[2] = init;
  83         l[3] = init;
  84       }
  85   }
  86 #endif
  87 }
  88
  89 static ip4_fib_mtrie_leaf_t
  90 ply_create (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t init_leaf, uword prefix_len)
  91 {
  92   ip4_fib_mtrie_ply_t * p;
  93
  94   /* Get cache aligned ply. */
  95   pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
  96
  97   ply_init (p, init_leaf, prefix_len);
  98   return ip4_fib_mtrie_leaf_set_next_ply_index (p - m->ply_pool);
  99 }
 100
 101 always_inline ip4_fib_mtrie_ply_t *
 102 get_next_ply_for_leaf (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t l)
 103 {
 104   uword n = ip4_fib_mtrie_leaf_get_next_ply_index (l);
 105   /* It better not be the root ply. */
 106   ASSERT (n != 0);
 107   return pool_elt_at_index (m->ply_pool, n);
 108 }
 109
 110 static void
 111 ply_free (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
 112 {
 113   uword i, is_root;
 114
 115   is_root = p - m->ply_pool == 0;
 116
 117   for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
 118     {
 119       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 120       if (ip4_fib_mtrie_leaf_is_next_ply (l))
 121         ply_free (m, get_next_ply_for_leaf (m, l));
 122     }
 123
 124   if (is_root)
 125     ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
 126   else
 127     pool_put (m->ply_pool, p);
 128 }
 129
 130 void ip4_fib_free (ip4_fib_mtrie_t * m)
 131 {
 132   ip4_fib_mtrie_ply_t * root_ply = pool_elt_at_index (m->ply_pool, 0);
 133   ply_free (m, root_ply);
 134 }
 135
 136 u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst)
 137 {
 138   ip4_fib_mtrie_ply_t * p = pool_elt_at_index (m->ply_pool, 0);
 139   ip4_fib_mtrie_leaf_t l;
 140
 141   l = p->leaves[dst.as_u8[0]];
 142   if (ip4_fib_mtrie_leaf_is_terminal (l))
 143     return ip4_fib_mtrie_leaf_get_adj_index (l);
 144
 145   p = get_next_ply_for_leaf (m, l);
 146   l = p->leaves[dst.as_u8[1]];
 147   if (ip4_fib_mtrie_leaf_is_terminal (l))
 148     return ip4_fib_mtrie_leaf_get_adj_index (l);
 149
 150   p = get_next_ply_for_leaf (m, l);
 151   l = p->leaves[dst.as_u8[2]];
 152   if (ip4_fib_mtrie_leaf_is_terminal (l))
 153     return ip4_fib_mtrie_leaf_get_adj_index (l);
 154
 155   p = get_next_ply_for_leaf (m, l);
 156   l = p->leaves[dst.as_u8[3]];
 157
 158   ASSERT (ip4_fib_mtrie_leaf_is_terminal (l));
 159   return ip4_fib_mtrie_leaf_get_adj_index (l);
 160 }
 161
 162 typedef struct {
 163   ip4_address_t dst_address;
 164   u32 dst_address_length;
 165   u32 adj_index;
 166 } ip4_fib_mtrie_set_unset_leaf_args_t;
 167
 168 static void
 169 set_ply_with_more_specific_leaf (ip4_fib_mtrie_t * m,
 170                                  ip4_fib_mtrie_ply_t * ply,
 171                                  ip4_fib_mtrie_leaf_t new_leaf,
 172                                  uword new_leaf_dst_address_bits)
 173 {
 174   ip4_fib_mtrie_leaf_t old_leaf;
 175   uword i;
 176
 177   ASSERT (ip4_fib_mtrie_leaf_is_terminal (new_leaf));
 178   ASSERT (! ip4_fib_mtrie_leaf_is_empty (new_leaf));
 179
 180   for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
 181     {
 182       old_leaf = ply->leaves[i];
 183
 184       /* Recurse into sub plies. */
 185       if (! ip4_fib_mtrie_leaf_is_terminal (old_leaf))
 186         {
 187           ip4_fib_mtrie_ply_t * sub_ply = get_next_ply_for_leaf (m, old_leaf);
 188           set_ply_with_more_specific_leaf (m, sub_ply, new_leaf, new_leaf_dst_address_bits);
 189         }
 190
 191       /* Replace less specific terminal leaves with new leaf. */
 192       else if (new_leaf_dst_address_bits >= ply->dst_address_bits_of_leaves[i])
 193         {
 194           __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
 195           ASSERT(ply->leaves[i] == new_leaf);
 196           ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
 197           ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
 198         }
 199     }
 200 }
 201
 202 static void
 203 set_leaf (ip4_fib_mtrie_t * m,
 204           ip4_fib_mtrie_set_unset_leaf_args_t * a,
 205           u32 old_ply_index,
 206           u32 dst_address_byte_index)
 207 {
 208   ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
 209   i32 n_dst_bits_next_plies;
 210   u8 dst_byte;
 211
 212   ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
 213   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 214
 215   n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 216
 217   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 218
 219   /* Number of bits next plies <= 0 => insert leaves this ply. */
 220   if (n_dst_bits_next_plies <= 0)
 221     {
 222       uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
 223
 224       n_dst_bits_this_ply = -n_dst_bits_next_plies;
 225       ASSERT ((a->dst_address.as_u8[dst_address_byte_index] & pow2_mask (n_dst_bits_this_ply)) == 0);
 226
 227       for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 228         {
 229           ip4_fib_mtrie_ply_t * old_ply, * new_ply;
 230
 231           old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 232
 233           old_leaf = old_ply->leaves[i];
 234           old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
 235
 236           /* Is leaf to be inserted more specific? */
 237           if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
 238             {
 239               new_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
 240
 241               if (old_leaf_is_terminal)
 242                 {
 243                   old_ply->dst_address_bits_of_leaves[i] = a->dst_address_length;
 244                   __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
 245                                                new_leaf);
 246                   ASSERT(old_ply->leaves[i] == new_leaf);
 247                   old_ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
 248                   ASSERT (old_ply->n_non_empty_leafs <= ARRAY_LEN (old_ply->leaves));
 249                 }
 250               else
 251                 {
 252                   /* Existing leaf points to another ply.  We need to place new_leaf into all
 253                      more specific slots. */
 254                   new_ply = get_next_ply_for_leaf (m, old_leaf);
 255                   set_ply_with_more_specific_leaf (m, new_ply, new_leaf, a->dst_address_length);
 256                 }
 257             }
 258
 259           else if (! old_leaf_is_terminal)
 260             {
 261               new_ply = get_next_ply_for_leaf (m, old_leaf);
 262               set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
 263             }
 264         }
 265     }
 266   else
 267     {
 268       ip4_fib_mtrie_ply_t * old_ply, * new_ply;
 269
 270       old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 271       old_leaf = old_ply->leaves[dst_byte];
 272       if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
 273         {
 274           new_leaf = ply_create (m, old_leaf, old_ply->dst_address_bits_of_leaves[dst_byte]);
 275           new_ply = get_next_ply_for_leaf (m, new_leaf);
 276
 277           /* Refetch since ply_create may move pool. */
 278           old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 279
 280           __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
 281                                        new_leaf);
 282           ASSERT(old_ply->leaves[dst_byte] == new_leaf);
 283           old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
 284
 285           old_ply->n_non_empty_leafs -= ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
 286           ASSERT (old_ply->n_non_empty_leafs >= 0);
 287
 288           /* Account for the ply we just created. */
 289           old_ply->n_non_empty_leafs += 1;
 290         }
 291       else
 292         new_ply = get_next_ply_for_leaf (m, old_leaf);
 293
 294       set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
 295     }
 296 }
 297
 298 static uword
 299 unset_leaf (ip4_fib_mtrie_t * m,
 300             ip4_fib_mtrie_set_unset_leaf_args_t * a,
 301             ip4_fib_mtrie_ply_t * old_ply,
 302             u32 dst_address_byte_index)
 303 {
 304   ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
 305   i32 n_dst_bits_next_plies;
 306   i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
 307   u8 dst_byte;
 308
 309   ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
 310   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 311
 312   n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 313
 314   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 315   if (n_dst_bits_next_plies < 0)
 316     dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
 317
 318   n_dst_bits_this_ply = n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
 319   n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
 320
 321   del_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
 322
 323   for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 324     {
 325       old_leaf = old_ply->leaves[i];
 326       old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
 327
 328       if (old_leaf == del_leaf
 329           || (! old_leaf_is_terminal
 330               && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf), dst_address_byte_index + 1)))
 331         {
 332           old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
 333           old_ply->dst_address_bits_of_leaves[i] = 0;
 334
 335           /* No matter what we just deleted a non-empty leaf. */
 336           ASSERT (! ip4_fib_mtrie_leaf_is_empty (old_leaf));
 337           old_ply->n_non_empty_leafs -= 1;
 338
 339           ASSERT (old_ply->n_non_empty_leafs >= 0);
 340           if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
 341             {
 342               pool_put (m->ply_pool, old_ply);
 343               /* Old ply was deleted. */
 344               return 1;
 345             }
 346         }
 347     }
 348
 349   /* Old ply was not deleted. */
 350   return 0;
 351 }
 352
 353 void ip4_mtrie_init (ip4_fib_mtrie_t * m)
 354 {
 355   ip4_fib_mtrie_leaf_t root;
 356   memset (m, 0, sizeof (m[0]));
 357   m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
 358   root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */ 0);
 359   ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (root) == 0);
 360 }
 361
 362 void
 363 ip4_fib_mtrie_add_del_route (ip4_fib_t * fib,
 364                              ip4_address_t dst_address,
 365                              u32 dst_address_length,
 366                              u32 adj_index,
 367                              u32 is_del)
 368 {
 369   ip4_fib_mtrie_t * m = &fib->mtrie;
 370   ip4_fib_mtrie_ply_t * root_ply;
 371   ip4_fib_mtrie_set_unset_leaf_args_t a;
 372   ip4_main_t * im = &ip4_main;
 373
 374   ASSERT(m->ply_pool != 0);
 375
 376   root_ply = pool_elt_at_index (m->ply_pool, 0);
 377
 378   /* Honor dst_address_length. Fib masks are in network byte order */
 379   dst_address.as_u32 &= im->fib_masks[dst_address_length];
 380   a.dst_address = dst_address;
 381   a.dst_address_length = dst_address_length;
 382   a.adj_index = adj_index;
 383
 384   if (! is_del)
 385     {
 386       if (dst_address_length == 0)
 387         m->default_leaf = ip4_fib_mtrie_leaf_set_adj_index (adj_index);
 388       else
 389         set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
 390     }
 391   else
 392     {
 393       if (dst_address_length == 0)
 394         m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
 395
 396       else
 397         {
 398           ip4_main_t * im = &ip4_main;
 399           uword i;
 400
 401           unset_leaf (m, &a, root_ply, 0);
 402
 403           /* Find next less specific route and insert into mtrie. */
 404           for (i = ARRAY_LEN (fib->adj_index_by_dst_address) - 1; i >= 1; i--)
 405             {
 406               uword * p;
 407               ip4_address_t key;
 408
 409               if (! fib->adj_index_by_dst_address[i])
 410                 continue;
 411
 412               key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
 413               p = hash_get (fib->adj_index_by_dst_address[i], key.as_u32);
 414               if (p)
 415                 {
 416                   a.dst_address = key;
 417                   a.dst_address_length = i;
 418                   a.adj_index = p[0];
 419                   set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
 420                   break;
 421                 }
 422             }
 423         }
 424     }
 425 }
 426
 427 always_inline uword
 428 maybe_remap_leaf (ip_lookup_main_t * lm, ip4_fib_mtrie_leaf_t * p)
 429 {
 430   ip4_fib_mtrie_leaf_t l = p[0];
 431   uword was_remapped_to_empty_leaf = 0;
 432   if (ip4_fib_mtrie_leaf_is_terminal (l))
 433     {
 434       u32 adj_index = ip4_fib_mtrie_leaf_get_adj_index (l);
 435       u32 m = vec_elt (lm->adjacency_remap_table, adj_index);
 436       if (m)
 437         {
 438           was_remapped_to_empty_leaf = m == ~0;
 439
 440           /*
 441            * The intent of the original form - which dates to 2013 or
 442            * earlier - is not obvious. Here's the original:
 443            *
 444            * if (was_remapped_to_empty_leaf)
 445            *   p[0] = (was_remapped_to_empty_leaf
 446            *           ? IP4_FIB_MTRIE_LEAF_EMPTY
 447            *           : ip4_fib_mtrie_leaf_set_adj_index (m - 1));
 448            *
 449            * Notice the outer "if (was_remapped_to_empty_leaf)"
 450            * means that p[0] is always set to IP4_FIB_MTRIE_LEAF_EMPTY,
 451            * and is otherwise left intact.
 452            *
 453            * It seems unlikely that the adjacency mapping scheme
 454            * works in detail. Coverity correctly complains that the
 455            * else-case of the original ternary expression is dead code.
 456            */
 457           if (was_remapped_to_empty_leaf)
 458             p[0] = IP4_FIB_MTRIE_LEAF_EMPTY;
 459         }
 460     }
 461   return was_remapped_to_empty_leaf;
 462 }
 463
 464 static void maybe_remap_ply (ip_lookup_main_t * lm, ip4_fib_mtrie_ply_t * ply)
 465 {
 466   u32 n_remapped_to_empty = 0;
 467   u32 i;
 468   for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
 469     n_remapped_to_empty += maybe_remap_leaf (lm, &ply->leaves[i]);
 470   if (n_remapped_to_empty > 0)
 471     {
 472       ASSERT (n_remapped_to_empty <= ply->n_non_empty_leafs);
 473       ply->n_non_empty_leafs -= n_remapped_to_empty;
 474       if (ply->n_non_empty_leafs == 0)
 475         os_panic ();
 476     }
 477 }
 478
 479 void ip4_mtrie_maybe_remap_adjacencies (ip_lookup_main_t * lm, ip4_fib_mtrie_t * m)
 480 {
 481   ip4_fib_mtrie_ply_t * ply;
 482   pool_foreach (ply, m->ply_pool, maybe_remap_ply (lm, ply));
 483   maybe_remap_leaf (lm, &m->default_leaf);
 484 }
 485
 486 /* Returns number of bytes of memory used by mtrie. */
 487 static uword mtrie_memory_usage (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
 488 {
 489   uword bytes, i;
 490
 491   if (! p)
 492     {
 493       if (pool_is_free_index (m->ply_pool, 0))
 494         return 0;
 495       p = pool_elt_at_index (m->ply_pool, 0);
 496     }
 497
 498   bytes = sizeof (p[0]);
 499   for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
 500     {
 501       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 502       if (ip4_fib_mtrie_leaf_is_next_ply (l))
 503         bytes += mtrie_memory_usage (m, get_next_ply_for_leaf (m, l));
 504     }
 505
 506   return bytes;
 507 }
 508
 509 static u8 * format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
 510 {
 511   ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
 512
 513   if (ip4_fib_mtrie_leaf_is_empty (l))
 514     s = format (s, "miss");
 515   else if (ip4_fib_mtrie_leaf_is_terminal (l))
 516     s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
 517   else
 518     s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
 519   return s;
 520 }
 521
 522 static u8 * format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
 523 {
 524   ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
 525   u32 base_address = va_arg (*va, u32);
 526   u32 ply_index = va_arg (*va, u32);
 527   u32 dst_address_byte_index = va_arg (*va, u32);
 528   ip4_fib_mtrie_ply_t * p;
 529   uword i, indent;
 530
 531   p = pool_elt_at_index (m->ply_pool, ply_index);
 532   indent = format_get_indent (s);
 533   s = format (s, "ply index %d, %d non-empty leaves", ply_index, p->n_non_empty_leafs);
 534   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 535     {
 536       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 537
 538       if (! ip4_fib_mtrie_leaf_is_empty (l))
 539         {
 540           u32 a, ia_length;
 541           ip4_address_t ia;
 542
 543           a = base_address + (i << (24 - 8*dst_address_byte_index));
 544           ia.as_u32 = clib_host_to_net_u32 (a);
 545           if (ip4_fib_mtrie_leaf_is_terminal (l))
 546             ia_length = p->dst_address_bits_of_leaves[i];
 547           else
 548             ia_length = 8*(1 + dst_address_byte_index);
 549           s = format (s, "\n%U%20U %U",
 550                       format_white_space, indent + 2,
 551                       format_ip4_address_and_length, &ia, ia_length,
 552                       format_ip4_fib_mtrie_leaf, l);
 553
 554           if (ip4_fib_mtrie_leaf_is_next_ply (l))
 555             s = format (s, "\n%U%U",
 556                         format_white_space, indent + 2,
 557                         format_ip4_fib_mtrie_ply, m, a,
 558                         ip4_fib_mtrie_leaf_get_next_ply_index (l),
 559                         dst_address_byte_index + 1);
 560         }
 561     }
 562
 563   return s;
 564 }
 565
 566 u8 * format_ip4_fib_mtrie (u8 * s, va_list * va)
 567 {
 568   ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
 569
 570   s = format (s, "%d plies, memory usage %U",
 571               pool_elts (m->ply_pool),
 572               format_memory_size, mtrie_memory_usage (m, 0));
 573
 574   if (pool_elts (m->ply_pool) > 0)
 575     {
 576       ip4_address_t base_address;
 577       base_address.as_u32 = 0;
 578       s = format (s, "\n  %U", format_ip4_fib_mtrie_ply, m, base_address, 0, 0);
 579     }
 580
 581   return s;
 582 }