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