src/vnet/fib/fib_entry_src.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 <vnet/adj/adj.h>
  17 #include <vnet/dpo/load_balance.h>
  18 #include <vnet/dpo/mpls_label_dpo.h>
  19 #include <vnet/dpo/drop_dpo.h>
  20 #include <vnet/dpo/replicate_dpo.h>
  21
  22 #include <vnet/fib/fib_entry_src.h>
  23 #include <vnet/fib/fib_table.h>
  24 #include <vnet/fib/fib_path_ext.h>
  25 #include <vnet/fib/fib_urpf_list.h>
  26
  27 /*
  28  * per-source type vft
  29  */
  30 static fib_entry_src_vft_t fib_entry_src_vft[FIB_SOURCE_MAX];
  31
  32 /**
  33  * Get the VFT for a given source. This is a combination of the source
  34  * enum and the interposer flags
  35  */
  36 const fib_entry_src_vft_t*
  37 fib_entry_src_get_vft (const fib_entry_src_t *esrc)
  38 {
  39     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_INTERPOSE)
  40     {
  41         return (&fib_entry_src_vft[FIB_SOURCE_INTERPOSE]);
  42     }
  43
  44     return (&fib_entry_src_vft[esrc->fes_src]);
  45 }
  46
  47 static void
  48 fib_entry_src_copy_default (const fib_entry_src_t *orig_src,
  49                             const fib_entry_t *fib_entry,
  50                             fib_entry_src_t *copy_src)
  51 {
  52     clib_memcpy(&copy_src->u, &orig_src->u, sizeof(copy_src->u));
  53 }
  54
  55 void
  56 fib_entry_src_register (fib_source_t source,
  57                         const fib_entry_src_vft_t *vft)
  58 {
  59     fib_entry_src_vft[source] = *vft;
  60
  61     if (NULL == fib_entry_src_vft[source].fesv_copy)
  62     {
  63         fib_entry_src_vft[source].fesv_copy = fib_entry_src_copy_default;
  64     }
  65 }
  66
  67 static int
  68 fib_entry_src_cmp_for_sort (void * v1,
  69                             void * v2)
  70 {
  71     fib_entry_src_t *esrc1 = v1, *esrc2 = v2;
  72
  73     return (esrc1->fes_src - esrc2->fes_src);
  74 }
  75
  76 static void
  77 fib_entry_src_action_init (fib_entry_t *fib_entry,
  78                            fib_source_t source,
  79                            fib_entry_flag_t flags)
  80 {
  81     fib_entry_src_t esrc = {
  82         .fes_pl = FIB_NODE_INDEX_INVALID,
  83         .fes_flags = FIB_ENTRY_SRC_FLAG_NONE,
  84         .fes_src = source,
  85         .fes_entry_flags = flags,
  86     };
  87
  88     FIB_ENTRY_SRC_VFT_INVOKE(&esrc, fesv_init, (&esrc));
  89
  90     vec_add1(fib_entry->fe_srcs, esrc);
  91     vec_sort_with_function(fib_entry->fe_srcs,
  92                            fib_entry_src_cmp_for_sort);
  93 }
  94
  95 static fib_entry_src_t *
  96 fib_entry_src_find_i (const fib_entry_t *fib_entry,
  97                       fib_source_t source,
  98                       u32 *index)
  99
 100 {
 101     fib_entry_src_t *esrc;
 102     int ii;
 103
 104     ii = 0;
 105     vec_foreach(esrc, fib_entry->fe_srcs)
 106     {
 107         if (esrc->fes_src == source)
 108         {
 109             if (NULL != index)
 110             {
 111                 *index = ii;
 112             }
 113             return (esrc);
 114         }
 115         else
 116         {
 117             ii++;
 118         }
 119     }
 120
 121     return (NULL);
 122 }
 123
 124 static fib_entry_src_t *
 125 fib_entry_src_find (const fib_entry_t *fib_entry,
 126                     fib_source_t source)
 127
 128 {
 129     return (fib_entry_src_find_i(fib_entry, source, NULL));
 130 }
 131
 132 int
 133 fib_entry_is_sourced (fib_node_index_t fib_entry_index,
 134                       fib_source_t source)
 135 {
 136     fib_entry_t *fib_entry;
 137
 138     fib_entry = fib_entry_get(fib_entry_index);
 139
 140     return (NULL != fib_entry_src_find(fib_entry, source));
 141 }
 142
 143 static fib_entry_src_t *
 144 fib_entry_src_find_or_create (fib_entry_t *fib_entry,
 145                               fib_source_t source,
 146                               fib_entry_flag_t flags)
 147 {
 148     fib_entry_src_t *esrc;
 149
 150     esrc = fib_entry_src_find(fib_entry, source);
 151
 152     if (NULL == esrc)
 153     {
 154         fib_entry_src_action_init(fib_entry, source, flags);
 155     }
 156
 157     return (fib_entry_src_find(fib_entry, source));
 158 }
 159
 160 static void
 161 fib_entry_src_action_deinit (fib_entry_t *fib_entry,
 162                              fib_source_t source)
 163
 164 {
 165     fib_entry_src_t *esrc;
 166     u32 index = ~0;
 167
 168     esrc = fib_entry_src_find_i(fib_entry, source, &index);
 169
 170     ASSERT(NULL != esrc);
 171
 172     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_deinit, (esrc));
 173
 174     fib_path_ext_list_flush(&esrc->fes_path_exts);
 175     vec_del1(fib_entry->fe_srcs, index);
 176     vec_sort_with_function(fib_entry->fe_srcs,
 177                            fib_entry_src_cmp_for_sort);
 178 }
 179
 180 fib_entry_src_cover_res_t
 181 fib_entry_src_action_cover_change (fib_entry_t *fib_entry,
 182                                    fib_entry_src_t *esrc)
 183 {
 184     FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_cover_change,
 185                                         (esrc, fib_entry));
 186
 187     fib_entry_src_cover_res_t res = {
 188         .install = !0,
 189         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
 190     };
 191     return (res);
 192 }
 193
 194 fib_entry_src_cover_res_t
 195 fib_entry_src_action_cover_update (fib_entry_t *fib_entry,
 196                                    fib_entry_src_t *esrc)
 197 {
 198     FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_cover_update,
 199                                         (esrc, fib_entry));
 200
 201     fib_entry_src_cover_res_t res = {
 202         .install = !0,
 203         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
 204     };
 205     return (res);
 206 }
 207
 208 typedef struct fib_entry_src_collect_forwarding_ctx_t_
 209 {
 210     load_balance_path_t *next_hops;
 211     const fib_entry_t *fib_entry;
 212     const fib_entry_src_t *esrc;
 213     fib_forward_chain_type_t fct;
 214     int n_recursive_constrained;
 215     u16 preference;
 216 } fib_entry_src_collect_forwarding_ctx_t;
 217
 218 /**
 219  * @brief Determine whether this FIB entry should use a load-balance MAP
 220  * to support PIC edge fast convergence
 221  */
 222 load_balance_flags_t
 223 fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
 224 {
 225     /**
 226      * We'll use a LB map if the path-list has multiple recursive paths.
 227      * recursive paths implies BGP, and hence scale.
 228      */
 229     if (ctx->n_recursive_constrained > 1 &&
 230         fib_path_list_is_popular(ctx->esrc->fes_pl))
 231     {
 232         return (LOAD_BALANCE_FLAG_USES_MAP);
 233     }
 234     return (LOAD_BALANCE_FLAG_NONE);
 235 }
 236
 237 static int
 238 fib_entry_src_valid_out_label (mpls_label_t label)
 239 {
 240     return ((MPLS_LABEL_IS_REAL(label) ||
 241              MPLS_LABEL_POP == label ||
 242              MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
 243              MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
 244              MPLS_IETF_IMPLICIT_NULL_LABEL == label));
 245 }
 246
 247 /**
 248  * @brief Turn the chain type requested by the client into the one they
 249  * really wanted
 250  */
 251 fib_forward_chain_type_t
 252 fib_entry_chain_type_fixup (const fib_entry_t *entry,
 253                             fib_forward_chain_type_t fct)
 254 {
 255     /*
 256      * The EOS chain is a tricky since one cannot know the adjacency
 257      * to link to without knowing what the packets payload protocol
 258      * will be once the label is popped.
 259      */
 260     fib_forward_chain_type_t dfct;
 261
 262     if (FIB_FORW_CHAIN_TYPE_MPLS_EOS != fct)
 263     {
 264         return (fct);
 265     }
 266
 267     dfct = fib_entry_get_default_chain_type(entry);
 268
 269     if (FIB_FORW_CHAIN_TYPE_MPLS_EOS == dfct)
 270     {
 271         /*
 272          * If the entry being asked is a eos-MPLS label entry,
 273          * then use the payload-protocol field, that we stashed there
 274          * for just this purpose
 275          */
 276         return (fib_forw_chain_type_from_dpo_proto(
 277                     entry->fe_prefix.fp_payload_proto));
 278     }
 279     /*
 280      * else give them what this entry would be by default. i.e. if it's a v6
 281      * entry, then the label its local labelled should be carrying v6 traffic.
 282      * If it's a non-EOS label entry, then there are more labels and we want
 283      * a non-eos chain.
 284      */
 285     return (dfct);
 286 }
 287
 288 static dpo_proto_t
 289 fib_prefix_get_payload_proto (const fib_prefix_t *pfx)
 290 {
 291     switch (pfx->fp_proto)
 292     {
 293     case FIB_PROTOCOL_IP4:
 294         return (DPO_PROTO_IP4);
 295     case FIB_PROTOCOL_IP6:
 296         return (DPO_PROTO_IP6);
 297     case FIB_PROTOCOL_MPLS:
 298         return (pfx->fp_payload_proto);
 299     }
 300
 301     ASSERT(0);
 302     return (DPO_PROTO_IP4);
 303 }
 304
 305 static void
 306 fib_entry_src_get_path_forwarding (fib_node_index_t path_index,
 307                                    fib_entry_src_collect_forwarding_ctx_t *ctx)
 308 {
 309     load_balance_path_t *nh;
 310
 311     /*
 312      * no extension => no out-going label for this path. that's OK
 313      * in the case of an IP or EOS chain, but not for non-EOS
 314      */
 315     switch (ctx->fct)
 316     {
 317     case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
 318     case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
 319     case FIB_FORW_CHAIN_TYPE_MCAST_IP4:
 320     case FIB_FORW_CHAIN_TYPE_MCAST_IP6:
 321     case FIB_FORW_CHAIN_TYPE_BIER:
 322         /*
 323          * EOS traffic with no label to stack, we need the IP Adj
 324          */
 325         vec_add2(ctx->next_hops, nh, 1);
 326
 327         nh->path_index = path_index;
 328         nh->path_weight = fib_path_get_weight(path_index);
 329         fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
 330
 331         break;
 332     case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
 333         if (fib_path_is_exclusive(path_index) ||
 334             fib_path_is_deag(path_index))
 335         {
 336             vec_add2(ctx->next_hops, nh, 1);
 337
 338             nh->path_index = path_index;
 339             nh->path_weight = fib_path_get_weight(path_index);
 340             fib_path_contribute_forwarding(path_index,
 341                                            FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 342                                            &nh->path_dpo);
 343         }
 344         break;
 345     case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
 346         {
 347             /*
 348              * no label. we need a chain based on the payload. fixup.
 349              */
 350             vec_add2(ctx->next_hops, nh, 1);
 351
 352             nh->path_index = path_index;
 353             nh->path_weight = fib_path_get_weight(path_index);
 354             fib_path_contribute_forwarding(path_index,
 355                                            fib_entry_chain_type_fixup(ctx->fib_entry,
 356                                                                       ctx->fct),
 357                                            &nh->path_dpo);
 358             fib_path_stack_mpls_disp(path_index,
 359                                      fib_prefix_get_payload_proto(&ctx->fib_entry->fe_prefix),
 360                                      FIB_MPLS_LSP_MODE_PIPE,
 361                                      &nh->path_dpo);
 362
 363             break;
 364         }
 365     case FIB_FORW_CHAIN_TYPE_ETHERNET:
 366     case FIB_FORW_CHAIN_TYPE_NSH:
 367         ASSERT(0);
 368         break;
 369     }
 370 }
 371
 372 static fib_path_list_walk_rc_t
 373 fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
 374                                   fib_node_index_t path_index,
 375                                   void *arg)
 376 {
 377     fib_entry_src_collect_forwarding_ctx_t *ctx;
 378     fib_path_ext_t *path_ext;
 379     u32 n_nhs;
 380
 381     ctx = arg;
 382     n_nhs = vec_len(ctx->next_hops);
 383
 384     /*
 385      * if the path is not resolved, don't include it.
 386      */
 387     if (!fib_path_is_resolved(path_index))
 388     {
 389         return (FIB_PATH_LIST_WALK_CONTINUE);
 390     }
 391
 392     if (fib_path_is_recursive_constrained(path_index))
 393     {
 394         ctx->n_recursive_constrained += 1;
 395     }
 396     if (0xffff == ctx->preference)
 397     {
 398         /*
 399          * not set a preference yet, so the first path we encounter
 400          * sets the preference we are collecting.
 401          */
 402         ctx->preference = fib_path_get_preference(path_index);
 403     }
 404     else if (ctx->preference != fib_path_get_preference(path_index))
 405     {
 406         /*
 407          * this path does not belong to the same preference as the
 408          * previous paths encountered. we are done now.
 409          */
 410         return (FIB_PATH_LIST_WALK_STOP);
 411     }
 412
 413     /*
 414      * get the matching path-extension for the path being visited.
 415      */
 416     path_ext = fib_path_ext_list_find_by_path_index(&ctx->esrc->fes_path_exts,
 417                                                     path_index);
 418
 419     if (NULL != path_ext)
 420     {
 421         switch (path_ext->fpe_type)
 422         {
 423         case FIB_PATH_EXT_MPLS:
 424             if (fib_entry_src_valid_out_label(path_ext->fpe_label_stack[0].fml_value))
 425             {
 426                 /*
 427                  * found a matching extension. stack it to obtain the forwarding
 428                  * info for this path.
 429                  */
 430                 ctx->next_hops =
 431                     fib_path_ext_stack(path_ext,
 432                                        ctx->fct,
 433                                        fib_entry_chain_type_fixup(ctx->fib_entry,
 434                                                                   ctx->fct),
 435                                        ctx->next_hops);
 436             }
 437             else
 438             {
 439                 fib_entry_src_get_path_forwarding(path_index, ctx);
 440             }
 441             break;
 442         case FIB_PATH_EXT_ADJ:
 443             if (FIB_PATH_EXT_ADJ_FLAG_REFINES_COVER & path_ext->fpe_adj_flags)
 444             {
 445                 fib_entry_src_get_path_forwarding(path_index, ctx);
 446             }
 447             /*
 448              * else
 449              *  the path does not refine the cover, meaning that
 450              *  the adjacency does/does not match the sub-net on the link.
 451              *  So this path does not contribute forwarding.
 452              */
 453             break;
 454         }
 455     }
 456     else
 457     {
 458         fib_entry_src_get_path_forwarding(path_index, ctx);
 459     }
 460
 461     /*
 462      * a this point 'ctx' has the DPO the path contributed, plus
 463      * any labels from path extensions.
 464      * check if there are any interpose sources that want to contribute
 465      */
 466     if (n_nhs < vec_len(ctx->next_hops))
 467     {
 468         /*
 469          * the path contributed a new choice.
 470          */
 471         const fib_entry_src_vft_t *vft;
 472
 473         vft = fib_entry_src_get_vft(ctx->esrc);
 474
 475         if (NULL != vft->fesv_contribute_interpose)
 476         {
 477             const dpo_id_t *interposer;
 478
 479             interposer = vft->fesv_contribute_interpose(ctx->esrc,
 480                                                         ctx->fib_entry);
 481
 482             if (NULL != interposer)
 483             {
 484                 dpo_id_t clone = DPO_INVALID;
 485
 486                 dpo_mk_interpose(interposer,
 487                                  &ctx->next_hops[n_nhs].path_dpo,
 488                                  &clone);
 489
 490                 dpo_copy(&ctx->next_hops[n_nhs].path_dpo, &clone);
 491                 dpo_reset(&clone);
 492             }
 493         }
 494     }
 495
 496     return (FIB_PATH_LIST_WALK_CONTINUE);
 497 }
 498
 499 void
 500 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
 501                      const fib_entry_src_t *esrc,
 502                      fib_forward_chain_type_t fct,
 503                      dpo_id_t *dpo_lb)
 504 {
 505     dpo_proto_t lb_proto;
 506
 507     /*
 508      * If the entry has path extensions then we construct a load-balance
 509      * by stacking the extensions on the forwarding chains of the paths.
 510      * Otherwise we use the load-balance of the path-list
 511      */
 512     fib_entry_src_collect_forwarding_ctx_t ctx = {
 513         .esrc = esrc,
 514         .fib_entry = fib_entry,
 515         .next_hops = NULL,
 516         .n_recursive_constrained = 0,
 517         .fct = fct,
 518         .preference = 0xffff,
 519     };
 520
 521     /*
 522      * As an optimisation we allocate the vector of next-hops to be sized
 523      * equal to the maximum number of paths we will need, which is also the
 524      * most likely number we will need, since in most cases the paths are 'up'.
 525      */
 526     vec_validate(ctx.next_hops, fib_path_list_get_n_paths(esrc->fes_pl));
 527     vec_reset_length(ctx.next_hops);
 528
 529     lb_proto = fib_forw_chain_type_to_dpo_proto(fct);
 530
 531     fib_path_list_walk(esrc->fes_pl,
 532                        fib_entry_src_collect_forwarding,
 533                        &ctx);
 534
 535     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
 536     {
 537         /*
 538          * the client provided the DPO that the entry should link to.
 539          * all entries must link to a LB, so if it is an LB already
 540          * then we can use it.
 541          */
 542         if ((1 == vec_len(ctx.next_hops)) &&
 543             (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
 544         {
 545             dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
 546             dpo_reset(&ctx.next_hops[0].path_dpo);
 547             return;
 548         }
 549     }
 550
 551     if (!dpo_id_is_valid(dpo_lb))
 552     {
 553         /*
 554          * first time create
 555          */
 556         if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
 557         {
 558             dpo_set(dpo_lb,
 559                     DPO_REPLICATE,
 560                     lb_proto,
 561                     MPLS_IS_REPLICATE | replicate_create(0, lb_proto));
 562         }
 563         else
 564         {
 565             fib_protocol_t flow_hash_proto;
 566             flow_hash_config_t fhc;
 567
 568             /*
 569              * if the protocol for the LB we are building does not match that
 570              * of the fib_entry (i.e. we are build the [n]EOS LB for an IPv[46]
 571              * then the fib_index is not an index that relates to the table
 572              * type we need. So get the default flow-hash config instead.
 573              */
 574             flow_hash_proto = dpo_proto_to_fib(lb_proto);
 575             if (fib_entry->fe_prefix.fp_proto != flow_hash_proto)
 576             {
 577                 fhc = fib_table_get_default_flow_hash_config(flow_hash_proto);
 578             }
 579             else
 580             {
 581                 fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
 582                                                      flow_hash_proto);
 583             }
 584
 585             dpo_set(dpo_lb,
 586                     DPO_LOAD_BALANCE,
 587                     lb_proto,
 588                     load_balance_create(0, lb_proto, fhc));
 589         }
 590     }
 591
 592     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_MULTICAST)
 593     {
 594         /*
 595          * MPLS multicast
 596          */
 597         replicate_multipath_update(dpo_lb, ctx.next_hops);
 598     }
 599     else
 600     {
 601         load_balance_multipath_update(dpo_lb,
 602                                       ctx.next_hops,
 603                                       fib_entry_calc_lb_flags(&ctx));
 604         vec_free(ctx.next_hops);
 605
 606         /*
 607          * if this entry is sourced by the uRPF-exempt source then we
 608          * append the always present local0 interface (index 0) to the
 609          * uRPF list so it is not empty. that way packets pass the loose check.
 610          */
 611         index_t ui = fib_path_list_get_urpf(esrc->fes_pl);
 612
 613         if ((fib_entry_is_sourced(fib_entry_get_index(fib_entry),
 614                                   FIB_SOURCE_URPF_EXEMPT) ||
 615              (esrc->fes_entry_flags & FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT))&&
 616             (0 == fib_urpf_check_size(ui)))
 617         {
 618             /*
 619              * The uRPF list we get from the path-list is shared by all
 620              * other users of the list, but the uRPF exemption applies
 621              * only to this prefix. So we need our own list.
 622              */
 623             ui = fib_urpf_list_alloc_and_lock();
 624             fib_urpf_list_append(ui, 0);
 625             fib_urpf_list_bake(ui);
 626             load_balance_set_urpf(dpo_lb->dpoi_index, ui);
 627             fib_urpf_list_unlock(ui);
 628         }
 629         else
 630         {
 631             load_balance_set_urpf(dpo_lb->dpoi_index, ui);
 632         }
 633         load_balance_set_fib_entry_flags(dpo_lb->dpoi_index,
 634                                          fib_entry_get_flags_i(fib_entry));
 635     }
 636 }
 637
 638 void
 639 fib_entry_src_action_install (fib_entry_t *fib_entry,
 640                               fib_source_t source)
 641 {
 642     /*
 643      * Install the forwarding chain for the given source into the forwarding
 644      * tables
 645      */
 646     fib_forward_chain_type_t fct;
 647     fib_entry_src_t *esrc;
 648     int insert;
 649
 650     fct = fib_entry_get_default_chain_type(fib_entry);
 651     esrc = fib_entry_src_find(fib_entry, source);
 652
 653     /*
 654      * Every entry has its own load-balance object. All changes to the entry's
 655      * forwarding result in an inplace modify of the load-balance. This means
 656      * the load-balance object only needs to be added to the forwarding
 657      * DB once, when it is created.
 658      */
 659     insert = !dpo_id_is_valid(&fib_entry->fe_lb);
 660
 661     fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb);
 662
 663     ASSERT(dpo_id_is_valid(&fib_entry->fe_lb));
 664     FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb);
 665
 666     /*
 667      * insert the adj into the data-plane forwarding trie
 668      */
 669     if (insert)
 670     {
 671        fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
 672                                    &fib_entry->fe_prefix,
 673                                    &fib_entry->fe_lb);
 674     }
 675
 676     /*
 677      * if any of the other chain types are already created they will need
 678      * updating too
 679      */
 680     fib_entry_delegate_type_t fdt;
 681     fib_entry_delegate_t *fed;
 682
 683     FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
 684     {
 685         fib_entry_src_mk_lb(fib_entry, esrc,
 686                             fib_entry_delegate_type_to_chain_type(fdt),
 687                             &fed->fd_dpo);
 688     });
 689 }
 690
 691 void
 692 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
 693 {
 694     /*
 695      * uninstall the forwarding chain from the forwarding tables
 696      */
 697     FIB_ENTRY_DBG(fib_entry, "uninstall");
 698
 699     if (dpo_id_is_valid(&fib_entry->fe_lb))
 700     {
 701         fib_table_fwding_dpo_remove(
 702             fib_entry->fe_fib_index,
 703             &fib_entry->fe_prefix,
 704             &fib_entry->fe_lb);
 705
 706         dpo_reset(&fib_entry->fe_lb);
 707     }
 708 }
 709
 710 static void
 711 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
 712 {
 713     fib_node_index_t *entries = NULL;
 714
 715     fib_path_list_recursive_loop_detect(path_list_index, &entries);
 716
 717     vec_free(entries);
 718 }
 719
 720 /*
 721  * fib_entry_src_action_copy
 722  *
 723  * copy a source data from another entry to this one
 724  */
 725 static fib_entry_t *
 726 fib_entry_src_action_copy (fib_entry_t *fib_entry,
 727                            const fib_entry_src_t *orig_src)
 728 {
 729     fib_entry_src_t *esrc;
 730
 731     esrc = fib_entry_src_find_or_create(fib_entry,
 732                                         orig_src->fes_src,
 733                                         orig_src->fes_entry_flags);
 734
 735     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_copy,
 736                              (orig_src, fib_entry, esrc));
 737
 738     fib_path_list_unlock(esrc->fes_pl);
 739
 740     /*
 741      * copy over all the data ...
 742      */
 743     esrc->fes_flags = orig_src->fes_flags;
 744     esrc->fes_pl = orig_src->fes_pl;
 745
 746     /*
 747      *  ... then update
 748      */
 749     esrc->fes_ref_count = 1;
 750     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_INHERITED;
 751     esrc->fes_flags &= ~(FIB_ENTRY_SRC_FLAG_ACTIVE |
 752                          FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
 753     esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
 754
 755     /*
 756      * the source owns a lock on the entry
 757      */
 758     fib_path_list_lock(esrc->fes_pl);
 759     fib_entry_lock(fib_entry_get_index(fib_entry));
 760
 761     return (fib_entry);
 762 }
 763
 764 /*
 765  * fib_entry_src_action_update
 766  *
 767  * copy a source data from another entry to this one
 768  */
 769 static fib_entry_src_t *
 770 fib_entry_src_action_update_from_cover (fib_entry_t *fib_entry,
 771                                         const fib_entry_src_t *orig_src)
 772 {
 773     fib_entry_src_t *esrc;
 774
 775     esrc = fib_entry_src_find_or_create(fib_entry,
 776                                         orig_src->fes_src,
 777                                         orig_src->fes_entry_flags);
 778
 779     /*
 780      * the source owns a lock on the entry
 781      */
 782     fib_path_list_unlock(esrc->fes_pl);
 783     esrc->fes_pl = orig_src->fes_pl;
 784     fib_path_list_lock(esrc->fes_pl);
 785
 786     return (esrc);
 787 }
 788
 789 static fib_table_walk_rc_t
 790 fib_entry_src_covered_inherit_add_i (fib_entry_t *fib_entry,
 791                                      const fib_entry_src_t *cover_src)
 792 {
 793     fib_entry_src_t *esrc;
 794
 795     esrc = fib_entry_src_find(fib_entry, cover_src->fes_src);
 796
 797     if (cover_src == esrc)
 798     {
 799         return (FIB_TABLE_WALK_CONTINUE);
 800     }
 801
 802     if (NULL != esrc)
 803     {
 804         /*
 805          * the covered entry already has this source.
 806          */
 807         if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
 808         {
 809             /*
 810              * the covered source is itself a COVERED_INHERIT, i.e.
 811              * it also pushes this source down the sub-tree.
 812              * We consider this more specific covered to be the owner
 813              * of the sub-tree from this point down.
 814              */
 815             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 816         }
 817         if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
 818         {
 819             /*
 820              * The covered's source data has been inherited, presumably
 821              * from this cover, i.e. this is a modify.
 822              */
 823             esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
 824             fib_entry_source_change(fib_entry, esrc->fes_src, esrc->fes_src);
 825         }
 826         else
 827         {
 828             /*
 829              * The covered's source was not inherited and it is also
 830              * not inheriting. Nevertheless, it still owns the sub-tree from
 831              * this point down.
 832              */
 833             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 834         }
 835     }
 836     else
 837     {
 838         /*
 839          * The covered does not have this source - add it.
 840          */
 841         fib_source_t best_source;
 842
 843         best_source = fib_entry_get_best_source(
 844             fib_entry_get_index(fib_entry));
 845
 846         fib_entry_src_action_copy(fib_entry, cover_src);
 847         fib_entry_source_change(fib_entry, best_source, cover_src->fes_src);
 848
 849     }
 850     return (FIB_TABLE_WALK_CONTINUE);
 851 }
 852
 853 static fib_table_walk_rc_t
 854 fib_entry_src_covered_inherit_walk_add (fib_node_index_t fei,
 855                                         void *ctx)
 856 {
 857     return (fib_entry_src_covered_inherit_add_i(fib_entry_get(fei), ctx));
 858 }
 859
 860 static fib_table_walk_rc_t
 861 fib_entry_src_covered_inherit_walk_remove (fib_node_index_t fei,
 862                                            void *ctx)
 863 {
 864     fib_entry_src_t *cover_src, *esrc;
 865     fib_entry_t *fib_entry;
 866
 867     fib_entry = fib_entry_get(fei);
 868
 869     cover_src = ctx;
 870     esrc = fib_entry_src_find(fib_entry, cover_src->fes_src);
 871
 872     if (cover_src == esrc)
 873     {
 874         return (FIB_TABLE_WALK_CONTINUE);
 875     }
 876
 877     if (NULL != esrc)
 878     {
 879         /*
 880          * the covered entry already has this source.
 881          */
 882         if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
 883         {
 884             /*
 885              * the covered source is itself a COVERED_INHERIT, i.e.
 886              * it also pushes this source down the sub-tree.
 887              * We consider this more specific covered to be the owner
 888              * of the sub-tree from this point down.
 889              */
 890             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 891         }
 892         if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
 893         {
 894             /*
 895              * The covered's source data has been inherited, presumably
 896              * from this cover
 897              */
 898             fib_entry_src_flag_t remaining;
 899
 900             remaining = fib_entry_special_remove(fei, cover_src->fes_src);
 901
 902             ASSERT(FIB_ENTRY_SRC_FLAG_ADDED == remaining);
 903         }
 904         else
 905         {
 906             /*
 907              * The covered's source was not inherited and it is also
 908              * not inheriting. Nevertheless, it still owns the sub-tree from
 909              * this point down.
 910              */
 911             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 912         }
 913     }
 914     else
 915     {
 916         /*
 917          * The covered does not have this source - that's an error,
 918          * since it should have inherited, but there is nothing we can do
 919          * about it now.
 920          */
 921     }
 922     return (FIB_TABLE_WALK_CONTINUE);
 923 }
 924
 925 void
 926 fib_entry_src_inherit (const fib_entry_t *cover,
 927                        fib_entry_t *covered)
 928 {
 929     CLIB_UNUSED(fib_source_t source);
 930     const fib_entry_src_t *src;
 931
 932     FOR_EACH_SRC_ADDED(cover, src, source,
 933     ({
 934         if ((src->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
 935             (src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 936         {
 937             fib_entry_src_covered_inherit_add_i(covered, src);
 938         }
 939     }))
 940 }
 941
 942 static void
 943 fib_entry_src_covered_inherit_add (fib_entry_t *fib_entry,
 944                                    fib_source_t source)
 945
 946 {
 947     fib_entry_src_t *esrc;
 948
 949     esrc = fib_entry_src_find(fib_entry, source);
 950
 951     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
 952
 953     if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
 954         (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 955     {
 956         fib_table_sub_tree_walk(fib_entry->fe_fib_index,
 957                                 fib_entry->fe_prefix.fp_proto,
 958                                 &fib_entry->fe_prefix,
 959                                 fib_entry_src_covered_inherit_walk_add,
 960                                 esrc);
 961     }
 962 }
 963
 964 static void
 965 fib_entry_src_covered_inherit_remove (fib_entry_t *fib_entry,
 966                                       fib_entry_src_t *esrc)
 967
 968 {
 969     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
 970
 971     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
 972     {
 973         fib_table_sub_tree_walk(fib_entry->fe_fib_index,
 974                                 fib_entry->fe_prefix.fp_proto,
 975                                 &fib_entry->fe_prefix,
 976                                 fib_entry_src_covered_inherit_walk_remove,
 977                                 esrc);
 978     }
 979 }
 980
 981 void
 982 fib_entry_src_action_activate (fib_entry_t *fib_entry,
 983                                fib_source_t source)
 984
 985 {
 986     int houston_we_are_go_for_install;
 987     const fib_entry_src_vft_t *vft;
 988     fib_entry_src_t *esrc;
 989
 990     esrc = fib_entry_src_find(fib_entry, source);
 991
 992     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
 993     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
 994
 995     esrc->fes_flags |= (FIB_ENTRY_SRC_FLAG_ACTIVE |
 996                         FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
 997     vft = fib_entry_src_get_vft(esrc);
 998
 999     if (NULL != vft->fesv_activate)
1000     {
1001         houston_we_are_go_for_install = vft->fesv_activate(esrc, fib_entry);
1002     }
1003     else
1004     {
1005         /*
1006          * the source is not providing an activate function, we'll assume
1007          * therefore it has no objection to installing the entry
1008          */
1009         houston_we_are_go_for_install = !0;
1010     }
1011
1012     /*
1013      * link to the path-list provided by the source, and go check
1014      * if that forms any loops in the graph.
1015      */
1016     fib_entry->fe_parent = esrc->fes_pl;
1017     fib_entry->fe_sibling =
1018         fib_path_list_child_add(fib_entry->fe_parent,
1019                                 FIB_NODE_TYPE_ENTRY,
1020                                 fib_entry_get_index(fib_entry));
1021
1022     fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1023
1024     FIB_ENTRY_DBG(fib_entry, "activate: %d",
1025                   fib_entry->fe_parent);
1026
1027     /*
1028      * If this source should push its state to covered prefixs, do that now.
1029      */
1030     fib_entry_src_covered_inherit_add(fib_entry, source);
1031
1032     if (0 != houston_we_are_go_for_install)
1033     {
1034         fib_entry_src_action_install(fib_entry, source);
1035     }
1036     else
1037     {
1038         fib_entry_src_action_uninstall(fib_entry);
1039     }
1040 }
1041
1042 void
1043 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
1044                                  fib_source_t source)
1045
1046 {
1047     fib_node_index_t path_list_index;
1048     fib_entry_src_t *esrc;
1049
1050     esrc = fib_entry_src_find(fib_entry, source);
1051
1052     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1053
1054     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_deactivate,
1055                              (esrc, fib_entry));
1056
1057     esrc->fes_flags &= ~(FIB_ENTRY_SRC_FLAG_ACTIVE |
1058                          FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
1059
1060     FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
1061
1062     /*
1063      * If this source should pull its state from covered prefixs, do that now.
1064      * If this source also has the INHERITED flag set then it has a cover
1065      * that wants to push down forwarding. We only want the covereds to see
1066      * one update.
1067      */
1068     fib_entry_src_covered_inherit_remove(fib_entry, esrc);
1069
1070     /*
1071      * un-link from an old path-list. Check for any loops this will clear
1072      */
1073     path_list_index = fib_entry->fe_parent;
1074     fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1075
1076     fib_entry_recursive_loop_detect_i(path_list_index);
1077
1078     /*
1079      * this will unlock the path-list, so it may be invalid thereafter.
1080      */
1081     fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
1082     fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
1083 }
1084
1085 static void
1086 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
1087                                  fib_source_t source)
1088 {
1089     fib_entry_src_t *esrc;
1090
1091     vec_foreach(esrc, fib_entry->fe_srcs)
1092     {
1093         FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_fwd_update,
1094                                  (esrc, fib_entry, source));
1095     }
1096 }
1097
1098 void
1099 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
1100                                  fib_source_t source)
1101 {
1102     fib_node_index_t path_list_index;
1103     const fib_entry_src_vft_t *vft;
1104     fib_entry_src_t *esrc;
1105     int remain_installed;
1106
1107     esrc = fib_entry_src_find(fib_entry, source);
1108
1109     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1110
1111     FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
1112                   fib_entry->fe_parent,
1113                   esrc->fes_pl);
1114
1115     /*
1116      * call the source to reactive and get the go/no-go to remain installed
1117      */
1118     vft = fib_entry_src_get_vft(esrc);
1119
1120     if (NULL != vft->fesv_reactivate)
1121     {
1122         remain_installed = vft->fesv_reactivate(esrc, fib_entry);
1123     }
1124     else
1125     {
1126         remain_installed = 1;
1127     }
1128
1129     if (fib_entry->fe_parent != esrc->fes_pl)
1130     {
1131         /*
1132          * un-link from an old path-list. Check for any loops this will clear
1133          */
1134         path_list_index = fib_entry->fe_parent;
1135         fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1136
1137         /*
1138          * temporary lock so it doesn't get deleted when this entry is no
1139          * longer a child.
1140          */
1141         fib_path_list_lock(path_list_index);
1142
1143         /*
1144          * this entry is no longer a child. after unlinking check if any loops
1145          * were broken
1146          */
1147         fib_path_list_child_remove(path_list_index,
1148                                    fib_entry->fe_sibling);
1149
1150         fib_entry_recursive_loop_detect_i(path_list_index);
1151
1152         /*
1153          * link to the path-list provided by the source, and go check
1154          * if that forms any loops in the graph.
1155          */
1156         fib_entry->fe_parent = esrc->fes_pl;
1157         fib_entry->fe_sibling =
1158             fib_path_list_child_add(fib_entry->fe_parent,
1159                                     FIB_NODE_TYPE_ENTRY,
1160                                     fib_entry_get_index(fib_entry));
1161
1162         fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1163         fib_path_list_unlock(path_list_index);
1164
1165         /*
1166          * If this source should push its state to covered prefixs, do that now.
1167          */
1168         fib_entry_src_covered_inherit_add(fib_entry, source);
1169     }
1170
1171     if (!remain_installed)
1172     {
1173         fib_entry_src_action_uninstall(fib_entry);
1174     }
1175     else
1176     {
1177         fib_entry_src_action_install(fib_entry, source);
1178     }
1179     fib_entry_src_action_fwd_update(fib_entry, source);
1180 }
1181
1182 void
1183 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
1184                                 fib_source_t source)
1185 {
1186     fib_entry_src_t *esrc;
1187
1188     esrc = fib_entry_src_find(fib_entry, source);
1189
1190     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_installed,
1191                              (esrc, fib_entry));
1192
1193     fib_entry_src_action_fwd_update(fib_entry, source);
1194 }
1195
1196 /*
1197  * fib_entry_src_action_add
1198  *
1199  * Adding a source can result in a new fib_entry being created, which
1200  * can inturn mean the pool is realloc'd and thus the entry passed as
1201  * an argument it also realloc'd
1202  * @return the original entry
1203  */
1204 fib_entry_t *
1205 fib_entry_src_action_add (fib_entry_t *fib_entry,
1206                           fib_source_t source,
1207                           fib_entry_flag_t flags,
1208                           const dpo_id_t *dpo)
1209 {
1210     fib_node_index_t fib_entry_index;
1211     fib_entry_src_t *esrc;
1212
1213     esrc = fib_entry_src_find_or_create(fib_entry, source, flags);
1214
1215     ASSERT(esrc->fes_ref_count < 255);
1216     esrc->fes_ref_count++;
1217
1218     if (flags != esrc->fes_entry_flags)
1219     {
1220         FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_flags_change,
1221                                  (esrc, fib_entry, flags));
1222     }
1223     esrc->fes_entry_flags = flags;
1224
1225     if (1 != esrc->fes_ref_count)
1226     {
1227         /*
1228          * we only want to add the source on the 0->1 transition
1229          */
1230         return (fib_entry);
1231     }
1232
1233     /*
1234      * save variable so we can recover from a fib_entry realloc.
1235      */
1236     fib_entry_index = fib_entry_get_index(fib_entry);
1237
1238     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_add,
1239                              (esrc,
1240                               fib_entry,
1241                               flags,
1242                               fib_entry_get_dpo_proto(fib_entry),
1243                               dpo));
1244
1245     fib_entry = fib_entry_get(fib_entry_index);
1246
1247     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1248
1249     fib_path_list_lock(esrc->fes_pl);
1250
1251     /*
1252      * the source owns a lock on the entry
1253      */
1254     fib_entry_lock(fib_entry_get_index(fib_entry));
1255
1256     return (fib_entry);
1257 }
1258
1259 /*
1260  * fib_entry_src_action_update
1261  *
1262  * Adding a source can result in a new fib_entry being created, which
1263  * can inturn mean the pool is realloc'd and thus the entry passed as
1264  * an argument it also realloc'd
1265  * @return the original entry
1266  */
1267 fib_entry_t *
1268 fib_entry_src_action_update (fib_entry_t *fib_entry,
1269                              fib_source_t source,
1270                              fib_entry_flag_t flags,
1271                              const dpo_id_t *dpo)
1272 {
1273     fib_node_index_t fib_entry_index, old_path_list_index;
1274     fib_entry_src_t *esrc;
1275
1276     esrc = fib_entry_src_find_or_create(fib_entry, source, flags);
1277
1278     if (NULL == esrc)
1279     {
1280         return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
1281     }
1282
1283     old_path_list_index = esrc->fes_pl;
1284     esrc->fes_entry_flags = flags;
1285
1286     /*
1287      * save variable so we can recover from a fib_entry realloc.
1288      */
1289     fib_entry_index = fib_entry_get_index(fib_entry);
1290
1291     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_add,
1292                              (esrc,
1293                               fib_entry,
1294                               flags,
1295                               fib_entry_get_dpo_proto(fib_entry),
1296                               dpo));
1297
1298     fib_entry = fib_entry_get(fib_entry_index);
1299
1300     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1301
1302     fib_path_list_lock(esrc->fes_pl);
1303     fib_path_list_unlock(old_path_list_index);
1304
1305     return (fib_entry);
1306 }
1307
1308 fib_entry_src_flag_t
1309 fib_entry_src_action_remove_or_update_inherit (fib_entry_t *fib_entry,
1310                                                fib_source_t source)
1311 {
1312     fib_entry_src_t *esrc;
1313
1314     esrc = fib_entry_src_find(fib_entry, source);
1315
1316     if (NULL == esrc)
1317         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1318
1319     if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) &&
1320         (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
1321     {
1322         fib_entry_src_t *cover_src;
1323         fib_node_index_t coveri;
1324         fib_entry_t *cover;
1325
1326         /*
1327          * this source was pushing inherited state, but so is its
1328          * cover. Now that this source is going away, we need to
1329          * pull the covers forwarding and use it to update the covereds.
1330          * Go grab the path-list from the cover, rather than start a walk from
1331          * the cover, so we don't recursively update this entry.
1332          */
1333         coveri = fib_table_get_less_specific(fib_entry->fe_fib_index,
1334                                              &fib_entry->fe_prefix);
1335
1336         /*
1337          * only the default route has itself as its own cover, but the
1338          * default route cannot have inherited from something else.
1339          */
1340         ASSERT(coveri != fib_entry_get_index(fib_entry));
1341
1342         cover = fib_entry_get(coveri);
1343         cover_src = fib_entry_src_find(cover, source);
1344
1345         ASSERT(NULL != cover_src);
1346
1347         esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
1348         esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
1349
1350         /*
1351          * Now push the new state from the cover down to the covereds
1352          */
1353         fib_entry_src_covered_inherit_add(fib_entry, source);
1354
1355         return (esrc->fes_flags);
1356     }
1357     else
1358     {
1359         return (fib_entry_src_action_remove(fib_entry, source));
1360     }
1361 }
1362
1363 fib_entry_src_flag_t
1364 fib_entry_src_action_remove (fib_entry_t *fib_entry,
1365                              fib_source_t source)
1366
1367 {
1368     fib_node_index_t old_path_list;
1369     fib_entry_src_flag_t sflags;
1370     fib_entry_src_t *esrc;
1371
1372     esrc = fib_entry_src_find(fib_entry, source);
1373
1374     if (NULL == esrc)
1375         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1376
1377     esrc->fes_ref_count--;
1378     sflags = esrc->fes_flags;
1379
1380     if (0 != esrc->fes_ref_count)
1381     {
1382         /*
1383          * only remove the source on the 1->0 transisition
1384          */
1385         return (sflags);
1386     }
1387
1388     if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
1389     {
1390         fib_entry_src_action_deactivate(fib_entry, source);
1391     }
1392     else if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING)
1393     {
1394         FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_deactivate,
1395                                  (esrc, fib_entry));
1396         esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_CONTRIBUTING;
1397     }
1398
1399     old_path_list = esrc->fes_pl;
1400
1401     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_remove, (esrc));
1402
1403     fib_path_list_unlock(old_path_list);
1404     fib_entry_unlock(fib_entry_get_index(fib_entry));
1405
1406     sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
1407     fib_entry_src_action_deinit(fib_entry, source);
1408
1409     return (sflags);
1410 }
1411
1412 /*
1413  * fib_route_attached_cross_table
1414  *
1415  * Return true the the route is attached via an interface that
1416  * is not in the same table as the route
1417  */
1418 static inline int
1419 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
1420                                 const fib_route_path_t *rpath)
1421 {
1422     /*
1423      * - All zeros next-hop
1424      * - a valid interface
1425      * - entry's fib index not equeal to interface's index
1426      */
1427     if (ip46_address_is_zero(&rpath->frp_addr) &&
1428         (~0 != rpath->frp_sw_if_index) &&
1429         !(rpath->frp_flags & FIB_ROUTE_PATH_DVR) &&
1430         (fib_entry->fe_fib_index !=
1431          fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
1432                                              rpath->frp_sw_if_index)))
1433     {
1434         return (!0);
1435     }
1436     return (0);
1437 }
1438
1439 /*
1440  * Return true if the path is attached
1441  */
1442 static inline int
1443 fib_path_is_attached (const fib_route_path_t *rpath)
1444 {
1445     /*
1446      * DVR paths are not attached, since we are not playing the
1447      * L3 game with these
1448      */
1449     if (rpath->frp_flags & FIB_ROUTE_PATH_DVR)
1450     {
1451         return (0);
1452     }
1453
1454     /*
1455      * - All zeros next-hop
1456      * - a valid interface
1457      */
1458     if (ip46_address_is_zero(&rpath->frp_addr) &&
1459         (~0 != rpath->frp_sw_if_index))
1460     {
1461         return (!0);
1462     }
1463     else if (rpath->frp_flags & FIB_ROUTE_PATH_ATTACHED)
1464     {
1465         return (!0);
1466     }
1467     return (0);
1468 }
1469
1470 fib_path_list_flags_t
1471 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
1472 {
1473     fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
1474
1475     if (eflags & FIB_ENTRY_FLAG_DROP)
1476     {
1477         plf |= FIB_PATH_LIST_FLAG_DROP;
1478     }
1479     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
1480     {
1481         plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
1482     }
1483     if (eflags & FIB_ENTRY_FLAG_LOCAL)
1484     {
1485         plf |= FIB_PATH_LIST_FLAG_LOCAL;
1486     }
1487
1488     return (plf);
1489 }
1490
1491 static void
1492 fib_entry_flags_update (const fib_entry_t *fib_entry,
1493                         const fib_route_path_t *rpath,
1494                         fib_path_list_flags_t *pl_flags,
1495                         fib_entry_src_t *esrc)
1496 {
1497     if ((esrc->fes_src == FIB_SOURCE_API) ||
1498         (esrc->fes_src == FIB_SOURCE_CLI))
1499     {
1500         if (fib_path_is_attached(rpath))
1501         {
1502             esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
1503         }
1504         else
1505         {
1506             esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
1507         }
1508         if (rpath->frp_flags & FIB_ROUTE_PATH_DEAG)
1509         {
1510             esrc->fes_entry_flags |= FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT;
1511         }
1512     }
1513     if (fib_route_attached_cross_table(fib_entry, rpath) &&
1514         !(esrc->fes_entry_flags & FIB_ENTRY_FLAG_NO_ATTACHED_EXPORT))
1515     {
1516         esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
1517     }
1518     else
1519     {
1520         esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
1521     }
1522 }
1523
1524 /*
1525  * fib_entry_src_action_add
1526  *
1527  * Adding a source can result in a new fib_entry being created, which
1528  * can inturn mean the pool is realloc'd and thus the entry passed as
1529  * an argument it also realloc'd
1530  * @return the entry
1531  */
1532 fib_entry_t*
1533 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
1534                                fib_source_t source,
1535                                fib_entry_flag_t flags,
1536                                const fib_route_path_t *rpath)
1537 {
1538     fib_node_index_t old_path_list, fib_entry_index;
1539     fib_path_list_flags_t pl_flags;
1540     fib_entry_src_t *esrc;
1541
1542     /*
1543      * save variable so we can recover from a fib_entry realloc.
1544      */
1545     fib_entry_index = fib_entry_get_index(fib_entry);
1546
1547     esrc = fib_entry_src_find(fib_entry, source);
1548     if (NULL == esrc)
1549     {
1550         const dpo_id_t *dpo;
1551
1552         if (flags == FIB_ENTRY_FLAG_EXCLUSIVE) {
1553             dpo = &rpath->dpo;
1554         } else {
1555             dpo = drop_dpo_get(fib_entry_get_dpo_proto(fib_entry));
1556         }
1557
1558         fib_entry =
1559             fib_entry_src_action_add(fib_entry,
1560                                      source,
1561                                      flags,
1562                                      dpo);
1563         esrc = fib_entry_src_find(fib_entry, source);
1564     }
1565
1566     /*
1567      * we are no doubt modifying a path-list. If the path-list
1568      * is shared, and hence not modifiable, then the index returned
1569      * will be for a different path-list. This FIB entry to needs
1570      * to maintain its lock appropriately.
1571      */
1572     old_path_list = esrc->fes_pl;
1573
1574     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_add));
1575
1576     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1577     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1578
1579     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_path_add,
1580                              (esrc, fib_entry, pl_flags, rpath));
1581     fib_entry = fib_entry_get(fib_entry_index);
1582
1583     fib_path_list_lock(esrc->fes_pl);
1584     fib_path_list_unlock(old_path_list);
1585
1586     return (fib_entry);
1587 }
1588
1589 /*
1590  * fib_entry_src_action_swap
1591  *
1592  * The source is providing new paths to replace the old ones.
1593  * Adding a source can result in a new fib_entry being created, which
1594  * can inturn mean the pool is realloc'd and thus the entry passed as
1595  * an argument it also realloc'd
1596  * @return the entry
1597  */
1598 fib_entry_t*
1599 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1600                                 fib_source_t source,
1601                                 fib_entry_flag_t flags,
1602                                 const fib_route_path_t *rpaths)
1603 {
1604     fib_node_index_t old_path_list, fib_entry_index;
1605     fib_path_list_flags_t pl_flags;
1606     const fib_route_path_t *rpath;
1607     fib_entry_src_t *esrc;
1608
1609     esrc = fib_entry_src_find(fib_entry, source);
1610
1611     /*
1612      * save variable so we can recover from a fib_entry realloc.
1613      */
1614     fib_entry_index = fib_entry_get_index(fib_entry);
1615
1616     if (NULL == esrc)
1617     {
1618         const dpo_id_t *dpo;
1619
1620         if (flags == FIB_ENTRY_FLAG_EXCLUSIVE) {
1621             dpo = &rpaths->dpo;
1622         } else {
1623             dpo = drop_dpo_get(fib_entry_get_dpo_proto(fib_entry));
1624         }
1625
1626         fib_entry = fib_entry_src_action_add(fib_entry,
1627                                              source,
1628                                              flags,
1629                                              dpo);
1630         esrc = fib_entry_src_find(fib_entry, source);
1631     }
1632     else
1633     {
1634         if (flags != esrc->fes_entry_flags)
1635         {
1636             FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_flags_change,
1637                                      (esrc, fib_entry, flags));
1638         }
1639         esrc->fes_entry_flags = flags;
1640     }
1641
1642     /*
1643      * swapping paths may create a new path-list (or may use an existing shared)
1644      * but we are certainly getting a different one. This FIB entry to needs
1645      * to maintain its lock appropriately.
1646      */
1647     old_path_list = esrc->fes_pl;
1648
1649     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_swap));
1650
1651     pl_flags = fib_entry_src_flags_2_path_list_flags(flags);
1652
1653     vec_foreach(rpath, rpaths)
1654     {
1655         fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1656     }
1657
1658     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_path_swap,
1659                              (esrc, fib_entry,
1660                               pl_flags, rpaths));
1661
1662     fib_entry = fib_entry_get(fib_entry_index);
1663
1664     fib_path_list_lock(esrc->fes_pl);
1665     fib_path_list_unlock(old_path_list);
1666
1667     return (fib_entry);
1668 }
1669
1670 fib_entry_src_flag_t
1671 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1672                                   fib_source_t source,
1673                                   const fib_route_path_t *rpath)
1674 {
1675     fib_path_list_flags_t pl_flags;
1676     fib_node_index_t old_path_list;
1677     fib_entry_src_t *esrc;
1678
1679     esrc = fib_entry_src_find(fib_entry, source);
1680
1681     ASSERT(NULL != esrc);
1682     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1683
1684     /*
1685      * we no doubt modifying a path-list. If the path-list
1686      * is shared, and hence not modifiable, then the index returned
1687      * will be for a different path-list. This FIB entry to needs
1688      * to maintain its lock appropriately.
1689      */
1690     old_path_list = esrc->fes_pl;
1691
1692     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_remove));
1693
1694     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1695     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1696
1697     FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_path_remove,
1698                              (esrc, pl_flags, rpath));
1699
1700     /*
1701      * lock the new path-list, unlock the old if it had one
1702      */
1703     fib_path_list_unlock(old_path_list);
1704
1705     if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1706         fib_path_list_lock(esrc->fes_pl);
1707         return (FIB_ENTRY_SRC_FLAG_ADDED);
1708     }
1709     else
1710     {
1711         /*
1712          * no more paths left from this source
1713          */
1714         fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1715         return (FIB_ENTRY_SRC_FLAG_NONE);
1716     }
1717 }
1718
1719 u8*
1720 fib_entry_src_format (fib_entry_t *fib_entry,
1721                       fib_source_t source,
1722                       u8* s)
1723 {
1724     fib_entry_src_t *esrc;
1725
1726     esrc = fib_entry_src_find(fib_entry, source);
1727
1728     FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_format, (esrc, s));
1729
1730     return (s);
1731 }
1732
1733 adj_index_t
1734 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1735                               fib_source_t source)
1736 {
1737     fib_entry_t *fib_entry;
1738     fib_entry_src_t *esrc;
1739
1740     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1741         return (ADJ_INDEX_INVALID);
1742
1743     fib_entry = fib_entry_get(fib_entry_index);
1744     esrc = fib_entry_src_find(fib_entry, source);
1745
1746     if (NULL != esrc)
1747     {
1748         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1749         {
1750             return (fib_path_list_get_adj(
1751                         esrc->fes_pl,
1752                         fib_entry_get_default_chain_type(fib_entry)));
1753         }
1754     }
1755     return (ADJ_INDEX_INVALID);
1756 }
1757
1758 const int
1759 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1760                               fib_source_t source,
1761                               dpo_id_t *dpo)
1762 {
1763     fib_entry_t *fib_entry;
1764     fib_entry_src_t *esrc;
1765
1766     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1767         return (0);
1768
1769     fib_entry = fib_entry_get(fib_entry_index);
1770     esrc = fib_entry_src_find(fib_entry, source);
1771
1772     if (NULL != esrc)
1773     {
1774         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1775         {
1776             fib_path_list_contribute_forwarding(
1777                 esrc->fes_pl,
1778                 fib_entry_get_default_chain_type(fib_entry),
1779                 FIB_PATH_LIST_FWD_FLAG_NONE,
1780                 dpo);
1781
1782             return (dpo_id_is_valid(dpo));
1783         }
1784     }
1785     return (0);
1786 }
1787
1788 u32
1789 fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index,
1790                                               fib_source_t source)
1791 {
1792     fib_entry_t *fib_entry;
1793     fib_entry_src_t *esrc;
1794
1795     fib_entry = fib_entry_get(entry_index);
1796
1797     esrc = fib_entry_src_find(fib_entry, source);
1798
1799     if (NULL != esrc)
1800     {
1801         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1802         {
1803             return (fib_path_list_get_resolving_interface(esrc->fes_pl));
1804         }
1805     }
1806     return (~0);
1807 }
1808
1809 fib_entry_flag_t
1810 fib_entry_get_flags_for_source (fib_node_index_t entry_index,
1811                                 fib_source_t source)
1812 {
1813     fib_entry_t *fib_entry;
1814     fib_entry_src_t *esrc;
1815
1816     fib_entry = fib_entry_get(entry_index);
1817
1818     esrc = fib_entry_src_find(fib_entry, source);
1819
1820     if (NULL != esrc)
1821     {
1822         return (esrc->fes_entry_flags);
1823     }
1824
1825     return (FIB_ENTRY_FLAG_NONE);
1826 }
1827
1828 fib_entry_flag_t
1829 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1830 {
1831     fib_entry_flag_t flags;
1832
1833     /*
1834      * the vector of sources is deliberately arranged in priority order
1835      */
1836     if (0 == vec_len(fib_entry->fe_srcs))
1837     {
1838         flags = FIB_ENTRY_FLAG_NONE;
1839     }
1840     else
1841     {
1842         fib_entry_src_t *esrc;
1843
1844         esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
1845         flags = esrc->fes_entry_flags;
1846     }
1847
1848     return (flags);
1849 }
1850
1851 void
1852 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1853                            fib_source_t source,
1854                            const void *data)
1855 {
1856     fib_entry_t *fib_entry;
1857     fib_entry_src_t *esrc;
1858
1859     fib_entry = fib_entry_get(fib_entry_index);
1860     esrc = fib_entry_src_find(fib_entry, source);
1861
1862     if (NULL != esrc)
1863     {
1864         FIB_ENTRY_SRC_VFT_INVOKE(esrc, fesv_set_data,
1865                                  (esrc, fib_entry, data));
1866     }
1867 }
1868
1869 const void*
1870 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1871                            fib_source_t source)
1872 {
1873     fib_entry_t *fib_entry;
1874     fib_entry_src_t *esrc;
1875
1876     fib_entry = fib_entry_get(fib_entry_index);
1877     esrc = fib_entry_src_find(fib_entry, source);
1878
1879     if (NULL != esrc)
1880     {
1881         FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_get_data,
1882                                             (esrc, fib_entry));
1883     }
1884     return (NULL);
1885 }
1886
1887 void
1888 fib_entry_src_module_init (void)
1889 {
1890     fib_entry_src_rr_register();
1891     fib_entry_src_interface_register();
1892     fib_entry_src_interpose_register();
1893     fib_entry_src_default_route_register();
1894     fib_entry_src_special_register();
1895     fib_entry_src_api_register();
1896     fib_entry_src_adj_register();
1897     fib_entry_src_mpls_register();
1898     fib_entry_src_lisp_register();
1899 }