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             ASSERT(0);
 302             break;
 303         }
 304     }
 305
 306     return (!0);
 307 }
 308
 309 void
 310 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
 311                      const fib_entry_src_t *esrc,
 312                      fib_forward_chain_type_t fct,
 313                      dpo_id_t *dpo_lb)
 314 {
 315     dpo_proto_t lb_proto;
 316
 317     /*
 318      * If the entry has path extensions then we construct a load-balance
 319      * by stacking the extensions on the forwarding chains of the paths.
 320      * Otherwise we use the load-balance of the path-list
 321      */
 322     fib_entry_src_collect_forwarding_ctx_t ctx = {
 323         .esrc = esrc,
 324         .fib_entry = fib_entry,
 325         .next_hops = NULL,
 326         .is_recursive = 0,
 327         .fct = fct,
 328     };
 329
 330     lb_proto = fib_proto_to_dpo(fib_entry_get_proto(fib_entry));
 331
 332     fib_path_list_walk(esrc->fes_pl,
 333                        fib_entry_src_collect_forwarding,
 334                        &ctx);
 335
 336     if (esrc->fes_entry_flags & FIB_ENTRY_FLAG_EXCLUSIVE)
 337     {
 338         /*
 339          * the client provided the DPO that the entry should link to.
 340          * all entries must link to a LB, so if it is an LB already
 341          * then we can use it.
 342          */
 343         if ((1 == vec_len(ctx.next_hops)) &&
 344             (DPO_LOAD_BALANCE == ctx.next_hops[0].path_dpo.dpoi_type))
 345         {
 346             dpo_copy(dpo_lb, &ctx.next_hops[0].path_dpo);
 347             dpo_reset(&ctx.next_hops[0].path_dpo);
 348             return;
 349         }
 350     }
 351
 352     if (!dpo_id_is_valid(dpo_lb))
 353     {
 354         /*
 355          * first time create
 356          */
 357         flow_hash_config_t fhc;
 358
 359         fhc = fib_table_get_flow_hash_config(fib_entry->fe_fib_index,
 360                                              dpo_proto_to_fib(lb_proto));
 361         dpo_set(dpo_lb,
 362                 DPO_LOAD_BALANCE,
 363                 lb_proto,
 364                 load_balance_create(0, lb_proto, fhc));
 365     }
 366
 367     load_balance_multipath_update(dpo_lb,
 368                                   ctx.next_hops,
 369                                   fib_entry_calc_lb_flags(&ctx));
 370 }
 371
 372 void
 373 fib_entry_src_action_install (fib_entry_t *fib_entry,
 374                               fib_source_t source)
 375 {
 376     /*
 377      * Install the forwarding chain for the given source into the forwarding
 378      * tables
 379      */
 380     fib_forward_chain_type_t fct;
 381     fib_entry_src_t *esrc;
 382
 383     fct = fib_entry_get_default_chain_type(fib_entry);
 384     esrc = fib_entry_src_find(fib_entry, source, NULL);
 385
 386     fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb[fct]);
 387
 388     FIB_ENTRY_DBG(fib_entry, "install: %d",
 389                   fib_entry->fe_lb[fct]);
 390
 391     /*
 392      * insert the adj into the data-plane forwarding trie
 393      */
 394     fib_table_fwding_dpo_update(fib_entry->fe_fib_index,
 395                                 &fib_entry->fe_prefix,
 396                                 &fib_entry->fe_lb[fct]);
 397
 398     if (FIB_FORW_CHAIN_TYPE_UNICAST_IP4 == fct ||
 399         FIB_FORW_CHAIN_TYPE_UNICAST_IP6 == fct)
 400     {
 401         for (fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 402              fct <= FIB_FORW_CHAIN_TYPE_MPLS_EOS;
 403              fct++)
 404         {
 405             /*
 406              * if any of the other chain types are already created they will need
 407              * updating too
 408              */
 409             if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
 410             {
 411                 fib_entry_src_mk_lb(fib_entry,
 412                                     esrc,
 413                                     fct,
 414                                     &fib_entry->fe_lb[fct]);
 415             }
 416         }
 417     }
 418 }
 419
 420 void
 421 fib_entry_src_action_uninstall (fib_entry_t *fib_entry)
 422 {
 423     fib_forward_chain_type_t fct;
 424
 425     fct = fib_entry_get_default_chain_type(fib_entry);
 426     /*
 427      * uninstall the forwarding chain for the given source from the
 428      * forwarding tables
 429      */
 430     FIB_ENTRY_DBG(fib_entry, "uninstall: %d",
 431                   fib_entry->fe_adj_index);
 432
 433     if (dpo_id_is_valid(&fib_entry->fe_lb[fct]))
 434     {
 435         /* fib_forward_chain_type_t fct; */
 436         /* fib_path_ext_t *path_ext; */
 437
 438         fib_table_fwding_dpo_remove(
 439             fib_entry->fe_fib_index,
 440             &fib_entry->fe_prefix,
 441             &fib_entry->fe_lb[fct]);
 442
 443         dpo_reset(&fib_entry->fe_lb[fct]);
 444     }
 445 }
 446
 447 static void
 448 fib_entry_recursive_loop_detect_i (fib_node_index_t path_list_index)
 449 {
 450     fib_node_index_t *entries = NULL;
 451
 452     fib_path_list_recursive_loop_detect(path_list_index, &entries);
 453
 454     vec_free(entries);
 455 }
 456
 457 void
 458 fib_entry_src_action_activate (fib_entry_t *fib_entry,
 459                                fib_source_t source)
 460
 461 {
 462     int houston_we_are_go_for_install;
 463     fib_entry_src_t *esrc;
 464
 465     esrc = fib_entry_src_find(fib_entry, source, NULL);
 466
 467     ASSERT(!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE));
 468     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
 469
 470     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ACTIVE;
 471
 472     if (NULL != fib_entry_src_vft[source].fesv_activate)
 473     {
 474         houston_we_are_go_for_install =
 475             fib_entry_src_vft[source].fesv_activate(esrc, fib_entry);
 476     }
 477     else
 478     {
 479         /*
 480          * the source is not providing an activate function, we'll assume
 481          * therefore it has no objection to installing the entry
 482          */
 483         houston_we_are_go_for_install = !0;
 484     }
 485
 486     /*
 487      * link to the path-list provided by the source, and go check
 488      * if that forms any loops in the graph.
 489      */
 490     fib_entry->fe_parent = esrc->fes_pl;
 491     fib_entry->fe_sibling =
 492         fib_path_list_child_add(fib_entry->fe_parent,
 493                                 FIB_NODE_TYPE_ENTRY,
 494                                 fib_entry_get_index(fib_entry));
 495
 496     fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
 497
 498     FIB_ENTRY_DBG(fib_entry, "activate: %d",
 499                   fib_entry->fe_parent);
 500
 501     if (0 != houston_we_are_go_for_install)
 502     {
 503         fib_entry_src_action_install(fib_entry, source);
 504     }
 505     else
 506     {
 507         fib_entry_src_action_uninstall(fib_entry);
 508     }
 509 }
 510
 511 void
 512 fib_entry_src_action_deactivate (fib_entry_t *fib_entry,
 513                                  fib_source_t source)
 514
 515 {
 516     fib_node_index_t path_list_index;
 517     fib_entry_src_t *esrc;
 518
 519     esrc = fib_entry_src_find(fib_entry, source, NULL);
 520
 521     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
 522
 523     if (NULL != fib_entry_src_vft[source].fesv_deactivate)
 524     {
 525         fib_entry_src_vft[source].fesv_deactivate(esrc, fib_entry);
 526     }
 527
 528     esrc->fes_flags &= ~FIB_ENTRY_SRC_FLAG_ACTIVE;
 529
 530     FIB_ENTRY_DBG(fib_entry, "deactivate: %d", fib_entry->fe_parent);
 531
 532     /*
 533      * un-link from an old path-list. Check for any loops this will clear
 534      */
 535     path_list_index = fib_entry->fe_parent;
 536     fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
 537
 538     fib_entry_recursive_loop_detect_i(path_list_index);
 539
 540     /*
 541      * this will unlock the path-list, so it may be invalid thereafter.
 542      */
 543     fib_path_list_child_remove(path_list_index, fib_entry->fe_sibling);
 544     fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID;
 545 }
 546
 547 static void
 548 fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry,
 549                                  fib_source_t source)
 550 {
 551     fib_entry_src_t *esrc;
 552
 553     vec_foreach(esrc, fib_entry->fe_srcs)
 554     {
 555         if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update)
 556         {
 557             fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc,
 558                                                              fib_entry,
 559                                                              source);
 560         }
 561     }
 562 }
 563
 564 void
 565 fib_entry_src_action_reactivate (fib_entry_t *fib_entry,
 566                                  fib_source_t source)
 567 {
 568     fib_node_index_t path_list_index;
 569     fib_entry_src_t *esrc;
 570
 571     esrc = fib_entry_src_find(fib_entry, source, NULL);
 572
 573     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE);
 574
 575     FIB_ENTRY_DBG(fib_entry, "reactivate: %d to %d",
 576                   fib_entry->fe_parent,
 577                   esrc->fes_pl);
 578
 579     if (fib_entry->fe_parent != esrc->fes_pl)
 580     {
 581         /*
 582          * un-link from an old path-list. Check for any loops this will clear
 583          */
 584         path_list_index = fib_entry->fe_parent;
 585         fib_entry->fe_parent = FIB_NODE_INDEX_INVALID;
 586
 587         /*
 588          * temporary lock so it doesn't get deleted when this entry is no
 589          * longer a child.
 590          */
 591         fib_path_list_lock(path_list_index);
 592
 593         /*
 594          * this entry is no longer a child. after unlinking check if any loops
 595          * were broken
 596          */
 597         fib_path_list_child_remove(path_list_index,
 598                                    fib_entry->fe_sibling);
 599
 600         fib_entry_recursive_loop_detect_i(path_list_index);
 601
 602         /*
 603          * link to the path-list provided by the source, and go check
 604          * if that forms any loops in the graph.
 605          */
 606         fib_entry->fe_parent = esrc->fes_pl;
 607         fib_entry->fe_sibling =
 608             fib_path_list_child_add(fib_entry->fe_parent,
 609                                     FIB_NODE_TYPE_ENTRY,
 610                                     fib_entry_get_index(fib_entry));
 611
 612         fib_entry_recursive_loop_detect_i(fib_entry->fe_parent);
 613         fib_path_list_unlock(path_list_index);
 614     }
 615     fib_entry_src_action_install(fib_entry, source);
 616     fib_entry_src_action_fwd_update(fib_entry, source);
 617 }
 618
 619 void
 620 fib_entry_src_action_installed (const fib_entry_t *fib_entry,
 621                                 fib_source_t source)
 622 {
 623     fib_entry_src_t *esrc;
 624
 625     esrc = fib_entry_src_find(fib_entry, source, NULL);
 626
 627     if (NULL != fib_entry_src_vft[source].fesv_installed)
 628     {
 629         fib_entry_src_vft[source].fesv_installed(esrc,
 630                                                  fib_entry);
 631     }
 632
 633     fib_entry_src_action_fwd_update(fib_entry, source);
 634 }
 635
 636 /*
 637  * fib_entry_src_action_add
 638  *
 639  * Adding a source can result in a new fib_entry being created, which
 640  * can inturn mean the pool is realloc'd and thus the entry passed as
 641  * an argument it also realloc'd
 642  * @return the original entry
 643  */
 644 fib_entry_t *
 645 fib_entry_src_action_add (fib_entry_t *fib_entry,
 646                           fib_source_t source,
 647                           fib_entry_flag_t flags,
 648                           const dpo_id_t *dpo)
 649 {
 650     fib_node_index_t fib_entry_index;
 651     fib_entry_src_t *esrc;
 652
 653     esrc = fib_entry_src_find_or_create(fib_entry, source, NULL);
 654
 655     esrc->fes_ref_count++;
 656
 657     if (1 != esrc->fes_ref_count)
 658     {
 659         /*
 660          * we only want to add the source on the 0->1 transition
 661          */
 662         return (fib_entry);
 663     }
 664
 665     esrc->fes_entry_flags = flags;
 666
 667     /*
 668      * save variable so we can recover from a fib_entry realloc.
 669      */
 670     fib_entry_index = fib_entry_get_index(fib_entry);
 671
 672     if (NULL != fib_entry_src_vft[source].fesv_add)
 673     {
 674         fib_entry_src_vft[source].fesv_add(esrc,
 675                                            fib_entry,
 676                                            flags,
 677                                            fib_entry_get_proto(fib_entry),
 678                                            dpo);
 679     }
 680
 681     fib_entry = fib_entry_get(fib_entry_index);
 682
 683     esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_ADDED;
 684
 685     fib_path_list_lock(esrc->fes_pl);
 686
 687     /*
 688      * the source owns a lock on the entry
 689      */
 690     fib_entry_lock(fib_entry_get_index(fib_entry));
 691
 692     return (fib_entry);
 693 }
 694
 695 fib_entry_src_flag_t
 696 fib_entry_src_action_remove (fib_entry_t *fib_entry,
 697                              fib_source_t source)
 698
 699 {
 700     fib_node_index_t old_path_list;
 701     fib_entry_src_flag_t sflags;
 702     fib_entry_src_t *esrc;
 703
 704     esrc = fib_entry_src_find(fib_entry, source, NULL);
 705
 706     if (NULL == esrc)
 707         return (FIB_ENTRY_SRC_FLAG_ACTIVE);
 708
 709     esrc->fes_ref_count--;
 710     sflags = esrc->fes_flags;
 711
 712     if (0 != esrc->fes_ref_count)
 713     {
 714         /*
 715          * only remove the source on the 1->0 transisition
 716          */
 717         return (sflags);
 718     }
 719
 720     if (esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ACTIVE)
 721     {
 722         fib_entry_src_action_deactivate(fib_entry, source);
 723     }
 724
 725     old_path_list = esrc->fes_pl;
 726
 727     if (NULL != fib_entry_src_vft[source].fesv_remove)
 728     {
 729         fib_entry_src_vft[source].fesv_remove(esrc);
 730     }
 731
 732     fib_path_list_unlock(old_path_list);
 733     fib_entry_unlock(fib_entry_get_index(fib_entry));
 734
 735     sflags &= ~FIB_ENTRY_SRC_FLAG_ADDED;
 736     fib_entry_src_action_deinit(fib_entry, source);
 737
 738     return (sflags);
 739 }
 740
 741 static inline int
 742 fib_route_recurses_via_self (const fib_prefix_t *prefix,
 743                              const fib_route_path_t *rpath)
 744 {
 745     /*
 746      * not all zeros next hop &&
 747      * is recursive path &&
 748      * nexthop is same as the route's address
 749      */
 750     return ((!ip46_address_is_zero(&rpath->frp_addr)) &&
 751             (~0 == rpath->frp_sw_if_index) &&
 752             (0 == ip46_address_cmp(&rpath->frp_addr, &prefix->fp_addr)));
 753
 754 }
 755
 756 /*
 757  * fib_route_attached_cross_table
 758  *
 759  * Return true the the route is attached via an interface that
 760  * is not in the same table as the route
 761  */
 762 static inline int
 763 fib_route_attached_cross_table (const fib_entry_t *fib_entry,
 764                                 const fib_route_path_t *rpath)
 765 {
 766     /*
 767      * - All zeros next-hop
 768      * - a valid interface
 769      * - entry's fib index not equeal to interface's index
 770      */
 771     if (ip46_address_is_zero(&rpath->frp_addr) &&
 772         (~0 != rpath->frp_sw_if_index) &&
 773         (fib_entry->fe_fib_index !=
 774          fib_table_get_index_for_sw_if_index(fib_entry_get_proto(fib_entry),
 775                                              rpath->frp_sw_if_index)))
 776     {
 777         return (!0);
 778     }
 779     return (0);
 780 }
 781
 782 /*
 783  * fib_route_attached_cross_table
 784  *
 785  * Return true the the route is attached via an interface that
 786  * is not in the same table as the route
 787  */
 788 static inline int
 789 fib_path_is_attached (const fib_route_path_t *rpath)
 790 {
 791     /*
 792      * - All zeros next-hop
 793      * - a valid interface
 794      */
 795     if (ip46_address_is_zero(&rpath->frp_addr) &&
 796         (~0 != rpath->frp_sw_if_index))
 797     {
 798         return (!0);
 799     }
 800     return (0);
 801 }
 802
 803 fib_path_list_flags_t
 804 fib_entry_src_flags_2_path_list_flags (fib_entry_flag_t eflags)
 805 {
 806     fib_path_list_flags_t plf = FIB_PATH_LIST_FLAG_NONE;
 807
 808     if (eflags & FIB_ENTRY_FLAG_DROP)
 809     {
 810         plf |= FIB_PATH_LIST_FLAG_DROP;
 811     }
 812     if (eflags & FIB_ENTRY_FLAG_LOCAL)
 813     {
 814         plf |= FIB_PATH_LIST_FLAG_LOCAL;
 815     }
 816     if (eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
 817     {
 818         plf |= FIB_PATH_LIST_FLAG_EXCLUSIVE;
 819     }
 820
 821     return (plf);
 822 }
 823
 824 static void
 825 fib_entry_flags_update (const fib_entry_t *fib_entry,
 826                         const fib_route_path_t *rpath,
 827                         fib_path_list_flags_t *pl_flags,
 828                         fib_entry_src_t *esrc)
 829 {
 830     /*
 831      * don't allow the addition of a recursive looped path for prefix
 832      * via itself.
 833      */
 834     if (fib_route_recurses_via_self(&fib_entry->fe_prefix, rpath))
 835     {
 836         /*
 837          * force the install of a drop path-list.
 838          * we want the entry to have some path-list, mainly so
 839          * the dodgy path can be rmeoved when the source stops playing
 840          * silly buggers.
 841          */
 842         *pl_flags |= FIB_PATH_LIST_FLAG_DROP;
 843     }
 844     else
 845     {
 846         *pl_flags &= ~FIB_PATH_LIST_FLAG_DROP;
 847     }
 848
 849     if ((esrc->fes_src == FIB_SOURCE_API) ||
 850         (esrc->fes_src == FIB_SOURCE_CLI))
 851     {
 852         if (fib_path_is_attached(rpath))
 853         {
 854             esrc->fes_entry_flags |= FIB_ENTRY_FLAG_ATTACHED;
 855         }
 856         else
 857         {
 858             esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_ATTACHED;
 859         }
 860     }
 861     if (fib_route_attached_cross_table(fib_entry, rpath))
 862     {
 863         esrc->fes_entry_flags |= FIB_ENTRY_FLAG_IMPORT;
 864     }
 865     else
 866     {
 867         esrc->fes_entry_flags &= ~FIB_ENTRY_FLAG_IMPORT;
 868     }
 869 }
 870
 871 /*
 872  * fib_entry_src_path_ext_add
 873  *
 874  * append a path extension to the entry's list
 875  */
 876 static void
 877 fib_entry_src_path_ext_append (fib_entry_src_t *esrc,
 878                                const fib_route_path_t *rpath)
 879 {
 880     if (MPLS_LABEL_INVALID != rpath->frp_label)
 881     {
 882         fib_path_ext_t *path_ext;
 883
 884         vec_add2(esrc->fes_path_exts, path_ext, 1);
 885
 886         fib_path_ext_init(path_ext, esrc->fes_pl, rpath);
 887     }
 888 }
 889
 890 /*
 891  * fib_entry_src_path_ext_insert
 892  *
 893  * insert, sorted, a path extension to the entry's list.
 894  * It's not strictly necessary in sort the path extensions, since each
 895  * extension has the path index to which it resolves. However, by being
 896  * sorted the load-balance produced has a deterministic order, not an order
 897  * based on the sequence of extension additions. this is a considerable benefit.
 898  */
 899 static void
 900 fib_entry_src_path_ext_insert (fib_entry_src_t *esrc,
 901                                const fib_route_path_t *rpath)
 902 {
 903     if (0 == vec_len(esrc->fes_path_exts))
 904         return (fib_entry_src_path_ext_append(esrc, rpath));
 905
 906     if (MPLS_LABEL_INVALID != rpath->frp_label)
 907     {
 908         fib_path_ext_t path_ext;
 909         int i = 0;
 910
 911         fib_path_ext_init(&path_ext, esrc->fes_pl, rpath);
 912
 913         while (i < vec_len(esrc->fes_path_exts) &&
 914                (fib_path_ext_cmp(&esrc->fes_path_exts[i], rpath) < 0))
 915         {
 916             i++;
 917         }
 918
 919         vec_insert_elts(esrc->fes_path_exts, &path_ext, 1, i);
 920     }
 921 }
 922
 923 /*
 924  * fib_entry_src_action_add
 925  *
 926  * Adding a source can result in a new fib_entry being created, which
 927  * can inturn mean the pool is realloc'd and thus the entry passed as
 928  * an argument it also realloc'd
 929  * @return the entry
 930  */
 931 fib_entry_t*
 932 fib_entry_src_action_path_add (fib_entry_t *fib_entry,
 933                                fib_source_t source,
 934                                fib_entry_flag_t flags,
 935                                const fib_route_path_t *rpath)
 936 {
 937     fib_node_index_t old_path_list, fib_entry_index;
 938     fib_path_list_flags_t pl_flags;
 939     fib_path_ext_t *path_ext;
 940     fib_entry_src_t *esrc;
 941
 942     /*
 943      * save variable so we can recover from a fib_entry realloc.
 944      */
 945     fib_entry_index = fib_entry_get_index(fib_entry);
 946
 947     esrc = fib_entry_src_find(fib_entry, source, NULL);
 948     if (NULL == esrc)
 949     {
 950         fib_entry =
 951             fib_entry_src_action_add(fib_entry,
 952                                      source,
 953                                      flags,
 954                                      drop_dpo_get(
 955                                          fib_proto_to_dpo(
 956                                              fib_entry_get_proto(fib_entry))));
 957         esrc = fib_entry_src_find(fib_entry, source, NULL);
 958     }
 959
 960     /*
 961      * we are no doubt modifying a path-list. If the path-list
 962      * is shared, and hence not modifiable, then the index returned
 963      * will be for a different path-list. This FIB entry to needs
 964      * to maintain its lock appropriately.
 965      */
 966     old_path_list = esrc->fes_pl;
 967
 968     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_add);
 969
 970     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
 971     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
 972
 973     fib_entry_src_vft[source].fesv_path_add(esrc, fib_entry, pl_flags, rpath);
 974     fib_entry = fib_entry_get(fib_entry_index);
 975
 976     /*
 977      * re-resolve all the path-extensions with the new path-list
 978      */
 979     vec_foreach(path_ext, esrc->fes_path_exts)
 980     {
 981         fib_path_ext_resolve(path_ext, esrc->fes_pl);
 982     }
 983     /*
 984      * if the path has a label we need to add a path extension
 985      */
 986     fib_entry_src_path_ext_insert(esrc, rpath);
 987
 988     fib_path_list_lock(esrc->fes_pl);
 989     fib_path_list_unlock(old_path_list);
 990
 991     return (fib_entry);
 992 }
 993
 994 /*
 995  * fib_entry_src_action_swap
 996  *
 997  * The source is providing new paths to replace the old ones.
 998  * Adding a source can result in a new fib_entry being created, which
 999  * can inturn mean the pool is realloc'd and thus the entry passed as
1000  * an argument it also realloc'd
1001  * @return the entry
1002  */
1003 fib_entry_t*
1004 fib_entry_src_action_path_swap (fib_entry_t *fib_entry,
1005                                 fib_source_t source,
1006                                 fib_entry_flag_t flags,
1007                                 const fib_route_path_t *rpaths)
1008 {
1009     fib_node_index_t old_path_list, fib_entry_index;
1010     fib_path_list_flags_t pl_flags;
1011     const fib_route_path_t *rpath;
1012     fib_entry_src_t *esrc;
1013
1014     esrc = fib_entry_src_find(fib_entry, source, NULL);
1015
1016     /*
1017      * save variable so we can recover from a fib_entry realloc.
1018      */
1019     fib_entry_index = fib_entry_get_index(fib_entry);
1020
1021     if (NULL == esrc)
1022     {
1023         fib_entry = fib_entry_src_action_add(fib_entry,
1024                                              source,
1025                                              flags,
1026                                              drop_dpo_get(
1027                                                  fib_proto_to_dpo(
1028                                                      fib_entry_get_proto(fib_entry))));
1029         esrc = fib_entry_src_find(fib_entry, source, NULL);
1030     }
1031
1032     /*
1033      * swapping paths may create a new path-list (or may use an existing shared)
1034      * but we are certainly getting a different one. This FIB entry to needs
1035      * to maintain its lock appropriately.
1036      */
1037     old_path_list = esrc->fes_pl;
1038
1039     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_swap);
1040
1041     pl_flags = fib_entry_src_flags_2_path_list_flags(
1042                    fib_entry_get_flags_i(fib_entry));
1043     vec_foreach(rpath, rpaths)
1044     {
1045         fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1046     }
1047
1048     fib_entry_src_vft[source].fesv_path_swap(esrc,
1049                                              fib_entry,
1050                                              pl_flags,
1051                                              rpaths);
1052
1053     vec_free(esrc->fes_path_exts);
1054     vec_foreach(rpath, rpaths)
1055     {
1056         fib_entry_src_path_ext_append(esrc, rpath);
1057     }
1058
1059     fib_entry = fib_entry_get(fib_entry_index);
1060
1061     fib_path_list_lock(esrc->fes_pl);
1062     fib_path_list_unlock(old_path_list);
1063
1064     return (fib_entry);
1065 }
1066
1067 fib_entry_src_flag_t
1068 fib_entry_src_action_path_remove (fib_entry_t *fib_entry,
1069                                   fib_source_t source,
1070                                   const fib_route_path_t *rpath)
1071 {
1072     fib_path_list_flags_t pl_flags;
1073     fib_node_index_t old_path_list;
1074     fib_path_ext_t *path_ext;
1075     fib_entry_src_t *esrc;
1076
1077     esrc = fib_entry_src_find(fib_entry, source, NULL);
1078
1079     ASSERT(NULL != esrc);
1080     ASSERT(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED);
1081
1082     /*
1083      * we no doubt modifying a path-list. If the path-list
1084      * is shared, and hence not modifiable, then the index returned
1085      * will be for a different path-list. This FIB entry to needs
1086      * to maintain its lock appropriately.
1087      */
1088     old_path_list = esrc->fes_pl;
1089
1090     ASSERT(NULL != fib_entry_src_vft[source].fesv_path_remove);
1091
1092     pl_flags = fib_entry_src_flags_2_path_list_flags(fib_entry_get_flags_i(fib_entry));
1093     fib_entry_flags_update(fib_entry, rpath, &pl_flags, esrc);
1094
1095     fib_entry_src_vft[source].fesv_path_remove(esrc, pl_flags, rpath);
1096     /*
1097      * find the matching path extension and remove it
1098      */
1099     vec_foreach(path_ext, esrc->fes_path_exts)
1100     {
1101         if (!fib_path_ext_cmp(path_ext, rpath))
1102         {
1103             /*
1104              * delete the element moving the remaining elements down 1 position.
1105              * this preserves the sorted order.
1106              */
1107             vec_delete(esrc->fes_path_exts, 1, (path_ext - esrc->fes_path_exts));
1108             break;
1109         }
1110     }
1111     /*
1112      * re-resolve all the path-extensions with the new path-list
1113      */
1114     vec_foreach(path_ext, esrc->fes_path_exts)
1115     {
1116         fib_path_ext_resolve(path_ext, esrc->fes_pl);
1117     }
1118
1119     /*
1120      * lock the new path-list, unlock the old if it had one
1121      */
1122     fib_path_list_unlock(old_path_list);
1123
1124     if (FIB_NODE_INDEX_INVALID != esrc->fes_pl) {
1125         fib_path_list_lock(esrc->fes_pl);
1126         return (FIB_ENTRY_SRC_FLAG_ADDED);
1127     }
1128     else
1129     {
1130         /*
1131          * no more paths left from this source
1132          */
1133         fib_entry_src_action_remove(fib_entry, source);
1134         return (FIB_ENTRY_SRC_FLAG_NONE);
1135     }
1136 }
1137
1138 u8*
1139 fib_entry_src_format (fib_entry_t *fib_entry,
1140                       fib_source_t source,
1141                       u8* s)
1142 {
1143     fib_entry_src_t *esrc;
1144
1145     esrc = fib_entry_src_find(fib_entry, source, NULL);
1146
1147     if (NULL != fib_entry_src_vft[source].fesv_format)
1148     {
1149         return (fib_entry_src_vft[source].fesv_format(esrc, s));
1150     }
1151     return (s);
1152 }
1153
1154 adj_index_t
1155 fib_entry_get_adj_for_source (fib_node_index_t fib_entry_index,
1156                               fib_source_t source)
1157 {
1158     fib_entry_t *fib_entry;
1159     fib_entry_src_t *esrc;
1160
1161     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1162         return (ADJ_INDEX_INVALID);
1163
1164     fib_entry = fib_entry_get(fib_entry_index);
1165     esrc = fib_entry_src_find(fib_entry, source, NULL);
1166
1167     if (NULL != esrc)
1168     {
1169         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1170         {
1171             return (fib_path_list_get_adj(
1172                         esrc->fes_pl,
1173                         fib_entry_get_default_chain_type(fib_entry)));
1174         }
1175     }
1176     return (ADJ_INDEX_INVALID);
1177 }
1178
1179 const int
1180 fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
1181                               fib_source_t source,
1182                               dpo_id_t *dpo)
1183 {
1184     fib_entry_t *fib_entry;
1185     fib_entry_src_t *esrc;
1186
1187     if (FIB_NODE_INDEX_INVALID == fib_entry_index)
1188         return (0);
1189
1190     fib_entry = fib_entry_get(fib_entry_index);
1191     esrc = fib_entry_src_find(fib_entry, source, NULL);
1192
1193     if (NULL != esrc)
1194     {
1195         if (FIB_NODE_INDEX_INVALID != esrc->fes_pl)
1196         {
1197             fib_path_list_contribute_forwarding(
1198                 esrc->fes_pl,
1199                 fib_entry_get_default_chain_type(fib_entry),
1200                 dpo);
1201
1202             return (dpo_id_is_valid(dpo));
1203         }
1204     }
1205     return (0);
1206 }
1207
1208 fib_entry_flag_t
1209 fib_entry_get_flags_i (const fib_entry_t *fib_entry)
1210 {
1211     fib_entry_flag_t flags;
1212
1213     /*
1214      * the vector of sources is deliberately arranged in priority order
1215      */
1216     if (0 == vec_len(fib_entry->fe_srcs))
1217     {
1218         flags = FIB_ENTRY_FLAG_NONE;
1219     }
1220     else
1221     {
1222         fib_entry_src_t *esrc;
1223
1224         esrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
1225         flags = esrc->fes_entry_flags;
1226     }
1227
1228     return (flags);
1229 }
1230
1231 void
1232 fib_entry_set_source_data (fib_node_index_t fib_entry_index,
1233                            fib_source_t source,
1234                            const void *data)
1235 {
1236     fib_entry_t *fib_entry;
1237     fib_entry_src_t *esrc;
1238
1239     fib_entry = fib_entry_get(fib_entry_index);
1240     esrc = fib_entry_src_find(fib_entry, source, NULL);
1241
1242     if (NULL != esrc &&
1243         NULL != fib_entry_src_vft[source].fesv_set_data)
1244     {
1245         fib_entry_src_vft[source].fesv_set_data(esrc, fib_entry, data);
1246     }
1247 }
1248
1249 const void*
1250 fib_entry_get_source_data (fib_node_index_t fib_entry_index,
1251                            fib_source_t source)
1252 {
1253     fib_entry_t *fib_entry;
1254     fib_entry_src_t *esrc;
1255
1256     fib_entry = fib_entry_get(fib_entry_index);
1257     esrc = fib_entry_src_find(fib_entry, source, NULL);
1258
1259     if (NULL != esrc &&
1260         NULL != fib_entry_src_vft[source].fesv_get_data)
1261     {
1262         return (fib_entry_src_vft[source].fesv_get_data(esrc, fib_entry));
1263     }
1264     return (NULL);
1265 }
1266
1267 void
1268 fib_entry_src_module_init (void)
1269 {
1270     fib_entry_src_rr_register();
1271     fib_entry_src_interface_register();
1272     fib_entry_src_default_route_register();
1273     fib_entry_src_special_register();
1274     fib_entry_src_api_register();
1275     fib_entry_src_adj_register();
1276     fib_entry_src_mpls_register();
1277     fib_entry_src_lisp_register();
1278 }