src/vnet/fib/fib_path_list.c

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