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