vnet/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
  21 #include <vnet/fib/fib_entry_src.h>
  22 #include <vnet/fib/fib_table.h>
  23 #include <vnet/fib/fib_path_ext.h>
  24 #include <vnet/fib/fib_urpf_list.h>
  25
  26 /*
  27  * per-source type vft
  28  */
  29 static fib_entry_src_vft_t fib_entry_src_vft[FIB_SOURCE_MAX];
  30
  31 static fib_protocol_t
  32 fib_entry_get_proto (const fib_entry_t * fib_entry)
  33 {
  34     return (fib_entry->fe_prefix.fp_proto);
  35 }
  36
  37 void
  38 fib_entry_src_register (fib_source_t source,
  39                         const fib_entry_src_vft_t *vft)
  40 {
  41     fib_entry_src_vft[source] = *vft;
  42 }
  43
  44 static int
  45 fib_entry_src_cmp_for_sort (void * v1,
  46                             void * v2)
  47 {
  48     fib_entry_src_t *esrc1 = v1, *esrc2 = v2;
  49
  50     return (esrc1->fes_src - esrc2->fes_src);
  51 }
  52
  53 void
  54 fib_entry_src_action_init (fib_entry_t *fib_entry,
  55                            fib_source_t source)
  56
  57 {
  58     fib_entry_src_t esrc = {
  59         .fes_pl = FIB_NODE_INDEX_INVALID,
  60         .fes_flags = FIB_ENTRY_SRC_FLAG_NONE,
  61         .fes_src = source,
  62     };
  63
  64     if (NULL != fib_entry_src_vft[source].fesv_init)
  65     {
  66         fib_entry_src_vft[source].fesv_init(&esrc);
  67     }
  68
  69     vec_add1(fib_entry->fe_srcs, esrc);
  70     vec_sort_with_function(fib_entry->fe_srcs,
  71                            fib_entry_src_cmp_for_sort);
  72 }
  73
  74 static fib_entry_src_t *
  75 fib_entry_src_find (const fib_entry_t *fib_entry,
  76                     fib_source_t source,
  77                     u32 *index)
  78
  79 {
  80     fib_entry_src_t *esrc;
  81     int ii;
  82
  83     ii = 0;
  84     vec_foreach(esrc, fib_entry->fe_srcs)
  85     {
  86         if (esrc->fes_src == source)
  87         {
  88             if (NULL != index)
  89             {
  90                 *index = ii;
  91             }
  92             return (esrc);
  93         }
  94         else
  95         {
  96             ii++;
  97         }
  98     }
  99
 100     return (NULL);
 101 }
 102
 103 int
 104 fib_entry_is_sourced (fib_node_index_t fib_entry_index,
 105                       fib_source_t source)
 106 {
 107     fib_entry_t *fib_entry;
 108
 109     fib_entry = fib_entry_get(fib_entry_index);
 110
 111     return (NULL != fib_entry_src_find(fib_entry, source, NULL));
 112 }
 113
 114 static fib_entry_src_t *
 115 fib_entry_src_find_or_create (fib_entry_t *fib_entry,
 116                               fib_source_t source,
 117                               u32 *index)
 118 {
 119     fib_entry_src_t *esrc;
 120
 121     esrc = fib_entry_src_find(fib_entry, source, NULL);
 122
 123     if (NULL == esrc)
 124     {
 125         fib_entry_src_action_init(fib_entry, source);
 126     }
 127
 128     return (fib_entry_src_find(fib_entry, source, NULL));
 129 }
 130
 131 void
 132 fib_entry_src_action_deinit (fib_entry_t *fib_entry,
 133                              fib_source_t source)
 134
 135 {
 136     fib_entry_src_t *esrc;
 137     u32 index = ~0;
 138
 139     esrc = fib_entry_src_find(fib_entry, source, &index);
 140
 141     ASSERT(NULL != esrc);
 142
 143     if (NULL != fib_entry_src_vft[source].fesv_deinit)
 144     {
 145         fib_entry_src_vft[source].fesv_deinit(esrc);
 146     }
 147
 148     vec_free(esrc->fes_path_exts);
 149     vec_del1(fib_entry->fe_srcs, index);
 150 }
 151
 152 fib_entry_src_cover_res_t
 153 fib_entry_src_action_cover_change (fib_entry_t *fib_entry,
 154                                    fib_source_t source)
 155 {
 156     if (NULL != fib_entry_src_vft[source].fesv_cover_change)
 157     {
 158         return (fib_entry_src_vft[source].fesv_cover_change(
 159                     fib_entry_src_find(fib_entry, source, NULL),
 160                     fib_entry));
 161     }
 162
 163     fib_entry_src_cover_res_t res = {
 164         .install = !0,
 165         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
 166     };
 167     return (res);
 168 }
 169
 170 fib_entry_src_cover_res_t
 171 fib_entry_src_action_cover_update (fib_entry_t *fib_entry,
 172                                    fib_source_t source)
 173 {
 174     if (NULL != fib_entry_src_vft[source].fesv_cover_update)
 175     {
 176         return (fib_entry_src_vft[source].fesv_cover_update(
 177                     fib_entry_src_find(fib_entry, source, NULL),
 178                     fib_entry));
 179     }
 180
 181     fib_entry_src_cover_res_t res = {
 182         .install = !0,
 183         .bw_reason = FIB_NODE_BW_REASON_FLAG_NONE,
 184     };
 185     return (res);
 186 }
 187
 188 typedef struct fib_entry_src_collect_forwarding_ctx_t_
 189 {
 190     load_balance_path_t * next_hops;
 191     const fib_entry_t *fib_entry;
 192     const fib_entry_src_t *esrc;
 193     fib_forward_chain_type_t fct;
 194     int is_recursive;
 195 } fib_entry_src_collect_forwarding_ctx_t;
 196
 197 /**
 198  * @brief Determine whether this FIB entry should use a load-balance MAP
 199  * to support PIC edge fast convergence
 200  */
 201 load_balance_flags_t
 202 fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
 203 {
 204     /**
 205      * We'll use a LB map is the path-list has recursive paths.
 206      * recursive paths implies BGP, and hence scale.
 207      */
 208     if (ctx->is_recursive)
 209     {
 210         return (LOAD_BALANCE_FLAG_USES_MAP);
 211     }
 212     return (LOAD_BALANCE_FLAG_NONE);
 213 }
 214
 215 static int
 216 fib_entry_src_valid_out_label (mpls_label_t label)
 217 {
 218     return ((MPLS_LABEL_IS_REAL(label) ||
 219              MPLS_IETF_IPV4_EXPLICIT_NULL_LABEL == label ||
 220              MPLS_IETF_IPV6_EXPLICIT_NULL_LABEL == label ||
 221              MPLS_IETF_IMPLICIT_NULL_LABEL == label));
 222 }
 223
 224 static int
 225 fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
 226                                   fib_node_index_t path_index,
 227                                   void *arg)
 228 {
 229     fib_entry_src_collect_forwarding_ctx_t *ctx;
 230     fib_path_ext_t *path_ext;
 231
 232     ctx = arg;
 233
 234     /*
 235      * if the path is not resolved, don't include it.
 236      */
 237     if (!fib_path_is_resolved(path_index))
 238     {
 239         return (!0);
 240     }
 241
 242     if (fib_path_is_recursive(path_index))
 243     {
 244         ctx->is_recursive = 1;
 245     }
 246
 247     /*
 248      * get the matching path-extension for the path being visited.
 249      */
 250     vec_foreach(path_ext, ctx->esrc->fes_path_exts)
 251     {
 252         if (path_ext->fpe_path_index == path_index)
 253             break;
 254     }
 255
 256     if (NULL != path_ext &&
 257         path_ext->fpe_path_index == path_index &&
 258         fib_entry_src_valid_out_label(path_ext->fpe_label))
 259     {
 260         /*
 261          * found a matching extension. stack it to obtain the forwarding
 262          * info for this path.
 263          */
 264         ctx->next_hops = fib_path_ext_stack(path_ext, ctx->fct, ctx->next_hops);
 265     }
 266     else
 267     {
 268         load_balance_path_t *nh;
 269
 270         /*
 271          * no extension => no out-going label for this path. that's OK
 272          * in the case of an IP or EOS chain, but not for non-EOS
 273          */
 274         switch (ctx->fct)
 275         {
 276         case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
 277         case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
 278             /*
 279              * EOS traffic with no label to stack, we need the IP Adj
 280              */
 281             vec_add2(ctx->next_hops, nh, 1);
 282
 283             nh->path_index = path_index;
 284             nh->path_weight = fib_path_get_weight(path_index);
 285             fib_path_contribute_forwarding(path_index, ctx->fct, &nh->path_dpo);
 286
 287             break;
 288         case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
 289             if (fib_path_is_exclusive(path_index) ||
 290                 fib_path_is_deag(path_index))
 291             {
 292                 vec_add2(ctx->next_hops, nh, 1);
 293
 294                 nh->path_index = path_index;
 295                 nh->path_weight = fib_path_get_weight(path_index);
 296                 fib_path_contribute_forwarding(path_index,
 297                                                FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 298                                                &nh->path_dpo);
 299             }
 300             break;
 301         case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
 302         case FIB_FORW_CHAIN_TYPE_ETHERNET:
 303             ASSERT(0);
 304             break;
 305         }
 306     }
 307
 308     return (!0);
 309 }
 310
 311 void
 312 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
 313                      const fib_entry_src_t *esrc,
 314                      fib_forward_chain_type_t fct,
 315                      dpo_id_t *dpo_lb)
 316 {
 317     dpo_proto_t lb_proto;
 318
 319     /*
 320      * If the entry has path extensions then we construct a load-balance
 321      * by stacking the extensions on the forwarding chains of the paths.
 322      * Otherwise we use the load-balance of the path-list
 323      */
 324     fib_entry_src_collect_forwarding_ctx_t ctx = {
 325         .esrc = esrc,
 326         .fib_entry = fib_entry,
 327         .next_hops = NULL,
 328         .is_recursive = 0,
 329         .fct = fct,
 330     };
 331
 332     lb_proto = fib_proto_to_dpo(fib_entry_get_proto(fib_entry));
 333
 334     fib_path_list_walk(esrc->fes_pl,
 335                        fib_entry_src_collect_forwarding,
 336                        &ctx);
 337
 338     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
 339     {
 340         /*
 341          * the client provided the DPO that the entry should link to.
 342          * all entries must link to a LB, so if it is an LB already
 343          * then we can use it.
 344          */
 345         if ((1 == vec_len(ctx.next_hops)) &&
 346             (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
 347         {
 348             dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
 349             dpo_reset(&ctx.next_hops[0].path_dpo);
 350             return;
 351         }
 352     }
 353
 354     if (!dpo_id_is_valid(dpo_lb))
 355     {
 356         /*
 357          * first time create
 358          */
 359         flow_hash_config_t fhc;
 360
 361         fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
 362                                              dpo_proto_to_fib(lb_proto));
 363         dpo_set(dpo_lb,
 364                 DPO_LOAD_BALANCE,
 365                 lb_proto,
 366                 load_balance_create(0, lb_proto, fhc));
 367     }
 368
 369     load_balance_multipath_update(dpo_lb,
 370                                   ctx.next_hops,
 371                                   fib_entry_calc_lb_flags(&ctx));
 372
 373     /*
 374      * if this entry is sourced by the uRPF-exempt source then we
 375      * append the always present local0 interface (index 0) to the
 376      * uRPF list so it is not empty. that way packets pass the loose check.
 377      */
 378     index_t ui = fib_path_list_get_urpf(esrc->fes_pl);
 379
 380     if (fib_entry_is_sourced(fib_entry_get_index(fib_entry),
 381                              FIB_SOURCE_URPF_EXEMPT) &&
 382         (0 == fib_urpf_check_size(ui)))
 383     {
 384         /*
 385          * The uRPF list we get from the path-list is shared by all
 386          * other users of the list, but the uRPF exemption applies
 387          * only to this prefix. So we need our own list.
 388          */
 389         ui = fib_urpf_list_alloc_and_lock();
 390         fib_urpf_list_append(ui, 0);
 391         fib_urpf_list_bake(ui);
 392         load_balance_set_urpf(dpo_lb->dpoi_index, ui);
 393         fib_urpf_list_unlock(ui);
 394     }
 395     else
 396     {
 397         load_balance_set_urpf(dpo_lb->dpoi_index, ui);
 398     }
 399 }
 400
 401 void
 402 fib_entry_src_action_install (fib_entry_t *fib_entry,
 403                               fib_source_t source)
 404 {
 405     /*
 406      * Install the forwarding chain for the given source into the forwarding
 407      * tables
 408      */
 409     fib_forward_chain_type_t fct;
 410     fib_entry_src_t *esrc;
 411
 412     fct = fib_entry_get_default_chain_type(fib_entry);
 413     esrc = fib_entry_src_find(fib_entry, source, NULL);
 414
 415     fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb[fct]);
 416
 417     FIB_ENTRY_DBG(fib_entry, "install: %d",
 418                   fib_entry->fe_lb[fct]);
 419
 420     /*
 421      * insert the adj into the data-plane forwarding trie
 422      */
 423     fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
 424                                 &fib_entry->fe_prefix,
 425                                 &fib_entry->fe_lb[fct]);
 426
 427     if (FIB_FORW_CHAIN_TYPE_UNICAST_IP4 == fct ||
 428         FIB_FORW_CHAIN_TYPE_UNICAST_IP6 == fct)
 429     {
 430         for (fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 431              fct <= FIB_FORW_CHAIN_TYPE_MPLS_EOS;
 432              fct++)
 433         {
 434             /*
 435              * if any of the other chain types are already created they will need
 436              * updating too
 437              */
 438             if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
 439             {
 440                 fib_entry_src_mk_lb(fib_entry,
 441                                     esrc,
 442                                     fct,
 443                                     &fib_entry->fe_lb[fct]);
 444             }
 445         }
 446     }
 447 }
 448
 449 void
 450 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
 451 {
 452     fib_forward_chain_type_t fct;
 453
 454     fct = fib_entry_get_default_chain_type(fib_entry);
 455     /*
 456      * uninstall the forwarding chain from the forwarding tables
 457      */
 458     FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
 459                   fib_entry->fe_adj_index);
 460
 461     if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
 462     {
 463         fib_table_fwding_dpo_remove(
 464             fib_entry->fe_fib_index,
 465             &fib_entry->fe_prefix,
 466             &fib_entry->fe_lb[fct]);
 467
 468         dpo_reset(&fib_entry->fe_lb[fct]);
 469     }
 470 }
 471
 472 static void
 473 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
 474 {
 475     fib_node_index_t *entries = NULL;
 476
 477     fib_path_list_recursive_loop_detect(path_list_index, &entries);
 478
 479     vec_free(entries);
 480 }
 481
 482 void
 483 fib_entry_src_action_activate (fib_entry_t *fib_entry,
 484                                fib_source_t source)
 485
 486 {
 487     int houston_we_are_go_for_install;
 488     fib_entry_src_t *esrc;
 489
 490     esrc = fib_entry_src_find(fib_entry, source, NULL);
 491
 492     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
 493     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
 494
 495     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
 496
 497     if (NULL != fib_entry_src_vft[source].fesv_activate)
 498     {
 499         houston_we_are_go_for_install =
 500             fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
 501     }
 502     else
 503     {
 504         /*
 505          * the source is not providing an activate function, we'll assume
 506          * therefore it has no objection to installing the entry
 507          */
 508         houston_we_are_go_for_install = !0;
 509     }
 510
 511     /*
 512      * link to the path-list provided by the source, and go check
 513      * if that forms any loops in the graph.
 514      */
 515     fib_entry->fe_parent = esrc->fes_pl;
 516     fib_entry->fe_sibling =
 517         fib_path_list_child_add(fib_entry->fe_parent,
 518                                 FIB_NODE_TYPE_ENTRY,
 519                                 fib_entry_get_index(fib_entry));
 520
 521     fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
 522
 523     FIB_ENTRY_DBG(fib_entry, "activate: %d",
 524                   fib_entry->fe_parent);
 525
 526     if (0 != houston_we_are_go_for_install)
 527     {
 528         fib_entry_src_action_install(fib_entry, source);
 529     }
 530     else
 531     {
 532         fib_entry_src_action_uninstall(fib_entry);
 533     }
 534 }
 535
 536 void
 537 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
 538                                  fib_source_t source)
 539
 540 {
 541     fib_node_index_t path_list_index;
 542     fib_entry_src_t *esrc;
 543
 544     esrc = fib_entry_src_find(fib_entry, source, NULL);
 545
 546     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
 547
 548     if (NULL != fib_entry_src_vft[source].fesv_deactivate)
 549     {
 550         fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
 551     }
 552
 553     esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
 554
 555     FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
 556
 557     /*
 558      * un-link from an old path-list. Check for any loops this will clear
 559      */
 560     path_list_index = fib_entry->fe_parent;
 561     fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
 562
 563     fib_entry_recursive_loop_detect_i(path_list_index);
 564
 565     /*
 566      * this will unlock the path-list, so it may be invalid thereafter.
 567      */
 568     fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
 569     fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
 570 }
 571
 572 static void
 573 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
 574                                  fib_source_t source)
 575 {
 576     fib_entry_src_t *esrc;
 577
 578     vec_foreach(esrc, fib_entry->fe_srcs)
 579     {
 580         if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
 581         {
 582             fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
 583                                                              fib_entry,
 584                                                              source);
 585         }
 586     }
 587 }
 588
 589 void
 590 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
 591                                  fib_source_t source)
 592 {
 593     fib_node_index_t path_list_index;
 594     fib_entry_src_t *esrc;
 595
 596     esrc = fib_entry_src_find(fib_entry, source, NULL);
 597
 598     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
 599
 600     FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
 601                   fib_entry->fe_parent,
 602                   esrc->fes_pl);
 603
 604     if (fib_entry->fe_parent != esrc->fes_pl)
 605     {
 606         /*
 607          * un-link from an old path-list. Check for any loops this will clear
 608          */
 609         path_list_index = fib_entry->fe_parent;
 610         fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
 611
 612         /*
 613          * temporary lock so it doesn't get deleted when this entry is no
 614          * longer a child.
 615          */
 616         fib_path_list_lock(path_list_index);
 617
 618         /*
 619          * this entry is no longer a child. after unlinking check if any loops
 620          * were broken
 621          */
 622         fib_path_list_child_remove(path_list_index,
 623                                    fib_entry->fe_sibling);
 624
 625         fib_entry_recursive_loop_detect_i(path_list_index);
 626
 627         /*
 628          * link to the path-list provided by the source, and go check
 629          * if that forms any loops in the graph.
 630          */
 631         fib_entry->fe_parent = esrc->fes_pl;
 632         fib_entry->fe_sibling =
 633             fib_path_list_child_add(fib_entry->fe_parent,
 634                                     FIB_NODE_TYPE_ENTRY,
 635                                     fib_entry_get_index(fib_entry));
 636
 637         fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
 638         fib_path_list_unlock(path_list_index);
 639     }
 640     fib_entry_src_action_install(fib_entry, source);
 641     fib_entry_src_action_fwd_update(fib_entry, source);
 642 }
 643
 644 void
 645 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
 646                                 fib_source_t source)
 647 {
 648     fib_entry_src_t *esrc;
 649
 650     esrc = fib_entry_src_find(fib_entry, source, NULL);
 651
 652     if (NULL != fib_entry_src_vft[source].fesv_installed)
 653     {
 654         fib_entry_src_vft[source].fesv_installed(esrc,
 655                                                  fib_entry);
 656     }
 657
 658     fib_entry_src_action_fwd_update(fib_entry, source);
 659 }
 660
 661 /*
 662  * fib_entry_src_action_add
 663  *
 664  * Adding a source can result in a new fib_entry being created, which
 665  * can inturn mean the pool is realloc'd and thus the entry passed as
 666  * an argument it also realloc'd
 667  * @return the original entry
 668  */
 669 fib_entry_t *
 670 fib_entry_src_action_add (fib_entry_t *fib_entry,
 671                           fib_source_t source,
 672                           fib_entry_flag_t flags,
 673                           const dpo_id_t *dpo)
 674 {
 675     fib_node_index_t fib_entry_index;
 676     fib_entry_src_t *esrc;
 677
 678     esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
 679
 680     esrc->fes_ref_count++;
 681
 682     if (1 != esrc->fes_ref_count)
 683     {
 684         /*
 685          * we only want to add the source on the 0->1 transition
 686          */
 687         return (fib_entry);
 688     }
 689
 690     esrc->fes_entry_flags = flags;
 691
 692     /*
 693      * save variable so we can recover from a fib_entry realloc.
 694      */
 695     fib_entry_index = fib_entry_get_index(fib_entry);
 696
 697     if (NULL != fib_entry_src_vft[source].fesv_add)
 698     {
 699         fib_entry_src_vft[source].fesv_add(esrc,
 700                                            fib_entry,
 701                                            flags,
 702                                            fib_entry_get_proto(fib_entry),
 703                                            dpo);
 704     }
 705
 706     fib_entry = fib_entry_get(fib_entry_index);
 707
 708     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
 709
 710     fib_path_list_lock(esrc->fes_pl);
 711
 712     /*
 713      * the source owns a lock on the entry
 714      */
 715     fib_entry_lock(fib_entry_get_index(fib_entry));
 716
 717     return (fib_entry);
 718 }
 719
 720 fib_entry_src_flag_t
 721 fib_entry_src_action_remove (fib_entry_t *fib_entry,
 722                              fib_source_t source)
 723
 724 {
 725     fib_node_index_t old_path_list;
 726     fib_entry_src_flag_t sflags;
 727     fib_entry_src_t *esrc;
 728
 729     esrc = fib_entry_src_find(fib_entry, source, NULL);
 730
 731     if (NULL == esrc)
 732         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
 733
 734     esrc->fes_ref_count--;
 735     sflags = esrc->fes_flags;
 736
 737     if (0 != esrc->fes_ref_count)
 738     {
 739         /*
 740          * only remove the source on the 1->0 transisition
 741          */
 742         return (sflags);
 743     }
 744
 745     if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
 746     {
 747         fib_entry_src_action_deactivate(fib_entry, source);
 748     }
 749
 750     old_path_list = esrc->fes_pl;
 751
 752     if (NULL != fib_entry_src_vft[source].fesv_remove)
 753     {
 754         fib_entry_src_vft[source].fesv_remove(esrc);
 755     }
 756
 757     fib_path_list_unlock(old_path_list);
 758     fib_entry_unlock(fib_entry_get_index(fib_entry));
 759
 760     sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
 761     fib_entry_src_action_deinit(fib_entry, source);
 762
 763     return (sflags);
 764 }
 765
 766 static inline int
 767 fib_route_recurses_via_self (const fib_prefix_t *prefix,
 768                              const fib_route_path_t *rpath)
 769 {
 770     /*
 771      * not all zeros next hop &&
 772      * is recursive path &&
 773      * nexthop is same as the route's address
 774      */
 775     return ((!ip46_address_is_zero(&rpath->frp_addr)) &&
 776             (~0 == rpath->frp_sw_if_index) &&
 777             (0 == ip46_address_cmp(&rpath->frp_addr, &prefix->fp_addr)));
 778
 779 }
 780
 781 /*
 782  * fib_route_attached_cross_table
 783  *
 784  * Return true the the route is attached via an interface that
 785  * is not in the same table as the route
 786  */
 787 static inline int
 788 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
 789                                 const fib_route_path_t *rpath)
 790 {
 791     /*
 792      * - All zeros next-hop
 793      * - a valid interface
 794      * - entry's fib index not equeal to interface's index
 795      */
 796     if (ip46_address_is_zero(&rpath->frp_addr) &&
 797         (~0 != rpath->frp_sw_if_index) &&
 798         (fib_entry->fe_fib_index !=
 799          fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
 800                                              rpath->frp_sw_if_index)))
 801     {
 802         return (!0);
 803     }
 804     return (0);
 805 }
 806
 807 /*
 808  * fib_route_attached_cross_table
 809  *
 810  * Return true the the route is attached via an interface that
 811  * is not in the same table as the route
 812  */
 813 static inline int
 814 fib_path_is_attached (const fib_route_path_t *rpath)
 815 {
 816     /*
 817      * - All zeros next-hop
 818      * - a valid interface
 819      */
 820     if (ip46_address_is_zero(&rpath->frp_addr) &&
 821         (~0 != rpath->frp_sw_if_index))
 822     {
 823         return (!0);
 824     }
 825     return (0);
 826 }
 827
 828 fib_path_list_flags_t
 829 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
 830 {
 831     fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
 832
 833     if (eflags & FIB_ENTRY_FLAG_DROP)
 834     {
 835         plf |= FIB_PATH_LIST_FLAG_DROP;
 836     }
 837     if (eflags & FIB_ENTRY_FLAG_LOCAL)
 838     {
 839         plf |= FIB_PATH_LIST_FLAG_LOCAL;
 840     }
 841     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 842     {
 843         plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
 844     }
 845
 846     return (plf);
 847 }
 848
 849 static void
 850 fib_entry_flags_update (const fib_entry_t *fib_entry,
 851                         const fib_route_path_t *rpath,
 852                         fib_path_list_flags_t *pl_flags,
 853                         fib_entry_src_t *esrc)
 854 {
 855     /*
 856      * don't allow the addition of a recursive looped path for prefix
 857      * via itself.
 858      */
 859     if (fib_route_recurses_via_self(&fib_entry->fe_prefix, rpath))
 860     {
 861         /*
 862          * force the install of a drop path-list.
 863          * we want the entry to have some path-list, mainly so
 864          * the dodgy path can be rmeoved when the source stops playing
 865          * silly buggers.
 866          */
 867         *pl_flags |= FIB_PATH_LIST_FLAG_DROP;
 868     }
 869     else
 870     {
 871         *pl_flags &= ~FIB_PATH_LIST_FLAG_DROP;
 872     }
 873
 874     if ((esrc->fes_src == FIB_SOURCE_API) ||
 875         (esrc->fes_src == FIB_SOURCE_CLI))
 876     {
 877         if (fib_path_is_attached(rpath))
 878         {
 879             esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
 880         }
 881         else
 882         {
 883             esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
 884         }
 885     }
 886     if (fib_route_attached_cross_table(fib_entry, rpath))
 887     {
 888         esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
 889     }
 890     else
 891     {
 892         esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
 893     }
 894 }
 895
 896 /*
 897  * fib_entry_src_path_ext_add
 898  *
 899  * append a path extension to the entry's list
 900  */
 901 static void
 902 fib_entry_src_path_ext_append (fib_entry_src_t *esrc,
 903                                const fib_route_path_t *rpath)
 904 {
 905     if (MPLS_LABEL_INVALID != rpath->frp_label)
 906     {
 907         fib_path_ext_t *path_ext;
 908
 909         vec_add2(esrc->fes_path_exts, path_ext, 1);
 910
 911         fib_path_ext_init(path_ext, esrc->fes_pl, rpath);
 912     }
 913 }
 914
 915 /*
 916  * fib_entry_src_path_ext_insert
 917  *
 918  * insert, sorted, a path extension to the entry's list.
 919  * It's not strictly necessary in sort the path extensions, since each
 920  * extension has the path index to which it resolves. However, by being
 921  * sorted the load-balance produced has a deterministic order, not an order
 922  * based on the sequence of extension additions. this is a considerable benefit.
 923  */
 924 static void
 925 fib_entry_src_path_ext_insert (fib_entry_src_t *esrc,
 926                                const fib_route_path_t *rpath)
 927 {
 928     if (0 == vec_len(esrc->fes_path_exts))
 929         return (fib_entry_src_path_ext_append(esrc, rpath));
 930
 931     if (MPLS_LABEL_INVALID != rpath->frp_label)
 932     {
 933         fib_path_ext_t path_ext;
 934         int i = 0;
 935
 936         fib_path_ext_init(&path_ext, esrc->fes_pl, rpath);
 937
 938         while (i < vec_len(esrc->fes_path_exts) &&
 939                (fib_path_ext_cmp(&esrc->fes_path_exts[i], rpath) < 0))
 940         {
 941             i++;
 942         }
 943
 944         vec_insert_elts(esrc->fes_path_exts, &path_ext, 1, i);
 945     }
 946 }
 947
 948 /*
 949  * fib_entry_src_action_add
 950  *
 951  * Adding a source can result in a new fib_entry being created, which
 952  * can inturn mean the pool is realloc'd and thus the entry passed as
 953  * an argument it also realloc'd
 954  * @return the entry
 955  */
 956 fib_entry_t*
 957 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
 958                                fib_source_t source,
 959                                fib_entry_flag_t flags,
 960                                const fib_route_path_t *rpath)
 961 {
 962     fib_node_index_t old_path_list, fib_entry_index;
 963     fib_path_list_flags_t pl_flags;
 964     fib_path_ext_t *path_ext;
 965     fib_entry_src_t *esrc;
 966
 967     /*
 968      * save variable so we can recover from a fib_entry realloc.
 969      */
 970     fib_entry_index = fib_entry_get_index(fib_entry);
 971
 972     esrc = fib_entry_src_find(fib_entry, source, NULL);
 973     if (NULL == esrc)
 974     {
 975         fib_entry =
 976             fib_entry_src_action_add(fib_entry,
 977                                      source,
 978                                      flags,
 979                                      drop_dpo_get(
 980                                          fib_proto_to_dpo(
 981                                              fib_entry_get_proto(fib_entry))));
 982         esrc = fib_entry_src_find(fib_entry, source, NULL);
 983     }
 984
 985     /*
 986      * we are no doubt modifying a path-list. If the path-list
 987      * is shared, and hence not modifiable, then the index returned
 988      * will be for a different path-list. This FIB entry to needs
 989      * to maintain its lock appropriately.
 990      */
 991     old_path_list = esrc->fes_pl;
 992
 993     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add);
 994
 995     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
 996     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
 997
 998     fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath);
 999     fib_entry = fib_entry_get(fib_entry_index);
1000
1001     /*
1002      * re-resolve all the path-extensions with the new path-list
1003      */
1004     vec_foreach(path_ext, esrc->fes_path_exts)
1005     {
1006         fib_path_ext_resolve(path_ext, esrc->fes_pl);
1007     }
1008     /*
1009      * if the path has a label we need to add a path extension
1010      */
1011     fib_entry_src_path_ext_insert(esrc, rpath);
1012
1013     fib_path_list_lock(esrc->fes_pl);
1014     fib_path_list_unlock(old_path_list);
1015
1016     return (fib_entry);
1017 }
1018
1019 /*
1020  * fib_entry_src_action_swap
1021  *
1022  * The source is providing new paths to replace the old ones.
1023  * Adding a source can result in a new fib_entry being created, which
1024  * can inturn mean the pool is realloc'd and thus the entry passed as
1025  * an argument it also realloc'd
1026  * @return the entry
1027  */
1028 fib_entry_t*
1029 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1030                                 fib_source_t source,
1031                                 fib_entry_flag_t flags,
1032                                 const fib_route_path_t *rpaths)
1033 {
1034     fib_node_index_t old_path_list, fib_entry_index;
1035     fib_path_list_flags_t pl_flags;
1036     const fib_route_path_t *rpath;
1037     fib_entry_src_t *esrc;
1038
1039     esrc = fib_entry_src_find(fib_entry, source, NULL);
1040
1041     /*
1042      * save variable so we can recover from a fib_entry realloc.
1043      */
1044     fib_entry_index = fib_entry_get_index(fib_entry);
1045
1046     if (NULL == esrc)
1047     {
1048         fib_entry = fib_entry_src_action_add(fib_entry,
1049                                              source,
1050                                              flags,
1051                                              drop_dpo_get(
1052                                                  fib_proto_to_dpo(
1053                                                      fib_entry_get_proto(fib_entry))));
1054         esrc = fib_entry_src_find(fib_entry, source, NULL);
1055     }
1056
1057     /*
1058      * swapping paths may create a new path-list (or may use an existing shared)
1059      * but we are certainly getting a different one. This FIB entry to needs
1060      * to maintain its lock appropriately.
1061      */
1062     old_path_list = esrc->fes_pl;
1063
1064     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap);
1065
1066     pl_flags = fib_entry_src_flags_2_path_list_flags(flags);
1067
1068     vec_foreach(rpath, rpaths)
1069     {
1070         fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1071     }
1072
1073     fib_entry_src_vft[source].fesv_path_swap(esrc,
1074                                              fib_entry,
1075                                              pl_flags,
1076                                              rpaths);
1077
1078     vec_free(esrc->fes_path_exts);
1079     vec_foreach(rpath, rpaths)
1080     {
1081         fib_entry_src_path_ext_append(esrc, rpath);
1082     }
1083
1084     fib_entry = fib_entry_get(fib_entry_index);
1085
1086     fib_path_list_lock(esrc->fes_pl);
1087     fib_path_list_unlock(old_path_list);
1088
1089     return (fib_entry);
1090 }
1091
1092 fib_entry_src_flag_t
1093 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1094                                   fib_source_t source,
1095                                   const fib_route_path_t *rpath)
1096 {
1097     fib_path_list_flags_t pl_flags;
1098     fib_node_index_t old_path_list;
1099     fib_path_ext_t *path_ext;
1100     fib_entry_src_t *esrc;
1101
1102     esrc = fib_entry_src_find(fib_entry, source, NULL);
1103
1104     ASSERT(NULL != esrc);
1105     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1106
1107     /*
1108      * we no doubt modifying a path-list. If the path-list
1109      * is shared, and hence not modifiable, then the index returned
1110      * will be for a different path-list. This FIB entry to needs
1111      * to maintain its lock appropriately.
1112      */
1113     old_path_list = esrc->fes_pl;
1114
1115     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove);
1116
1117     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1118     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1119
1120     fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath);
1121     /*
1122      * find the matching path extension and remove it
1123      */
1124     vec_foreach(path_ext, esrc->fes_path_exts)
1125     {
1126         if (!fib_path_ext_cmp(path_ext, rpath))
1127         {
1128             /*
1129              * delete the element moving the remaining elements down 1 position.
1130              * this preserves the sorted order.
1131              */
1132             vec_delete(esrc->fes_path_exts, 1, (path_ext - esrc->fes_path_exts));
1133             break;
1134         }
1135     }
1136     /*
1137      * re-resolve all the path-extensions with the new path-list
1138      */
1139     vec_foreach(path_ext, esrc->fes_path_exts)
1140     {
1141         fib_path_ext_resolve(path_ext, esrc->fes_pl);
1142     }
1143
1144     /*
1145      * lock the new path-list, unlock the old if it had one
1146      */
1147     fib_path_list_unlock(old_path_list);
1148
1149     if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1150         fib_path_list_lock(esrc->fes_pl);
1151         return (FIB_ENTRY_SRC_FLAG_ADDED);
1152     }
1153     else
1154     {
1155         /*
1156          * no more paths left from this source
1157          */
1158         fib_entry_src_action_remove(fib_entry, source);
1159         return (FIB_ENTRY_SRC_FLAG_NONE);
1160     }
1161 }
1162
1163 u8*
1164 fib_entry_src_format (fib_entry_t *fib_entry,
1165                       fib_source_t source,
1166                       u8* s)
1167 {
1168     fib_entry_src_t *esrc;
1169
1170     esrc = fib_entry_src_find(fib_entry, source, NULL);
1171
1172     if (NULL != fib_entry_src_vft[source].fesv_format)
1173     {
1174         return (fib_entry_src_vft[source].fesv_format(esrc, s));
1175     }
1176     return (s);
1177 }
1178
1179 adj_index_t
1180 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1181                               fib_source_t source)
1182 {
1183     fib_entry_t *fib_entry;
1184     fib_entry_src_t *esrc;
1185
1186     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1187         return (ADJ_INDEX_INVALID);
1188
1189     fib_entry = fib_entry_get(fib_entry_index);
1190     esrc = fib_entry_src_find(fib_entry, source, NULL);
1191
1192     if (NULL != esrc)
1193     {
1194         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1195         {
1196             return (fib_path_list_get_adj(
1197                         esrc->fes_pl,
1198                         fib_entry_get_default_chain_type(fib_entry)));
1199         }
1200     }
1201     return (ADJ_INDEX_INVALID);
1202 }
1203
1204 const int
1205 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1206                               fib_source_t source,
1207                               dpo_id_t *dpo)
1208 {
1209     fib_entry_t *fib_entry;
1210     fib_entry_src_t *esrc;
1211
1212     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1213         return (0);
1214
1215     fib_entry = fib_entry_get(fib_entry_index);
1216     esrc = fib_entry_src_find(fib_entry, source, NULL);
1217
1218     if (NULL != esrc)
1219     {
1220         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1221         {
1222             fib_path_list_contribute_forwarding(
1223                 esrc->fes_pl,
1224                 fib_entry_get_default_chain_type(fib_entry),
1225                 dpo);
1226
1227             return (dpo_id_is_valid(dpo));
1228         }
1229     }
1230     return (0);
1231 }
1232
1233 u32
1234 fib_entry_get_resolving_interface_for_source (fib_node_index_t entry_index,
1235                                               fib_source_t source)
1236 {
1237     fib_entry_t *fib_entry;
1238     fib_entry_src_t *esrc;
1239
1240     fib_entry = fib_entry_get(entry_index);
1241
1242     esrc = fib_entry_src_find(fib_entry, source, NULL);
1243
1244     if (NULL != esrc)
1245     {
1246         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1247         {
1248             return (fib_path_list_get_resolving_interface(esrc->fes_pl));
1249         }
1250     }
1251     return (~0);
1252 }
1253
1254 fib_entry_flag_t
1255 fib_entry_get_flags_for_source (fib_node_index_t entry_index,
1256                                 fib_source_t source)
1257 {
1258     fib_entry_t *fib_entry;
1259     fib_entry_src_t *esrc;
1260
1261     fib_entry = fib_entry_get(entry_index);
1262
1263     esrc = fib_entry_src_find(fib_entry, source, NULL);
1264
1265     if (NULL != esrc)
1266     {
1267         return (esrc->fes_entry_flags);
1268     }
1269
1270     return (FIB_ENTRY_FLAG_NONE);
1271 }
1272
1273 fib_entry_flag_t
1274 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1275 {
1276     fib_entry_flag_t flags;
1277
1278     /*
1279      * the vector of sources is deliberately arranged in priority order
1280      */
1281     if (0 == vec_len(fib_entry->fe_srcs))
1282     {
1283         flags = FIB_ENTRY_FLAG_NONE;
1284     }
1285     else
1286     {
1287         fib_entry_src_t *esrc;
1288
1289         esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
1290         flags = esrc->fes_entry_flags;
1291     }
1292
1293     return (flags);
1294 }
1295
1296 void
1297 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1298                            fib_source_t source,
1299                            const void *data)
1300 {
1301     fib_entry_t *fib_entry;
1302     fib_entry_src_t *esrc;
1303
1304     fib_entry = fib_entry_get(fib_entry_index);
1305     esrc = fib_entry_src_find(fib_entry, source, NULL);
1306
1307     if (NULL != esrc &&
1308         NULL != fib_entry_src_vft[source].fesv_set_data)
1309     {
1310         fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data);
1311     }
1312 }
1313
1314 const void*
1315 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1316                            fib_source_t source)
1317 {
1318     fib_entry_t *fib_entry;
1319     fib_entry_src_t *esrc;
1320
1321     fib_entry = fib_entry_get(fib_entry_index);
1322     esrc = fib_entry_src_find(fib_entry, source, NULL);
1323
1324     if (NULL != esrc &&
1325         NULL != fib_entry_src_vft[source].fesv_get_data)
1326     {
1327         return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry));
1328     }
1329     return (NULL);
1330 }
1331
1332 void
1333 fib_entry_src_module_init (void)
1334 {
1335     fib_entry_src_rr_register();
1336     fib_entry_src_interface_register();
1337     fib_entry_src_default_route_register();
1338     fib_entry_src_special_register();
1339     fib_entry_src_api_register();
1340     fib_entry_src_adj_register();
1341     fib_entry_src_mpls_register();
1342     fib_entry_src_lisp_register();
1343 }