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