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         dpo_reset(&fib_entry->fe_lb);
 761     }
 762 }
 763
 764 static void
 765 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
 766 {
 767     fib_node_index_t *entries = NULL;
 768
 769     fib_path_list_recursive_loop_detect(path_list_index, &entries);
 770
 771     vec_free(entries);
 772 }
 773
 774 /*
 775  * fib_entry_src_action_copy
 776  *
 777  * copy a source data from another entry to this one
 778  */
 779 static fib_entry_t *
 780 fib_entry_src_action_copy (fib_entry_t *fib_entry,
 781                            const fib_entry_src_t *orig_src)
 782 {
 783     fib_entry_src_t *esrc;
 784
 785     esrc = fib_entry_src_find_or_create(fib_entry,
 786                                         orig_src->fes_src,
 787                                         orig_src->fes_entry_flags);
 788
 789     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_copy,
 790                              (orig_src, fib_entry, esrc));
 791
 792     fib_path_list_unlock(esrc->fes_pl);
 793
 794     /*
 795      * copy over all the data ...
 796      */
 797     esrc->fes_flags = orig_src->fes_flags;
 798     esrc->fes_pl = orig_src->fes_pl;
 799
 800     /*
 801      *  ... then update
 802      */
 803     esrc->fes_ref_count = 1;
 804     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_INHERITED;
 805     esrc->fes_flags &= ~(FIB_ENTRY_SRC_FLAG_ACTIVE |
 806                          FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
 807     esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
 808
 809     /*
 810      * the source owns a lock on the entry
 811      */
 812     fib_path_list_lock(esrc->fes_pl);
 813     fib_entry_lock(fib_entry_get_index(fib_entry));
 814
 815     return (fib_entry);
 816 }
 817
 818 /*
 819  * fib_entry_src_action_update
 820  *
 821  * copy a source data from another entry to this one
 822  */
 823 static fib_entry_src_t *
 824 fib_entry_src_action_update_from_cover (fib_entry_t *fib_entry,
 825                                         const fib_entry_src_t *orig_src)
 826 {
 827     fib_entry_src_t *esrc;
 828
 829     esrc = fib_entry_src_find_or_create(fib_entry,
 830                                         orig_src->fes_src,
 831                                         orig_src->fes_entry_flags);
 832
 833     /*
 834      * the source owns a lock on the entry
 835      */
 836     fib_path_list_unlock(esrc->fes_pl);
 837     esrc->fes_pl = orig_src->fes_pl;
 838     fib_path_list_lock(esrc->fes_pl);
 839
 840     return (esrc);
 841 }
 842
 843 static fib_table_walk_rc_t
 844 fib_entry_src_covered_inherit_add_i (fib_entry_t *fib_entry,
 845                                      const fib_entry_src_t *cover_src)
 846 {
 847     fib_entry_src_t *esrc;
 848
 849     esrc = fib_entry_src_find(fib_entry, cover_src->fes_src);
 850
 851     if (cover_src == esrc)
 852     {
 853         return (FIB_TABLE_WALK_CONTINUE);
 854     }
 855
 856     if (NULL != esrc)
 857     {
 858         /*
 859          * the covered entry already has this source.
 860          */
 861         if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
 862         {
 863             /*
 864              * the covered source is itself a COVERED_INHERIT, i.e.
 865              * it also pushes this source down the sub-tree.
 866              * We consider this more specific covered to be the owner
 867              * of the sub-tree from this point down.
 868              */
 869             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 870         }
 871         if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
 872         {
 873             /*
 874              * The covered's source data has been inherited, presumably
 875              * from this cover, i.e. this is a modify.
 876              */
 877             esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
 878             fib_entry_source_change(fib_entry, esrc->fes_src, esrc->fes_src);
 879         }
 880         else
 881         {
 882             /*
 883              * The covered's source was not inherited and it is also
 884              * not inheriting. Nevertheless, it still owns the sub-tree from
 885              * this point down.
 886              */
 887             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 888         }
 889     }
 890     else
 891     {
 892         /*
 893          * The covered does not have this source - add it.
 894          */
 895         fib_source_t best_source;
 896
 897         best_source = fib_entry_get_best_source(
 898             fib_entry_get_index(fib_entry));
 899
 900         fib_entry_src_action_copy(fib_entry, cover_src);
 901         fib_entry_source_change(fib_entry, best_source, cover_src->fes_src);
 902
 903     }
 904     return (FIB_TABLE_WALK_CONTINUE);
 905 }
 906
 907 static fib_table_walk_rc_t
 908 fib_entry_src_covered_inherit_walk_add (fib_node_index_t fei,
 909                                         void *ctx)
 910 {
 911     return (fib_entry_src_covered_inherit_add_i(fib_entry_get(fei), ctx));
 912 }
 913
 914 static fib_table_walk_rc_t
 915 fib_entry_src_covered_inherit_walk_remove (fib_node_index_t fei,
 916                                            void *ctx)
 917 {
 918     fib_entry_src_t *cover_src, *esrc;
 919     fib_entry_t *fib_entry;
 920
 921     fib_entry = fib_entry_get(fei);
 922
 923     cover_src = ctx;
 924     esrc = fib_entry_src_find(fib_entry, cover_src->fes_src);
 925
 926     if (cover_src == esrc)
 927     {
 928         return (FIB_TABLE_WALK_CONTINUE);
 929     }
 930
 931     if (NULL != esrc)
 932     {
 933         /*
 934          * the covered entry already has this source.
 935          */
 936         if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
 937         {
 938             /*
 939              * the covered source is itself a COVERED_INHERIT, i.e.
 940              * it also pushes this source down the sub-tree.
 941              * We consider this more specific covered to be the owner
 942              * of the sub-tree from this point down.
 943              */
 944             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 945         }
 946         if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED)
 947         {
 948             /*
 949              * The covered's source data has been inherited, presumably
 950              * from this cover
 951              */
 952             fib_entry_src_flag_t remaining;
 953
 954             remaining = fib_entry_special_remove(fei, cover_src->fes_src);
 955
 956             ASSERT(FIB_ENTRY_SRC_FLAG_ADDED == remaining);
 957         }
 958         else
 959         {
 960             /*
 961              * The covered's source was not inherited and it is also
 962              * not inheriting. Nevertheless, it still owns the sub-tree from
 963              * this point down.
 964              */
 965             return (FIB_TABLE_WALK_SUB_TREE_STOP);
 966         }
 967     }
 968     else
 969     {
 970         /*
 971          * The covered does not have this source - that's an error,
 972          * since it should have inherited, but there is nothing we can do
 973          * about it now.
 974          */
 975     }
 976     return (FIB_TABLE_WALK_CONTINUE);
 977 }
 978
 979 void
 980 fib_entry_src_inherit (const fib_entry_t *cover,
 981                        fib_entry_t *covered)
 982 {
 983     CLIB_UNUSED(fib_source_t source);
 984     const fib_entry_src_t *src;
 985
 986     FOR_EACH_SRC_ADDED(cover, src, source,
 987     ({
 988         if ((src->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
 989             (src->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
 990         {
 991             fib_entry_src_covered_inherit_add_i(covered, src);
 992         }
 993     }))
 994 }
 995
 996 static void
 997 fib_entry_src_covered_inherit_add (fib_entry_t *fib_entry,
 998                                    fib_source_t source)
 999
1000 {
1001     fib_entry_src_t *esrc;
1002
1003     esrc = fib_entry_src_find(fib_entry, source);
1004
1005     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1006
1007     if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) ||
1008         (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
1009     {
1010         fib_table_sub_tree_walk(fib_entry->fe_fib_index,
1011                                 fib_entry->fe_prefix.fp_proto,
1012                                 &fib_entry->fe_prefix,
1013                                 fib_entry_src_covered_inherit_walk_add,
1014                                 esrc);
1015     }
1016 }
1017
1018 static void
1019 fib_entry_src_covered_inherit_remove (fib_entry_t *fib_entry,
1020                                       fib_entry_src_t *esrc)
1021
1022 {
1023     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
1024
1025     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT)
1026     {
1027         fib_table_sub_tree_walk(fib_entry->fe_fib_index,
1028                                 fib_entry->fe_prefix.fp_proto,
1029                                 &fib_entry->fe_prefix,
1030                                 fib_entry_src_covered_inherit_walk_remove,
1031                                 esrc);
1032     }
1033 }
1034
1035 void
1036 fib_entry_src_action_activate (fib_entry_t *fib_entry,
1037                                fib_source_t source)
1038
1039 {
1040     int houston_we_are_go_for_install;
1041     const fib_entry_src_vft_t *vft;
1042     fib_entry_src_t *esrc;
1043
1044     esrc = fib_entry_src_find(fib_entry, source);
1045
1046     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
1047     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1048
1049     esrc->fes_flags |= (FIB_ENTRY_SRC_FLAG_ACTIVE |
1050                         FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
1051     vft = fib_entry_src_get_vft(esrc);
1052
1053     if (NULL != vft->fesv_activate)
1054     {
1055         houston_we_are_go_for_install = vft->fesv_activate(esrc, fib_entry);
1056     }
1057     else
1058     {
1059         /*
1060          * the source is not providing an activate function, we'll assume
1061          * therefore it has no objection to installing the entry
1062          */
1063         houston_we_are_go_for_install = !0;
1064     }
1065
1066     /*
1067      * link to the path-list provided by the source, and go check
1068      * if that forms any loops in the graph.
1069      */
1070     fib_entry->fe_parent = esrc->fes_pl;
1071     fib_entry->fe_sibling =
1072         fib_path_list_child_add(fib_entry->fe_parent,
1073                                 FIB_NODE_TYPE_ENTRY,
1074                                 fib_entry_get_index(fib_entry));
1075
1076     fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1077
1078     FIB_ENTRY_DBG(fib_entry, "activate: %d",
1079                   fib_entry->fe_parent);
1080
1081     /*
1082      * If this source should push its state to covered prefixs, do that now.
1083      */
1084     fib_entry_src_covered_inherit_add(fib_entry, source);
1085
1086     if (0 != houston_we_are_go_for_install)
1087     {
1088         fib_entry_src_action_install(fib_entry, source);
1089     }
1090     else
1091     {
1092         fib_entry_src_action_uninstall(fib_entry);
1093     }
1094 }
1095
1096 void
1097 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
1098                                  fib_source_t source)
1099
1100 {
1101     fib_node_index_t path_list_index;
1102     fib_entry_src_t *esrc;
1103
1104     esrc = fib_entry_src_find(fib_entry, source);
1105
1106     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1107
1108     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_deactivate,
1109                              (esrc, fib_entry));
1110
1111     esrc->fes_flags &= ~(FIB_ENTRY_SRC_FLAG_ACTIVE |
1112                          FIB_ENTRY_SRC_FLAG_CONTRIBUTING);
1113
1114     FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
1115
1116     /*
1117      * If this source should pull its state from covered prefixs, do that now.
1118      * If this source also has the INHERITED flag set then it has a cover
1119      * that wants to push down forwarding. We only want the covereds to see
1120      * one update.
1121      */
1122     fib_entry_src_covered_inherit_remove(fib_entry, esrc);
1123
1124     /*
1125      * un-link from an old path-list. Check for any loops this will clear
1126      */
1127     path_list_index = fib_entry->fe_parent;
1128     fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1129
1130     fib_entry_recursive_loop_detect_i(path_list_index);
1131
1132     /*
1133      * this will unlock the path-list, so it may be invalid thereafter.
1134      */
1135     fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
1136     fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
1137 }
1138
1139 static void
1140 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
1141                                  fib_source_t source)
1142 {
1143     fib_entry_src_t *esrc;
1144
1145     vec_foreach(esrc, fib_entry->fe_srcs)
1146     {
1147         FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_fwd_update,
1148                                  (esrc, fib_entry, source));
1149     }
1150 }
1151
1152 void
1153 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
1154                                  fib_source_t source)
1155 {
1156     fib_node_index_t path_list_index;
1157     const fib_entry_src_vft_t *vft;
1158     fib_entry_src_t *esrc;
1159     int remain_installed;
1160
1161     esrc = fib_entry_src_find(fib_entry, source);
1162
1163     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
1164
1165     FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
1166                   fib_entry->fe_parent,
1167                   esrc->fes_pl);
1168
1169     /*
1170      * call the source to reactive and get the go/no-go to remain installed
1171      */
1172     vft = fib_entry_src_get_vft(esrc);
1173
1174     if (NULL != vft->fesv_reactivate)
1175     {
1176         remain_installed = vft->fesv_reactivate(esrc, fib_entry);
1177     }
1178     else
1179     {
1180         remain_installed = 1;
1181     }
1182
1183     if (fib_entry->fe_parent != esrc->fes_pl)
1184     {
1185         /*
1186          * un-link from an old path-list. Check for any loops this will clear
1187          */
1188         path_list_index = fib_entry->fe_parent;
1189         fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
1190
1191         /*
1192          * temporary lock so it doesn't get deleted when this entry is no
1193          * longer a child.
1194          */
1195         fib_path_list_lock(path_list_index);
1196
1197         /*
1198          * this entry is no longer a child. after unlinking check if any loops
1199          * were broken
1200          */
1201         fib_path_list_child_remove(path_list_index,
1202                                    fib_entry->fe_sibling);
1203
1204         fib_entry_recursive_loop_detect_i(path_list_index);
1205
1206         /*
1207          * link to the path-list provided by the source, and go check
1208          * if that forms any loops in the graph.
1209          */
1210         fib_entry->fe_parent = esrc->fes_pl;
1211         fib_entry->fe_sibling =
1212             fib_path_list_child_add(fib_entry->fe_parent,
1213                                     FIB_NODE_TYPE_ENTRY,
1214                                     fib_entry_get_index(fib_entry));
1215
1216         fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
1217         fib_path_list_unlock(path_list_index);
1218
1219         /*
1220          * If this source should push its state to covered prefixs, do that now.
1221          */
1222         fib_entry_src_covered_inherit_add(fib_entry, source);
1223     }
1224
1225     if (!remain_installed)
1226     {
1227         fib_entry_src_action_uninstall(fib_entry);
1228     }
1229     else
1230     {
1231         fib_entry_src_action_install(fib_entry, source);
1232     }
1233     fib_entry_src_action_fwd_update(fib_entry, source);
1234 }
1235
1236 fib_entry_t *
1237 fib_entry_src_action_installed (fib_entry_t *fib_entry,
1238                                 fib_source_t source)
1239 {
1240     fib_entry_src_t *esrc;
1241
1242     esrc = fib_entry_src_find(fib_entry, source);
1243
1244     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_installed,
1245                              (esrc, fib_entry));
1246
1247     fib_entry_src_action_fwd_update(fib_entry, source);
1248
1249     return (fib_entry);
1250 }
1251
1252 /*
1253  * fib_entry_src_action_add
1254  *
1255  * Adding a source can result in a new fib_entry being created, which
1256  * can inturn mean the pool is realloc'd and thus the entry passed as
1257  * an argument it also realloc'd
1258  * @return the original entry
1259  */
1260 fib_entry_t *
1261 fib_entry_src_action_add (fib_entry_t *fib_entry,
1262                           fib_source_t source,
1263                           fib_entry_flag_t flags,
1264                           const dpo_id_t *dpo)
1265 {
1266     fib_entry_src_t *esrc;
1267
1268     esrc = fib_entry_src_find_or_create(fib_entry, source, flags);
1269
1270     ASSERT(esrc->fes_ref_count < 255);
1271     esrc->fes_ref_count++;
1272
1273     if (flags != esrc->fes_entry_flags)
1274     {
1275         FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_flags_change,
1276                                  (esrc, fib_entry, flags));
1277     }
1278     esrc->fes_entry_flags = flags;
1279
1280     if (1 != esrc->fes_ref_count)
1281     {
1282         /*
1283          * we only want to add the source on the 0->1 transition
1284          */
1285         return (fib_entry);
1286     }
1287
1288     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_add,
1289                              (esrc,
1290                               fib_entry,
1291                               flags,
1292                               fib_entry_get_dpo_proto(fib_entry),
1293                               dpo));
1294
1295     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1296
1297     fib_path_list_lock(esrc->fes_pl);
1298
1299     /*
1300      * the source owns a lock on the entry
1301      */
1302     fib_entry_lock(fib_entry_get_index(fib_entry));
1303
1304     return (fib_entry);
1305 }
1306
1307 /*
1308  * fib_entry_src_action_update
1309  *
1310  * Adding a source can result in a new fib_entry being created, which
1311  * can inturn mean the pool is realloc'd and thus the entry passed as
1312  * an argument it also realloc'd
1313  * @return the original entry
1314  */
1315 fib_entry_t *
1316 fib_entry_src_action_update (fib_entry_t *fib_entry,
1317                              fib_source_t source,
1318                              fib_entry_flag_t flags,
1319                              const dpo_id_t *dpo)
1320 {
1321     fib_node_index_t old_path_list_index;
1322     fib_entry_src_t *esrc;
1323
1324     esrc = fib_entry_src_find_or_create(fib_entry, source, flags);
1325
1326     if (NULL == esrc)
1327     {
1328         return (fib_entry_src_action_add(fib_entry, source, flags, dpo));
1329     }
1330
1331     old_path_list_index = esrc->fes_pl;
1332     esrc->fes_entry_flags = flags;
1333
1334     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_add,
1335                              (esrc,
1336                               fib_entry,
1337                               flags,
1338                               fib_entry_get_dpo_proto(fib_entry),
1339                               dpo));
1340
1341     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
1342
1343     fib_path_list_lock(esrc->fes_pl);
1344     fib_path_list_unlock(old_path_list_index);
1345
1346     return (fib_entry);
1347 }
1348
1349 fib_entry_src_flag_t
1350 fib_entry_src_action_remove_or_update_inherit (fib_entry_t *fib_entry,
1351                                                fib_source_t source)
1352 {
1353     fib_entry_src_t *esrc;
1354
1355     esrc = fib_entry_src_find(fib_entry, source);
1356
1357     if (NULL == esrc)
1358         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1359
1360     if ((esrc->fes_entry_flags & FIB_ENTRY_FLAG_COVERED_INHERIT) &&
1361         (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_INHERITED))
1362     {
1363         fib_entry_src_t *cover_src;
1364         fib_node_index_t coveri;
1365         fib_entry_t *cover;
1366
1367         /*
1368          * this source was pushing inherited state, but so is its
1369          * cover. Now that this source is going away, we need to
1370          * pull the covers forwarding and use it to update the covereds.
1371          * Go grab the path-list from the cover, rather than start a walk from
1372          * the cover, so we don't recursively update this entry.
1373          */
1374         coveri = fib_table_get_less_specific(fib_entry->fe_fib_index,
1375                                              &fib_entry->fe_prefix);
1376
1377         /*
1378          * only the default route has itself as its own cover, but the
1379          * default route cannot have inherited from something else.
1380          */
1381         ASSERT(coveri != fib_entry_get_index(fib_entry));
1382
1383         cover = fib_entry_get(coveri);
1384         cover_src = fib_entry_src_find(cover, source);
1385
1386         ASSERT(NULL != cover_src);
1387
1388         esrc = fib_entry_src_action_update_from_cover(fib_entry, cover_src);
1389         esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_COVERED_INHERIT;
1390
1391         /*
1392          * Now push the new state from the cover down to the covereds
1393          */
1394         fib_entry_src_covered_inherit_add(fib_entry, source);
1395
1396         return (esrc->fes_flags);
1397     }
1398     else
1399     {
1400         return (fib_entry_src_action_remove(fib_entry, source));
1401     }
1402 }
1403
1404 fib_entry_src_flag_t
1405 fib_entry_src_action_remove (fib_entry_t *fib_entry,
1406                              fib_source_t source)
1407
1408 {
1409     fib_node_index_t old_path_list;
1410     fib_entry_src_flag_t sflags;
1411     fib_entry_src_t *esrc;
1412
1413     esrc = fib_entry_src_find(fib_entry, source);
1414
1415     if (NULL == esrc)
1416         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
1417
1418     esrc->fes_ref_count--;
1419     sflags = esrc->fes_flags;
1420
1421     if (0 != esrc->fes_ref_count)
1422     {
1423         /*
1424          * only remove the source on the 1->0 transisition
1425          */
1426         return (sflags);
1427     }
1428
1429     if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
1430     {
1431         fib_entry_src_action_deactivate(fib_entry, source);
1432     }
1433     else if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING)
1434     {
1435         FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_deactivate,
1436                                  (esrc, fib_entry));
1437         esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_CONTRIBUTING;
1438     }
1439
1440     old_path_list = esrc->fes_pl;
1441
1442     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_remove, (esrc));
1443
1444     fib_path_list_unlock(old_path_list);
1445     fib_entry_unlock(fib_entry_get_index(fib_entry));
1446
1447     sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
1448     fib_entry_src_action_deinit(fib_entry, source);
1449
1450     return (sflags);
1451 }
1452
1453 /*
1454  * fib_route_attached_cross_table
1455  *
1456  * Return true the the route is attached via an interface that
1457  * is not in the same table as the route
1458  */
1459 static int
1460 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
1461                                 const fib_route_path_t *rpath)
1462 {
1463     const fib_prefix_t *pfx = &fib_entry->fe_prefix;
1464
1465     switch (pfx->fp_proto)
1466     {
1467     case FIB_PROTOCOL_MPLS:
1468         /* MPLS routes are never imported/exported */
1469         return (0);
1470     case FIB_PROTOCOL_IP6:
1471         /* Ignore link local addresses these also can't be imported/exported */
1472         if (ip6_address_is_link_local_unicast (&pfx->fp_addr.ip6))
1473         {
1474             return (0);
1475         }
1476         break;
1477     case FIB_PROTOCOL_IP4:
1478         break;
1479     }
1480
1481     /*
1482      * an attached path and entry's fib index not equal to interface's index
1483      */
1484     if (fib_route_path_is_attached(rpath) &&
1485         fib_entry->fe_fib_index !=
1486         fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
1487                                             rpath->frp_sw_if_index))
1488     {
1489         return (!0);
1490     }
1491     return (0);
1492 }
1493
1494 fib_path_list_flags_t
1495 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
1496 {
1497     fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
1498
1499     if (eflags & FIB_ENTRY_FLAG_DROP)
1500     {
1501         plf |= FIB_PATH_LIST_FLAG_DROP;
1502     }
1503     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
1504     {
1505         plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
1506     }
1507     if (eflags & FIB_ENTRY_FLAG_LOCAL)
1508     {
1509         plf |= FIB_PATH_LIST_FLAG_LOCAL;
1510     }
1511
1512     return (plf);
1513 }
1514
1515 static void
1516 fib_entry_flags_update (const fib_entry_t *fib_entry,
1517                         const fib_route_path_t *rpaths,
1518                         fib_path_list_flags_t *pl_flags,
1519                         fib_entry_src_t *esrc)
1520 {
1521     const fib_route_path_t *rpath;
1522
1523     vec_foreach(rpath, rpaths)
1524     {
1525         if ((esrc->fes_src == FIB_SOURCE_API) ||
1526             (esrc->fes_src == FIB_SOURCE_CLI))
1527         {
1528             if (fib_route_path_is_attached(rpath))
1529             {
1530                 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
1531             }
1532             else
1533             {
1534                 esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
1535             }
1536             if (rpath->frp_flags & FIB_ROUTE_PATH_DEAG)
1537             {
1538                 esrc->fes_entry_flags |= FIB_ENTRY_FLAG_LOOSE_URPF_EXEMPT;
1539             }
1540         }
1541         if (fib_route_attached_cross_table(fib_entry, rpath) &&
1542             !(esrc->fes_entry_flags & FIB_ENTRY_FLAG_NO_ATTACHED_EXPORT))
1543         {
1544             esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
1545         }
1546         else
1547         {
1548             esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
1549         }
1550     }
1551 }
1552
1553 /*
1554  * fib_entry_src_action_add
1555  *
1556  * Adding a source can result in a new fib_entry being created, which
1557  * can inturn mean the pool is realloc'd and thus the entry passed as
1558  * an argument it also realloc'd
1559  * @return the entry
1560  */
1561 fib_entry_t*
1562 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
1563                                fib_source_t source,
1564                                fib_entry_flag_t flags,
1565                                const fib_route_path_t *rpaths)
1566 {
1567     fib_node_index_t old_path_list;
1568     fib_path_list_flags_t pl_flags;
1569     fib_entry_src_t *esrc;
1570
1571     esrc = fib_entry_src_find(fib_entry, source);
1572     if (NULL == esrc)
1573     {
1574         const dpo_id_t *dpo;
1575
1576         if (flags == FIB_ENTRY_FLAG_EXCLUSIVE) {
1577             dpo = &rpaths->dpo;
1578         } else {
1579             dpo = drop_dpo_get(fib_entry_get_dpo_proto(fib_entry));
1580         }
1581
1582         fib_entry =
1583             fib_entry_src_action_add(fib_entry,
1584                                      source,
1585                                      flags,
1586                                      dpo);
1587         esrc = fib_entry_src_find(fib_entry, source);
1588     }
1589
1590     /*
1591      * we are no doubt modifying a path-list. If the path-list
1592      * is shared, and hence not modifiable, then the index returned
1593      * will be for a different path-list. This FIB entry to needs
1594      * to maintain its lock appropriately.
1595      */
1596     old_path_list = esrc->fes_pl;
1597
1598     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_add));
1599
1600     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1601     fib_entry_flags_update(fib_entry, rpaths, &pl_flags, esrc);
1602
1603     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_path_add,
1604                              (esrc, fib_entry, pl_flags, rpaths));
1605
1606     fib_path_list_lock(esrc->fes_pl);
1607     fib_path_list_unlock(old_path_list);
1608
1609     return (fib_entry);
1610 }
1611
1612 /*
1613  * fib_entry_src_action_swap
1614  *
1615  * The source is providing new paths to replace the old ones.
1616  * Adding a source can result in a new fib_entry being created, which
1617  * can inturn mean the pool is realloc'd and thus the entry passed as
1618  * an argument it also realloc'd
1619  * @return the entry
1620  */
1621 fib_entry_t*
1622 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1623                                 fib_source_t source,
1624                                 fib_entry_flag_t flags,
1625                                 const fib_route_path_t *rpaths)
1626 {
1627     fib_node_index_t old_path_list;
1628     fib_path_list_flags_t pl_flags;
1629     fib_entry_src_t *esrc;
1630
1631     esrc = fib_entry_src_find(fib_entry, source);
1632
1633     if (NULL == esrc)
1634     {
1635         const dpo_id_t *dpo;
1636
1637         if (flags == FIB_ENTRY_FLAG_EXCLUSIVE) {
1638             dpo = &rpaths->dpo;
1639         } else {
1640             dpo = drop_dpo_get(fib_entry_get_dpo_proto(fib_entry));
1641         }
1642
1643         fib_entry = fib_entry_src_action_add(fib_entry,
1644                                              source,
1645                                              flags,
1646                                              dpo);
1647         esrc = fib_entry_src_find(fib_entry, source);
1648     }
1649     else
1650     {
1651         if (flags != esrc->fes_entry_flags)
1652         {
1653             FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_flags_change,
1654                                      (esrc, fib_entry, flags));
1655         }
1656         esrc->fes_entry_flags = flags;
1657     }
1658
1659     /*
1660      * swapping paths may create a new path-list (or may use an existing shared)
1661      * but we are certainly getting a different one. This FIB entry to needs
1662      * to maintain its lock appropriately.
1663      */
1664     old_path_list = esrc->fes_pl;
1665
1666     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_swap));
1667
1668     pl_flags = fib_entry_src_flags_2_path_list_flags(flags);
1669
1670     fib_entry_flags_update(fib_entry, rpaths, &pl_flags, esrc);
1671
1672     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_path_swap,
1673                              (esrc, fib_entry,
1674                               pl_flags, rpaths));
1675
1676     fib_path_list_lock(esrc->fes_pl);
1677     fib_path_list_unlock(old_path_list);
1678
1679     return (fib_entry);
1680 }
1681
1682 fib_entry_src_flag_t
1683 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1684                                   fib_source_t source,
1685                                   const fib_route_path_t *rpaths)
1686 {
1687     fib_path_list_flags_t pl_flags;
1688     fib_node_index_t old_path_list;
1689     fib_entry_src_t *esrc;
1690
1691     esrc = fib_entry_src_find(fib_entry, source);
1692
1693     ASSERT(NULL != esrc);
1694     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1695
1696     /*
1697      * we no doubt modifying a path-list. If the path-list
1698      * is shared, and hence not modifiable, then the index returned
1699      * will be for a different path-list. This FIB entry to needs
1700      * to maintain its lock appropriately.
1701      */
1702     old_path_list = esrc->fes_pl;
1703
1704     ASSERT(FIB_ENTRY_SRC_VFT_EXISTS(esrc, fesv_path_remove));
1705
1706     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1707     fib_entry_flags_update(fib_entry, rpaths, &pl_flags, esrc);
1708
1709     FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_path_remove,
1710                              (esrc, pl_flags, rpaths));
1711
1712     /*
1713      * lock the new path-list, unlock the old if it had one
1714      */
1715     fib_path_list_unlock(old_path_list);
1716
1717     if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1718         fib_path_list_lock(esrc->fes_pl);
1719         return (FIB_ENTRY_SRC_FLAG_ADDED);
1720     }
1721     else
1722     {
1723         /*
1724          * no more paths left from this source
1725          */
1726         fib_entry_src_action_remove_or_update_inherit(fib_entry, source);
1727         return (FIB_ENTRY_SRC_FLAG_NONE);
1728     }
1729 }
1730
1731 u8*
1732 fib_entry_src_format (fib_entry_t *fib_entry,
1733                       fib_source_t source,
1734                       u8* s)
1735 {
1736     fib_entry_src_t *esrc;
1737
1738     esrc = fib_entry_src_find(fib_entry, source);
1739
1740     FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_format, (esrc, s));
1741
1742     return (s);
1743 }
1744
1745 adj_index_t
1746 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1747                               fib_source_t source)
1748 {
1749     fib_entry_t *fib_entry;
1750     fib_entry_src_t *esrc;
1751
1752     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1753         return (ADJ_INDEX_INVALID);
1754
1755     fib_entry = fib_entry_get(fib_entry_index);
1756     esrc = fib_entry_src_find(fib_entry, source);
1757
1758     if (NULL != esrc)
1759     {
1760         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1761         {
1762             return (fib_path_list_get_adj(
1763                         esrc->fes_pl,
1764                         fib_entry_get_default_chain_type(fib_entry)));
1765         }
1766     }
1767     return (ADJ_INDEX_INVALID);
1768 }
1769
1770 const int
1771 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1772                               fib_source_t source,
1773                               dpo_id_t *dpo)
1774 {
1775     fib_entry_t *fib_entry;
1776     fib_entry_src_t *esrc;
1777
1778     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1779         return (0);
1780
1781     fib_entry = fib_entry_get(fib_entry_index);
1782     esrc = fib_entry_src_find(fib_entry, source);
1783
1784     if (NULL != esrc)
1785     {
1786         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1787         {
1788             fib_path_list_contribute_forwarding(
1789                 esrc->fes_pl,
1790                 fib_entry_get_default_chain_type(fib_entry),
1791                 FIB_PATH_LIST_FWD_FLAG_NONE,
1792                 dpo);
1793
1794             return (dpo_id_is_valid(dpo));
1795         }
1796     }
1797     return (0);
1798 }
1799
1800 fib_node_index_t
1801 fib_entry_get_path_list_for_source (fib_node_index_t fib_entry_index,
1802                                     fib_source_t source)
1803 {
1804   fib_entry_t *fib_entry;
1805   fib_entry_src_t *esrc;
1806
1807   if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1808     return FIB_NODE_INDEX_INVALID;
1809
1810   fib_entry = fib_entry_get(fib_entry_index);
1811   esrc = fib_entry_src_find(fib_entry, source);
1812
1813   if (esrc)
1814     return esrc->fes_pl;
1815
1816   return FIB_NODE_INDEX_INVALID;
1817 }
1818
1819 u32
1820 fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index,
1821                                               fib_source_t source)
1822 {
1823     fib_entry_t *fib_entry;
1824     fib_entry_src_t *esrc;
1825
1826     fib_entry = fib_entry_get(entry_index);
1827
1828     esrc = fib_entry_src_find(fib_entry, source);
1829
1830     if (NULL != esrc)
1831     {
1832         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1833         {
1834             return (fib_path_list_get_resolving_interface(esrc->fes_pl));
1835         }
1836     }
1837     return (~0);
1838 }
1839
1840 fib_entry_flag_t
1841 fib_entry_get_flags_for_source (fib_node_index_t entry_index,
1842                                 fib_source_t source)
1843 {
1844     fib_entry_t *fib_entry;
1845     fib_entry_src_t *esrc;
1846
1847     fib_entry = fib_entry_get(entry_index);
1848
1849     esrc = fib_entry_src_find(fib_entry, source);
1850
1851     if (NULL != esrc)
1852     {
1853         return (esrc->fes_entry_flags);
1854     }
1855
1856     return (FIB_ENTRY_FLAG_NONE);
1857 }
1858
1859 fib_source_t
1860 fib_entry_get_source_i (const fib_entry_t *fib_entry)
1861 {
1862     /* the vector of sources is deliberately arranged in priority order */
1863     if (0 == vec_len(fib_entry->fe_srcs))
1864         return (FIB_SOURCE_INVALID);
1865     return (vec_elt(fib_entry->fe_srcs, 0).fes_src);
1866 }
1867
1868 fib_entry_flag_t
1869 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1870 {
1871     /* the vector of sources is deliberately arranged in priority order */
1872     if (0 == vec_len(fib_entry->fe_srcs))
1873         return (FIB_ENTRY_FLAG_NONE);
1874     return (vec_elt(fib_entry->fe_srcs, 0).fes_entry_flags);
1875 }
1876
1877 void
1878 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1879                            fib_source_t source,
1880                            const void *data)
1881 {
1882     fib_entry_t *fib_entry;
1883     fib_entry_src_t *esrc;
1884
1885     fib_entry = fib_entry_get(fib_entry_index);
1886     esrc = fib_entry_src_find(fib_entry, source);
1887
1888     if (NULL != esrc)
1889     {
1890         FIB_ENTRY_SRC_VFT_INVOKE(fib_entry, esrc, fesv_set_data,
1891                                  (esrc, fib_entry, data));
1892     }
1893 }
1894
1895 const void*
1896 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1897                            fib_source_t source)
1898 {
1899     fib_entry_t *fib_entry;
1900     fib_entry_src_t *esrc;
1901
1902     fib_entry = fib_entry_get(fib_entry_index);
1903     esrc = fib_entry_src_find(fib_entry, source);
1904
1905     if (NULL != esrc)
1906     {
1907         FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, fesv_get_data,
1908                                             (esrc, fib_entry));
1909     }
1910     return (NULL);
1911 }
1912
1913 void
1914 fib_entry_src_module_init (void)
1915 {
1916     fib_entry_src_rr_register();
1917     fib_entry_src_interface_register();
1918     fib_entry_src_interpose_register();
1919     fib_entry_src_drop_register();
1920     fib_entry_src_simple_register();
1921     fib_entry_src_api_register();
1922     fib_entry_src_adj_register();
1923     fib_entry_src_mpls_register();
1924     fib_entry_src_lisp_register();
1925 }