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