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