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