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