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