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