src/vnet/fib/fib_entry_src.c

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