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