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