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