src/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 #include <vnet/ip/ip4_mtrie.h>
  42 #include <vnet/fib/ip4_fib.h>
  43
  44
  45 /**
  46  * Global pool of IPv4 8bit PLYs
  47  */
  48 ip4_mtrie_8_ply_t *ip4_ply_pool;
  49
  50 always_inline u32
  51 ip4_mtrie_leaf_is_non_empty (ip4_mtrie_8_ply_t *p, u8 dst_byte)
  52 {
  53   /*
  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
  57    */
  58   if (p->dst_address_bits_of_leaves[dst_byte] > p->dst_address_bits_base)
  59     return (1);
  60   return (0);
  61 }
  62
  63 always_inline ip4_mtrie_leaf_t
  64 ip4_mtrie_leaf_set_adj_index (u32 adj_index)
  65 {
  66   ip4_mtrie_leaf_t l;
  67   l = 1 + 2 * adj_index;
  68   ASSERT (ip4_mtrie_leaf_get_adj_index (l) == adj_index);
  69   return l;
  70 }
  71
  72 always_inline u32
  73 ip4_mtrie_leaf_is_next_ply (ip4_mtrie_leaf_t n)
  74 {
  75   return (n & 1) == 0;
  76 }
  77
  78 always_inline u32
  79 ip4_mtrie_leaf_get_next_ply_index (ip4_mtrie_leaf_t n)
  80 {
  81   ASSERT (ip4_mtrie_leaf_is_next_ply (n));
  82   return n >> 1;
  83 }
  84
  85 always_inline ip4_mtrie_leaf_t
  86 ip4_mtrie_leaf_set_next_ply_index (u32 i)
  87 {
  88   ip4_mtrie_leaf_t l;
  89   l = 0 + 2 * i;
  90   ASSERT (ip4_mtrie_leaf_get_next_ply_index (l) == i);
  91   return l;
  92 }
  93
  94 static void
  95 ply_8_init (ip4_mtrie_8_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len,
  96             u32 ply_base_len)
  97 {
  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;
 102
 103   clib_memset_u32 (p->leaves, init, ARRAY_LEN (p->leaves));
 104 }
 105
 106 static void
 107 ply_16_init (ip4_mtrie_16_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len)
 108 {
 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));
 112 }
 113
 114 static ip4_mtrie_leaf_t
 115 ply_create (ip4_mtrie_leaf_t init_leaf, u32 leaf_prefix_len, u32 ply_base_len)
 116 {
 117   ip4_mtrie_8_ply_t *p;
 118   /* Get cache aligned ply. */
 119
 120   pool_get_aligned (ip4_ply_pool, p, CLIB_CACHE_LINE_BYTES);
 121
 122   ply_8_init (p, init_leaf, leaf_prefix_len, ply_base_len);
 123   return ip4_mtrie_leaf_set_next_ply_index (p - ip4_ply_pool);
 124 }
 125
 126 always_inline ip4_mtrie_8_ply_t *
 127 get_next_ply_for_leaf (ip4_mtrie_leaf_t l)
 128 {
 129   uword n = ip4_mtrie_leaf_get_next_ply_index (l);
 130
 131   return pool_elt_at_index (ip4_ply_pool, n);
 132 }
 133
 134 void
 135 ip4_mtrie_16_free (ip4_mtrie_16_t *m)
 136 {
 137   /* the root ply is embedded so there is nothing to do,
 138    * the assumption being that the IP4 FIB table has emptied the trie
 139    * before deletion.
 140    */
 141 #if CLIB_DEBUG > 0
 142   int i;
 143   for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
 144     {
 145       ASSERT (!ip4_mtrie_leaf_is_next_ply (m->root_ply.leaves[i]));
 146     }
 147 #endif
 148 }
 149
 150 void
 151 ip4_mtrie_16_init (ip4_mtrie_16_t *m)
 152 {
 153   ply_16_init (&m->root_ply, IP4_MTRIE_LEAF_EMPTY, 0);
 154 }
 155
 156 void
 157 ip4_mtrie_8_free (ip4_mtrie_8_t *m)
 158 {
 159   /* the root ply is embedded so there is nothing to do,
 160    * the assumption being that the IP4 FIB table has emptied the trie
 161    * before deletion.
 162    */
 163   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 164
 165 #if CLIB_DEBUG > 0
 166   int i;
 167   for (i = 0; i < ARRAY_LEN (root->leaves); i++)
 168     {
 169       ASSERT (!ip4_mtrie_leaf_is_next_ply (root->leaves[i]));
 170     }
 171 #endif
 172
 173   pool_put (ip4_ply_pool, root);
 174 }
 175
 176 void
 177 ip4_mtrie_8_init (ip4_mtrie_8_t *m)
 178 {
 179   ip4_mtrie_8_ply_t *root;
 180
 181   pool_get (ip4_ply_pool, root);
 182   m->root_ply = root - ip4_ply_pool;
 183
 184   ply_8_init (root, IP4_MTRIE_LEAF_EMPTY, 0, 0);
 185 }
 186
 187 typedef struct
 188 {
 189   ip4_address_t dst_address;
 190   u32 dst_address_length;
 191   u32 adj_index;
 192   u32 cover_address_length;
 193   u32 cover_adj_index;
 194 } ip4_mtrie_set_unset_leaf_args_t;
 195
 196 static void
 197 set_ply_with_more_specific_leaf (ip4_mtrie_8_ply_t *ply,
 198                                  ip4_mtrie_leaf_t new_leaf,
 199                                  uword new_leaf_dst_address_bits)
 200 {
 201   ip4_mtrie_leaf_t old_leaf;
 202   uword i;
 203
 204   ASSERT (ip4_mtrie_leaf_is_terminal (new_leaf));
 205
 206   for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
 207     {
 208       old_leaf = ply->leaves[i];
 209
 210       /* Recurse into sub plies. */
 211       if (!ip4_mtrie_leaf_is_terminal (old_leaf))
 212         {
 213           ip4_mtrie_8_ply_t *sub_ply = get_next_ply_for_leaf (old_leaf);
 214           set_ply_with_more_specific_leaf (sub_ply, new_leaf,
 215                                            new_leaf_dst_address_bits);
 216         }
 217
 218       /* Replace less specific terminal leaves with new leaf. */
 219       else if (new_leaf_dst_address_bits >=
 220                ply->dst_address_bits_of_leaves[i])
 221         {
 222           clib_atomic_store_rel_n (&ply->leaves[i], new_leaf);
 223           ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
 224           ply->n_non_empty_leafs += ip4_mtrie_leaf_is_non_empty (ply, i);
 225         }
 226     }
 227 }
 228
 229 static void
 230 set_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index,
 231           u32 dst_address_byte_index)
 232 {
 233   ip4_mtrie_leaf_t old_leaf, new_leaf;
 234   i32 n_dst_bits_next_plies;
 235   u8 dst_byte;
 236   ip4_mtrie_8_ply_t *old_ply;
 237
 238   old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
 239
 240   ASSERT (a->dst_address_length <= 32);
 241   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 242
 243   /* how many bits of the destination address are in the next PLY */
 244   n_dst_bits_next_plies =
 245     a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 246
 247   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 248
 249   /* Number of bits next plies <= 0 => insert leaves this ply. */
 250   if (n_dst_bits_next_plies <= 0)
 251     {
 252       /* The mask length of the address to insert maps to this ply */
 253       uword old_leaf_is_terminal;
 254       u32 i, n_dst_bits_this_ply;
 255
 256       /* The number of bits, and hence slots/buckets, we will fill */
 257       n_dst_bits_this_ply = clib_min (8, -n_dst_bits_next_plies);
 258       ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
 259                pow2_mask (n_dst_bits_this_ply)) == 0);
 260
 261       /* Starting at the value of the byte at this section of the v4 address
 262        * fill the buckets/slots of the ply */
 263       for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 264         {
 265           ip4_mtrie_8_ply_t *new_ply;
 266
 267           old_leaf = old_ply->leaves[i];
 268           old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 269
 270           if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
 271             {
 272               /* The new leaf is more or equally specific than the one currently
 273                * occupying the slot */
 274               new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 275
 276               if (old_leaf_is_terminal)
 277                 {
 278                   /* The current leaf is terminal, we can replace it with
 279                    * the new one */
 280                   old_ply->n_non_empty_leafs -=
 281                     ip4_mtrie_leaf_is_non_empty (old_ply, i);
 282
 283                   old_ply->dst_address_bits_of_leaves[i] =
 284                     a->dst_address_length;
 285                   clib_atomic_store_rel_n (&old_ply->leaves[i], new_leaf);
 286
 287                   old_ply->n_non_empty_leafs +=
 288                     ip4_mtrie_leaf_is_non_empty (old_ply, i);
 289                   ASSERT (old_ply->n_non_empty_leafs <=
 290                           ARRAY_LEN (old_ply->leaves));
 291                 }
 292               else
 293                 {
 294                   /* Existing leaf points to another ply.  We need to place
 295                    * new_leaf into all more specific slots. */
 296                   new_ply = get_next_ply_for_leaf (old_leaf);
 297                   set_ply_with_more_specific_leaf (new_ply, new_leaf,
 298                                                    a->dst_address_length);
 299                 }
 300             }
 301           else if (!old_leaf_is_terminal)
 302             {
 303               /* The current leaf is less specific and not termial (i.e. a ply),
 304                * recurse on down the trie */
 305               new_ply = get_next_ply_for_leaf (old_leaf);
 306               set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
 307             }
 308           /*
 309            * else
 310            *  the route we are adding is less specific than the leaf currently
 311            *  occupying this slot. leave it there
 312            */
 313         }
 314     }
 315   else
 316     {
 317       /* The address to insert requires us to move down at a lower level of
 318        * the trie - recurse on down */
 319       ip4_mtrie_8_ply_t *new_ply;
 320       u8 ply_base_len;
 321
 322       ply_base_len = 8 * (dst_address_byte_index + 1);
 323
 324       old_leaf = old_ply->leaves[dst_byte];
 325
 326       if (ip4_mtrie_leaf_is_terminal (old_leaf))
 327         {
 328           /* There is a leaf occupying the slot. Replace it with a new ply */
 329           old_ply->n_non_empty_leafs -=
 330             ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
 331
 332           new_leaf = ply_create (old_leaf,
 333                                  old_ply->dst_address_bits_of_leaves[dst_byte],
 334                                  ply_base_len);
 335           new_ply = get_next_ply_for_leaf (new_leaf);
 336
 337           /* Refetch since ply_create may move pool. */
 338           old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
 339
 340           clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
 341           old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
 342
 343           old_ply->n_non_empty_leafs +=
 344             ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
 345           ASSERT (old_ply->n_non_empty_leafs >= 0);
 346         }
 347       else
 348         new_ply = get_next_ply_for_leaf (old_leaf);
 349
 350       set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
 351     }
 352 }
 353
 354 static void
 355 set_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
 356 {
 357   ip4_mtrie_leaf_t old_leaf, new_leaf;
 358   ip4_mtrie_16_ply_t *old_ply;
 359   i32 n_dst_bits_next_plies;
 360   u16 dst_byte;
 361
 362   old_ply = &m->root_ply;
 363
 364   ASSERT (a->dst_address_length <= 32);
 365
 366   /* how many bits of the destination address are in the next PLY */
 367   n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
 368
 369   dst_byte = a->dst_address.as_u16[0];
 370
 371   /* Number of bits next plies <= 0 => insert leaves this ply. */
 372   if (n_dst_bits_next_plies <= 0)
 373     {
 374       /* The mask length of the address to insert maps to this ply */
 375       uword old_leaf_is_terminal;
 376       u32 i, n_dst_bits_this_ply;
 377
 378       /* The number of bits, and hence slots/buckets, we will fill */
 379       n_dst_bits_this_ply = 16 - a->dst_address_length;
 380       ASSERT ((clib_host_to_net_u16 (a->dst_address.as_u16[0]) &
 381                pow2_mask (n_dst_bits_this_ply)) == 0);
 382
 383       /* Starting at the value of the byte at this section of the v4 address
 384        * fill the buckets/slots of the ply */
 385       for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
 386         {
 387           ip4_mtrie_8_ply_t *new_ply;
 388           u16 slot;
 389
 390           slot = clib_net_to_host_u16 (dst_byte);
 391           slot += i;
 392           slot = clib_host_to_net_u16 (slot);
 393
 394           old_leaf = old_ply->leaves[slot];
 395           old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 396
 397           if (a->dst_address_length >=
 398               old_ply->dst_address_bits_of_leaves[slot])
 399             {
 400               /* The new leaf is more or equally specific than the one currently
 401                * occupying the slot */
 402               new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 403
 404               if (old_leaf_is_terminal)
 405                 {
 406                   /* The current leaf is terminal, we can replace it with
 407                    * the new one */
 408                   old_ply->dst_address_bits_of_leaves[slot] =
 409                     a->dst_address_length;
 410                   clib_atomic_store_rel_n (&old_ply->leaves[slot], new_leaf);
 411                 }
 412               else
 413                 {
 414                   /* Existing leaf points to another ply.  We need to place
 415                    * new_leaf into all more specific slots. */
 416                   new_ply = get_next_ply_for_leaf (old_leaf);
 417                   set_ply_with_more_specific_leaf (new_ply, new_leaf,
 418                                                    a->dst_address_length);
 419                 }
 420             }
 421           else if (!old_leaf_is_terminal)
 422             {
 423               /* The current leaf is less specific and not termial (i.e. a ply),
 424                * recurse on down the trie */
 425               new_ply = get_next_ply_for_leaf (old_leaf);
 426               set_leaf (a, new_ply - ip4_ply_pool, 2);
 427             }
 428           /*
 429            * else
 430            *  the route we are adding is less specific than the leaf currently
 431            *  occupying this slot. leave it there
 432            */
 433         }
 434     }
 435   else
 436     {
 437       /* The address to insert requires us to move down at a lower level of
 438        * the trie - recurse on down */
 439       ip4_mtrie_8_ply_t *new_ply;
 440       u8 ply_base_len;
 441
 442       ply_base_len = 16;
 443
 444       old_leaf = old_ply->leaves[dst_byte];
 445
 446       if (ip4_mtrie_leaf_is_terminal (old_leaf))
 447         {
 448           /* There is a leaf occupying the slot. Replace it with a new ply */
 449           new_leaf = ply_create (old_leaf,
 450                                  old_ply->dst_address_bits_of_leaves[dst_byte],
 451                                  ply_base_len);
 452           new_ply = get_next_ply_for_leaf (new_leaf);
 453
 454           clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
 455           old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
 456         }
 457       else
 458         new_ply = get_next_ply_for_leaf (old_leaf);
 459
 460       set_leaf (a, new_ply - ip4_ply_pool, 2);
 461     }
 462 }
 463
 464 static uword
 465 unset_leaf (const ip4_mtrie_set_unset_leaf_args_t *a,
 466             ip4_mtrie_8_ply_t *old_ply, u32 dst_address_byte_index)
 467 {
 468   ip4_mtrie_leaf_t old_leaf, del_leaf;
 469   i32 n_dst_bits_next_plies;
 470   i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
 471   u8 dst_byte;
 472
 473   ASSERT (a->dst_address_length <= 32);
 474   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 475
 476   n_dst_bits_next_plies =
 477     a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 478
 479   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 480   if (n_dst_bits_next_plies < 0)
 481     dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
 482
 483   n_dst_bits_this_ply =
 484     n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
 485   n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
 486
 487   del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 488
 489   for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 490     {
 491       old_leaf = old_ply->leaves[i];
 492       old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 493
 494       if (old_leaf == del_leaf ||
 495           (!old_leaf_is_terminal &&
 496            unset_leaf (a, get_next_ply_for_leaf (old_leaf),
 497                        dst_address_byte_index + 1)))
 498         {
 499           old_ply->n_non_empty_leafs -=
 500             ip4_mtrie_leaf_is_non_empty (old_ply, i);
 501
 502           clib_atomic_store_rel_n (
 503             &old_ply->leaves[i],
 504             ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
 505           old_ply->dst_address_bits_of_leaves[i] = a->cover_address_length;
 506
 507           old_ply->n_non_empty_leafs +=
 508             ip4_mtrie_leaf_is_non_empty (old_ply, i);
 509
 510           ASSERT (old_ply->n_non_empty_leafs >= 0);
 511           if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
 512             {
 513               pool_put (ip4_ply_pool, old_ply);
 514               /* Old ply was deleted. */
 515               return 1;
 516             }
 517 #if CLIB_DEBUG > 0
 518           else if (dst_address_byte_index)
 519             {
 520               int ii, count = 0;
 521               for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
 522                 {
 523                   count += ip4_mtrie_leaf_is_non_empty (old_ply, ii);
 524                 }
 525               ASSERT (count);
 526             }
 527 #endif
 528         }
 529     }
 530
 531   /* Old ply was not deleted. */
 532   return 0;
 533 }
 534
 535 static void
 536 unset_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
 537 {
 538   ip4_mtrie_leaf_t old_leaf, del_leaf;
 539   i32 n_dst_bits_next_plies;
 540   i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
 541   u16 dst_byte;
 542   ip4_mtrie_16_ply_t *old_ply;
 543
 544   ASSERT (a->dst_address_length <= 32);
 545
 546   old_ply = &m->root_ply;
 547   n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
 548
 549   dst_byte = a->dst_address.as_u16[0];
 550
 551   n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
 552                          (16 - a->dst_address_length) : 0);
 553
 554   del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 555
 556   /* Starting at the value of the byte at this section of the v4 address
 557    * fill the buckets/slots of the ply */
 558   for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
 559     {
 560       u16 slot;
 561
 562       slot = clib_net_to_host_u16 (dst_byte);
 563       slot += i;
 564       slot = clib_host_to_net_u16 (slot);
 565
 566       old_leaf = old_ply->leaves[slot];
 567       old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 568
 569       if (old_leaf == del_leaf ||
 570           (!old_leaf_is_terminal &&
 571            unset_leaf (a, get_next_ply_for_leaf (old_leaf), 2)))
 572         {
 573           clib_atomic_store_rel_n (
 574             &old_ply->leaves[slot],
 575             ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
 576           old_ply->dst_address_bits_of_leaves[slot] = a->cover_address_length;
 577         }
 578     }
 579 }
 580
 581 void
 582 ip4_mtrie_16_route_add (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
 583                         u32 dst_address_length, u32 adj_index)
 584 {
 585   ip4_mtrie_set_unset_leaf_args_t a;
 586   ip4_main_t *im = &ip4_main;
 587
 588   /* Honor dst_address_length. Fib masks are in network byte order */
 589   a.dst_address.as_u32 = (dst_address->as_u32 &
 590                           im->fib_masks[dst_address_length]);
 591   a.dst_address_length = dst_address_length;
 592   a.adj_index = adj_index;
 593
 594   set_root_leaf (m, &a);
 595 }
 596
 597 void
 598 ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
 599                        u32 dst_address_length, u32 adj_index)
 600 {
 601   ip4_mtrie_set_unset_leaf_args_t a;
 602   ip4_main_t *im = &ip4_main;
 603
 604   /* Honor dst_address_length. Fib masks are in network byte order */
 605   a.dst_address.as_u32 =
 606     (dst_address->as_u32 & im->fib_masks[dst_address_length]);
 607   a.dst_address_length = dst_address_length;
 608   a.adj_index = adj_index;
 609
 610   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 611
 612   set_leaf (&a, root - ip4_ply_pool, 0);
 613 }
 614
 615 void
 616 ip4_mtrie_16_route_del (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
 617                         u32 dst_address_length, u32 adj_index,
 618                         u32 cover_address_length, u32 cover_adj_index)
 619 {
 620   ip4_mtrie_set_unset_leaf_args_t a;
 621   ip4_main_t *im = &ip4_main;
 622
 623   /* Honor dst_address_length. Fib masks are in network byte order */
 624   a.dst_address.as_u32 = (dst_address->as_u32 &
 625                           im->fib_masks[dst_address_length]);
 626   a.dst_address_length = dst_address_length;
 627   a.adj_index = adj_index;
 628   a.cover_adj_index = cover_adj_index;
 629   a.cover_address_length = cover_address_length;
 630
 631   /* the top level ply is never removed */
 632   unset_root_leaf (m, &a);
 633 }
 634
 635 void
 636 ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
 637                        u32 dst_address_length, u32 adj_index,
 638                        u32 cover_address_length, u32 cover_adj_index)
 639 {
 640   ip4_main_t *im = &ip4_main;
 641
 642   /* Honor dst_address_length. Fib masks are in network byte order */
 643   ip4_mtrie_set_unset_leaf_args_t a = {
 644     .dst_address.as_u32 =
 645       (dst_address->as_u32 & im->fib_masks[dst_address_length]),
 646     .dst_address_length = dst_address_length,
 647     .adj_index = adj_index,
 648     .cover_adj_index = cover_adj_index,
 649     .cover_address_length = cover_address_length,
 650   };
 651
 652   /* the top level ply is never removed */
 653   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 654
 655   unset_leaf (&a, root, 0);
 656 }
 657
 658 /* Returns number of bytes of memory used by mtrie. */
 659 static uword
 660 mtrie_ply_memory_usage (ip4_mtrie_8_ply_t *p)
 661 {
 662   uword bytes, i;
 663
 664   bytes = sizeof (p[0]);
 665   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 666     {
 667       ip4_mtrie_leaf_t l = p->leaves[i];
 668       if (ip4_mtrie_leaf_is_next_ply (l))
 669         bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
 670     }
 671
 672   return bytes;
 673 }
 674
 675 /* Returns number of bytes of memory used by mtrie. */
 676 uword
 677 ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
 678 {
 679   uword bytes, i;
 680
 681   bytes = sizeof (*m);
 682   for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
 683     {
 684       ip4_mtrie_leaf_t l = m->root_ply.leaves[i];
 685       if (ip4_mtrie_leaf_is_next_ply (l))
 686         bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
 687     }
 688
 689   return bytes;
 690 }
 691 uword
 692 ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
 693 {
 694   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 695   uword bytes, i;
 696
 697   bytes = sizeof (*m);
 698   for (i = 0; i < ARRAY_LEN (root->leaves); i++)
 699     {
 700       ip4_mtrie_leaf_t l = root->leaves[i];
 701       if (ip4_mtrie_leaf_is_next_ply (l))
 702         bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
 703     }
 704
 705   return bytes;
 706 }
 707
 708 static u8 *
 709 format_ip4_mtrie_leaf (u8 *s, va_list *va)
 710 {
 711   ip4_mtrie_leaf_t l = va_arg (*va, ip4_mtrie_leaf_t);
 712
 713   if (ip4_mtrie_leaf_is_terminal (l))
 714     s = format (s, "lb-index %d", ip4_mtrie_leaf_get_adj_index (l));
 715   else
 716     s = format (s, "next ply %d", ip4_mtrie_leaf_get_next_ply_index (l));
 717   return s;
 718 }
 719
 720 #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent)       \
 721   ({                                                                          \
 722     u32 a, ia_length;                                                         \
 723     ip4_address_t ia;                                                         \
 724     ip4_mtrie_leaf_t _l = (_p)->leaves[(_i)];                                 \
 725                                                                               \
 726     a = (_base_address) + ((_a) << (32 - (_ply_max_len)));                    \
 727     ia.as_u32 = clib_host_to_net_u32 (a);                                     \
 728     ia_length = (_p)->dst_address_bits_of_leaves[(_i)];                       \
 729     s = format (s, "\n%U%U %U", format_white_space, (_indent) + 4,            \
 730                 format_ip4_address_and_length, &ia, ia_length,                \
 731                 format_ip4_mtrie_leaf, _l);                                   \
 732                                                                               \
 733     if (ip4_mtrie_leaf_is_next_ply (_l))                                      \
 734       s = format (s, "\n%U", format_ip4_mtrie_ply, m, a, (_indent) + 8,       \
 735                   ip4_mtrie_leaf_get_next_ply_index (_l));                    \
 736     s;                                                                        \
 737   })
 738
 739 static u8 *
 740 format_ip4_mtrie_ply (u8 *s, va_list *va)
 741 {
 742   ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
 743   u32 base_address = va_arg (*va, u32);
 744   u32 indent = va_arg (*va, u32);
 745   u32 ply_index = va_arg (*va, u32);
 746   ip4_mtrie_8_ply_t *p;
 747   int i;
 748
 749   p = pool_elt_at_index (ip4_ply_pool, ply_index);
 750   s = format (s, "%Uply index %d, %d non-empty leaves",
 751               format_white_space, indent, ply_index, p->n_non_empty_leafs);
 752
 753   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 754     {
 755       if (ip4_mtrie_leaf_is_non_empty (p, i))
 756         {
 757           s = FORMAT_PLY (s, p, i, i, base_address,
 758                           p->dst_address_bits_base + 8, indent);
 759         }
 760     }
 761
 762   return s;
 763 }
 764
 765 u8 *
 766 format_ip4_mtrie_16 (u8 *s, va_list *va)
 767 {
 768   ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
 769   int verbose = va_arg (*va, int);
 770   ip4_mtrie_16_ply_t *p;
 771   u32 base_address = 0;
 772   int i;
 773
 774   s =
 775     format (s, "16-8-8: %d plies, memory usage %U\n", pool_elts (ip4_ply_pool),
 776             format_memory_size, ip4_mtrie_16_memory_usage (m));
 777   p = &m->root_ply;
 778
 779   if (verbose)
 780     {
 781       s = format (s, "root-ply");
 782       p = &m->root_ply;
 783
 784       for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 785         {
 786           u16 slot;
 787
 788           slot = clib_host_to_net_u16 (i);
 789
 790           if (p->dst_address_bits_of_leaves[slot] > 0)
 791             {
 792               s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
 793             }
 794         }
 795     }
 796
 797   return s;
 798 }
 799
 800 u8 *
 801 format_ip4_mtrie_8 (u8 *s, va_list *va)
 802 {
 803   ip4_mtrie_8_t *m = va_arg (*va, ip4_mtrie_8_t *);
 804   int verbose = va_arg (*va, int);
 805   ip4_mtrie_8_ply_t *root;
 806   u32 base_address = 0;
 807   u16 slot;
 808
 809   root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 810
 811   s = format (s, "8-8-8-8; %d plies, memory usage %U\n",
 812               pool_elts (ip4_ply_pool), format_memory_size,
 813               ip4_mtrie_8_memory_usage (m));
 814
 815   if (verbose)
 816     {
 817       s = format (s, "root-ply");
 818
 819       for (slot = 0; slot < ARRAY_LEN (root->leaves); slot++)
 820         {
 821           if (root->dst_address_bits_of_leaves[slot] > 0)
 822             {
 823               s = FORMAT_PLY (s, root, slot, slot, base_address, 8, 0);
 824             }
 825         }
 826     }
 827
 828   return s;
 829 }
 830
 831 /** Default heap size for the IPv4 mtries */
 832 #define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE (32<<20)
 833 #ifndef MAP_HUGE_SHIFT
 834 #define MAP_HUGE_SHIFT 26
 835 #endif
 836
 837 static clib_error_t *
 838 ip4_mtrie_module_init (vlib_main_t * vm)
 839 {
 840   CLIB_UNUSED (ip4_mtrie_8_ply_t * p);
 841   clib_error_t *error = NULL;
 842
 843   /* Burn one ply so index 0 is taken */
 844   pool_get (ip4_ply_pool, p);
 845
 846   return (error);
 847 }
 848
 849 VLIB_INIT_FUNCTION (ip4_mtrie_module_init);
 850
 851 /*
 852  * fd.io coding-style-patch-verification: ON
 853  *
 854  * Local Variables:
 855  * eval: (c-set-style "gnu")
 856  * End:
 857  */