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