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