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