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