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