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