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