src/vnet/mpls/mpls_tunnel.c

   1 /*
   2  * mpls_tunnel.c: MPLS tunnel interfaces (i.e. for RSVP-TE)
   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 #include <vnet/vnet.h>
  19 #include <vnet/pg/pg.h>
  20 #include <vnet/mpls/mpls_tunnel.h>
  21 #include <vnet/mpls/mpls_types.h>
  22 #include <vnet/ip/ip.h>
  23 #include <vnet/fib/fib_path_list.h>
  24 #include <vnet/adj/adj_midchain.h>
  25 #include <vnet/adj/adj_mcast.h>
  26 #include <vnet/dpo/replicate_dpo.h>
  27 #include <vnet/fib/mpls_fib.h>
  28
  29 /**
  30  * @brief pool of tunnel instances
  31  */
  32 static mpls_tunnel_t *mpls_tunnel_pool;
  33
  34 /**
  35  * @brief Pool of free tunnel SW indices - i.e. recycled indices
  36  */
  37 static u32 * mpls_tunnel_free_hw_if_indices;
  38
  39 /**
  40  * @brief DB of SW index to tunnel index
  41  */
  42 static u32 *mpls_tunnel_db;
  43
  44 /**
  45  * @brief MPLS tunnel flags strings
  46  */
  47 static const char *mpls_tunnel_attribute_names[] = MPLS_TUNNEL_ATTRIBUTES;
  48
  49 /**
  50  * @brief Get a tunnel object from a SW interface index
  51  */
  52 static mpls_tunnel_t*
  53 mpls_tunnel_get_from_sw_if_index (u32 sw_if_index)
  54 {
  55     if ((vec_len(mpls_tunnel_db) < sw_if_index) ||
  56         (~0 == mpls_tunnel_db[sw_if_index]))
  57         return (NULL);
  58
  59     return (pool_elt_at_index(mpls_tunnel_pool,
  60                               mpls_tunnel_db[sw_if_index]));
  61 }
  62
  63 /**
  64  * @brief Build a rewrite string for the MPLS tunnel.
  65  */
  66 static u8*
  67 mpls_tunnel_build_rewrite_i (void)
  68 {
  69     /*
  70      * passing the adj code a NULL rewirte means 'i don't have one cos
  71      * t'other end is unresolved'. That's not the case here. For the mpls
  72      * tunnel there are just no bytes of encap to apply in the adj. We'll impose
  73      * the label stack once we choose a path. So return a zero length rewrite.
  74      */
  75     u8 *rewrite = NULL;
  76
  77     vec_validate(rewrite, 0);
  78     vec_reset_length(rewrite);
  79
  80     return (rewrite);
  81 }
  82
  83 /**
  84  * @brief Build a rewrite string for the MPLS tunnel.
  85  */
  86 static u8*
  87 mpls_tunnel_build_rewrite (vnet_main_t * vnm,
  88                            u32 sw_if_index,
  89                            vnet_link_t link_type,
  90                            const void *dst_address)
  91 {
  92     return (mpls_tunnel_build_rewrite_i());
  93 }
  94
  95 typedef struct mpls_tunnel_collect_forwarding_ctx_t_
  96 {
  97     load_balance_path_t * next_hops;
  98     const mpls_tunnel_t *mt;
  99     fib_forward_chain_type_t fct;
 100 } mpls_tunnel_collect_forwarding_ctx_t;
 101
 102 static int
 103 mpls_tunnel_collect_forwarding (fib_node_index_t pl_index,
 104                                 fib_node_index_t path_index,
 105                                 void *arg)
 106 {
 107     mpls_tunnel_collect_forwarding_ctx_t *ctx;
 108     fib_path_ext_t *path_ext;
 109     int have_path_ext;
 110
 111     ctx = arg;
 112
 113     /*
 114      * if the path is not resolved, don't include it.
 115      */
 116     if (!fib_path_is_resolved(path_index))
 117     {
 118         return (!0);
 119     }
 120
 121     /*
 122      * get the matching path-extension for the path being visited.
 123      */
 124     have_path_ext = 0;
 125     vec_foreach(path_ext, ctx->mt->mt_path_exts)
 126     {
 127         if (path_ext->fpe_path_index == path_index)
 128         {
 129             have_path_ext = 1;
 130             break;
 131         }
 132     }
 133
 134     if (have_path_ext)
 135     {
 136         /*
 137          * found a matching extension. stack it to obtain the forwarding
 138          * info for this path.
 139          */
 140         ctx->next_hops = fib_path_ext_stack(path_ext,
 141                                             ctx->fct,
 142                                             ctx->fct,
 143                                             ctx->next_hops);
 144     }
 145     else
 146         ASSERT(0);
 147     /*
 148      * else
 149      *   There should be a path-extenios associated with each path
 150      */
 151
 152     return (!0);
 153 }
 154
 155 static void
 156 mpls_tunnel_mk_lb (mpls_tunnel_t *mt,
 157                    vnet_link_t linkt,
 158                    fib_forward_chain_type_t fct,
 159                    dpo_id_t *dpo_lb)
 160 {
 161     dpo_proto_t lb_proto;
 162
 163     /*
 164      * If the entry has path extensions then we construct a load-balance
 165      * by stacking the extensions on the forwarding chains of the paths.
 166      * Otherwise we use the load-balance of the path-list
 167      */
 168     mpls_tunnel_collect_forwarding_ctx_t ctx = {
 169         .mt = mt,
 170         .next_hops = NULL,
 171         .fct = fct,
 172     };
 173
 174     /*
 175      * As an optimisation we allocate the vector of next-hops to be sized
 176      * equal to the maximum nuber of paths we will need, which is also the
 177      * most likely number we will need, since in most cases the paths are 'up'.
 178      */
 179     vec_validate(ctx.next_hops, fib_path_list_get_n_paths(mt->mt_path_list));
 180     vec_reset_length(ctx.next_hops);
 181
 182     lb_proto = vnet_link_to_dpo_proto(linkt);
 183
 184     fib_path_list_walk(mt->mt_path_list,
 185                        mpls_tunnel_collect_forwarding,
 186                        &ctx);
 187
 188     if (!dpo_id_is_valid(dpo_lb))
 189     {
 190         /*
 191          * first time create
 192          */
 193         if (mt->mt_flags & MPLS_TUNNEL_FLAG_MCAST)
 194         {
 195             dpo_set(dpo_lb,
 196                     DPO_REPLICATE,
 197                     lb_proto,
 198                     replicate_create(0, lb_proto));
 199         }
 200         else
 201         {
 202             flow_hash_config_t fhc;
 203
 204             switch (linkt)
 205             {
 206             case VNET_LINK_MPLS:
 207                 fhc = MPLS_FLOW_HASH_DEFAULT;
 208                 break;
 209             case VNET_LINK_IP4:
 210             case VNET_LINK_IP6:
 211                 fhc = IP_FLOW_HASH_DEFAULT;
 212                 break;
 213             default:
 214                 fhc = 0;
 215                 break;
 216             }
 217
 218             dpo_set(dpo_lb,
 219                     DPO_LOAD_BALANCE,
 220                     lb_proto,
 221                     load_balance_create(0, lb_proto, fhc));
 222         }
 223     }
 224
 225     if (mt->mt_flags & MPLS_TUNNEL_FLAG_MCAST)
 226     {
 227         /*
 228          * MPLS multicast
 229          */
 230         replicate_multipath_update(dpo_lb, ctx.next_hops);
 231     }
 232     else
 233     {
 234         load_balance_multipath_update(dpo_lb,
 235                                       ctx.next_hops,
 236                                       LOAD_BALANCE_FLAG_NONE);
 237         vec_free(ctx.next_hops);
 238     }
 239 }
 240
 241 /**
 242  * mpls_tunnel_stack
 243  *
 244  * 'stack' (resolve the recursion for) the tunnel's midchain adjacency
 245  */
 246 static void
 247 mpls_tunnel_stack (adj_index_t ai)
 248 {
 249     ip_adjacency_t *adj;
 250     mpls_tunnel_t *mt;
 251     u32 sw_if_index;
 252
 253     adj = adj_get(ai);
 254     sw_if_index = adj->rewrite_header.sw_if_index;
 255
 256     mt = mpls_tunnel_get_from_sw_if_index(sw_if_index);
 257
 258     if (NULL == mt)
 259         return;
 260
 261     /*
 262      * while we're stacking the adj, remove the tunnel from the child list
 263      * of the path list. this breaks a circular dependency of walk updates
 264      * where the create of adjacencies in the children can lead to walks
 265      * that get back here.
 266      */
 267     fib_path_list_lock(mt->mt_path_list);
 268
 269     fib_path_list_child_remove(mt->mt_path_list,
 270                                mt->mt_sibling_index);
 271
 272     /*
 273      * Construct the DPO (load-balance or replicate) that we can stack
 274      * the tunnel's midchain on
 275      */
 276     if (vnet_hw_interface_get_flags(vnet_get_main(),
 277                                     mt->mt_hw_if_index) &
 278         VNET_HW_INTERFACE_FLAG_LINK_UP)
 279     {
 280         dpo_id_t dpo = DPO_INVALID;
 281
 282         mpls_tunnel_mk_lb(mt,
 283                           adj->ia_link,
 284                           FIB_FORW_CHAIN_TYPE_MPLS_EOS,
 285                           &dpo);
 286
 287         adj_nbr_midchain_stack(ai, &dpo);
 288         dpo_reset(&dpo);
 289     }
 290     else
 291     {
 292         adj_nbr_midchain_unstack(ai);
 293     }
 294
 295     mt->mt_sibling_index = fib_path_list_child_add(mt->mt_path_list,
 296                                                    FIB_NODE_TYPE_MPLS_TUNNEL,
 297                                                    mt - mpls_tunnel_pool);
 298
 299     fib_path_list_lock(mt->mt_path_list);
 300 }
 301
 302 /**
 303  * @brief Call back when restacking all adjacencies on a MPLS interface
 304  */
 305 static adj_walk_rc_t
 306 mpls_adj_walk_cb (adj_index_t ai,
 307                  void *ctx)
 308 {
 309     mpls_tunnel_stack(ai);
 310
 311     return (ADJ_WALK_RC_CONTINUE);
 312 }
 313
 314 static void
 315 mpls_tunnel_restack (mpls_tunnel_t *mt)
 316 {
 317     fib_protocol_t proto;
 318
 319     /*
 320      * walk all the adjacencies on the MPLS interface and restack them
 321      */
 322     FOR_EACH_FIB_PROTOCOL(proto)
 323     {
 324         adj_nbr_walk(mt->mt_sw_if_index,
 325                      proto,
 326                      mpls_adj_walk_cb,
 327                      NULL);
 328     }
 329 }
 330
 331 static clib_error_t *
 332 mpls_tunnel_admin_up_down (vnet_main_t * vnm,
 333                            u32 hw_if_index,
 334                            u32 flags)
 335 {
 336     vnet_hw_interface_t * hi;
 337     mpls_tunnel_t *mt;
 338
 339     hi = vnet_get_hw_interface (vnm, hw_if_index);
 340
 341     mt = mpls_tunnel_get_from_sw_if_index(hi->sw_if_index);
 342
 343     if (NULL == mt)
 344         return (NULL);
 345
 346     if (flags & VNET_SW_INTERFACE_FLAG_ADMIN_UP)
 347         vnet_hw_interface_set_flags (vnm, hw_if_index,
 348                                      VNET_HW_INTERFACE_FLAG_LINK_UP);
 349     else
 350         vnet_hw_interface_set_flags (vnm, hw_if_index, 0 /* down */);
 351
 352     mpls_tunnel_restack(mt);
 353
 354     return (NULL);
 355 }
 356
 357 /**
 358  * @brief Fixup the adj rewrite post encap. This is a no-op since the
 359  * rewrite is a stack of labels.
 360  */
 361 static void
 362 mpls_tunnel_fixup (vlib_main_t *vm,
 363                    ip_adjacency_t *adj,
 364                    vlib_buffer_t *b0)
 365 {
 366     /*
 367      * A no-op w.r.t. the header. but reset the 'have we pushed any
 368      * MPLS labels onto the packet' flag. That way when we enter the
 369      * tunnel we'll get a TTL set to 255
 370      */
 371     vnet_buffer(b0)->mpls.first = 0;
 372 }
 373
 374 static void
 375 mpls_tunnel_update_adj (vnet_main_t * vnm,
 376                         u32 sw_if_index,
 377                         adj_index_t ai)
 378 {
 379     ip_adjacency_t *adj;
 380
 381     ASSERT(ADJ_INDEX_INVALID != ai);
 382
 383     adj = adj_get(ai);
 384
 385     switch (adj->lookup_next_index)
 386     {
 387     case IP_LOOKUP_NEXT_ARP:
 388     case IP_LOOKUP_NEXT_GLEAN:
 389         adj_nbr_midchain_update_rewrite(ai, mpls_tunnel_fixup,
 390                                         ADJ_FLAG_NONE,
 391                                         mpls_tunnel_build_rewrite_i());
 392         break;
 393     case IP_LOOKUP_NEXT_MCAST:
 394         /*
 395          * Construct a partial rewrite from the known ethernet mcast dest MAC
 396          * There's no MAC fixup, so the last 2 parameters are 0
 397          */
 398         adj_mcast_midchain_update_rewrite(ai, mpls_tunnel_fixup,
 399                                           ADJ_FLAG_NONE,
 400                                           mpls_tunnel_build_rewrite_i(),
 401                                           0, 0);
 402         break;
 403
 404     case IP_LOOKUP_NEXT_DROP:
 405     case IP_LOOKUP_NEXT_PUNT:
 406     case IP_LOOKUP_NEXT_LOCAL:
 407     case IP_LOOKUP_NEXT_REWRITE:
 408     case IP_LOOKUP_NEXT_MIDCHAIN:
 409     case IP_LOOKUP_NEXT_MCAST_MIDCHAIN:
 410     case IP_LOOKUP_NEXT_ICMP_ERROR:
 411     case IP_LOOKUP_N_NEXT:
 412       ASSERT (0);
 413       break;
 414     }
 415
 416     mpls_tunnel_stack(ai);
 417 }
 418
 419 static u8 *
 420 format_mpls_tunnel_name (u8 * s, va_list * args)
 421 {
 422   u32 dev_instance = va_arg (*args, u32);
 423   return format (s, "mpls-tunnel%d", dev_instance);
 424 }
 425
 426 static u8 *
 427 format_mpls_tunnel_device (u8 * s, va_list * args)
 428 {
 429   u32 dev_instance = va_arg (*args, u32);
 430   CLIB_UNUSED (int verbose) = va_arg (*args, int);
 431
 432   return (format (s, "MPLS-tunnel: id %d\n", dev_instance));
 433 }
 434
 435 /**
 436  * @brief Packet trace structure
 437  */
 438 typedef struct mpls_tunnel_trace_t_
 439 {
 440     /**
 441    * Tunnel-id / index in tunnel vector
 442    */
 443   u32 tunnel_id;
 444 } mpls_tunnel_trace_t;
 445
 446 static u8 *
 447 format_mpls_tunnel_tx_trace (u8 * s,
 448                              va_list * args)
 449 {
 450   CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
 451   CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
 452   mpls_tunnel_trace_t * t = va_arg (*args, mpls_tunnel_trace_t *);
 453
 454   s = format (s, "MPLS: tunnel %d", t->tunnel_id);
 455   return s;
 456 }
 457
 458 /**
 459  * @brief TX function. Only called L2. L3 traffic uses the adj-midchains
 460  */
 461 static uword
 462 mpls_tunnel_tx (vlib_main_t * vm,
 463                 vlib_node_runtime_t * node,
 464                 vlib_frame_t * frame)
 465 {
 466   u32 next_index;
 467   u32 * from, * to_next, n_left_from, n_left_to_next;
 468   vnet_interface_output_runtime_t * rd = (void *) node->runtime_data;
 469   const mpls_tunnel_t *mt;
 470
 471   mt = pool_elt_at_index(mpls_tunnel_pool, rd->dev_instance);
 472
 473   /* Vector of buffer / pkt indices we're supposed to process */
 474   from = vlib_frame_vector_args (frame);
 475
 476   /* Number of buffers / pkts */
 477   n_left_from = frame->n_vectors;
 478
 479   /* Speculatively send the first buffer to the last disposition we used */
 480   next_index = node->cached_next_index;
 481
 482   while (n_left_from > 0)
 483     {
 484       /* set up to enqueue to our disposition with index = next_index */
 485       vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
 486
 487       /*
 488        * FIXME DUAL LOOP
 489        */
 490       while (n_left_from > 0 && n_left_to_next > 0)
 491         {
 492           vlib_buffer_t * b0;
 493           u32 bi0;
 494
 495           bi0 = from[0];
 496           to_next[0] = bi0;
 497           from += 1;
 498           to_next += 1;
 499           n_left_from -= 1;
 500           n_left_to_next -= 1;
 501
 502           b0 = vlib_get_buffer(vm, bi0);
 503
 504           vnet_buffer(b0)->ip.adj_index[VLIB_TX] = mt->mt_l2_adj;
 505
 506           if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
 507             {
 508               mpls_tunnel_trace_t *tr = vlib_add_trace (vm, node,
 509                                                    b0, sizeof (*tr));
 510               tr->tunnel_id = rd->dev_instance;
 511             }
 512
 513           vlib_validate_buffer_enqueue_x1 (vm, node, next_index,
 514                                            to_next, n_left_to_next,
 515                                            bi0, mt->mt_l2_tx_arc);
 516         }
 517
 518       vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 519     }
 520
 521   return frame->n_vectors;
 522 }
 523
 524 VNET_DEVICE_CLASS (mpls_tunnel_class) = {
 525     .name = "MPLS tunnel device",
 526     .format_device_name = format_mpls_tunnel_name,
 527     .format_device = format_mpls_tunnel_device,
 528     .format_tx_trace = format_mpls_tunnel_tx_trace,
 529     .tx_function = mpls_tunnel_tx,
 530     .admin_up_down_function = mpls_tunnel_admin_up_down,
 531 };
 532
 533 VNET_HW_INTERFACE_CLASS (mpls_tunnel_hw_interface_class) = {
 534   .name = "MPLS-Tunnel",
 535 //  .format_header = format_mpls_eth_header_with_length,
 536 //  .unformat_header = unformat_mpls_eth_header,
 537   .update_adjacency = mpls_tunnel_update_adj,
 538   .build_rewrite = mpls_tunnel_build_rewrite,
 539   .flags = VNET_HW_INTERFACE_CLASS_FLAG_P2P,
 540 };
 541
 542 const mpls_tunnel_t *
 543 mpls_tunnel_get (u32 mti)
 544 {
 545     return (pool_elt_at_index(mpls_tunnel_pool, mti));
 546 }
 547
 548 /**
 549  * @brief Walk all the MPLS tunnels
 550  */
 551 void
 552 mpls_tunnel_walk (mpls_tunnel_walk_cb_t cb,
 553                   void *ctx)
 554 {
 555     u32 mti;
 556
 557     pool_foreach_index(mti, mpls_tunnel_pool,
 558     ({
 559         cb(mti, ctx);
 560     }));
 561 }
 562
 563 void
 564 vnet_mpls_tunnel_del (u32 sw_if_index)
 565 {
 566     mpls_tunnel_t *mt;
 567
 568     mt = mpls_tunnel_get_from_sw_if_index(sw_if_index);
 569
 570     if (NULL == mt)
 571         return;
 572
 573     if (FIB_NODE_INDEX_INVALID != mt->mt_path_list)
 574         fib_path_list_child_remove(mt->mt_path_list,
 575                                    mt->mt_sibling_index);
 576     if (ADJ_INDEX_INVALID != mt->mt_l2_adj)
 577         adj_unlock(mt->mt_l2_adj);
 578
 579     vec_add1 (mpls_tunnel_free_hw_if_indices, mt->mt_hw_if_index);
 580     pool_put(mpls_tunnel_pool, mt);
 581     mpls_tunnel_db[sw_if_index] = ~0;
 582 }
 583
 584 u32
 585 vnet_mpls_tunnel_create (u8 l2_only,
 586                          u8 is_multicast)
 587 {
 588     vnet_hw_interface_t * hi;
 589     mpls_tunnel_t *mt;
 590     vnet_main_t * vnm;
 591     u32 mti;
 592
 593     vnm = vnet_get_main();
 594     pool_get(mpls_tunnel_pool, mt);
 595     memset (mt, 0, sizeof (*mt));
 596     mti = mt - mpls_tunnel_pool;
 597     fib_node_init(&mt->mt_node, FIB_NODE_TYPE_MPLS_TUNNEL);
 598     mt->mt_l2_adj = ADJ_INDEX_INVALID;
 599     mt->mt_path_list = FIB_NODE_INDEX_INVALID;
 600     mt->mt_sibling_index = FIB_NODE_INDEX_INVALID;
 601
 602     if (is_multicast)
 603         mt->mt_flags |= MPLS_TUNNEL_FLAG_MCAST;
 604
 605     /*
 606      * Create a new, or re=use and old, tunnel HW interface
 607      */
 608     if (vec_len (mpls_tunnel_free_hw_if_indices) > 0)
 609     {
 610         mt->mt_hw_if_index =
 611             mpls_tunnel_free_hw_if_indices[vec_len(mpls_tunnel_free_hw_if_indices)-1];
 612         _vec_len (mpls_tunnel_free_hw_if_indices) -= 1;
 613         hi = vnet_get_hw_interface (vnm, mt->mt_hw_if_index);
 614         hi->hw_instance = mti;
 615         hi->dev_instance = mti;
 616     }
 617     else
 618     {
 619         mt->mt_hw_if_index = vnet_register_interface(
 620                                  vnm,
 621                                  mpls_tunnel_class.index,
 622                                  mti,
 623                                  mpls_tunnel_hw_interface_class.index,
 624                                  mti);
 625         hi = vnet_get_hw_interface(vnm, mt->mt_hw_if_index);
 626     }
 627
 628     /*
 629      * Add the new tunnel to the tunnel DB - key:SW if index
 630      */
 631     mt->mt_sw_if_index = hi->sw_if_index;
 632     vec_validate_init_empty(mpls_tunnel_db, mt->mt_sw_if_index, ~0);
 633     mpls_tunnel_db[mt->mt_sw_if_index] = mti;
 634
 635     if (l2_only)
 636     {
 637         mt->mt_l2_adj =
 638             adj_nbr_add_or_lock(fib_path_list_get_proto(mt->mt_path_list),
 639                                 VNET_LINK_ETHERNET,
 640                                 &zero_addr,
 641                                 mt->mt_sw_if_index);
 642
 643         mt->mt_l2_tx_arc = vlib_node_add_named_next(vlib_get_main(),
 644                                                     hi->tx_node_index,
 645                                                     "adj-l2-midchain");
 646     }
 647
 648     return (mt->mt_sw_if_index);
 649 }
 650
 651 /*
 652  * mpls_tunnel_path_ext_add
 653  *
 654  * append a path extension to the entry's list
 655  */
 656 static void
 657 mpls_tunnel_path_ext_append (mpls_tunnel_t *mt,
 658                              const fib_route_path_t *rpath)
 659 {
 660     if (NULL != rpath->frp_label_stack)
 661     {
 662         fib_path_ext_t *path_ext;
 663
 664         vec_add2(mt->mt_path_exts, path_ext, 1);
 665
 666         fib_path_ext_init(path_ext, mt->mt_path_list, rpath);
 667     }
 668 }
 669
 670 /*
 671  * mpls_tunnel_path_ext_insert
 672  *
 673  * insert, sorted, a path extension to the entry's list.
 674  * It's not strictly necessary in sort the path extensions, since each
 675  * extension has the path index to which it resolves. However, by being
 676  * sorted the load-balance produced has a deterministic order, not an order
 677  * based on the sequence of extension additions. this is a considerable benefit.
 678  */
 679 static void
 680 mpls_tunnel_path_ext_insert (mpls_tunnel_t *mt,
 681                              const fib_route_path_t *rpath)
 682 {
 683     if (0 == vec_len(mt->mt_path_exts))
 684         return (mpls_tunnel_path_ext_append(mt, rpath));
 685
 686     if (NULL != rpath->frp_label_stack)
 687     {
 688         fib_path_ext_t path_ext;
 689         int i = 0;
 690
 691         fib_path_ext_init(&path_ext, mt->mt_path_list, rpath);
 692
 693         while (i < vec_len(mt->mt_path_exts) &&
 694                (fib_path_ext_cmp(&mt->mt_path_exts[i], rpath) < 0))
 695         {
 696             i++;
 697         }
 698
 699         vec_insert_elts(mt->mt_path_exts, &path_ext, 1, i);
 700     }
 701 }
 702
 703 void
 704 vnet_mpls_tunnel_path_add (u32 sw_if_index,
 705                            fib_route_path_t *rpaths)
 706 {
 707     mpls_tunnel_t *mt;
 708     u32 mti;
 709
 710     mt = mpls_tunnel_get_from_sw_if_index(sw_if_index);
 711
 712     if (NULL == mt)
 713         return;
 714
 715     mti = mt - mpls_tunnel_pool;
 716
 717     /*
 718      * construct a path-list from the path provided
 719      */
 720     if (FIB_NODE_INDEX_INVALID == mt->mt_path_list)
 721     {
 722         mt->mt_path_list = fib_path_list_create(FIB_PATH_LIST_FLAG_SHARED, rpaths);
 723         mt->mt_sibling_index = fib_path_list_child_add(mt->mt_path_list,
 724                                                        FIB_NODE_TYPE_MPLS_TUNNEL,
 725                                                        mti);
 726     }
 727     else
 728     {
 729         fib_node_index_t old_pl_index;
 730         fib_path_ext_t *path_ext;
 731
 732         old_pl_index = mt->mt_path_list;
 733
 734         mt->mt_path_list =
 735             fib_path_list_copy_and_path_add(old_pl_index,
 736                                             FIB_PATH_LIST_FLAG_SHARED,
 737                                             rpaths);
 738
 739         fib_path_list_child_remove(old_pl_index,
 740                                    mt->mt_sibling_index);
 741         mt->mt_sibling_index = fib_path_list_child_add(mt->mt_path_list,
 742                                                        FIB_NODE_TYPE_MPLS_TUNNEL,
 743                                                        mti);
 744         /*
 745          * re-resolve all the path-extensions with the new path-list
 746          */
 747         vec_foreach(path_ext, mt->mt_path_exts)
 748         {
 749             fib_path_ext_resolve(path_ext, mt->mt_path_list);
 750         }
 751     }
 752     mpls_tunnel_path_ext_insert(mt, rpaths);
 753     mpls_tunnel_restack(mt);
 754 }
 755
 756 int
 757 vnet_mpls_tunnel_path_remove (u32 sw_if_index,
 758                               fib_route_path_t *rpaths)
 759 {
 760     mpls_tunnel_t *mt;
 761     u32 mti;
 762
 763     mt = mpls_tunnel_get_from_sw_if_index(sw_if_index);
 764
 765     if (NULL == mt)
 766         return (0);
 767
 768     mti = mt - mpls_tunnel_pool;
 769
 770     /*
 771      * construct a path-list from the path provided
 772      */
 773     if (FIB_NODE_INDEX_INVALID == mt->mt_path_list)
 774     {
 775         /* can't remove a path if we have onoe */
 776         return (0);
 777     }
 778     else
 779     {
 780         fib_node_index_t old_pl_index;
 781         fib_path_ext_t *path_ext;
 782
 783         old_pl_index = mt->mt_path_list;
 784
 785         mt->mt_path_list =
 786             fib_path_list_copy_and_path_remove(old_pl_index,
 787                                                FIB_PATH_LIST_FLAG_SHARED,
 788                                                rpaths);
 789
 790         fib_path_list_child_remove(old_pl_index,
 791                                    mt->mt_sibling_index);
 792
 793         if (FIB_NODE_INDEX_INVALID == mt->mt_path_list)
 794         {
 795             /* no paths left */
 796             return (0);
 797         }
 798         else
 799         {
 800             mt->mt_sibling_index =
 801                 fib_path_list_child_add(mt->mt_path_list,
 802                                         FIB_NODE_TYPE_MPLS_TUNNEL,
 803                                         mti);
 804         }
 805         /*
 806          * find the matching path extension and remove it
 807          */
 808         vec_foreach(path_ext, mt->mt_path_exts)
 809         {
 810             if (!fib_path_ext_cmp(path_ext, rpaths))
 811             {
 812                 /*
 813                  * delete the element moving the remaining elements down 1 position.
 814                  * this preserves the sorted order.
 815                  */
 816                 vec_free(path_ext->fpe_label_stack);
 817                 vec_delete(mt->mt_path_exts, 1,
 818                            (path_ext - mt->mt_path_exts));
 819                 break;
 820             }
 821         }
 822        /*
 823          * re-resolve all the path-extensions with the new path-list
 824          */
 825         vec_foreach(path_ext, mt->mt_path_exts)
 826         {
 827             fib_path_ext_resolve(path_ext, mt->mt_path_list);
 828         }
 829
 830         mpls_tunnel_restack(mt);
 831    }
 832
 833     return (fib_path_list_get_n_paths(mt->mt_path_list));
 834 }
 835
 836
 837 static clib_error_t *
 838 vnet_create_mpls_tunnel_command_fn (vlib_main_t * vm,
 839                                     unformat_input_t * input,
 840                                     vlib_cli_command_t * cmd)
 841 {
 842     unformat_input_t _line_input, * line_input = &_line_input;
 843     vnet_main_t * vnm = vnet_get_main();
 844     u8 is_del = 0, l2_only = 0, is_multicast =0;
 845     fib_route_path_t rpath, *rpaths = NULL;
 846     mpls_label_t out_label = MPLS_LABEL_INVALID;
 847     u32 sw_if_index;
 848     clib_error_t *error = NULL;
 849
 850     memset(&rpath, 0, sizeof(rpath));
 851
 852     /* Get a line of input. */
 853     if (! unformat_user (input, unformat_line_input, line_input))
 854         return 0;
 855
 856     while (unformat_check_input (line_input) != UNFORMAT_END_OF_INPUT)
 857     {
 858         if (unformat (line_input, "del %U",
 859                       unformat_vnet_sw_interface, vnm,
 860                       &sw_if_index))
 861             is_del = 1;
 862         else if (unformat (line_input, "add"))
 863             is_del = 0;
 864         else if (unformat (line_input, "out-label %U",
 865                            unformat_mpls_unicast_label, &out_label))
 866         {
 867             vec_add1(rpath.frp_label_stack, out_label);
 868         }
 869         else if (unformat (line_input, "via %U %U",
 870                            unformat_ip4_address,
 871                            &rpath.frp_addr.ip4,
 872                            unformat_vnet_sw_interface, vnm,
 873                            &rpath.frp_sw_if_index))
 874         {
 875             rpath.frp_weight = 1;
 876             rpath.frp_proto = FIB_PROTOCOL_IP4;
 877         }
 878
 879         else if (unformat (line_input, "via %U %U",
 880                            unformat_ip6_address,
 881                            &rpath.frp_addr.ip6,
 882                            unformat_vnet_sw_interface, vnm,
 883                            &rpath.frp_sw_if_index))
 884         {
 885             rpath.frp_weight = 1;
 886             rpath.frp_proto = FIB_PROTOCOL_IP6;
 887         }
 888         else if (unformat (line_input, "via %U",
 889                            unformat_ip6_address,
 890                            &rpath.frp_addr.ip6))
 891         {
 892             rpath.frp_fib_index = 0;
 893             rpath.frp_weight = 1;
 894             rpath.frp_sw_if_index = ~0;
 895             rpath.frp_proto = FIB_PROTOCOL_IP6;
 896         }
 897         else if (unformat (line_input, "via %U",
 898                            unformat_ip4_address,
 899                            &rpath.frp_addr.ip4))
 900         {
 901             rpath.frp_fib_index = 0;
 902             rpath.frp_weight = 1;
 903             rpath.frp_sw_if_index = ~0;
 904             rpath.frp_proto = FIB_PROTOCOL_IP4;
 905         }
 906         else if (unformat (line_input, "l2-only"))
 907             l2_only = 1;
 908         else if (unformat (line_input, "multicast"))
 909             is_multicast = 1;
 910         else
 911         {
 912             error = clib_error_return (0, "unknown input '%U'",
 913                                        format_unformat_error, line_input);
 914             goto done;
 915         }
 916     }
 917
 918     if (is_del)
 919     {
 920         vnet_mpls_tunnel_del(sw_if_index);
 921     }
 922     else
 923     {
 924         if (0 == vec_len(rpath.frp_label_stack))
 925         {
 926             error = clib_error_return (0, "No Output Labels '%U'",
 927                                        format_unformat_error, line_input);
 928             goto done;
 929         }
 930
 931         vec_add1(rpaths, rpath);
 932         sw_if_index = vnet_mpls_tunnel_create(l2_only, is_multicast);
 933         vnet_mpls_tunnel_path_add(sw_if_index, rpaths);
 934     }
 935
 936 done:
 937     vec_free(rpaths);
 938     unformat_free (line_input);
 939
 940     return error;
 941 }
 942
 943 /*?
 944  * This command create a uni-directional MPLS tunnel
 945  *
 946  * @cliexpar
 947  * @cliexstart{create mpls tunnel}
 948  *  create mpls tunnel via 10.0.0.1 GigEthernet0/8/0 out-label 33 out-label 34
 949  * @cliexend
 950  ?*/
 951 VLIB_CLI_COMMAND (create_mpls_tunnel_command, static) = {
 952   .path = "mpls tunnel",
 953   .short_help =
 954   "mpls tunnel via [addr] [interface] [out-labels]",
 955   .function = vnet_create_mpls_tunnel_command_fn,
 956 };
 957
 958 static u8 *
 959 format_mpls_tunnel (u8 * s, va_list * args)
 960 {
 961     mpls_tunnel_t *mt = va_arg (*args, mpls_tunnel_t *);
 962     mpls_tunnel_attribute_t attr;
 963     fib_path_ext_t *path_ext;
 964
 965     s = format(s, "mpls_tunnel%d: sw_if_index:%d hw_if_index:%d",
 966                mt - mpls_tunnel_pool,
 967                mt->mt_sw_if_index,
 968                mt->mt_hw_if_index);
 969     if (MPLS_TUNNEL_FLAG_NONE != mt->mt_flags) {
 970         s = format(s, " \n flags:");
 971         FOR_EACH_MPLS_TUNNEL_ATTRIBUTE(attr) {
 972             if ((1<<attr) & mt->mt_flags) {
 973                 s = format (s, "%s,", mpls_tunnel_attribute_names[attr]);
 974             }
 975         }
 976     }
 977     s = format(s, "\n via:\n");
 978     s = fib_path_list_format(mt->mt_path_list, s);
 979     s = format(s, "    Extensions:");
 980     vec_foreach(path_ext, mt->mt_path_exts)
 981     {
 982         s = format(s, "\n     %U", format_fib_path_ext, path_ext);
 983     }
 984     s = format(s, "\n");
 985
 986     return (s);
 987 }
 988
 989 static clib_error_t *
 990 show_mpls_tunnel_command_fn (vlib_main_t * vm,
 991                              unformat_input_t * input,
 992                              vlib_cli_command_t * cmd)
 993 {
 994     mpls_tunnel_t * mt;
 995     u32 mti = ~0;
 996
 997     if (pool_elts (mpls_tunnel_pool) == 0)
 998         vlib_cli_output (vm, "No MPLS tunnels configured...");
 999
1000     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1001     {
1002         if (unformat (input, "%d", &mti))
1003             ;
1004         else
1005             break;
1006     }
1007
1008     if (~0 == mti)
1009     {
1010         pool_foreach (mt, mpls_tunnel_pool,
1011         ({
1012             vlib_cli_output (vm, "[@%d] %U",
1013                              mt - mpls_tunnel_pool,
1014                              format_mpls_tunnel, mt);
1015         }));
1016     }
1017     else
1018     {
1019         if (pool_is_free_index(mpls_tunnel_pool, mti))
1020             return clib_error_return (0, "Not atunnel index %d", mti);
1021
1022         mt = pool_elt_at_index(mpls_tunnel_pool, mti);
1023
1024         vlib_cli_output (vm, "[@%d] %U",
1025                          mt - mpls_tunnel_pool,
1026                          format_mpls_tunnel, mt);
1027     }
1028
1029     return 0;
1030 }
1031
1032 /*?
1033  * This command to show MPLS tunnels
1034  *
1035  * @cliexpar
1036  * @cliexstart{sh mpls tunnel 2}
1037  * [@2] mpls_tunnel2: sw_if_index:5 hw_if_index:5
1038  *  label-stack:
1039  *    3,
1040  *  via:
1041  *   index:26 locks:1 proto:ipv4 uPRF-list:26 len:1 itfs:[2, ]
1042  *     index:26 pl-index:26 ipv4 weight=1 attached-nexthop:  oper-flags:resolved,
1043  *      10.0.0.2 loop0
1044  *         [@0]: ipv4 via 10.0.0.2 loop0: IP4: de:ad:00:00:00:00 -> 00:00:11:aa:bb:cc
1045  * @cliexend
1046  ?*/
1047 VLIB_CLI_COMMAND (show_mpls_tunnel_command, static) = {
1048     .path = "show mpls tunnel",
1049     .function = show_mpls_tunnel_command_fn,
1050 };
1051
1052 static mpls_tunnel_t *
1053 mpls_tunnel_from_fib_node (fib_node_t *node)
1054 {
1055 #if (CLIB_DEBUG > 0)
1056     ASSERT(FIB_NODE_TYPE_MPLS_TUNNEL == node->fn_type);
1057 #endif
1058     return ((mpls_tunnel_t*) (((char*)node) -
1059                              STRUCT_OFFSET_OF(mpls_tunnel_t, mt_node)));
1060 }
1061
1062 /**
1063  * Function definition to backwalk a FIB node
1064  */
1065 static fib_node_back_walk_rc_t
1066 mpls_tunnel_back_walk (fib_node_t *node,
1067                       fib_node_back_walk_ctx_t *ctx)
1068 {
1069     mpls_tunnel_restack(mpls_tunnel_from_fib_node(node));
1070
1071     return (FIB_NODE_BACK_WALK_CONTINUE);
1072 }
1073
1074 /**
1075  * Function definition to get a FIB node from its index
1076  */
1077 static fib_node_t*
1078 mpls_tunnel_fib_node_get (fib_node_index_t index)
1079 {
1080     mpls_tunnel_t * mt;
1081
1082     mt = pool_elt_at_index(mpls_tunnel_pool, index);
1083
1084     return (&mt->mt_node);
1085 }
1086
1087 /**
1088  * Function definition to inform the FIB node that its last lock has gone.
1089  */
1090 static void
1091 mpls_tunnel_last_lock_gone (fib_node_t *node)
1092 {
1093     /*
1094      * The MPLS MPLS tunnel is a root of the graph. As such
1095      * it never has children and thus is never locked.
1096      */
1097     ASSERT(0);
1098 }
1099
1100 /*
1101  * Virtual function table registered by MPLS MPLS tunnels
1102  * for participation in the FIB object graph.
1103  */
1104 const static fib_node_vft_t mpls_vft = {
1105     .fnv_get = mpls_tunnel_fib_node_get,
1106     .fnv_last_lock = mpls_tunnel_last_lock_gone,
1107     .fnv_back_walk = mpls_tunnel_back_walk,
1108 };
1109
1110 static clib_error_t *
1111 mpls_tunnel_init (vlib_main_t *vm)
1112 {
1113   fib_node_register_type(FIB_NODE_TYPE_MPLS_TUNNEL, &mpls_vft);
1114
1115   return 0;
1116 }
1117 VLIB_INIT_FUNCTION(mpls_tunnel_init);