src/vnet/fib/fib_path.c

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