vnet/vnet/ip/ip4_mtrie.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16  * ip/ip4_fib.h: ip4 mtrie fib
  17  *
  18  * Copyright (c) 2012 Eliot Dresselhaus
  19  *
  20  * Permission is hereby granted, free of charge, to any person obtaining
  21  * a copy of this software and associated documentation files (the
  22  * "Software"), to deal in the Software without restriction, including
  23  * without limitation the rights to use, copy, modify, merge, publish,
  24  * distribute, sublicense, and/or sell copies of the Software, and to
  25  * permit persons to whom the Software is furnished to do so, subject to
  26  * the following conditions:
  27  *
  28  * The above copyright notice and this permission notice shall be
  29  * included in all copies or substantial portions of the Software.
  30  *
  31  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  32  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  33  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  34  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  35  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  36  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  37  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  38  */
  39
  40 #include <vnet/ip/ip.h>
  41 #include <vnet/fib/fib_entry.h>
  42
  43 static void
  44 ply_init (ip4_fib_mtrie_ply_t * p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
  45 {
  46   p->n_non_empty_leafs = ip4_fib_mtrie_leaf_is_empty (init) ? 0 : ARRAY_LEN (p->leaves);
  47   memset (p->dst_address_bits_of_leaves, prefix_len, sizeof (p->dst_address_bits_of_leaves));
  48
  49   /* Initialize leaves. */
  50 #ifdef CLIB_HAVE_VEC128
  51   {
  52     u32x4 * l, init_x4;
  53
  54 #ifndef __ALTIVEC__
  55     init_x4 = u32x4_splat (init);
  56 #else
  57     {
  58       u32x4_union_t y;
  59       y.as_u32[0] = init;
  60       y.as_u32[1] = init;
  61       y.as_u32[2] = init;
  62       y.as_u32[3] = init;
  63       init_x4 = y.as_u32x4;
  64     }
  65 #endif
  66
  67     for (l = p->leaves_as_u32x4; l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); l += 4)
  68       {
  69         l[0] = init_x4;
  70         l[1] = init_x4;
  71         l[2] = init_x4;
  72         l[3] = init_x4;
  73       }
  74   }
  75 #else
  76   {
  77     u32 * l;
  78
  79     for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4)
  80       {
  81         l[0] = init;
  82         l[1] = init;
  83         l[2] = init;
  84         l[3] = init;
  85       }
  86   }
  87 #endif
  88 }
  89
  90 static ip4_fib_mtrie_leaf_t
  91 ply_create (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t init_leaf, uword prefix_len)
  92 {
  93   ip4_fib_mtrie_ply_t * p;
  94
  95   /* Get cache aligned ply. */
  96   pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
  97
  98   ply_init (p, init_leaf, prefix_len);
  99   return ip4_fib_mtrie_leaf_set_next_ply_index (p - m->ply_pool);
 100 }
 101
 102 always_inline ip4_fib_mtrie_ply_t *
 103 get_next_ply_for_leaf (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t l)
 104 {
 105   uword n = ip4_fib_mtrie_leaf_get_next_ply_index (l);
 106   /* It better not be the root ply. */
 107   ASSERT (n != 0);
 108   return pool_elt_at_index (m->ply_pool, n);
 109 }
 110
 111 static void
 112 ply_free (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
 113 {
 114   uword i, is_root;
 115
 116   is_root = p - m->ply_pool == 0;
 117
 118   for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
 119     {
 120       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 121       if (ip4_fib_mtrie_leaf_is_next_ply (l))
 122         ply_free (m, get_next_ply_for_leaf (m, l));
 123     }
 124
 125   if (is_root)
 126     ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
 127   else
 128     pool_put (m->ply_pool, p);
 129 }
 130
 131 void ip4_fib_free (ip4_fib_mtrie_t * m)
 132 {
 133   ip4_fib_mtrie_ply_t * root_ply = pool_elt_at_index (m->ply_pool, 0);
 134   ply_free (m, root_ply);
 135 }
 136
 137 u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst)
 138 {
 139   ip4_fib_mtrie_ply_t * p = pool_elt_at_index (m->ply_pool, 0);
 140   ip4_fib_mtrie_leaf_t l;
 141
 142   l = p->leaves[dst.as_u8[0]];
 143   if (ip4_fib_mtrie_leaf_is_terminal (l))
 144     return ip4_fib_mtrie_leaf_get_adj_index (l);
 145
 146   p = get_next_ply_for_leaf (m, l);
 147   l = p->leaves[dst.as_u8[1]];
 148   if (ip4_fib_mtrie_leaf_is_terminal (l))
 149     return ip4_fib_mtrie_leaf_get_adj_index (l);
 150
 151   p = get_next_ply_for_leaf (m, l);
 152   l = p->leaves[dst.as_u8[2]];
 153   if (ip4_fib_mtrie_leaf_is_terminal (l))
 154     return ip4_fib_mtrie_leaf_get_adj_index (l);
 155
 156   p = get_next_ply_for_leaf (m, l);
 157   l = p->leaves[dst.as_u8[3]];
 158
 159   ASSERT (ip4_fib_mtrie_leaf_is_terminal (l));
 160   return ip4_fib_mtrie_leaf_get_adj_index (l);
 161 }
 162
 163 typedef struct {
 164   ip4_address_t dst_address;
 165   u32 dst_address_length;
 166   u32 adj_index;
 167 } ip4_fib_mtrie_set_unset_leaf_args_t;
 168
 169 static void
 170 set_ply_with_more_specific_leaf (ip4_fib_mtrie_t * m,
 171                                  ip4_fib_mtrie_ply_t * ply,
 172                                  ip4_fib_mtrie_leaf_t new_leaf,
 173                                  uword new_leaf_dst_address_bits)
 174 {
 175   ip4_fib_mtrie_leaf_t old_leaf;
 176   uword i;
 177
 178   ASSERT (ip4_fib_mtrie_leaf_is_terminal (new_leaf));
 179   ASSERT (! ip4_fib_mtrie_leaf_is_empty (new_leaf));
 180
 181   for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
 182     {
 183       old_leaf = ply->leaves[i];
 184
 185       /* Recurse into sub plies. */
 186       if (! ip4_fib_mtrie_leaf_is_terminal (old_leaf))
 187         {
 188           ip4_fib_mtrie_ply_t * sub_ply = get_next_ply_for_leaf (m, old_leaf);
 189           set_ply_with_more_specific_leaf (m, sub_ply, new_leaf, new_leaf_dst_address_bits);
 190         }
 191
 192       /* Replace less specific terminal leaves with new leaf. */
 193       else if (new_leaf_dst_address_bits >= ply->dst_address_bits_of_leaves[i])
 194         {
 195           __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
 196           ASSERT(ply->leaves[i] == new_leaf);
 197           ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
 198           ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
 199         }
 200     }
 201 }
 202
 203 static void
 204 set_leaf (ip4_fib_mtrie_t * m,
 205           ip4_fib_mtrie_set_unset_leaf_args_t * a,
 206           u32 old_ply_index,
 207           u32 dst_address_byte_index)
 208 {
 209   ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
 210   i32 n_dst_bits_next_plies;
 211   u8 dst_byte;
 212
 213   ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
 214   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 215
 216   n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 217
 218   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 219
 220   /* Number of bits next plies <= 0 => insert leaves this ply. */
 221   if (n_dst_bits_next_plies <= 0)
 222     {
 223       uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
 224
 225       n_dst_bits_this_ply = -n_dst_bits_next_plies;
 226       ASSERT ((a->dst_address.as_u8[dst_address_byte_index] & pow2_mask (n_dst_bits_this_ply)) == 0);
 227
 228       for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 229         {
 230           ip4_fib_mtrie_ply_t * old_ply, * new_ply;
 231
 232           old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 233
 234           old_leaf = old_ply->leaves[i];
 235           old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
 236
 237           /* Is leaf to be inserted more specific? */
 238           if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
 239             {
 240               new_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
 241
 242               if (old_leaf_is_terminal)
 243                 {
 244                   old_ply->dst_address_bits_of_leaves[i] = a->dst_address_length;
 245                   __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
 246                                                new_leaf);
 247                   ASSERT(old_ply->leaves[i] == new_leaf);
 248                   old_ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
 249                   ASSERT (old_ply->n_non_empty_leafs <= ARRAY_LEN (old_ply->leaves));
 250                 }
 251               else
 252                 {
 253                   /* Existing leaf points to another ply.  We need to place new_leaf into all
 254                      more specific slots. */
 255                   new_ply = get_next_ply_for_leaf (m, old_leaf);
 256                   set_ply_with_more_specific_leaf (m, new_ply, new_leaf, a->dst_address_length);
 257                 }
 258             }
 259
 260           else if (! old_leaf_is_terminal)
 261             {
 262               new_ply = get_next_ply_for_leaf (m, old_leaf);
 263               set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
 264             }
 265         }
 266     }
 267   else
 268     {
 269       ip4_fib_mtrie_ply_t * old_ply, * new_ply;
 270
 271       old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 272       old_leaf = old_ply->leaves[dst_byte];
 273       if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
 274         {
 275           new_leaf = ply_create (m, old_leaf, old_ply->dst_address_bits_of_leaves[dst_byte]);
 276           new_ply = get_next_ply_for_leaf (m, new_leaf);
 277
 278           /* Refetch since ply_create may move pool. */
 279           old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
 280
 281           __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
 282                                        new_leaf);
 283           ASSERT(old_ply->leaves[dst_byte] == new_leaf);
 284           old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
 285
 286           old_ply->n_non_empty_leafs -= ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
 287           ASSERT (old_ply->n_non_empty_leafs >= 0);
 288
 289           /* Account for the ply we just created. */
 290           old_ply->n_non_empty_leafs += 1;
 291         }
 292       else
 293         new_ply = get_next_ply_for_leaf (m, old_leaf);
 294
 295       set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
 296     }
 297 }
 298
 299 static uword
 300 unset_leaf (ip4_fib_mtrie_t * m,
 301             ip4_fib_mtrie_set_unset_leaf_args_t * a,
 302             ip4_fib_mtrie_ply_t * old_ply,
 303             u32 dst_address_byte_index)
 304 {
 305   ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
 306   i32 n_dst_bits_next_plies;
 307   i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
 308   u8 dst_byte;
 309
 310   ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
 311   ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
 312
 313   n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
 314
 315   dst_byte = a->dst_address.as_u8[dst_address_byte_index];
 316   if (n_dst_bits_next_plies < 0)
 317     dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
 318
 319   n_dst_bits_this_ply = n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
 320   n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
 321
 322   del_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
 323
 324   for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
 325     {
 326       old_leaf = old_ply->leaves[i];
 327       old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
 328
 329       if (old_leaf == del_leaf
 330           || (! old_leaf_is_terminal
 331               && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf), dst_address_byte_index + 1)))
 332         {
 333           old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
 334           old_ply->dst_address_bits_of_leaves[i] = 0;
 335
 336           /* No matter what we just deleted a non-empty leaf. */
 337           ASSERT (! ip4_fib_mtrie_leaf_is_empty (old_leaf));
 338           old_ply->n_non_empty_leafs -= 1;
 339
 340           ASSERT (old_ply->n_non_empty_leafs >= 0);
 341           if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
 342             {
 343               pool_put (m->ply_pool, old_ply);
 344               /* Old ply was deleted. */
 345               return 1;
 346             }
 347         }
 348     }
 349
 350   /* Old ply was not deleted. */
 351   return 0;
 352 }
 353
 354 void ip4_mtrie_init (ip4_fib_mtrie_t * m)
 355 {
 356   ip4_fib_mtrie_leaf_t root;
 357   memset (m, 0, sizeof (m[0]));
 358   m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
 359   root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */ 0);
 360   ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (root) == 0);
 361 }
 362
 363 void
 364 ip4_fib_mtrie_add_del_route (ip4_fib_t * fib,
 365                              ip4_address_t dst_address,
 366                              u32 dst_address_length,
 367                              u32 adj_index,
 368                              u32 is_del)
 369 {
 370   ip4_fib_mtrie_t * m = &fib->mtrie;
 371   ip4_fib_mtrie_ply_t * root_ply;
 372   ip4_fib_mtrie_set_unset_leaf_args_t a;
 373   ip4_main_t * im = &ip4_main;
 374
 375   ASSERT(m->ply_pool != 0);
 376
 377   root_ply = pool_elt_at_index (m->ply_pool, 0);
 378
 379   /* Honor dst_address_length. Fib masks are in network byte order */
 380   dst_address.as_u32 &= im->fib_masks[dst_address_length];
 381   a.dst_address = dst_address;
 382   a.dst_address_length = dst_address_length;
 383   a.adj_index = adj_index;
 384
 385   if (! is_del)
 386     {
 387       if (dst_address_length == 0)
 388         m->default_leaf = ip4_fib_mtrie_leaf_set_adj_index (adj_index);
 389       else
 390         set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
 391     }
 392   else
 393     {
 394       if (dst_address_length == 0)
 395         m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
 396
 397       else
 398         {
 399           ip4_main_t * im = &ip4_main;
 400           uword i;
 401
 402           unset_leaf (m, &a, root_ply, 0);
 403
 404           /* Find next less specific route and insert into mtrie. */
 405           for (i = dst_address_length - 1; i >= 1; i--)
 406             {
 407               uword * p;
 408               index_t lbi;
 409               ip4_address_t key;
 410
 411               if (! fib->fib_entry_by_dst_address[i])
 412                 continue;
 413
 414               key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
 415               p = hash_get (fib->fib_entry_by_dst_address[i], key.as_u32);
 416               if (p)
 417                 {
 418                   lbi = fib_entry_contribute_ip_forwarding(p[0])->dpoi_index;
 419                   if (INDEX_INVALID == lbi)
 420                     continue;
 421
 422                   a.dst_address = key;
 423                   a.adj_index = lbi;
 424                   a.dst_address_length = i;
 425
 426                   set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
 427                   break;
 428                 }
 429             }
 430         }
 431     }
 432 }
 433
 434 /* Returns number of bytes of memory used by mtrie. */
 435 static uword mtrie_memory_usage (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
 436 {
 437   uword bytes, i;
 438
 439   if (! p)
 440     {
 441       if (pool_is_free_index (m->ply_pool, 0))
 442         return 0;
 443       p = pool_elt_at_index (m->ply_pool, 0);
 444     }
 445
 446   bytes = sizeof (p[0]);
 447   for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
 448     {
 449       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 450       if (ip4_fib_mtrie_leaf_is_next_ply (l))
 451         bytes += mtrie_memory_usage (m, get_next_ply_for_leaf (m, l));
 452     }
 453
 454   return bytes;
 455 }
 456
 457 static u8 * format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
 458 {
 459   ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
 460
 461   if (ip4_fib_mtrie_leaf_is_empty (l))
 462     s = format (s, "miss");
 463   else if (ip4_fib_mtrie_leaf_is_terminal (l))
 464     s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
 465   else
 466     s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
 467   return s;
 468 }
 469
 470 static u8 * format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
 471 {
 472   ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
 473   u32 base_address = va_arg (*va, u32);
 474   u32 ply_index = va_arg (*va, u32);
 475   u32 dst_address_byte_index = va_arg (*va, u32);
 476   ip4_fib_mtrie_ply_t * p;
 477   uword i, indent;
 478
 479   p = pool_elt_at_index (m->ply_pool, ply_index);
 480   indent = format_get_indent (s);
 481   s = format (s, "ply index %d, %d non-empty leaves", ply_index, p->n_non_empty_leafs);
 482   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
 483     {
 484       ip4_fib_mtrie_leaf_t l = p->leaves[i];
 485
 486       if (! ip4_fib_mtrie_leaf_is_empty (l))
 487         {
 488           u32 a, ia_length;
 489           ip4_address_t ia;
 490
 491           a = base_address + (i << (24 - 8*dst_address_byte_index));
 492           ia.as_u32 = clib_host_to_net_u32 (a);
 493           if (ip4_fib_mtrie_leaf_is_terminal (l))
 494             ia_length = p->dst_address_bits_of_leaves[i];
 495           else
 496             ia_length = 8*(1 + dst_address_byte_index);
 497           s = format (s, "\n%U%20U %U",
 498                       format_white_space, indent + 2,
 499                       format_ip4_address_and_length, &ia, ia_length,
 500                       format_ip4_fib_mtrie_leaf, l);
 501
 502           if (ip4_fib_mtrie_leaf_is_next_ply (l))
 503             s = format (s, "\n%U%U",
 504                         format_white_space, indent + 2,
 505                         format_ip4_fib_mtrie_ply, m, a,
 506                         ip4_fib_mtrie_leaf_get_next_ply_index (l),
 507                         dst_address_byte_index + 1);
 508         }
 509     }
 510
 511   return s;
 512 }
 513
 514 u8 * format_ip4_fib_mtrie (u8 * s, va_list * va)
 515 {
 516   ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
 517
 518   s = format (s, "%d plies, memory usage %U",
 519               pool_elts (m->ply_pool),
 520               format_memory_size, mtrie_memory_usage (m, 0));
 521
 522   if (pool_elts (m->ply_pool) > 0)
 523     {
 524       ip4_address_t base_address;
 525       base_address.as_u32 = 0;
 526       s = format (s, "\n  %U", format_ip4_fib_mtrie_ply, m, base_address, 0, 0);
 527     }
 528
 529   return s;
 530 }