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