src/vnet/fib/fib_path_list.c

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