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