src/vnet/fib/mpls_fib.c

   1 /*
   2  * mpls_fib.h: The Label/MPLS FIB
   3  *
   4  * Copyright (c) 2012 Cisco and/or its affiliates.
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at:
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17 /**
  18  * An MPLS_FIB table;
  19  *
  20  * The entries in the table are programmed wtih one or more MOIs. These MOIs
  21  * may result in different forwarding actions for end-of-stack (EOS) and non-EOS
  22  * packets. Whether the two actions are the same more often than they are
  23  * different, or vice versa, is a function of the deployment in which the router
  24  * is used and thus not predictable.
  25  * The design choice to make with an MPLS_FIB table is:
  26  *  1 - 20 bit key: label only.
  27  *      When the EOS and non-EOS actions differ the result is a 'EOS-choice' object.
  28  *  2 - 21 bit key: label and EOS-bit.
  29  *      The result is then the specific action based on EOS-bit.
  30  *
  31  * 20 bit key:
  32  *   Advantages:
  33  *    - lower memory overhead, since there are few DB entries.
  34  *   Disadvantages:
  35  *    - slower DP performance in the case the chains differ, as more objects are
  36  *      encountered in the switch path
  37  *
  38  * 21 bit key:
  39  *   Advantages:
  40  *    - faster DP performance
  41  *   Disadvantages
  42  *    - increased memory footprint.
  43  *
  44  * Switching between schemes based on observed/measured action similarity is not
  45  * considered on the grounds of complexity and flip-flopping.
  46  *
  47  * VPP mantra - favour performance over memory. We choose a 21 bit key.
  48  */
  49
  50 #include <vnet/fib/fib_table.h>
  51 #include <vnet/fib/mpls_fib.h>
  52 #include <vnet/dpo/load_balance.h>
  53 #include <vnet/dpo/drop_dpo.h>
  54 #include <vnet/dpo/punt_dpo.h>
  55 #include <vnet/dpo/lookup_dpo.h>
  56 #include <vnet/mpls/mpls.h>
  57
  58 /**
  59  * All lookups in an MPLS_FIB table must result in a DPO of type load-balance.
  60  * This is the default result which links to drop
  61  */
  62 static index_t mpls_fib_drop_dpo_index = INDEX_INVALID;
  63
  64 static inline u32
  65 mpls_fib_entry_mk_key (mpls_label_t label,
  66                        mpls_eos_bit_t eos)
  67 {
  68     ASSERT(eos <= 1);
  69     return (label << 1 | eos);
  70 }
  71
  72 u32
  73 mpls_fib_index_from_table_id (u32 table_id)
  74 {
  75     mpls_main_t *mm = &mpls_main;
  76     uword * p;
  77
  78     p = hash_get (mm->fib_index_by_table_id, table_id);
  79     if (!p)
  80         return FIB_NODE_INDEX_INVALID;
  81
  82     return p[0];
  83 }
  84
  85 static u32
  86 mpls_fib_create_with_table_id (u32 table_id,
  87                                fib_source_t src)
  88 {
  89     dpo_id_t dpo = DPO_INVALID;
  90     fib_table_t *fib_table;
  91     mpls_eos_bit_t eos;
  92     mpls_fib_t *mf;
  93     int i;
  94
  95     pool_get(mpls_main.fibs, fib_table);
  96     pool_get_aligned(mpls_main.mpls_fibs, mf, CLIB_CACHE_LINE_BYTES);
  97
  98     ASSERT((fib_table - mpls_main.fibs) ==
  99            (mf - mpls_main.mpls_fibs));
 100
 101     clib_memset(fib_table, 0, sizeof(*fib_table));
 102
 103     fib_table->ft_proto = FIB_PROTOCOL_MPLS;
 104     fib_table->ft_index = (fib_table - mpls_main.fibs);
 105
 106     hash_set (mpls_main.fib_index_by_table_id, table_id, fib_table->ft_index);
 107
 108     fib_table->ft_table_id = table_id;
 109     fib_table->ft_flow_hash_config = MPLS_FLOW_HASH_DEFAULT;
 110
 111     fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_MPLS, src);
 112
 113     if (INDEX_INVALID == mpls_fib_drop_dpo_index)
 114     {
 115         mpls_fib_drop_dpo_index = load_balance_create(1, DPO_PROTO_MPLS, 0);
 116         load_balance_set_bucket(mpls_fib_drop_dpo_index,
 117                                 0,
 118                                 drop_dpo_get(DPO_PROTO_MPLS));
 119     }
 120
 121     mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
 122     for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
 123     {
 124         /*
 125          * initialise each DPO in the data-path lookup table
 126          * to be the special MPLS drop
 127          */
 128         mf->mf_lbs[i] = mpls_fib_drop_dpo_index;
 129     }
 130
 131     /*
 132      * non-default forwarding for the special labels.
 133      */
 134     fib_prefix_t prefix = {
 135         .fp_proto = FIB_PROTOCOL_MPLS,
 136         .fp_payload_proto = DPO_PROTO_MPLS,
 137     };
 138
 139     /*
 140      * PUNT the router alert, both EOS and non-eos
 141      */
 142     prefix.fp_label = MPLS_IETF_ROUTER_ALERT_LABEL;
 143     FOR_EACH_MPLS_EOS_BIT(eos)
 144     {
 145         prefix.fp_eos = eos;
 146         fib_table_entry_special_dpo_add(fib_table->ft_index,
 147                                         &prefix,
 148                                         FIB_SOURCE_SPECIAL,
 149                                         FIB_ENTRY_FLAG_EXCLUSIVE,
 150                                         punt_dpo_get(DPO_PROTO_MPLS));
 151     }
 152
 153     /*
 154      * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
 155      */
 156     prefix.fp_label = MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL;
 157     prefix.fp_payload_proto = DPO_PROTO_IP4;
 158     prefix.fp_eos = MPLS_EOS;
 159
 160     lookup_dpo_add_or_lock_w_fib_index(0, // unused
 161                                        DPO_PROTO_IP4,
 162                                        LOOKUP_UNICAST,
 163                                        LOOKUP_INPUT_DST_ADDR,
 164                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 165                                        &dpo);
 166     fib_table_entry_special_dpo_add(fib_table->ft_index,
 167                                     &prefix,
 168                                     FIB_SOURCE_SPECIAL,
 169                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 170                                     &dpo);
 171
 172     prefix.fp_payload_proto = DPO_PROTO_MPLS;
 173     prefix.fp_eos = MPLS_NON_EOS;
 174
 175     lookup_dpo_add_or_lock_w_fib_index(0, //unsued
 176                                        DPO_PROTO_MPLS,
 177                                        LOOKUP_UNICAST,
 178                                        LOOKUP_INPUT_DST_ADDR,
 179                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 180                                        &dpo);
 181     fib_table_entry_special_dpo_add(fib_table->ft_index,
 182                                     &prefix,
 183                                     FIB_SOURCE_SPECIAL,
 184                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 185                                     &dpo);
 186
 187     /*
 188      * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
 189      */
 190     prefix.fp_label = MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL;
 191     prefix.fp_payload_proto = DPO_PROTO_IP6;
 192     prefix.fp_eos = MPLS_EOS;
 193
 194     lookup_dpo_add_or_lock_w_fib_index(0, //unused
 195                                        DPO_PROTO_IP6,
 196                                        LOOKUP_UNICAST,
 197                                        LOOKUP_INPUT_DST_ADDR,
 198                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 199                                        &dpo);
 200     fib_table_entry_special_dpo_add(fib_table->ft_index,
 201                                     &prefix,
 202                                     FIB_SOURCE_SPECIAL,
 203                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 204                                     &dpo);
 205
 206     prefix.fp_payload_proto = DPO_PROTO_MPLS;
 207     prefix.fp_eos = MPLS_NON_EOS;
 208     lookup_dpo_add_or_lock_w_fib_index(0, // unsued
 209                                        DPO_PROTO_MPLS,
 210                                        LOOKUP_UNICAST,
 211                                        LOOKUP_INPUT_DST_ADDR,
 212                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 213                                        &dpo);
 214     fib_table_entry_special_dpo_add(fib_table->ft_index,
 215                                     &prefix,
 216                                     FIB_SOURCE_SPECIAL,
 217                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 218                                     &dpo);
 219
 220     return (fib_table->ft_index);
 221 }
 222
 223 u32
 224 mpls_fib_table_find_or_create_and_lock (u32 table_id,
 225                                         fib_source_t src)
 226 {
 227     u32 index;
 228
 229     index = mpls_fib_index_from_table_id(table_id);
 230     if (~0 == index)
 231         return mpls_fib_create_with_table_id(table_id, src);
 232
 233     fib_table_lock(index, FIB_PROTOCOL_MPLS, src);
 234
 235     return (index);
 236 }
 237 u32
 238 mpls_fib_table_create_and_lock (fib_source_t src)
 239 {
 240     return (mpls_fib_create_with_table_id(~0, src));
 241 }
 242
 243 void
 244 mpls_fib_table_destroy (u32 fib_index)
 245 {
 246     fib_table_t *fib_table = pool_elt_at_index(mpls_main.fibs, fib_index);
 247     mpls_fib_t *mf = pool_elt_at_index(mpls_main.mpls_fibs, fib_index);
 248     fib_prefix_t prefix = {
 249         .fp_proto = FIB_PROTOCOL_MPLS,
 250     };
 251     mpls_label_t special_labels[] = {
 252         MPLS_IETF_ROUTER_ALERT_LABEL,
 253         MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL,
 254         MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL,
 255     };
 256     mpls_eos_bit_t eos;
 257     u32 ii;
 258
 259     for (ii = 0; ii < ARRAY_LEN(special_labels); ii++)
 260     {
 261         FOR_EACH_MPLS_EOS_BIT(eos)
 262         {
 263             prefix.fp_label = special_labels[ii];
 264             prefix.fp_eos   = eos;
 265
 266             fib_table_entry_delete(fib_table->ft_index,
 267                                    &prefix,
 268                                    FIB_SOURCE_SPECIAL);
 269         }
 270     }
 271     if (~0 != fib_table->ft_table_id)
 272     {
 273         hash_unset(mpls_main.fib_index_by_table_id,
 274                    fib_table->ft_table_id);
 275     }
 276     hash_free(mf->mf_entries);
 277
 278     vec_free(fib_table->ft_src_route_counts);
 279     pool_put(mpls_main.mpls_fibs, mf);
 280     pool_put(mpls_main.fibs, fib_table);
 281 }
 282
 283 fib_node_index_t
 284 mpls_fib_table_lookup (const mpls_fib_t *mf,
 285                        mpls_label_t label,
 286                        mpls_eos_bit_t eos)
 287 {
 288     uword *p;
 289
 290     p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
 291
 292     if (NULL == p)
 293         return FIB_NODE_INDEX_INVALID;
 294
 295     return p[0];
 296 }
 297
 298 void
 299 mpls_fib_table_entry_insert (mpls_fib_t *mf,
 300                              mpls_label_t label,
 301                              mpls_eos_bit_t eos,
 302                              fib_node_index_t lfei)
 303 {
 304     hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
 305 }
 306
 307 void
 308 mpls_fib_table_entry_remove (mpls_fib_t *mf,
 309                              mpls_label_t label,
 310                              mpls_eos_bit_t eos)
 311 {
 312     hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
 313 }
 314
 315 void
 316 mpls_fib_forwarding_table_update (mpls_fib_t *mf,
 317                                   mpls_label_t label,
 318                                   mpls_eos_bit_t eos,
 319                                   const dpo_id_t *dpo)
 320 {
 321     mpls_label_t key;
 322
 323     ASSERT((DPO_LOAD_BALANCE == dpo->dpoi_type) ||
 324            (DPO_REPLICATE == dpo->dpoi_type));
 325     if (CLIB_DEBUG > 0)
 326     {
 327         if (DPO_REPLICATE == dpo->dpoi_type)
 328             ASSERT(dpo->dpoi_index & MPLS_IS_REPLICATE);
 329         if (DPO_LOAD_BALANCE == dpo->dpoi_type)
 330             ASSERT(!(dpo->dpoi_index & MPLS_IS_REPLICATE));
 331     }
 332     key = mpls_fib_entry_mk_key(label, eos);
 333
 334     mf->mf_lbs[key] = dpo->dpoi_index;
 335 }
 336
 337 void
 338 mpls_fib_forwarding_table_reset (mpls_fib_t *mf,
 339                                  mpls_label_t label,
 340                                  mpls_eos_bit_t eos)
 341 {
 342     mpls_label_t key;
 343
 344     key = mpls_fib_entry_mk_key(label, eos);
 345
 346     mf->mf_lbs[key] = mpls_fib_drop_dpo_index;
 347 }
 348
 349 void
 350 mpls_fib_table_walk (mpls_fib_t *mpls_fib,
 351                      fib_table_walk_fn_t fn,
 352                      void *ctx)
 353 {
 354     fib_node_index_t lfei;
 355     mpls_label_t key;
 356
 357     hash_foreach(key, lfei, mpls_fib->mf_entries,
 358     ({
 359         fn(lfei, ctx);
 360     }));
 361 }
 362
 363 u8 *
 364 format_mpls_fib_table_memory (u8 * s, va_list * args)
 365 {
 366     u64 n_tables, mem;
 367
 368     n_tables = pool_elts(mpls_main.fibs);
 369     mem = n_tables * sizeof(mpls_fib_t);
 370     s = format(s, "%=30s %=6ld %=12ld\n", "MPLS", n_tables, mem);
 371
 372     return (s);
 373 }
 374
 375 static void
 376 mpls_fib_table_show_all (const mpls_fib_t *mpls_fib,
 377                          vlib_main_t * vm)
 378 {
 379     fib_node_index_t lfei, *lfeip, *lfeis = NULL;
 380     mpls_label_t key;
 381
 382     hash_foreach(key, lfei, mpls_fib->mf_entries,
 383     ({
 384         vec_add1(lfeis, lfei);
 385     }));
 386
 387     vec_sort_with_function(lfeis, fib_entry_cmp_for_sort);
 388
 389     vec_foreach(lfeip, lfeis)
 390     {
 391         vlib_cli_output (vm, "%U",
 392                          format_fib_entry, *lfeip,
 393                          FIB_ENTRY_FORMAT_DETAIL);
 394     }
 395     vec_free(lfeis);
 396 }
 397
 398 static void
 399 mpls_fib_table_show_one (const mpls_fib_t *mpls_fib,
 400                          mpls_label_t label,
 401                          vlib_main_t * vm)
 402 {
 403     fib_node_index_t lfei;
 404     mpls_eos_bit_t eos;
 405
 406     FOR_EACH_MPLS_EOS_BIT(eos)
 407     {
 408         lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
 409
 410         if (FIB_NODE_INDEX_INVALID != lfei)
 411         {
 412             vlib_cli_output (vm, "%U",
 413                              format_fib_entry, lfei, FIB_ENTRY_FORMAT_DETAIL);
 414         }
 415     }
 416 }
 417
 418 static clib_error_t *
 419 mpls_fib_show (vlib_main_t * vm,
 420                unformat_input_t * input,
 421                vlib_cli_command_t * cmd)
 422 {
 423     fib_table_t * fib_table;
 424     mpls_label_t label;
 425     int table_id;
 426
 427     table_id = -1;
 428     label = MPLS_LABEL_INVALID;
 429
 430     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 431     {
 432         /* if (unformat (input, "brief") || unformat (input, "summary") */
 433         /*     || unformat (input, "sum")) */
 434         /*     verbose = 0; */
 435
 436         if (unformat (input, "%d", &label))
 437             continue;
 438         else if (unformat (input, "table %d", &table_id))
 439             ;
 440         else
 441             break;
 442     }
 443
 444     pool_foreach (fib_table, mpls_main.fibs)
 445      {
 446         fib_source_t source;
 447         u8 *s = NULL;
 448
 449         if (table_id >= 0 && table_id != fib_table->ft_table_id)
 450             continue;
 451
 452         s = format (s, "%v, fib_index:%d locks:[",
 453                     fib_table->ft_desc, mpls_main.fibs - fib_table);
 454         vec_foreach_index(source, fib_table->ft_locks)
 455         {
 456             if (0 != fib_table->ft_locks[source])
 457             {
 458                 s = format(s, "%U:%d, ",
 459                            format_fib_source, source,
 460                            fib_table->ft_locks[source]);
 461             }
 462         }
 463         vlib_cli_output (vm, "%v]", s);
 464
 465         if (MPLS_LABEL_INVALID == label)
 466         {
 467             mpls_fib_table_show_all(mpls_fib_get(fib_table->ft_index), vm);
 468         }
 469         else
 470         {
 471             mpls_fib_table_show_one(mpls_fib_get(fib_table->ft_index), label, vm);
 472         }
 473     }
 474
 475     return 0;
 476 }
 477
 478 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
 479     .path = "show mpls fib",
 480     .short_help = "show mpls fib [summary] [table <n>]",
 481     .function = mpls_fib_show,
 482 };