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