src/vnet/fib/fib_entry.c

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