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