src/vnet/fib/fib_path_list.c

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