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