src/vnet/fib/fib_path.c

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