src/vnet/fib/fib_entry.c

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