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