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