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