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