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_set_len(path_list->fpl_paths, vec_len(path_list->fpl_paths) - 1);
 968             fib_path_destroy(new_path_index);
 969         }
 970         else
 971         {
 972             path_list->fpl_paths[pi++] = new_path_index;
 973         }
 974     }
 975
 976     /*
 977      * we sort the paths since the key for the path-list is
 978      * the description of the paths it contains. The paths need to
 979      * be sorted else this description will differ.
 980      */
 981     vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
 982
 983     FIB_PATH_LIST_DBG(path_list, "path-added");
 984
 985     /*
 986      * check for a matching path-list in the DB.
 987      * If we find one then we can return the existing one and destroy the
 988      * new one just created.
 989      */
 990     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 991     {
 992         exist_path_list_index = fib_path_list_db_find(path_list);
 993         if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
 994         {
 995             fib_path_list_destroy(path_list);
 996
 997             path_list_index = exist_path_list_index;
 998         }
 999         else
1000         {
1001             /*
1002              * if there was not a matching path-list, then this
1003              * new one will need inserting into the DB and resolving.
1004              */
1005             fib_path_list_db_insert(path_list_index);
1006
1007             path_list = fib_path_list_resolve(path_list);
1008         }
1009     }
1010     else
1011     {
1012         /*
1013          * no shared path list requested. resolve and use the one
1014          * just created.
1015          */
1016         path_list = fib_path_list_resolve(path_list);
1017     }
1018
1019     return (path_list_index);
1020 }
1021
1022 /*
1023  * fib_path_list_paths_remove
1024  */
1025 fib_node_index_t*
1026 fib_path_list_paths_remove (fib_node_index_t path_list_index,
1027                            const fib_route_path_t *rpaths)
1028 {
1029     fib_node_index_t *match_path_indices;
1030     fib_path_list_t *path_list;
1031     i32 ii, jj;
1032
1033     path_list = fib_path_list_get(path_list_index);
1034     match_path_indices = NULL;
1035     vec_validate_init_empty(match_path_indices,
1036                             vec_len(rpaths) - 1,
1037                             FIB_NODE_INDEX_INVALID);
1038
1039     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
1040
1041     FIB_PATH_LIST_DBG(path_list, "path-remove");
1042
1043     /*
1044      * the number of existing paths is likely to be larger than the
1045      * number of paths being added.
1046      * walk in reverse so the vec_del is ok
1047      */
1048     vec_foreach_index_backwards(ii, path_list->fpl_paths)
1049     {
1050         int found = ~0;
1051
1052         vec_foreach_index(jj, rpaths)
1053         {
1054             if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
1055                                                &rpaths[jj]))
1056             {
1057                 found = jj;
1058                 break;
1059             }
1060         }
1061         if (~0 != found)
1062         {
1063             fib_node_index_t match_path_index;
1064             /*
1065              * match - remove it
1066              */
1067             match_path_index = path_list->fpl_paths[ii];
1068             vec_del1(path_list->fpl_paths, ii);
1069             fib_path_destroy(match_path_index);
1070             match_path_indices[jj] = match_path_index;
1071         }
1072     }
1073
1074     FIB_PATH_LIST_DBG(path_list, "paths-removed");
1075
1076     return (match_path_indices);
1077 }
1078
1079 /*
1080  * fib_path_list_copy_and_path_remove
1081  *
1082  * Copy the path-list excluding the path passed.
1083  * If the path is the last one, then the index reurned will be invalid.
1084  * i.e. the path-list is toast.
1085  */
1086 fib_node_index_t
1087 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1088                                     fib_path_list_flags_t flags,
1089                                     const fib_route_path_t *rpaths)
1090 {
1091     fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
1092     fib_path_list_t *path_list,  *orig_path_list;
1093     const fib_route_path_t *rpath;
1094     fib_node_index_t pi;
1095
1096     path_list = fib_path_list_alloc(&path_list_index);
1097
1098     flags = fib_path_list_flags_fixup(flags);
1099     orig_path_list = fib_path_list_get(orig_path_list_index);
1100
1101     FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1102
1103     path_list->fpl_flags = flags;
1104     /*
1105      * allocate as many paths as we might need in one go, rather than
1106      * using vec_add to do a few at a time.
1107      */
1108     vec_validate(path_list->fpl_paths,
1109                  vec_len(orig_path_list->fpl_paths) - 1);
1110     pi = 0;
1111
1112     /*
1113      * create a representation of the path to be removed, so it
1114      * can be used as a comparison object during the copy.
1115      */
1116     vec_foreach(orig_path_index, orig_path_list->fpl_paths)
1117     {
1118         /*
1119          * copy the original paths over to the new list
1120          */
1121         path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
1122                                                    path_list_index);
1123     }
1124     vec_foreach(rpath, rpaths)
1125     {
1126         int found = 0;
1127         tmp_path_index = fib_path_create(path_list_index, rpath);
1128
1129         vec_foreach_index(pi, path_list->fpl_paths)
1130         {
1131             if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
1132             {
1133                 found = 1;
1134                 break;
1135             }
1136         }
1137         if (found)
1138         {
1139             fib_path_destroy(path_list->fpl_paths[pi]);
1140             vec_del1(path_list->fpl_paths, pi);
1141         }
1142         fib_path_destroy(tmp_path_index);
1143     }
1144
1145     /*
1146      * if there are no paths, then the new path-list is aborted
1147      */
1148     if (0 == vec_len(path_list->fpl_paths)) {
1149         FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1150
1151         fib_path_list_destroy(path_list);
1152
1153         path_list_index = FIB_NODE_INDEX_INVALID;
1154     } else {
1155         /*
1156          * we sort the paths since the key for the path-list is
1157          * the description of the paths it contains. The paths need to
1158          * be sorted else this description will differ.
1159          */
1160         vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1161
1162         /*
1163          * If a shared path list is requested, consult the DB for a match
1164          */
1165         if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1166         {
1167             fib_node_index_t exist_path_list_index;
1168
1169             /*
1170              * check for a matching path-list in the DB.
1171              * If we find one then we can return the existing one and destroy the
1172              * new one just created.
1173              */
1174             exist_path_list_index = fib_path_list_db_find(path_list);
1175             if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1176             {
1177                 fib_path_list_destroy(path_list);
1178
1179                 path_list_index = exist_path_list_index;
1180             }
1181             else
1182             {
1183                 /*
1184                  * if there was not a matching path-list, then this
1185                  * new one will need inserting into the DB and resolving.
1186                  */
1187                 fib_path_list_db_insert(path_list_index);
1188
1189                 path_list = fib_path_list_resolve(path_list);
1190             }
1191         }
1192         else
1193         {
1194             /*
1195              * no shared path list requested. resolve and use the one
1196              * just created.
1197              */
1198             path_list = fib_path_list_resolve(path_list);
1199         }
1200     }
1201
1202     return (path_list_index);
1203 }
1204
1205 /*
1206  * fib_path_list_contribute_forwarding
1207  *
1208  * Return the index of a load-balance that user of this path-list should
1209  * use for forwarding
1210  */
1211 void
1212 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1213                                      fib_forward_chain_type_t fct,
1214                                      fib_path_list_fwd_flags_t flags,
1215                                      dpo_id_t *dpo)
1216 {
1217     fib_path_list_t *path_list;
1218
1219     path_list = fib_path_list_get(path_list_index);
1220
1221     fib_path_list_mk_lb(path_list, fct, dpo, flags);
1222
1223     ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1224
1225     /*
1226      * If there's only one bucket in the load-balance then we can
1227      * squash it out.
1228      */
1229     if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1230         (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1231     {
1232         dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1233     }
1234 }
1235
1236 /*
1237  * fib_path_list_get_adj
1238  *
1239  * Return the index of a adjacency for the first path that user of this
1240  * path-list should use for forwarding
1241  */
1242 adj_index_t
1243 fib_path_list_get_adj (fib_node_index_t path_list_index,
1244                        fib_forward_chain_type_t type)
1245 {
1246     fib_path_list_t *path_list;
1247
1248     path_list = fib_path_list_get(path_list_index);
1249     return (fib_path_get_adj(path_list->fpl_paths[0]));
1250 }
1251
1252 int
1253 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1254                                      fib_node_index_t **entry_indicies)
1255 {
1256     fib_node_index_t *path_index;
1257     int is_looped, list_looped;
1258     fib_path_list_t *path_list;
1259
1260     list_looped = 0;
1261     path_list = fib_path_list_get(path_list_index);
1262
1263     vec_foreach (path_index, path_list->fpl_paths)
1264     {
1265         fib_node_index_t *copy, **copy_ptr;
1266
1267         /*
1268          * we need a copy of the nodes visited so that when we add entries
1269          * we explore on the nth path and a looped is detected, those entries
1270          * are not again searched for n+1 path and so finding a loop that does
1271          * not exist.
1272          */
1273         copy = vec_dup(*entry_indicies);
1274         copy_ptr = &copy;
1275
1276         is_looped  = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1277         list_looped += is_looped;
1278
1279         vec_free(copy);
1280     }
1281
1282     FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1283
1284     if (list_looped)
1285     {
1286         path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1287     }
1288     else
1289     {
1290         path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1291     }
1292
1293     return (list_looped);
1294 }
1295
1296 u32
1297 fib_path_list_child_add (fib_node_index_t path_list_index,
1298                          fib_node_type_t child_type,
1299                          fib_node_index_t child_index)
1300 {
1301     if (FIB_PATH_LIST_POPULAR - 1 == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1302                                                              path_list_index))
1303     {
1304         /*
1305          * Set the popular flag on the path-list once we pass the magic
1306          * threshold. then walk children to update.
1307          * We don't undo this action. The rational being that the number
1308          * of entries using this prefix is large enough such that it is a
1309          * non-trival amount of effort to converge them. If we get into the
1310          * situation where we are adding and removing entries such that we
1311          * flip-flop over the threshold, then this non-trivial work is added
1312          * to each of those routes adds/deletes - not a situation we want.
1313          */
1314         fib_node_back_walk_ctx_t ctx = {
1315             .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1316         };
1317         fib_path_list_t *path_list;
1318
1319         path_list = fib_path_list_get(path_list_index);
1320         path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1321
1322         fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1323     }
1324
1325     return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1326                                  path_list_index,
1327                                  child_type,
1328                                  child_index));
1329 }
1330
1331 void
1332 fib_path_list_child_remove (fib_node_index_t path_list_index,
1333                             u32 si)
1334 {
1335     fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1336                           path_list_index,
1337                           si);
1338 }
1339
1340 void
1341 fib_path_list_lock(fib_node_index_t path_list_index)
1342 {
1343     fib_path_list_t *path_list;
1344
1345     if (FIB_NODE_INDEX_INVALID != path_list_index)
1346     {
1347         path_list = fib_path_list_get(path_list_index);
1348
1349         fib_node_lock(&path_list->fpl_node);
1350     }
1351 }
1352
1353 void
1354 fib_path_list_unlock (fib_node_index_t path_list_index)
1355 {
1356     fib_path_list_t *path_list;
1357
1358     if (FIB_NODE_INDEX_INVALID != path_list_index)
1359     {
1360         path_list = fib_path_list_get(path_list_index);
1361
1362         fib_node_unlock(&path_list->fpl_node);
1363     }
1364 }
1365
1366 u32
1367 fib_path_list_pool_size (void)
1368 {
1369     return (pool_elts(fib_path_list_pool));
1370 }
1371
1372 u32
1373 fib_path_list_db_size (void)
1374 {
1375     return (hash_elts(fib_path_list_db));
1376 }
1377
1378 void
1379 fib_path_list_walk (fib_node_index_t path_list_index,
1380                     fib_path_list_walk_fn_t func,
1381                     void *ctx)
1382 {
1383     fib_node_index_t *path_index;
1384     fib_path_list_t *path_list;
1385
1386     path_list = fib_path_list_get(path_list_index);
1387
1388     vec_foreach(path_index, path_list->fpl_paths)
1389     {
1390         if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1391                                             *path_index,
1392                                             ctx))
1393             break;
1394     }
1395 }
1396
1397 void
1398 fib_path_list_walk_w_ext (fib_node_index_t path_list_index,
1399                           const fib_path_ext_list_t *ext_list,
1400                           fib_path_list_walk_w_ext_fn_t func,
1401                           void *ctx)
1402 {
1403     fib_node_index_t *path_index;
1404     fib_path_list_t *path_list;
1405     fib_path_ext_t *path_ext;
1406
1407     path_list = fib_path_list_get(path_list_index);
1408
1409     vec_foreach(path_index, path_list->fpl_paths)
1410     {
1411         path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1412
1413         if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1414                                             *path_index,
1415                                             path_ext,
1416                                             ctx))
1417             break;
1418     }
1419 }
1420
1421 void
1422 fib_path_list_module_init (void)
1423 {
1424     fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1425
1426     fib_path_list_db = hash_create2 (/* elts */ 0,
1427                                      /* user */ 0,
1428                                      /* value_bytes */ sizeof (fib_node_index_t),
1429                                      fib_path_list_db_hash_key_sum,
1430                                      fib_path_list_db_hash_key_equal,
1431                                      /* format pair/arg */
1432                                      0, 0);
1433     fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1434 }
1435
1436 static clib_error_t *
1437 show_fib_path_list_command (vlib_main_t * vm,
1438                             unformat_input_t * input,
1439                             vlib_cli_command_t * cmd)
1440 {
1441     fib_path_list_t *path_list;
1442     fib_node_index_t pli;
1443
1444     if (unformat (input, "%d", &pli))
1445     {
1446         /*
1447          * show one in detail
1448          */
1449         if (!pool_is_free_index(fib_path_list_pool, pli))
1450         {
1451             path_list = fib_path_list_get(pli);
1452             u8 *s = fib_path_list_format(pli, NULL);
1453             s = format(s, "children:");
1454             s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1455             vlib_cli_output (vm, "%v", s);
1456             vec_free(s);
1457         }
1458         else
1459         {
1460             vlib_cli_output (vm, "path list %d invalid", pli);
1461         }
1462     }
1463     else
1464     {
1465         /*
1466          * show all
1467          */
1468         vlib_cli_output (vm, "FIB Path Lists");
1469         pool_foreach_index (pli, fib_path_list_pool)
1470          {
1471             vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1472         }
1473     }
1474     return (NULL);
1475 }
1476
1477 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1478   .path = "show fib path-lists",
1479   .function = show_fib_path_list_command,
1480   .short_help = "show fib path-lists",
1481 };