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