src/vnet/fib/fib_entry_src.c

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