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