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