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