vnet/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
  27 /**
  28  * FIB path-list
  29  * A representation of the list/set of path trough which a prefix is reachable
  30  */
  31 typedef struct fib_path_list_t_ {
  32     /**
  33      * A path-list is a node in the FIB graph.
  34      */
  35     fib_node_t fpl_node;
  36
  37     /**
  38      * Flags on the path-list
  39      */
  40     fib_path_list_flags_t fpl_flags;
  41
  42     /**
  43      * The next-hop protocol for the paths in this path list.
  44      * Note that fixing the proto here means we don't support a mix of
  45      * v4 and v6 paths. ho hum.
  46      */
  47     fib_protocol_t fpl_nh_proto;
  48
  49     /**
  50      * Vector of paths indecies for all configured paths.
  51      * For shareable path-lists this list MUST not change.
  52      */
  53     fib_node_index_t *fpl_paths;
  54 } fib_path_list_t;
  55
  56 /*
  57  * Array of strings/names for the FIB sources
  58  */
  59 static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
  60
  61 /*
  62  * The memory pool from which we allocate all the path-lists
  63  */
  64 static fib_path_list_t * fib_path_list_pool;
  65
  66 /*
  67  * The data-base of shared path-lists
  68  */
  69 static uword *fib_path_list_db;
  70
  71 /*
  72  * Debug macro
  73  */
  74 #ifdef FIB_DEBUG
  75 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)            \
  76 {                                                         \
  77     u8 *_tmp = 0;                                         \
  78     _tmp = fib_path_list_format(                          \
  79         fib_path_list_get_index(_pl), _tmp);              \
  80     clib_warning("pl:[%d:%p:%p:%s]:" _fmt,                \
  81                  fib_path_list_get_index(_pl),            \
  82                  _pl, _pl->fpl_paths, _tmp,               \
  83                  ##_args);                                \
  84     vec_free(_tmp);                                       \
  85 }
  86 #else
  87 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
  88 #endif
  89
  90 static fib_path_list_t *
  91 fib_path_list_get (fib_node_index_t index)
  92 {
  93     return (pool_elt_at_index(fib_path_list_pool, index));
  94 }
  95
  96 static fib_node_t *
  97 fib_path_list_get_node (fib_node_index_t index)
  98 {
  99     return ((fib_node_t*)fib_path_list_get(index));
 100 }
 101
 102 static fib_path_list_t*
 103 fib_path_list_from_fib_node (fib_node_t *node)
 104 {
 105 #if CLIB_DEBUG > 0
 106     ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
 107 #endif
 108     return ((fib_path_list_t*)node);
 109 }
 110
 111 static fib_node_index_t
 112 fib_path_list_get_index (fib_path_list_t *path_list)
 113 {
 114     return (path_list - fib_path_list_pool);
 115 }
 116
 117 static u8 *
 118 format_fib_path_list (u8 * s, va_list * args)
 119 {
 120     fib_path_list_attribute_t attr;
 121     fib_node_index_t *path_index;
 122     fib_path_list_t *path_list;
 123
 124     path_list = va_arg (*args, fib_path_list_t *);
 125
 126     s = format (s, "    index:%u", fib_path_list_get_index(path_list));
 127     s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
 128     s = format (s, " proto:%U", format_fib_protocol, path_list->fpl_nh_proto);
 129
 130     if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
 131     {
 132         s = format (s, " flags:");
 133         FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
 134         {
 135             if ((1<<attr) & path_list->fpl_flags)
 136             {
 137                 s = format (s, "%s,", fib_path_list_attr_names[attr]);
 138             }
 139         }
 140     }
 141     vec_foreach (path_index, path_list->fpl_paths)
 142     {
 143         s = fib_path_format(*path_index, s);
 144         s = format(s, "\n");
 145     }
 146
 147     return (s);
 148 }
 149
 150 u8 *
 151 fib_path_list_adjs_format (fib_node_index_t path_list_index,
 152                            u32 indent,
 153                            u8 * s)
 154 {
 155     fib_path_list_t *path_list;
 156     u32 i;
 157
 158     path_list = fib_path_list_get(path_list_index);
 159
 160     vec_foreach_index (i, path_list->fpl_paths)
 161     {
 162         s = fib_path_adj_format(path_list->fpl_paths[i],
 163                                 indent, s);
 164     }
 165
 166     return (s);
 167 }
 168
 169
 170 u8 *
 171 fib_path_list_format (fib_node_index_t path_list_index,
 172                       u8 * s)
 173 {
 174     fib_path_list_t *path_list;
 175
 176     path_list = fib_path_list_get(path_list_index);
 177
 178     return (format(s, "%U", format_fib_path_list, path_list));
 179 }
 180
 181 static uword
 182 fib_path_list_hash (fib_path_list_t *path_list)
 183 {
 184     uword old_path_list_hash, new_path_list_hash, path_hash;
 185     fib_node_index_t *path_index;
 186
 187     ASSERT(path_list);
 188
 189     new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
 190
 191     vec_foreach (path_index, path_list->fpl_paths)
 192     {
 193         path_hash = fib_path_hash(*path_index);
 194 #if uword_bits == 64
 195         hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
 196 #else
 197         hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
 198 #endif
 199     }
 200
 201     return (new_path_list_hash);
 202 }
 203
 204 always_inline uword
 205 fib_path_list_db_hash_key_from_index (uword index)
 206 {
 207     return 1 + 2*index;
 208 }
 209
 210 always_inline uword
 211 fib_path_list_db_hash_key_is_index (uword key)
 212 {
 213     return key & 1;
 214 }
 215
 216 always_inline uword
 217 fib_path_list_db_hash_key_2_index (uword key)
 218 {
 219     ASSERT (fib_path_list_db_hash_key_is_index (key));
 220     return key / 2;
 221 }
 222
 223 static fib_path_list_t*
 224 fib_path_list_db_get_from_hash_key (uword key)
 225 {
 226     fib_path_list_t *path_list;
 227
 228     if (fib_path_list_db_hash_key_is_index (key))
 229     {
 230         fib_node_index_t path_list_index;
 231
 232         path_list_index = fib_path_list_db_hash_key_2_index(key);
 233         path_list = fib_path_list_get(path_list_index);
 234     }
 235     else
 236     {
 237         path_list = uword_to_pointer (key, fib_path_list_t *);
 238     }
 239
 240     return (path_list);
 241 }
 242
 243 static uword
 244 fib_path_list_db_hash_key_sum (hash_t * h,
 245                                uword key)
 246 {
 247     fib_path_list_t *path_list;
 248
 249     path_list = fib_path_list_db_get_from_hash_key(key);
 250
 251     return (fib_path_list_hash(path_list));
 252 }
 253
 254 static uword
 255 fib_path_list_db_hash_key_equal (hash_t * h,
 256                                  uword key1,
 257                                  uword key2)
 258 {
 259     fib_path_list_t *path_list1, *path_list2;
 260
 261     path_list1 = fib_path_list_db_get_from_hash_key(key1);
 262     path_list2 = fib_path_list_db_get_from_hash_key(key2);
 263
 264     return (fib_path_list_hash(path_list1) ==
 265             fib_path_list_hash(path_list2));
 266 }
 267
 268 static fib_node_index_t
 269 fib_path_list_db_find (fib_path_list_t *path_list)
 270 {
 271     uword *p;
 272
 273     p = hash_get(fib_path_list_db, path_list);
 274
 275     if (NULL != p)
 276     {
 277         return p[0];
 278     }
 279
 280     return (FIB_NODE_INDEX_INVALID);
 281 }
 282
 283 static void
 284 fib_path_list_db_insert (fib_node_index_t path_list_index)
 285 {
 286     fib_path_list_t *path_list;
 287
 288     path_list = fib_path_list_get(path_list_index);
 289
 290     ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
 291
 292     hash_set (fib_path_list_db,
 293               fib_path_list_db_hash_key_from_index(path_list_index),
 294               path_list_index);
 295
 296     FIB_PATH_LIST_DBG(path_list, "DB-inserted");
 297 }
 298
 299 static void
 300 fib_path_list_db_remove (fib_node_index_t path_list_index)
 301 {
 302     fib_path_list_t *path_list;
 303
 304     path_list = fib_path_list_get(path_list_index);
 305
 306     ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
 307
 308     hash_unset(fib_path_list_db,
 309                fib_path_list_db_hash_key_from_index(path_list_index));
 310
 311     FIB_PATH_LIST_DBG(path_list, "DB-removed");
 312 }
 313
 314 static void
 315 fib_path_list_destroy (fib_path_list_t *path_list)
 316 {
 317     fib_node_index_t *path_index;
 318
 319     FIB_PATH_LIST_DBG(path_list, "destroy");
 320
 321     vec_foreach (path_index, path_list->fpl_paths)
 322     {
 323         fib_path_destroy(*path_index);
 324     }
 325
 326     vec_free(path_list->fpl_paths);
 327
 328     fib_node_deinit(&path_list->fpl_node);
 329     pool_put(fib_path_list_pool, path_list);
 330 }
 331
 332 static void
 333 fib_path_list_last_lock_gone (fib_node_t *node)
 334 {
 335     fib_path_list_t *path_list;
 336
 337     path_list = fib_path_list_from_fib_node(node);
 338
 339     FIB_PATH_LIST_DBG(path_list, "last-lock");
 340
 341     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 342     {
 343         fib_path_list_db_remove(fib_path_list_get_index(path_list));
 344     }
 345     fib_path_list_destroy(path_list);
 346 }
 347
 348 /*
 349  * fib_path_mk_lb
 350  *
 351  * update the multipath adj this path-list will contribute to its
 352  * children's forwarding.
 353  */
 354 static void
 355 fib_path_list_mk_lb (fib_path_list_t *path_list,
 356                      fib_forward_chain_type_t type,
 357                      dpo_id_t *dpo)
 358 {
 359     load_balance_path_t *hash_key;
 360     fib_node_index_t *path_index;
 361
 362     hash_key  = NULL;
 363
 364     /*
 365      * We gather the DPOs from resolved paths.
 366      */
 367     vec_foreach (path_index, path_list->fpl_paths)
 368     {
 369         hash_key = fib_path_append_nh_for_multipath_hash(
 370                        *path_index,
 371                        type,
 372                        hash_key);
 373     }
 374
 375     /*
 376      * Path-list load-balances, which if used, would be shared and hence
 377      * never need a load-balance map.
 378      */
 379     load_balance_multipath_update(dpo, hash_key, LOAD_BALANCE_FLAG_NONE);
 380
 381     FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
 382
 383     vec_free(hash_key);
 384 }
 385
 386 /*
 387  * fib_path_list_back_walk
 388  *
 389  * Called from one of this path-list's paths to progate
 390  * a back walk
 391  */
 392 void
 393 fib_path_list_back_walk (fib_node_index_t path_list_index,
 394                          fib_node_back_walk_ctx_t *ctx)
 395 {
 396     fib_path_list_t *path_list;
 397
 398     path_list = fib_path_list_get(path_list_index);
 399
 400     /*
 401      * propagate the backwalk further
 402      */
 403     if (32 >= fib_node_list_get_size(path_list->fpl_node.fn_children))
 404     {
 405         /*
 406          * only a few children. continue the walk synchronously
 407          */
 408         fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
 409     }
 410     else
 411     {
 412         /*
 413          * many children. schedule a async walk
 414          */
 415         fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
 416                        path_list_index,
 417                        FIB_WALK_PRIORITY_LOW,
 418                        ctx);
 419     }
 420 }
 421
 422 /*
 423  * fib_path_list_back_walk_notify
 424  *
 425  * A back walk has reach this path-list.
 426  */
 427 static fib_node_back_walk_rc_t
 428 fib_path_list_back_walk_notify (fib_node_t *node,
 429                                 fib_node_back_walk_ctx_t *ctx)
 430 {
 431     /*
 432      * the path-list is not a direct child of any other node type
 433      * paths, which do not change thier to-list-mapping, save the
 434      * list they are a member of, and invoke the BW function directly.
 435      */
 436     ASSERT(0);
 437
 438     return (FIB_NODE_BACK_WALK_CONTINUE);
 439 }
 440
 441 /*
 442  * The FIB path-list's graph node virtual function table
 443  */
 444 static const fib_node_vft_t fib_path_list_vft = {
 445     .fnv_get = fib_path_list_get_node,
 446     .fnv_last_lock = fib_path_list_last_lock_gone,
 447     .fnv_back_walk = fib_path_list_back_walk_notify,
 448 };
 449
 450 static fib_path_list_t *
 451 fib_path_list_alloc (fib_node_index_t *path_list_index)
 452 {
 453     fib_path_list_t *path_list;
 454
 455     pool_get(fib_path_list_pool, path_list);
 456     memset(path_list, 0, sizeof(*path_list));
 457
 458     fib_node_init(&path_list->fpl_node,
 459                   FIB_NODE_TYPE_PATH_LIST);
 460
 461     if (NULL != path_list_index)
 462     {
 463         *path_list_index = fib_path_list_get_index(path_list);
 464     }
 465
 466     FIB_PATH_LIST_DBG(path_list, "alloc");
 467
 468     return (path_list);
 469 }
 470
 471 static fib_path_list_t *
 472 fib_path_list_resolve (fib_path_list_t *path_list)
 473 {
 474     fib_node_index_t *path_index, *paths, path_list_index;
 475
 476     ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
 477
 478     /*
 479      * resolving a path-list is a recursive action. this means more path
 480      * lists can be created during this call, and hence this path-list
 481      * can be realloc'd. so we work with copies.
 482      * this function is called only once per-path list, so its no great overhead.
 483      */
 484     path_list_index = fib_path_list_get_index(path_list);
 485     paths = vec_dup(path_list->fpl_paths);
 486
 487     vec_foreach (path_index, paths)
 488     {
 489         fib_path_resolve(*path_index);
 490     }
 491
 492     vec_free(paths);
 493     path_list = fib_path_list_get(path_list_index);
 494
 495     FIB_PATH_LIST_DBG(path_list, "resovled");
 496
 497     return (path_list);
 498 }
 499
 500 u32
 501 fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
 502 {
 503     fib_node_index_t *path_index;
 504     fib_path_list_t *path_list;
 505     u32 sw_if_index;
 506
 507     path_list = fib_path_list_get(path_list_index);
 508
 509     sw_if_index = ~0;
 510     vec_foreach (path_index, path_list->fpl_paths)
 511     {
 512         sw_if_index = fib_path_get_resolving_interface(*path_index);
 513         if (~0 != sw_if_index)
 514         {
 515             return (sw_if_index);
 516         }
 517     }
 518
 519     return (sw_if_index);
 520 }
 521
 522 int
 523 fib_path_list_is_looped (fib_node_index_t path_list_index)
 524 {
 525     fib_path_list_t *path_list;
 526
 527     path_list = fib_path_list_get(path_list_index);
 528
 529     return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
 530 }
 531
 532 static fib_path_cfg_flags_t
 533 fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
 534 {
 535     fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
 536
 537     if (plf & FIB_PATH_LIST_FLAG_LOCAL)
 538     {
 539         pf |= FIB_PATH_CFG_FLAG_LOCAL;
 540     }
 541     if (plf & FIB_PATH_LIST_FLAG_DROP)
 542     {
 543         pf |= FIB_PATH_CFG_FLAG_DROP;
 544     }
 545     if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
 546     {
 547         pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
 548     }
 549
 550     return (pf);
 551 }
 552
 553 static fib_path_list_flags_t
 554 fib_path_list_flags_fixup (fib_path_list_flags_t flags)
 555 {
 556     /*
 557      * we do no share drop nor exclusive path-lists
 558      */
 559     if (flags & FIB_PATH_LIST_FLAG_DROP ||
 560         flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
 561     {
 562         flags &= ~FIB_PATH_LIST_FLAG_SHARED;
 563     }
 564
 565     return (flags);
 566 }
 567
 568 fib_node_index_t
 569 fib_path_list_create (fib_path_list_flags_t flags,
 570                       const fib_route_path_t *rpaths)
 571 {
 572     fib_node_index_t path_list_index, old_path_list_index;
 573     fib_path_list_t *path_list;
 574     int i;
 575
 576     flags = fib_path_list_flags_fixup(flags);
 577     path_list = fib_path_list_alloc(&path_list_index);
 578     path_list->fpl_flags = flags;
 579     /*
 580      * we'll assume for now all paths are the same next-hop protocol
 581      */
 582     path_list->fpl_nh_proto = rpaths[0].frp_proto;
 583
 584     vec_foreach_index(i, rpaths)
 585     {
 586         vec_add1(path_list->fpl_paths,
 587                  fib_path_create(path_list_index,
 588                                  path_list->fpl_nh_proto,
 589                                  fib_path_list_flags_2_path_flags(flags),
 590                                  &rpaths[i]));
 591     }
 592
 593     /*
 594      * If a shared path list is requested, consult the DB for a match
 595      */
 596     if (flags & FIB_PATH_LIST_FLAG_SHARED)
 597     {
 598         /*
 599          * check for a matching path-list in the DB.
 600          * If we find one then we can return the existing one and destroy the
 601          * new one just created.
 602          */
 603         old_path_list_index = fib_path_list_db_find(path_list);
 604         if (FIB_NODE_INDEX_INVALID != old_path_list_index)
 605         {
 606             fib_path_list_destroy(path_list);
 607
 608             path_list_index = old_path_list_index;
 609         }
 610         else
 611         {
 612             /*
 613              * if there was not a matching path-list, then this
 614              * new one will need inserting into the DB and resolving.
 615              */
 616             fib_path_list_db_insert(path_list_index);
 617             path_list = fib_path_list_resolve(path_list);
 618         }
 619     }
 620     else
 621     {
 622         /*
 623          * no shared path list requested. resolve and use the one
 624          * just created.
 625          */
 626         path_list = fib_path_list_resolve(path_list);
 627     }
 628
 629     return (path_list_index);
 630 }
 631
 632 fib_node_index_t
 633 fib_path_list_create_special (fib_protocol_t nh_proto,
 634                               fib_path_list_flags_t flags,
 635                               const dpo_id_t *dpo)
 636 {
 637     fib_node_index_t path_index, path_list_index;
 638     fib_path_list_t *path_list;
 639
 640     path_list = fib_path_list_alloc(&path_list_index);
 641     path_list->fpl_flags = flags;
 642     path_list->fpl_nh_proto = nh_proto;
 643
 644     path_index =
 645         fib_path_create_special(path_list_index,
 646                                 path_list->fpl_nh_proto,
 647                                 fib_path_list_flags_2_path_flags(flags),
 648                                 dpo);
 649     vec_add1(path_list->fpl_paths, path_index);
 650
 651     /*
 652      * we don't share path-lists. we can do PIC on them so why bother.
 653      */
 654     path_list = fib_path_list_resolve(path_list);
 655
 656     return (path_list_index);
 657 }
 658
 659 /*
 660  * fib_path_list_copy_and_path_add
 661  *
 662  * Create a copy of a path-list and append one more path to it.
 663  * The path-list returned could either have been newly created, or
 664  * can be a shared path-list from the data-base.
 665  */
 666 fib_node_index_t
 667 fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
 668                                  fib_path_list_flags_t flags,
 669                                  const fib_route_path_t *rpaths)
 670 {
 671     fib_node_index_t path_index, path_list_index, *orig_path_index;
 672     fib_path_list_t *path_list, *orig_path_list;
 673     fib_node_index_t pi;
 674
 675     ASSERT(1 == vec_len(rpaths));
 676
 677     /*
 678      * alloc the new list before we retrieve the old one, lest
 679      * the alloc result in a realloc
 680      */
 681     path_list = fib_path_list_alloc(&path_list_index);
 682
 683     orig_path_list = fib_path_list_get(orig_path_list_index);
 684
 685     FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
 686
 687     flags = fib_path_list_flags_fixup(flags);
 688     path_list->fpl_flags = flags;
 689     path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
 690     vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
 691     pi = 0;
 692
 693     vec_foreach (orig_path_index, orig_path_list->fpl_paths)
 694     {
 695         path_index = fib_path_copy(*orig_path_index, path_list_index);
 696         path_list->fpl_paths[pi++] = path_index;
 697     }
 698     path_index = fib_path_create(path_list_index,
 699                                  path_list->fpl_nh_proto,
 700                                  fib_path_list_flags_2_path_flags(flags),
 701                                  rpaths);
 702     path_list->fpl_paths[pi] = path_index;
 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     vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
 710
 711     FIB_PATH_LIST_DBG(path_list, "path-added");
 712
 713     /*
 714      * If a shared path list is requested, consult the DB for a match
 715      */
 716     if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 717     {
 718         fib_node_index_t exist_path_list_index;
 719         /*
 720          * check for a matching path-list in the DB.
 721          * If we find one then we can return the existing one and destroy the
 722          * new one just created.
 723          */
 724         exist_path_list_index = fib_path_list_db_find(path_list);
 725         if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
 726         {
 727             fib_path_list_destroy(path_list);
 728
 729             path_list_index = exist_path_list_index;
 730         }
 731         else
 732         {
 733             /*
 734              * if there was not a matching path-list, then this
 735              * new one will need inserting into the DB and resolving.
 736              */
 737             fib_path_list_db_insert(path_list_index);
 738
 739             path_list = fib_path_list_resolve(path_list);
 740         }
 741     }
 742     else
 743     {
 744         /*
 745          * no shared path list requested. resolve and use the one
 746          * just created.
 747          */
 748         path_list = fib_path_list_resolve(path_list);
 749     }
 750
 751     return (path_list_index);
 752 }
 753
 754 /*
 755  * fib_path_list_copy_and_path_remove
 756  *
 757  * Copy the path-list excluding the path passed.
 758  * If the path is the last one, then the index reurned will be invalid.
 759  * i.e. the path-list is toast.
 760  */
 761 fib_node_index_t
 762 fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
 763                                     fib_path_list_flags_t flags,
 764                                     const fib_route_path_t *rpaths)
 765 {
 766     fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
 767     fib_path_list_t *path_list,  *orig_path_list;
 768     fib_node_index_t pi;
 769
 770     ASSERT(1 == vec_len(rpaths));
 771
 772     path_list = fib_path_list_alloc(&path_list_index);
 773
 774     flags = fib_path_list_flags_fixup(flags);
 775     orig_path_list = fib_path_list_get(orig_path_list_index);
 776
 777     FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
 778
 779     path_list->fpl_flags = flags;
 780     path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
 781     /*
 782      * allocate as many paths as we might need in one go, rather than
 783      * using vec_add to do a few at a time.
 784      */
 785     if (vec_len(orig_path_list->fpl_paths) > 1)
 786     {
 787         vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
 788     }
 789     pi = 0;
 790
 791     /*
 792      * create a representation of the path to be removed, so it
 793      * can be used as a comparison object during the copy.
 794      */
 795     tmp_path_index = fib_path_create(path_list_index,
 796                                      path_list->fpl_nh_proto,
 797                                      fib_path_list_flags_2_path_flags(flags),
 798                                      rpaths);
 799
 800     vec_foreach (orig_path_index, orig_path_list->fpl_paths)
 801     {
 802         if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
 803             path_index = fib_path_copy(*orig_path_index, path_list_index);
 804             if (pi < vec_len(path_list->fpl_paths))
 805             {
 806                 path_list->fpl_paths[pi++] = path_index;
 807             }
 808             else
 809             {
 810                 /*
 811                  * this is the unlikely case that the path being
 812                  * removed does not match one in the path-list, so
 813                  * we end up with as many paths as we started with.
 814                  * the paths vector was sized above with the expectation
 815                  * that we would have 1 less.
 816                  */
 817                 vec_add1(path_list->fpl_paths, path_index);
 818             }
 819         }
 820     }
 821
 822     /*
 823      * done with the temporary now
 824      */
 825     fib_path_destroy(tmp_path_index);
 826
 827     /*
 828      * if there are no paths, then the new path-list is aborted
 829      */
 830     if (0 == vec_len(path_list->fpl_paths)) {
 831         FIB_PATH_LIST_DBG(path_list, "last-path-removed");
 832
 833         fib_path_list_destroy(path_list);
 834
 835         path_list_index = FIB_NODE_INDEX_INVALID;
 836     } else {
 837         /*
 838          * we sort the paths since the key for the path-list is
 839          * the description of the paths it contains. The paths need to
 840          * be sorted else this description will differ.
 841          */
 842         vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
 843
 844         /*
 845          * If a shared path list is requested, consult the DB for a match
 846          */
 847         if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
 848         {
 849             fib_node_index_t exist_path_list_index;
 850
 851             /*
 852              * check for a matching path-list in the DB.
 853              * If we find one then we can return the existing one and destroy the
 854              * new one just created.
 855              */
 856             exist_path_list_index = fib_path_list_db_find(path_list);
 857             if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
 858             {
 859                 fib_path_list_destroy(path_list);
 860
 861                 path_list_index = exist_path_list_index;
 862             }
 863             else
 864             {
 865                 /*
 866                  * if there was not a matching path-list, then this
 867                  * new one will need inserting into the DB and resolving.
 868                  */
 869                 fib_path_list_db_insert(path_list_index);
 870
 871                 path_list = fib_path_list_resolve(path_list);
 872             }
 873         }
 874         else
 875         {
 876             /*
 877              * no shared path list requested. resolve and use the one
 878              * just created.
 879              */
 880             path_list = fib_path_list_resolve(path_list);
 881         }
 882     }
 883
 884     return (path_list_index);
 885 }
 886
 887 /*
 888  * fib_path_list_contribute_forwarding
 889  *
 890  * Return the index of a load-balance that user of this path-list should
 891  * use for forwarding
 892  */
 893 void
 894 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
 895                                      fib_forward_chain_type_t type,
 896                                      dpo_id_t *dpo)
 897 {
 898     fib_path_list_t *path_list;
 899
 900     path_list = fib_path_list_get(path_list_index);
 901
 902     fib_path_list_mk_lb(path_list, type, dpo);
 903 }
 904
 905 /*
 906  * fib_path_list_get_adj
 907  *
 908  * Return the index of a adjacency for the first path that user of this
 909  * path-list should use for forwarding
 910  */
 911 adj_index_t
 912 fib_path_list_get_adj (fib_node_index_t path_list_index,
 913                        fib_forward_chain_type_t type)
 914 {
 915     fib_path_list_t *path_list;
 916
 917     path_list = fib_path_list_get(path_list_index);
 918     return (fib_path_get_adj(path_list->fpl_paths[0]));
 919 }
 920
 921 int
 922 fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
 923                                      fib_node_index_t **entry_indicies)
 924 {
 925     fib_node_index_t *path_index;
 926     int is_looped, list_looped;
 927     fib_path_list_t *path_list;
 928
 929     list_looped = 0;
 930     path_list = fib_path_list_get(path_list_index);
 931
 932     vec_foreach (path_index, path_list->fpl_paths)
 933     {
 934         fib_node_index_t *copy, **copy_ptr;
 935
 936         /*
 937          * we need a copy of the nodes visited so that when we add entries
 938          * we explore on the nth path and a looped is detected, those entries
 939          * are not again searched for n+1 path and so finding a loop that does
 940          * not exist.
 941          */
 942         copy = vec_dup(*entry_indicies);
 943         copy_ptr = &copy;
 944
 945         is_looped  = fib_path_recursive_loop_detect(*path_index, copy_ptr);
 946         list_looped += is_looped;
 947     }
 948
 949     FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
 950
 951     if (list_looped)
 952     {
 953         path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
 954     }
 955     else
 956     {
 957         path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
 958     }
 959
 960     return (list_looped);
 961 }
 962
 963 u32
 964 fib_path_list_child_add (fib_node_index_t path_list_index,
 965                          fib_node_type_t child_type,
 966                          fib_node_index_t child_index)
 967 {
 968     return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
 969                                path_list_index,
 970                                child_type,
 971                                child_index));
 972 }
 973
 974 void
 975 fib_path_list_child_remove (fib_node_index_t path_list_index,
 976                             u32 si)
 977 {
 978     fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
 979                           path_list_index,
 980                           si);
 981 }
 982
 983 void
 984 fib_path_list_lock(fib_node_index_t path_list_index)
 985 {
 986     fib_path_list_t *path_list;
 987
 988     if (FIB_NODE_INDEX_INVALID != path_list_index)
 989     {
 990         path_list = fib_path_list_get(path_list_index);
 991
 992         fib_node_lock(&path_list->fpl_node);
 993         FIB_PATH_LIST_DBG(path_list, "lock");
 994     }
 995 }
 996
 997 void
 998 fib_path_list_unlock (fib_node_index_t path_list_index)
 999 {
1000     fib_path_list_t *path_list;
1001
1002     if (FIB_NODE_INDEX_INVALID != path_list_index)
1003     {
1004         path_list = fib_path_list_get(path_list_index);
1005         FIB_PATH_LIST_DBG(path_list, "unlock");
1006
1007         fib_node_unlock(&path_list->fpl_node);
1008     }
1009 }
1010
1011 u32
1012 fib_path_list_pool_size (void)
1013 {
1014     return (pool_elts(fib_path_list_pool));
1015 }
1016
1017 u32
1018 fib_path_list_db_size (void)
1019 {
1020     return (hash_elts(fib_path_list_db));
1021 }
1022
1023 void
1024 fib_path_list_walk (fib_node_index_t path_list_index,
1025                     fib_path_list_walk_fn_t func,
1026                     void *ctx)
1027 {
1028     fib_node_index_t *path_index;
1029     fib_path_list_t *path_list;
1030
1031     path_list = fib_path_list_get(path_list_index);
1032
1033     vec_foreach(path_index, path_list->fpl_paths)
1034     {
1035         if (!func(path_list_index, *path_index, ctx))
1036             break;
1037     }
1038 }
1039
1040
1041 void
1042 fib_path_list_module_init (void)
1043 {
1044     fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1045
1046     fib_path_list_db = hash_create2 (/* elts */ 0,
1047                                      /* user */ 0,
1048                                      /* value_bytes */ sizeof (fib_node_index_t),
1049                                      fib_path_list_db_hash_key_sum,
1050                                      fib_path_list_db_hash_key_equal,
1051                                      /* format pair/arg */
1052                                      0, 0);
1053 }
1054
1055 static clib_error_t *
1056 show_fib_path_list_command (vlib_main_t * vm,
1057                             unformat_input_t * input,
1058                             vlib_cli_command_t * cmd)
1059 {
1060     fib_path_list_t *path_list;
1061     fib_node_index_t pli;
1062
1063     if (unformat (input, "%d", &pli))
1064     {
1065         /*
1066          * show one in detail
1067          */
1068         if (!pool_is_free_index(fib_path_list_pool, pli))
1069         {
1070             path_list = fib_path_list_get(pli);
1071             u8 *s = fib_path_list_format(pli, NULL);
1072             s = format(s, "children:");
1073             s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1074             vlib_cli_output (vm, "%s", s);
1075             vec_free(s);
1076         }
1077         else
1078         {
1079             vlib_cli_output (vm, "path list %d invalid", pli);
1080         }
1081     }
1082     else
1083     {
1084         /*
1085          * show all
1086          */
1087         vlib_cli_output (vm, "FIB Path Lists");
1088         pool_foreach(path_list, fib_path_list_pool,
1089         ({
1090             vlib_cli_output (vm, "%U", format_fib_path_list, path_list);
1091         }));
1092     }
1093     return (NULL);
1094 }
1095
1096 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1097   .path = "show fib path list",
1098   .function = show_fib_path_list_command,
1099   .short_help = "show fib path list",
1100 };