src/vnet/fib/fib_path_list.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 <vppinfra/mhash.h>
  17 #include <vnet/ip/ip.h>
  18 #include <vnet/adj/adj.h>
  19 #include <vnet/dpo/load_balance.h>
  20 #include <vnet/dpo/load_balance_map.h>
  21
  22 #include <vnet/fib/fib_path_list.h>
  23 #include <vnet/fib/fib_internal.h>
  24 #include <vnet/fib/fib_node_list.h>
  25 #include <vnet/fib/fib_walk.h>
  26 #include <vnet/fib/fib_urpf_list.h>
  27 #include <vnet/fib/fib_path_ext.h>
  28
  29 /**
  30  * The magic number of child entries that make a path-list popular.
  31  * There's a trade-off here between convergnece and forwarding speed.
  32  * Popular path-lists generate load-balance maps for the entries that
  33  * use them. If the map is present there is a switch path cost to indirect
  34  * through the map - this indirection provides the fast convergence - so
  35  * without the map convergence is slower.
  36  */
  37 #define FIB_PATH_LIST_POPULAR 64
  38
  39 /**
  40  * FIB path-list
  41  * A representation of the list/set of path trough which a prefix is reachable
  42  */
  43 typedef struct fib_path_list_t_ {
  44     /**
  45      * A path-list is a node in the FIB graph.
  46      */
  47     fib_node_t fpl_node;
  48
  49     /**
  50      * Flags on the path-list
  51      */
  52     fib_path_list_flags_t fpl_flags;
  53
  54     /**
  55      * Vector of paths indicies for all configured paths.
  56      * For shareable path-lists this list MUST not change.
  57      */
  58     fib_node_index_t *fpl_paths;
  59
  60     /**
  61      * the RPF list calculated for this path list
  62      */
  63     fib_node_index_t fpl_urpf;
  64
  65     /**
  66      * Hash table of paths. valid only with INDEXED flag
  67      */
  68     uword *fpl_db;
  69 } fib_path_list_t;
  70
  71 /*
  72  * Array of strings/names for the FIB sources
  73  */
  74 static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
  75
  76 /*
  77  * The memory pool from which we allocate all the path-lists
  78  */
  79 static fib_path_list_t * fib_path_list_pool;
  80
  81 /*
  82  * The data-base of shared path-lists
  83  */
  84 static uword *fib_path_list_db;
  85
  86 /**
  87  * the logger
  88  */
  89 vlib_log_class_t fib_path_list_logger;
  90
  91 /*
  92  * Debug macro
  93  */
  94 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)                  \
  95 {                                                               \
  96     vlib_log_debug(fib_path_list_logger,                        \
  97                    "[%U]:" _fmt,                                \
  98                    format_fib_path_list,                        \
  99                    fib_path_list_get_index(_pl), 0,             \
 100                    ##_args);                                    \
 101 }
 102
 103 static fib_path_list_t *
 104 fib_path_list_get (fib_node_index_t index)
 105 {
 106     return (pool_elt_at_index(fib_path_list_pool, index));
 107 }
 108
 109 static fib_node_t *
 110 fib_path_list_get_node (fib_node_index_t index)
 111 {
 112     return ((fib_node_t*)fib_path_list_get(index));
 113 }
 114
 115 static fib_path_list_t*
 116 fib_path_list_from_fib_node (fib_node_t *node)
 117 {
 118     ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
 119     return ((fib_path_list_t*)node);
 120 }
 121
 122 static fib_node_index_t
 123 fib_path_list_get_index (fib_path_list_t *path_list)
 124 {
 125     return (path_list - fib_path_list_pool);
 126 }
 127
 128 u8 *
 129 format_fib_path_list (u8 * s, va_list * args)
 130 {
 131     fib_node_index_t *path_index, path_list_index;
 132     fib_path_list_attribute_t attr;
 133     fib_path_list_t *path_list;
 134     u32 indent;
 135
 136     path_list_index = va_arg (*args, fib_node_index_t);
 137     indent = va_arg (*args, u32);
 138     path_list = fib_path_list_get(path_list_index);
 139
 140     s = format (s, "%Upath-list:[%d]",
 141                 format_white_space, indent,
 142                 fib_path_list_get_index(path_list));
 143     s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
 144
 145     if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
 146     {
 147         s = format (s, " flags:");
 148         FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
 149         {
 150             if ((1<<attr) & path_list->fpl_flags)
 151             {
 152                 s = format (s, "%s,", fib_path_list_attr_names[attr]);
 153             }
 154         }
 155     }
 156     s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
 157
 158     vec_foreach (path_index, path_list->fpl_paths)
 159     {
 160         s = format(s, "%U", format_fib_path, *path_index, indent+2,
 161                    FIB_PATH_FORMAT_FLAGS_NONE);
 162         s = format(s, "\n");
 163     }
 164
 165     return (s);
 166 }
 167
 168 u8 *
 169 fib_path_list_format (fib_node_index_t path_list_index,
 170                       u8 * s)
 171 {
 172     return (format(s, "%U", format_fib_path_list, path_list_index, 4));
 173 }
 174
 175 static uword
 176 fib_path_list_hash (fib_path_list_t *path_list)
 177 {
 178     uword old_path_list_hash, new_path_list_hash, path_hash;
 179     fib_node_index_t *path_index;
 180
 181     ASSERT(path_list);
 182
 183     new_path_list_hash =
 184         old_path_list_hash =
 185             (vec_len(path_list->fpl_paths) << 16 |
 186              (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS));
 187
 188     vec_foreach (path_index, path_list->fpl_paths)
 189     {
 190         path_hash = fib_path_hash(*path_index);
 191 #if uword_bits == 64
 192         hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
 193 #else
 194         hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
 195 #endif
 196     }
 197
 198     return (new_path_list_hash);
 199 }
 200
 201 always_inline uword
 202 fib_path_list_db_hash_key_from_index (uword index)
 203 {
 204     return 1 + 2*index;
 205 }
 206
 207 always_inline uword
 208 fib_path_list_db_hash_key_is_index (uword key)
 209 {
 210     return key & 1;
 211 }
 212
 213 always_inline uword
 214 fib_path_list_db_hash_key_2_index (uword key)
 215 {
 216     ASSERT (fib_path_list_db_hash_key_is_index (key));
 217     return key / 2;
 218 }
 219
 220 static fib_path_list_t*
 221 fib_path_list_db_get_from_hash_key (uword key)
 222 {
 223     fib_path_list_t *path_list;
 224
 225     if (fib_path_list_db_hash_key_is_index (key))
 226     {
 227         fib_node_index_t path_list_index;
 228
 229         path_list_index = fib_path_list_db_hash_key_2_index(key);
 230         path_list = fib_path_list_get(path_list_index);
 231     }
 232     else
 233     {
 234         path_list = uword_to_pointer (key, fib_path_list_t *);
 235     }
 236
 237     return (path_list);
 238 }
 239
 240 static uword
 241 fib_path_list_db_hash_key_sum (hash_t * h,
 242                                uword key)
 243 {
 244     fib_path_list_t *path_list;
 245
 246     path_list = fib_path_list_db_get_from_hash_key(key);
 247
 248     return (fib_path_list_hash(path_list));
 249 }
 250
 251 static uword
 252 fib_path_list_db_hash_key_equal (hash_t * h,
 253                                  uword key1,
 254                                  uword key2)
 255 {
 256     fib_path_list_t *path_list1, *path_list2;
 257
 258     path_list1 = fib_path_list_db_get_from_hash_key(key1);
 259     path_list2 = fib_path_list_db_get_from_hash_key(key2);
 260
 261     return (fib_path_list_hash(path_list1) ==
 262             fib_path_list_hash(path_list2));
 263 }
 264
 265 static fib_node_index_t
 266 fib_path_list_db_find (fib_path_list_t *path_list)
 267 {
 268     uword *p;
 269
 270     p = hash_get(fib_path_list_db, path_list);
 271
 272     if (NULL != p)
 273     {
 274         return p[0];
 275     }
 276
 277     return (FIB_NODE_INDEX_INVALID);
 278 }
 279
 280 static void
 281 fib_path_list_db_insert (fib_node_index_t path_list_index)
 282 {
 283     fib_path_list_t *path_list;
 284
 285     path_list = fib_path_list_get(path_list_index);
 286
 287     ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
 288
 289     hash_set (fib_path_list_db,
 290               fib_path_list_db_hash_key_from_index(path_list_index),
 291               path_list_index);
 292
 293     FIB_PATH_LIST_DBG(path_list, "DB-inserted");
 294 }
 295
 296 static void
 297 fib_path_list_db_remove (fib_node_index_t path_list_index)
 298 {
 299     fib_path_list_t *path_list;
 300
 301     path_list = fib_path_list_get(path_list_index);
 302
 303     ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
 304
 305     hash_unset(fib_path_list_db,
 306                fib_path_list_db_hash_key_from_index(path_list_index));
 307
 308     FIB_PATH_LIST_DBG(path_list, "DB-removed");
 309 }
 310
 311 static void
 312 fib_path_list_destroy (fib_path_list_t *path_list)
 313 {
 314     fib_node_index_t *path_index;
 315
 316     FIB_PATH_LIST_DBG(path_list, "destroy");
 317
 318     vec_foreach (path_index, path_list->fpl_paths)
 319     {
 320         fib_path_destroy(*path_index);
 321     }
 322
 323     vec_free(path_list->fpl_paths);
 324     fib_urpf_list_unlock(path_list->fpl_urpf);
 325
 326     fib_node_deinit(&path_list->fpl_node);
 327     pool_put(fib_path_list_pool, path_list);
 328 }
 329
 330 static void
 331 fib_path_list_last_lock_gone (fib_node_t *node)
 332 {
 333     fib_path_list_t *path_list;
 334
 335     path_list = fib_path_list_from_fib_node(node);
 336
 337     FIB_PATH_LIST_DBG(path_list, "last-lock");
 338
 339     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 340     {
 341         fib_path_list_db_remove(fib_path_list_get_index(path_list));
 342     }
 343     fib_path_list_destroy(path_list);
 344 }
 345
 346 static load_balance_flags_t
 347 fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags)
 348 {
 349     load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE;
 350
 351     if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
 352     {
 353         lb_flags |= LOAD_BALANCE_ATTR_STICKY;
 354     }
 355     return (lb_flags);
 356 }
 357
 358 /*
 359  * fib_path_mk_lb
 360  *
 361  * update the multipath adj this path-list will contribute to its
 362  * children's forwarding.
 363  */
 364 static void
 365 fib_path_list_mk_lb (fib_path_list_t *path_list,
 366                      fib_forward_chain_type_t fct,
 367                      dpo_id_t *dpo,
 368                      fib_path_list_fwd_flags_t flags)
 369 {
 370     load_balance_path_t *nhs;
 371     fib_node_index_t *path_index;
 372
 373     nhs = NULL;
 374
 375     /*
 376      * We gather the DPOs from resolved paths.
 377      */
 378     vec_foreach (path_index, path_list->fpl_paths)
 379     {
 380         if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
 381             fib_path_is_resolved(*path_index))
 382         {
 383             nhs = fib_path_append_nh_for_multipath_hash(*path_index,
 384                                                         fct, nhs);
 385         }
 386     }
 387
 388     /*
 389      * Path-list load-balances, which if used, would be shared and hence
 390      * never need a load-balance map.
 391      */
 392     dpo_set(dpo,
 393             DPO_LOAD_BALANCE,
 394             fib_forw_chain_type_to_dpo_proto(fct),
 395             load_balance_create(vec_len(nhs),
 396                                 fib_forw_chain_type_to_dpo_proto(fct),
 397                                 0 /* FIXME FLOW HASH */));
 398     load_balance_multipath_update(dpo, nhs,
 399                                   fib_path_list_fwd_flags_2_load_balance(flags));
 400
 401     FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
 402
 403     vec_free(nhs);
 404 }
 405
 406 /**
 407  * @brief [re]build the path list's uRPF list
 408  */
 409 static void
 410 fib_path_list_mk_urpf (fib_path_list_t *path_list)
 411 {
 412     fib_node_index_t *path_index;
 413
 414     /*
 415      * ditch the old one. by iterating through all paths we are going
 416      * to re-find all the adjs that were in the old one anyway. If we
 417      * keep the old one, then the |sort|uniq requires more work.
 418      * All users of the RPF list have their own lock, so we can release
 419      * immediately.
 420      */
 421     fib_urpf_list_unlock(path_list->fpl_urpf);
 422     path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
 423
 424     vec_foreach (path_index, path_list->fpl_paths)
 425     {
 426         fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
 427     }
 428
 429     fib_urpf_list_bake(path_list->fpl_urpf);
 430 }
 431
 432 /**
 433  * @brief Contribute (add) this path list's uRPF list. This allows the child
 434  * to construct an aggregate list.
 435  */
 436 void
 437 fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
 438                                index_t urpf)
 439 {
 440     fib_path_list_t *path_list;
 441
 442     path_list = fib_path_list_get(path_list_index);
 443
 444     fib_urpf_list_combine(urpf, path_list->fpl_urpf);
 445 }
 446
 447 /**
 448  * @brief Return the the child the RPF list pre-built for this path list
 449  */
 450 index_t
 451 fib_path_list_get_urpf (fib_node_index_t path_list_index)
 452 {
 453     fib_path_list_t *path_list;
 454
 455     path_list = fib_path_list_get(path_list_index);
 456
 457     return (path_list->fpl_urpf);
 458 }
 459
 460 /*
 461  * fib_path_list_back_walk
 462  *
 463  * Called from one of this path-list's paths to progate
 464  * a back walk
 465  */
 466 void
 467 fib_path_list_back_walk (fib_node_index_t path_list_index,
 468                          fib_node_back_walk_ctx_t *ctx)
 469 {
 470     fib_path_list_t *path_list;
 471
 472     path_list = fib_path_list_get(path_list_index);
 473
 474     fib_path_list_mk_urpf(path_list);
 475
 476     FIB_PATH_LIST_DBG(path_list, "bw:%U",
 477                       format_fib_node_bw_reason, ctx->fnbw_reason);
 478
 479     /*
 480      * propagate the backwalk further
 481      */
 482     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
 483     {
 484         /*
 485          * many children. schedule a async walk
 486          */
 487         fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
 488                        path_list_index,
 489                        FIB_WALK_PRIORITY_LOW,
 490                        ctx);
 491     }
 492     else
 493     {
 494         /*
 495          * only a few children. continue the walk synchronously
 496          */
 497         fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
 498     }
 499 }
 500
 501 /*
 502  * fib_path_list_back_walk_notify
 503  *
 504  * A back walk has reach this path-list.
 505  */
 506 static fib_node_back_walk_rc_t
 507 fib_path_list_back_walk_notify (fib_node_t *node,
 508                                 fib_node_back_walk_ctx_t *ctx)
 509 {
 510     /*
 511      * the path-list is not a direct child of any other node type
 512      * paths, which do not change thier to-list-mapping, save the
 513      * list they are a member of, and invoke the BW function directly.
 514      */
 515     ASSERT(0);
 516
 517     return (FIB_NODE_BACK_WALK_CONTINUE);
 518 }
 519
 520 /*
 521  * Display the path-list memory usage
 522  */
 523 static void
 524 fib_path_list_memory_show (void)
 525 {
 526     fib_show_memory_usage("Path-list",
 527                           pool_elts(fib_path_list_pool),
 528                           pool_len(fib_path_list_pool),
 529                           sizeof(fib_path_list_t));
 530     fib_urpf_list_show_mem();
 531 }
 532
 533 /*
 534  * The FIB path-list's graph node virtual function table
 535  */
 536 static const fib_node_vft_t fib_path_list_vft = {
 537     .fnv_get = fib_path_list_get_node,
 538     .fnv_last_lock = fib_path_list_last_lock_gone,
 539     .fnv_back_walk = fib_path_list_back_walk_notify,
 540     .fnv_mem_show = fib_path_list_memory_show,
 541 };
 542
 543 static inline fib_path_list_t *
 544 fib_path_list_alloc (fib_node_index_t *path_list_index)
 545 {
 546     fib_path_list_t *path_list;
 547
 548     pool_get(fib_path_list_pool, path_list);
 549     clib_memset(path_list, 0, sizeof(*path_list));
 550
 551     fib_node_init(&path_list->fpl_node,
 552                   FIB_NODE_TYPE_PATH_LIST);
 553     path_list->fpl_urpf = INDEX_INVALID;
 554     path_list->fpl_paths = NULL;
 555
 556     *path_list_index = fib_path_list_get_index(path_list);
 557
 558     FIB_PATH_LIST_DBG(path_list, "alloc");
 559
 560     return (path_list);
 561 }
 562
 563 static fib_path_list_t *
 564 fib_path_list_resolve (fib_path_list_t *path_list)
 565 {
 566     fib_node_index_t *path_index, *paths, path_list_index;
 567
 568     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
 569
 570     /*
 571      * resolving a path-list is a recursive action. this means more path
 572      * lists can be created during this call, and hence this path-list
 573      * can be realloc'd. so we work with copies.
 574      * this function is called only once per-path list, so its no great overhead.
 575      */
 576     path_list_index = fib_path_list_get_index(path_list);
 577     paths = vec_dup(path_list->fpl_paths);
 578
 579     vec_foreach (path_index, paths)
 580     {
 581         fib_path_resolve(*path_index);
 582     }
 583
 584     vec_free(paths);
 585     path_list = fib_path_list_get(path_list_index);
 586
 587     FIB_PATH_LIST_DBG(path_list, "resovled");
 588
 589     if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
 590     {
 591         fib_path_list_mk_urpf(path_list);
 592     }
 593     return (path_list);
 594 }
 595
 596 u32
 597 fib_path_list_get_n_paths (fib_node_index_t path_list_index)
 598 {
 599     fib_path_list_t *path_list;
 600
 601     if (FIB_NODE_INDEX_INVALID == path_list_index)
 602     {
 603         return (0);
 604     }
 605
 606     path_list = fib_path_list_get(path_list_index);
 607
 608     return (vec_len(path_list->fpl_paths));
 609 }
 610
 611
 612 u32
 613 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
 614 {
 615     fib_node_index_t *path_index;
 616     fib_path_list_t *path_list;
 617     u32 sw_if_index;
 618
 619     path_list = fib_path_list_get(path_list_index);
 620
 621     sw_if_index = ~0;
 622     vec_foreach (path_index, path_list->fpl_paths)
 623     {
 624         sw_if_index = fib_path_get_resolving_interface(*path_index);
 625         if (~0 != sw_if_index)
 626         {
 627             return (sw_if_index);
 628         }
 629     }
 630
 631     return (sw_if_index);
 632 }
 633
 634 dpo_proto_t
 635 fib_path_list_get_proto (fib_node_index_t path_list_index)
 636 {
 637     fib_path_list_t *path_list;
 638
 639     path_list = fib_path_list_get(path_list_index);
 640
 641     /*
 642      * we don't support a mix of path protocols, so we can return the proto
 643      * of the first
 644      */
 645     return (fib_path_get_proto(path_list->fpl_paths[0]));
 646 }
 647
 648 int
 649 fib_path_list_is_looped (fib_node_index_t path_list_index)
 650 {
 651     fib_path_list_t *path_list;
 652
 653     path_list = fib_path_list_get(path_list_index);
 654
 655     return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
 656 }
 657
 658 int
 659 fib_path_list_is_popular (fib_node_index_t path_list_index)
 660 {
 661     fib_path_list_t *path_list;
 662
 663     path_list = fib_path_list_get(path_list_index);
 664
 665     return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
 666 }
 667
 668 static fib_path_list_flags_t
 669 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
 670 {
 671     /*
 672      * we do no share drop nor exclusive path-lists
 673      */
 674     if (flags & FIB_PATH_LIST_FLAG_DROP ||
 675         flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
 676     {
 677         flags &= ~FIB_PATH_LIST_FLAG_SHARED;
 678     }
 679
 680     return (flags);
 681 }
 682
 683 fib_node_index_t
 684 fib_path_list_create (fib_path_list_flags_t flags,
 685                       const fib_route_path_t *rpaths)
 686 {
 687     fib_node_index_t path_list_index, old_path_list_index;
 688     fib_path_list_t *path_list;
 689     int i;
 690
 691     flags = fib_path_list_flags_fixup(flags);
 692     path_list = fib_path_list_alloc(&path_list_index);
 693     path_list->fpl_flags = flags;
 694
 695     if (NULL != rpaths)
 696     {
 697         vec_foreach_index(i, rpaths)
 698         {
 699             vec_add1(path_list->fpl_paths,
 700                      fib_path_create(path_list_index,
 701                                      &rpaths[i]));
 702         }
 703         /*
 704          * we sort the paths since the key for the path-list is
 705          * the description of the paths it contains. The paths need to
 706          * be sorted else this description will differ.
 707          */
 708         if (vec_len(path_list->fpl_paths) > 1)
 709         {
 710             vec_sort_with_function(path_list->fpl_paths,
 711                                    fib_path_cmp_for_sort);
 712         }
 713     }
 714
 715     /*
 716      * If a shared path list is requested, consult the DB for a match
 717      */
 718     if (flags & FIB_PATH_LIST_FLAG_SHARED)
 719     {
 720         /*
 721          * check for a matching path-list in the DB.
 722          * If we find one then we can return the existing one and destroy the
 723          * new one just created.
 724          */
 725         old_path_list_index = fib_path_list_db_find(path_list);
 726         if (FIB_NODE_INDEX_INVALID != old_path_list_index)
 727         {
 728             fib_path_list_destroy(path_list);
 729
 730             path_list_index = old_path_list_index;
 731         }
 732         else
 733         {
 734             /*
 735              * if there was not a matching path-list, then this
 736              * new one will need inserting into the DB and resolving.
 737              */
 738             fib_path_list_db_insert(path_list_index);
 739             path_list = fib_path_list_resolve(path_list);
 740         }
 741     }
 742     else
 743     {
 744         /*
 745          * no shared path list requested. resolve and use the one
 746          * just created.
 747          */
 748         path_list = fib_path_list_resolve(path_list);
 749     }
 750
 751     return (path_list_index);
 752 }
 753
 754 static fib_path_cfg_flags_t
 755 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
 756 {
 757     fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
 758
 759     if (plf & FIB_PATH_LIST_FLAG_DROP)
 760     {
 761         pf |= FIB_PATH_CFG_FLAG_DROP;
 762     }
 763     if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
 764     {
 765         pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
 766     }
 767     if (plf & FIB_PATH_LIST_FLAG_LOCAL)
 768     {
 769         pf |= FIB_PATH_CFG_FLAG_LOCAL;
 770     }
 771
 772     return (pf);
 773 }
 774
 775 fib_node_index_t
 776 fib_path_list_create_special (dpo_proto_t nh_proto,
 777                               fib_path_list_flags_t flags,
 778                               const dpo_id_t *dpo)
 779 {
 780     fib_node_index_t path_index, path_list_index;
 781     fib_path_list_t *path_list;
 782
 783     path_list = fib_path_list_alloc(&path_list_index);
 784     path_list->fpl_flags = flags;
 785
 786     path_index =
 787         fib_path_create_special(path_list_index,
 788                                 nh_proto,
 789                                 fib_path_list_flags_2_path_flags(flags),
 790                                 dpo);
 791     vec_add1(path_list->fpl_paths, path_index);
 792
 793     /*
 794      * we don't share path-lists. we can do PIC on them so why bother.
 795      */
 796     path_list = fib_path_list_resolve(path_list);
 797
 798     return (path_list_index);
 799 }
 800
 801 /*
 802  * return the index info the path-lists's vector of paths, of the matching path.
 803  * ~0 if not found
 804  */
 805 u32
 806 fib_path_list_find_rpath (fib_node_index_t path_list_index,
 807                           const fib_route_path_t *rpath)
 808 {
 809     fib_path_list_t *path_list;
 810     u32 ii;
 811
 812     path_list = fib_path_list_get(path_list_index);
 813
 814     vec_foreach_index (ii, path_list->fpl_paths)
 815     {
 816         if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
 817         {
 818             return (ii);
 819         }
 820     }
 821     return (~0);
 822 }
 823
 824
 825 /*
 826  * fib_path_list_copy_and_path_add
 827  *
 828  * Create a copy of a path-list and append one more path to it.
 829  * The path-list returned could either have been newly created, or
 830  * can be a shared path-list from the data-base.
 831  */
 832 fib_node_index_t
 833 fib_path_list_path_add (fib_node_index_t path_list_index,
 834                         const fib_route_path_t *rpaths)
 835 {
 836     fib_node_index_t new_path_index, *orig_path_index;
 837     fib_path_list_t *path_list;
 838
 839     /*
 840      * alloc the new list before we retrieve the old one, lest
 841      * the alloc result in a realloc
 842      */
 843     path_list = fib_path_list_get(path_list_index);
 844
 845     ASSERT(1 == vec_len(rpaths));
 846     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
 847
 848     FIB_PATH_LIST_DBG(path_list, "path-add");
 849
 850     new_path_index = fib_path_create(path_list_index,
 851                                      rpaths);
 852
 853     vec_foreach (orig_path_index, path_list->fpl_paths)
 854     {
 855         /*
 856          * don't add duplicate paths
 857          */
 858         if (0 == fib_path_cmp(new_path_index, *orig_path_index))
 859         {
 860             fib_path_destroy(new_path_index);
 861             return (*orig_path_index);
 862         }
 863     }
 864
 865     /*
 866      * Add the new path - no sort, no sharing, no key..
 867      */
 868     vec_add1(path_list->fpl_paths, new_path_index);
 869
 870     FIB_PATH_LIST_DBG(path_list, "path-added");
 871
 872     /*
 873      * no shared path list requested. resolve and use the one
 874      * just created.
 875      */
 876     fib_path_resolve(new_path_index);
 877
 878     return (new_path_index);
 879 }
 880
 881 fib_node_index_t
 882 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
 883                                  fib_path_list_flags_t flags,
 884                                  const fib_route_path_t *rpaths)
 885 {
 886     fib_node_index_t path_index, new_path_index, *orig_path_index;
 887     fib_path_list_t *path_list, *orig_path_list;
 888     fib_node_index_t exist_path_list_index;
 889     fib_node_index_t path_list_index;
 890     fib_node_index_t pi;
 891
 892     ASSERT(1 == vec_len(rpaths));
 893
 894     /*
 895      * alloc the new list before we retrieve the old one, lest
 896      * the alloc result in a realloc
 897      */
 898     path_list = fib_path_list_alloc(&path_list_index);
 899
 900     orig_path_list = fib_path_list_get(orig_path_list_index);
 901
 902     FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
 903
 904     flags = fib_path_list_flags_fixup(flags);
 905     path_list->fpl_flags = flags;
 906
 907     vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
 908     pi = 0;
 909
 910     new_path_index = fib_path_create(path_list_index,
 911                                      rpaths);
 912
 913     vec_foreach (orig_path_index, orig_path_list->fpl_paths)
 914     {
 915         /*
 916          * don't add duplicate paths
 917          * In the unlikely event the path is a duplicate, then we'll
 918          * find a matching path-list later and this one will be toast.
 919          */
 920         if (0 != fib_path_cmp(new_path_index, *orig_path_index))
 921         {
 922             path_index = fib_path_copy(*orig_path_index, path_list_index);
 923             path_list->fpl_paths[pi++] = path_index;
 924         }
 925         else
 926         {
 927             _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
 928         }
 929     }
 930
 931     path_list->fpl_paths[pi] = new_path_index;
 932
 933     /*
 934      * we sort the paths since the key for the path-list is
 935      * the description of the paths it contains. The paths need to
 936      * be sorted else this description will differ.
 937      */
 938     vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
 939
 940     FIB_PATH_LIST_DBG(path_list, "path-added");
 941
 942     /*
 943      * check for a matching path-list in the DB.
 944      * If we find one then we can return the existing one and destroy the
 945      * new one just created.
 946      */
 947     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 948     {
 949         exist_path_list_index = fib_path_list_db_find(path_list);
 950         if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
 951         {
 952             fib_path_list_destroy(path_list);
 953
 954             path_list_index = exist_path_list_index;
 955         }
 956         else
 957         {
 958             /*
 959              * if there was not a matching path-list, then this
 960              * new one will need inserting into the DB and resolving.
 961              */
 962             fib_path_list_db_insert(path_list_index);
 963
 964             path_list = fib_path_list_resolve(path_list);
 965         }
 966     }
 967     else
 968     {
 969         /*
 970          * no shared path list requested. resolve and use the one
 971          * just created.
 972          */
 973         path_list = fib_path_list_resolve(path_list);
 974     }
 975
 976     return (path_list_index);
 977 }
 978
 979 /*
 980  * fib_path_list_path_remove
 981  */
 982 fib_node_index_t
 983 fib_path_list_path_remove (fib_node_index_t path_list_index,
 984                            const fib_route_path_t *rpaths)
 985 {
 986     fib_node_index_t match_path_index, tmp_path_index;
 987     fib_path_list_t *path_list;
 988     fib_node_index_t pi;
 989
 990     path_list = fib_path_list_get(path_list_index);
 991
 992     ASSERT(1 == vec_len(rpaths));
 993     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
 994
 995     FIB_PATH_LIST_DBG(path_list, "path-remove");
 996
 997     /*
 998      * create a representation of the path to be removed, so it
 999      * can be used as a comparison object during the copy.
1000      */
1001     tmp_path_index = fib_path_create(path_list_index,
1002                                      rpaths);
1003     match_path_index = FIB_NODE_INDEX_INVALID;
1004
1005     vec_foreach_index (pi, path_list->fpl_paths)
1006     {
1007         if (0 == fib_path_cmp(tmp_path_index,
1008                               path_list->fpl_paths[pi]))
1009         {
1010             /*
1011              * match - remove it
1012              */
1013             match_path_index = path_list->fpl_paths[pi];
1014             fib_path_destroy(match_path_index);
1015             vec_del1(path_list->fpl_paths, pi);
1016         }
1017     }
1018
1019     /*
1020      * done with the temporary now
1021      */
1022     fib_path_destroy(tmp_path_index);
1023
1024     return (match_path_index);
1025 }
1026
1027 /*
1028  * fib_path_list_copy_and_path_remove
1029  *
1030  * Copy the path-list excluding the path passed.
1031  * If the path is the last one, then the index reurned will be invalid.
1032  * i.e. the path-list is toast.
1033  */
1034 fib_node_index_t
1035 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1036                                     fib_path_list_flags_t flags,
1037                                     const fib_route_path_t *rpath)
1038 {
1039     fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1040     fib_path_list_t *path_list,  *orig_path_list;
1041     fib_node_index_t pi;
1042
1043     path_list = fib_path_list_alloc(&path_list_index);
1044
1045     flags = fib_path_list_flags_fixup(flags);
1046     orig_path_list = fib_path_list_get(orig_path_list_index);
1047
1048     FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1049
1050     path_list->fpl_flags = flags;
1051     /*
1052      * allocate as many paths as we might need in one go, rather than
1053      * using vec_add to do a few at a time.
1054      */
1055     if (vec_len(orig_path_list->fpl_paths) > 1)
1056     {
1057         vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1058     }
1059     pi = 0;
1060
1061     /*
1062      * create a representation of the path to be removed, so it
1063      * can be used as a comparison object during the copy.
1064      */
1065     tmp_path_index = fib_path_create(path_list_index, rpath);
1066
1067     vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1068     {
1069         if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1070             path_index = fib_path_copy(*orig_path_index, path_list_index);
1071             if (pi < vec_len(path_list->fpl_paths))
1072             {
1073                 path_list->fpl_paths[pi++] = path_index;
1074             }
1075             else
1076             {
1077                 /*
1078                  * this is the unlikely case that the path being
1079                  * removed does not match one in the path-list, so
1080                  * we end up with as many paths as we started with.
1081                  * the paths vector was sized above with the expectation
1082                  * that we would have 1 less.
1083                  */
1084                 vec_add1(path_list->fpl_paths, path_index);
1085             }
1086         }
1087     }
1088
1089     /*
1090      * done with the temporary now
1091      */
1092     fib_path_destroy(tmp_path_index);
1093
1094     /*
1095      * if there are no paths, then the new path-list is aborted
1096      */
1097     if (0 == vec_len(path_list->fpl_paths)) {
1098         FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1099
1100         fib_path_list_destroy(path_list);
1101
1102         path_list_index = FIB_NODE_INDEX_INVALID;
1103     } else {
1104         /*
1105          * we sort the paths since the key for the path-list is
1106          * the description of the paths it contains. The paths need to
1107          * be sorted else this description will differ.
1108          */
1109         vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1110
1111         /*
1112          * If a shared path list is requested, consult the DB for a match
1113          */
1114         if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1115         {
1116             fib_node_index_t exist_path_list_index;
1117
1118             /*
1119              * check for a matching path-list in the DB.
1120              * If we find one then we can return the existing one and destroy the
1121              * new one just created.
1122              */
1123             exist_path_list_index = fib_path_list_db_find(path_list);
1124             if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1125             {
1126                 fib_path_list_destroy(path_list);
1127
1128                 path_list_index = exist_path_list_index;
1129             }
1130             else
1131             {
1132                 /*
1133                  * if there was not a matching path-list, then this
1134                  * new one will need inserting into the DB and resolving.
1135                  */
1136                 fib_path_list_db_insert(path_list_index);
1137
1138                 path_list = fib_path_list_resolve(path_list);
1139             }
1140         }
1141         else
1142         {
1143             /*
1144              * no shared path list requested. resolve and use the one
1145              * just created.
1146              */
1147             path_list = fib_path_list_resolve(path_list);
1148         }
1149     }
1150
1151     return (path_list_index);
1152 }
1153
1154 /*
1155  * fib_path_list_contribute_forwarding
1156  *
1157  * Return the index of a load-balance that user of this path-list should
1158  * use for forwarding
1159  */
1160 void
1161 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1162                                      fib_forward_chain_type_t fct,
1163                                      fib_path_list_fwd_flags_t flags,
1164                                      dpo_id_t *dpo)
1165 {
1166     fib_path_list_t *path_list;
1167
1168     path_list = fib_path_list_get(path_list_index);
1169
1170     fib_path_list_mk_lb(path_list, fct, dpo, flags);
1171
1172     ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1173
1174     /*
1175      * If there's only one bucket in the load-balance then we can
1176      * squash it out.
1177      */
1178     if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1179         (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1180     {
1181         dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1182     }
1183 }
1184
1185 /*
1186  * fib_path_list_get_adj
1187  *
1188  * Return the index of a adjacency for the first path that user of this
1189  * path-list should use for forwarding
1190  */
1191 adj_index_t
1192 fib_path_list_get_adj (fib_node_index_t path_list_index,
1193                        fib_forward_chain_type_t type)
1194 {
1195     fib_path_list_t *path_list;
1196
1197     path_list = fib_path_list_get(path_list_index);
1198     return (fib_path_get_adj(path_list->fpl_paths[0]));
1199 }
1200
1201 int
1202 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1203                                      fib_node_index_t **entry_indicies)
1204 {
1205     fib_node_index_t *path_index;
1206     int is_looped, list_looped;
1207     fib_path_list_t *path_list;
1208
1209     list_looped = 0;
1210     path_list = fib_path_list_get(path_list_index);
1211
1212     vec_foreach (path_index, path_list->fpl_paths)
1213     {
1214         fib_node_index_t *copy, **copy_ptr;
1215
1216         /*
1217          * we need a copy of the nodes visited so that when we add entries
1218          * we explore on the nth path and a looped is detected, those entries
1219          * are not again searched for n+1 path and so finding a loop that does
1220          * not exist.
1221          */
1222         copy = vec_dup(*entry_indicies);
1223         copy_ptr = &copy;
1224
1225         is_looped  = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1226         list_looped += is_looped;
1227
1228         vec_free(copy);
1229     }
1230
1231     FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1232
1233     if (list_looped)
1234     {
1235         path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1236     }
1237     else
1238     {
1239         path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1240     }
1241
1242     return (list_looped);
1243 }
1244
1245 u32
1246 fib_path_list_child_add (fib_node_index_t path_list_index,
1247                          fib_node_type_t child_type,
1248                          fib_node_index_t child_index)
1249 {
1250     u32 sibling;
1251
1252     sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1253                                  path_list_index,
1254                                  child_type,
1255                                  child_index);
1256
1257     if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1258                                                          path_list_index))
1259     {
1260         /*
1261          * Set the popular flag on the path-list once we pass the magic
1262          * threshold. then walk children to update.
1263          * We don't undo this action. The rational being that the number
1264          * of entries using this prefix is large enough such that it is a
1265          * non-trival amount of effort to converge them. If we get into the
1266          * situation where we are adding and removing entries such that we
1267          * flip-flop over the threshold, then this non-trivial work is added
1268          * to each of those routes adds/deletes - not a situation we want.
1269          */
1270         fib_node_back_walk_ctx_t ctx = {
1271             .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1272         };
1273         fib_path_list_t *path_list;
1274
1275         path_list = fib_path_list_get(path_list_index);
1276         path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1277
1278         fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1279     }
1280
1281     return (sibling);
1282 }
1283
1284 void
1285 fib_path_list_child_remove (fib_node_index_t path_list_index,
1286                             u32 si)
1287 {
1288     fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1289                           path_list_index,
1290                           si);
1291 }
1292
1293 void
1294 fib_path_list_lock(fib_node_index_t path_list_index)
1295 {
1296     fib_path_list_t *path_list;
1297
1298     if (FIB_NODE_INDEX_INVALID != path_list_index)
1299     {
1300         path_list = fib_path_list_get(path_list_index);
1301
1302         fib_node_lock(&path_list->fpl_node);
1303     }
1304 }
1305
1306 void
1307 fib_path_list_unlock (fib_node_index_t path_list_index)
1308 {
1309     fib_path_list_t *path_list;
1310
1311     if (FIB_NODE_INDEX_INVALID != path_list_index)
1312     {
1313         path_list = fib_path_list_get(path_list_index);
1314
1315         fib_node_unlock(&path_list->fpl_node);
1316     }
1317 }
1318
1319 u32
1320 fib_path_list_pool_size (void)
1321 {
1322     return (pool_elts(fib_path_list_pool));
1323 }
1324
1325 u32
1326 fib_path_list_db_size (void)
1327 {
1328     return (hash_elts(fib_path_list_db));
1329 }
1330
1331 void
1332 fib_path_list_walk (fib_node_index_t path_list_index,
1333                     fib_path_list_walk_fn_t func,
1334                     void *ctx)
1335 {
1336     fib_node_index_t *path_index;
1337     fib_path_list_t *path_list;
1338
1339     path_list = fib_path_list_get(path_list_index);
1340
1341     vec_foreach(path_index, path_list->fpl_paths)
1342     {
1343         if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1344                                             *path_index,
1345                                             ctx))
1346             break;
1347     }
1348 }
1349
1350 void
1351 fib_path_list_walk_w_ext (fib_node_index_t path_list_index,
1352                           const fib_path_ext_list_t *ext_list,
1353                           fib_path_list_walk_w_ext_fn_t func,
1354                           void *ctx)
1355 {
1356     fib_node_index_t *path_index;
1357     fib_path_list_t *path_list;
1358     fib_path_ext_t *path_ext;
1359
1360     path_list = fib_path_list_get(path_list_index);
1361
1362     vec_foreach(path_index, path_list->fpl_paths)
1363     {
1364         path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1365
1366         if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1367                                             *path_index,
1368                                             path_ext,
1369                                             ctx))
1370             break;
1371     }
1372 }
1373
1374 void
1375 fib_path_list_module_init (void)
1376 {
1377     fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1378
1379     fib_path_list_db = hash_create2 (/* elts */ 0,
1380                                      /* user */ 0,
1381                                      /* value_bytes */ sizeof (fib_node_index_t),
1382                                      fib_path_list_db_hash_key_sum,
1383                                      fib_path_list_db_hash_key_equal,
1384                                      /* format pair/arg */
1385                                      0, 0);
1386     fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1387 }
1388
1389 static clib_error_t *
1390 show_fib_path_list_command (vlib_main_t * vm,
1391                             unformat_input_t * input,
1392                             vlib_cli_command_t * cmd)
1393 {
1394     fib_path_list_t *path_list;
1395     fib_node_index_t pli;
1396
1397     if (unformat (input, "%d", &pli))
1398     {
1399         /*
1400          * show one in detail
1401          */
1402         if (!pool_is_free_index(fib_path_list_pool, pli))
1403         {
1404             path_list = fib_path_list_get(pli);
1405             u8 *s = fib_path_list_format(pli, NULL);
1406             s = format(s, "children:");
1407             s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1408             vlib_cli_output (vm, "%s", s);
1409             vec_free(s);
1410         }
1411         else
1412         {
1413             vlib_cli_output (vm, "path list %d invalid", pli);
1414         }
1415     }
1416     else
1417     {
1418         /*
1419          * show all
1420          */
1421         vlib_cli_output (vm, "FIB Path Lists");
1422         pool_foreach_index (pli, fib_path_list_pool,
1423         ({
1424             vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1425         }));
1426     }
1427     return (NULL);
1428 }
1429
1430 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1431   .path = "show fib path-lists",
1432   .function = show_fib_path_list_command,
1433   .short_help = "show fib path-lists",
1434 };