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