src/vnet/fib/fib_path_list.c

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