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   ip4_mtrie_leaf_t l;
 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);
 122
 123   if (need_barrier_sync)
 124     vlib_worker_thread_barrier_sync (vm);
 125
 126   /* Get cache aligned ply. */
 127   pool_get_aligned (ip4_ply_pool, p, CLIB_CACHE_LINE_BYTES);
 128
 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);
 131
 132   if (need_barrier_sync)
 133     vlib_worker_thread_barrier_release (vm);
 134
 135   return l;
 136 }
 137
 138 always_inline ip4_mtrie_8_ply_t *
 139 get_next_ply_for_leaf (ip4_mtrie_leaf_t l)
 140 {
 141   uword n = ip4_mtrie_leaf_get_next_ply_index (l);
 142
 143   return pool_elt_at_index (ip4_ply_pool, n);
 144 }
 145
 146 void
 147 ip4_mtrie_16_free (ip4_mtrie_16_t *m)
 148 {
 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
 151    * before deletion.
 152    */
 153 #if CLIB_DEBUG > 0
 154   int i;
 155   for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
 156     {
 157       ASSERT (!ip4_mtrie_leaf_is_next_ply (m->root_ply.leaves[i]));
 158     }
 159 #endif
 160 }
 161
 162 void
 163 ip4_mtrie_16_init (ip4_mtrie_16_t *m)
 164 {
 165   ply_16_init (&m->root_ply, IP4_MTRIE_LEAF_EMPTY, 0);
 166 }
 167
 168 void
 169 ip4_mtrie_8_free (ip4_mtrie_8_t *m)
 170 {
 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
 173    * before deletion.
 174    */
 175   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 176
 177 #if CLIB_DEBUG > 0
 178   int i;
 179   for (i = 0; i < ARRAY_LEN (root->leaves); i++)
 180     {
 181       ASSERT (!ip4_mtrie_leaf_is_next_ply (root->leaves[i]));
 182     }
 183 #endif
 184
 185   pool_put (ip4_ply_pool, root);
 186 }
 187
 188 void
 189 ip4_mtrie_8_init (ip4_mtrie_8_t *m)
 190 {
 191   ip4_mtrie_8_ply_t *root;
 192
 193   pool_get (ip4_ply_pool, root);
 194   m->root_ply = root - ip4_ply_pool;
 195
 196   ply_8_init (root, IP4_MTRIE_LEAF_EMPTY, 0, 0);
 197 }
 198
 199 typedef struct
 200 {
 201   ip4_address_t dst_address;
 202   u32 dst_address_length;
 203   u32 adj_index;
 204   u32 cover_address_length;
 205   u32 cover_adj_index;
 206 } ip4_mtrie_set_unset_leaf_args_t;
 207
 208 static void
 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)
 212 {
 213   ip4_mtrie_leaf_t old_leaf;
 214   uword i;
 215
 216   ASSERT (ip4_mtrie_leaf_is_terminal (new_leaf));
 217
 218   for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
 219     {
 220       old_leaf = ply->leaves[i];
 221
 222       /* Recurse into sub plies. */
 223       if (!ip4_mtrie_leaf_is_terminal (old_leaf))
 224         {
 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);
 228         }
 229
 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])
 233         {
 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);
 237         }
 238     }
 239 }
 240
 241 static void
 242 set_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index,
 243           u32 dst_address_byte_index)
 244 {
 245   ip4_mtrie_leaf_t old_leaf, new_leaf;
 246   i32 n_dst_bits_next_plies;
 247   u8 dst_byte;
 248   ip4_mtrie_8_ply_t *old_ply;
 249
 250   old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
 251
 252   ASSERT (a->dst_address_length <= 32);
 253   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 254
 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);
 258
 259   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 260
 261   /* Number of bits next plies <= 0 => insert leaves this ply. */
 262   if (n_dst_bits_next_plies <= 0)
 263     {
 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;
 267
 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);
 272
 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++)
 276         {
 277           ip4_mtrie_8_ply_t *new_ply;
 278
 279           old_leaf = old_ply->leaves[i];
 280           old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 281
 282           if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
 283             {
 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);
 287
 288               if (old_leaf_is_terminal)
 289                 {
 290                   /* The current leaf is terminal, we can replace it with
 291                    * the new one */
 292                   old_ply->n_non_empty_leafs -=
 293                     ip4_mtrie_leaf_is_non_empty (old_ply, i);
 294
 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);
 298
 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));
 303                 }
 304               else
 305                 {
 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);
 311                 }
 312             }
 313           else if (!old_leaf_is_terminal)
 314             {
 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);
 319             }
 320           /*
 321            * else
 322            *  the route we are adding is less specific than the leaf currently
 323            *  occupying this slot. leave it there
 324            */
 325         }
 326     }
 327   else
 328     {
 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;
 332       u8 ply_base_len;
 333
 334       ply_base_len = 8 * (dst_address_byte_index + 1);
 335
 336       old_leaf = old_ply->leaves[dst_byte];
 337
 338       if (ip4_mtrie_leaf_is_terminal (old_leaf))
 339         {
 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);
 343
 344           new_leaf = ply_create (old_leaf,
 345                                  old_ply->dst_address_bits_of_leaves[dst_byte],
 346                                  ply_base_len);
 347           new_ply = get_next_ply_for_leaf (new_leaf);
 348
 349           /* Refetch since ply_create may move pool. */
 350           old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
 351
 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;
 354
 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);
 358         }
 359       else
 360         new_ply = get_next_ply_for_leaf (old_leaf);
 361
 362       set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
 363     }
 364 }
 365
 366 static void
 367 set_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
 368 {
 369   ip4_mtrie_leaf_t old_leaf, new_leaf;
 370   ip4_mtrie_16_ply_t *old_ply;
 371   i32 n_dst_bits_next_plies;
 372   u16 dst_byte;
 373
 374   old_ply = &m->root_ply;
 375
 376   ASSERT (a->dst_address_length <= 32);
 377
 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);
 380
 381   dst_byte = a->dst_address.as_u16[0];
 382
 383   /* Number of bits next plies <= 0 => insert leaves this ply. */
 384   if (n_dst_bits_next_plies <= 0)
 385     {
 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;
 389
 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);
 394
 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++)
 398         {
 399           ip4_mtrie_8_ply_t *new_ply;
 400           u16 slot;
 401
 402           slot = clib_net_to_host_u16 (dst_byte);
 403           slot += i;
 404           slot = clib_host_to_net_u16 (slot);
 405
 406           old_leaf = old_ply->leaves[slot];
 407           old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 408
 409           if (a->dst_address_length >=
 410               old_ply->dst_address_bits_of_leaves[slot])
 411             {
 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);
 415
 416               if (old_leaf_is_terminal)
 417                 {
 418                   /* The current leaf is terminal, we can replace it with
 419                    * the new one */
 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);
 423                 }
 424               else
 425                 {
 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);
 431                 }
 432             }
 433           else if (!old_leaf_is_terminal)
 434             {
 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);
 439             }
 440           /*
 441            * else
 442            *  the route we are adding is less specific than the leaf currently
 443            *  occupying this slot. leave it there
 444            */
 445         }
 446     }
 447   else
 448     {
 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;
 452       u8 ply_base_len;
 453
 454       ply_base_len = 16;
 455
 456       old_leaf = old_ply->leaves[dst_byte];
 457
 458       if (ip4_mtrie_leaf_is_terminal (old_leaf))
 459         {
 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],
 463                                  ply_base_len);
 464           new_ply = get_next_ply_for_leaf (new_leaf);
 465
 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;
 468         }
 469       else
 470         new_ply = get_next_ply_for_leaf (old_leaf);
 471
 472       set_leaf (a, new_ply - ip4_ply_pool, 2);
 473     }
 474 }
 475
 476 static uword
 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)
 479 {
 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;
 483   u8 dst_byte;
 484
 485   ASSERT (a->dst_address_length <= 32);
 486   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 487
 488   n_dst_bits_next_plies =
 489     a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 490
 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);
 494
 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);
 498
 499   del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 500
 501   for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 502     {
 503       old_leaf = old_ply->leaves[i];
 504       old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 505
 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)))
 510         {
 511           old_ply->n_non_empty_leafs -=
 512             ip4_mtrie_leaf_is_non_empty (old_ply, i);
 513
 514           clib_atomic_store_rel_n (
 515             &old_ply->leaves[i],
 516             ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
 517           old_ply->dst_address_bits_of_leaves[i] = a->cover_address_length;
 518
 519           old_ply->n_non_empty_leafs +=
 520             ip4_mtrie_leaf_is_non_empty (old_ply, i);
 521
 522           ASSERT (old_ply->n_non_empty_leafs >= 0);
 523           if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
 524             {
 525               pool_put (ip4_ply_pool, old_ply);
 526               /* Old ply was deleted. */
 527               return 1;
 528             }
 529 #if CLIB_DEBUG > 0
 530           else if (dst_address_byte_index)
 531             {
 532               int ii, count = 0;
 533               for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
 534                 {
 535                   count += ip4_mtrie_leaf_is_non_empty (old_ply, ii);
 536                 }
 537               ASSERT (count);
 538             }
 539 #endif
 540         }
 541     }
 542
 543   /* Old ply was not deleted. */
 544   return 0;
 545 }
 546
 547 static void
 548 unset_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
 549 {
 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;
 553   u16 dst_byte;
 554   ip4_mtrie_16_ply_t *old_ply;
 555
 556   ASSERT (a->dst_address_length <= 32);
 557
 558   old_ply = &m->root_ply;
 559   n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
 560
 561   dst_byte = a->dst_address.as_u16[0];
 562
 563   n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
 564                          (16 - a->dst_address_length) : 0);
 565
 566   del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
 567
 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++)
 571     {
 572       u16 slot;
 573
 574       slot = clib_net_to_host_u16 (dst_byte);
 575       slot += i;
 576       slot = clib_host_to_net_u16 (slot);
 577
 578       old_leaf = old_ply->leaves[slot];
 579       old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
 580
 581       if (old_leaf == del_leaf ||
 582           (!old_leaf_is_terminal &&
 583            unset_leaf (a, get_next_ply_for_leaf (old_leaf), 2)))
 584         {
 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;
 589         }
 590     }
 591 }
 592
 593 void
 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)
 596 {
 597   ip4_mtrie_set_unset_leaf_args_t a;
 598   ip4_main_t *im = &ip4_main;
 599
 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;
 605
 606   set_root_leaf (m, &a);
 607 }
 608
 609 void
 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)
 612 {
 613   ip4_mtrie_set_unset_leaf_args_t a;
 614   ip4_main_t *im = &ip4_main;
 615
 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;
 621
 622   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 623
 624   set_leaf (&a, root - ip4_ply_pool, 0);
 625 }
 626
 627 void
 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)
 631 {
 632   ip4_mtrie_set_unset_leaf_args_t a;
 633   ip4_main_t *im = &ip4_main;
 634
 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;
 642
 643   /* the top level ply is never removed */
 644   unset_root_leaf (m, &a);
 645 }
 646
 647 void
 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)
 651 {
 652   ip4_main_t *im = &ip4_main;
 653
 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,
 662   };
 663
 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);
 666
 667   unset_leaf (&a, root, 0);
 668 }
 669
 670 /* Returns number of bytes of memory used by mtrie. */
 671 static uword
 672 mtrie_ply_memory_usage (ip4_mtrie_8_ply_t *p)
 673 {
 674   uword bytes, i;
 675
 676   bytes = sizeof (p[0]);
 677   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 678     {
 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));
 682     }
 683
 684   return bytes;
 685 }
 686
 687 /* Returns number of bytes of memory used by mtrie. */
 688 uword
 689 ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
 690 {
 691   uword bytes, i;
 692
 693   bytes = sizeof (*m);
 694   for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
 695     {
 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));
 699     }
 700
 701   return bytes;
 702 }
 703 uword
 704 ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
 705 {
 706   ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 707   uword bytes, i;
 708
 709   bytes = sizeof (*m);
 710   for (i = 0; i < ARRAY_LEN (root->leaves); i++)
 711     {
 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));
 715     }
 716
 717   return bytes;
 718 }
 719
 720 static u8 *
 721 format_ip4_mtrie_leaf (u8 *s, va_list *va)
 722 {
 723   ip4_mtrie_leaf_t l = va_arg (*va, ip4_mtrie_leaf_t);
 724
 725   if (ip4_mtrie_leaf_is_terminal (l))
 726     s = format (s, "lb-index %d", ip4_mtrie_leaf_get_adj_index (l));
 727   else
 728     s = format (s, "next ply %d", ip4_mtrie_leaf_get_next_ply_index (l));
 729   return s;
 730 }
 731
 732 #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent)       \
 733   ({                                                                          \
 734     u32 a, ia_length;                                                         \
 735     ip4_address_t ia;                                                         \
 736     ip4_mtrie_leaf_t _l = (_p)->leaves[(_i)];                                 \
 737                                                                               \
 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);                                   \
 744                                                                               \
 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));                    \
 748     s;                                                                        \
 749   })
 750
 751 static u8 *
 752 format_ip4_mtrie_ply (u8 *s, va_list *va)
 753 {
 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;
 759   int i;
 760
 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);
 764
 765   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 766     {
 767       if (ip4_mtrie_leaf_is_non_empty (p, i))
 768         {
 769           s = FORMAT_PLY (s, p, i, i, base_address,
 770                           p->dst_address_bits_base + 8, indent);
 771         }
 772     }
 773
 774   return s;
 775 }
 776
 777 u8 *
 778 format_ip4_mtrie_16 (u8 *s, va_list *va)
 779 {
 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;
 784   int i;
 785
 786   s =
 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));
 789   p = &m->root_ply;
 790
 791   if (verbose)
 792     {
 793       s = format (s, "root-ply");
 794       p = &m->root_ply;
 795
 796       for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 797         {
 798           u16 slot;
 799
 800           slot = clib_host_to_net_u16 (i);
 801
 802           if (p->dst_address_bits_of_leaves[slot] > 0)
 803             {
 804               s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
 805             }
 806         }
 807     }
 808
 809   return s;
 810 }
 811
 812 u8 *
 813 format_ip4_mtrie_8 (u8 *s, va_list *va)
 814 {
 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;
 819   u16 slot;
 820
 821   root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
 822
 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));
 826
 827   if (verbose)
 828     {
 829       s = format (s, "root-ply");
 830
 831       for (slot = 0; slot < ARRAY_LEN (root->leaves); slot++)
 832         {
 833           if (root->dst_address_bits_of_leaves[slot] > 0)
 834             {
 835               s = FORMAT_PLY (s, root, slot, slot, base_address, 8, 0);
 836             }
 837         }
 838     }
 839
 840   return s;
 841 }
 842
 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
 847 #endif
 848
 849 static clib_error_t *
 850 ip4_mtrie_module_init (vlib_main_t * vm)
 851 {
 852   CLIB_UNUSED (ip4_mtrie_8_ply_t * p);
 853   clib_error_t *error = NULL;
 854
 855   /* Burn one ply so index 0 is taken */
 856   pool_get (ip4_ply_pool, p);
 857
 858   return (error);
 859 }
 860
 861 VLIB_INIT_FUNCTION (ip4_mtrie_module_init);
 862
 863 /*
 864  * fd.io coding-style-patch-verification: ON
 865  *
 866  * Local Variables:
 867  * eval: (c-set-style "gnu")
 868  * End:
 869  */