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 desgin 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  *      encounterd 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 /**
  65  * FIXME
  66  */
  67 #define MPLS_FLOW_HASH_DEFAULT 0
  68
  69 static inline u32
  70 mpls_fib_entry_mk_key (mpls_label_t label,
  71                        mpls_eos_bit_t eos)
  72 {
  73     ASSERT(eos <= 1);
  74     return (label << 1 | eos);
  75 }
  76
  77 u32
  78 mpls_fib_index_from_table_id (u32 table_id)
  79 {
  80     mpls_main_t *mm = &mpls_main;
  81     uword * p;
  82
  83     p = hash_get (mm->fib_index_by_table_id, table_id);
  84     if (!p)
  85         return FIB_NODE_INDEX_INVALID;
  86
  87     return p[0];
  88 }
  89
  90 static u32
  91 mpls_fib_create_with_table_id (u32 table_id)
  92 {
  93     dpo_id_t dpo = DPO_INVALID;
  94     fib_table_t *fib_table;
  95     mpls_eos_bit_t eos;
  96     mpls_fib_t *mf;
  97     int i;
  98
  99     pool_get_aligned(mpls_main.fibs, fib_table, CLIB_CACHE_LINE_BYTES);
 100     pool_get_aligned(mpls_main.mpls_fibs, mf, CLIB_CACHE_LINE_BYTES);
 101
 102     ASSERT((fib_table - mpls_main.fibs) ==
 103            (mf - mpls_main.mpls_fibs));
 104
 105     memset(fib_table, 0, sizeof(*fib_table));
 106
 107     fib_table->ft_proto = FIB_PROTOCOL_MPLS;
 108     fib_table->ft_index = (fib_table - mpls_main.fibs);
 109
 110     hash_set (mpls_main.fib_index_by_table_id, table_id, fib_table->ft_index);
 111
 112     fib_table->ft_table_id =
 113         table_id;
 114     fib_table->ft_flow_hash_config =
 115         MPLS_FLOW_HASH_DEFAULT;
 116
 117     fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_MPLS);
 118
 119     if (INDEX_INVALID == mpls_fib_drop_dpo_index)
 120     {
 121         mpls_fib_drop_dpo_index = load_balance_create(1, DPO_PROTO_MPLS, 0);
 122         load_balance_set_bucket(mpls_fib_drop_dpo_index,
 123                                 0,
 124                                 drop_dpo_get(DPO_PROTO_MPLS));
 125     }
 126
 127     mf->mf_entries = hash_create(0, sizeof(fib_node_index_t));
 128     for (i = 0; i < MPLS_FIB_DB_SIZE; i++)
 129     {
 130         /*
 131          * initialise each DPO in the data-path lookup table
 132          * to be the special MPLS drop
 133          */
 134         mf->mf_lbs[i] = mpls_fib_drop_dpo_index;
 135     }
 136
 137     /*
 138      * non-default forwarding for the special labels.
 139      */
 140     fib_prefix_t prefix = {
 141         .fp_proto = FIB_PROTOCOL_MPLS,
 142         .fp_payload_proto = DPO_PROTO_MPLS,
 143     };
 144
 145     /*
 146      * PUNT the router alert, both EOS and non-eos
 147      */
 148     prefix.fp_label = MPLS_IETF_ROUTER_ALERT_LABEL;
 149     FOR_EACH_MPLS_EOS_BIT(eos)
 150     {
 151         prefix.fp_eos = eos;
 152         fib_table_entry_special_dpo_add(fib_table->ft_index,
 153                                         &prefix,
 154                                         FIB_SOURCE_SPECIAL,
 155                                         FIB_ENTRY_FLAG_EXCLUSIVE,
 156                                         punt_dpo_get(DPO_PROTO_MPLS));
 157     }
 158
 159     /*
 160      * IPv4 explicit NULL EOS lookup in the interface's IPv4 table
 161      */
 162     prefix.fp_label = MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL;
 163     prefix.fp_payload_proto = DPO_PROTO_IP4;
 164     prefix.fp_eos = MPLS_EOS;
 165
 166     lookup_dpo_add_or_lock_w_fib_index(0, // unused
 167                                        DPO_PROTO_IP4,
 168                                        LOOKUP_UNICAST,
 169                                        LOOKUP_INPUT_DST_ADDR,
 170                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 171                                        &dpo);
 172     fib_table_entry_special_dpo_add(fib_table->ft_index,
 173                                     &prefix,
 174                                     FIB_SOURCE_SPECIAL,
 175                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 176                                     &dpo);
 177
 178     prefix.fp_payload_proto = DPO_PROTO_MPLS;
 179     prefix.fp_eos = MPLS_NON_EOS;
 180
 181     lookup_dpo_add_or_lock_w_fib_index(0, //unsued
 182                                        DPO_PROTO_MPLS,
 183                                        LOOKUP_UNICAST,
 184                                        LOOKUP_INPUT_DST_ADDR,
 185                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 186                                        &dpo);
 187     fib_table_entry_special_dpo_add(fib_table->ft_index,
 188                                     &prefix,
 189                                     FIB_SOURCE_SPECIAL,
 190                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 191                                     &dpo);
 192
 193     /*
 194      * IPv6 explicit NULL EOS lookup in the interface's IPv6 table
 195      */
 196     prefix.fp_label = MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL;
 197     prefix.fp_payload_proto = DPO_PROTO_IP6;
 198     prefix.fp_eos = MPLS_EOS;
 199
 200     lookup_dpo_add_or_lock_w_fib_index(0, //unused
 201                                        DPO_PROTO_IP6,
 202                                        LOOKUP_UNICAST,
 203                                        LOOKUP_INPUT_DST_ADDR,
 204                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 205                                        &dpo);
 206     fib_table_entry_special_dpo_add(fib_table->ft_index,
 207                                     &prefix,
 208                                     FIB_SOURCE_SPECIAL,
 209                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 210                                     &dpo);
 211
 212     prefix.fp_payload_proto = DPO_PROTO_MPLS;
 213     prefix.fp_eos = MPLS_NON_EOS;
 214     lookup_dpo_add_or_lock_w_fib_index(0, // unsued
 215                                        DPO_PROTO_MPLS,
 216                                        LOOKUP_UNICAST,
 217                                        LOOKUP_INPUT_DST_ADDR,
 218                                        LOOKUP_TABLE_FROM_INPUT_INTERFACE,
 219                                        &dpo);
 220     fib_table_entry_special_dpo_add(fib_table->ft_index,
 221                                     &prefix,
 222                                     FIB_SOURCE_SPECIAL,
 223                                     FIB_ENTRY_FLAG_EXCLUSIVE,
 224                                     &dpo);
 225
 226     return (fib_table->ft_index);
 227 }
 228
 229 u32
 230 mpls_fib_table_find_or_create_and_lock (u32 table_id)
 231 {
 232     u32 index;
 233
 234     index = mpls_fib_index_from_table_id(table_id);
 235     if (~0 == index)
 236         return mpls_fib_create_with_table_id(table_id);
 237
 238     fib_table_lock(index, FIB_PROTOCOL_MPLS);
 239
 240     return (index);
 241 }
 242 u32
 243 mpls_fib_table_create_and_lock (void)
 244 {
 245     return (mpls_fib_create_with_table_id(~0));
 246 }
 247
 248 void
 249 mpls_fib_table_destroy (u32 fib_index)
 250 {
 251     fib_table_t *fib_table = pool_elt_at_index(mpls_main.fibs, fib_index);
 252     mpls_fib_t *mf = pool_elt_at_index(mpls_main.mpls_fibs, fib_index);
 253     fib_prefix_t prefix = {
 254         .fp_proto = FIB_PROTOCOL_MPLS,
 255     };
 256     mpls_label_t special_labels[] = {
 257         MPLS_IETF_ROUTER_ALERT_LABEL,
 258         MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL,
 259         MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL,
 260     };
 261     mpls_eos_bit_t eos;
 262     u32 ii;
 263
 264     for (ii = 0; ii < ARRAY_LEN(special_labels); ii++)
 265     {
 266         FOR_EACH_MPLS_EOS_BIT(eos)
 267         {
 268             prefix.fp_label = special_labels[ii];
 269             prefix.fp_eos   = eos;
 270
 271             fib_table_entry_delete(fib_table->ft_index,
 272                                    &prefix,
 273                                    FIB_SOURCE_SPECIAL);
 274         }
 275     }
 276     if (~0 != fib_table->ft_table_id)
 277     {
 278         hash_unset(mpls_main.fib_index_by_table_id,
 279                    fib_table->ft_table_id);
 280     }
 281     hash_free(mf->mf_entries);
 282
 283     pool_put(mpls_main.mpls_fibs, mf);
 284     pool_put(mpls_main.fibs, fib_table);
 285 }
 286
 287 fib_node_index_t
 288 mpls_fib_table_lookup (const mpls_fib_t *mf,
 289                        mpls_label_t label,
 290                        mpls_eos_bit_t eos)
 291 {
 292     uword *p;
 293
 294     p = hash_get(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
 295
 296     if (NULL == p)
 297         return FIB_NODE_INDEX_INVALID;
 298
 299     return p[0];
 300 }
 301
 302 void
 303 mpls_fib_table_entry_insert (mpls_fib_t *mf,
 304                              mpls_label_t label,
 305                              mpls_eos_bit_t eos,
 306                              fib_node_index_t lfei)
 307 {
 308     hash_set(mf->mf_entries, mpls_fib_entry_mk_key(label, eos), lfei);
 309 }
 310
 311 void
 312 mpls_fib_table_entry_remove (mpls_fib_t *mf,
 313                              mpls_label_t label,
 314                              mpls_eos_bit_t eos)
 315 {
 316     hash_unset(mf->mf_entries, mpls_fib_entry_mk_key(label, eos));
 317 }
 318
 319 void
 320 mpls_fib_forwarding_table_update (mpls_fib_t *mf,
 321                                   mpls_label_t label,
 322                                   mpls_eos_bit_t eos,
 323                                   const dpo_id_t *dpo)
 324 {
 325     mpls_label_t key;
 326
 327     ASSERT((DPO_LOAD_BALANCE == dpo->dpoi_type) ||
 328            (DPO_REPLICATE == dpo->dpoi_type));
 329     if (CLIB_DEBUG > 0)
 330     {
 331         if (DPO_REPLICATE == dpo->dpoi_type)
 332             ASSERT(dpo->dpoi_index & MPLS_IS_REPLICATE);
 333         if (DPO_LOAD_BALANCE == dpo->dpoi_type)
 334             ASSERT(!(dpo->dpoi_index & MPLS_IS_REPLICATE));
 335     }
 336     key = mpls_fib_entry_mk_key(label, eos);
 337
 338     mf->mf_lbs[key] = dpo->dpoi_index;
 339 }
 340
 341 void
 342 mpls_fib_forwarding_table_reset (mpls_fib_t *mf,
 343                                  mpls_label_t label,
 344                                  mpls_eos_bit_t eos)
 345 {
 346     mpls_label_t key;
 347
 348     key = mpls_fib_entry_mk_key(label, eos);
 349
 350     mf->mf_lbs[key] = mpls_fib_drop_dpo_index;
 351 }
 352
 353 flow_hash_config_t
 354 mpls_fib_table_get_flow_hash_config (u32 fib_index)
 355 {
 356     // FIXME.
 357     return (0);
 358 }
 359
 360 void
 361 mpls_fib_table_walk (mpls_fib_t *mpls_fib,
 362                      fib_table_walk_fn_t fn,
 363                      void *ctx)
 364 {
 365     fib_node_index_t lfei;
 366     mpls_label_t key;
 367
 368     hash_foreach(key, lfei, mpls_fib->mf_entries,
 369     ({
 370         fn(lfei, ctx);
 371     }));
 372 }
 373
 374 static void
 375 mpls_fib_table_show_all (const mpls_fib_t *mpls_fib,
 376                          vlib_main_t * vm)
 377 {
 378     fib_node_index_t lfei, *lfeip, *lfeis = NULL;
 379     mpls_label_t key;
 380
 381     hash_foreach(key, lfei, mpls_fib->mf_entries,
 382     ({
 383         vec_add1(lfeis, lfei);
 384     }));
 385
 386     vec_sort_with_function(lfeis, fib_entry_cmp_for_sort);
 387
 388     vec_foreach(lfeip, lfeis)
 389     {
 390         vlib_cli_output (vm, "%U",
 391                          format_fib_entry, *lfeip,
 392                          FIB_ENTRY_FORMAT_DETAIL);
 393     }
 394     vec_free(lfeis);
 395 }
 396
 397 static void
 398 mpls_fib_table_show_one (const mpls_fib_t *mpls_fib,
 399                          mpls_label_t label,
 400                          vlib_main_t * vm)
 401 {
 402     fib_node_index_t lfei;
 403     mpls_eos_bit_t eos;
 404
 405     FOR_EACH_MPLS_EOS_BIT(eos)
 406     {
 407         lfei = mpls_fib_table_lookup(mpls_fib, label, eos);
 408
 409         if (FIB_NODE_INDEX_INVALID != lfei)
 410         {
 411             vlib_cli_output (vm, "%U",
 412                              format_fib_entry, lfei, FIB_ENTRY_FORMAT_DETAIL);
 413         }
 414     }
 415 }
 416
 417 static clib_error_t *
 418 mpls_fib_show (vlib_main_t * vm,
 419                unformat_input_t * input,
 420                vlib_cli_command_t * cmd)
 421 {
 422     fib_table_t * fib_table;
 423     mpls_label_t label;
 424     int table_id;
 425
 426     table_id = -1;
 427     label = MPLS_LABEL_INVALID;
 428
 429     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 430     {
 431         /* if (unformat (input, "brief") || unformat (input, "summary") */
 432         /*     || unformat (input, "sum")) */
 433         /*     verbose = 0; */
 434
 435         if (unformat (input, "%d", &label))
 436             continue;
 437         else if (unformat (input, "table %d", &table_id))
 438             ;
 439         else
 440             break;
 441     }
 442
 443     pool_foreach (fib_table, mpls_main.fibs,
 444     ({
 445         if (table_id >= 0 && table_id != fib_table->ft_table_id)
 446             continue;
 447
 448         vlib_cli_output (vm, "%v, fib_index %d",
 449                          fib_table->ft_desc, mpls_main.fibs - fib_table);
 450
 451         if (MPLS_LABEL_INVALID == label)
 452         {
 453             mpls_fib_table_show_all(mpls_fib_get(fib_table->ft_index), vm);
 454         }
 455         else
 456         {
 457             mpls_fib_table_show_one(mpls_fib_get(fib_table->ft_index), label, vm);
 458         }
 459     }));
 460
 461     return 0;
 462 }
 463
 464 VLIB_CLI_COMMAND (mpls_fib_show_command, static) = {
 465     .path = "show mpls fib",
 466     .short_help = "show mpls fib [summary] [table <n>]",
 467     .function = mpls_fib_show,
 468 };