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