src/vnet/fib/fib_path_list.c

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