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