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