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 initialize 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 *rpaths)
 910 {
 911     fib_source_t best_source;
 912     fib_entry_t *fib_entry;
 913     fib_entry_src_t *bsrc;
 914
 915     fib_entry = fib_entry_get(fib_entry_index);
 916     ASSERT(NULL != fib_entry);
 917
 918     bsrc = fib_entry_get_best_src_i(fib_entry);
 919     best_source = fib_entry_src_get_source(bsrc);
 920
 921     fib_entry = fib_entry_src_action_path_add(fib_entry, source, flags, rpaths);
 922
 923     fib_entry_source_change(fib_entry, best_source, source);
 924
 925     FIB_ENTRY_DBG(fib_entry, "path add:%U", format_fib_source, source);
 926 }
 927
 928 static fib_entry_src_flag_t
 929 fib_entry_src_burn_only_inherited (fib_entry_t *fib_entry)
 930 {
 931     fib_entry_src_t *src;
 932     fib_source_t source;
 933     int has_only_inherited_sources = 1;
 934
 935     FOR_EACH_SRC_ADDED(fib_entry, src, source,
 936     ({
 937         if (!(src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 938         {
 939             has_only_inherited_sources = 0;
 940             break;
 941         }
 942     }));
 943     if (has_only_inherited_sources)
 944     {
 945         FOR_EACH_SRC_ADDED(fib_entry, src, source,
 946         ({
 947             fib_entry_src_action_remove(fib_entry, source);
 948         }));
 949         return (FIB_ENTRY_SRC_FLAG_NONE);
 950     }
 951     else
 952     {
 953         return (FIB_ENTRY_SRC_FLAG_ADDED);
 954     }
 955 }
 956
 957 static fib_entry_src_flag_t
 958 fib_entry_source_removed (fib_entry_t *fib_entry,
 959                           fib_entry_flag_t old_flags)
 960 {
 961     const fib_entry_src_t *bsrc;
 962     fib_source_t best_source;
 963
 964     /*
 965      * if all that is left are inherited sources, then burn them
 966      */
 967     fib_entry_src_burn_only_inherited(fib_entry);
 968
 969     bsrc = fib_entry_get_best_src_i(fib_entry);
 970     best_source = fib_entry_src_get_source(bsrc);
 971
 972     if (FIB_SOURCE_MAX == best_source)
 973     {
 974         /*
 975          * no more sources left. this entry is toast.
 976          */
 977         fib_entry = fib_entry_post_flag_update_actions(fib_entry, old_flags);
 978         fib_entry_src_action_uninstall(fib_entry);
 979
 980         return (FIB_ENTRY_SRC_FLAG_NONE);
 981     }
 982     else
 983     {
 984         fib_entry_src_action_activate(fib_entry, best_source);
 985     }
 986
 987     fib_entry_post_update_actions(fib_entry, best_source, old_flags);
 988
 989     /*
 990      * still have sources
 991      */
 992     return (FIB_ENTRY_SRC_FLAG_ADDED);
 993 }
 994
 995 /*
 996  * fib_entry_path_remove
 997  *
 998  * remove a path from the entry.
 999  * return the fib_entry's index if it is still present, INVALID otherwise.
1000  */
1001 fib_entry_src_flag_t
1002 fib_entry_path_remove (fib_node_index_t fib_entry_index,
1003                        fib_source_t source,
1004                        const fib_route_path_t *rpaths)
1005 {
1006     fib_entry_src_flag_t sflag;
1007     fib_source_t best_source;
1008     fib_entry_flag_t bflags;
1009     fib_entry_t *fib_entry;
1010     fib_entry_src_t *bsrc;
1011
1012     fib_entry = fib_entry_get(fib_entry_index);
1013     ASSERT(NULL != fib_entry);
1014
1015     bsrc = fib_entry_get_best_src_i(fib_entry);
1016     best_source = fib_entry_src_get_source(bsrc);
1017     bflags = fib_entry_src_get_flags(bsrc);
1018
1019     sflag = fib_entry_src_action_path_remove(fib_entry, source, rpaths);
1020
1021     FIB_ENTRY_DBG(fib_entry, "path remove:%U", format_fib_source, source);
1022
1023     /*
1024      * if the path list for the source passed is invalid,
1025      * then we need to create a new one. else we are updating
1026      * an existing.
1027      */
1028     if (source < best_source)
1029     {
1030         /*
1031          * Que! removing a path from a source that is better than the
1032          * one this entry is using.
1033          */
1034         ASSERT(0);
1035     }
1036     else if (source > best_source )
1037     {
1038         /*
1039          * the source is not the best. no need to update forwarding
1040          */
1041         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1042         {
1043             /*
1044              * the source being removed still has paths
1045              */
1046             return (FIB_ENTRY_SRC_FLAG_ADDED);
1047         }
1048         else
1049         {
1050             /*
1051              * that was the last path from this source, check if those
1052              * that remain are non-inherited
1053              */
1054             return (fib_entry_src_burn_only_inherited(fib_entry));
1055        }
1056     }
1057     else
1058     {
1059         /*
1060          * removing a path from the path-list we were using.
1061          */
1062         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1063         {
1064             /*
1065              * the last path from the source was removed.
1066              * fallback to lower source
1067              */
1068             return (fib_entry_source_removed(fib_entry, bflags));
1069         }
1070         else
1071         {
1072             /*
1073              * re-install the new forwarding information
1074              */
1075             fib_entry_src_action_reactivate(fib_entry, source);
1076         }
1077     }
1078
1079     fib_entry_post_update_actions(fib_entry, source, bflags);
1080
1081     /*
1082      * still have sources
1083      */
1084     return (FIB_ENTRY_SRC_FLAG_ADDED);
1085 }
1086
1087 /*
1088  * fib_entry_special_remove
1089  *
1090  * remove a special source from the entry.
1091  * return the fib_entry's index if it is still present, INVALID otherwise.
1092  */
1093 fib_entry_src_flag_t
1094 fib_entry_special_remove (fib_node_index_t fib_entry_index,
1095                           fib_source_t source)
1096 {
1097     fib_entry_src_flag_t sflag;
1098     fib_source_t best_source;
1099     fib_entry_flag_t bflags;
1100     fib_entry_t *fib_entry;
1101     fib_entry_src_t *bsrc;
1102
1103     fib_entry = fib_entry_get(fib_entry_index);
1104     ASSERT(NULL != fib_entry);
1105
1106     bsrc = fib_entry_get_best_src_i(fib_entry);
1107     best_source = fib_entry_src_get_source(bsrc);
1108     bflags = fib_entry_src_get_flags(bsrc);
1109
1110     FIB_ENTRY_DBG(fib_entry, "special remove:%U", format_fib_source, source);
1111
1112     sflag = fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1113
1114     /*
1115      * if the path list for the source passed is invalid,
1116      * then we need to create a new one. else we are updating
1117      * an existing.
1118      */
1119     if (source < best_source )
1120     {
1121         /*
1122          * Que! removing a path from a source that is better than the
1123          * one this entry is using. This can only mean it is a source
1124          * this prefix does not have.
1125          */
1126         return (FIB_ENTRY_SRC_FLAG_ADDED);
1127     }
1128     else if (source > best_source ) {
1129         /*
1130          * the source is not the best. no need to update forwarding
1131          */
1132         if (FIB_ENTRY_SRC_FLAG_ADDED & sflag)
1133         {
1134             /*
1135              * the source being removed still has paths
1136              */
1137             return (FIB_ENTRY_SRC_FLAG_ADDED);
1138         }
1139         else
1140         {
1141             /*
1142              * that was the last path from this source, check if those
1143              * that remain are non-inherited
1144              */
1145             if (FIB_ENTRY_SRC_FLAG_NONE == fib_entry_src_burn_only_inherited(fib_entry))
1146             {
1147                 /*
1148                  * no more sources left. this entry is toast.
1149                  */
1150                 fib_entry = fib_entry_post_flag_update_actions(fib_entry, bflags);
1151                 fib_entry_src_action_uninstall(fib_entry);
1152                 return (FIB_ENTRY_SRC_FLAG_NONE);
1153             }
1154
1155             /*
1156              * reactivate the best source so the interposer gets restacked
1157              */
1158             fib_entry_src_action_reactivate(fib_entry, best_source);
1159
1160             return (FIB_ENTRY_SRC_FLAG_ADDED);
1161         }
1162     }
1163     else
1164     {
1165         if (!(FIB_ENTRY_SRC_FLAG_ADDED & sflag))
1166         {
1167             /*
1168              * the source was removed. use the next best.
1169              */
1170             return (fib_entry_source_removed(fib_entry, bflags));
1171         }
1172         else
1173         {
1174             /*
1175              * re-install the new forwarding information
1176              */
1177             fib_entry_src_action_reactivate(fib_entry, source);
1178         }
1179     }
1180
1181     fib_entry_post_update_actions(fib_entry, source, bflags);
1182
1183     /*
1184      * still have sources
1185      */
1186     return (FIB_ENTRY_SRC_FLAG_ADDED);
1187 }
1188
1189 /**
1190  * fib_entry_inherit
1191  *
1192  * If the source on the cover is inheriting then push this source
1193  * down to the covered.
1194  */
1195 void
1196 fib_entry_inherit (fib_node_index_t cover,
1197                    fib_node_index_t covered)
1198 {
1199     fib_entry_src_inherit(fib_entry_get(cover),
1200                           fib_entry_get(covered));
1201 }
1202
1203 /**
1204  * fib_entry_delete
1205  *
1206  * The source is withdrawing all the paths it provided
1207  */
1208 fib_entry_src_flag_t
1209 fib_entry_delete (fib_node_index_t fib_entry_index,
1210                   fib_source_t source)
1211 {
1212     return (fib_entry_special_remove(fib_entry_index, source));
1213 }
1214
1215 /**
1216  * fib_entry_update
1217  *
1218  * The source has provided a new set of paths that will replace the old.
1219  */
1220 void
1221 fib_entry_update (fib_node_index_t fib_entry_index,
1222                   fib_source_t source,
1223                   fib_entry_flag_t flags,
1224                   const fib_route_path_t *paths)
1225 {
1226     fib_source_t best_source;
1227     fib_entry_flag_t bflags;
1228     fib_entry_t *fib_entry;
1229     fib_entry_src_t *bsrc;
1230
1231     fib_entry = fib_entry_get(fib_entry_index);
1232     ASSERT(NULL != fib_entry);
1233
1234     bsrc = fib_entry_get_best_src_i(fib_entry);
1235     best_source = fib_entry_src_get_source(bsrc);
1236     bflags = fib_entry_get_flags_i(fib_entry);
1237
1238     fib_entry = fib_entry_src_action_path_swap(fib_entry,
1239                                                source,
1240                                                flags,
1241                                                paths);
1242
1243     fib_entry_source_change_w_flags(fib_entry, best_source, bflags, source);
1244     FIB_ENTRY_DBG(fib_entry, "update");
1245 }
1246
1247
1248 /*
1249  * fib_entry_cover_changed
1250  *
1251  * this entry is tracking its cover and that cover has changed.
1252  */
1253 void
1254 fib_entry_cover_changed (fib_node_index_t fib_entry_index)
1255 {
1256     fib_entry_src_cover_res_t res = {
1257         .install = !0,
1258         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1259     };
1260     CLIB_UNUSED(fib_source_t source);
1261     fib_source_t best_source;
1262     fib_entry_flag_t bflags;
1263     fib_entry_t *fib_entry;
1264     fib_entry_src_t *esrc;
1265     u32 index;
1266
1267     bflags = FIB_ENTRY_FLAG_NONE;
1268     best_source = FIB_SOURCE_FIRST;
1269     fib_entry = fib_entry_get(fib_entry_index);
1270
1271     fib_attached_export_cover_change(fib_entry);
1272
1273     /*
1274      * propagate the notification to each of the added sources
1275      */
1276     index = 0;
1277     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1278     ({
1279         if (0 == index)
1280         {
1281             /*
1282              * only the best source gets to set the back walk flags
1283              */
1284             res = fib_entry_src_action_cover_change(fib_entry, esrc);
1285             bflags = fib_entry_src_get_flags(esrc);
1286             best_source = fib_entry_src_get_source(esrc);
1287         }
1288         else
1289         {
1290             fib_entry_src_action_cover_change(fib_entry, esrc);
1291         }
1292         index++;
1293     }));
1294
1295     if (res.install)
1296     {
1297         fib_entry_src_action_reactivate(fib_entry,
1298                                         fib_entry_src_get_source(
1299                                             fib_entry_get_best_src_i(fib_entry)));
1300         fib_entry_post_install_actions(fib_entry, best_source, bflags);
1301     }
1302     else
1303     {
1304         fib_entry_src_action_uninstall(fib_entry);
1305     }
1306
1307     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1308     {
1309         /*
1310          * time for walkies fido.
1311          */
1312         fib_node_back_walk_ctx_t bw_ctx = {
1313             .fnbw_reason = res.bw_reason,
1314         };
1315
1316         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1317     }
1318     FIB_ENTRY_DBG(fib_entry, "cover-changed");
1319 }
1320
1321 /*
1322  * fib_entry_cover_updated
1323  *
1324  * this entry is tracking its cover and that cover has been updated
1325  * (i.e. its forwarding information has changed).
1326  */
1327 void
1328 fib_entry_cover_updated (fib_node_index_t fib_entry_index)
1329 {
1330     fib_entry_src_cover_res_t res = {
1331         .install = !0,
1332         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
1333     };
1334     CLIB_UNUSED(fib_source_t source);
1335     fib_source_t best_source;
1336     fib_entry_flag_t bflags;
1337     fib_entry_t *fib_entry;
1338     fib_entry_src_t *esrc;
1339     u32 index;
1340
1341     bflags = FIB_ENTRY_FLAG_NONE;
1342     best_source = FIB_SOURCE_FIRST;
1343     fib_entry = fib_entry_get(fib_entry_index);
1344
1345     fib_attached_export_cover_update(fib_entry);
1346
1347     /*
1348      * propagate the notification to each of the added sources
1349      */
1350     index = 0;
1351     FOR_EACH_SRC_ADDED(fib_entry, esrc, source,
1352     ({
1353         if (0 == index)
1354         {
1355             /*
1356              * only the best source gets to set the back walk flags
1357              */
1358             res = fib_entry_src_action_cover_update(fib_entry, esrc);
1359             bflags = fib_entry_src_get_flags(esrc);
1360             best_source = fib_entry_src_get_source(esrc);
1361         }
1362         else
1363         {
1364             fib_entry_src_action_cover_update(fib_entry, esrc);
1365         }
1366         index++;
1367     }));
1368
1369     if (res.install)
1370     {
1371         fib_entry_src_action_reactivate(fib_entry,
1372                                         fib_entry_src_get_source(
1373                                             fib_entry_get_best_src_i(fib_entry)));
1374         fib_entry_post_install_actions(fib_entry, best_source, bflags);
1375     }
1376     else
1377     {
1378         fib_entry_src_action_uninstall(fib_entry);
1379     }
1380
1381     if (FIB_NODE_BW_REASON_FLAG_NONE != res.bw_reason)
1382     {
1383         /*
1384          * time for walkies fido.
1385          */
1386         fib_node_back_walk_ctx_t bw_ctx = {
1387             .fnbw_reason = res.bw_reason,
1388         };
1389
1390         fib_walk_sync(FIB_NODE_TYPE_ENTRY, fib_entry_index, &bw_ctx);
1391     }
1392     FIB_ENTRY_DBG(fib_entry, "cover-updated");
1393 }
1394
1395 int
1396 fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
1397                                  fib_node_index_t **entry_indicies)
1398 {
1399     fib_entry_t *fib_entry;
1400     int was_looped, is_looped;
1401
1402     fib_entry = fib_entry_get(entry_index);
1403
1404     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1405     {
1406         fib_node_index_t *entries = *entry_indicies;
1407
1408         vec_add1(entries, entry_index);
1409         was_looped = fib_path_list_is_looped(fib_entry->fe_parent);
1410         is_looped = fib_path_list_recursive_loop_detect(fib_entry->fe_parent,
1411                                                         &entries);
1412
1413         *entry_indicies = entries;
1414
1415         if (!!was_looped != !!is_looped)
1416         {
1417             /*
1418              * re-evaluate all the entry's forwarding
1419              * NOTE: this is an inplace modify
1420              */
1421             fib_entry_delegate_type_t fdt;
1422             fib_entry_delegate_t *fed;
1423
1424             FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
1425             {
1426                 fib_entry_src_mk_lb(fib_entry,
1427                                     fib_entry_get_best_src_i(fib_entry),
1428                                     fib_entry_delegate_type_to_chain_type(fdt),
1429                                     &fed->fd_dpo);
1430             });
1431         }
1432     }
1433     else
1434     {
1435         /*
1436          * the entry is currently not linked to a path-list. this happens
1437          * when it is this entry that is re-linking path-lists and has thus
1438          * broken the loop
1439          */
1440         is_looped = 0;
1441     }
1442
1443     return (is_looped);
1444 }
1445
1446 u32
1447 fib_entry_get_resolving_interface (fib_node_index_t entry_index)
1448 {
1449     fib_entry_t *fib_entry;
1450
1451     fib_entry = fib_entry_get(entry_index);
1452
1453     return (fib_path_list_get_resolving_interface(fib_entry->fe_parent));
1454 }
1455
1456 fib_source_t
1457 fib_entry_get_best_source (fib_node_index_t entry_index)
1458 {
1459     fib_entry_t *fib_entry;
1460     fib_entry_src_t *bsrc;
1461
1462     fib_entry = fib_entry_get(entry_index);
1463
1464     bsrc = fib_entry_get_best_src_i(fib_entry);
1465     return (fib_entry_src_get_source(bsrc));
1466 }
1467
1468 /**
1469  * Return !0 is the entry represents a host prefix
1470  */
1471 int
1472 fib_entry_is_host (fib_node_index_t fib_entry_index)
1473 {
1474     return (fib_prefix_is_host(fib_entry_get_prefix(fib_entry_index)));
1475 }
1476
1477 /**
1478  * Return !0 is the entry is resolved, i.e. will return a valid forwarding
1479  * chain
1480  */
1481 int
1482 fib_entry_is_resolved (fib_node_index_t fib_entry_index)
1483 {
1484     fib_entry_delegate_t *fed;
1485     fib_entry_t *fib_entry;
1486
1487     fib_entry = fib_entry_get(fib_entry_index);
1488
1489     fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
1490
1491     if (NULL == fed)
1492     {
1493         /*
1494          * no BFD tracking - consider it resolved.
1495          */
1496         return (!0);
1497     }
1498     else
1499     {
1500         /*
1501          * defer to the state of the BFD tracking
1502          */
1503         return (FIB_BFD_STATE_UP == fed->fd_bfd_state);
1504     }
1505 }
1506
1507 void
1508 fib_entry_set_flow_hash_config (fib_node_index_t fib_entry_index,
1509                                 flow_hash_config_t hash_config)
1510 {
1511     fib_entry_t *fib_entry;
1512
1513     fib_entry = fib_entry_get(fib_entry_index);
1514
1515     /*
1516      * pass the hash-config on to the load-balance object where it is cached.
1517      * we can ignore LBs in the delegate chains, since they will not be of the
1518      * correct protocol type (i.e. they are not IP)
1519      * There's no way, nor need, to change the hash config for MPLS.
1520      */
1521     if (dpo_id_is_valid(&fib_entry->fe_lb))
1522     {
1523         load_balance_t *lb;
1524
1525         ASSERT(DPO_LOAD_BALANCE == fib_entry->fe_lb.dpoi_type);
1526
1527         lb = load_balance_get(fib_entry->fe_lb.dpoi_index);
1528
1529         /*
1530          * atomic update for packets in flight
1531          */
1532         lb->lb_hash_config = hash_config;
1533     }
1534 }
1535
1536 u32
1537 fib_entry_get_stats_index (fib_node_index_t fib_entry_index)
1538 {
1539     fib_entry_t *fib_entry;
1540
1541     fib_entry = fib_entry_get(fib_entry_index);
1542
1543     return (fib_entry->fe_lb.dpoi_index);
1544 }
1545
1546 static int
1547 fib_ip4_address_compare (const ip4_address_t * a1,
1548                          const ip4_address_t * a2)
1549 {
1550     /*
1551      * IP addresses are unsigned ints. the return value here needs to be signed
1552      * a simple subtraction won't cut it.
1553      * If the addresses are the same, the sort order is undefined, so phoey.
1554      */
1555     return ((clib_net_to_host_u32(a1->data_u32) >
1556              clib_net_to_host_u32(a2->data_u32) ) ?
1557             1 : -1);
1558 }
1559
1560 static int
1561 fib_ip6_address_compare (const ip6_address_t * a1,
1562                          const ip6_address_t * a2)
1563 {
1564   int i;
1565   for (i = 0; i < ARRAY_LEN (a1->as_u16); i++)
1566   {
1567       int cmp = (clib_net_to_host_u16 (a1->as_u16[i]) -
1568                  clib_net_to_host_u16 (a2->as_u16[i]));
1569       if (cmp != 0)
1570           return cmp;
1571   }
1572   return 0;
1573 }
1574
1575 static int
1576 fib_entry_cmp (fib_node_index_t fib_entry_index1,
1577                fib_node_index_t fib_entry_index2)
1578 {
1579     fib_entry_t *fib_entry1, *fib_entry2;
1580     int cmp = 0;
1581
1582     fib_entry1 = fib_entry_get(fib_entry_index1);
1583     fib_entry2 = fib_entry_get(fib_entry_index2);
1584
1585     switch (fib_entry1->fe_prefix.fp_proto)
1586     {
1587     case FIB_PROTOCOL_IP4:
1588         cmp = fib_ip4_address_compare(&fib_entry1->fe_prefix.fp_addr.ip4,
1589                                       &fib_entry2->fe_prefix.fp_addr.ip4);
1590         break;
1591     case FIB_PROTOCOL_IP6:
1592         cmp = fib_ip6_address_compare(&fib_entry1->fe_prefix.fp_addr.ip6,
1593                                       &fib_entry2->fe_prefix.fp_addr.ip6);
1594         break;
1595     case FIB_PROTOCOL_MPLS:
1596         cmp = (fib_entry1->fe_prefix.fp_label - fib_entry2->fe_prefix.fp_label);
1597
1598         if (0 == cmp)
1599         {
1600             cmp = (fib_entry1->fe_prefix.fp_eos - fib_entry2->fe_prefix.fp_eos);
1601         }
1602         break;
1603     }
1604
1605     if (0 == cmp) {
1606         cmp = (fib_entry1->fe_prefix.fp_len - fib_entry2->fe_prefix.fp_len);
1607     }
1608     return (cmp);
1609 }
1610
1611 int
1612 fib_entry_cmp_for_sort (void *i1, void *i2)
1613 {
1614     fib_node_index_t *fib_entry_index1 = i1, *fib_entry_index2 = i2;
1615
1616     return (fib_entry_cmp(*fib_entry_index1,
1617                           *fib_entry_index2));
1618 }
1619
1620 void
1621 fib_entry_lock (fib_node_index_t fib_entry_index)
1622 {
1623     fib_entry_t *fib_entry;
1624
1625     fib_entry = fib_entry_get(fib_entry_index);
1626
1627     fib_node_lock(&fib_entry->fe_node);
1628 }
1629
1630 void
1631 fib_entry_unlock (fib_node_index_t fib_entry_index)
1632 {
1633     fib_entry_t *fib_entry;
1634
1635     fib_entry = fib_entry_get(fib_entry_index);
1636
1637     fib_node_unlock(&fib_entry->fe_node);
1638 }
1639
1640 void
1641 fib_entry_module_init (void)
1642 {
1643     fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
1644     fib_entry_logger = vlib_log_register_class("fib", "entry");
1645 }
1646
1647 fib_route_path_t *
1648 fib_entry_encode (fib_node_index_t fib_entry_index)
1649 {
1650     fib_path_ext_list_t *ext_list;
1651     fib_path_encode_ctx_t ctx = {
1652         .rpaths = NULL,
1653     };
1654     fib_entry_t *fib_entry;
1655     fib_entry_src_t *bsrc;
1656
1657     ext_list = NULL;
1658     fib_entry = fib_entry_get(fib_entry_index);
1659     bsrc = fib_entry_get_best_src_i(fib_entry);
1660
1661     if (bsrc)
1662     {
1663         ext_list = &bsrc->fes_path_exts;
1664     }
1665
1666     if (FIB_NODE_INDEX_INVALID != fib_entry->fe_parent)
1667     {
1668         fib_path_list_walk_w_ext(fib_entry->fe_parent,
1669                                  ext_list,
1670                                  fib_path_encode,
1671                                  &ctx);
1672     }
1673
1674     return (ctx.rpaths);
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 };