src/vnet/fib/fib_entry.c

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