src/vnet/fib/fib_entry.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/ip/format.h>
  18 #include <vnet/ip/lookup.h>
  19 #include <vnet/adj/adj.h>
  20 #include <vnet/dpo/load_balance.h>
  21 #include <vnet/dpo/drop_dpo.h>
  22
  23 #include <vnet/fib/fib_entry.h>
  24 #include <vnet/fib/fib_walk.h>
  25 #include <vnet/fib/fib_entry_src.h>
  26 #include <vnet/fib/fib_entry_cover.h>
  27 #include <vnet/fib/fib_table.h>
  28 #include <vnet/fib/fib_internal.h>
  29 #include <vnet/fib/fib_attached_export.h>
  30 #include <vnet/fib/fib_path_ext.h>
  31 #include <vnet/fib/fib_entry_delegate.h>
  32 #include <vnet/fib/fib_entry_track.h>
  33
  34 /*
  35  * Array of strings/names for the FIB sources
  36  */
  37 static const char *fib_attribute_names[] = FIB_ENTRY_ATTRIBUTES;
  38 static const char *fib_src_attribute_names[] = FIB_ENTRY_SRC_ATTRIBUTES;
  39
  40 /*
  41  * Pool for all fib_entries
  42  */
  43 static fib_entry_t *fib_entry_pool;
  44
  45 /**
  46  * the logger
  47  */
  48 vlib_log_class_t fib_entry_logger;
  49
  50 fib_entry_t *
  51 fib_entry_get (fib_node_index_t index)
  52 {
  53     return (pool_elt_at_index(fib_entry_pool, index));
  54 }
  55
  56 static fib_node_t *
  57 fib_entry_get_node (fib_node_index_t index)
  58 {
  59     return ((fib_node_t*)fib_entry_get(index));
  60 }
  61
  62 fib_node_index_t
  63 fib_entry_get_index (const fib_entry_t * fib_entry)
  64 {
  65     return (fib_entry - fib_entry_pool);
  66 }
  67
  68 fib_protocol_t
  69 fib_entry_get_proto (const fib_entry_t * fib_entry)
  70 {
  71     return (fib_entry->fe_prefix.fp_proto);
  72 }
  73
  74 dpo_proto_t
  75 fib_entry_get_dpo_proto (const fib_entry_t * fib_entry)
  76 {
  77     return (fib_proto_to_dpo(fib_entry->fe_prefix.fp_proto));
  78 }
  79
  80 fib_forward_chain_type_t
  81 fib_entry_get_default_chain_type (const fib_entry_t *fib_entry)
  82 {
  83     switch (fib_entry->fe_prefix.fp_proto)
  84     {
  85     case FIB_PROTOCOL_IP4:
  86         return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
  87     case FIB_PROTOCOL_IP6:
  88         return (FIB_FORW_CHAIN_TYPE_UNICAST_IP6);
  89     case FIB_PROTOCOL_MPLS:
  90         if (MPLS_EOS == fib_entry->fe_prefix.fp_eos)
  91             return (FIB_FORW_CHAIN_TYPE_MPLS_EOS);
  92         else
  93             return (FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS);
  94     }
  95
  96     return (FIB_FORW_CHAIN_TYPE_UNICAST_IP4);
  97 }
  98
  99 u8 *
 100 format_fib_entry_flags (u8 *s, va_list *args)
 101 {
 102     fib_entry_attribute_t attr;
 103     fib_entry_flag_t flag = va_arg(*args, int);
 104
 105     FOR_EACH_FIB_ATTRIBUTE(attr) {
 106         if ((1<<attr) & flag) {
 107             s = format (s, "%s,", fib_attribute_names[attr]);
 108         }
 109     }
 110
 111     return (s);
 112 }
 113
 114 u8 *
 115 format_fib_entry_src_flags (u8 *s, va_list *args)
 116 {
 117     fib_entry_src_attribute_t sattr;
 118     fib_entry_src_flag_t flag = va_arg(*args, int);
 119
 120     FOR_EACH_FIB_SRC_ATTRIBUTE(sattr) {
 121         if ((1<<sattr) & flag) {
 122             s = format (s, "%s,", fib_src_attribute_names[sattr]);
 123         }
 124     }
 125
 126     return (s);
 127 }
 128
 129 u8 *
 130 format_fib_entry (u8 * s, va_list * args)
 131 {
 132     fib_forward_chain_type_t fct;
 133     fib_entry_t *fib_entry;
 134     fib_entry_src_t *src;
 135     fib_node_index_t fei;
 136     fib_source_t source;
 137     int level;
 138
 139     fei = va_arg (*args, fib_node_index_t);
 140     level = va_arg (*args, int);
 141     fib_entry = fib_entry_get(fei);
 142
 143     s = format (s, "%U", format_fib_prefix, &fib_entry->fe_prefix);
 144
 145     if (level >= FIB_ENTRY_FORMAT_DETAIL)
 146     {
 147         s = format (s, " fib:%d", fib_entry->fe_fib_index);
 148         s = format (s, " index:%d", fib_entry_get_index(fib_entry));
 149         s = format (s, " locks:%d", fib_entry->fe_node.fn_locks);
 150
 151         FOR_EACH_SRC_ADDED(fib_entry, src, source,
 152         ({
 153             s = format (s, "\n  %U", format_fib_source, source);
 154             s = format (s, " refs:%d", src->fes_ref_count);
 155             if (FIB_ENTRY_FLAG_NONE != src->fes_entry_flags) {
 156                 s = format(s, " entry-flags:%U",
 157                            format_fib_entry_flags, src->fes_entry_flags);
 158             }
 159             if (FIB_ENTRY_SRC_FLAG_NONE != src->fes_flags) {
 160                 s = format(s, " src-flags:%U",
 161                            format_fib_entry_src_flags, src->fes_flags);
 162             }
 163             s = fib_entry_src_format(fib_entry, source, s);
 164             s = format (s, "\n");
 165             if (FIB_NODE_INDEX_INVALID != src->fes_pl)
 166             {
 167                 s = fib_path_list_format(src->fes_pl, s);
 168             }
 169             s = format(s, "%U", format_fib_path_ext_list, &src->fes_path_exts);
 170         }));
 171
 172         s = format (s, "\n forwarding: ");
 173     }
 174     else
 175     {
 176         s = format (s, "\n");
 177     }
 178
 179     fct = fib_entry_get_default_chain_type(fib_entry);
 180
 181     if (!dpo_id_is_valid(&fib_entry->fe_lb))
 182     {
 183         s = format (s, "  UNRESOLVED\n");
 184         return (s);
 185     }
 186     else
 187     {
 188         s = format(s, "  %U-chain\n  %U",
 189                    format_fib_forw_chain_type, fct,
 190                    format_dpo_id,
 191                    &fib_entry->fe_lb,
 192                    2);
 193         s = format(s, "\n");
 194
 195         if (level >= FIB_ENTRY_FORMAT_DETAIL2)
 196         {
 197             index_t *fedi;
 198
 199             s = format (s, " Delegates:\n");
 200             vec_foreach(fedi, fib_entry->fe_delegates)
 201             {
 202                 s = format(s, "  %U\n", format_fib_entry_delegate, *fedi);
 203             }
 204         }
 205     }
 206
 207     if (level >= FIB_ENTRY_FORMAT_DETAIL2)
 208     {
 209         s = format(s, " Children:");
 210         s = fib_node_children_format(fib_entry->fe_node.fn_children, s);
 211     }
 212
 213     return (s);
 214 }
 215
 216 static fib_entry_t*
 217 fib_entry_from_fib_node (fib_node_t *node)
 218 {
 219     ASSERT(FIB_NODE_TYPE_ENTRY == node->fn_type);
 220     return ((fib_entry_t*)node);
 221 }
 222
 223 static void
 224 fib_entry_last_lock_gone (fib_node_t *node)
 225 {
 226     fib_entry_delegate_type_t fdt;
 227     fib_entry_delegate_t *fed;
 228     fib_entry_t *fib_entry;
 229
 230     fib_entry = fib_entry_from_fib_node(node);
 231
 232     ASSERT(!dpo_id_is_valid(&fib_entry->fe_lb));
 233
 234     FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
 235     {
 236         dpo_reset(&fed->fd_dpo);
 237         fib_entry_delegate_remove(fib_entry, fdt);
 238     });
 239
 240     FIB_ENTRY_DBG(fib_entry, "last-lock");
 241
 242     fib_node_deinit(&fib_entry->fe_node);
 243
 244     ASSERT(0 == vec_len(fib_entry->fe_delegates));
 245     vec_free(fib_entry->fe_delegates);
 246     vec_free(fib_entry->fe_srcs);
 247     pool_put(fib_entry_pool, fib_entry);
 248 }
 249
 250 static fib_entry_src_t*
 251 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
 252 {
 253     fib_entry_src_t *bsrc;
 254
 255     /*
 256      * the enum of sources is deliberately arranged in priority order
 257      */
 258     if (0 == vec_len(fib_entry->fe_srcs))
 259     {
 260         bsrc = NULL;
 261     }
 262     else
 263     {
 264         bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
 265     }
 266
 267     return (bsrc);
 268 }
 269
 270 static fib_source_t
 271 fib_entry_src_get_source (const fib_entry_src_t *esrc)
 272 {
 273     if (NULL != esrc)
 274     {
 275         return (esrc->fes_src);
 276     }
 277     return (FIB_SOURCE_INVALID);
 278 }
 279
 280 static fib_entry_flag_t
 281 fib_entry_src_get_flags (const fib_entry_src_t *esrc)
 282 {
 283     if (NULL != esrc)
 284     {
 285         return (esrc->fes_entry_flags);
 286     }
 287     return (FIB_ENTRY_FLAG_NONE);
 288 }
 289
 290 fib_entry_flag_t
 291 fib_entry_get_flags (fib_node_index_t fib_entry_index)
 292 {
 293     return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
 294 }
 295
 296 /*
 297  * fib_entry_back_walk_notify
 298  *
 299  * A back walk has reach this entry.
 300  */
 301 static fib_node_back_walk_rc_t
 302 fib_entry_back_walk_notify (fib_node_t *node,
 303                             fib_node_back_walk_ctx_t *ctx)
 304 {
 305     fib_entry_t *fib_entry;
 306
 307     fib_entry = fib_entry_from_fib_node(node);
 308
 309     if (FIB_NODE_BW_REASON_FLAG_EVALUATE & ctx->fnbw_reason        ||
 310         FIB_NODE_BW_REASON_FLAG_ADJ_UPDATE & ctx->fnbw_reason      ||
 311         FIB_NODE_BW_REASON_FLAG_ADJ_DOWN & ctx->fnbw_reason        ||
 312         FIB_NODE_BW_REASON_FLAG_INTERFACE_UP & ctx->fnbw_reason    ||
 313         FIB_NODE_BW_REASON_FLAG_INTERFACE_DOWN & ctx->fnbw_reason  ||
 314         FIB_NODE_BW_REASON_FLAG_INTERFACE_DELETE & ctx->fnbw_reason)
 315     {
 316         fib_entry_src_action_reactivate(fib_entry,
 317                                         fib_entry_get_best_source(
 318                                             fib_entry_get_index(fib_entry)));
 319     }
 320
 321     /*
 322      * all other walk types can be reclassifed to a re-evaluate to
 323      * all recursive dependents.
 324      * By reclassifying we ensure that should any of these walk types meet
 325      * they can be merged.
 326      */
 327     ctx->fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE;
 328
 329     /*
 330      * ... and nothing is forced sync from now on.
 331      */
 332     ctx->fnbw_flags &= ~FIB_NODE_BW_FLAG_FORCE_SYNC;
 333
 334     FIB_ENTRY_DBG(fib_entry, "bw:%U",
 335                   format_fib_node_bw_reason, ctx->fnbw_reason);
 336
 337     /*
 338      * propagate the backwalk further if we haven't already reached the
 339      * maximum depth.
 340      */
 341     fib_walk_sync(FIB_NODE_TYPE_ENTRY,
 342                   fib_entry_get_index(fib_entry),
 343                   ctx);
 344
 345     return (FIB_NODE_BACK_WALK_CONTINUE);
 346 }
 347
 348 static void
 349 fib_entry_show_memory (void)
 350 {
 351     u32 n_srcs = 0, n_exts = 0;
 352     fib_entry_src_t *esrc;
 353     fib_entry_t *entry;
 354
 355     fib_show_memory_usage("Entry",
 356                           pool_elts(fib_entry_pool),
 357                           pool_len(fib_entry_pool),
 358                           sizeof(fib_entry_t));
 359
 360     pool_foreach (entry, fib_entry_pool)
 361      {
 362         n_srcs += vec_len(entry->fe_srcs);
 363         vec_foreach(esrc, entry->fe_srcs)
 364         {
 365             n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
 366         }
 367     }
 368
 369     fib_show_memory_usage("Entry Source",
 370                           n_srcs, n_srcs, sizeof(fib_entry_src_t));
 371     fib_show_memory_usage("Entry Path-Extensions",
 372                           n_exts, n_exts,
 373                           sizeof(fib_path_ext_t));
 374 }
 375
 376 /*
 377  * The FIB path-list's graph node virtual function table
 378  */
 379 static const fib_node_vft_t fib_entry_vft = {
 380     .fnv_get = fib_entry_get_node,
 381     .fnv_last_lock = fib_entry_last_lock_gone,
 382     .fnv_back_walk = fib_entry_back_walk_notify,
 383     .fnv_mem_show = fib_entry_show_memory,
 384 };
 385
 386 /**
 387  * @brief Contribute the set of Adjacencies that this entry forwards with
 388  * to build the uRPF list of its children
 389  */
 390 void
 391 fib_entry_contribute_urpf (fib_node_index_t entry_index,
 392                            index_t urpf)
 393 {
 394     fib_entry_t *fib_entry;
 395
 396     fib_entry = fib_entry_get(entry_index);
 397
 398     return (fib_path_list_contribute_urpf(fib_entry->fe_parent, urpf));
 399 }
 400
 401 /*
 402  * If the client is request a chain for multicast forwarding then swap
 403  * the chain type to one that can provide such transport.
 404  */
 405 static fib_forward_chain_type_t
 406 fib_entry_chain_type_mcast_to_ucast (fib_forward_chain_type_t fct)
 407 {
 408     switch (fct)
 409     {
 410     case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
 411     case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
 412         /*
 413          * we can only transport IP multicast packets if there is an
 414          * LSP.
 415          */
 416         fct = FIB_FORW_CHAIN_TYPE_MPLS_EOS;
 417         break;
 418     case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
 419     case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
 420     case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
 421     case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
 422     case FIB_FORW_CHAIN_TYPE_ETHERNET:
 423     case FIB_FORW_CHAIN_TYPE_NSH:
 424     case FIB_FORW_CHAIN_TYPE_BIER:
 425         break;
 426     }
 427
 428     return (fct);
 429 }
 430
 431 /*
 432  * fib_entry_contribute_forwarding
 433  *
 434  * Get an lock the forwarding information (DPO) contributed by the FIB entry.
 435  */
 436 void
 437 fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
 438                                  fib_forward_chain_type_t fct,
 439                                  dpo_id_t *dpo)
 440 {
 441     fib_entry_delegate_t *fed;
 442     fib_entry_t *fib_entry;
 443
 444     fib_entry = fib_entry_get(fib_entry_index);
 445
 446     /*
 447      * mfib children ask for mcast chains. fix these to the appropriate ucast types.
 448      */
 449     fct = fib_entry_chain_type_mcast_to_ucast(fct);
 450
 451     if (fct == fib_entry_get_default_chain_type(fib_entry))
 452     {
 453         dpo_copy(dpo, &fib_entry->fe_lb);
 454     }
 455     else
 456     {
 457         fed = fib_entry_delegate_find(fib_entry,
 458                                       fib_entry_chain_type_to_delegate_type(fct));
 459
 460         if (NULL == fed)
 461         {
 462             /*
 463              * use a temporary DPO lest the delegate realloc in the recursive
 464              * calculation.
 465              */
 466             dpo_id_t tmp = DPO_INVALID;
 467
 468             /*
 469              * on-demand create eos/non-eos.
 470              * There is no on-demand delete because:
 471              *   - memory versus complexity & reliability:
 472              *      leaving unrequired [n]eos LB arounds wastes memory, cleaning
 473              *      then up on the right trigger is more code. i favour the latter.
 474              */
 475             fib_entry_src_mk_lb(fib_entry,
 476                                 fib_entry_get_best_source(fib_entry_index),
 477                                 fct,
 478                                 &tmp);
 479
 480             fed = fib_entry_delegate_find_or_add(
 481                 fib_entry,
 482                 fib_entry_chain_type_to_delegate_type(fct));
 483
 484             dpo_copy(&fed->fd_dpo, &tmp);
 485             dpo_reset(&tmp);
 486         }
 487
 488         dpo_copy(dpo, &fed->fd_dpo);
 489     }
 490     /*
 491      * use the drop DPO is nothing else is present
 492      */
 493     if (!dpo_id_is_valid(dpo))
 494     {
 495         dpo_copy(dpo, drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
 496     }
 497
 498     /*
 499      * don't allow the special index indicating replicate.vs.load-balance
 500      * to escape to the clients
 501      */
 502     dpo->dpoi_index &= ~MPLS_IS_REPLICATE;
 503 }
 504
 505 const dpo_id_t *
 506 fib_entry_contribute_ip_forwarding (fib_node_index_t fib_entry_index)
 507 {
 508     fib_forward_chain_type_t fct;
 509     fib_entry_t *fib_entry;
 510
 511     fib_entry = fib_entry_get(fib_entry_index);
 512     fct = fib_entry_get_default_chain_type(fib_entry);
 513
 514     ASSERT((fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP4 ||
 515             fct == FIB_FORW_CHAIN_TYPE_UNICAST_IP6));
 516
 517     if (dpo_id_is_valid(&fib_entry->fe_lb))
 518     {
 519         return (&fib_entry->fe_lb);
 520     }
 521
 522     return (drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct)));
 523 }
 524
 525 adj_index_t
 526 fib_entry_get_adj (fib_node_index_t fib_entry_index)
 527 {
 528     const dpo_id_t *dpo;
 529
 530     dpo = fib_entry_contribute_ip_forwarding(fib_entry_index);
 531
 532     if (dpo_id_is_valid(dpo))
 533     {
 534         dpo = load_balance_get_bucket(dpo->dpoi_index, 0);
 535
 536         if (dpo_is_adj(dpo))
 537         {
 538             return (dpo->dpoi_index);
 539         }
 540     }
 541     return (ADJ_INDEX_INVALID);
 542 }
 543
 544 fib_node_index_t
 545 fib_entry_get_path_list (fib_node_index_t fib_entry_index)
 546 {
 547     fib_entry_t *fib_entry;
 548
 549     fib_entry = fib_entry_get(fib_entry_index);
 550
 551     return (fib_entry->fe_parent);
 552 }
 553
 554 u32
 555 fib_entry_child_add (fib_node_index_t fib_entry_index,
 556                      fib_node_type_t child_type,
 557                      fib_node_index_t child_index)
 558 {
 559     return (fib_node_child_add(FIB_NODE_TYPE_ENTRY,
 560                                fib_entry_index,
 561                                child_type,
 562                                child_index));
 563 };
 564
 565 void
 566 fib_entry_child_remove (fib_node_index_t fib_entry_index,
 567                         u32 sibling_index)
 568 {
 569     fib_node_child_remove(FIB_NODE_TYPE_ENTRY,
 570                           fib_entry_index,
 571                           sibling_index);
 572
 573     if (0 == fib_node_get_n_children(FIB_NODE_TYPE_ENTRY,
 574                                      fib_entry_index))
 575     {
 576         /*
 577          * if there are no children left then there is no reason to keep
 578          * the non-default forwarding chains. those chains are built only
 579          * because the children want them.
 580          */
 581         fib_entry_delegate_type_t fdt;
 582         fib_entry_delegate_t *fed;
 583         fib_entry_t *fib_entry;
 584
 585         fib_entry = fib_entry_get(fib_entry_index);
 586
 587         FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
 588         {
 589             dpo_reset(&fed->fd_dpo);
 590             fib_entry_delegate_remove(fib_entry, fdt);
 591         });
 592     }
 593 }
 594
 595 static fib_entry_t *
 596 fib_entry_alloc (u32 fib_index,
 597                  const fib_prefix_t *prefix,
 598                  fib_node_index_t *fib_entry_index)
 599 {
 600     fib_entry_t *fib_entry;
 601     fib_prefix_t *fep;
 602     u8 need_barrier_sync = 0;
 603     vlib_main_t *vm = vlib_get_main();
 604     ASSERT (vm->thread_index == 0);
 605
 606     pool_get_will_expand (fib_entry_pool, need_barrier_sync );
 607     if (need_barrier_sync)
 608         vlib_worker_thread_barrier_sync (vm);
 609
 610     pool_get(fib_entry_pool, fib_entry);
 611
 612     if (need_barrier_sync)
 613         vlib_worker_thread_barrier_release (vm);
 614
 615     clib_memset(fib_entry, 0, sizeof(*fib_entry));
 616
 617     fib_node_init(&fib_entry->fe_node,
 618                   FIB_NODE_TYPE_ENTRY);
 619
 620     fib_entry->fe_fib_index = fib_index;
 621
 622     /*
 623      * the one time we need to update the const prefix is when
 624      * the entry is first created
 625      */
 626     fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
 627     *fep = *prefix;
 628
 629     if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
 630     {
 631         fep->fp_len = 21;
 632         if (MPLS_NON_EOS == fep->fp_eos)
 633         {
 634             fep->fp_payload_proto = DPO_PROTO_MPLS;
 635         }
 636         ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
 637     }
 638
 639     dpo_reset(&fib_entry->fe_lb);
 640
 641     *fib_entry_index = fib_entry_get_index(fib_entry);
 642
 643     return (fib_entry);
 644 }
 645
 646 static fib_entry_t*
 647 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
 648                                     fib_entry_flag_t old_flags)
 649 {
 650     fib_node_index_t fei;
 651
 652     /*
 653      * save the index so we can recover from pool reallocs
 654      */
 655     fei = fib_entry_get_index(fib_entry);
 656
 657     /*
 658      * handle changes to attached export for import entries
 659      */
 660     int is_import  = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
 661     int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
 662
 663     if (!was_import && is_import)
 664     {
 665         /*
 666          * transition from not exported to exported
 667          */
 668
 669         /*
 670          * there is an assumption here that the entry resolves via only
 671          * one interface and that it is the cross VRF interface.
 672          */
 673         u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
 674
 675         fib_attached_export_import(fib_entry,
 676                                    fib_table_get_index_for_sw_if_index(
 677                                        fib_entry_get_proto(fib_entry),
 678                                        sw_if_index));
 679     }
 680     else if (was_import && !is_import)
 681     {
 682         /*
 683          * transition from exported to not exported
 684          */
 685         fib_attached_export_purge(fib_entry);
 686     }
 687     /*
 688      * else
 689      *   no change. nothing to do.
 690      */
 691
 692     /*
 693      * reload the entry address post possible pool realloc
 694      */
 695     fib_entry = fib_entry_get(fei);
 696
 697     /*
 698      * handle changes to attached export for export entries
 699      */
 700     int is_attached  = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
 701     int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
 702
 703     if (!was_attached && is_attached)
 704     {
 705         /*
 706          * transition to attached. time to export
 707          */
 708         // FIXME
 709     }
 710     // else FIXME
 711
 712     return (fib_entry);
 713 }
 714
 715 static fib_entry_t*
 716 fib_entry_post_install_actions (fib_entry_t *fib_entry,
 717                                 fib_source_t source,
 718                                 fib_entry_flag_t old_flags)
 719 {
 720     fib_entry = fib_entry_post_flag_update_actions(fib_entry,
 721                                                    old_flags);
 722     fib_entry = fib_entry_src_action_installed(fib_entry, source);
 723
 724     return (fib_entry);
 725 }
 726
 727 fib_node_index_t
 728 fib_entry_create (u32 fib_index,
 729                   const fib_prefix_t *prefix,
 730                   fib_source_t source,
 731                   fib_entry_flag_t flags,
 732                   const fib_route_path_t *paths)
 733 {
 734     fib_node_index_t fib_entry_index;
 735     fib_entry_t *fib_entry;
 736
 737     ASSERT(0 < vec_len(paths));
 738
 739     fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
 740
 741     /*
 742      * since this is a new entry create, we don't need to check for winning
 743      * sources - there is only one.
 744      */
 745     fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
 746                                          drop_dpo_get(
 747                                              fib_proto_to_dpo(
 748                                                  fib_entry_get_proto(fib_entry))));
 749     fib_entry_src_action_path_swap(fib_entry,
 750                                    source,
 751                                    flags,
 752                                    paths);
 753     /*
 754      * handle possible realloc's by refetching the pointer
 755      */
 756     fib_entry = fib_entry_get(fib_entry_index);
 757     fib_entry_src_action_activate(fib_entry, source);
 758
 759     fib_entry = fib_entry_post_install_actions(fib_entry, source,
 760                                                FIB_ENTRY_FLAG_NONE);
 761
 762     FIB_ENTRY_DBG(fib_entry, "create");
 763
 764     return (fib_entry_index);
 765 }
 766
 767 fib_node_index_t
 768 fib_entry_create_special (u32 fib_index,
 769                           const fib_prefix_t *prefix,
 770                           fib_source_t source,
 771                           fib_entry_flag_t flags,
 772                           const dpo_id_t *dpo)
 773 {
 774     fib_node_index_t fib_entry_index;
 775     fib_entry_t *fib_entry;
 776
 777     /*
 778      * create and initialize the new enty
 779      */
 780     fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
 781
 782     /*
 783      * create the path-list
 784      */
 785     fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
 786     fib_entry_src_action_activate(fib_entry, source);
 787
 788     fib_entry = fib_entry_post_install_actions(fib_entry, source,
 789                                                FIB_ENTRY_FLAG_NONE);
 790
 791     FIB_ENTRY_DBG(fib_entry, "create-special");
 792
 793     return (fib_entry_index);
 794 }
 795
 796 static void
 797 fib_entry_post_update_actions (fib_entry_t *fib_entry,
 798                                fib_source_t source,
 799                                fib_entry_flag_t old_flags)
 800 {
 801     /*
 802      * backwalk to children to inform then of the change to forwarding.
 803      */
 804     fib_node_back_walk_ctx_t bw_ctx = {
 805         .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
 806     };
 807
 808     fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
 809
 810     /*
 811      * then inform any covered prefixes
 812      */
 813     fib_entry_cover_update_notify(fib_entry);
 814
 815     fib_entry_post_install_actions(fib_entry, source, old_flags);
 816 }
 817
 818 void
 819 fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
 820 {
 821     fib_source_t best_source;
 822     fib_entry_t *fib_entry;
 823     fib_entry_src_t *bsrc;
 824
 825     fib_entry = fib_entry_get(fib_entry_index);
 826
 827     bsrc = fib_entry_get_best_src_i(fib_entry);
 828     best_source = fib_entry_src_get_source(bsrc);
 829
 830     fib_entry_src_action_reactivate(fib_entry, best_source);
 831 }
 832
 833 static void
 834 fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
 835                                  fib_source_t old_source,
 836                                  fib_entry_flag_t old_flags,
 837                                  fib_source_t new_source)
 838 {
 839     switch (fib_source_cmp(new_source, old_source))
 840     {
 841     case FIB_SOURCE_CMP_BETTER:
 842         /*
 843          * we have a new winning source.
 844          */
 845         fib_entry_src_action_deactivate(fib_entry, old_source);
 846         fib_entry_src_action_activate(fib_entry, new_source);
 847         break;
 848
 849     case FIB_SOURCE_CMP_WORSE:
 850         /*
 851          * the new source loses. Re-activate the winning sources
 852          * in case it is an interposer and hence relied on the losing
 853          * source's path-list.
 854          */
 855         fib_entry_src_action_reactivate(fib_entry, old_source);
 856         return;
 857
 858     case FIB_SOURCE_CMP_EQUAL:
 859         /*
 860          * the new source is one this entry already has.
 861          * But the path-list was updated, which will contribute new forwarding,
 862          * so install it.
 863          */
 864         fib_entry_src_action_reactivate(fib_entry, new_source);
 865         break;
 866     }
 867
 868     fib_entry_post_update_actions(fib_entry, new_source, old_flags);
 869 }
 870
 871 void
 872 fib_entry_source_change (fib_entry_t *fib_entry,
 873                          fib_source_t old_source,
 874                          fib_source_t new_source)
 875 {
 876     fib_entry_flag_t old_flags;
 877
 878     old_flags = fib_entry_get_flags_for_source(
 879         fib_entry_get_index(fib_entry), old_source);
 880
 881     return (fib_entry_source_change_w_flags(fib_entry, old_source,
 882                                             old_flags, new_source));
 883 }
 884
 885 void
 886 fib_entry_special_add (fib_node_index_t fib_entry_index,
 887                        fib_source_t source,
 888                        fib_entry_flag_t flags,
 889                        const dpo_id_t *dpo)
 890 {
 891     fib_source_t best_source;
 892     fib_entry_t *fib_entry;
 893
 894     fib_entry = fib_entry_get(fib_entry_index);
 895     best_source = fib_entry_get_best_source(fib_entry_index);
 896
 897     fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
 898     fib_entry_source_change(fib_entry, best_source, source);
 899     FIB_ENTRY_DBG(fib_entry, "special-add:%U", format_fib_source, source);
 900 }
 901
 902 void
 903 fib_entry_special_update (fib_node_index_t fib_entry_index,
 904                           fib_source_t source,
 905                           fib_entry_flag_t flags,
 906                           const dpo_id_t *dpo)
 907 {
 908     fib_source_t best_source;
 909     fib_entry_t *fib_entry;
 910
 911     fib_entry = fib_entry_get(fib_entry_index);
 912     best_source = fib_entry_get_best_source(fib_entry_index);
 913
 914     fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
 915     fib_entry_source_change(fib_entry, best_source, source);
 916
 917     FIB_ENTRY_DBG(fib_entry, "special-updated:%U", format_fib_source, source);
 918 }
 919
 920
 921 void
 922 fib_entry_path_add (fib_node_index_t fib_entry_index,
 923                     fib_source_t source,
 924                     fib_entry_flag_t flags,
 925                     const fib_route_path_t *rpaths)
 926 {
 927     fib_source_t best_source;
 928     fib_entry_t *fib_entry;
 929     fib_entry_src_t *bsrc;
 930
 931     fib_entry = fib_entry_get(fib_entry_index);
 932     ASSERT(NULL != fib_entry);
 933
 934     bsrc = fib_entry_get_best_src_i(fib_entry);
 935     best_source = fib_entry_src_get_source(bsrc);
 936
 937     fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpaths);
 938
 939     fib_entry_source_change(fib_entry, best_source, source);
 940
 941     FIB_ENTRY_DBG(fib_entry, "path add:%U", format_fib_source, source);
 942 }
 943
 944 static fib_entry_src_flag_t
 945 fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
 946 {
 947     fib_entry_src_t *src;
 948     fib_source_t source;
 949     int has_only_inherited_sources = 1;
 950
 951     FOR_EACH_SRC_ADDED(fib_entry, src, source,
 952     ({
 953         if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 954         {
 955             has_only_inherited_sources = 0;
 956             break;
 957         }
 958     }));
 959     if (has_only_inherited_sources)
 960     {
 961         FOR_EACH_SRC_ADDED(fib_entry, src, source,
 962         ({
 963             fib_entry_src_action_remove(fib_entry, source);
 964         }));
 965         return (FIB_ENTRY_SRC_FLAG_NONE);
 966     }
 967     else
 968     {
 969         return (FIB_ENTRY_SRC_FLAG_ADDED);
 970     }
 971 }
 972
 973 static fib_entry_src_flag_t
 974 fib_entry_source_removed (fib_entry_t *fib_entry,
 975                           fib_entry_flag_t old_flags)
 976 {
 977     const fib_entry_src_t *bsrc;
 978     fib_source_t best_source;
 979
 980     /*
 981      * if all that is left are inherited sources, then burn them
 982      */
 983     fib_entry_src_burn_only_inherited(fib_entry);
 984
 985     bsrc = fib_entry_get_best_src_i(fib_entry);
 986     best_source = fib_entry_src_get_source(bsrc);
 987
 988     if (FIB_SOURCE_INVALID == best_source)
 989     {
 990         /*
 991          * no more sources left. this entry is toast.
 992          */
 993         fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
 994         fib_entry_src_action_uninstall(fib_entry);
 995
 996         return (FIB_ENTRY_SRC_FLAG_NONE);
 997     }
 998     else
 999     {
1000         fib_entry_src_action_activate(fib_entry, best_source);
1001     }
1002
1003     fib_entry_post_update_actions(fib_entry, best_source, old_flags);
1004
1005     /*
1006      * still have sources
1007      */
1008     return (FIB_ENTRY_SRC_FLAG_ADDED);
1009 }
1010
1011 /*
1012  * fib_entry_path_remove
1013  *
1014  * remove a path from the entry.
1015  * return the fib_entry's index if it is still present, INVALID otherwise.
1016  */
1017 fib_entry_src_flag_t
1018 fib_entry_path_remove (fib_node_index_t fib_entry_index,
1019                        fib_source_t source,
1020                        const fib_route_path_t *rpaths)
1021 {
1022     fib_entry_src_flag_t sflag;
1023     fib_source_t best_source;
1024     fib_entry_flag_t bflags;
1025     fib_entry_t *fib_entry;
1026     fib_entry_src_t *bsrc;
1027
1028     fib_entry = fib_entry_get(fib_entry_index);
1029     ASSERT(NULL != fib_entry);
1030
1031     bsrc = fib_entry_get_best_src_i(fib_entry);
1032     best_source = fib_entry_src_get_source(bsrc);
1033     bflags = fib_entry_src_get_flags(bsrc);
1034
1035     sflag = fib_entry_src_action_path_remove(fib_entry, source, rpaths);
1036
1037     FIB_ENTRY_DBG(fib_entry, "path remove:%U", format_fib_source, source);
1038
1039     /*
1040      * if the path list for the source passed is invalid,
1041      * then we need to create a new one. else we are updating
1042      * an existing.
1043      */
1044     switch (fib_source_cmp(source, best_source))
1045     {
1046     case FIB_SOURCE_CMP_BETTER:
1047         /*
1048          * Que! removing a path from a source that is better than the
1049          * one this entry is using.
1050          */
1051         ASSERT(0);
1052         break;
1053     case FIB_SOURCE_CMP_WORSE:
1054         /*
1055          * the source is not the best. no need to update forwarding
1056          */
1057         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1058         {
1059             /*
1060              * the source being removed still has paths
1061              */
1062             return (FIB_ENTRY_SRC_FLAG_ADDED);
1063         }
1064         else
1065         {
1066             /*
1067              * that was the last path from this source, check if those
1068              * that remain are non-inherited
1069              */
1070             return (fib_entry_src_burn_only_inherited(fib_entry));
1071         }
1072         break;
1073     case FIB_SOURCE_CMP_EQUAL:
1074         /*
1075          * removing a path from the path-list we were using.
1076          */
1077         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1078         {
1079             /*
1080              * the last path from the source was removed.
1081              * fallback to lower source
1082              */
1083             return (fib_entry_source_removed(fib_entry, bflags));
1084         }
1085         else
1086         {
1087             /*
1088              * re-install the new forwarding information
1089              */
1090             fib_entry_src_action_reactivate(fib_entry, source);
1091         }
1092         break;
1093     }
1094
1095     fib_entry_post_update_actions(fib_entry, source, bflags);
1096
1097     /*
1098      * still have sources
1099      */
1100     return (FIB_ENTRY_SRC_FLAG_ADDED);
1101 }
1102
1103 /*
1104  * fib_entry_special_remove
1105  *
1106  * remove a special source from the entry.
1107  * return the fib_entry's index if it is still present, INVALID otherwise.
1108  */
1109 fib_entry_src_flag_t
1110 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1111                           fib_source_t source)
1112 {
1113     fib_entry_src_flag_t sflag;
1114     fib_source_t best_source;
1115     fib_entry_flag_t bflags;
1116     fib_entry_t *fib_entry;
1117     fib_entry_src_t *bsrc;
1118
1119     fib_entry = fib_entry_get(fib_entry_index);
1120     ASSERT(NULL != fib_entry);
1121
1122     bsrc = fib_entry_get_best_src_i(fib_entry);
1123     best_source = fib_entry_src_get_source(bsrc);
1124     bflags = fib_entry_src_get_flags(bsrc);
1125
1126     FIB_ENTRY_DBG(fib_entry, "special remove:%U", format_fib_source, source);
1127
1128     sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1129
1130     /*
1131      * if the path list for the source passed is invalid,
1132      * then we need to create a new one. else we are updating
1133      * an existing.
1134      */
1135     switch (fib_source_cmp(source, best_source))
1136     {
1137     case FIB_SOURCE_CMP_BETTER:
1138         /*
1139          * Que! removing a path from a source that is better than the
1140          * one this entry is using. This can only mean it is a source
1141          * this prefix does not have.
1142          */
1143         return (FIB_ENTRY_SRC_FLAG_ADDED);
1144
1145     case FIB_SOURCE_CMP_WORSE:
1146         /*
1147          * the source is not the best. no need to update forwarding
1148          */
1149         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1150         {
1151             /*
1152              * the source being removed still has paths
1153              */
1154             return (FIB_ENTRY_SRC_FLAG_ADDED);
1155         }
1156         else
1157         {
1158             /*
1159              * that was the last path from this source, check if those
1160              * that remain are non-inherited
1161              */
1162             if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1163             {
1164                 /*
1165                  * no more sources left. this entry is toast.
1166                  */
1167                 fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
1168                 fib_entry_src_action_uninstall(fib_entry);
1169                 return (FIB_ENTRY_SRC_FLAG_NONE);
1170             }
1171
1172             /*
1173              * reactivate the best source so the interposer gets restacked
1174              */
1175             fib_entry_src_action_reactivate(fib_entry, best_source);
1176
1177             return (FIB_ENTRY_SRC_FLAG_ADDED);
1178         }
1179         break;
1180
1181     case FIB_SOURCE_CMP_EQUAL:
1182         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1183         {
1184             /*
1185              * the source was removed. use the next best.
1186              */
1187             return (fib_entry_source_removed(fib_entry, bflags));
1188         }
1189         else
1190         {
1191             /*
1192              * re-install the new forwarding information
1193              */
1194             fib_entry_src_action_reactivate(fib_entry, source);
1195         }
1196         break;
1197     }
1198
1199     fib_entry_post_update_actions(fib_entry, source, bflags);
1200
1201     /*
1202      * still have sources
1203      */
1204     return (FIB_ENTRY_SRC_FLAG_ADDED);
1205 }
1206
1207 /**
1208  * fib_entry_inherit
1209  *
1210  * If the source on the cover is inheriting then push this source
1211  * down to the covered.
1212  */
1213 void
1214 fib_entry_inherit (fib_node_index_t cover,
1215                    fib_node_index_t covered)
1216 {
1217     fib_entry_src_inherit(fib_entry_get(cover),
1218                           fib_entry_get(covered));
1219 }
1220
1221 /**
1222  * fib_entry_delete
1223  *
1224  * The source is withdrawing all the paths it provided
1225  */
1226 fib_entry_src_flag_t
1227 fib_entry_delete (fib_node_index_t fib_entry_index,
1228                   fib_source_t source)
1229 {
1230     return (fib_entry_special_remove(fib_entry_index, source));
1231 }
1232
1233 /**
1234  * fib_entry_update
1235  *
1236  * The source has provided a new set of paths that will replace the old.
1237  */
1238 void
1239 fib_entry_update (fib_node_index_t fib_entry_index,
1240                   fib_source_t source,
1241                   fib_entry_flag_t flags,
1242                   const fib_route_path_t *paths)
1243 {
1244     fib_source_t best_source;
1245     fib_entry_flag_t bflags;
1246     fib_entry_t *fib_entry;
1247     fib_entry_src_t *bsrc;
1248
1249     fib_entry = fib_entry_get(fib_entry_index);
1250     ASSERT(NULL != fib_entry);
1251
1252     bsrc = fib_entry_get_best_src_i(fib_entry);
1253     best_source = fib_entry_src_get_source(bsrc);
1254     bflags = fib_entry_get_flags_i(fib_entry);
1255
1256     fib_entry = fib_entry_src_action_path_swap(fib_entry,
1257                                                source,
1258                                                flags,
1259                                                paths);
1260
1261     fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1262     FIB_ENTRY_DBG(fib_entry, "update");
1263 }
1264
1265
1266 /*
1267  * fib_entry_cover_changed
1268  *
1269  * this entry is tracking its cover and that cover has changed.
1270  */
1271 void
1272 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1273 {
1274     fib_entry_src_cover_res_t res = {
1275         .install = !0,
1276         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1277     };
1278     CLIB_UNUSED(fib_source_t source);
1279     fib_source_t best_source;
1280     fib_entry_flag_t bflags;
1281     fib_entry_t *fib_entry;
1282     fib_entry_src_t *esrc;
1283     u32 index;
1284
1285     bflags = FIB_ENTRY_FLAG_NONE;
1286     best_source = FIB_SOURCE_FIRST;
1287     fib_entry = fib_entry_get(fib_entry_index);
1288
1289     fib_attached_export_cover_change(fib_entry);
1290
1291     /*
1292      * propagate the notification to each of the added sources
1293      */
1294     index = 0;
1295     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1296     ({
1297         if (0 == index)
1298         {
1299             /*
1300              * only the best source gets to set the back walk flags
1301              */
1302             res = fib_entry_src_action_cover_change(fib_entry, esrc);
1303             bflags = fib_entry_src_get_flags(esrc);
1304             best_source = fib_entry_src_get_source(esrc);
1305         }
1306         else
1307         {
1308             fib_entry_src_action_cover_change(fib_entry, esrc);
1309         }
1310         index++;
1311     }));
1312
1313     if (res.install)
1314     {
1315         fib_entry_src_action_reactivate(fib_entry,
1316                                         fib_entry_src_get_source(
1317                                             fib_entry_get_best_src_i(fib_entry)));
1318         fib_entry = fib_entry_post_install_actions(fib_entry,
1319                                                    best_source,
1320                                                    bflags);
1321     }
1322     else
1323     {
1324         fib_entry_src_action_uninstall(fib_entry);
1325     }
1326
1327     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1328     {
1329         /*
1330          * time for walkies fido.
1331          */
1332         fib_node_back_walk_ctx_t bw_ctx = {
1333             .fnbw_reason = res.bw_reason,
1334         };
1335
1336         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1337     }
1338     FIB_ENTRY_DBG(fib_entry, "cover-changed");
1339 }
1340
1341 /*
1342  * fib_entry_cover_updated
1343  *
1344  * this entry is tracking its cover and that cover has been updated
1345  * (i.e. its forwarding information has changed).
1346  */
1347 void
1348 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1349 {
1350     fib_entry_src_cover_res_t res = {
1351         .install = !0,
1352         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1353     };
1354     CLIB_UNUSED(fib_source_t source);
1355     fib_source_t best_source;
1356     fib_entry_flag_t bflags;
1357     fib_entry_t *fib_entry;
1358     fib_entry_src_t *esrc;
1359     u32 index;
1360
1361     bflags = FIB_ENTRY_FLAG_NONE;
1362     best_source = FIB_SOURCE_FIRST;
1363     fib_entry = fib_entry_get(fib_entry_index);
1364
1365     fib_attached_export_cover_update(fib_entry);
1366
1367     /*
1368      * propagate the notification to each of the added sources
1369      */
1370     index = 0;
1371     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1372     ({
1373         if (0 == index)
1374         {
1375             /*
1376              * only the best source gets to set the install result
1377              */
1378             res = fib_entry_src_action_cover_update(fib_entry, esrc);
1379             bflags = fib_entry_src_get_flags(esrc);
1380             best_source = fib_entry_src_get_source(esrc);
1381         }
1382         else
1383         {
1384             /*
1385              * contirubting sources can set backwalk flags
1386              */
1387             if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING)
1388             {
1389                 fib_entry_src_cover_res_t tmp = {
1390                     .install = !0,
1391                     .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1392                 };
1393
1394                 tmp = fib_entry_src_action_cover_update(fib_entry, esrc);
1395                 res.bw_reason |= tmp.bw_reason;
1396             }
1397             else
1398             {
1399                 fib_entry_src_action_cover_update(fib_entry, esrc);
1400             }
1401         }
1402         index++;
1403     }));
1404
1405     if (res.install)
1406     {
1407         fib_entry_src_action_reactivate(fib_entry,
1408                                         fib_entry_src_get_source(
1409                                             fib_entry_get_best_src_i(fib_entry)));
1410         fib_entry = fib_entry_post_install_actions(fib_entry,
1411                                                    best_source,
1412                                                    bflags);
1413     }
1414     else
1415     {
1416         fib_entry_src_action_uninstall(fib_entry);
1417     }
1418
1419     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1420     {
1421         /*
1422          * time for walkies fido.
1423          */
1424         fib_node_back_walk_ctx_t bw_ctx = {
1425             .fnbw_reason = res.bw_reason,
1426         };
1427
1428         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1429     }
1430     FIB_ENTRY_DBG(fib_entry, "cover-updated");
1431 }
1432
1433 int
1434 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1435                                  fib_node_index_t **entry_indicies)
1436 {
1437     fib_entry_t *fib_entry;
1438     int was_looped, is_looped;
1439
1440     fib_entry = fib_entry_get(entry_index);
1441
1442     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1443     {
1444         fib_node_index_t *entries = *entry_indicies;
1445
1446         vec_add1(entries, entry_index);
1447         was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1448         is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1449                                                         &entries);
1450
1451         *entry_indicies = entries;
1452
1453         if (!!was_looped != !!is_looped)
1454         {
1455             /*
1456              * re-evaluate all the entry's forwarding
1457              * NOTE: this is an inplace modify
1458              */
1459             fib_entry_delegate_type_t fdt;
1460             fib_entry_delegate_t *fed;
1461
1462             FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1463             {
1464                 fib_entry_src_mk_lb(fib_entry,
1465                                     fib_entry_get_best_source(entry_index),
1466                                     fib_entry_delegate_type_to_chain_type(fdt),
1467                                     &fed->fd_dpo);
1468             });
1469         }
1470     }
1471     else
1472     {
1473         /*
1474          * the entry is currently not linked to a path-list. this happens
1475          * when it is this entry that is re-linking path-lists and has thus
1476          * broken the loop
1477          */
1478         is_looped = 0;
1479     }
1480
1481     return (is_looped);
1482 }
1483
1484 u32
1485 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1486 {
1487     fib_entry_t *fib_entry;
1488
1489     fib_entry = fib_entry_get(entry_index);
1490
1491     return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1492 }
1493
1494 u32
1495 fib_entry_get_any_resolving_interface (fib_node_index_t entry_index)
1496 {
1497     const fib_entry_src_t *src;
1498     fib_entry_t *fib_entry;
1499     fib_source_t source;
1500     u32 sw_if_index;
1501
1502     fib_entry = fib_entry_get(entry_index);
1503
1504     FOR_EACH_SRC_ADDED(fib_entry, src, source,
1505     ({
1506         sw_if_index = fib_entry_get_resolving_interface_for_source (entry_index,
1507                                                                     source);
1508
1509         if (~0 != sw_if_index)
1510             break;
1511     }));
1512     return (sw_if_index);
1513 }
1514
1515 fib_source_t
1516 fib_entry_get_best_source (fib_node_index_t entry_index)
1517 {
1518     fib_entry_t *fib_entry;
1519     fib_entry_src_t *bsrc;
1520
1521     fib_entry = fib_entry_get(entry_index);
1522
1523     bsrc = fib_entry_get_best_src_i(fib_entry);
1524     return (fib_entry_src_get_source(bsrc));
1525 }
1526
1527 /**
1528  * Return !0 is the entry represents a host prefix
1529  */
1530 int
1531 fib_entry_is_host (fib_node_index_t fib_entry_index)
1532 {
1533     return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1534 }
1535
1536 /**
1537  * Return !0 is the entry is resolved, i.e. will return a valid forwarding
1538  * chain
1539  */
1540 int
1541 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1542 {
1543     fib_entry_delegate_t *fed;
1544     fib_entry_t *fib_entry;
1545
1546     fib_entry = fib_entry_get(fib_entry_index);
1547
1548     fed = fib_entry_delegate_find(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1549
1550     if (NULL == fed)
1551     {
1552         /*
1553          * no BFD tracking - consider it resolved.
1554          */
1555         return (!0);
1556     }
1557     else
1558     {
1559         /*
1560          * defer to the state of the BFD tracking
1561          */
1562         return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1563     }
1564 }
1565
1566 void
1567 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1568                                 flow_hash_config_t hash_config)
1569 {
1570     fib_entry_t *fib_entry;
1571
1572     fib_entry = fib_entry_get(fib_entry_index);
1573
1574     /*
1575      * pass the hash-config on to the load-balance object where it is cached.
1576      * we can ignore LBs in the delegate chains, since they will not be of the
1577      * correct protocol type (i.e. they are not IP)
1578      * There's no way, nor need, to change the hash config for MPLS.
1579      */
1580     if (dpo_id_is_valid(&fib_entry->fe_lb))
1581     {
1582         load_balance_t *lb;
1583
1584         ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1585
1586         lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1587
1588         /*
1589          * atomic update for packets in flight
1590          */
1591         lb->lb_hash_config = hash_config;
1592     }
1593 }
1594
1595 u32
1596 fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1597 {
1598     fib_entry_t *fib_entry;
1599
1600     fib_entry = fib_entry_get(fib_entry_index);
1601
1602     return (fib_entry->fe_lb.dpoi_index);
1603 }
1604
1605 static int
1606 fib_ip4_address_compare (const ip4_address_t * a1,
1607                          const ip4_address_t * a2)
1608 {
1609     /*
1610      * IP addresses are unsigned ints. the return value here needs to be signed
1611      * a simple subtraction won't cut it.
1612      * If the addresses are the same, the sort order is undefined, so phoey.
1613      */
1614     return ((clib_net_to_host_u32(a1->data_u32) >
1615              clib_net_to_host_u32(a2->data_u32) ) ?
1616             1 : -1);
1617 }
1618
1619 static int
1620 fib_ip6_address_compare (const ip6_address_t * a1,
1621                          const ip6_address_t * a2)
1622 {
1623   int i;
1624   for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1625   {
1626       int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1627                  clib_net_to_host_u16 (a2->as_u16[i]));
1628       if (cmp != 0)
1629           return cmp;
1630   }
1631   return 0;
1632 }
1633
1634 static int
1635 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1636                fib_node_index_t fib_entry_index2)
1637 {
1638     fib_entry_t *fib_entry1, *fib_entry2;
1639     int cmp = 0;
1640
1641     fib_entry1 = fib_entry_get(fib_entry_index1);
1642     fib_entry2 = fib_entry_get(fib_entry_index2);
1643
1644     switch (fib_entry1->fe_prefix.fp_proto)
1645     {
1646     case FIB_PROTOCOL_IP4:
1647         cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1648                                       &fib_entry2->fe_prefix.fp_addr.ip4);
1649         break;
1650     case FIB_PROTOCOL_IP6:
1651         cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1652                                       &fib_entry2->fe_prefix.fp_addr.ip6);
1653         break;
1654     case FIB_PROTOCOL_MPLS:
1655         cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1656
1657         if (0 == cmp)
1658         {
1659             cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1660         }
1661         break;
1662     }
1663
1664     if (0 == cmp) {
1665         cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1666     }
1667     return (cmp);
1668 }
1669
1670 int
1671 fib_entry_cmp_for_sort (void *i1, void *i2)
1672 {
1673     fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1674
1675     return (fib_entry_cmp(*fib_entry_index1,
1676                           *fib_entry_index2));
1677 }
1678
1679 void
1680 fib_entry_lock (fib_node_index_t fib_entry_index)
1681 {
1682     fib_entry_t *fib_entry;
1683
1684     fib_entry = fib_entry_get(fib_entry_index);
1685
1686     fib_node_lock(&fib_entry->fe_node);
1687 }
1688
1689 void
1690 fib_entry_unlock (fib_node_index_t fib_entry_index)
1691 {
1692     fib_entry_t *fib_entry;
1693
1694     fib_entry = fib_entry_get(fib_entry_index);
1695
1696     fib_node_unlock(&fib_entry->fe_node);
1697 }
1698
1699 void
1700 fib_entry_module_init (void)
1701 {
1702     fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1703     fib_entry_logger = vlib_log_register_class("fib", "entry");
1704
1705     fib_entry_track_module_init();
1706 }
1707
1708 fib_route_path_t *
1709 fib_entry_encode (fib_node_index_t fib_entry_index)
1710 {
1711     fib_path_ext_list_t *ext_list;
1712     fib_path_encode_ctx_t ctx = {
1713         .rpaths = NULL,
1714     };
1715     fib_entry_t *fib_entry;
1716     fib_entry_src_t *bsrc;
1717
1718     ext_list = NULL;
1719     fib_entry = fib_entry_get(fib_entry_index);
1720     bsrc = fib_entry_get_best_src_i(fib_entry);
1721
1722     if (bsrc)
1723     {
1724         ext_list = &bsrc->fes_path_exts;
1725     }
1726
1727     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1728     {
1729         fib_path_list_walk_w_ext(fib_entry->fe_parent,
1730                                  ext_list,
1731                                  fib_path_encode,
1732                                  &ctx);
1733     }
1734
1735     return (ctx.rpaths);
1736 }
1737
1738 const fib_prefix_t *
1739 fib_entry_get_prefix (fib_node_index_t fib_entry_index)
1740 {
1741     fib_entry_t *fib_entry;
1742
1743     fib_entry = fib_entry_get(fib_entry_index);
1744
1745     return (&fib_entry->fe_prefix);
1746 }
1747
1748 u32
1749 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1750 {
1751     fib_entry_t *fib_entry;
1752
1753     fib_entry = fib_entry_get(fib_entry_index);
1754
1755     return (fib_entry->fe_fib_index);
1756 }
1757
1758 u32
1759 fib_entry_pool_size (void)
1760 {
1761     return (pool_elts(fib_entry_pool));
1762 }
1763
1764 #if CLIB_DEBUG > 0
1765 void
1766 fib_table_assert_empty (const fib_table_t *fib_table)
1767 {
1768     fib_node_index_t *fei, *feis = NULL;
1769     fib_entry_t *fib_entry;
1770
1771     pool_foreach (fib_entry, fib_entry_pool)
1772      {
1773         if (fib_entry->fe_fib_index == fib_table->ft_index)
1774             vec_add1 (feis, fib_entry_get_index(fib_entry));
1775     }
1776
1777     if (vec_len(feis))
1778     {
1779         vec_foreach (fei, feis)
1780             clib_error ("%U", format_fib_entry, *fei, FIB_ENTRY_FORMAT_DETAIL);
1781     }
1782
1783     ASSERT(0);
1784 }
1785 #endif
1786
1787 static clib_error_t *
1788 show_fib_entry_command (vlib_main_t * vm,
1789                         unformat_input_t * input,
1790                         vlib_cli_command_t * cmd)
1791 {
1792     fib_node_index_t fei;
1793
1794     if (unformat (input, "%d", &fei))
1795     {
1796         /*
1797          * show one in detail
1798          */
1799         if (!pool_is_free_index(fib_entry_pool, fei))
1800         {
1801             vlib_cli_output (vm, "%d@%U",
1802                              fei,
1803                              format_fib_entry, fei,
1804                              FIB_ENTRY_FORMAT_DETAIL2);
1805         }
1806         else
1807         {
1808             vlib_cli_output (vm, "entry %d invalid", fei);
1809         }
1810     }
1811     else
1812     {
1813         /*
1814          * show all
1815          */
1816         vlib_cli_output (vm, "FIB Entries:");
1817         pool_foreach_index (fei, fib_entry_pool)
1818          {
1819             vlib_cli_output (vm, "%d@%U",
1820                              fei,
1821                              format_fib_entry, fei,
1822                              FIB_ENTRY_FORMAT_BRIEF);
1823         }
1824     }
1825
1826     return (NULL);
1827 }
1828
1829 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1830   .path = "show fib entry",
1831   .function = show_fib_entry_command,
1832   .short_help = "show fib entry",
1833 };