src/vnet/fib/fib_path.c

   1 /*
   2  * Copyright (c) 2016 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 #include <vlib/vlib.h>
  17 #include <vnet/vnet.h>
  18 #include <vnet/ip/format.h>
  19 #include <vnet/ip/ip.h>
  20 #include <vnet/dpo/drop_dpo.h>
  21 #include <vnet/dpo/receive_dpo.h>
  22 #include <vnet/dpo/load_balance_map.h>
  23 #include <vnet/dpo/lookup_dpo.h>
  24 #include <vnet/dpo/interface_dpo.h>
  25 #include <vnet/dpo/mpls_disposition.h>
  26
  27 #include <vnet/adj/adj.h>
  28 #include <vnet/adj/adj_mcast.h>
  29
  30 #include <vnet/fib/fib_path.h>
  31 #include <vnet/fib/fib_node.h>
  32 #include <vnet/fib/fib_table.h>
  33 #include <vnet/fib/fib_entry.h>
  34 #include <vnet/fib/fib_path_list.h>
  35 #include <vnet/fib/fib_internal.h>
  36 #include <vnet/fib/fib_urpf_list.h>
  37 #include <vnet/fib/mpls_fib.h>
  38
  39 /**
  40  * Enurmeration of path types
  41  */
  42 typedef enum fib_path_type_t_ {
  43     /**
  44      * Marker. Add new types after this one.
  45      */
  46     FIB_PATH_TYPE_FIRST = 0,
  47     /**
  48      * Attached-nexthop. An interface and a nexthop are known.
  49      */
  50     FIB_PATH_TYPE_ATTACHED_NEXT_HOP = FIB_PATH_TYPE_FIRST,
  51     /**
  52      * attached. Only the interface is known.
  53      */
  54     FIB_PATH_TYPE_ATTACHED,
  55     /**
  56      * recursive. Only the next-hop is known.
  57      */
  58     FIB_PATH_TYPE_RECURSIVE,
  59     /**
  60      * special. nothing is known. so we drop.
  61      */
  62     FIB_PATH_TYPE_SPECIAL,
  63     /**
  64      * exclusive. user provided adj.
  65      */
  66     FIB_PATH_TYPE_EXCLUSIVE,
  67     /**
  68      * deag. Link to a lookup adj in the next table
  69      */
  70     FIB_PATH_TYPE_DEAG,
  71     /**
  72      * interface receive.
  73      */
  74     FIB_PATH_TYPE_INTF_RX,
  75     /**
  76      * receive. it's for-us.
  77      */
  78     FIB_PATH_TYPE_RECEIVE,
  79     /**
  80      * Marker. Add new types before this one, then update it.
  81      */
  82     FIB_PATH_TYPE_LAST = FIB_PATH_TYPE_RECEIVE,
  83 } __attribute__ ((packed)) fib_path_type_t;
  84
  85 /**
  86  * The maximum number of path_types
  87  */
  88 #define FIB_PATH_TYPE_MAX (FIB_PATH_TYPE_LAST + 1)
  89
  90 #define FIB_PATH_TYPES {                                        \
  91     [FIB_PATH_TYPE_ATTACHED_NEXT_HOP] = "attached-nexthop",     \
  92     [FIB_PATH_TYPE_ATTACHED]          = "attached",             \
  93     [FIB_PATH_TYPE_RECURSIVE]         = "recursive",            \
  94     [FIB_PATH_TYPE_SPECIAL]           = "special",              \
  95     [FIB_PATH_TYPE_EXCLUSIVE]         = "exclusive",            \
  96     [FIB_PATH_TYPE_DEAG]              = "deag",                 \
  97     [FIB_PATH_TYPE_INTF_RX]           = "intf-rx",              \
  98     [FIB_PATH_TYPE_RECEIVE]           = "receive",              \
  99 }
 100
 101 #define FOR_EACH_FIB_PATH_TYPE(_item) \
 102     for (_item = FIB_PATH_TYPE_FIRST; _item <= FIB_PATH_TYPE_LAST; _item++)
 103
 104 /**
 105  * Enurmeration of path operational (i.e. derived) attributes
 106  */
 107 typedef enum fib_path_oper_attribute_t_ {
 108     /**
 109      * Marker. Add new types after this one.
 110      */
 111     FIB_PATH_OPER_ATTRIBUTE_FIRST = 0,
 112     /**
 113      * The path forms part of a recursive loop.
 114      */
 115     FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP = FIB_PATH_OPER_ATTRIBUTE_FIRST,
 116     /**
 117      * The path is resolved
 118      */
 119     FIB_PATH_OPER_ATTRIBUTE_RESOLVED,
 120     /**
 121      * The path is attached, despite what the next-hop may say.
 122      */
 123     FIB_PATH_OPER_ATTRIBUTE_ATTACHED,
 124     /**
 125      * The path has become a permanent drop.
 126      */
 127     FIB_PATH_OPER_ATTRIBUTE_DROP,
 128     /**
 129      * Marker. Add new types before this one, then update it.
 130      */
 131     FIB_PATH_OPER_ATTRIBUTE_LAST = FIB_PATH_OPER_ATTRIBUTE_DROP,
 132 } __attribute__ ((packed)) fib_path_oper_attribute_t;
 133
 134 /**
 135  * The maximum number of path operational attributes
 136  */
 137 #define FIB_PATH_OPER_ATTRIBUTE_MAX (FIB_PATH_OPER_ATTRIBUTE_LAST + 1)
 138
 139 #define FIB_PATH_OPER_ATTRIBUTES {                                      \
 140     [FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP] = "recursive-loop",        \
 141     [FIB_PATH_OPER_ATTRIBUTE_RESOLVED]       = "resolved",              \
 142     [FIB_PATH_OPER_ATTRIBUTE_DROP]           = "drop",                  \
 143 }
 144
 145 #define FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(_item) \
 146     for (_item = FIB_PATH_OPER_ATTRIBUTE_FIRST; \
 147          _item <= FIB_PATH_OPER_ATTRIBUTE_LAST; \
 148          _item++)
 149
 150 /**
 151  * Path flags from the attributes
 152  */
 153 typedef enum fib_path_oper_flags_t_ {
 154     FIB_PATH_OPER_FLAG_NONE = 0,
 155     FIB_PATH_OPER_FLAG_RECURSIVE_LOOP = (1 << FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP),
 156     FIB_PATH_OPER_FLAG_DROP = (1 << FIB_PATH_OPER_ATTRIBUTE_DROP),
 157     FIB_PATH_OPER_FLAG_RESOLVED = (1 << FIB_PATH_OPER_ATTRIBUTE_RESOLVED),
 158     FIB_PATH_OPER_FLAG_ATTACHED = (1 << FIB_PATH_OPER_ATTRIBUTE_ATTACHED),
 159 } __attribute__ ((packed)) fib_path_oper_flags_t;
 160
 161 /**
 162  * A FIB path
 163  */
 164 typedef struct fib_path_t_ {
 165     /**
 166      * A path is a node in the FIB graph.
 167      */
 168     fib_node_t fp_node;
 169
 170     /**
 171      * The index of the path-list to which this path belongs
 172      */
 173     u32 fp_pl_index;
 174
 175     /**
 176      * This marks the start of the memory area used to hash
 177      * the path
 178      */
 179     STRUCT_MARK(path_hash_start);
 180
 181     /**
 182      * Configuration Flags
 183      */
 184     fib_path_cfg_flags_t fp_cfg_flags;
 185
 186     /**
 187      * The type of the path. This is the selector for the union
 188      */
 189     fib_path_type_t fp_type;
 190
 191     /**
 192      * The protocol of the next-hop, i.e. the address family of the
 193      * next-hop's address. We can't derive this from the address itself
 194      * since the address can be all zeros
 195      */
 196     fib_protocol_t fp_nh_proto;
 197
 198     /**
 199      * UCMP [unnormalised] weigt
 200      */
 201     u32 fp_weight;
 202
 203     /**
 204      * per-type union of the data required to resolve the path
 205      */
 206     union {
 207         struct {
 208             /**
 209              * The next-hop
 210              */
 211             ip46_address_t fp_nh;
 212             /**
 213              * The interface
 214              */
 215             u32 fp_interface;
 216         } attached_next_hop;
 217         struct {
 218             /**
 219              * The interface
 220              */
 221             u32 fp_interface;
 222         } attached;
 223         struct {
 224             union
 225             {
 226                 /**
 227                  * The next-hop
 228                  */
 229                 ip46_address_t fp_ip;
 230                 struct {
 231                     /**
 232                      * The local label to resolve through.
 233                      */
 234                     mpls_label_t fp_local_label;
 235                     /**
 236                      * The EOS bit of the resolving label
 237                      */
 238                     mpls_eos_bit_t fp_eos;
 239                 };
 240             } fp_nh;
 241             /**
 242              * The FIB table index in which to find the next-hop.
 243              * This needs to be fixed. We should lookup the adjacencies in
 244              * a separate table of adjacencies, rather than from the FIB.
 245              * Two reasons I can think of:
 246              *   - consider:
 247              *       int ip addr Gig0 10.0.0.1/24
 248              *       ip route 10.0.0.2/32 via Gig1 192.168.1.2
 249              *       ip route 1.1.1.1/32 via Gig0 10.0.0.2
 250              *     this is perfectly valid.
 251              *     Packets addressed to 10.0.0.2 should be sent via Gig1.
 252              *     Packets address to 1.1.1.1 should be sent via Gig0.
 253              *    when we perform the adj resolution from the FIB for the path
 254              *    "via Gig0 10.0.0.2" the lookup will result in the route via Gig1
 255              *    and so we will pick up the adj via Gig1 - which was not what the
 256              *    operator wanted.
 257              *  - we can only return link-type IPv4 and so not the link-type MPLS.
 258              *    more on this in a later commit.
 259              *
 260              * The table ID should only belong to a recursive path and indicate
 261              * which FIB should be used to resolve the next-hop.
 262              */
 263             fib_node_index_t fp_tbl_id;
 264         } recursive;
 265         struct {
 266             /**
 267              * The FIB index in which to perfom the next lookup
 268              */
 269             fib_node_index_t fp_tbl_id;
 270             /**
 271              * The RPF-ID to tag the packets with
 272              */
 273             fib_rpf_id_t fp_rpf_id;
 274         } deag;
 275         struct {
 276         } special;
 277         struct {
 278             /**
 279              * The user provided 'exclusive' DPO
 280              */
 281             dpo_id_t fp_ex_dpo;
 282         } exclusive;
 283         struct {
 284             /**
 285              * The interface on which the local address is configured
 286              */
 287             u32 fp_interface;
 288             /**
 289              * The next-hop
 290              */
 291             ip46_address_t fp_addr;
 292         } receive;
 293         struct {
 294             /**
 295              * The interface on which the packets will be input.
 296              */
 297             u32 fp_interface;
 298         } intf_rx;
 299     };
 300     STRUCT_MARK(path_hash_end);
 301
 302     /**
 303      * Memebers in this last section represent information that is
 304      * dervied during resolution. It should not be copied to new paths
 305      * nor compared.
 306      */
 307
 308     /**
 309      * Operational Flags
 310      */
 311     fib_path_oper_flags_t fp_oper_flags;
 312
 313     /**
 314      * the resolving via fib. not part of the union, since it it not part
 315      * of the path's hash.
 316      */
 317     fib_node_index_t fp_via_fib;
 318
 319     /**
 320      * The Data-path objects through which this path resolves for IP.
 321      */
 322     dpo_id_t fp_dpo;
 323
 324     /**
 325      * the index of this path in the parent's child list.
 326      */
 327     u32 fp_sibling;
 328 } fib_path_t;
 329
 330 /*
 331  * Array of strings/names for the path types and attributes
 332  */
 333 static const char *fib_path_type_names[] = FIB_PATH_TYPES;
 334 static const char *fib_path_oper_attribute_names[] = FIB_PATH_OPER_ATTRIBUTES;
 335 static const char *fib_path_cfg_attribute_names[]  = FIB_PATH_CFG_ATTRIBUTES;
 336
 337 /*
 338  * The memory pool from which we allocate all the paths
 339  */
 340 static fib_path_t *fib_path_pool;
 341
 342 /*
 343  * Debug macro
 344  */
 345 #ifdef FIB_DEBUG
 346 #define FIB_PATH_DBG(_p, _fmt, _args...)                        \
 347 {                                                               \
 348     u8 *_tmp = NULL;                                            \
 349     _tmp = fib_path_format(fib_path_get_index(_p), _tmp);       \
 350     clib_warning("path:[%d:%s]:" _fmt,                          \
 351                  fib_path_get_index(_p), _tmp,                  \
 352                  ##_args);                                      \
 353     vec_free(_tmp);                                             \
 354 }
 355 #else
 356 #define FIB_PATH_DBG(_p, _fmt, _args...)
 357 #endif
 358
 359 static fib_path_t *
 360 fib_path_get (fib_node_index_t index)
 361 {
 362     return (pool_elt_at_index(fib_path_pool, index));
 363 }
 364
 365 static fib_node_index_t
 366 fib_path_get_index (fib_path_t *path)
 367 {
 368     return (path - fib_path_pool);
 369 }
 370
 371 static fib_node_t *
 372 fib_path_get_node (fib_node_index_t index)
 373 {
 374     return ((fib_node_t*)fib_path_get(index));
 375 }
 376
 377 static fib_path_t*
 378 fib_path_from_fib_node (fib_node_t *node)
 379 {
 380 #if CLIB_DEBUG > 0
 381     ASSERT(FIB_NODE_TYPE_PATH == node->fn_type);
 382 #endif
 383     return ((fib_path_t*)node);
 384 }
 385
 386 u8 *
 387 format_fib_path (u8 * s, va_list * args)
 388 {
 389     fib_path_t *path = va_arg (*args, fib_path_t *);
 390     vnet_main_t * vnm = vnet_get_main();
 391     fib_path_oper_attribute_t oattr;
 392     fib_path_cfg_attribute_t cattr;
 393
 394     s = format (s, "      index:%d ", fib_path_get_index(path));
 395     s = format (s, "pl-index:%d ", path->fp_pl_index);
 396     s = format (s, "%U ", format_fib_protocol, path->fp_nh_proto);
 397     s = format (s, "weight=%d ", path->fp_weight);
 398     s = format (s, "%s: ", fib_path_type_names[path->fp_type]);
 399     if (FIB_PATH_OPER_FLAG_NONE != path->fp_oper_flags) {
 400         s = format(s, " oper-flags:");
 401         FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(oattr) {
 402             if ((1<<oattr) & path->fp_oper_flags) {
 403                 s = format (s, "%s,", fib_path_oper_attribute_names[oattr]);
 404             }
 405         }
 406     }
 407     if (FIB_PATH_CFG_FLAG_NONE != path->fp_cfg_flags) {
 408         s = format(s, " cfg-flags:");
 409         FOR_EACH_FIB_PATH_CFG_ATTRIBUTE(cattr) {
 410             if ((1<<cattr) & path->fp_cfg_flags) {
 411                 s = format (s, "%s,", fib_path_cfg_attribute_names[cattr]);
 412             }
 413         }
 414     }
 415     s = format(s, "\n       ");
 416
 417     switch (path->fp_type)
 418     {
 419     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
 420         s = format (s, "%U", format_ip46_address,
 421                     &path->attached_next_hop.fp_nh,
 422                     IP46_TYPE_ANY);
 423         if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
 424         {
 425             s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
 426         }
 427         else
 428         {
 429             s = format (s, " %U",
 430                         format_vnet_sw_interface_name,
 431                         vnm,
 432                         vnet_get_sw_interface(
 433                             vnm,
 434                             path->attached_next_hop.fp_interface));
 435             if (vnet_sw_interface_is_p2p(vnet_get_main(),
 436                                          path->attached_next_hop.fp_interface))
 437             {
 438                 s = format (s, " (p2p)");
 439             }
 440         }
 441         if (!dpo_id_is_valid(&path->fp_dpo))
 442         {
 443             s = format(s, "\n          unresolved");
 444         }
 445         else
 446         {
 447             s = format(s, "\n          %U",
 448                        format_dpo_id,
 449                        &path->fp_dpo, 13);
 450         }
 451         break;
 452     case FIB_PATH_TYPE_ATTACHED:
 453         if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
 454         {
 455             s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
 456         }
 457         else
 458         {
 459             s = format (s, " %U",
 460                         format_vnet_sw_interface_name,
 461                         vnm,
 462                         vnet_get_sw_interface(
 463                             vnm,
 464                             path->attached.fp_interface));
 465         }
 466         break;
 467     case FIB_PATH_TYPE_RECURSIVE:
 468         if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
 469         {
 470             s = format (s, "via %U %U",
 471                         format_mpls_unicast_label,
 472                         path->recursive.fp_nh.fp_local_label,
 473                         format_mpls_eos_bit,
 474                         path->recursive.fp_nh.fp_eos);
 475         }
 476         else
 477         {
 478             s = format (s, "via %U",
 479                         format_ip46_address,
 480                         &path->recursive.fp_nh.fp_ip,
 481                         IP46_TYPE_ANY);
 482         }
 483         s = format (s, " in fib:%d",
 484                     path->recursive.fp_tbl_id,
 485                     path->fp_via_fib);
 486         s = format (s, " via-fib:%d", path->fp_via_fib);
 487         s = format (s, " via-dpo:[%U:%d]",
 488                     format_dpo_type, path->fp_dpo.dpoi_type,
 489                     path->fp_dpo.dpoi_index);
 490
 491         break;
 492     case FIB_PATH_TYPE_RECEIVE:
 493     case FIB_PATH_TYPE_INTF_RX:
 494     case FIB_PATH_TYPE_SPECIAL:
 495     case FIB_PATH_TYPE_DEAG:
 496     case FIB_PATH_TYPE_EXCLUSIVE:
 497         if (dpo_id_is_valid(&path->fp_dpo))
 498         {
 499             s = format(s, "%U", format_dpo_id,
 500                        &path->fp_dpo, 2);
 501         }
 502         break;
 503     }
 504     return (s);
 505 }
 506
 507 u8 *
 508 fib_path_format (fib_node_index_t pi, u8 *s)
 509 {
 510     fib_path_t *path;
 511
 512     path = fib_path_get(pi);
 513     ASSERT(NULL != path);
 514
 515     return (format (s, "%U", format_fib_path, path));
 516 }
 517
 518 u8 *
 519 fib_path_adj_format (fib_node_index_t pi,
 520                      u32 indent,
 521                      u8 *s)
 522 {
 523     fib_path_t *path;
 524
 525     path = fib_path_get(pi);
 526     ASSERT(NULL != path);
 527
 528     if (!dpo_id_is_valid(&path->fp_dpo))
 529     {
 530         s = format(s, " unresolved");
 531     }
 532     else
 533     {
 534         s = format(s, "%U", format_dpo_id,
 535                    &path->fp_dpo, 2);
 536     }
 537
 538     return (s);
 539 }
 540
 541 /*
 542  * fib_path_last_lock_gone
 543  *
 544  * We don't share paths, we share path lists, so the [un]lock functions
 545  * are no-ops
 546  */
 547 static void
 548 fib_path_last_lock_gone (fib_node_t *node)
 549 {
 550     ASSERT(0);
 551 }
 552
 553 static const adj_index_t
 554 fib_path_attached_next_hop_get_adj (fib_path_t *path,
 555                                     vnet_link_t link)
 556 {
 557     if (vnet_sw_interface_is_p2p(vnet_get_main(),
 558                                  path->attached_next_hop.fp_interface))
 559     {
 560         /*
 561          * if the interface is p2p then the adj for the specific
 562          * neighbour on that link will never exist. on p2p links
 563          * the subnet address (the attached route) links to the
 564          * auto-adj (see below), we want that adj here too.
 565          */
 566         return (adj_nbr_add_or_lock(path->fp_nh_proto,
 567                                     link,
 568                                     &zero_addr,
 569                                     path->attached_next_hop.fp_interface));
 570     }
 571     else
 572     {
 573         return (adj_nbr_add_or_lock(path->fp_nh_proto,
 574                                     link,
 575                                     &path->attached_next_hop.fp_nh,
 576                                     path->attached_next_hop.fp_interface));
 577     }
 578 }
 579
 580 static void
 581 fib_path_attached_next_hop_set (fib_path_t *path)
 582 {
 583     /*
 584      * resolve directly via the adjacnecy discribed by the
 585      * interface and next-hop
 586      */
 587     dpo_set(&path->fp_dpo,
 588             DPO_ADJACENCY,
 589             fib_proto_to_dpo(path->fp_nh_proto),
 590             fib_path_attached_next_hop_get_adj(
 591                  path,
 592                  fib_proto_to_link(path->fp_nh_proto)));
 593
 594     /*
 595      * become a child of the adjacency so we receive updates
 596      * when its rewrite changes
 597      */
 598     path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
 599                                      FIB_NODE_TYPE_PATH,
 600                                      fib_path_get_index(path));
 601
 602     if (!vnet_sw_interface_is_admin_up(vnet_get_main(),
 603                                       path->attached_next_hop.fp_interface) ||
 604         !adj_is_up(path->fp_dpo.dpoi_index))
 605     {
 606         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 607     }
 608 }
 609
 610 /*
 611  * create of update the paths recursive adj
 612  */
 613 static void
 614 fib_path_recursive_adj_update (fib_path_t *path,
 615                                fib_forward_chain_type_t fct,
 616                                dpo_id_t *dpo)
 617 {
 618     dpo_id_t via_dpo = DPO_INVALID;
 619
 620     /*
 621      * get the DPO to resolve through from the via-entry
 622      */
 623     fib_entry_contribute_forwarding(path->fp_via_fib,
 624                                     fct,
 625                                     &via_dpo);
 626
 627
 628     /*
 629      * hope for the best - clear if restrictions apply.
 630      */
 631     path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 632
 633     /*
 634      * Validate any recursion constraints and over-ride the via
 635      * adj if not met
 636      */
 637     if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP)
 638     {
 639         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 640         dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
 641     }
 642     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_HOST)
 643     {
 644         /*
 645          * the via FIB must be a host route.
 646          * note the via FIB just added will always be a host route
 647          * since it is an RR source added host route. So what we need to
 648          * check is whether the route has other sources. If it does then
 649          * some other source has added it as a host route. If it doesn't
 650          * then it was added only here and inherits forwarding from a cover.
 651          * the cover is not a host route.
 652          * The RR source is the lowest priority source, so we check if it
 653          * is the best. if it is there are no other sources.
 654          */
 655         if (fib_entry_get_best_source(path->fp_via_fib) >= FIB_SOURCE_RR)
 656         {
 657             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 658             dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
 659
 660             /*
 661              * PIC edge trigger. let the load-balance maps know
 662              */
 663             load_balance_map_path_state_change(fib_path_get_index(path));
 664         }
 665     }
 666     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED)
 667     {
 668         /*
 669          * RR source entries inherit the flags from the cover, so
 670          * we can check the via directly
 671          */
 672         if (!(FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags(path->fp_via_fib)))
 673         {
 674             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 675             dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
 676
 677             /*
 678              * PIC edge trigger. let the load-balance maps know
 679              */
 680             load_balance_map_path_state_change(fib_path_get_index(path));
 681         }
 682     }
 683     /*
 684      * check for over-riding factors on the FIB entry itself
 685      */
 686     if (!fib_entry_is_resolved(path->fp_via_fib))
 687     {
 688         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 689         dpo_copy(&via_dpo, drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
 690
 691         /*
 692          * PIC edge trigger. let the load-balance maps know
 693          */
 694         load_balance_map_path_state_change(fib_path_get_index(path));
 695     }
 696
 697     /*
 698      * update the path's contributed DPO
 699      */
 700     dpo_copy(dpo, &via_dpo);
 701
 702     FIB_PATH_DBG(path, "recursive update: %U",
 703                  fib_get_lookup_main(path->fp_nh_proto),
 704                  &path->fp_dpo, 2);
 705
 706     dpo_reset(&via_dpo);
 707 }
 708
 709 /*
 710  * fib_path_is_permanent_drop
 711  *
 712  * Return !0 if the path is configured to permanently drop,
 713  * despite other attributes.
 714  */
 715 static int
 716 fib_path_is_permanent_drop (fib_path_t *path)
 717 {
 718     return ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DROP) ||
 719             (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP));
 720 }
 721
 722 /*
 723  * fib_path_unresolve
 724  *
 725  * Remove our dependency on the resolution target
 726  */
 727 static void
 728 fib_path_unresolve (fib_path_t *path)
 729 {
 730     /*
 731      * the forced drop path does not need unresolving
 732      */
 733     if (fib_path_is_permanent_drop(path))
 734     {
 735         return;
 736     }
 737
 738     switch (path->fp_type)
 739     {
 740     case FIB_PATH_TYPE_RECURSIVE:
 741         if (FIB_NODE_INDEX_INVALID != path->fp_via_fib)
 742         {
 743             fib_prefix_t pfx;
 744
 745             fib_entry_get_prefix(path->fp_via_fib, &pfx);
 746             fib_entry_child_remove(path->fp_via_fib,
 747                                    path->fp_sibling);
 748             fib_table_entry_special_remove(path->recursive.fp_tbl_id,
 749                                            &pfx,
 750                                            FIB_SOURCE_RR);
 751             path->fp_via_fib = FIB_NODE_INDEX_INVALID;
 752         }
 753         break;
 754     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
 755     case FIB_PATH_TYPE_ATTACHED:
 756         adj_child_remove(path->fp_dpo.dpoi_index,
 757                          path->fp_sibling);
 758         adj_unlock(path->fp_dpo.dpoi_index);
 759         break;
 760     case FIB_PATH_TYPE_EXCLUSIVE:
 761         dpo_reset(&path->exclusive.fp_ex_dpo);
 762         break;
 763     case FIB_PATH_TYPE_SPECIAL:
 764     case FIB_PATH_TYPE_RECEIVE:
 765     case FIB_PATH_TYPE_INTF_RX:
 766     case FIB_PATH_TYPE_DEAG:
 767         /*
 768          * these hold only the path's DPO, which is reset below.
 769          */
 770         break;
 771     }
 772
 773     /*
 774      * release the adj we were holding and pick up the
 775      * drop just in case.
 776      */
 777     dpo_reset(&path->fp_dpo);
 778     path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 779
 780     return;
 781 }
 782
 783 static fib_forward_chain_type_t
 784 fib_path_to_chain_type (const fib_path_t *path)
 785 {
 786     switch (path->fp_nh_proto)
 787     {
 788     case FIB_PROTOCOL_IP4:
 789         return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
 790     case FIB_PROTOCOL_IP6:
 791         return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
 792     case FIB_PROTOCOL_MPLS:
 793         if (FIB_PATH_TYPE_RECURSIVE == path->fp_type &&
 794             MPLS_EOS == path->recursive.fp_nh.fp_eos)
 795         {
 796             return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
 797         }
 798         else
 799         {
 800             return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
 801         }
 802     }
 803     return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
 804 }
 805
 806 /*
 807  * fib_path_back_walk_notify
 808  *
 809  * A back walk has reach this path.
 810  */
 811 static fib_node_back_walk_rc_t
 812 fib_path_back_walk_notify (fib_node_t *node,
 813                            fib_node_back_walk_ctx_t *ctx)
 814 {
 815     fib_path_t *path;
 816
 817     path = fib_path_from_fib_node(node);
 818
 819     switch (path->fp_type)
 820     {
 821     case FIB_PATH_TYPE_RECURSIVE:
 822         if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason)
 823         {
 824             /*
 825              * modify the recursive adjacency to use the new forwarding
 826              * of the via-fib.
 827              * this update is visible to packets in flight in the DP.
 828              */
 829             fib_path_recursive_adj_update(
 830                 path,
 831                 fib_path_to_chain_type(path),
 832                 &path->fp_dpo);
 833         }
 834         if ((FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason) ||
 835             (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN   & ctx->fnbw_reason))
 836         {
 837             /*
 838              * ADJ updates (complete<->incomplete) do not need to propagate to
 839              * recursive entries.
 840              * The only reason its needed as far back as here, is that the adj
 841              * and the incomplete adj are a different DPO type, so the LBs need
 842              * to re-stack.
 843              * If this walk was quashed in the fib_entry, then any non-fib_path
 844              * children (like tunnels that collapse out the LB when they stack)
 845              * would not see the update.
 846              */
 847             return (FIB_NODE_BACK_WALK_CONTINUE);
 848         }
 849         break;
 850     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
 851         /*
 852 FIXME comment
 853          * ADJ_UPDATE backwalk pass silently through here and up to
 854          * the path-list when the multipath adj collapse occurs.
 855          * The reason we do this is that the assumtption is that VPP
 856          * runs in an environment where the Control-Plane is remote
 857          * and hence reacts slowly to link up down. In order to remove
 858          * this down link from the ECMP set quickly, we back-walk.
 859          * VPP also has dedicated CPUs, so we are not stealing resources
 860          * from the CP to do so.
 861          */
 862         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
 863         {
 864             if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED)
 865             {
 866                 /*
 867                  * alreday resolved. no need to walk back again
 868                  */
 869                 return (FIB_NODE_BACK_WALK_CONTINUE);
 870             }
 871             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 872         }
 873         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
 874         {
 875             if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
 876             {
 877                 /*
 878                  * alreday unresolved. no need to walk back again
 879                  */
 880                 return (FIB_NODE_BACK_WALK_CONTINUE);
 881             }
 882             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 883         }
 884         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
 885         {
 886             /*
 887              * The interface this path resolves through has been deleted.
 888              * This will leave the path in a permanent drop state. The route
 889              * needs to be removed and readded (and hence the path-list deleted)
 890              * before it can forward again.
 891              */
 892             fib_path_unresolve(path);
 893             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
 894         }
 895         if (FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason)
 896         {
 897             /*
 898              * restack the DPO to pick up the correct DPO sub-type
 899              */
 900             uword if_is_up;
 901             adj_index_t ai;
 902
 903             if_is_up = vnet_sw_interface_is_admin_up(
 904                            vnet_get_main(),
 905                            path->attached_next_hop.fp_interface);
 906
 907             ai = fib_path_attached_next_hop_get_adj(
 908                      path,
 909                      fib_proto_to_link(path->fp_nh_proto));
 910
 911             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 912             if (if_is_up && adj_is_up(ai))
 913             {
 914                 path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 915             }
 916
 917             dpo_set(&path->fp_dpo, DPO_ADJACENCY,
 918                     fib_proto_to_dpo(path->fp_nh_proto),
 919                     ai);
 920             adj_unlock(ai);
 921
 922             if (!if_is_up)
 923             {
 924                 /*
 925                  * If the interface is not up there is no reason to walk
 926                  * back to children. if we did they would only evalute
 927                  * that this path is unresolved and hence it would
 928                  * not contribute the adjacency - so it would be wasted
 929                  * CPU time.
 930                  */
 931                 return (FIB_NODE_BACK_WALK_CONTINUE);
 932             }
 933         }
 934         if (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason)
 935         {
 936             if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
 937             {
 938                 /*
 939                  * alreday unresolved. no need to walk back again
 940                  */
 941                 return (FIB_NODE_BACK_WALK_CONTINUE);
 942             }
 943             /*
 944              * the adj has gone down. the path is no longer resolved.
 945              */
 946             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 947         }
 948         break;
 949     case FIB_PATH_TYPE_ATTACHED:
 950         /*
 951          * FIXME; this could schedule a lower priority walk, since attached
 952          * routes are not usually in ECMP configurations so the backwalk to
 953          * the FIB entry does not need to be high priority
 954          */
 955         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
 956         {
 957             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 958         }
 959         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
 960         {
 961             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 962         }
 963         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
 964         {
 965             fib_path_unresolve(path);
 966             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
 967         }
 968         break;
 969     case FIB_PATH_TYPE_INTF_RX:
 970         ASSERT(0);
 971     case FIB_PATH_TYPE_DEAG:
 972         /*
 973          * FIXME When VRF delete is allowed this will need a poke.
 974          */
 975     case FIB_PATH_TYPE_SPECIAL:
 976     case FIB_PATH_TYPE_RECEIVE:
 977     case FIB_PATH_TYPE_EXCLUSIVE:
 978         /*
 979          * these path types have no parents. so to be
 980          * walked from one is unexpected.
 981          */
 982         ASSERT(0);
 983         break;
 984     }
 985
 986     /*
 987      * propagate the backwalk further to the path-list
 988      */
 989     fib_path_list_back_walk(path->fp_pl_index, ctx);
 990
 991     return (FIB_NODE_BACK_WALK_CONTINUE);
 992 }
 993
 994 static void
 995 fib_path_memory_show (void)
 996 {
 997     fib_show_memory_usage("Path",
 998                           pool_elts(fib_path_pool),
 999                           pool_len(fib_path_pool),
1000                           sizeof(fib_path_t));
1001 }
1002
1003 /*
1004  * The FIB path's graph node virtual function table
1005  */
1006 static const fib_node_vft_t fib_path_vft = {
1007     .fnv_get = fib_path_get_node,
1008     .fnv_last_lock = fib_path_last_lock_gone,
1009     .fnv_back_walk = fib_path_back_walk_notify,
1010     .fnv_mem_show = fib_path_memory_show,
1011 };
1012
1013 static fib_path_cfg_flags_t
1014 fib_path_route_flags_to_cfg_flags (const fib_route_path_t *rpath)
1015 {
1016     fib_path_cfg_flags_t cfg_flags = FIB_PATH_CFG_FLAG_NONE;
1017
1018     if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_HOST)
1019         cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_HOST;
1020     if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_ATTACHED)
1021         cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED;
1022     if (rpath->frp_flags & FIB_ROUTE_PATH_LOCAL)
1023         cfg_flags |= FIB_PATH_CFG_FLAG_LOCAL;
1024     if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
1025         cfg_flags |= FIB_PATH_CFG_FLAG_ATTACHED;
1026     if (rpath->frp_flags & FIB_ROUTE_PATH_INTF_RX)
1027         cfg_flags |= FIB_PATH_CFG_FLAG_INTF_RX;
1028     if (rpath->frp_flags & FIB_ROUTE_PATH_RPF_ID)
1029         cfg_flags |= FIB_PATH_CFG_FLAG_RPF_ID;
1030     if (rpath->frp_flags & FIB_ROUTE_PATH_EXCLUSIVE)
1031         cfg_flags |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
1032     if (rpath->frp_flags & FIB_ROUTE_PATH_DROP)
1033         cfg_flags |= FIB_PATH_CFG_FLAG_DROP;
1034
1035     return (cfg_flags);
1036 }
1037
1038 /*
1039  * fib_path_create
1040  *
1041  * Create and initialise a new path object.
1042  * return the index of the path.
1043  */
1044 fib_node_index_t
1045 fib_path_create (fib_node_index_t pl_index,
1046                  const fib_route_path_t *rpath)
1047 {
1048     fib_path_t *path;
1049
1050     pool_get(fib_path_pool, path);
1051     memset(path, 0, sizeof(*path));
1052
1053     fib_node_init(&path->fp_node,
1054                   FIB_NODE_TYPE_PATH);
1055
1056     dpo_reset(&path->fp_dpo);
1057     path->fp_pl_index = pl_index;
1058     path->fp_nh_proto = rpath->frp_proto;
1059     path->fp_via_fib = FIB_NODE_INDEX_INVALID;
1060     path->fp_weight = rpath->frp_weight;
1061     if (0 == path->fp_weight)
1062     {
1063         /*
1064          * a weight of 0 is a meaningless value. We could either reject it, and thus force
1065          * clients to always use 1, or we can accept it and fixup approrpiately.
1066          */
1067         path->fp_weight = 1;
1068     }
1069     path->fp_cfg_flags = fib_path_route_flags_to_cfg_flags(rpath);
1070
1071     /*
1072      * deduce the path's tpye from the parementers and save what is needed.
1073      */
1074     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_LOCAL)
1075     {
1076         path->fp_type = FIB_PATH_TYPE_RECEIVE;
1077         path->receive.fp_interface = rpath->frp_sw_if_index;
1078         path->receive.fp_addr = rpath->frp_addr;
1079     }
1080     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_INTF_RX)
1081     {
1082         path->fp_type = FIB_PATH_TYPE_INTF_RX;
1083         path->intf_rx.fp_interface = rpath->frp_sw_if_index;
1084     }
1085     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID)
1086     {
1087         path->fp_type = FIB_PATH_TYPE_DEAG;
1088         path->deag.fp_tbl_id = rpath->frp_fib_index;
1089         path->deag.fp_rpf_id = rpath->frp_rpf_id;
1090     }
1091     else if (~0 != rpath->frp_sw_if_index)
1092     {
1093         if (ip46_address_is_zero(&rpath->frp_addr))
1094         {
1095             path->fp_type = FIB_PATH_TYPE_ATTACHED;
1096             path->attached.fp_interface = rpath->frp_sw_if_index;
1097         }
1098         else
1099         {
1100             path->fp_type = FIB_PATH_TYPE_ATTACHED_NEXT_HOP;
1101             path->attached_next_hop.fp_interface = rpath->frp_sw_if_index;
1102             path->attached_next_hop.fp_nh = rpath->frp_addr;
1103         }
1104     }
1105     else
1106     {
1107         if (ip46_address_is_zero(&rpath->frp_addr))
1108         {
1109             if (~0 == rpath->frp_fib_index)
1110             {
1111                 path->fp_type = FIB_PATH_TYPE_SPECIAL;
1112             }
1113             else
1114             {
1115                 path->fp_type = FIB_PATH_TYPE_DEAG;
1116                 path->deag.fp_tbl_id = rpath->frp_fib_index;
1117             }
1118         }
1119         else
1120         {
1121             path->fp_type = FIB_PATH_TYPE_RECURSIVE;
1122             if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
1123             {
1124                 path->recursive.fp_nh.fp_local_label = rpath->frp_local_label;
1125                 path->recursive.fp_nh.fp_eos = rpath->frp_eos;
1126             }
1127             else
1128             {
1129                 path->recursive.fp_nh.fp_ip = rpath->frp_addr;
1130             }
1131             path->recursive.fp_tbl_id = rpath->frp_fib_index;
1132         }
1133     }
1134
1135     FIB_PATH_DBG(path, "create");
1136
1137     return (fib_path_get_index(path));
1138 }
1139
1140 /*
1141  * fib_path_create_special
1142  *
1143  * Create and initialise a new path object.
1144  * return the index of the path.
1145  */
1146 fib_node_index_t
1147 fib_path_create_special (fib_node_index_t pl_index,
1148                          fib_protocol_t nh_proto,
1149                          fib_path_cfg_flags_t flags,
1150                          const dpo_id_t *dpo)
1151 {
1152     fib_path_t *path;
1153
1154     pool_get(fib_path_pool, path);
1155     memset(path, 0, sizeof(*path));
1156
1157     fib_node_init(&path->fp_node,
1158                   FIB_NODE_TYPE_PATH);
1159     dpo_reset(&path->fp_dpo);
1160
1161     path->fp_pl_index = pl_index;
1162     path->fp_weight = 1;
1163     path->fp_nh_proto = nh_proto;
1164     path->fp_via_fib = FIB_NODE_INDEX_INVALID;
1165     path->fp_cfg_flags = flags;
1166
1167     if (FIB_PATH_CFG_FLAG_DROP & flags)
1168     {
1169         path->fp_type = FIB_PATH_TYPE_SPECIAL;
1170     }
1171     else if (FIB_PATH_CFG_FLAG_LOCAL & flags)
1172     {
1173         path->fp_type = FIB_PATH_TYPE_RECEIVE;
1174         path->attached.fp_interface = FIB_NODE_INDEX_INVALID;
1175     }
1176     else
1177     {
1178         path->fp_type = FIB_PATH_TYPE_EXCLUSIVE;
1179         ASSERT(NULL != dpo);
1180         dpo_copy(&path->exclusive.fp_ex_dpo, dpo);
1181     }
1182
1183     return (fib_path_get_index(path));
1184 }
1185
1186 /*
1187  * fib_path_copy
1188  *
1189  * Copy a path. return index of new path.
1190  */
1191 fib_node_index_t
1192 fib_path_copy (fib_node_index_t path_index,
1193                fib_node_index_t path_list_index)
1194 {
1195     fib_path_t *path, *orig_path;
1196
1197     pool_get(fib_path_pool, path);
1198
1199     orig_path = fib_path_get(path_index);
1200     ASSERT(NULL != orig_path);
1201
1202     memcpy(path, orig_path, sizeof(*path));
1203
1204     FIB_PATH_DBG(path, "create-copy:%d", path_index);
1205
1206     /*
1207      * reset the dynamic section
1208      */
1209     fib_node_init(&path->fp_node, FIB_NODE_TYPE_PATH);
1210     path->fp_oper_flags     = FIB_PATH_OPER_FLAG_NONE;
1211     path->fp_pl_index  = path_list_index;
1212     path->fp_via_fib   = FIB_NODE_INDEX_INVALID;
1213     memset(&path->fp_dpo, 0, sizeof(path->fp_dpo));
1214     dpo_reset(&path->fp_dpo);
1215
1216     return (fib_path_get_index(path));
1217 }
1218
1219 /*
1220  * fib_path_destroy
1221  *
1222  * destroy a path that is no longer required
1223  */
1224 void
1225 fib_path_destroy (fib_node_index_t path_index)
1226 {
1227     fib_path_t *path;
1228
1229     path = fib_path_get(path_index);
1230
1231     ASSERT(NULL != path);
1232     FIB_PATH_DBG(path, "destroy");
1233
1234     fib_path_unresolve(path);
1235
1236     fib_node_deinit(&path->fp_node);
1237     pool_put(fib_path_pool, path);
1238 }
1239
1240 /*
1241  * fib_path_destroy
1242  *
1243  * destroy a path that is no longer required
1244  */
1245 uword
1246 fib_path_hash (fib_node_index_t path_index)
1247 {
1248     fib_path_t *path;
1249
1250     path = fib_path_get(path_index);
1251
1252     return (hash_memory(STRUCT_MARK_PTR(path, path_hash_start),
1253                         (STRUCT_OFFSET_OF(fib_path_t, path_hash_end) -
1254                          STRUCT_OFFSET_OF(fib_path_t, path_hash_start)),
1255                         0));
1256 }
1257
1258 /*
1259  * fib_path_cmp_i
1260  *
1261  * Compare two paths for equivalence.
1262  */
1263 static int
1264 fib_path_cmp_i (const fib_path_t *path1,
1265                 const fib_path_t *path2)
1266 {
1267     int res;
1268
1269     res = 1;
1270
1271     /*
1272      * paths of different types and protocol are not equal.
1273      * different weights only are the same path.
1274      */
1275     if (path1->fp_type != path2->fp_type)
1276     {
1277         res = (path1->fp_type - path2->fp_type);
1278     }
1279     else if (path1->fp_nh_proto != path2->fp_nh_proto)
1280     {
1281         res = (path1->fp_nh_proto - path2->fp_nh_proto);
1282     }
1283     else
1284     {
1285         /*
1286          * both paths are of the same type.
1287          * consider each type and its attributes in turn.
1288          */
1289         switch (path1->fp_type)
1290         {
1291         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1292             res = ip46_address_cmp(&path1->attached_next_hop.fp_nh,
1293                                    &path2->attached_next_hop.fp_nh);
1294             if (0 == res) {
1295                 res = (path1->attached_next_hop.fp_interface -
1296                        path2->attached_next_hop.fp_interface);
1297             }
1298             break;
1299         case FIB_PATH_TYPE_ATTACHED:
1300             res = (path1->attached.fp_interface -
1301                    path2->attached.fp_interface);
1302             break;
1303         case FIB_PATH_TYPE_RECURSIVE:
1304             res = ip46_address_cmp(&path1->recursive.fp_nh,
1305                                    &path2->recursive.fp_nh);
1306
1307             if (0 == res)
1308             {
1309                 res = (path1->recursive.fp_tbl_id - path2->recursive.fp_tbl_id);
1310             }
1311             break;
1312         case FIB_PATH_TYPE_DEAG:
1313             res = (path1->deag.fp_tbl_id - path2->deag.fp_tbl_id);
1314             if (0 == res)
1315             {
1316                 res = (path1->deag.fp_rpf_id - path2->deag.fp_rpf_id);
1317             }
1318             break;
1319         case FIB_PATH_TYPE_INTF_RX:
1320             res = (path1->intf_rx.fp_interface - path2->intf_rx.fp_interface);
1321             break;
1322         case FIB_PATH_TYPE_SPECIAL:
1323         case FIB_PATH_TYPE_RECEIVE:
1324         case FIB_PATH_TYPE_EXCLUSIVE:
1325             res = 0;
1326             break;
1327         }
1328     }
1329     return (res);
1330 }
1331
1332 /*
1333  * fib_path_cmp_for_sort
1334  *
1335  * Compare two paths for equivalence. Used during path sorting.
1336  * As usual 0 means equal.
1337  */
1338 int
1339 fib_path_cmp_for_sort (void * v1,
1340                        void * v2)
1341 {
1342     fib_node_index_t *pi1 = v1, *pi2 = v2;
1343     fib_path_t *path1, *path2;
1344
1345     path1 = fib_path_get(*pi1);
1346     path2 = fib_path_get(*pi2);
1347
1348     return (fib_path_cmp_i(path1, path2));
1349 }
1350
1351 /*
1352  * fib_path_cmp
1353  *
1354  * Compare two paths for equivalence.
1355  */
1356 int
1357 fib_path_cmp (fib_node_index_t pi1,
1358               fib_node_index_t pi2)
1359 {
1360     fib_path_t *path1, *path2;
1361
1362     path1 = fib_path_get(pi1);
1363     path2 = fib_path_get(pi2);
1364
1365     return (fib_path_cmp_i(path1, path2));
1366 }
1367
1368 int
1369 fib_path_cmp_w_route_path (fib_node_index_t path_index,
1370                            const fib_route_path_t *rpath)
1371 {
1372     fib_path_t *path;
1373     int res;
1374
1375     path = fib_path_get(path_index);
1376
1377     res = 1;
1378
1379     if (path->fp_weight != rpath->frp_weight)
1380     {
1381         res = (path->fp_weight - rpath->frp_weight);
1382     }
1383     else
1384     {
1385         /*
1386          * both paths are of the same type.
1387          * consider each type and its attributes in turn.
1388          */
1389         switch (path->fp_type)
1390         {
1391         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1392             res = ip46_address_cmp(&path->attached_next_hop.fp_nh,
1393                                    &rpath->frp_addr);
1394             if (0 == res)
1395             {
1396                 res = (path->attached_next_hop.fp_interface -
1397                        rpath->frp_sw_if_index);
1398             }
1399             break;
1400         case FIB_PATH_TYPE_ATTACHED:
1401             res = (path->attached.fp_interface - rpath->frp_sw_if_index);
1402             break;
1403         case FIB_PATH_TYPE_RECURSIVE:
1404             if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
1405             {
1406                 res = path->recursive.fp_nh.fp_local_label - rpath->frp_local_label;
1407
1408                 if (res == 0)
1409                 {
1410                     res = path->recursive.fp_nh.fp_eos - rpath->frp_eos;
1411                 }
1412             }
1413             else
1414             {
1415                 res = ip46_address_cmp(&path->recursive.fp_nh.fp_ip,
1416                                        &rpath->frp_addr);
1417             }
1418
1419             if (0 == res)
1420             {
1421                 res = (path->recursive.fp_tbl_id - rpath->frp_fib_index);
1422             }
1423             break;
1424         case FIB_PATH_TYPE_INTF_RX:
1425             res = (path->intf_rx.fp_interface - rpath->frp_sw_if_index);
1426             break;
1427         case FIB_PATH_TYPE_DEAG:
1428             res = (path->deag.fp_tbl_id - rpath->frp_fib_index);
1429             if (0 == res)
1430             {
1431                 res = (path->deag.fp_rpf_id - rpath->frp_rpf_id);
1432             }
1433             break;
1434         case FIB_PATH_TYPE_SPECIAL:
1435         case FIB_PATH_TYPE_RECEIVE:
1436         case FIB_PATH_TYPE_EXCLUSIVE:
1437             res = 0;
1438             break;
1439         }
1440     }
1441     return (res);
1442 }
1443
1444 /*
1445  * fib_path_recursive_loop_detect
1446  *
1447  * A forward walk of the FIB object graph to detect for a cycle/loop. This
1448  * walk is initiated when an entry is linking to a new path list or from an old.
1449  * The entry vector passed contains all the FIB entrys that are children of this
1450  * path (it is all the entries encountered on the walk so far). If this vector
1451  * contains the entry this path resolve via, then a loop is about to form.
1452  * The loop must be allowed to form, since we need the dependencies in place
1453  * so that we can track when the loop breaks.
1454  * However, we MUST not produce a loop in the forwarding graph (else packets
1455  * would loop around the switch path until the loop breaks), so we mark recursive
1456  * paths as looped so that they do not contribute forwarding information.
1457  * By marking the path as looped, an etry such as;
1458  *    X/Y
1459  *     via a.a.a.a (looped)
1460  *     via b.b.b.b (not looped)
1461  * can still forward using the info provided by b.b.b.b only
1462  */
1463 int
1464 fib_path_recursive_loop_detect (fib_node_index_t path_index,
1465                                 fib_node_index_t **entry_indicies)
1466 {
1467     fib_path_t *path;
1468
1469     path = fib_path_get(path_index);
1470
1471     /*
1472      * the forced drop path is never looped, cos it is never resolved.
1473      */
1474     if (fib_path_is_permanent_drop(path))
1475     {
1476         return (0);
1477     }
1478
1479     switch (path->fp_type)
1480     {
1481     case FIB_PATH_TYPE_RECURSIVE:
1482     {
1483         fib_node_index_t *entry_index, *entries;
1484         int looped = 0;
1485         entries = *entry_indicies;
1486
1487         vec_foreach(entry_index, entries) {
1488             if (*entry_index == path->fp_via_fib)
1489             {
1490                 /*
1491                  * the entry that is about to link to this path-list (or
1492                  * one of this path-list's children) is the same entry that
1493                  * this recursive path resolves through. this is a cycle.
1494                  * abort the walk.
1495                  */
1496                 looped = 1;
1497                 break;
1498             }
1499         }
1500
1501         if (looped)
1502         {
1503             FIB_PATH_DBG(path, "recursive loop formed");
1504             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1505
1506             dpo_copy(&path->fp_dpo,
1507                     drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
1508         }
1509         else
1510         {
1511             /*
1512              * no loop here yet. keep forward walking the graph.
1513              */
1514             if (fib_entry_recursive_loop_detect(path->fp_via_fib, entry_indicies))
1515             {
1516                 FIB_PATH_DBG(path, "recursive loop formed");
1517                 path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1518             }
1519             else
1520             {
1521                 FIB_PATH_DBG(path, "recursive loop cleared");
1522                 path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1523             }
1524         }
1525         break;
1526     }
1527     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1528     case FIB_PATH_TYPE_ATTACHED:
1529     case FIB_PATH_TYPE_SPECIAL:
1530     case FIB_PATH_TYPE_DEAG:
1531     case FIB_PATH_TYPE_RECEIVE:
1532     case FIB_PATH_TYPE_INTF_RX:
1533     case FIB_PATH_TYPE_EXCLUSIVE:
1534         /*
1535          * these path types cannot be part of a loop, since they are the leaves
1536          * of the graph.
1537          */
1538         break;
1539     }
1540
1541     return (fib_path_is_looped(path_index));
1542 }
1543
1544 int
1545 fib_path_resolve (fib_node_index_t path_index)
1546 {
1547     fib_path_t *path;
1548
1549     path = fib_path_get(path_index);
1550
1551     /*
1552      * hope for the best.
1553      */
1554     path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1555
1556     /*
1557      * the forced drop path resolves via the drop adj
1558      */
1559     if (fib_path_is_permanent_drop(path))
1560     {
1561         dpo_copy(&path->fp_dpo,
1562                  drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
1563         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1564         return (fib_path_is_resolved(path_index));
1565     }
1566
1567     switch (path->fp_type)
1568     {
1569     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1570         fib_path_attached_next_hop_set(path);
1571         break;
1572     case FIB_PATH_TYPE_ATTACHED:
1573         /*
1574          * path->attached.fp_interface
1575          */
1576         if (!vnet_sw_interface_is_admin_up(vnet_get_main(),
1577                                            path->attached.fp_interface))
1578         {
1579             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1580         }
1581         if (vnet_sw_interface_is_p2p(vnet_get_main(),
1582                                      path->attached.fp_interface))
1583         {
1584             /*
1585              * point-2-point interfaces do not require a glean, since
1586              * there is nothing to ARP. Install a rewrite/nbr adj instead
1587              */
1588             dpo_set(&path->fp_dpo,
1589                     DPO_ADJACENCY,
1590                     fib_proto_to_dpo(path->fp_nh_proto),
1591                     adj_nbr_add_or_lock(
1592                         path->fp_nh_proto,
1593                         fib_proto_to_link(path->fp_nh_proto),
1594                         &zero_addr,
1595                         path->attached.fp_interface));
1596         }
1597         else
1598         {
1599             dpo_set(&path->fp_dpo,
1600                     DPO_ADJACENCY_GLEAN,
1601                     fib_proto_to_dpo(path->fp_nh_proto),
1602                     adj_glean_add_or_lock(path->fp_nh_proto,
1603                                           path->attached.fp_interface,
1604                                           NULL));
1605         }
1606         /*
1607          * become a child of the adjacency so we receive updates
1608          * when the interface state changes
1609          */
1610         path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
1611                                          FIB_NODE_TYPE_PATH,
1612                                          fib_path_get_index(path));
1613
1614         break;
1615     case FIB_PATH_TYPE_RECURSIVE:
1616     {
1617         /*
1618          * Create a RR source entry in the table for the address
1619          * that this path recurses through.
1620          * This resolve action is recursive, hence we may create
1621          * more paths in the process. more creates mean maybe realloc
1622          * of this path.
1623          */
1624         fib_node_index_t fei;
1625         fib_prefix_t pfx;
1626
1627         ASSERT(FIB_NODE_INDEX_INVALID == path->fp_via_fib);
1628
1629         if (FIB_PROTOCOL_MPLS == path->fp_nh_proto)
1630         {
1631             fib_prefix_from_mpls_label(path->recursive.fp_nh.fp_local_label,
1632                                        path->recursive.fp_nh.fp_eos,
1633                                        &pfx);
1634         }
1635         else
1636         {
1637             fib_prefix_from_ip46_addr(&path->recursive.fp_nh.fp_ip, &pfx);
1638         }
1639
1640         fei = fib_table_entry_special_add(path->recursive.fp_tbl_id,
1641                                           &pfx,
1642                                           FIB_SOURCE_RR,
1643                                           FIB_ENTRY_FLAG_NONE,
1644                                           ADJ_INDEX_INVALID);
1645
1646         path = fib_path_get(path_index);
1647         path->fp_via_fib = fei;
1648
1649         /*
1650          * become a dependent child of the entry so the path is
1651          * informed when the forwarding for the entry changes.
1652          */
1653         path->fp_sibling = fib_entry_child_add(path->fp_via_fib,
1654                                                FIB_NODE_TYPE_PATH,
1655                                                fib_path_get_index(path));
1656
1657         /*
1658          * create and configure the IP DPO
1659          */
1660         fib_path_recursive_adj_update(
1661             path,
1662             fib_path_to_chain_type(path),
1663             &path->fp_dpo);
1664
1665         break;
1666     }
1667     case FIB_PATH_TYPE_SPECIAL:
1668         /*
1669          * Resolve via the drop
1670          */
1671         dpo_copy(&path->fp_dpo,
1672                  drop_dpo_get(fib_proto_to_dpo(path->fp_nh_proto)));
1673         break;
1674     case FIB_PATH_TYPE_DEAG:
1675     {
1676         /*
1677          * Resolve via a lookup DPO.
1678          * FIXME. control plane should add routes with a table ID
1679          */
1680         lookup_cast_t cast;
1681
1682         cast = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID ?
1683                 LOOKUP_MULTICAST :
1684                 LOOKUP_UNICAST);
1685
1686         lookup_dpo_add_or_lock_w_fib_index(path->deag.fp_tbl_id,
1687                                            fib_proto_to_dpo(path->fp_nh_proto),
1688                                            cast,
1689                                            LOOKUP_INPUT_DST_ADDR,
1690                                            LOOKUP_TABLE_FROM_CONFIG,
1691                                            &path->fp_dpo);
1692         break;
1693     }
1694     case FIB_PATH_TYPE_RECEIVE:
1695         /*
1696          * Resolve via a receive DPO.
1697          */
1698         receive_dpo_add_or_lock(fib_proto_to_dpo(path->fp_nh_proto),
1699                                 path->receive.fp_interface,
1700                                 &path->receive.fp_addr,
1701                                 &path->fp_dpo);
1702         break;
1703     case FIB_PATH_TYPE_INTF_RX: {
1704         /*
1705          * Resolve via a receive DPO.
1706          */
1707         interface_dpo_add_or_lock(fib_proto_to_dpo(path->fp_nh_proto),
1708                                   path->intf_rx.fp_interface,
1709                                   &path->fp_dpo);
1710         break;
1711     }
1712     case FIB_PATH_TYPE_EXCLUSIVE:
1713         /*
1714          * Resolve via the user provided DPO
1715          */
1716         dpo_copy(&path->fp_dpo, &path->exclusive.fp_ex_dpo);
1717         break;
1718     }
1719
1720     return (fib_path_is_resolved(path_index));
1721 }
1722
1723 u32
1724 fib_path_get_resolving_interface (fib_node_index_t path_index)
1725 {
1726     fib_path_t *path;
1727
1728     path = fib_path_get(path_index);
1729
1730     switch (path->fp_type)
1731     {
1732     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1733         return (path->attached_next_hop.fp_interface);
1734     case FIB_PATH_TYPE_ATTACHED:
1735         return (path->attached.fp_interface);
1736     case FIB_PATH_TYPE_RECEIVE:
1737         return (path->receive.fp_interface);
1738     case FIB_PATH_TYPE_RECURSIVE:
1739         return (fib_entry_get_resolving_interface(path->fp_via_fib));
1740     case FIB_PATH_TYPE_INTF_RX:
1741     case FIB_PATH_TYPE_SPECIAL:
1742     case FIB_PATH_TYPE_DEAG:
1743     case FIB_PATH_TYPE_EXCLUSIVE:
1744         break;
1745     }
1746     return (~0);
1747 }
1748
1749 adj_index_t
1750 fib_path_get_adj (fib_node_index_t path_index)
1751 {
1752     fib_path_t *path;
1753
1754     path = fib_path_get(path_index);
1755
1756     ASSERT(dpo_is_adj(&path->fp_dpo));
1757     if (dpo_is_adj(&path->fp_dpo))
1758     {
1759         return (path->fp_dpo.dpoi_index);
1760     }
1761     return (ADJ_INDEX_INVALID);
1762 }
1763
1764 int
1765 fib_path_get_weight (fib_node_index_t path_index)
1766 {
1767     fib_path_t *path;
1768
1769     path = fib_path_get(path_index);
1770
1771     ASSERT(path);
1772
1773     return (path->fp_weight);
1774 }
1775
1776 /**
1777  * @brief Contribute the path's adjacency to the list passed.
1778  * By calling this function over all paths, recursively, a child
1779  * can construct its full set of forwarding adjacencies, and hence its
1780  * uRPF list.
1781  */
1782 void
1783 fib_path_contribute_urpf (fib_node_index_t path_index,
1784                           index_t urpf)
1785 {
1786     fib_path_t *path;
1787
1788     path = fib_path_get(path_index);
1789
1790     /*
1791      * resolved and unresolved paths contribute to the RPF list.
1792      */
1793     switch (path->fp_type)
1794     {
1795     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1796         fib_urpf_list_append(urpf, path->attached_next_hop.fp_interface);
1797         break;
1798
1799     case FIB_PATH_TYPE_ATTACHED:
1800         fib_urpf_list_append(urpf, path->attached.fp_interface);
1801         break;
1802
1803     case FIB_PATH_TYPE_RECURSIVE:
1804         if (FIB_NODE_INDEX_INVALID != path->fp_via_fib)
1805         {
1806             /*
1807              * there's unresolved due to constraints, and there's unresolved
1808              * due to ain't go no via. can't do nowt w'out via.
1809              */
1810             fib_entry_contribute_urpf(path->fp_via_fib, urpf);
1811         }
1812         break;
1813
1814     case FIB_PATH_TYPE_EXCLUSIVE:
1815     case FIB_PATH_TYPE_SPECIAL:
1816         /*
1817          * these path types may link to an adj, if that's what
1818          * the clinet gave
1819          */
1820         if (dpo_is_adj(&path->fp_dpo))
1821         {
1822             ip_adjacency_t *adj;
1823
1824             adj = adj_get(path->fp_dpo.dpoi_index);
1825
1826             fib_urpf_list_append(urpf, adj->rewrite_header.sw_if_index);
1827         }
1828         break;
1829
1830     case FIB_PATH_TYPE_DEAG:
1831     case FIB_PATH_TYPE_RECEIVE:
1832     case FIB_PATH_TYPE_INTF_RX:
1833         /*
1834          * these path types don't link to an adj
1835          */
1836         break;
1837     }
1838 }
1839
1840 void
1841 fib_path_stack_mpls_disp (fib_node_index_t path_index,
1842                           dpo_proto_t payload_proto,
1843                           dpo_id_t *dpo)
1844 {
1845     fib_path_t *path;
1846
1847     path = fib_path_get(path_index);
1848
1849     ASSERT(path);
1850
1851     switch (path->fp_type)
1852     {
1853     case FIB_PATH_TYPE_DEAG:
1854     {
1855         dpo_id_t tmp = DPO_INVALID;
1856
1857         dpo_copy(&tmp, dpo);
1858         dpo_set(dpo,
1859                 DPO_MPLS_DISPOSITION,
1860                 payload_proto,
1861                 mpls_disp_dpo_create(payload_proto,
1862                                      path->deag.fp_rpf_id,
1863                                      &tmp));
1864         dpo_reset(&tmp);
1865         break;
1866     }
1867     case FIB_PATH_TYPE_RECEIVE:
1868     case FIB_PATH_TYPE_ATTACHED:
1869     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1870     case FIB_PATH_TYPE_RECURSIVE:
1871     case FIB_PATH_TYPE_INTF_RX:
1872     case FIB_PATH_TYPE_EXCLUSIVE:
1873     case FIB_PATH_TYPE_SPECIAL:
1874         break;
1875     }
1876 }
1877
1878 void
1879 fib_path_contribute_forwarding (fib_node_index_t path_index,
1880                                 fib_forward_chain_type_t fct,
1881                                 dpo_id_t *dpo)
1882 {
1883     fib_path_t *path;
1884
1885     path = fib_path_get(path_index);
1886
1887     ASSERT(path);
1888     ASSERT(FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct);
1889
1890     FIB_PATH_DBG(path, "contribute");
1891
1892     /*
1893      * The DPO stored in the path was created when the path was resolved.
1894      * This then represents the path's 'native' protocol; IP.
1895      * For all others will need to go find something else.
1896      */
1897     if (fib_path_to_chain_type(path) == fct)
1898     {
1899         dpo_copy(dpo, &path->fp_dpo);
1900     }
1901     else
1902     {
1903         switch (path->fp_type)
1904         {
1905         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1906             switch (fct)
1907             {
1908             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
1909             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
1910             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
1911             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
1912             case FIB_FORW_CHAIN_TYPE_ETHERNET:
1913             case FIB_FORW_CHAIN_TYPE_NSH:
1914             {
1915                 adj_index_t ai;
1916
1917                 /*
1918                  * get a appropriate link type adj.
1919                  */
1920                 ai = fib_path_attached_next_hop_get_adj(
1921                          path,
1922                          fib_forw_chain_type_to_link_type(fct));
1923                 dpo_set(dpo, DPO_ADJACENCY,
1924                         fib_forw_chain_type_to_dpo_proto(fct), ai);
1925                 adj_unlock(ai);
1926
1927                 break;
1928             }
1929             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
1930             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
1931             break;
1932             }
1933             break;
1934         case FIB_PATH_TYPE_RECURSIVE:
1935             switch (fct)
1936             {
1937             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
1938             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
1939             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
1940             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
1941             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
1942             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
1943                 fib_path_recursive_adj_update(path, fct, dpo);
1944                 break;
1945             case FIB_FORW_CHAIN_TYPE_ETHERNET:
1946             case FIB_FORW_CHAIN_TYPE_NSH:
1947                 ASSERT(0);
1948                 break;
1949             }
1950             break;
1951         case FIB_PATH_TYPE_DEAG:
1952             switch (fct)
1953             {
1954             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
1955                 lookup_dpo_add_or_lock_w_table_id(MPLS_FIB_DEFAULT_TABLE_ID,
1956                                                   DPO_PROTO_MPLS,
1957                                                   LOOKUP_UNICAST,
1958                                                   LOOKUP_INPUT_DST_ADDR,
1959                                                   LOOKUP_TABLE_FROM_CONFIG,
1960                                                   dpo);
1961                 break;
1962             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
1963             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
1964             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
1965                 dpo_copy(dpo, &path->fp_dpo);
1966                 break;
1967             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
1968             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
1969             case FIB_FORW_CHAIN_TYPE_ETHERNET:
1970             case FIB_FORW_CHAIN_TYPE_NSH:
1971                 ASSERT(0);
1972                 break;
1973             }
1974             break;
1975         case FIB_PATH_TYPE_EXCLUSIVE:
1976             dpo_copy(dpo, &path->exclusive.fp_ex_dpo);
1977             break;
1978         case FIB_PATH_TYPE_ATTACHED:
1979             switch (fct)
1980             {
1981             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
1982             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
1983             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
1984             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
1985             case FIB_FORW_CHAIN_TYPE_ETHERNET:
1986             case FIB_FORW_CHAIN_TYPE_NSH:
1987                 break;
1988             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
1989             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
1990                 {
1991                     adj_index_t ai;
1992
1993                     /*
1994                      * Create the adj needed for sending IP multicast traffic
1995                      */
1996                     ai = adj_mcast_add_or_lock(path->fp_nh_proto,
1997                                                fib_forw_chain_type_to_link_type(fct),
1998                                                path->attached.fp_interface);
1999                     dpo_set(dpo, DPO_ADJACENCY,
2000                             fib_forw_chain_type_to_dpo_proto(fct),
2001                             ai);
2002                     adj_unlock(ai);
2003                 }
2004                 break;
2005             }
2006             break;
2007         case FIB_PATH_TYPE_INTF_RX:
2008             /*
2009              * Create the adj needed for sending IP multicast traffic
2010              */
2011             interface_dpo_add_or_lock(fib_forw_chain_type_to_dpo_proto(fct),
2012                                       path->attached.fp_interface,
2013                                       dpo);
2014             break;
2015         case FIB_PATH_TYPE_RECEIVE:
2016         case FIB_PATH_TYPE_SPECIAL:
2017             dpo_copy(dpo, &path->fp_dpo);
2018             break;
2019         }
2020     }
2021 }
2022
2023 load_balance_path_t *
2024 fib_path_append_nh_for_multipath_hash (fib_node_index_t path_index,
2025                                        fib_forward_chain_type_t fct,
2026                                        load_balance_path_t *hash_key)
2027 {
2028     load_balance_path_t *mnh;
2029     fib_path_t *path;
2030
2031     path = fib_path_get(path_index);
2032
2033     ASSERT(path);
2034
2035     if (fib_path_is_resolved(path_index))
2036     {
2037         vec_add2(hash_key, mnh, 1);
2038
2039         mnh->path_weight = path->fp_weight;
2040         mnh->path_index = path_index;
2041         fib_path_contribute_forwarding(path_index, fct, &mnh->path_dpo);
2042     }
2043
2044     return (hash_key);
2045 }
2046
2047 int
2048 fib_path_is_recursive (fib_node_index_t path_index)
2049 {
2050     fib_path_t *path;
2051
2052     path = fib_path_get(path_index);
2053
2054     return (FIB_PATH_TYPE_RECURSIVE == path->fp_type);
2055 }
2056
2057 int
2058 fib_path_is_exclusive (fib_node_index_t path_index)
2059 {
2060     fib_path_t *path;
2061
2062     path = fib_path_get(path_index);
2063
2064     return (FIB_PATH_TYPE_EXCLUSIVE == path->fp_type);
2065 }
2066
2067 int
2068 fib_path_is_deag (fib_node_index_t path_index)
2069 {
2070     fib_path_t *path;
2071
2072     path = fib_path_get(path_index);
2073
2074     return (FIB_PATH_TYPE_DEAG == path->fp_type);
2075 }
2076
2077 int
2078 fib_path_is_resolved (fib_node_index_t path_index)
2079 {
2080     fib_path_t *path;
2081
2082     path = fib_path_get(path_index);
2083
2084     return (dpo_id_is_valid(&path->fp_dpo) &&
2085             (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED) &&
2086             !fib_path_is_looped(path_index) &&
2087             !fib_path_is_permanent_drop(path));
2088 }
2089
2090 int
2091 fib_path_is_looped (fib_node_index_t path_index)
2092 {
2093     fib_path_t *path;
2094
2095     path = fib_path_get(path_index);
2096
2097     return (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP);
2098 }
2099
2100 int
2101 fib_path_encode (fib_node_index_t path_list_index,
2102                  fib_node_index_t path_index,
2103                  void *ctx)
2104 {
2105     fib_route_path_encode_t **api_rpaths = ctx;
2106     fib_route_path_encode_t *api_rpath;
2107     fib_path_t *path;
2108
2109     path = fib_path_get(path_index);
2110     if (!path)
2111       return (0);
2112     vec_add2(*api_rpaths, api_rpath, 1);
2113     api_rpath->rpath.frp_weight = path->fp_weight;
2114     api_rpath->rpath.frp_proto = path->fp_nh_proto;
2115     api_rpath->rpath.frp_sw_if_index = ~0;
2116     api_rpath->dpo = path->exclusive.fp_ex_dpo;
2117     switch (path->fp_type)
2118       {
2119       case FIB_PATH_TYPE_RECEIVE:
2120         api_rpath->rpath.frp_addr = path->receive.fp_addr;
2121         api_rpath->rpath.frp_sw_if_index = path->receive.fp_interface;
2122         break;
2123       case FIB_PATH_TYPE_ATTACHED:
2124         api_rpath->rpath.frp_sw_if_index = path->attached.fp_interface;
2125         break;
2126       case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2127         api_rpath->rpath.frp_sw_if_index = path->attached_next_hop.fp_interface;
2128         api_rpath->rpath.frp_addr = path->attached_next_hop.fp_nh;
2129         break;
2130       case FIB_PATH_TYPE_SPECIAL:
2131         break;
2132       case FIB_PATH_TYPE_DEAG:
2133         break;
2134       case FIB_PATH_TYPE_RECURSIVE:
2135         api_rpath->rpath.frp_addr = path->recursive.fp_nh.fp_ip;
2136         break;
2137       default:
2138         break;
2139       }
2140     return (1);
2141 }
2142
2143 fib_protocol_t
2144 fib_path_get_proto (fib_node_index_t path_index)
2145 {
2146     fib_path_t *path;
2147
2148     path = fib_path_get(path_index);
2149
2150     return (path->fp_nh_proto);
2151 }
2152
2153 void
2154 fib_path_module_init (void)
2155 {
2156     fib_node_register_type (FIB_NODE_TYPE_PATH, &fib_path_vft);
2157 }
2158
2159 static clib_error_t *
2160 show_fib_path_command (vlib_main_t * vm,
2161                         unformat_input_t * input,
2162                         vlib_cli_command_t * cmd)
2163 {
2164     fib_node_index_t pi;
2165     fib_path_t *path;
2166
2167     if (unformat (input, "%d", &pi))
2168     {
2169         /*
2170          * show one in detail
2171          */
2172         if (!pool_is_free_index(fib_path_pool, pi))
2173         {
2174             path = fib_path_get(pi);
2175             u8 *s = fib_path_format(pi, NULL);
2176             s = format(s, "children:");
2177             s = fib_node_children_format(path->fp_node.fn_children, s);
2178             vlib_cli_output (vm, "%s", s);
2179             vec_free(s);
2180         }
2181         else
2182         {
2183             vlib_cli_output (vm, "path %d invalid", pi);
2184         }
2185     }
2186     else
2187     {
2188         vlib_cli_output (vm, "FIB Paths");
2189         pool_foreach(path, fib_path_pool,
2190         ({
2191             vlib_cli_output (vm, "%U", format_fib_path, path);
2192         }));
2193     }
2194
2195     return (NULL);
2196 }
2197
2198 VLIB_CLI_COMMAND (show_fib_path, static) = {
2199   .path = "show fib paths",
2200   .function = show_fib_path_command,
2201   .short_help = "show fib paths",
2202 };