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