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