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_rx_dpo.h>
  25 #include <vnet/dpo/mpls_disposition.h>
  26 #include <vnet/dpo/dvr_dpo.h>
  27 #include <vnet/dpo/ip_null_dpo.h>
  28 #include <vnet/dpo/classify_dpo.h>
  29 #include <vnet/dpo/pw_cw.h>
  30
  31 #include <vnet/adj/adj.h>
  32 #include <vnet/adj/adj_mcast.h>
  33
  34 #include <vnet/fib/fib_path.h>
  35 #include <vnet/fib/fib_node.h>
  36 #include <vnet/fib/fib_table.h>
  37 #include <vnet/fib/fib_entry.h>
  38 #include <vnet/fib/fib_path_list.h>
  39 #include <vnet/fib/fib_internal.h>
  40 #include <vnet/fib/fib_urpf_list.h>
  41 #include <vnet/fib/mpls_fib.h>
  42 #include <vnet/fib/fib_path_ext.h>
  43 #include <vnet/udp/udp_encap.h>
  44 #include <vnet/bier/bier_fmask.h>
  45 #include <vnet/bier/bier_table.h>
  46 #include <vnet/bier/bier_imp.h>
  47 #include <vnet/bier/bier_disp_table.h>
  48
  49 /**
  50  * Enurmeration of path types
  51  */
  52 typedef enum fib_path_type_t_ {
  53     /**
  54      * Marker. Add new types after this one.
  55      */
  56     FIB_PATH_TYPE_FIRST = 0,
  57     /**
  58      * Attached-nexthop. An interface and a nexthop are known.
  59      */
  60     FIB_PATH_TYPE_ATTACHED_NEXT_HOP = FIB_PATH_TYPE_FIRST,
  61     /**
  62      * attached. Only the interface is known.
  63      */
  64     FIB_PATH_TYPE_ATTACHED,
  65     /**
  66      * recursive. Only the next-hop is known.
  67      */
  68     FIB_PATH_TYPE_RECURSIVE,
  69     /**
  70      * special. nothing is known. so we drop.
  71      */
  72     FIB_PATH_TYPE_SPECIAL,
  73     /**
  74      * exclusive. user provided adj.
  75      */
  76     FIB_PATH_TYPE_EXCLUSIVE,
  77     /**
  78      * deag. Link to a lookup adj in the next table
  79      */
  80     FIB_PATH_TYPE_DEAG,
  81     /**
  82      * interface receive.
  83      */
  84     FIB_PATH_TYPE_INTF_RX,
  85     /**
  86      * Path resolves via a UDP encap object.
  87      */
  88     FIB_PATH_TYPE_UDP_ENCAP,
  89     /**
  90      * receive. it's for-us.
  91      */
  92     FIB_PATH_TYPE_RECEIVE,
  93     /**
  94      * bier-imp. it's via a BIER imposition.
  95      */
  96     FIB_PATH_TYPE_BIER_IMP,
  97     /**
  98      * bier-fmask. it's via a BIER ECMP-table.
  99      */
 100     FIB_PATH_TYPE_BIER_TABLE,
 101     /**
 102      * bier-fmask. it's via a BIER f-mask.
 103      */
 104     FIB_PATH_TYPE_BIER_FMASK,
 105     /**
 106      * via a DVR.
 107      */
 108     FIB_PATH_TYPE_DVR,
 109 } __attribute__ ((packed)) fib_path_type_t;
 110
 111 #define FIB_PATH_TYPES {                                        \
 112     [FIB_PATH_TYPE_ATTACHED_NEXT_HOP] = "attached-nexthop",     \
 113     [FIB_PATH_TYPE_ATTACHED]          = "attached",             \
 114     [FIB_PATH_TYPE_RECURSIVE]         = "recursive",            \
 115     [FIB_PATH_TYPE_SPECIAL]           = "special",              \
 116     [FIB_PATH_TYPE_EXCLUSIVE]         = "exclusive",            \
 117     [FIB_PATH_TYPE_DEAG]              = "deag",                 \
 118     [FIB_PATH_TYPE_INTF_RX]           = "intf-rx",              \
 119     [FIB_PATH_TYPE_UDP_ENCAP]         = "udp-encap",            \
 120     [FIB_PATH_TYPE_RECEIVE]           = "receive",              \
 121     [FIB_PATH_TYPE_BIER_IMP]          = "bier-imp",             \
 122     [FIB_PATH_TYPE_BIER_TABLE]        = "bier-table",           \
 123     [FIB_PATH_TYPE_BIER_FMASK]        = "bier-fmask",           \
 124     [FIB_PATH_TYPE_DVR]               = "dvr",                  \
 125 }
 126
 127 /**
 128  * Enurmeration of path operational (i.e. derived) attributes
 129  */
 130 typedef enum fib_path_oper_attribute_t_ {
 131     /**
 132      * Marker. Add new types after this one.
 133      */
 134     FIB_PATH_OPER_ATTRIBUTE_FIRST = 0,
 135     /**
 136      * The path forms part of a recursive loop.
 137      */
 138     FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP = FIB_PATH_OPER_ATTRIBUTE_FIRST,
 139     /**
 140      * The path is resolved
 141      */
 142     FIB_PATH_OPER_ATTRIBUTE_RESOLVED,
 143     /**
 144      * The path has become a permanent drop.
 145      */
 146     FIB_PATH_OPER_ATTRIBUTE_DROP,
 147     /**
 148      * Marker. Add new types before this one, then update it.
 149      */
 150     FIB_PATH_OPER_ATTRIBUTE_LAST = FIB_PATH_OPER_ATTRIBUTE_DROP,
 151 } __attribute__ ((packed)) fib_path_oper_attribute_t;
 152
 153 /**
 154  * The maximum number of path operational attributes
 155  */
 156 #define FIB_PATH_OPER_ATTRIBUTE_MAX (FIB_PATH_OPER_ATTRIBUTE_LAST + 1)
 157
 158 #define FIB_PATH_OPER_ATTRIBUTES {                                      \
 159     [FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP] = "recursive-loop",        \
 160     [FIB_PATH_OPER_ATTRIBUTE_RESOLVED]       = "resolved",              \
 161     [FIB_PATH_OPER_ATTRIBUTE_DROP]           = "drop",                  \
 162 }
 163
 164 #define FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(_item) \
 165     for (_item = FIB_PATH_OPER_ATTRIBUTE_FIRST; \
 166          _item <= FIB_PATH_OPER_ATTRIBUTE_LAST; \
 167          _item++)
 168
 169 /**
 170  * Path flags from the attributes
 171  */
 172 typedef enum fib_path_oper_flags_t_ {
 173     FIB_PATH_OPER_FLAG_NONE = 0,
 174     FIB_PATH_OPER_FLAG_RECURSIVE_LOOP = (1 << FIB_PATH_OPER_ATTRIBUTE_RECURSIVE_LOOP),
 175     FIB_PATH_OPER_FLAG_DROP = (1 << FIB_PATH_OPER_ATTRIBUTE_DROP),
 176     FIB_PATH_OPER_FLAG_RESOLVED = (1 << FIB_PATH_OPER_ATTRIBUTE_RESOLVED),
 177 } __attribute__ ((packed)) fib_path_oper_flags_t;
 178
 179 /**
 180  * A FIB path
 181  */
 182 typedef struct fib_path_t_ {
 183     /**
 184      * A path is a node in the FIB graph.
 185      */
 186     fib_node_t fp_node;
 187
 188     /**
 189      * The index of the path-list to which this path belongs
 190      */
 191     u32 fp_pl_index;
 192
 193     /**
 194      * This marks the start of the memory area used to hash
 195      * the path
 196      */
 197     STRUCT_MARK(path_hash_start);
 198
 199     /**
 200      * Configuration Flags
 201      */
 202     fib_path_cfg_flags_t fp_cfg_flags;
 203
 204     /**
 205      * The type of the path. This is the selector for the union
 206      */
 207     fib_path_type_t fp_type;
 208
 209     /**
 210      * The protocol of the next-hop, i.e. the address family of the
 211      * next-hop's address. We can't derive this from the address itself
 212      * since the address can be all zeros
 213      */
 214     dpo_proto_t fp_nh_proto;
 215
 216     /**
 217      * UCMP [unnormalised] weigth
 218      */
 219     u8 fp_weight;
 220
 221     /**
 222      * A path preference. 0 is the best.
 223      * Only paths of the best preference, that are 'up', are considered
 224      * for forwarding.
 225      */
 226     u8 fp_preference;
 227
 228     /**
 229      * per-type union of the data required to resolve the path
 230      */
 231     union {
 232         struct {
 233             /**
 234              * The next-hop
 235              */
 236             ip46_address_t fp_nh;
 237             /**
 238              * The interface
 239              */
 240             u32 fp_interface;
 241         } attached_next_hop;
 242         struct {
 243             /**
 244              * The Connected local address
 245              */
 246             fib_prefix_t fp_connected;
 247             /**
 248              * The interface
 249              */
 250             u32 fp_interface;
 251         } attached;
 252         struct {
 253             union
 254             {
 255                 /**
 256                  * The next-hop
 257                  */
 258                 ip46_address_t fp_ip;
 259                 struct {
 260                     /**
 261                      * The local label to resolve through.
 262                      */
 263                     mpls_label_t fp_local_label;
 264                     /**
 265                      * The EOS bit of the resolving label
 266                      */
 267                     mpls_eos_bit_t fp_eos;
 268                 };
 269             } fp_nh;
 270             /**
 271              * The FIB table index in which to find the next-hop.
 272              */
 273             fib_node_index_t fp_tbl_id;
 274         } recursive;
 275         struct {
 276             /**
 277              * BIER FMask ID
 278              */
 279             index_t fp_bier_fmask;
 280         } bier_fmask;
 281         struct {
 282             /**
 283              * The BIER table's ID
 284              */
 285             bier_table_id_t fp_bier_tbl;
 286         } bier_table;
 287         struct {
 288             /**
 289              * The BIER imposition object
 290              * this is part of the path's key, since the index_t
 291              * of an imposition object is the object's key.
 292              */
 293             index_t fp_bier_imp;
 294         } bier_imp;
 295         struct {
 296             /**
 297              * The FIB index in which to perfom the next lookup
 298              */
 299             fib_node_index_t fp_tbl_id;
 300             /**
 301              * The RPF-ID to tag the packets with
 302              */
 303             fib_rpf_id_t fp_rpf_id;
 304         } deag;
 305         struct {
 306         } special;
 307         struct {
 308             /**
 309              * The user provided 'exclusive' DPO
 310              */
 311             dpo_id_t fp_ex_dpo;
 312         } exclusive;
 313         struct {
 314             /**
 315              * The interface on which the local address is configured
 316              */
 317             u32 fp_interface;
 318             /**
 319              * The next-hop
 320              */
 321             ip46_address_t fp_addr;
 322         } receive;
 323         struct {
 324             /**
 325              * The interface on which the packets will be input.
 326              */
 327             u32 fp_interface;
 328         } intf_rx;
 329         struct {
 330             /**
 331              * The UDP Encap object this path resolves through
 332              */
 333             u32 fp_udp_encap_id;
 334         } udp_encap;
 335         struct {
 336             /**
 337              * The UDP Encap object this path resolves through
 338              */
 339             u32 fp_classify_table_id;
 340         } classify;
 341         struct {
 342             /**
 343              * The interface
 344              */
 345             u32 fp_interface;
 346         } dvr;
 347     };
 348     STRUCT_MARK(path_hash_end);
 349
 350     /**
 351      * Members in this last section represent information that is
 352      * dervied during resolution. It should not be copied to new paths
 353      * nor compared.
 354      */
 355
 356     /**
 357      * Operational Flags
 358      */
 359     fib_path_oper_flags_t fp_oper_flags;
 360
 361     union {
 362         /**
 363          * the resolving via fib. not part of the union, since it it not part
 364          * of the path's hash.
 365          */
 366         fib_node_index_t fp_via_fib;
 367         /**
 368          * the resolving bier-table
 369          */
 370         index_t fp_via_bier_tbl;
 371         /**
 372          * the resolving bier-fmask
 373          */
 374         index_t fp_via_bier_fmask;
 375     };
 376
 377     /**
 378      * The Data-path objects through which this path resolves for IP.
 379      */
 380     dpo_id_t fp_dpo;
 381
 382     /**
 383      * the index of this path in the parent's child list.
 384      */
 385     u32 fp_sibling;
 386 } fib_path_t;
 387
 388 /*
 389  * Array of strings/names for the path types and attributes
 390  */
 391 static const char *fib_path_type_names[] = FIB_PATH_TYPES;
 392 static const char *fib_path_oper_attribute_names[] = FIB_PATH_OPER_ATTRIBUTES;
 393 static const char *fib_path_cfg_attribute_names[]  = FIB_PATH_CFG_ATTRIBUTES;
 394
 395 /*
 396  * The memory pool from which we allocate all the paths
 397  */
 398 static fib_path_t *fib_path_pool;
 399
 400 /**
 401  * the logger
 402  */
 403 vlib_log_class_t fib_path_logger;
 404
 405 /*
 406  * Debug macro
 407  */
 408 #define FIB_PATH_DBG(_p, _fmt, _args...)                                \
 409 {                                                                       \
 410     vlib_log_debug (fib_path_logger,                                    \
 411                     "[%U]: " _fmt,                                      \
 412                     format_fib_path, fib_path_get_index(_p), 0,         \
 413                     FIB_PATH_FORMAT_FLAGS_ONE_LINE,                     \
 414                     ##_args);                                           \
 415 }
 416
 417 static fib_path_t *
 418 fib_path_get (fib_node_index_t index)
 419 {
 420     return (pool_elt_at_index(fib_path_pool, index));
 421 }
 422
 423 static fib_node_index_t
 424 fib_path_get_index (fib_path_t *path)
 425 {
 426     return (path - fib_path_pool);
 427 }
 428
 429 static fib_node_t *
 430 fib_path_get_node (fib_node_index_t index)
 431 {
 432     return ((fib_node_t*)fib_path_get(index));
 433 }
 434
 435 static fib_path_t*
 436 fib_path_from_fib_node (fib_node_t *node)
 437 {
 438     ASSERT(FIB_NODE_TYPE_PATH == node->fn_type);
 439     return ((fib_path_t*)node);
 440 }
 441
 442 u8 *
 443 format_fib_path (u8 * s, va_list * args)
 444 {
 445     fib_node_index_t path_index = va_arg (*args, fib_node_index_t);
 446     u32 indent = va_arg (*args, u32);
 447     fib_format_path_flags_t flags =  va_arg (*args, fib_format_path_flags_t);
 448     vnet_main_t * vnm = vnet_get_main();
 449     fib_path_oper_attribute_t oattr;
 450     fib_path_cfg_attribute_t cattr;
 451     fib_path_t *path;
 452     const char *eol;
 453
 454     if (flags & FIB_PATH_FORMAT_FLAGS_ONE_LINE)
 455     {
 456         eol = "";
 457     }
 458     else
 459     {
 460         eol = "\n";
 461     }
 462
 463     path = fib_path_get(path_index);
 464
 465     s = format (s, "%Upath:[%d] ", format_white_space, indent,
 466                 fib_path_get_index(path));
 467     s = format (s, "pl-index:%d ", path->fp_pl_index);
 468     s = format (s, "%U ", format_dpo_proto, path->fp_nh_proto);
 469     s = format (s, "weight=%d ", path->fp_weight);
 470     s = format (s, "pref=%d ", path->fp_preference);
 471     s = format (s, "%s: ", fib_path_type_names[path->fp_type]);
 472     if (FIB_PATH_OPER_FLAG_NONE != path->fp_oper_flags) {
 473         s = format(s, " oper-flags:");
 474         FOR_EACH_FIB_PATH_OPER_ATTRIBUTE(oattr) {
 475             if ((1<<oattr) & path->fp_oper_flags) {
 476                 s = format (s, "%s,", fib_path_oper_attribute_names[oattr]);
 477             }
 478         }
 479     }
 480     if (FIB_PATH_CFG_FLAG_NONE != path->fp_cfg_flags) {
 481         s = format(s, " cfg-flags:");
 482         FOR_EACH_FIB_PATH_CFG_ATTRIBUTE(cattr) {
 483             if ((1<<cattr) & path->fp_cfg_flags) {
 484                 s = format (s, "%s,", fib_path_cfg_attribute_names[cattr]);
 485             }
 486         }
 487     }
 488     if (!(flags & FIB_PATH_FORMAT_FLAGS_ONE_LINE))
 489         s = format(s, "\n%U", format_white_space, indent+2);
 490
 491     switch (path->fp_type)
 492     {
 493     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
 494         s = format (s, "%U", format_ip46_address,
 495                     &path->attached_next_hop.fp_nh,
 496                     IP46_TYPE_ANY);
 497         if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
 498         {
 499             s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
 500         }
 501         else
 502         {
 503             s = format (s, " %U",
 504                         format_vnet_sw_if_index_name,
 505                         vnm,
 506                         path->attached_next_hop.fp_interface);
 507             if (vnet_sw_interface_is_p2p(vnet_get_main(),
 508                                          path->attached_next_hop.fp_interface))
 509             {
 510                 s = format (s, " (p2p)");
 511             }
 512         }
 513         if (!dpo_id_is_valid(&path->fp_dpo))
 514         {
 515             s = format(s, "%s%Uunresolved", eol, format_white_space, indent+2);
 516         }
 517         else
 518         {
 519             s = format(s, "%s%U%U", eol,
 520                        format_white_space, indent,
 521                        format_dpo_id,
 522                        &path->fp_dpo, 13);
 523         }
 524         break;
 525     case FIB_PATH_TYPE_ATTACHED:
 526         if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
 527         {
 528             s = format (s, "if_index:%d", path->attached_next_hop.fp_interface);
 529         }
 530         else
 531         {
 532             s = format (s, " %U",
 533                         format_vnet_sw_if_index_name,
 534                         vnm, path->attached.fp_interface);
 535         }
 536         break;
 537     case FIB_PATH_TYPE_RECURSIVE:
 538         if (DPO_PROTO_MPLS == path->fp_nh_proto)
 539         {
 540             s = format (s, "via %U %U",
 541                         format_mpls_unicast_label,
 542                         path->recursive.fp_nh.fp_local_label,
 543                         format_mpls_eos_bit,
 544                         path->recursive.fp_nh.fp_eos);
 545         }
 546         else
 547         {
 548             s = format (s, "via %U",
 549                         format_ip46_address,
 550                         &path->recursive.fp_nh.fp_ip,
 551                         IP46_TYPE_ANY);
 552         }
 553         s = format (s, " in fib:%d",
 554                     path->recursive.fp_tbl_id,
 555                     path->fp_via_fib);
 556         s = format (s, " via-fib:%d", path->fp_via_fib);
 557         s = format (s, " via-dpo:[%U:%d]",
 558                     format_dpo_type, path->fp_dpo.dpoi_type,
 559                     path->fp_dpo.dpoi_index);
 560
 561         break;
 562     case FIB_PATH_TYPE_UDP_ENCAP:
 563         s = format (s, "UDP-encap ID:%d", path->udp_encap.fp_udp_encap_id);
 564         break;
 565     case FIB_PATH_TYPE_BIER_TABLE:
 566         s = format (s, "via bier-table:[%U}",
 567                     format_bier_table_id,
 568                     &path->bier_table.fp_bier_tbl);
 569         s = format (s, " via-dpo:[%U:%d]",
 570                     format_dpo_type, path->fp_dpo.dpoi_type,
 571                     path->fp_dpo.dpoi_index);
 572         break;
 573     case FIB_PATH_TYPE_BIER_FMASK:
 574         s = format (s, "via-fmask:%d", path->bier_fmask.fp_bier_fmask);
 575         s = format (s, " via-dpo:[%U:%d]",
 576                     format_dpo_type, path->fp_dpo.dpoi_type,
 577                     path->fp_dpo.dpoi_index);
 578         break;
 579     case FIB_PATH_TYPE_BIER_IMP:
 580         s = format (s, "via %U", format_bier_imp,
 581                     path->bier_imp.fp_bier_imp, 0, BIER_SHOW_BRIEF);
 582         break;
 583     case FIB_PATH_TYPE_DVR:
 584         s = format (s, " %U",
 585                     format_vnet_sw_if_index_name,
 586                     vnm, path->dvr.fp_interface);
 587         break;
 588     case FIB_PATH_TYPE_DEAG:
 589         s = format (s, " %sfib-index:%d",
 590                     (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID ?  "m" : ""),
 591                     path->deag.fp_tbl_id);
 592         break;
 593     case FIB_PATH_TYPE_RECEIVE:
 594     case FIB_PATH_TYPE_INTF_RX:
 595     case FIB_PATH_TYPE_SPECIAL:
 596     case FIB_PATH_TYPE_EXCLUSIVE:
 597         if (dpo_id_is_valid(&path->fp_dpo))
 598         {
 599             s = format(s, "%U", format_dpo_id,
 600                        &path->fp_dpo, indent+2);
 601         }
 602         break;
 603     }
 604     return (s);
 605 }
 606
 607 /*
 608  * fib_path_last_lock_gone
 609  *
 610  * We don't share paths, we share path lists, so the [un]lock functions
 611  * are no-ops
 612  */
 613 static void
 614 fib_path_last_lock_gone (fib_node_t *node)
 615 {
 616     ASSERT(0);
 617 }
 618
 619 static fib_path_t*
 620 fib_path_attached_next_hop_get_adj (fib_path_t *path,
 621                                     vnet_link_t link,
 622                                     dpo_id_t *dpo)
 623 {
 624     fib_node_index_t fib_path_index;
 625     fib_protocol_t nh_proto;
 626     adj_index_t ai;
 627
 628     fib_path_index = fib_path_get_index(path);
 629     nh_proto = dpo_proto_to_fib(path->fp_nh_proto);
 630
 631     if (vnet_sw_interface_is_p2p(vnet_get_main(),
 632                                  path->attached_next_hop.fp_interface))
 633     {
 634         /*
 635          * if the interface is p2p then the adj for the specific
 636          * neighbour on that link will never exist. on p2p links
 637          * the subnet address (the attached route) links to the
 638          * auto-adj (see below), we want that adj here too.
 639          */
 640         ai = adj_nbr_add_or_lock(nh_proto, link, &zero_addr,
 641                                  path->attached_next_hop.fp_interface);
 642     }
 643     else
 644     {
 645         ai = adj_nbr_add_or_lock(nh_proto, link,
 646                                  &path->attached_next_hop.fp_nh,
 647                                  path->attached_next_hop.fp_interface);
 648     }
 649
 650     dpo_set(dpo, DPO_ADJACENCY, vnet_link_to_dpo_proto(link), ai);
 651     adj_unlock(ai);
 652
 653     return (fib_path_get(fib_path_index));
 654 }
 655
 656 static void
 657 fib_path_attached_next_hop_set (fib_path_t *path)
 658 {
 659     dpo_id_t tmp = DPO_INVALID;
 660
 661     /*
 662      * resolve directly via the adjacency discribed by the
 663      * interface and next-hop
 664      */
 665     dpo_copy (&tmp, &path->fp_dpo);
 666     path = fib_path_attached_next_hop_get_adj(path,
 667                                               dpo_proto_to_link(path->fp_nh_proto),
 668                                               &tmp);
 669     dpo_copy(&path->fp_dpo, &tmp);
 670     dpo_reset(&tmp);
 671     ASSERT(dpo_is_adj(&path->fp_dpo));
 672
 673     /*
 674      * become a child of the adjacency so we receive updates
 675      * when its rewrite changes
 676      */
 677     path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
 678                                      FIB_NODE_TYPE_PATH,
 679                                      fib_path_get_index(path));
 680
 681     if (!vnet_sw_interface_is_up(vnet_get_main(),
 682                                  path->attached_next_hop.fp_interface) ||
 683         !adj_is_up(path->fp_dpo.dpoi_index))
 684     {
 685         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 686     }
 687 }
 688
 689 static void
 690 fib_path_attached_get_adj (fib_path_t *path,
 691                            vnet_link_t link,
 692                            dpo_id_t *dpo)
 693 {
 694     fib_protocol_t nh_proto;
 695
 696     nh_proto = dpo_proto_to_fib(path->fp_nh_proto);
 697
 698     if (vnet_sw_interface_is_p2p(vnet_get_main(),
 699                                  path->attached.fp_interface))
 700     {
 701         /*
 702          * point-2-point interfaces do not require a glean, since
 703          * there is nothing to ARP. Install a rewrite/nbr adj instead
 704          */
 705         adj_index_t ai;
 706
 707         ai = adj_nbr_add_or_lock(nh_proto, link, &zero_addr,
 708                                  path->attached.fp_interface);
 709
 710         dpo_set(dpo, DPO_ADJACENCY, vnet_link_to_dpo_proto(link), ai);
 711         adj_unlock(ai);
 712     }
 713     else if (vnet_sw_interface_is_nbma(vnet_get_main(),
 714                                        path->attached.fp_interface))
 715     {
 716         dpo_copy(dpo, drop_dpo_get(path->fp_nh_proto));
 717     }
 718     else
 719     {
 720         adj_index_t ai;
 721
 722         ai = adj_glean_add_or_lock(nh_proto, link,
 723                                    path->attached.fp_interface,
 724                                    &path->attached.fp_connected);
 725         dpo_set(dpo, DPO_ADJACENCY_GLEAN, vnet_link_to_dpo_proto(link), ai);
 726         adj_unlock(ai);
 727     }
 728 }
 729
 730 /*
 731  * create of update the paths recursive adj
 732  */
 733 static void
 734 fib_path_recursive_adj_update (fib_path_t *path,
 735                                fib_forward_chain_type_t fct,
 736                                dpo_id_t *dpo)
 737 {
 738     dpo_id_t via_dpo = DPO_INVALID;
 739
 740     /*
 741      * get the DPO to resolve through from the via-entry
 742      */
 743     fib_entry_contribute_forwarding(path->fp_via_fib,
 744                                     fct,
 745                                     &via_dpo);
 746
 747
 748     /*
 749      * hope for the best - clear if restrictions apply.
 750      */
 751     path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 752
 753     /*
 754      * Validate any recursion constraints and over-ride the via
 755      * adj if not met
 756      */
 757     if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP)
 758     {
 759         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 760         dpo_copy(&via_dpo, drop_dpo_get(path->fp_nh_proto));
 761     }
 762     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_HOST)
 763     {
 764         /*
 765          * the via FIB must be a host route.
 766          * note the via FIB just added will always be a host route
 767          * since it is an RR source added host route. So what we need to
 768          * check is whether the route has other sources. If it does then
 769          * some other source has added it as a host route. If it doesn't
 770          * then it was added only here and inherits forwarding from a cover.
 771          * the cover is not a host route.
 772          * The RR source is the lowest priority source, so we check if it
 773          * is the best. if it is there are no other sources.
 774          */
 775         if (fib_entry_get_best_source(path->fp_via_fib) >= FIB_SOURCE_RR)
 776         {
 777             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 778             dpo_copy(&via_dpo, drop_dpo_get(path->fp_nh_proto));
 779
 780             /*
 781              * PIC edge trigger. let the load-balance maps know
 782              */
 783             load_balance_map_path_state_change(fib_path_get_index(path));
 784         }
 785     }
 786     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED)
 787     {
 788         /*
 789          * RR source entries inherit the flags from the cover, so
 790          * we can check the via directly
 791          */
 792         if (!(FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags(path->fp_via_fib)))
 793         {
 794             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 795             dpo_copy(&via_dpo, drop_dpo_get(path->fp_nh_proto));
 796
 797             /*
 798              * PIC edge trigger. let the load-balance maps know
 799              */
 800             load_balance_map_path_state_change(fib_path_get_index(path));
 801         }
 802     }
 803     /*
 804      * check for over-riding factors on the FIB entry itself
 805      */
 806     if (!fib_entry_is_resolved(path->fp_via_fib))
 807     {
 808         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 809         dpo_copy(&via_dpo, drop_dpo_get(path->fp_nh_proto));
 810
 811         /*
 812          * PIC edge trigger. let the load-balance maps know
 813          */
 814         load_balance_map_path_state_change(fib_path_get_index(path));
 815     }
 816
 817     /*
 818      * If this path is contributing a drop, then it's not resolved
 819      */
 820     if (dpo_is_drop(&via_dpo) || load_balance_is_drop(&via_dpo))
 821     {
 822         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 823     }
 824
 825     /*
 826      * update the path's contributed DPO
 827      */
 828     dpo_copy(dpo, &via_dpo);
 829
 830     FIB_PATH_DBG(path, "recursive update:");
 831
 832     dpo_reset(&via_dpo);
 833 }
 834
 835 /*
 836  * re-evaulate the forwarding state for a via fmask path
 837  */
 838 static void
 839 fib_path_bier_fmask_update (fib_path_t *path,
 840                             dpo_id_t *dpo)
 841 {
 842     bier_fmask_contribute_forwarding(path->bier_fmask.fp_bier_fmask, dpo);
 843
 844     /*
 845      * if we are stakcing on the drop, then the path is not resolved
 846      */
 847     if (dpo_is_drop(dpo))
 848     {
 849         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 850     }
 851     else
 852     {
 853         path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
 854     }
 855 }
 856
 857 /*
 858  * fib_path_is_permanent_drop
 859  *
 860  * Return !0 if the path is configured to permanently drop,
 861  * despite other attributes.
 862  */
 863 static int
 864 fib_path_is_permanent_drop (fib_path_t *path)
 865 {
 866     return ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DROP) ||
 867             (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP));
 868 }
 869
 870 /*
 871  * fib_path_unresolve
 872  *
 873  * Remove our dependency on the resolution target
 874  */
 875 static void
 876 fib_path_unresolve (fib_path_t *path)
 877 {
 878     /*
 879      * the forced drop path does not need unresolving
 880      */
 881     if (fib_path_is_permanent_drop(path))
 882     {
 883         return;
 884     }
 885
 886     switch (path->fp_type)
 887     {
 888     case FIB_PATH_TYPE_RECURSIVE:
 889         if (FIB_NODE_INDEX_INVALID != path->fp_via_fib)
 890         {
 891             fib_entry_child_remove(path->fp_via_fib,
 892                                    path->fp_sibling);
 893             fib_table_entry_special_remove(path->recursive.fp_tbl_id,
 894                                            fib_entry_get_prefix(path->fp_via_fib),
 895                                            FIB_SOURCE_RR);
 896             fib_table_unlock(path->recursive.fp_tbl_id,
 897                              dpo_proto_to_fib(path->fp_nh_proto),
 898                              FIB_SOURCE_RR);
 899             path->fp_via_fib = FIB_NODE_INDEX_INVALID;
 900         }
 901         break;
 902     case FIB_PATH_TYPE_BIER_FMASK:
 903         bier_fmask_child_remove(path->fp_via_bier_fmask,
 904                                 path->fp_sibling);
 905         break;
 906     case FIB_PATH_TYPE_BIER_IMP:
 907         bier_imp_unlock(path->fp_dpo.dpoi_index);
 908         break;
 909     case FIB_PATH_TYPE_BIER_TABLE:
 910         bier_table_ecmp_unlock(path->fp_via_bier_tbl);
 911         break;
 912     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
 913     case FIB_PATH_TYPE_ATTACHED:
 914         if (dpo_is_adj(&path->fp_dpo))
 915             adj_child_remove(path->fp_dpo.dpoi_index,
 916                              path->fp_sibling);
 917         break;
 918     case FIB_PATH_TYPE_UDP_ENCAP:
 919         udp_encap_unlock(path->fp_dpo.dpoi_index);
 920         break;
 921     case FIB_PATH_TYPE_EXCLUSIVE:
 922         dpo_reset(&path->exclusive.fp_ex_dpo);
 923         break;
 924     case FIB_PATH_TYPE_SPECIAL:
 925     case FIB_PATH_TYPE_RECEIVE:
 926     case FIB_PATH_TYPE_INTF_RX:
 927     case FIB_PATH_TYPE_DEAG:
 928     case FIB_PATH_TYPE_DVR:
 929         /*
 930          * these hold only the path's DPO, which is reset below.
 931          */
 932         break;
 933     }
 934
 935     /*
 936      * release the adj we were holding and pick up the
 937      * drop just in case.
 938      */
 939     dpo_reset(&path->fp_dpo);
 940     path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
 941
 942     return;
 943 }
 944
 945 static fib_forward_chain_type_t
 946 fib_path_to_chain_type (const fib_path_t *path)
 947 {
 948     if (DPO_PROTO_MPLS == path->fp_nh_proto)
 949     {
 950         if (FIB_PATH_TYPE_RECURSIVE == path->fp_type &&
 951             MPLS_EOS == path->recursive.fp_nh.fp_eos)
 952         {
 953             return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
 954         }
 955         else
 956         {
 957             return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
 958         }
 959     }
 960     else
 961     {
 962         return (fib_forw_chain_type_from_dpo_proto(path->fp_nh_proto));
 963     }
 964 }
 965
 966 /*
 967  * fib_path_back_walk_notify
 968  *
 969  * A back walk has reach this path.
 970  */
 971 static fib_node_back_walk_rc_t
 972 fib_path_back_walk_notify (fib_node_t *node,
 973                            fib_node_back_walk_ctx_t *ctx)
 974 {
 975     fib_path_t *path;
 976
 977     path = fib_path_from_fib_node(node);
 978
 979     FIB_PATH_DBG(path, "bw:%U",
 980                  format_fib_node_bw_reason, ctx->fnbw_reason);
 981
 982     switch (path->fp_type)
 983     {
 984     case FIB_PATH_TYPE_RECURSIVE:
 985         if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason)
 986         {
 987             /*
 988              * modify the recursive adjacency to use the new forwarding
 989              * of the via-fib.
 990              * this update is visible to packets in flight in the DP.
 991              */
 992             fib_path_recursive_adj_update(
 993                 path,
 994                 fib_path_to_chain_type(path),
 995                 &path->fp_dpo);
 996         }
 997         if ((FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason) ||
 998             (FIB_NODE_BW_REASON_FLAG_ADJ_MTU    & ctx->fnbw_reason) ||
 999             (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN   & ctx->fnbw_reason))
1000         {
1001             /*
1002              * ADJ updates (complete<->incomplete) do not need to propagate to
1003              * recursive entries.
1004              * The only reason its needed as far back as here, is that the adj
1005              * and the incomplete adj are a different DPO type, so the LBs need
1006              * to re-stack.
1007              * If this walk was quashed in the fib_entry, then any non-fib_path
1008              * children (like tunnels that collapse out the LB when they stack)
1009              * would not see the update.
1010              */
1011             return (FIB_NODE_BACK_WALK_CONTINUE);
1012         }
1013         break;
1014     case FIB_PATH_TYPE_BIER_FMASK:
1015         if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason)
1016         {
1017             /*
1018              * update to use the BIER fmask's new forwading
1019              */
1020             fib_path_bier_fmask_update(path, &path->fp_dpo);
1021         }
1022         if ((FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason) ||
1023             (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN   & ctx->fnbw_reason))
1024         {
1025             /*
1026              * ADJ updates (complete<->incomplete) do not need to propagate to
1027              * recursive entries.
1028              * The only reason its needed as far back as here, is that the adj
1029              * and the incomplete adj are a different DPO type, so the LBs need
1030              * to re-stack.
1031              * If this walk was quashed in the fib_entry, then any non-fib_path
1032              * children (like tunnels that collapse out the LB when they stack)
1033              * would not see the update.
1034              */
1035             return (FIB_NODE_BACK_WALK_CONTINUE);
1036         }
1037         break;
1038     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1039         /*
1040 FIXME comment
1041          * ADJ_UPDATE backwalk pass silently through here and up to
1042          * the path-list when the multipath adj collapse occurs.
1043          * The reason we do this is that the assumtption is that VPP
1044          * runs in an environment where the Control-Plane is remote
1045          * and hence reacts slowly to link up down. In order to remove
1046          * this down link from the ECMP set quickly, we back-walk.
1047          * VPP also has dedicated CPUs, so we are not stealing resources
1048          * from the CP to do so.
1049          */
1050         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
1051         {
1052             if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED)
1053             {
1054                 /*
1055                  * alreday resolved. no need to walk back again
1056                  */
1057                 return (FIB_NODE_BACK_WALK_CONTINUE);
1058             }
1059             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1060         }
1061         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
1062         {
1063             if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
1064             {
1065                 /*
1066                  * alreday unresolved. no need to walk back again
1067                  */
1068                 return (FIB_NODE_BACK_WALK_CONTINUE);
1069             }
1070             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1071         }
1072         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
1073         {
1074             /*
1075              * The interface this path resolves through has been deleted.
1076              * This will leave the path in a permanent drop state. The route
1077              * needs to be removed and readded (and hence the path-list deleted)
1078              * before it can forward again.
1079              */
1080             fib_path_unresolve(path);
1081             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
1082         }
1083         if (FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason)
1084         {
1085             /*
1086              * restack the DPO to pick up the correct DPO sub-type
1087              */
1088             dpo_id_t tmp = DPO_INVALID;
1089             uword if_is_up;
1090
1091             if_is_up = vnet_sw_interface_is_up(
1092                            vnet_get_main(),
1093                            path->attached_next_hop.fp_interface);
1094
1095             dpo_copy (&tmp, &path->fp_dpo);
1096             path = fib_path_attached_next_hop_get_adj(
1097                 path,
1098                 dpo_proto_to_link(path->fp_nh_proto),
1099                 &tmp);
1100             dpo_copy(&path->fp_dpo, &tmp);
1101             dpo_reset(&tmp);
1102
1103             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1104             if (if_is_up && adj_is_up(path->fp_dpo.dpoi_index))
1105             {
1106                 path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1107             }
1108
1109             if (!if_is_up)
1110             {
1111                 /*
1112                  * If the interface is not up there is no reason to walk
1113                  * back to children. if we did they would only evalute
1114                  * that this path is unresolved and hence it would
1115                  * not contribute the adjacency - so it would be wasted
1116                  * CPU time.
1117                  */
1118                 return (FIB_NODE_BACK_WALK_CONTINUE);
1119             }
1120         }
1121         if (FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason)
1122         {
1123             if (!(path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED))
1124             {
1125                 /*
1126                  * alreday unresolved. no need to walk back again
1127                  */
1128                 return (FIB_NODE_BACK_WALK_CONTINUE);
1129             }
1130             /*
1131              * the adj has gone down. the path is no longer resolved.
1132              */
1133             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1134         }
1135         break;
1136     case FIB_PATH_TYPE_ATTACHED:
1137     case FIB_PATH_TYPE_DVR:
1138         /*
1139          * FIXME; this could schedule a lower priority walk, since attached
1140          * routes are not usually in ECMP configurations so the backwalk to
1141          * the FIB entry does not need to be high priority
1142          */
1143         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason)
1144         {
1145             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1146         }
1147         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason)
1148         {
1149             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1150         }
1151         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
1152         {
1153             fib_path_unresolve(path);
1154             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_DROP;
1155         }
1156         if (FIB_NODE_BW_REASON_FLAG_INTERFACE_BIND & ctx->fnbw_reason)
1157         {
1158             /* bind walks should appear here and pass silently up to
1159              * to the fib_entry */
1160         }
1161         break;
1162     case FIB_PATH_TYPE_UDP_ENCAP:
1163     {
1164         dpo_id_t via_dpo = DPO_INVALID;
1165
1166         /*
1167          * hope for the best - clear if restrictions apply.
1168          */
1169         path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1170
1171         udp_encap_contribute_forwarding(path->udp_encap.fp_udp_encap_id,
1172                                         path->fp_nh_proto,
1173                                         &via_dpo);
1174         /*
1175          * If this path is contributing a drop, then it's not resolved
1176          */
1177         if (dpo_is_drop(&via_dpo) || load_balance_is_drop(&via_dpo))
1178         {
1179             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1180         }
1181
1182         /*
1183          * update the path's contributed DPO
1184          */
1185         dpo_copy(&path->fp_dpo, &via_dpo);
1186         dpo_reset(&via_dpo);
1187         break;
1188     }
1189     case FIB_PATH_TYPE_INTF_RX:
1190         ASSERT(0);
1191     case FIB_PATH_TYPE_DEAG:
1192         /*
1193          * FIXME When VRF delete is allowed this will need a poke.
1194          */
1195     case FIB_PATH_TYPE_SPECIAL:
1196     case FIB_PATH_TYPE_RECEIVE:
1197     case FIB_PATH_TYPE_EXCLUSIVE:
1198     case FIB_PATH_TYPE_BIER_TABLE:
1199     case FIB_PATH_TYPE_BIER_IMP:
1200         /*
1201          * these path types have no parents. so to be
1202          * walked from one is unexpected.
1203          */
1204         ASSERT(0);
1205         break;
1206     }
1207
1208     /*
1209      * propagate the backwalk further to the path-list
1210      */
1211     fib_path_list_back_walk(path->fp_pl_index, ctx);
1212
1213     return (FIB_NODE_BACK_WALK_CONTINUE);
1214 }
1215
1216 static void
1217 fib_path_memory_show (void)
1218 {
1219     fib_show_memory_usage("Path",
1220                           pool_elts(fib_path_pool),
1221                           pool_len(fib_path_pool),
1222                           sizeof(fib_path_t));
1223 }
1224
1225 /*
1226  * The FIB path's graph node virtual function table
1227  */
1228 static const fib_node_vft_t fib_path_vft = {
1229     .fnv_get = fib_path_get_node,
1230     .fnv_last_lock = fib_path_last_lock_gone,
1231     .fnv_back_walk = fib_path_back_walk_notify,
1232     .fnv_mem_show = fib_path_memory_show,
1233 };
1234
1235 static fib_path_cfg_flags_t
1236 fib_path_route_flags_to_cfg_flags (const fib_route_path_t *rpath)
1237 {
1238     fib_path_cfg_flags_t cfg_flags = FIB_PATH_CFG_FLAG_NONE;
1239
1240     if (rpath->frp_flags & FIB_ROUTE_PATH_POP_PW_CW)
1241         cfg_flags |= FIB_PATH_CFG_FLAG_POP_PW_CW;
1242     if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_HOST)
1243         cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_HOST;
1244     if (rpath->frp_flags & FIB_ROUTE_PATH_RESOLVE_VIA_ATTACHED)
1245         cfg_flags |= FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED;
1246     if (rpath->frp_flags & FIB_ROUTE_PATH_LOCAL)
1247         cfg_flags |= FIB_PATH_CFG_FLAG_LOCAL;
1248     if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
1249         cfg_flags |= FIB_PATH_CFG_FLAG_ATTACHED;
1250     if (rpath->frp_flags & FIB_ROUTE_PATH_INTF_RX)
1251         cfg_flags |= FIB_PATH_CFG_FLAG_INTF_RX;
1252     if (rpath->frp_flags & FIB_ROUTE_PATH_RPF_ID)
1253         cfg_flags |= FIB_PATH_CFG_FLAG_RPF_ID;
1254     if (rpath->frp_flags & FIB_ROUTE_PATH_EXCLUSIVE)
1255         cfg_flags |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
1256     if (rpath->frp_flags & FIB_ROUTE_PATH_DROP)
1257         cfg_flags |= FIB_PATH_CFG_FLAG_DROP;
1258     if (rpath->frp_flags & FIB_ROUTE_PATH_SOURCE_LOOKUP)
1259         cfg_flags |= FIB_PATH_CFG_FLAG_DEAG_SRC;
1260     if (rpath->frp_flags & FIB_ROUTE_PATH_ICMP_UNREACH)
1261         cfg_flags |= FIB_PATH_CFG_FLAG_ICMP_UNREACH;
1262     if (rpath->frp_flags & FIB_ROUTE_PATH_ICMP_PROHIBIT)
1263         cfg_flags |= FIB_PATH_CFG_FLAG_ICMP_PROHIBIT;
1264     if (rpath->frp_flags & FIB_ROUTE_PATH_GLEAN)
1265         cfg_flags |= FIB_PATH_CFG_FLAG_GLEAN;
1266
1267     return (cfg_flags);
1268 }
1269
1270 /*
1271  * fib_path_create
1272  *
1273  * Create and initialise a new path object.
1274  * return the index of the path.
1275  */
1276 fib_node_index_t
1277 fib_path_create (fib_node_index_t pl_index,
1278                  const fib_route_path_t *rpath)
1279 {
1280     fib_path_t *path;
1281
1282     pool_get(fib_path_pool, path);
1283     clib_memset(path, 0, sizeof(*path));
1284
1285     fib_node_init(&path->fp_node,
1286                   FIB_NODE_TYPE_PATH);
1287
1288     dpo_reset(&path->fp_dpo);
1289     path->fp_pl_index = pl_index;
1290     path->fp_nh_proto = rpath->frp_proto;
1291     path->fp_via_fib = FIB_NODE_INDEX_INVALID;
1292     path->fp_weight = rpath->frp_weight;
1293     if (0 == path->fp_weight)
1294     {
1295         /*
1296          * a weight of 0 is a meaningless value. We could either reject it, and thus force
1297          * clients to always use 1, or we can accept it and fixup approrpiately.
1298          */
1299         path->fp_weight = 1;
1300     }
1301     path->fp_preference = rpath->frp_preference;
1302     path->fp_cfg_flags = fib_path_route_flags_to_cfg_flags(rpath);
1303
1304     /*
1305      * deduce the path's tpye from the parementers and save what is needed.
1306      */
1307     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_LOCAL)
1308     {
1309         path->fp_type = FIB_PATH_TYPE_RECEIVE;
1310         path->receive.fp_interface = rpath->frp_sw_if_index;
1311         path->receive.fp_addr = rpath->frp_addr;
1312     }
1313     else if (rpath->frp_flags & FIB_ROUTE_PATH_UDP_ENCAP)
1314     {
1315         path->fp_type = FIB_PATH_TYPE_UDP_ENCAP;
1316         path->udp_encap.fp_udp_encap_id = rpath->frp_udp_encap_id;
1317     }
1318     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_INTF_RX)
1319     {
1320         path->fp_type = FIB_PATH_TYPE_INTF_RX;
1321         path->intf_rx.fp_interface = rpath->frp_sw_if_index;
1322     }
1323     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID)
1324     {
1325         path->fp_type = FIB_PATH_TYPE_DEAG;
1326         path->deag.fp_tbl_id = rpath->frp_fib_index;
1327         path->deag.fp_rpf_id = rpath->frp_rpf_id;
1328     }
1329     else if (rpath->frp_flags & FIB_ROUTE_PATH_BIER_FMASK)
1330     {
1331         path->fp_type = FIB_PATH_TYPE_BIER_FMASK;
1332         path->bier_fmask.fp_bier_fmask = rpath->frp_bier_fmask;
1333     }
1334     else if (rpath->frp_flags & FIB_ROUTE_PATH_BIER_IMP)
1335     {
1336         path->fp_type = FIB_PATH_TYPE_BIER_IMP;
1337         path->bier_imp.fp_bier_imp = rpath->frp_bier_imp;
1338     }
1339     else if (rpath->frp_flags & FIB_ROUTE_PATH_BIER_TABLE)
1340     {
1341         path->fp_type = FIB_PATH_TYPE_BIER_TABLE;
1342         path->bier_table.fp_bier_tbl = rpath->frp_bier_tbl;
1343     }
1344     else if (rpath->frp_flags & FIB_ROUTE_PATH_DEAG)
1345     {
1346         path->fp_type = FIB_PATH_TYPE_DEAG;
1347         path->deag.fp_tbl_id = rpath->frp_fib_index;
1348     }
1349     else if (rpath->frp_flags & FIB_ROUTE_PATH_DVR)
1350     {
1351         path->fp_type = FIB_PATH_TYPE_DVR;
1352         path->dvr.fp_interface = rpath->frp_sw_if_index;
1353     }
1354     else if (rpath->frp_flags & FIB_ROUTE_PATH_EXCLUSIVE)
1355     {
1356         path->fp_type = FIB_PATH_TYPE_EXCLUSIVE;
1357         dpo_copy(&path->exclusive.fp_ex_dpo, &rpath->dpo);
1358     }
1359     else if ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_PROHIBIT) ||
1360         (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_UNREACH) ||
1361         (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DROP))
1362     {
1363         path->fp_type = FIB_PATH_TYPE_SPECIAL;
1364     }
1365     else if ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_CLASSIFY))
1366     {
1367         path->fp_type = FIB_PATH_TYPE_SPECIAL;
1368         path->classify.fp_classify_table_id = rpath->frp_classify_table_id;
1369     }
1370     else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_GLEAN)
1371     {
1372         path->fp_type = FIB_PATH_TYPE_ATTACHED;
1373         path->attached.fp_interface = rpath->frp_sw_if_index;
1374         path->attached.fp_connected = rpath->frp_connected;
1375     }
1376     else if (~0 != rpath->frp_sw_if_index)
1377     {
1378         if (ip46_address_is_zero(&rpath->frp_addr))
1379         {
1380             path->fp_type = FIB_PATH_TYPE_ATTACHED;
1381             path->attached.fp_interface = rpath->frp_sw_if_index;
1382         }
1383         else
1384         {
1385             path->fp_type = FIB_PATH_TYPE_ATTACHED_NEXT_HOP;
1386             path->attached_next_hop.fp_interface = rpath->frp_sw_if_index;
1387             path->attached_next_hop.fp_nh = rpath->frp_addr;
1388         }
1389     }
1390     else
1391     {
1392         if (ip46_address_is_zero(&rpath->frp_addr))
1393         {
1394             if (~0 == rpath->frp_fib_index)
1395             {
1396                 path->fp_type = FIB_PATH_TYPE_SPECIAL;
1397             }
1398             else
1399             {
1400                 path->fp_type = FIB_PATH_TYPE_DEAG;
1401                 path->deag.fp_tbl_id = rpath->frp_fib_index;
1402                 path->deag.fp_rpf_id = ~0;
1403             }
1404         }
1405         else
1406         {
1407             path->fp_type = FIB_PATH_TYPE_RECURSIVE;
1408             if (DPO_PROTO_MPLS == path->fp_nh_proto)
1409             {
1410                 path->recursive.fp_nh.fp_local_label = rpath->frp_local_label;
1411                 path->recursive.fp_nh.fp_eos = rpath->frp_eos;
1412             }
1413             else
1414             {
1415                 path->recursive.fp_nh.fp_ip = rpath->frp_addr;
1416             }
1417             path->recursive.fp_tbl_id = rpath->frp_fib_index;
1418         }
1419     }
1420
1421     FIB_PATH_DBG(path, "create");
1422
1423     return (fib_path_get_index(path));
1424 }
1425
1426 /*
1427  * fib_path_create_special
1428  *
1429  * Create and initialise a new path object.
1430  * return the index of the path.
1431  */
1432 fib_node_index_t
1433 fib_path_create_special (fib_node_index_t pl_index,
1434                          dpo_proto_t nh_proto,
1435                          fib_path_cfg_flags_t flags,
1436                          const dpo_id_t *dpo)
1437 {
1438     fib_path_t *path;
1439
1440     pool_get(fib_path_pool, path);
1441     clib_memset(path, 0, sizeof(*path));
1442
1443     fib_node_init(&path->fp_node,
1444                   FIB_NODE_TYPE_PATH);
1445     dpo_reset(&path->fp_dpo);
1446
1447     path->fp_pl_index = pl_index;
1448     path->fp_weight = 1;
1449     path->fp_preference = 0;
1450     path->fp_nh_proto = nh_proto;
1451     path->fp_via_fib = FIB_NODE_INDEX_INVALID;
1452     path->fp_cfg_flags = flags;
1453
1454     if (FIB_PATH_CFG_FLAG_DROP & flags)
1455     {
1456         path->fp_type = FIB_PATH_TYPE_SPECIAL;
1457     }
1458     else if (FIB_PATH_CFG_FLAG_LOCAL & flags)
1459     {
1460         path->fp_type = FIB_PATH_TYPE_RECEIVE;
1461         path->attached.fp_interface = FIB_NODE_INDEX_INVALID;
1462     }
1463     else
1464     {
1465         path->fp_type = FIB_PATH_TYPE_EXCLUSIVE;
1466         ASSERT(NULL != dpo);
1467         dpo_copy(&path->exclusive.fp_ex_dpo, dpo);
1468     }
1469
1470     return (fib_path_get_index(path));
1471 }
1472
1473 /*
1474  * fib_path_copy
1475  *
1476  * Copy a path. return index of new path.
1477  */
1478 fib_node_index_t
1479 fib_path_copy (fib_node_index_t path_index,
1480                fib_node_index_t path_list_index)
1481 {
1482     fib_path_t *path, *orig_path;
1483
1484     pool_get(fib_path_pool, path);
1485
1486     orig_path = fib_path_get(path_index);
1487     ASSERT(NULL != orig_path);
1488
1489     clib_memcpy(path, orig_path, sizeof(*path));
1490
1491     FIB_PATH_DBG(path, "create-copy:%d", path_index);
1492
1493     /*
1494      * reset the dynamic section
1495      */
1496     fib_node_init(&path->fp_node, FIB_NODE_TYPE_PATH);
1497     path->fp_oper_flags     = FIB_PATH_OPER_FLAG_NONE;
1498     path->fp_pl_index  = path_list_index;
1499     path->fp_via_fib   = FIB_NODE_INDEX_INVALID;
1500     clib_memset(&path->fp_dpo, 0, sizeof(path->fp_dpo));
1501     dpo_reset(&path->fp_dpo);
1502
1503     if (path->fp_type == FIB_PATH_TYPE_EXCLUSIVE)
1504     {
1505         clib_memset(&path->exclusive.fp_ex_dpo, 0, sizeof(dpo_id_t));
1506         dpo_copy(&path->exclusive.fp_ex_dpo, &orig_path->exclusive.fp_ex_dpo);
1507     }
1508
1509     return (fib_path_get_index(path));
1510 }
1511
1512 /*
1513  * fib_path_destroy
1514  *
1515  * destroy a path that is no longer required
1516  */
1517 void
1518 fib_path_destroy (fib_node_index_t path_index)
1519 {
1520     fib_path_t *path;
1521
1522     path = fib_path_get(path_index);
1523
1524     ASSERT(NULL != path);
1525     FIB_PATH_DBG(path, "destroy");
1526
1527     fib_path_unresolve(path);
1528
1529     fib_node_deinit(&path->fp_node);
1530     pool_put(fib_path_pool, path);
1531 }
1532
1533 /*
1534  * fib_path_destroy
1535  *
1536  * destroy a path that is no longer required
1537  */
1538 uword
1539 fib_path_hash (fib_node_index_t path_index)
1540 {
1541     fib_path_t *path;
1542
1543     path = fib_path_get(path_index);
1544
1545     return (hash_memory(STRUCT_MARK_PTR(path, path_hash_start),
1546                         (STRUCT_OFFSET_OF(fib_path_t, path_hash_end) -
1547                          STRUCT_OFFSET_OF(fib_path_t, path_hash_start)),
1548                         0));
1549 }
1550
1551 /*
1552  * fib_path_cmp_i
1553  *
1554  * Compare two paths for equivalence.
1555  */
1556 static int
1557 fib_path_cmp_i (const fib_path_t *path1,
1558                 const fib_path_t *path2)
1559 {
1560     int res;
1561
1562     res = 1;
1563
1564     /*
1565      * paths of different types and protocol are not equal.
1566      * different weights and/or preference only are the same path.
1567      */
1568     if (path1->fp_type != path2->fp_type)
1569     {
1570         res = (path1->fp_type - path2->fp_type);
1571     }
1572     else if (path1->fp_nh_proto != path2->fp_nh_proto)
1573     {
1574         res = (path1->fp_nh_proto - path2->fp_nh_proto);
1575     }
1576     else
1577     {
1578         /*
1579          * both paths are of the same type.
1580          * consider each type and its attributes in turn.
1581          */
1582         switch (path1->fp_type)
1583         {
1584         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1585             res = ip46_address_cmp(&path1->attached_next_hop.fp_nh,
1586                                    &path2->attached_next_hop.fp_nh);
1587             if (0 == res) {
1588                 res = (path1->attached_next_hop.fp_interface -
1589                        path2->attached_next_hop.fp_interface);
1590             }
1591             break;
1592         case FIB_PATH_TYPE_ATTACHED:
1593             res = (path1->attached.fp_interface -
1594                    path2->attached.fp_interface);
1595             break;
1596         case FIB_PATH_TYPE_RECURSIVE:
1597             res = ip46_address_cmp(&path1->recursive.fp_nh.fp_ip,
1598                                    &path2->recursive.fp_nh.fp_ip);
1599
1600             if (0 == res)
1601             {
1602                 res = (path1->recursive.fp_tbl_id - path2->recursive.fp_tbl_id);
1603             }
1604             break;
1605         case FIB_PATH_TYPE_BIER_FMASK:
1606             res = (path1->bier_fmask.fp_bier_fmask -
1607                    path2->bier_fmask.fp_bier_fmask);
1608             break;
1609         case FIB_PATH_TYPE_BIER_IMP:
1610             res = (path1->bier_imp.fp_bier_imp -
1611                    path2->bier_imp.fp_bier_imp);
1612             break;
1613         case FIB_PATH_TYPE_BIER_TABLE:
1614             res = bier_table_id_cmp(&path1->bier_table.fp_bier_tbl,
1615                                     &path2->bier_table.fp_bier_tbl);
1616             break;
1617         case FIB_PATH_TYPE_DEAG:
1618             res = (path1->deag.fp_tbl_id - path2->deag.fp_tbl_id);
1619             if (0 == res)
1620             {
1621                 res = (path1->deag.fp_rpf_id - path2->deag.fp_rpf_id);
1622             }
1623             break;
1624         case FIB_PATH_TYPE_INTF_RX:
1625             res = (path1->intf_rx.fp_interface - path2->intf_rx.fp_interface);
1626             break;
1627         case FIB_PATH_TYPE_UDP_ENCAP:
1628             res = (path1->udp_encap.fp_udp_encap_id - path2->udp_encap.fp_udp_encap_id);
1629             break;
1630         case FIB_PATH_TYPE_DVR:
1631             res = (path1->dvr.fp_interface - path2->dvr.fp_interface);
1632             break;
1633         case FIB_PATH_TYPE_EXCLUSIVE:
1634             res = dpo_cmp(&path1->exclusive.fp_ex_dpo, &path2->exclusive.fp_ex_dpo);
1635             break;
1636         case FIB_PATH_TYPE_SPECIAL:
1637         case FIB_PATH_TYPE_RECEIVE:
1638             res = 0;
1639             break;
1640         }
1641     }
1642     return (res);
1643 }
1644
1645 /*
1646  * fib_path_cmp_for_sort
1647  *
1648  * Compare two paths for equivalence. Used during path sorting.
1649  * As usual 0 means equal.
1650  */
1651 int
1652 fib_path_cmp_for_sort (void * v1,
1653                        void * v2)
1654 {
1655     fib_node_index_t *pi1 = v1, *pi2 = v2;
1656     fib_path_t *path1, *path2;
1657
1658     path1 = fib_path_get(*pi1);
1659     path2 = fib_path_get(*pi2);
1660
1661     /*
1662      * when sorting paths we want the highest preference paths
1663      * first, so that the choices set built is in prefernce order
1664      */
1665     if (path1->fp_preference != path2->fp_preference)
1666     {
1667         return (path1->fp_preference - path2->fp_preference);
1668     }
1669
1670     return (fib_path_cmp_i(path1, path2));
1671 }
1672
1673 /*
1674  * fib_path_cmp
1675  *
1676  * Compare two paths for equivalence.
1677  */
1678 int
1679 fib_path_cmp (fib_node_index_t pi1,
1680               fib_node_index_t pi2)
1681 {
1682     fib_path_t *path1, *path2;
1683
1684     path1 = fib_path_get(pi1);
1685     path2 = fib_path_get(pi2);
1686
1687     return (fib_path_cmp_i(path1, path2));
1688 }
1689
1690 int
1691 fib_path_cmp_w_route_path (fib_node_index_t path_index,
1692                            const fib_route_path_t *rpath)
1693 {
1694     fib_path_t *path;
1695     int res;
1696
1697     path = fib_path_get(path_index);
1698
1699     res = 1;
1700
1701     if (path->fp_weight != rpath->frp_weight)
1702     {
1703         res = (path->fp_weight - rpath->frp_weight);
1704     }
1705     else
1706     {
1707         /*
1708          * both paths are of the same type.
1709          * consider each type and its attributes in turn.
1710          */
1711         switch (path->fp_type)
1712         {
1713         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1714             res = ip46_address_cmp(&path->attached_next_hop.fp_nh,
1715                                    &rpath->frp_addr);
1716             if (0 == res)
1717             {
1718                 res = (path->attached_next_hop.fp_interface -
1719                        rpath->frp_sw_if_index);
1720             }
1721             break;
1722         case FIB_PATH_TYPE_ATTACHED:
1723             res = (path->attached.fp_interface - rpath->frp_sw_if_index);
1724             break;
1725         case FIB_PATH_TYPE_RECURSIVE:
1726             if (DPO_PROTO_MPLS == path->fp_nh_proto)
1727             {
1728                 res = path->recursive.fp_nh.fp_local_label - rpath->frp_local_label;
1729
1730                 if (res == 0)
1731                 {
1732                     res = path->recursive.fp_nh.fp_eos - rpath->frp_eos;
1733                 }
1734             }
1735             else
1736             {
1737                 res = ip46_address_cmp(&path->recursive.fp_nh.fp_ip,
1738                                        &rpath->frp_addr);
1739             }
1740
1741             if (0 == res)
1742             {
1743                 res = (path->recursive.fp_tbl_id - rpath->frp_fib_index);
1744             }
1745             break;
1746         case FIB_PATH_TYPE_BIER_FMASK:
1747             res = (path->bier_fmask.fp_bier_fmask - rpath->frp_bier_fmask);
1748             break;
1749         case FIB_PATH_TYPE_BIER_IMP:
1750             res = (path->bier_imp.fp_bier_imp - rpath->frp_bier_imp);
1751             break;
1752         case FIB_PATH_TYPE_BIER_TABLE:
1753             res = bier_table_id_cmp(&path->bier_table.fp_bier_tbl,
1754                                     &rpath->frp_bier_tbl);
1755             break;
1756         case FIB_PATH_TYPE_INTF_RX:
1757             res = (path->intf_rx.fp_interface - rpath->frp_sw_if_index);
1758             break;
1759         case FIB_PATH_TYPE_UDP_ENCAP:
1760             res = (path->udp_encap.fp_udp_encap_id - rpath->frp_udp_encap_id);
1761             break;
1762         case FIB_PATH_TYPE_DEAG:
1763             res = (path->deag.fp_tbl_id - rpath->frp_fib_index);
1764             if (0 == res)
1765             {
1766                 res = (path->deag.fp_rpf_id - rpath->frp_rpf_id);
1767             }
1768             break;
1769         case FIB_PATH_TYPE_DVR:
1770             res = (path->dvr.fp_interface - rpath->frp_sw_if_index);
1771             break;
1772         case FIB_PATH_TYPE_EXCLUSIVE:
1773             res = dpo_cmp(&path->exclusive.fp_ex_dpo, &rpath->dpo);
1774             break;
1775         case FIB_PATH_TYPE_RECEIVE:
1776             if (rpath->frp_flags & FIB_ROUTE_PATH_LOCAL)
1777             {
1778                 res = 0;
1779             }
1780             else
1781             {
1782                 res = 1;
1783             }
1784             break;
1785         case FIB_PATH_TYPE_SPECIAL:
1786             res = 0;
1787             break;
1788         }
1789     }
1790     return (res);
1791 }
1792
1793 /*
1794  * fib_path_recursive_loop_detect
1795  *
1796  * A forward walk of the FIB object graph to detect for a cycle/loop. This
1797  * walk is initiated when an entry is linking to a new path list or from an old.
1798  * The entry vector passed contains all the FIB entrys that are children of this
1799  * path (it is all the entries encountered on the walk so far). If this vector
1800  * contains the entry this path resolve via, then a loop is about to form.
1801  * The loop must be allowed to form, since we need the dependencies in place
1802  * so that we can track when the loop breaks.
1803  * However, we MUST not produce a loop in the forwarding graph (else packets
1804  * would loop around the switch path until the loop breaks), so we mark recursive
1805  * paths as looped so that they do not contribute forwarding information.
1806  * By marking the path as looped, an etry such as;
1807  *    X/Y
1808  *     via a.a.a.a (looped)
1809  *     via b.b.b.b (not looped)
1810  * can still forward using the info provided by b.b.b.b only
1811  */
1812 int
1813 fib_path_recursive_loop_detect (fib_node_index_t path_index,
1814                                 fib_node_index_t **entry_indicies)
1815 {
1816     fib_path_t *path;
1817
1818     path = fib_path_get(path_index);
1819
1820     /*
1821      * the forced drop path is never looped, cos it is never resolved.
1822      */
1823     if (fib_path_is_permanent_drop(path))
1824     {
1825         return (0);
1826     }
1827
1828     switch (path->fp_type)
1829     {
1830     case FIB_PATH_TYPE_RECURSIVE:
1831     {
1832         fib_node_index_t *entry_index, *entries;
1833         int looped = 0;
1834         entries = *entry_indicies;
1835
1836         vec_foreach(entry_index, entries) {
1837             if (*entry_index == path->fp_via_fib)
1838             {
1839                 /*
1840                  * the entry that is about to link to this path-list (or
1841                  * one of this path-list's children) is the same entry that
1842                  * this recursive path resolves through. this is a cycle.
1843                  * abort the walk.
1844                  */
1845                 looped = 1;
1846                 break;
1847             }
1848         }
1849
1850         if (looped)
1851         {
1852             FIB_PATH_DBG(path, "recursive loop formed");
1853             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1854
1855             dpo_copy(&path->fp_dpo, drop_dpo_get(path->fp_nh_proto));
1856         }
1857         else
1858         {
1859             /*
1860              * no loop here yet. keep forward walking the graph.
1861              */
1862             if (fib_entry_recursive_loop_detect(path->fp_via_fib, entry_indicies))
1863             {
1864                 FIB_PATH_DBG(path, "recursive loop formed");
1865                 path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1866             }
1867             else
1868             {
1869                 FIB_PATH_DBG(path, "recursive loop cleared");
1870                 path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1871             }
1872         }
1873         break;
1874     }
1875     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1876     case FIB_PATH_TYPE_ATTACHED:
1877         if (dpo_is_adj(&path->fp_dpo) &&
1878             adj_recursive_loop_detect(path->fp_dpo.dpoi_index,
1879                                       entry_indicies))
1880         {
1881             FIB_PATH_DBG(path, "recursive loop formed");
1882             path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1883         }
1884         else
1885         {
1886             FIB_PATH_DBG(path, "recursive loop cleared");
1887             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RECURSIVE_LOOP;
1888         }
1889         break;
1890     case FIB_PATH_TYPE_SPECIAL:
1891     case FIB_PATH_TYPE_DEAG:
1892     case FIB_PATH_TYPE_DVR:
1893     case FIB_PATH_TYPE_RECEIVE:
1894     case FIB_PATH_TYPE_INTF_RX:
1895     case FIB_PATH_TYPE_UDP_ENCAP:
1896     case FIB_PATH_TYPE_EXCLUSIVE:
1897     case FIB_PATH_TYPE_BIER_FMASK:
1898     case FIB_PATH_TYPE_BIER_TABLE:
1899     case FIB_PATH_TYPE_BIER_IMP:
1900         /*
1901          * these path types cannot be part of a loop, since they are the leaves
1902          * of the graph.
1903          */
1904         break;
1905     }
1906
1907     return (fib_path_is_looped(path_index));
1908 }
1909
1910 int
1911 fib_path_resolve (fib_node_index_t path_index)
1912 {
1913     fib_path_t *path;
1914
1915     path = fib_path_get(path_index);
1916
1917     /*
1918      * hope for the best.
1919      */
1920     path->fp_oper_flags |= FIB_PATH_OPER_FLAG_RESOLVED;
1921
1922     /*
1923      * the forced drop path resolves via the drop adj
1924      */
1925     if (fib_path_is_permanent_drop(path))
1926     {
1927         dpo_copy(&path->fp_dpo, drop_dpo_get(path->fp_nh_proto));
1928         path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1929         return (fib_path_is_resolved(path_index));
1930     }
1931
1932     switch (path->fp_type)
1933     {
1934     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
1935         fib_path_attached_next_hop_set(path);
1936         break;
1937     case FIB_PATH_TYPE_ATTACHED:
1938     {
1939         dpo_id_t tmp = DPO_INVALID;
1940
1941         /*
1942          * path->attached.fp_interface
1943          */
1944         if (!vnet_sw_interface_is_up(vnet_get_main(),
1945                                      path->attached.fp_interface))
1946         {
1947             path->fp_oper_flags &= ~FIB_PATH_OPER_FLAG_RESOLVED;
1948         }
1949         fib_path_attached_get_adj(path,
1950                                   dpo_proto_to_link(path->fp_nh_proto),
1951                                   &tmp);
1952
1953         /*
1954          * re-fetch after possible mem realloc
1955          */
1956         path = fib_path_get(path_index);
1957         dpo_copy(&path->fp_dpo, &tmp);
1958
1959         /*
1960          * become a child of the adjacency so we receive updates
1961          * when the interface state changes
1962          */
1963         if (dpo_is_adj(&path->fp_dpo))
1964         {
1965             path->fp_sibling = adj_child_add(path->fp_dpo.dpoi_index,
1966                                              FIB_NODE_TYPE_PATH,
1967                                              fib_path_get_index(path));
1968         }
1969         dpo_reset(&tmp);
1970         break;
1971     }
1972     case FIB_PATH_TYPE_RECURSIVE:
1973     {
1974         /*
1975          * Create a RR source entry in the table for the address
1976          * that this path recurses through.
1977          * This resolve action is recursive, hence we may create
1978          * more paths in the process. more creates mean maybe realloc
1979          * of this path.
1980          */
1981         fib_node_index_t fei;
1982         fib_prefix_t pfx;
1983
1984         ASSERT(FIB_NODE_INDEX_INVALID == path->fp_via_fib);
1985
1986         if (DPO_PROTO_MPLS == path->fp_nh_proto)
1987         {
1988             fib_prefix_from_mpls_label(path->recursive.fp_nh.fp_local_label,
1989                                        path->recursive.fp_nh.fp_eos,
1990                                        &pfx);
1991         }
1992         else
1993         {
1994             ASSERT(!ip46_address_is_zero(&path->recursive.fp_nh.fp_ip));
1995
1996             fib_protocol_t fp = (ip46_address_is_ip4(&path->recursive.fp_nh.fp_ip) ?
1997                                         FIB_PROTOCOL_IP4 : FIB_PROTOCOL_IP6);
1998             fib_prefix_from_ip46_addr(fp, &path->recursive.fp_nh.fp_ip, &pfx);
1999         }
2000
2001         fib_table_lock(path->recursive.fp_tbl_id,
2002                        dpo_proto_to_fib(path->fp_nh_proto),
2003                        FIB_SOURCE_RR);
2004         fei = fib_table_entry_special_add(path->recursive.fp_tbl_id,
2005                                           &pfx,
2006                                           FIB_SOURCE_RR,
2007                                           FIB_ENTRY_FLAG_NONE);
2008
2009         path = fib_path_get(path_index);
2010         path->fp_via_fib = fei;
2011
2012         /*
2013          * become a dependent child of the entry so the path is
2014          * informed when the forwarding for the entry changes.
2015          */
2016         path->fp_sibling = fib_entry_child_add(path->fp_via_fib,
2017                                                FIB_NODE_TYPE_PATH,
2018                                                fib_path_get_index(path));
2019
2020         /*
2021          * create and configure the IP DPO
2022          */
2023         fib_path_recursive_adj_update(
2024             path,
2025             fib_path_to_chain_type(path),
2026             &path->fp_dpo);
2027
2028         break;
2029     }
2030     case FIB_PATH_TYPE_BIER_FMASK:
2031     {
2032         /*
2033          * become a dependent child of the entry so the path is
2034          * informed when the forwarding for the entry changes.
2035          */
2036         path->fp_sibling = bier_fmask_child_add(path->bier_fmask.fp_bier_fmask,
2037                                                 FIB_NODE_TYPE_PATH,
2038                                                 fib_path_get_index(path));
2039
2040         path->fp_via_bier_fmask = path->bier_fmask.fp_bier_fmask;
2041         fib_path_bier_fmask_update(path, &path->fp_dpo);
2042
2043         break;
2044     }
2045     case FIB_PATH_TYPE_BIER_IMP:
2046         bier_imp_lock(path->bier_imp.fp_bier_imp);
2047         bier_imp_contribute_forwarding(path->bier_imp.fp_bier_imp,
2048                                        DPO_PROTO_IP4,
2049                                        &path->fp_dpo);
2050         break;
2051     case FIB_PATH_TYPE_BIER_TABLE:
2052     {
2053         /*
2054          * Find/create the BIER table to link to
2055          */
2056         ASSERT(FIB_NODE_INDEX_INVALID == path->fp_via_bier_tbl);
2057
2058         path->fp_via_bier_tbl =
2059             bier_table_ecmp_create_and_lock(&path->bier_table.fp_bier_tbl);
2060
2061         bier_table_contribute_forwarding(path->fp_via_bier_tbl,
2062                                          &path->fp_dpo);
2063         break;
2064     }
2065     case FIB_PATH_TYPE_SPECIAL:
2066         if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_PROHIBIT)
2067         {
2068             ip_null_dpo_add_and_lock (path->fp_nh_proto,
2069                                       IP_NULL_ACTION_SEND_ICMP_PROHIBIT,
2070                                       &path->fp_dpo);
2071         }
2072         else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_UNREACH)
2073         {
2074             ip_null_dpo_add_and_lock (path->fp_nh_proto,
2075                                       IP_NULL_ACTION_SEND_ICMP_UNREACH,
2076                                       &path->fp_dpo);
2077         }
2078         else if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_CLASSIFY)
2079         {
2080             dpo_set (&path->fp_dpo, DPO_CLASSIFY,
2081                      path->fp_nh_proto,
2082                      classify_dpo_create (path->fp_nh_proto,
2083                                           path->classify.fp_classify_table_id));
2084         }
2085         else
2086         {
2087             /*
2088              * Resolve via the drop
2089              */
2090             dpo_copy(&path->fp_dpo, drop_dpo_get(path->fp_nh_proto));
2091         }
2092         break;
2093     case FIB_PATH_TYPE_DEAG:
2094     {
2095         if (DPO_PROTO_BIER == path->fp_nh_proto)
2096         {
2097             bier_disp_table_contribute_forwarding(path->deag.fp_tbl_id,
2098                                                   &path->fp_dpo);
2099         }
2100         else
2101         {
2102             /*
2103              * Resolve via a lookup DPO.
2104              * FIXME. control plane should add routes with a table ID
2105              */
2106             lookup_input_t input;
2107             lookup_cast_t cast;
2108
2109             cast = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID ?
2110                     LOOKUP_MULTICAST :
2111                     LOOKUP_UNICAST);
2112             input = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DEAG_SRC ?
2113                      LOOKUP_INPUT_SRC_ADDR :
2114                      LOOKUP_INPUT_DST_ADDR);
2115
2116             lookup_dpo_add_or_lock_w_fib_index(path->deag.fp_tbl_id,
2117                                                path->fp_nh_proto,
2118                                                cast,
2119                                                input,
2120                                                LOOKUP_TABLE_FROM_CONFIG,
2121                                                &path->fp_dpo);
2122         }
2123         break;
2124     }
2125     case FIB_PATH_TYPE_DVR:
2126         dvr_dpo_add_or_lock(path->dvr.fp_interface,
2127                             path->fp_nh_proto,
2128                             &path->fp_dpo);
2129         break;
2130     case FIB_PATH_TYPE_RECEIVE:
2131         /*
2132          * Resolve via a receive DPO.
2133          */
2134         receive_dpo_add_or_lock(path->fp_nh_proto,
2135                                 path->receive.fp_interface,
2136                                 &path->receive.fp_addr,
2137                                 &path->fp_dpo);
2138         break;
2139     case FIB_PATH_TYPE_UDP_ENCAP:
2140         udp_encap_lock(path->udp_encap.fp_udp_encap_id);
2141         udp_encap_contribute_forwarding(path->udp_encap.fp_udp_encap_id,
2142                                         path->fp_nh_proto,
2143                                         &path->fp_dpo);
2144         break;
2145     case FIB_PATH_TYPE_INTF_RX: {
2146         /*
2147          * Resolve via a receive DPO.
2148          */
2149         interface_rx_dpo_add_or_lock(path->fp_nh_proto,
2150                                      path->intf_rx.fp_interface,
2151                                      &path->fp_dpo);
2152         break;
2153     }
2154     case FIB_PATH_TYPE_EXCLUSIVE:
2155         /*
2156          * Resolve via the user provided DPO
2157          */
2158         dpo_copy(&path->fp_dpo, &path->exclusive.fp_ex_dpo);
2159         break;
2160     }
2161
2162     return (fib_path_is_resolved(path_index));
2163 }
2164
2165 u32
2166 fib_path_get_resolving_interface (fib_node_index_t path_index)
2167 {
2168     fib_path_t *path;
2169
2170     path = fib_path_get(path_index);
2171
2172     switch (path->fp_type)
2173     {
2174     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2175         return (path->attached_next_hop.fp_interface);
2176     case FIB_PATH_TYPE_ATTACHED:
2177         return (path->attached.fp_interface);
2178     case FIB_PATH_TYPE_RECEIVE:
2179         return (path->receive.fp_interface);
2180     case FIB_PATH_TYPE_RECURSIVE:
2181         if (fib_path_is_resolved(path_index))
2182         {
2183             return (fib_entry_get_resolving_interface(path->fp_via_fib));
2184         }
2185         break;
2186     case FIB_PATH_TYPE_DVR:
2187         return (path->dvr.fp_interface);
2188     case FIB_PATH_TYPE_INTF_RX:
2189     case FIB_PATH_TYPE_UDP_ENCAP:
2190     case FIB_PATH_TYPE_SPECIAL:
2191     case FIB_PATH_TYPE_DEAG:
2192     case FIB_PATH_TYPE_EXCLUSIVE:
2193     case FIB_PATH_TYPE_BIER_FMASK:
2194     case FIB_PATH_TYPE_BIER_TABLE:
2195     case FIB_PATH_TYPE_BIER_IMP:
2196         break;
2197     }
2198     return (dpo_get_urpf(&path->fp_dpo));
2199 }
2200
2201 index_t
2202 fib_path_get_resolving_index (fib_node_index_t path_index)
2203 {
2204     fib_path_t *path;
2205
2206     path = fib_path_get(path_index);
2207
2208     switch (path->fp_type)
2209     {
2210     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2211     case FIB_PATH_TYPE_ATTACHED:
2212     case FIB_PATH_TYPE_RECEIVE:
2213     case FIB_PATH_TYPE_INTF_RX:
2214     case FIB_PATH_TYPE_SPECIAL:
2215     case FIB_PATH_TYPE_DEAG:
2216     case FIB_PATH_TYPE_DVR:
2217     case FIB_PATH_TYPE_EXCLUSIVE:
2218         break;
2219     case FIB_PATH_TYPE_UDP_ENCAP:
2220         return (path->udp_encap.fp_udp_encap_id);
2221     case FIB_PATH_TYPE_RECURSIVE:
2222         return (path->fp_via_fib);
2223     case FIB_PATH_TYPE_BIER_FMASK:
2224         return (path->bier_fmask.fp_bier_fmask);
2225    case FIB_PATH_TYPE_BIER_TABLE:
2226        return (path->fp_via_bier_tbl);
2227    case FIB_PATH_TYPE_BIER_IMP:
2228        return (path->bier_imp.fp_bier_imp);
2229     }
2230     return (~0);
2231 }
2232
2233 adj_index_t
2234 fib_path_get_adj (fib_node_index_t path_index)
2235 {
2236     fib_path_t *path;
2237
2238     path = fib_path_get(path_index);
2239
2240     if (dpo_is_adj(&path->fp_dpo))
2241     {
2242         return (path->fp_dpo.dpoi_index);
2243     }
2244     return (ADJ_INDEX_INVALID);
2245 }
2246
2247 u16
2248 fib_path_get_weight (fib_node_index_t path_index)
2249 {
2250     fib_path_t *path;
2251
2252     path = fib_path_get(path_index);
2253
2254     ASSERT(path);
2255
2256     return (path->fp_weight);
2257 }
2258
2259 u16
2260 fib_path_get_preference (fib_node_index_t path_index)
2261 {
2262     fib_path_t *path;
2263
2264     path = fib_path_get(path_index);
2265
2266     ASSERT(path);
2267
2268     return (path->fp_preference);
2269 }
2270
2271 u32
2272 fib_path_get_rpf_id (fib_node_index_t path_index)
2273 {
2274     fib_path_t *path;
2275
2276     path = fib_path_get(path_index);
2277
2278     ASSERT(path);
2279
2280     if (FIB_PATH_CFG_FLAG_RPF_ID & path->fp_cfg_flags)
2281     {
2282         return (path->deag.fp_rpf_id);
2283     }
2284
2285     return (~0);
2286 }
2287
2288 /**
2289  * @brief Contribute the path's adjacency to the list passed.
2290  * By calling this function over all paths, recursively, a child
2291  * can construct its full set of forwarding adjacencies, and hence its
2292  * uRPF list.
2293  */
2294 void
2295 fib_path_contribute_urpf (fib_node_index_t path_index,
2296                           index_t urpf)
2297 {
2298     fib_path_t *path;
2299
2300     path = fib_path_get(path_index);
2301
2302     /*
2303      * resolved and unresolved paths contribute to the RPF list.
2304      */
2305     switch (path->fp_type)
2306     {
2307     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2308         fib_urpf_list_append(urpf, path->attached_next_hop.fp_interface);
2309         break;
2310
2311     case FIB_PATH_TYPE_ATTACHED:
2312         fib_urpf_list_append(urpf, path->attached.fp_interface);
2313         break;
2314
2315     case FIB_PATH_TYPE_RECURSIVE:
2316         if (FIB_NODE_INDEX_INVALID != path->fp_via_fib &&
2317             !fib_path_is_looped(path_index))
2318         {
2319             /*
2320              * there's unresolved due to constraints, and there's unresolved
2321              * due to ain't got no via. can't do nowt w'out via.
2322              */
2323             fib_entry_contribute_urpf(path->fp_via_fib, urpf);
2324         }
2325         break;
2326
2327     case FIB_PATH_TYPE_EXCLUSIVE:
2328     case FIB_PATH_TYPE_SPECIAL:
2329     {
2330         /*
2331          * these path types may link to an adj, if that's what
2332          * the clinet gave
2333          */
2334         u32 rpf_sw_if_index;
2335
2336         rpf_sw_if_index = dpo_get_urpf(&path->fp_dpo);
2337
2338         if (~0 != rpf_sw_if_index)
2339         {
2340             fib_urpf_list_append(urpf, rpf_sw_if_index);
2341         }
2342         break;
2343     }
2344     case FIB_PATH_TYPE_DVR:
2345         fib_urpf_list_append(urpf, path->dvr.fp_interface);
2346         break;
2347     case FIB_PATH_TYPE_UDP_ENCAP:
2348         fib_urpf_list_append(urpf, path->udp_encap.fp_udp_encap_id);
2349         break;
2350     case FIB_PATH_TYPE_DEAG:
2351     case FIB_PATH_TYPE_RECEIVE:
2352     case FIB_PATH_TYPE_INTF_RX:
2353     case FIB_PATH_TYPE_BIER_FMASK:
2354     case FIB_PATH_TYPE_BIER_TABLE:
2355     case FIB_PATH_TYPE_BIER_IMP:
2356         /*
2357          * these path types don't link to an adj
2358          */
2359         break;
2360     }
2361 }
2362
2363 void
2364 fib_path_stack_mpls_disp (fib_node_index_t path_index,
2365                           dpo_proto_t payload_proto,
2366                           fib_mpls_lsp_mode_t mode,
2367                           dpo_id_t *dpo)
2368 {
2369     fib_path_t *path;
2370
2371     path = fib_path_get(path_index);
2372
2373     ASSERT(path);
2374
2375     switch (path->fp_type)
2376     {
2377     case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2378     {
2379         dpo_id_t tmp = DPO_INVALID;
2380
2381         dpo_copy(&tmp, dpo);
2382
2383         mpls_disp_dpo_create(payload_proto, ~0, mode, &tmp, dpo);
2384         dpo_reset(&tmp);
2385         break;
2386     }
2387     case FIB_PATH_TYPE_DEAG:
2388     {
2389         dpo_id_t tmp = DPO_INVALID;
2390
2391         dpo_copy(&tmp, dpo);
2392
2393         mpls_disp_dpo_create(payload_proto,
2394                              path->deag.fp_rpf_id,
2395                              mode, &tmp, dpo);
2396         dpo_reset(&tmp);
2397         break;
2398     }
2399     case FIB_PATH_TYPE_RECEIVE:
2400     case FIB_PATH_TYPE_ATTACHED:
2401     case FIB_PATH_TYPE_RECURSIVE:
2402     case FIB_PATH_TYPE_INTF_RX:
2403     case FIB_PATH_TYPE_UDP_ENCAP:
2404     case FIB_PATH_TYPE_EXCLUSIVE:
2405     case FIB_PATH_TYPE_SPECIAL:
2406     case FIB_PATH_TYPE_BIER_FMASK:
2407     case FIB_PATH_TYPE_BIER_TABLE:
2408     case FIB_PATH_TYPE_BIER_IMP:
2409     case FIB_PATH_TYPE_DVR:
2410         break;
2411     }
2412
2413     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_POP_PW_CW)
2414     {
2415         dpo_id_t tmp = DPO_INVALID;
2416
2417         dpo_copy(&tmp, dpo);
2418
2419         pw_cw_dpo_create(&tmp, dpo);
2420         dpo_reset(&tmp);
2421     }
2422 }
2423
2424 void
2425 fib_path_contribute_forwarding (fib_node_index_t path_index,
2426                                 fib_forward_chain_type_t fct,
2427                                 dpo_proto_t payload_proto,
2428                                 dpo_id_t *dpo)
2429 {
2430     fib_path_t *path;
2431
2432     path = fib_path_get(path_index);
2433
2434     ASSERT(path);
2435
2436     /*
2437      * The DPO stored in the path was created when the path was resolved.
2438      * This then represents the path's 'native' protocol; IP.
2439      * For all others will need to go find something else.
2440      */
2441     if (fib_path_to_chain_type(path) == fct)
2442     {
2443         dpo_copy(dpo, &path->fp_dpo);
2444     }
2445     else
2446     {
2447         switch (path->fp_type)
2448         {
2449         case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2450             switch (fct)
2451             {
2452             case FIB_FORW_CHAIN_TYPE_MPLS_EOS: {
2453                     dpo_id_t tmp = DPO_INVALID;
2454                     dpo_copy (&tmp, dpo);
2455                     path = fib_path_attached_next_hop_get_adj(
2456                            path,
2457                            dpo_proto_to_link(payload_proto),
2458                            &tmp);
2459                     dpo_copy (dpo, &tmp);
2460                     dpo_reset(&tmp);
2461                     break;
2462             }
2463             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2464             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2465             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2466             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2467             case FIB_FORW_CHAIN_TYPE_NSH:
2468             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2469             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2470                 {
2471                     dpo_id_t tmp = DPO_INVALID;
2472                     dpo_copy (&tmp, dpo);
2473                     path = fib_path_attached_next_hop_get_adj(
2474                            path,
2475                            fib_forw_chain_type_to_link_type(fct),
2476                            &tmp);
2477                     dpo_copy (dpo, &tmp);
2478                     dpo_reset(&tmp);
2479                     break;
2480                 }
2481             case FIB_FORW_CHAIN_TYPE_BIER:
2482                 break;
2483             }
2484             break;
2485         case FIB_PATH_TYPE_RECURSIVE:
2486             switch (fct)
2487             {
2488             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
2489             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2490             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2491             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2492             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2493             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2494             case FIB_FORW_CHAIN_TYPE_BIER:
2495                 fib_path_recursive_adj_update(path, fct, dpo);
2496                 break;
2497             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2498             case FIB_FORW_CHAIN_TYPE_NSH:
2499                 ASSERT(0);
2500                 break;
2501             }
2502             break;
2503         case FIB_PATH_TYPE_BIER_TABLE:
2504             switch (fct)
2505             {
2506             case FIB_FORW_CHAIN_TYPE_BIER:
2507                 bier_table_contribute_forwarding(path->fp_via_bier_tbl, dpo);
2508                 break;
2509             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
2510             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2511             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2512             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2513             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2514             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2515             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2516             case FIB_FORW_CHAIN_TYPE_NSH:
2517                 ASSERT(0);
2518                 break;
2519             }
2520             break;
2521         case FIB_PATH_TYPE_BIER_FMASK:
2522             switch (fct)
2523             {
2524             case FIB_FORW_CHAIN_TYPE_BIER:
2525                 fib_path_bier_fmask_update(path, dpo);
2526                 break;
2527             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
2528             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2529             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2530             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2531             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2532             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2533             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2534             case FIB_FORW_CHAIN_TYPE_NSH:
2535                 ASSERT(0);
2536                 break;
2537             }
2538             break;
2539         case FIB_PATH_TYPE_BIER_IMP:
2540             bier_imp_contribute_forwarding(path->bier_imp.fp_bier_imp,
2541                                            fib_forw_chain_type_to_dpo_proto(fct),
2542                                            dpo);
2543             break;
2544         case FIB_PATH_TYPE_DEAG:
2545             switch (fct)
2546             {
2547             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2548                 lookup_dpo_add_or_lock_w_table_id(MPLS_FIB_DEFAULT_TABLE_ID,
2549                                                   DPO_PROTO_MPLS,
2550                                                   LOOKUP_UNICAST,
2551                                                   LOOKUP_INPUT_DST_ADDR,
2552                                                   LOOKUP_TABLE_FROM_CONFIG,
2553                                                   dpo);
2554                 break;
2555             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
2556             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2557             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2558             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2559             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2560                 dpo_copy(dpo, &path->fp_dpo);
2561                 break;
2562             case FIB_FORW_CHAIN_TYPE_BIER:
2563                 break;
2564             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2565             case FIB_FORW_CHAIN_TYPE_NSH:
2566                 ASSERT(0);
2567                 break;
2568             }
2569             break;
2570         case FIB_PATH_TYPE_EXCLUSIVE:
2571             dpo_copy(dpo, &path->exclusive.fp_ex_dpo);
2572             break;
2573         case FIB_PATH_TYPE_ATTACHED:
2574             switch (fct)
2575             {
2576             case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
2577                 /*
2578                  * End of stack traffic via an attacehd path (a glean)
2579                  * must forace an IP lookup so that the IP packet can
2580                  * match against any installed adj-fibs
2581                  */
2582                 lookup_dpo_add_or_lock_w_fib_index(
2583                     fib_table_get_index_for_sw_if_index(
2584                         dpo_proto_to_fib(payload_proto),
2585                         path->attached.fp_interface),
2586                     payload_proto,
2587                     LOOKUP_UNICAST,
2588                     LOOKUP_INPUT_DST_ADDR,
2589                     LOOKUP_TABLE_FROM_CONFIG,
2590                     dpo);
2591                 break;
2592             case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
2593             case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
2594             case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
2595             case FIB_FORW_CHAIN_TYPE_ETHERNET:
2596             case FIB_FORW_CHAIN_TYPE_NSH:
2597             case FIB_FORW_CHAIN_TYPE_BIER:
2598                 fib_path_attached_get_adj(path,
2599                                           fib_forw_chain_type_to_link_type(fct),
2600                                           dpo);
2601                 break;
2602             case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
2603             case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
2604                 {
2605                     adj_index_t ai;
2606
2607                     /*
2608                      * Create the adj needed for sending IP multicast traffic
2609                      */
2610                     if (vnet_sw_interface_is_p2p(vnet_get_main(),
2611                                                  path->attached.fp_interface))
2612                     {
2613                         /*
2614                          * point-2-point interfaces do not require a glean, since
2615                          * there is nothing to ARP. Install a rewrite/nbr adj instead
2616                          */
2617                         ai = adj_nbr_add_or_lock(dpo_proto_to_fib(path->fp_nh_proto),
2618                                                  fib_forw_chain_type_to_link_type(fct),
2619                                                  &zero_addr,
2620                                                  path->attached.fp_interface);
2621                     }
2622                     else
2623                     {
2624                         ai = adj_mcast_add_or_lock(dpo_proto_to_fib(path->fp_nh_proto),
2625                                                    fib_forw_chain_type_to_link_type(fct),
2626                                                    path->attached.fp_interface);
2627                     }
2628                     dpo_set(dpo, DPO_ADJACENCY,
2629                             fib_forw_chain_type_to_dpo_proto(fct),
2630                             ai);
2631                     adj_unlock(ai);
2632                 }
2633                 break;
2634             }
2635             break;
2636         case FIB_PATH_TYPE_INTF_RX:
2637             /*
2638              * Create the adj needed for sending IP multicast traffic
2639              */
2640             interface_rx_dpo_add_or_lock(payload_proto,
2641                                          path->intf_rx.fp_interface,
2642                                          dpo);
2643             break;
2644         case FIB_PATH_TYPE_UDP_ENCAP:
2645             udp_encap_contribute_forwarding(path->udp_encap.fp_udp_encap_id,
2646                                             path->fp_nh_proto,
2647                                             dpo);
2648             break;
2649         case FIB_PATH_TYPE_RECEIVE:
2650         case FIB_PATH_TYPE_SPECIAL:
2651         case FIB_PATH_TYPE_DVR:
2652             dpo_copy(dpo, &path->fp_dpo);
2653             break;
2654         }
2655     }
2656 }
2657
2658 load_balance_path_t *
2659 fib_path_append_nh_for_multipath_hash (fib_node_index_t path_index,
2660                                        fib_forward_chain_type_t fct,
2661                                        dpo_proto_t payload_proto,
2662                                        load_balance_path_t *hash_key)
2663 {
2664     load_balance_path_t *mnh;
2665     fib_path_t *path;
2666
2667     path = fib_path_get(path_index);
2668
2669     ASSERT(path);
2670
2671     vec_add2(hash_key, mnh, 1);
2672
2673     mnh->path_weight = path->fp_weight;
2674     mnh->path_index = path_index;
2675
2676     if (fib_path_is_resolved(path_index))
2677     {
2678         fib_path_contribute_forwarding(path_index, fct, payload_proto, &mnh->path_dpo);
2679     }
2680     else
2681     {
2682         dpo_copy(&mnh->path_dpo,
2683                  drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
2684     }
2685     return (hash_key);
2686 }
2687
2688 int
2689 fib_path_is_recursive_constrained (fib_node_index_t path_index)
2690 {
2691     fib_path_t *path;
2692
2693     path = fib_path_get(path_index);
2694
2695     return ((FIB_PATH_TYPE_RECURSIVE == path->fp_type) &&
2696             ((path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_ATTACHED) ||
2697              (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RESOLVE_HOST)));
2698 }
2699
2700 int
2701 fib_path_is_exclusive (fib_node_index_t path_index)
2702 {
2703     fib_path_t *path;
2704
2705     path = fib_path_get(path_index);
2706
2707     return (FIB_PATH_TYPE_EXCLUSIVE == path->fp_type);
2708 }
2709
2710 int
2711 fib_path_is_deag (fib_node_index_t path_index)
2712 {
2713     fib_path_t *path;
2714
2715     path = fib_path_get(path_index);
2716
2717     return (FIB_PATH_TYPE_DEAG == path->fp_type);
2718 }
2719
2720 int
2721 fib_path_is_resolved (fib_node_index_t path_index)
2722 {
2723     fib_path_t *path;
2724
2725     path = fib_path_get(path_index);
2726
2727     return (dpo_id_is_valid(&path->fp_dpo) &&
2728             (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RESOLVED) &&
2729             !fib_path_is_looped(path_index) &&
2730             !fib_path_is_permanent_drop(path));
2731 }
2732
2733 int
2734 fib_path_is_looped (fib_node_index_t path_index)
2735 {
2736     fib_path_t *path;
2737
2738     path = fib_path_get(path_index);
2739
2740     return (path->fp_oper_flags & FIB_PATH_OPER_FLAG_RECURSIVE_LOOP);
2741 }
2742
2743 fib_path_list_walk_rc_t
2744 fib_path_encode (fib_node_index_t path_list_index,
2745                  fib_node_index_t path_index,
2746                  const fib_path_ext_t *path_ext,
2747                  void *args)
2748 {
2749     fib_path_encode_ctx_t *ctx = args;
2750     fib_route_path_t *rpath;
2751     fib_path_t *path;
2752
2753     path = fib_path_get(path_index);
2754     if (!path)
2755       return (FIB_PATH_LIST_WALK_CONTINUE);
2756
2757     vec_add2(ctx->rpaths, rpath, 1);
2758     rpath->frp_weight = path->fp_weight;
2759     rpath->frp_preference = path->fp_preference;
2760     rpath->frp_proto = path->fp_nh_proto;
2761     rpath->frp_sw_if_index = ~0;
2762     rpath->frp_fib_index = 0;
2763
2764     switch (path->fp_type)
2765     {
2766       case FIB_PATH_TYPE_RECEIVE:
2767         rpath->frp_addr = path->receive.fp_addr;
2768         rpath->frp_sw_if_index = path->receive.fp_interface;
2769         rpath->frp_flags |= FIB_ROUTE_PATH_LOCAL;
2770         break;
2771       case FIB_PATH_TYPE_ATTACHED:
2772         rpath->frp_sw_if_index = path->attached.fp_interface;
2773         break;
2774       case FIB_PATH_TYPE_ATTACHED_NEXT_HOP:
2775         rpath->frp_sw_if_index = path->attached_next_hop.fp_interface;
2776         rpath->frp_addr = path->attached_next_hop.fp_nh;
2777         break;
2778       case FIB_PATH_TYPE_BIER_FMASK:
2779         rpath->frp_bier_fmask = path->bier_fmask.fp_bier_fmask;
2780         break;
2781       case FIB_PATH_TYPE_SPECIAL:
2782         break;
2783       case FIB_PATH_TYPE_DEAG:
2784         rpath->frp_fib_index = path->deag.fp_tbl_id;
2785         if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID)
2786         {
2787             rpath->frp_flags |= FIB_ROUTE_PATH_RPF_ID;
2788         }
2789         break;
2790       case FIB_PATH_TYPE_RECURSIVE:
2791         rpath->frp_addr = path->recursive.fp_nh.fp_ip;
2792         rpath->frp_fib_index = path->recursive.fp_tbl_id;
2793         break;
2794       case FIB_PATH_TYPE_DVR:
2795           rpath->frp_sw_if_index = path->dvr.fp_interface;
2796           rpath->frp_flags |= FIB_ROUTE_PATH_DVR;
2797           break;
2798       case FIB_PATH_TYPE_UDP_ENCAP:
2799           rpath->frp_udp_encap_id = path->udp_encap.fp_udp_encap_id;
2800           rpath->frp_flags |= FIB_ROUTE_PATH_UDP_ENCAP;
2801           break;
2802       case FIB_PATH_TYPE_INTF_RX:
2803           rpath->frp_sw_if_index = path->receive.fp_interface;
2804           rpath->frp_flags |= FIB_ROUTE_PATH_INTF_RX;
2805           break;
2806       case FIB_PATH_TYPE_EXCLUSIVE:
2807         rpath->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
2808       default:
2809         break;
2810     }
2811
2812     if (path_ext && path_ext->fpe_type == FIB_PATH_EXT_MPLS)
2813     {
2814         rpath->frp_label_stack = path_ext->fpe_path.frp_label_stack;
2815     }
2816
2817     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DROP)
2818         rpath->frp_flags |= FIB_ROUTE_PATH_DROP;
2819     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_UNREACH)
2820         rpath->frp_flags |= FIB_ROUTE_PATH_ICMP_UNREACH;
2821     if (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_ICMP_PROHIBIT)
2822         rpath->frp_flags |= FIB_ROUTE_PATH_ICMP_PROHIBIT;
2823
2824     return (FIB_PATH_LIST_WALK_CONTINUE);
2825 }
2826
2827 dpo_proto_t
2828 fib_path_get_proto (fib_node_index_t path_index)
2829 {
2830     fib_path_t *path;
2831
2832     path = fib_path_get(path_index);
2833
2834     return (path->fp_nh_proto);
2835 }
2836
2837 void
2838 fib_path_module_init (void)
2839 {
2840     fib_node_register_type (FIB_NODE_TYPE_PATH, &fib_path_vft);
2841     fib_path_logger = vlib_log_register_class ("fib", "path");
2842 }
2843
2844 static clib_error_t *
2845 show_fib_path_command (vlib_main_t * vm,
2846                         unformat_input_t * input,
2847                         vlib_cli_command_t * cmd)
2848 {
2849     fib_node_index_t pi;
2850     fib_path_t *path;
2851
2852     if (unformat (input, "%d", &pi))
2853     {
2854         /*
2855          * show one in detail
2856          */
2857         if (!pool_is_free_index(fib_path_pool, pi))
2858         {
2859             path = fib_path_get(pi);
2860             u8 *s = format(NULL, "%U", format_fib_path, pi, 1,
2861                            FIB_PATH_FORMAT_FLAGS_NONE);
2862             s = format(s, "\n  children:");
2863             s = fib_node_children_format(path->fp_node.fn_children, s);
2864             vlib_cli_output (vm, "%v", s);
2865             vec_free(s);
2866         }
2867         else
2868         {
2869             vlib_cli_output (vm, "path %d invalid", pi);
2870         }
2871     }
2872     else
2873     {
2874         vlib_cli_output (vm, "FIB Paths");
2875         pool_foreach_index (pi, fib_path_pool)
2876          {
2877             vlib_cli_output (vm, "%U", format_fib_path, pi, 0,
2878                              FIB_PATH_FORMAT_FLAGS_NONE);
2879         }
2880     }
2881
2882     return (NULL);
2883 }
2884
2885 VLIB_CLI_COMMAND (show_fib_path, static) = {
2886   .path = "show fib paths",
2887   .function = show_fib_path_command,
2888   .short_help = "show fib paths",
2889 };