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