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