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
 603     pool_get(fib_entry_pool, fib_entry);
 604     clib_memset(fib_entry, 0, sizeof(*fib_entry));
 605
 606     fib_node_init(&fib_entry->fe_node,
 607                   FIB_NODE_TYPE_ENTRY);
 608
 609     fib_entry->fe_fib_index = fib_index;
 610
 611     /*
 612      * the one time we need to update the const prefix is when
 613      * the entry is first created
 614      */
 615     fep = (fib_prefix_t*)&(fib_entry->fe_prefix);
 616     *fep = *prefix;
 617
 618     if (FIB_PROTOCOL_MPLS == fib_entry->fe_prefix.fp_proto)
 619     {
 620         fep->fp_len = 21;
 621         if (MPLS_NON_EOS == fep->fp_eos)
 622         {
 623             fep->fp_payload_proto = DPO_PROTO_MPLS;
 624         }
 625         ASSERT(DPO_PROTO_NONE != fib_entry->fe_prefix.fp_payload_proto);
 626     }
 627
 628     dpo_reset(&fib_entry->fe_lb);
 629
 630     *fib_entry_index = fib_entry_get_index(fib_entry);
 631
 632     return (fib_entry);
 633 }
 634
 635 static fib_entry_t*
 636 fib_entry_post_flag_update_actions (fib_entry_t *fib_entry,
 637                                     fib_entry_flag_t old_flags)
 638 {
 639     fib_node_index_t fei;
 640
 641     /*
 642      * save the index so we can recover from pool reallocs
 643      */
 644     fei = fib_entry_get_index(fib_entry);
 645
 646     /*
 647      * handle changes to attached export for import entries
 648      */
 649     int is_import  = (FIB_ENTRY_FLAG_IMPORT & fib_entry_get_flags_i(fib_entry));
 650     int was_import = (FIB_ENTRY_FLAG_IMPORT & old_flags);
 651
 652     if (!was_import && is_import)
 653     {
 654         /*
 655          * transition from not exported to exported
 656          */
 657
 658         /*
 659          * there is an assumption here that the entry resolves via only
 660          * one interface and that it is the cross VRF interface.
 661          */
 662         u32 sw_if_index = fib_path_list_get_resolving_interface(fib_entry->fe_parent);
 663
 664         fib_attached_export_import(fib_entry,
 665                                    fib_table_get_index_for_sw_if_index(
 666                                        fib_entry_get_proto(fib_entry),
 667                                        sw_if_index));
 668     }
 669     else if (was_import && !is_import)
 670     {
 671         /*
 672          * transition from exported to not exported
 673          */
 674         fib_attached_export_purge(fib_entry);
 675     }
 676     /*
 677      * else
 678      *   no change. nothing to do.
 679      */
 680
 681     /*
 682      * reload the entry address post possible pool realloc
 683      */
 684     fib_entry = fib_entry_get(fei);
 685
 686     /*
 687      * handle changes to attached export for export entries
 688      */
 689     int is_attached  = (FIB_ENTRY_FLAG_ATTACHED & fib_entry_get_flags_i(fib_entry));
 690     int was_attached = (FIB_ENTRY_FLAG_ATTACHED & old_flags);
 691
 692     if (!was_attached && is_attached)
 693     {
 694         /*
 695          * transition to attached. time to export
 696          */
 697         // FIXME
 698     }
 699     // else FIXME
 700
 701     return (fib_entry);
 702 }
 703
 704 static fib_entry_t*
 705 fib_entry_post_install_actions (fib_entry_t *fib_entry,
 706                                 fib_source_t source,
 707                                 fib_entry_flag_t old_flags)
 708 {
 709     fib_entry = fib_entry_post_flag_update_actions(fib_entry,
 710                                                    old_flags);
 711     fib_entry = fib_entry_src_action_installed(fib_entry, source);
 712
 713     return (fib_entry);
 714 }
 715
 716 fib_node_index_t
 717 fib_entry_create (u32 fib_index,
 718                   const fib_prefix_t *prefix,
 719                   fib_source_t source,
 720                   fib_entry_flag_t flags,
 721                   const fib_route_path_t *paths)
 722 {
 723     fib_node_index_t fib_entry_index;
 724     fib_entry_t *fib_entry;
 725
 726     ASSERT(0 < vec_len(paths));
 727
 728     fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
 729
 730     /*
 731      * since this is a new entry create, we don't need to check for winning
 732      * sources - there is only one.
 733      */
 734     fib_entry = fib_entry_src_action_add(fib_entry, source, flags,
 735                                          drop_dpo_get(
 736                                              fib_proto_to_dpo(
 737                                                  fib_entry_get_proto(fib_entry))));
 738     fib_entry_src_action_path_swap(fib_entry,
 739                                    source,
 740                                    flags,
 741                                    paths);
 742     /*
 743      * handle possible realloc's by refetching the pointer
 744      */
 745     fib_entry = fib_entry_get(fib_entry_index);
 746     fib_entry_src_action_activate(fib_entry, source);
 747
 748     fib_entry = fib_entry_post_install_actions(fib_entry, source,
 749                                                FIB_ENTRY_FLAG_NONE);
 750
 751     FIB_ENTRY_DBG(fib_entry, "create");
 752
 753     return (fib_entry_index);
 754 }
 755
 756 fib_node_index_t
 757 fib_entry_create_special (u32 fib_index,
 758                           const fib_prefix_t *prefix,
 759                           fib_source_t source,
 760                           fib_entry_flag_t flags,
 761                           const dpo_id_t *dpo)
 762 {
 763     fib_node_index_t fib_entry_index;
 764     fib_entry_t *fib_entry;
 765
 766     /*
 767      * create and initialize the new enty
 768      */
 769     fib_entry = fib_entry_alloc(fib_index, prefix, &fib_entry_index);
 770
 771     /*
 772      * create the path-list
 773      */
 774     fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
 775     fib_entry_src_action_activate(fib_entry, source);
 776
 777     fib_entry = fib_entry_post_install_actions(fib_entry, source,
 778                                                FIB_ENTRY_FLAG_NONE);
 779
 780     FIB_ENTRY_DBG(fib_entry, "create-special");
 781
 782     return (fib_entry_index);
 783 }
 784
 785 static void
 786 fib_entry_post_update_actions (fib_entry_t *fib_entry,
 787                                fib_source_t source,
 788                                fib_entry_flag_t old_flags)
 789 {
 790     /*
 791      * backwalk to children to inform then of the change to forwarding.
 792      */
 793     fib_node_back_walk_ctx_t bw_ctx = {
 794         .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
 795     };
 796
 797     fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_get_index(fib_entry), &bw_ctx);
 798
 799     /*
 800      * then inform any covered prefixes
 801      */
 802     fib_entry_cover_update_notify(fib_entry);
 803
 804     fib_entry_post_install_actions(fib_entry, source, old_flags);
 805 }
 806
 807 void
 808 fib_entry_recalculate_forwarding (fib_node_index_t fib_entry_index)
 809 {
 810     fib_source_t best_source;
 811     fib_entry_t *fib_entry;
 812     fib_entry_src_t *bsrc;
 813
 814     fib_entry = fib_entry_get(fib_entry_index);
 815
 816     bsrc = fib_entry_get_best_src_i(fib_entry);
 817     best_source = fib_entry_src_get_source(bsrc);
 818
 819     fib_entry_src_action_reactivate(fib_entry, best_source);
 820 }
 821
 822 static void
 823 fib_entry_source_change_w_flags (fib_entry_t *fib_entry,
 824                                  fib_source_t old_source,
 825                                  fib_entry_flag_t old_flags,
 826                                  fib_source_t new_source)
 827 {
 828     switch (fib_source_cmp(new_source, old_source))
 829     {
 830     case FIB_SOURCE_CMP_BETTER:
 831         /*
 832          * we have a new winning source.
 833          */
 834         fib_entry_src_action_deactivate(fib_entry, old_source);
 835         fib_entry_src_action_activate(fib_entry, new_source);
 836         break;
 837
 838     case FIB_SOURCE_CMP_WORSE:
 839         /*
 840          * the new source loses. Re-activate the winning sources
 841          * in case it is an interposer and hence relied on the losing
 842          * source's path-list.
 843          */
 844         fib_entry_src_action_reactivate(fib_entry, old_source);
 845         return;
 846
 847     case FIB_SOURCE_CMP_EQUAL:
 848         /*
 849          * the new source is one this entry already has.
 850          * But the path-list was updated, which will contribute new forwarding,
 851          * so install it.
 852          */
 853         fib_entry_src_action_reactivate(fib_entry, new_source);
 854         break;
 855     }
 856
 857     fib_entry_post_update_actions(fib_entry, new_source, old_flags);
 858 }
 859
 860 void
 861 fib_entry_source_change (fib_entry_t *fib_entry,
 862                          fib_source_t old_source,
 863                          fib_source_t new_source)
 864 {
 865     fib_entry_flag_t old_flags;
 866
 867     old_flags = fib_entry_get_flags_for_source(
 868         fib_entry_get_index(fib_entry), old_source);
 869
 870     return (fib_entry_source_change_w_flags(fib_entry, old_source,
 871                                             old_flags, new_source));
 872 }
 873
 874 void
 875 fib_entry_special_add (fib_node_index_t fib_entry_index,
 876                        fib_source_t source,
 877                        fib_entry_flag_t flags,
 878                        const dpo_id_t *dpo)
 879 {
 880     fib_source_t best_source;
 881     fib_entry_t *fib_entry;
 882
 883     fib_entry = fib_entry_get(fib_entry_index);
 884     best_source = fib_entry_get_best_source(fib_entry_index);
 885
 886     fib_entry = fib_entry_src_action_add(fib_entry, source, flags, dpo);
 887     fib_entry_source_change(fib_entry, best_source, source);
 888     FIB_ENTRY_DBG(fib_entry, "special-add:%U", format_fib_source, source);
 889 }
 890
 891 void
 892 fib_entry_special_update (fib_node_index_t fib_entry_index,
 893                           fib_source_t source,
 894                           fib_entry_flag_t flags,
 895                           const dpo_id_t *dpo)
 896 {
 897     fib_source_t best_source;
 898     fib_entry_t *fib_entry;
 899
 900     fib_entry = fib_entry_get(fib_entry_index);
 901     best_source = fib_entry_get_best_source(fib_entry_index);
 902
 903     fib_entry = fib_entry_src_action_update(fib_entry, source, flags, dpo);
 904     fib_entry_source_change(fib_entry, best_source, source);
 905
 906     FIB_ENTRY_DBG(fib_entry, "special-updated:%U", format_fib_source, source);
 907 }
 908
 909
 910 void
 911 fib_entry_path_add (fib_node_index_t fib_entry_index,
 912                     fib_source_t source,
 913                     fib_entry_flag_t flags,
 914                     const fib_route_path_t *rpaths)
 915 {
 916     fib_source_t best_source;
 917     fib_entry_t *fib_entry;
 918     fib_entry_src_t *bsrc;
 919
 920     fib_entry = fib_entry_get(fib_entry_index);
 921     ASSERT(NULL != fib_entry);
 922
 923     bsrc = fib_entry_get_best_src_i(fib_entry);
 924     best_source = fib_entry_src_get_source(bsrc);
 925
 926     fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpaths);
 927
 928     fib_entry_source_change(fib_entry, best_source, source);
 929
 930     FIB_ENTRY_DBG(fib_entry, "path add:%U", format_fib_source, source);
 931 }
 932
 933 static fib_entry_src_flag_t
 934 fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
 935 {
 936     fib_entry_src_t *src;
 937     fib_source_t source;
 938     int has_only_inherited_sources = 1;
 939
 940     FOR_EACH_SRC_ADDED(fib_entry, src, source,
 941     ({
 942         if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 943         {
 944             has_only_inherited_sources = 0;
 945             break;
 946         }
 947     }));
 948     if (has_only_inherited_sources)
 949     {
 950         FOR_EACH_SRC_ADDED(fib_entry, src, source,
 951         ({
 952             fib_entry_src_action_remove(fib_entry, source);
 953         }));
 954         return (FIB_ENTRY_SRC_FLAG_NONE);
 955     }
 956     else
 957     {
 958         return (FIB_ENTRY_SRC_FLAG_ADDED);
 959     }
 960 }
 961
 962 static fib_entry_src_flag_t
 963 fib_entry_source_removed (fib_entry_t *fib_entry,
 964                           fib_entry_flag_t old_flags)
 965 {
 966     const fib_entry_src_t *bsrc;
 967     fib_source_t best_source;
 968
 969     /*
 970      * if all that is left are inherited sources, then burn them
 971      */
 972     fib_entry_src_burn_only_inherited(fib_entry);
 973
 974     bsrc = fib_entry_get_best_src_i(fib_entry);
 975     best_source = fib_entry_src_get_source(bsrc);
 976
 977     if (FIB_SOURCE_INVALID == best_source)
 978     {
 979         /*
 980          * no more sources left. this entry is toast.
 981          */
 982         fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
 983         fib_entry_src_action_uninstall(fib_entry);
 984
 985         return (FIB_ENTRY_SRC_FLAG_NONE);
 986     }
 987     else
 988     {
 989         fib_entry_src_action_activate(fib_entry, best_source);
 990     }
 991
 992     fib_entry_post_update_actions(fib_entry, best_source, old_flags);
 993
 994     /*
 995      * still have sources
 996      */
 997     return (FIB_ENTRY_SRC_FLAG_ADDED);
 998 }
 999
1000 /*
1001  * fib_entry_path_remove
1002  *
1003  * remove a path from the entry.
1004  * return the fib_entry's index if it is still present, INVALID otherwise.
1005  */
1006 fib_entry_src_flag_t
1007 fib_entry_path_remove (fib_node_index_t fib_entry_index,
1008                        fib_source_t source,
1009                        const fib_route_path_t *rpaths)
1010 {
1011     fib_entry_src_flag_t sflag;
1012     fib_source_t best_source;
1013     fib_entry_flag_t bflags;
1014     fib_entry_t *fib_entry;
1015     fib_entry_src_t *bsrc;
1016
1017     fib_entry = fib_entry_get(fib_entry_index);
1018     ASSERT(NULL != fib_entry);
1019
1020     bsrc = fib_entry_get_best_src_i(fib_entry);
1021     best_source = fib_entry_src_get_source(bsrc);
1022     bflags = fib_entry_src_get_flags(bsrc);
1023
1024     sflag = fib_entry_src_action_path_remove(fib_entry, source, rpaths);
1025
1026     FIB_ENTRY_DBG(fib_entry, "path remove:%U", format_fib_source, source);
1027
1028     /*
1029      * if the path list for the source passed is invalid,
1030      * then we need to create a new one. else we are updating
1031      * an existing.
1032      */
1033     switch (fib_source_cmp(source, best_source))
1034     {
1035     case FIB_SOURCE_CMP_BETTER:
1036         /*
1037          * Que! removing a path from a source that is better than the
1038          * one this entry is using.
1039          */
1040         ASSERT(0);
1041         break;
1042     case FIB_SOURCE_CMP_WORSE:
1043         /*
1044          * the source is not the best. no need to update forwarding
1045          */
1046         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1047         {
1048             /*
1049              * the source being removed still has paths
1050              */
1051             return (FIB_ENTRY_SRC_FLAG_ADDED);
1052         }
1053         else
1054         {
1055             /*
1056              * that was the last path from this source, check if those
1057              * that remain are non-inherited
1058              */
1059             return (fib_entry_src_burn_only_inherited(fib_entry));
1060         }
1061         break;
1062     case FIB_SOURCE_CMP_EQUAL:
1063         /*
1064          * removing a path from the path-list we were using.
1065          */
1066         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1067         {
1068             /*
1069              * the last path from the source was removed.
1070              * fallback to lower source
1071              */
1072             return (fib_entry_source_removed(fib_entry, bflags));
1073         }
1074         else
1075         {
1076             /*
1077              * re-install the new forwarding information
1078              */
1079             fib_entry_src_action_reactivate(fib_entry, source);
1080         }
1081         break;
1082     }
1083
1084     fib_entry_post_update_actions(fib_entry, source, bflags);
1085
1086     /*
1087      * still have sources
1088      */
1089     return (FIB_ENTRY_SRC_FLAG_ADDED);
1090 }
1091
1092 /*
1093  * fib_entry_special_remove
1094  *
1095  * remove a special source from the entry.
1096  * return the fib_entry's index if it is still present, INVALID otherwise.
1097  */
1098 fib_entry_src_flag_t
1099 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1100                           fib_source_t source)
1101 {
1102     fib_entry_src_flag_t sflag;
1103     fib_source_t best_source;
1104     fib_entry_flag_t bflags;
1105     fib_entry_t *fib_entry;
1106     fib_entry_src_t *bsrc;
1107
1108     fib_entry = fib_entry_get(fib_entry_index);
1109     ASSERT(NULL != fib_entry);
1110
1111     bsrc = fib_entry_get_best_src_i(fib_entry);
1112     best_source = fib_entry_src_get_source(bsrc);
1113     bflags = fib_entry_src_get_flags(bsrc);
1114
1115     FIB_ENTRY_DBG(fib_entry, "special remove:%U", format_fib_source, source);
1116
1117     sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1118
1119     /*
1120      * if the path list for the source passed is invalid,
1121      * then we need to create a new one. else we are updating
1122      * an existing.
1123      */
1124     switch (fib_source_cmp(source, best_source))
1125     {
1126     case FIB_SOURCE_CMP_BETTER:
1127         /*
1128          * Que! removing a path from a source that is better than the
1129          * one this entry is using. This can only mean it is a source
1130          * this prefix does not have.
1131          */
1132         return (FIB_ENTRY_SRC_FLAG_ADDED);
1133
1134     case FIB_SOURCE_CMP_WORSE:
1135         /*
1136          * the source is not the best. no need to update forwarding
1137          */
1138         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1139         {
1140             /*
1141              * the source being removed still has paths
1142              */
1143             return (FIB_ENTRY_SRC_FLAG_ADDED);
1144         }
1145         else
1146         {
1147             /*
1148              * that was the last path from this source, check if those
1149              * that remain are non-inherited
1150              */
1151             if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1152             {
1153                 /*
1154                  * no more sources left. this entry is toast.
1155                  */
1156                 fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
1157                 fib_entry_src_action_uninstall(fib_entry);
1158                 return (FIB_ENTRY_SRC_FLAG_NONE);
1159             }
1160
1161             /*
1162              * reactivate the best source so the interposer gets restacked
1163              */
1164             fib_entry_src_action_reactivate(fib_entry, best_source);
1165
1166             return (FIB_ENTRY_SRC_FLAG_ADDED);
1167         }
1168         break;
1169
1170     case FIB_SOURCE_CMP_EQUAL:
1171         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1172         {
1173             /*
1174              * the source was removed. use the next best.
1175              */
1176             return (fib_entry_source_removed(fib_entry, bflags));
1177         }
1178         else
1179         {
1180             /*
1181              * re-install the new forwarding information
1182              */
1183             fib_entry_src_action_reactivate(fib_entry, source);
1184         }
1185         break;
1186     }
1187
1188     fib_entry_post_update_actions(fib_entry, source, bflags);
1189
1190     /*
1191      * still have sources
1192      */
1193     return (FIB_ENTRY_SRC_FLAG_ADDED);
1194 }
1195
1196 /**
1197  * fib_entry_inherit
1198  *
1199  * If the source on the cover is inheriting then push this source
1200  * down to the covered.
1201  */
1202 void
1203 fib_entry_inherit (fib_node_index_t cover,
1204                    fib_node_index_t covered)
1205 {
1206     fib_entry_src_inherit(fib_entry_get(cover),
1207                           fib_entry_get(covered));
1208 }
1209
1210 /**
1211  * fib_entry_delete
1212  *
1213  * The source is withdrawing all the paths it provided
1214  */
1215 fib_entry_src_flag_t
1216 fib_entry_delete (fib_node_index_t fib_entry_index,
1217                   fib_source_t source)
1218 {
1219     return (fib_entry_special_remove(fib_entry_index, source));
1220 }
1221
1222 /**
1223  * fib_entry_update
1224  *
1225  * The source has provided a new set of paths that will replace the old.
1226  */
1227 void
1228 fib_entry_update (fib_node_index_t fib_entry_index,
1229                   fib_source_t source,
1230                   fib_entry_flag_t flags,
1231                   const fib_route_path_t *paths)
1232 {
1233     fib_source_t best_source;
1234     fib_entry_flag_t bflags;
1235     fib_entry_t *fib_entry;
1236     fib_entry_src_t *bsrc;
1237
1238     fib_entry = fib_entry_get(fib_entry_index);
1239     ASSERT(NULL != fib_entry);
1240
1241     bsrc = fib_entry_get_best_src_i(fib_entry);
1242     best_source = fib_entry_src_get_source(bsrc);
1243     bflags = fib_entry_get_flags_i(fib_entry);
1244
1245     fib_entry = fib_entry_src_action_path_swap(fib_entry,
1246                                                source,
1247                                                flags,
1248                                                paths);
1249
1250     fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1251     FIB_ENTRY_DBG(fib_entry, "update");
1252 }
1253
1254
1255 /*
1256  * fib_entry_cover_changed
1257  *
1258  * this entry is tracking its cover and that cover has changed.
1259  */
1260 void
1261 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1262 {
1263     fib_entry_src_cover_res_t res = {
1264         .install = !0,
1265         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1266     };
1267     CLIB_UNUSED(fib_source_t source);
1268     fib_source_t best_source;
1269     fib_entry_flag_t bflags;
1270     fib_entry_t *fib_entry;
1271     fib_entry_src_t *esrc;
1272     u32 index;
1273
1274     bflags = FIB_ENTRY_FLAG_NONE;
1275     best_source = FIB_SOURCE_FIRST;
1276     fib_entry = fib_entry_get(fib_entry_index);
1277
1278     fib_attached_export_cover_change(fib_entry);
1279
1280     /*
1281      * propagate the notification to each of the added sources
1282      */
1283     index = 0;
1284     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1285     ({
1286         if (0 == index)
1287         {
1288             /*
1289              * only the best source gets to set the back walk flags
1290              */
1291             res = fib_entry_src_action_cover_change(fib_entry, esrc);
1292             bflags = fib_entry_src_get_flags(esrc);
1293             best_source = fib_entry_src_get_source(esrc);
1294         }
1295         else
1296         {
1297             fib_entry_src_action_cover_change(fib_entry, esrc);
1298         }
1299         index++;
1300     }));
1301
1302     if (res.install)
1303     {
1304         fib_entry_src_action_reactivate(fib_entry,
1305                                         fib_entry_src_get_source(
1306                                             fib_entry_get_best_src_i(fib_entry)));
1307         fib_entry = fib_entry_post_install_actions(fib_entry,
1308                                                    best_source,
1309                                                    bflags);
1310     }
1311     else
1312     {
1313         fib_entry_src_action_uninstall(fib_entry);
1314     }
1315
1316     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1317     {
1318         /*
1319          * time for walkies fido.
1320          */
1321         fib_node_back_walk_ctx_t bw_ctx = {
1322             .fnbw_reason = res.bw_reason,
1323         };
1324
1325         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1326     }
1327     FIB_ENTRY_DBG(fib_entry, "cover-changed");
1328 }
1329
1330 /*
1331  * fib_entry_cover_updated
1332  *
1333  * this entry is tracking its cover and that cover has been updated
1334  * (i.e. its forwarding information has changed).
1335  */
1336 void
1337 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1338 {
1339     fib_entry_src_cover_res_t res = {
1340         .install = !0,
1341         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1342     };
1343     CLIB_UNUSED(fib_source_t source);
1344     fib_source_t best_source;
1345     fib_entry_flag_t bflags;
1346     fib_entry_t *fib_entry;
1347     fib_entry_src_t *esrc;
1348     u32 index;
1349
1350     bflags = FIB_ENTRY_FLAG_NONE;
1351     best_source = FIB_SOURCE_FIRST;
1352     fib_entry = fib_entry_get(fib_entry_index);
1353
1354     fib_attached_export_cover_update(fib_entry);
1355
1356     /*
1357      * propagate the notification to each of the added sources
1358      */
1359     index = 0;
1360     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1361     ({
1362         if (0 == index)
1363         {
1364             /*
1365              * only the best source gets to set the install result
1366              */
1367             res = fib_entry_src_action_cover_update(fib_entry, esrc);
1368             bflags = fib_entry_src_get_flags(esrc);
1369             best_source = fib_entry_src_get_source(esrc);
1370         }
1371         else
1372         {
1373             /*
1374              * contirubting sources can set backwalk flags
1375              */
1376             if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING)
1377             {
1378                 fib_entry_src_cover_res_t tmp = {
1379                     .install = !0,
1380                     .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1381                 };
1382
1383                 tmp = fib_entry_src_action_cover_update(fib_entry, esrc);
1384                 res.bw_reason |= tmp.bw_reason;
1385             }
1386             else
1387             {
1388                 fib_entry_src_action_cover_update(fib_entry, esrc);
1389             }
1390         }
1391         index++;
1392     }));
1393
1394     if (res.install)
1395     {
1396         fib_entry_src_action_reactivate(fib_entry,
1397                                         fib_entry_src_get_source(
1398                                             fib_entry_get_best_src_i(fib_entry)));
1399         fib_entry = fib_entry_post_install_actions(fib_entry,
1400                                                    best_source,
1401                                                    bflags);
1402     }
1403     else
1404     {
1405         fib_entry_src_action_uninstall(fib_entry);
1406     }
1407
1408     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1409     {
1410         /*
1411          * time for walkies fido.
1412          */
1413         fib_node_back_walk_ctx_t bw_ctx = {
1414             .fnbw_reason = res.bw_reason,
1415         };
1416
1417         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1418     }
1419     FIB_ENTRY_DBG(fib_entry, "cover-updated");
1420 }
1421
1422 int
1423 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1424                                  fib_node_index_t **entry_indicies)
1425 {
1426     fib_entry_t *fib_entry;
1427     int was_looped, is_looped;
1428
1429     fib_entry = fib_entry_get(entry_index);
1430
1431     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1432     {
1433         fib_node_index_t *entries = *entry_indicies;
1434
1435         vec_add1(entries, entry_index);
1436         was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1437         is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1438                                                         &entries);
1439
1440         *entry_indicies = entries;
1441
1442         if (!!was_looped != !!is_looped)
1443         {
1444             /*
1445              * re-evaluate all the entry's forwarding
1446              * NOTE: this is an inplace modify
1447              */
1448             fib_entry_delegate_type_t fdt;
1449             fib_entry_delegate_t *fed;
1450
1451             FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1452             {
1453                 fib_entry_src_mk_lb(fib_entry,
1454                                     fib_entry_get_best_source(entry_index),
1455                                     fib_entry_delegate_type_to_chain_type(fdt),
1456                                     &fed->fd_dpo);
1457             });
1458         }
1459     }
1460     else
1461     {
1462         /*
1463          * the entry is currently not linked to a path-list. this happens
1464          * when it is this entry that is re-linking path-lists and has thus
1465          * broken the loop
1466          */
1467         is_looped = 0;
1468     }
1469
1470     return (is_looped);
1471 }
1472
1473 u32
1474 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1475 {
1476     fib_entry_t *fib_entry;
1477
1478     fib_entry = fib_entry_get(entry_index);
1479
1480     return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1481 }
1482
1483 u32
1484 fib_entry_get_any_resolving_interface (fib_node_index_t entry_index)
1485 {
1486     const fib_entry_src_t *src;
1487     fib_entry_t *fib_entry;
1488     fib_source_t source;
1489     u32 sw_if_index;
1490
1491     fib_entry = fib_entry_get(entry_index);
1492
1493     FOR_EACH_SRC_ADDED(fib_entry, src, source,
1494     ({
1495         sw_if_index = fib_entry_get_resolving_interface_for_source (entry_index,
1496                                                                     source);
1497
1498         if (~0 != sw_if_index)
1499             break;
1500     }));
1501     return (sw_if_index);
1502 }
1503
1504 fib_source_t
1505 fib_entry_get_best_source (fib_node_index_t entry_index)
1506 {
1507     fib_entry_t *fib_entry;
1508     fib_entry_src_t *bsrc;
1509
1510     fib_entry = fib_entry_get(entry_index);
1511
1512     bsrc = fib_entry_get_best_src_i(fib_entry);
1513     return (fib_entry_src_get_source(bsrc));
1514 }
1515
1516 /**
1517  * Return !0 is the entry represents a host prefix
1518  */
1519 int
1520 fib_entry_is_host (fib_node_index_t fib_entry_index)
1521 {
1522     return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1523 }
1524
1525 /**
1526  * Return !0 is the entry is resolved, i.e. will return a valid forwarding
1527  * chain
1528  */
1529 int
1530 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1531 {
1532     fib_entry_delegate_t *fed;
1533     fib_entry_t *fib_entry;
1534
1535     fib_entry = fib_entry_get(fib_entry_index);
1536
1537     fed = fib_entry_delegate_find(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1538
1539     if (NULL == fed)
1540     {
1541         /*
1542          * no BFD tracking - consider it resolved.
1543          */
1544         return (!0);
1545     }
1546     else
1547     {
1548         /*
1549          * defer to the state of the BFD tracking
1550          */
1551         return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1552     }
1553 }
1554
1555 void
1556 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1557                                 flow_hash_config_t hash_config)
1558 {
1559     fib_entry_t *fib_entry;
1560
1561     fib_entry = fib_entry_get(fib_entry_index);
1562
1563     /*
1564      * pass the hash-config on to the load-balance object where it is cached.
1565      * we can ignore LBs in the delegate chains, since they will not be of the
1566      * correct protocol type (i.e. they are not IP)
1567      * There's no way, nor need, to change the hash config for MPLS.
1568      */
1569     if (dpo_id_is_valid(&fib_entry->fe_lb))
1570     {
1571         load_balance_t *lb;
1572
1573         ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1574
1575         lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1576
1577         /*
1578          * atomic update for packets in flight
1579          */
1580         lb->lb_hash_config = hash_config;
1581     }
1582 }
1583
1584 u32
1585 fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1586 {
1587     fib_entry_t *fib_entry;
1588
1589     fib_entry = fib_entry_get(fib_entry_index);
1590
1591     return (fib_entry->fe_lb.dpoi_index);
1592 }
1593
1594 static int
1595 fib_ip4_address_compare (const ip4_address_t * a1,
1596                          const ip4_address_t * a2)
1597 {
1598     /*
1599      * IP addresses are unsigned ints. the return value here needs to be signed
1600      * a simple subtraction won't cut it.
1601      * If the addresses are the same, the sort order is undefined, so phoey.
1602      */
1603     return ((clib_net_to_host_u32(a1->data_u32) >
1604              clib_net_to_host_u32(a2->data_u32) ) ?
1605             1 : -1);
1606 }
1607
1608 static int
1609 fib_ip6_address_compare (const ip6_address_t * a1,
1610                          const ip6_address_t * a2)
1611 {
1612   int i;
1613   for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1614   {
1615       int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1616                  clib_net_to_host_u16 (a2->as_u16[i]));
1617       if (cmp != 0)
1618           return cmp;
1619   }
1620   return 0;
1621 }
1622
1623 static int
1624 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1625                fib_node_index_t fib_entry_index2)
1626 {
1627     fib_entry_t *fib_entry1, *fib_entry2;
1628     int cmp = 0;
1629
1630     fib_entry1 = fib_entry_get(fib_entry_index1);
1631     fib_entry2 = fib_entry_get(fib_entry_index2);
1632
1633     switch (fib_entry1->fe_prefix.fp_proto)
1634     {
1635     case FIB_PROTOCOL_IP4:
1636         cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1637                                       &fib_entry2->fe_prefix.fp_addr.ip4);
1638         break;
1639     case FIB_PROTOCOL_IP6:
1640         cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1641                                       &fib_entry2->fe_prefix.fp_addr.ip6);
1642         break;
1643     case FIB_PROTOCOL_MPLS:
1644         cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1645
1646         if (0 == cmp)
1647         {
1648             cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1649         }
1650         break;
1651     }
1652
1653     if (0 == cmp) {
1654         cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1655     }
1656     return (cmp);
1657 }
1658
1659 int
1660 fib_entry_cmp_for_sort (void *i1, void *i2)
1661 {
1662     fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1663
1664     return (fib_entry_cmp(*fib_entry_index1,
1665                           *fib_entry_index2));
1666 }
1667
1668 void
1669 fib_entry_lock (fib_node_index_t fib_entry_index)
1670 {
1671     fib_entry_t *fib_entry;
1672
1673     fib_entry = fib_entry_get(fib_entry_index);
1674
1675     fib_node_lock(&fib_entry->fe_node);
1676 }
1677
1678 void
1679 fib_entry_unlock (fib_node_index_t fib_entry_index)
1680 {
1681     fib_entry_t *fib_entry;
1682
1683     fib_entry = fib_entry_get(fib_entry_index);
1684
1685     fib_node_unlock(&fib_entry->fe_node);
1686 }
1687
1688 void
1689 fib_entry_module_init (void)
1690 {
1691     fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1692     fib_entry_logger = vlib_log_register_class("fib", "entry");
1693
1694     fib_entry_track_module_init();
1695 }
1696
1697 fib_route_path_t *
1698 fib_entry_encode (fib_node_index_t fib_entry_index)
1699 {
1700     fib_path_ext_list_t *ext_list;
1701     fib_path_encode_ctx_t ctx = {
1702         .rpaths = NULL,
1703     };
1704     fib_entry_t *fib_entry;
1705     fib_entry_src_t *bsrc;
1706
1707     ext_list = NULL;
1708     fib_entry = fib_entry_get(fib_entry_index);
1709     bsrc = fib_entry_get_best_src_i(fib_entry);
1710
1711     if (bsrc)
1712     {
1713         ext_list = &bsrc->fes_path_exts;
1714     }
1715
1716     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1717     {
1718         fib_path_list_walk_w_ext(fib_entry->fe_parent,
1719                                  ext_list,
1720                                  fib_path_encode,
1721                                  &ctx);
1722     }
1723
1724     return (ctx.rpaths);
1725 }
1726
1727 const fib_prefix_t *
1728 fib_entry_get_prefix (fib_node_index_t fib_entry_index)
1729 {
1730     fib_entry_t *fib_entry;
1731
1732     fib_entry = fib_entry_get(fib_entry_index);
1733
1734     return (&fib_entry->fe_prefix);
1735 }
1736
1737 u32
1738 fib_entry_get_fib_index (fib_node_index_t fib_entry_index)
1739 {
1740     fib_entry_t *fib_entry;
1741
1742     fib_entry = fib_entry_get(fib_entry_index);
1743
1744     return (fib_entry->fe_fib_index);
1745 }
1746
1747 u32
1748 fib_entry_pool_size (void)
1749 {
1750     return (pool_elts(fib_entry_pool));
1751 }
1752
1753 #if CLIB_DEBUG > 0
1754 void
1755 fib_table_assert_empty (const fib_table_t *fib_table)
1756 {
1757     fib_node_index_t *fei, *feis = NULL;
1758     fib_entry_t *fib_entry;
1759
1760     pool_foreach (fib_entry, fib_entry_pool)
1761      {
1762         if (fib_entry->fe_fib_index == fib_table->ft_index)
1763             vec_add1 (feis, fib_entry_get_index(fib_entry));
1764     }
1765
1766     if (vec_len(feis))
1767     {
1768         vec_foreach (fei, feis)
1769             clib_error ("%U", format_fib_entry, *fei, FIB_ENTRY_FORMAT_DETAIL);
1770     }
1771
1772     ASSERT(0);
1773 }
1774 #endif
1775
1776 static clib_error_t *
1777 show_fib_entry_command (vlib_main_t * vm,
1778                         unformat_input_t * input,
1779                         vlib_cli_command_t * cmd)
1780 {
1781     fib_node_index_t fei;
1782
1783     if (unformat (input, "%d", &fei))
1784     {
1785         /*
1786          * show one in detail
1787          */
1788         if (!pool_is_free_index(fib_entry_pool, fei))
1789         {
1790             vlib_cli_output (vm, "%d@%U",
1791                              fei,
1792                              format_fib_entry, fei,
1793                              FIB_ENTRY_FORMAT_DETAIL2);
1794         }
1795         else
1796         {
1797             vlib_cli_output (vm, "entry %d invalid", fei);
1798         }
1799     }
1800     else
1801     {
1802         /*
1803          * show all
1804          */
1805         vlib_cli_output (vm, "FIB Entries:");
1806         pool_foreach_index (fei, fib_entry_pool)
1807          {
1808             vlib_cli_output (vm, "%d@%U",
1809                              fei,
1810                              format_fib_entry, fei,
1811                              FIB_ENTRY_FORMAT_BRIEF);
1812         }
1813     }
1814
1815     return (NULL);
1816 }
1817
1818 VLIB_CLI_COMMAND (show_fib_entry, static) = {
1819   .path = "show fib entry",
1820   .function = show_fib_entry_command,
1821   .short_help = "show fib entry",
1822 };