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