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