src/vnet/bier/bier_entry.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 <vnet/bier/bier_entry.h>
  17 #include <vnet/bier/bier_update.h>
  18
  19 #include <vnet/fib/fib_path_list.h>
  20
  21 #include <vnet/bier/bier_fmask_db.h>
  22 #include <vnet/bier/bier_fmask.h>
  23 #include <vnet/bier/bier_table.h>
  24
  25 bier_entry_t *bier_entry_pool;
  26
  27 static index_t
  28 bier_entry_get_index (const bier_entry_t *be)
  29 {
  30     return (be - bier_entry_pool);
  31 }
  32
  33 static fib_path_list_walk_rc_t
  34 bier_entry_link_walk (fib_node_index_t pl_index,
  35                       fib_node_index_t path_index,
  36                       void *arg)
  37 {
  38     bier_entry_t *be = arg;
  39     index_t bfmi;
  40
  41     bfmi = fib_path_get_resolving_index(path_index);
  42     bier_fmask_link(bfmi, be->be_bp);
  43
  44     return (FIB_PATH_LIST_WALK_CONTINUE);
  45 }
  46
  47 static fib_path_list_walk_rc_t
  48 bier_entry_unlink_walk (fib_node_index_t pl_index,
  49                         fib_node_index_t path_index,
  50                         void *arg)
  51 {
  52     bier_entry_t *be = arg;
  53     index_t bfmi;
  54
  55     bfmi = fib_path_get_resolving_index(path_index);
  56     bier_fmask_unlink(bfmi, be->be_bp);
  57
  58     return (FIB_PATH_LIST_WALK_CONTINUE);
  59 }
  60
  61 index_t
  62 bier_entry_create (index_t bti,
  63                    bier_bp_t bp)
  64 {
  65     bier_entry_t *be;
  66
  67     pool_get(bier_entry_pool, be);
  68
  69     be->be_bp = bp;
  70     be->be_bti = bti;
  71     be->be_path_list = FIB_NODE_INDEX_INVALID;
  72
  73     return (bier_entry_get_index(be));
  74 }
  75
  76
  77 static void
  78 bier_entry_table_ecmp_walk_add_fmask (index_t btei,
  79                                       void *arg)
  80 {
  81     bier_entry_t *be = arg;;
  82
  83     /*
  84      * choose a fmask from the entry's resolved set to add
  85      * to ECMP table's lookup table
  86      */
  87     if (FIB_NODE_INDEX_INVALID != be->be_path_list)
  88     {
  89         const bier_table_id_t *btid;
  90         dpo_id_t dpo = DPO_INVALID;
  91         const dpo_id_t *choice;
  92         load_balance_t *lb;
  93
  94         btid = bier_table_get_id(btei);
  95
  96         fib_path_list_contribute_forwarding(be->be_path_list,
  97                                             FIB_FORW_CHAIN_TYPE_BIER,
  98                                             FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
  99                                             &dpo);
 100
 101         /*
 102          * select the appropriate bucket from the LB
 103          */
 104         if (dpo.dpoi_type == DPO_LOAD_BALANCE)
 105         {
 106             lb = load_balance_get(dpo.dpoi_index);
 107             choice = load_balance_get_bucket_i(lb,
 108                                                btid->bti_ecmp &
 109                                                (lb->lb_n_buckets_minus_1));
 110         }
 111         else
 112         {
 113             choice = &dpo;
 114         }
 115
 116         if (choice->dpoi_type == DPO_BIER_FMASK)
 117         {
 118             bier_table_ecmp_set_fmask(btei, be->be_bp,
 119                                       choice->dpoi_index);
 120         }
 121         else
 122         {
 123             /*
 124              * any other type results in a drop, which we represent
 125              * with an empty bucket
 126              */
 127             bier_table_ecmp_set_fmask(btei, be->be_bp,
 128                                       INDEX_INVALID);
 129         }
 130
 131         dpo_reset(&dpo);
 132     }
 133     else
 134     {
 135         /*
 136          * no fmasks left. insert a drop
 137          */
 138         bier_table_ecmp_set_fmask(btei, be->be_bp, INDEX_INVALID);
 139     }
 140 }
 141
 142 void
 143 bier_entry_delete (index_t bei)
 144 {
 145     bier_entry_t *be;
 146
 147     be = bier_entry_get(bei);
 148
 149     /*
 150      * if we still ahve a path-list, unlink from it
 151      */
 152     if (FIB_NODE_INDEX_INVALID != be->be_path_list)
 153     {
 154         fib_path_list_walk(be->be_path_list,
 155                            bier_entry_unlink_walk,
 156                            be);
 157         fib_path_list_child_remove(be->be_path_list,
 158                                    be->be_sibling_index);
 159
 160         be->be_path_list = FIB_NODE_INDEX_INVALID;
 161         bier_table_ecmp_walk(be->be_bti,
 162                              bier_entry_table_ecmp_walk_add_fmask,
 163                              be);
 164     }
 165
 166     pool_put(bier_entry_pool, be);
 167 }
 168
 169 void
 170 bier_entry_path_add (index_t bei,
 171                      const fib_route_path_t *rpaths)
 172 {
 173     fib_node_index_t old_pl_index;
 174     bier_entry_t *be;
 175
 176     be = bier_entry_get(bei);
 177     old_pl_index = be->be_path_list;
 178
 179     /*
 180      * lock the path-list so it does not go away before we unlink
 181      * from its resolved fmasks
 182      */
 183     fib_path_list_lock(old_pl_index);
 184
 185     if (FIB_NODE_INDEX_INVALID == be->be_path_list)
 186     {
 187         old_pl_index = FIB_NODE_INDEX_INVALID;
 188         be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
 189                                                  FIB_PATH_LIST_FLAG_NO_URPF),
 190                                                 rpaths);
 191         be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
 192                                                        FIB_NODE_TYPE_BIER_ENTRY,
 193                                                        bier_entry_get_index(be));
 194     }
 195     else
 196     {
 197
 198         old_pl_index = be->be_path_list;
 199
 200         be->be_path_list =
 201             fib_path_list_copy_and_path_add(old_pl_index,
 202                                             (FIB_PATH_LIST_FLAG_SHARED |
 203                                              FIB_PATH_LIST_FLAG_NO_URPF),
 204                                             rpaths);
 205
 206         fib_path_list_child_remove(old_pl_index,
 207                                    be->be_sibling_index);
 208         be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
 209                                                        FIB_NODE_TYPE_BIER_ENTRY,
 210                                                        bier_entry_get_index(be));
 211     }
 212     /*
 213      * link the entry's bit-position to each fmask in the new path-list
 214      * then unlink from the old.
 215      */
 216     fib_path_list_walk(be->be_path_list,
 217                        bier_entry_link_walk,
 218                        be);
 219     if (FIB_NODE_INDEX_INVALID != old_pl_index)
 220     {
 221         fib_path_list_walk(old_pl_index,
 222                            bier_entry_unlink_walk,
 223                            be);
 224     }
 225
 226     /*
 227      * update the ECNP tables with the new choice
 228      */
 229     bier_table_ecmp_walk(be->be_bti,
 230                          bier_entry_table_ecmp_walk_add_fmask,
 231                          be);
 232
 233     /*
 234      * symmetric unlock. The old path-list may not exist hereinafter
 235      */
 236     fib_path_list_unlock(old_pl_index);
 237 }
 238
 239 void
 240 bier_entry_path_update (index_t bei,
 241                         const fib_route_path_t *rpaths)
 242 {
 243     fib_node_index_t old_pl_index;
 244     bier_entry_t *be;
 245
 246     be = bier_entry_get(bei);
 247     old_pl_index = be->be_path_list;
 248
 249     /*
 250      * lock the path-list so it does not go away before we unlink
 251      * from its resolved fmasks
 252      */
 253     fib_path_list_lock(old_pl_index);
 254
 255     if (FIB_NODE_INDEX_INVALID != old_pl_index)
 256     {
 257         fib_path_list_child_remove(old_pl_index,
 258                                    be->be_sibling_index);
 259     }
 260
 261     be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
 262                                              FIB_PATH_LIST_FLAG_NO_URPF),
 263                                             rpaths);
 264     be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
 265                                                    FIB_NODE_TYPE_BIER_ENTRY,
 266                                                    bier_entry_get_index(be));
 267
 268     /*
 269      * link the entry's bit-position to each fmask in the new path-list
 270      * then unlink from the old.
 271      */
 272     fib_path_list_walk(be->be_path_list,
 273                        bier_entry_link_walk,
 274                        be);
 275     if (FIB_NODE_INDEX_INVALID != old_pl_index)
 276     {
 277         fib_path_list_walk(old_pl_index,
 278                            bier_entry_unlink_walk,
 279                            be);
 280     }
 281
 282     /*
 283      * update the ECNP tables with the new choice
 284      */
 285     bier_table_ecmp_walk(be->be_bti,
 286                          bier_entry_table_ecmp_walk_add_fmask,
 287                          be);
 288
 289     /*
 290      * symmetric unlock. The old path-list may not exist hereinafter
 291      */
 292     fib_path_list_unlock(old_pl_index);
 293 }
 294
 295 int
 296 bier_entry_path_remove (index_t bei,
 297                         const fib_route_path_t *rpaths)
 298 {
 299     fib_node_index_t old_pl_index;
 300     bier_entry_t *be;
 301
 302     be = bier_entry_get(bei);
 303     old_pl_index = be->be_path_list;
 304
 305     fib_path_list_lock(old_pl_index);
 306
 307     ASSERT (FIB_NODE_INDEX_INVALID != be->be_path_list);
 308
 309     be->be_path_list =
 310         fib_path_list_copy_and_path_remove(old_pl_index,
 311                                            (FIB_PATH_LIST_FLAG_SHARED |
 312                                             FIB_PATH_LIST_FLAG_NO_URPF),
 313                                            rpaths);
 314
 315     if (be->be_path_list != old_pl_index)
 316     {
 317         /*
 318          * a path was removed
 319          */
 320         fib_path_list_child_remove(old_pl_index,
 321                                    be->be_sibling_index);
 322
 323         if (FIB_NODE_INDEX_INVALID != be->be_path_list)
 324         {
 325             /*
 326              * link the entry's bit-position to each fmask in the new path-list
 327              * then unlink from the old.
 328              */
 329             fib_path_list_walk(be->be_path_list,
 330                                bier_entry_link_walk,
 331                                be);
 332             be->be_sibling_index =
 333                 fib_path_list_child_add(be->be_path_list,
 334                                         FIB_NODE_TYPE_BIER_ENTRY,
 335                                         bier_entry_get_index(be));
 336         }
 337
 338         fib_path_list_walk(old_pl_index,
 339                            bier_entry_unlink_walk,
 340                            be);
 341     }
 342     fib_path_list_unlock(old_pl_index);
 343
 344     /*
 345      * update the ECNP tables with the new choice
 346      */
 347     bier_table_ecmp_walk(be->be_bti,
 348                          bier_entry_table_ecmp_walk_add_fmask,
 349                          be);
 350
 351     return (fib_path_list_get_n_paths(be->be_path_list));
 352 }
 353
 354 void
 355 bier_entry_contribute_forwarding(index_t bei,
 356                                  dpo_id_t *dpo)
 357 {
 358     bier_entry_t *be = bier_entry_get(bei);
 359
 360     fib_path_list_contribute_forwarding(be->be_path_list,
 361                                         FIB_FORW_CHAIN_TYPE_BIER,
 362                                         FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
 363                                         dpo);
 364 }
 365
 366 u8*
 367 format_bier_entry (u8* s, va_list *ap)
 368 {
 369     index_t bei = va_arg(*ap, index_t);
 370     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 371
 372     bier_entry_t *be = bier_entry_get(bei);
 373
 374     s = format(s, " bp:%d\n", be->be_bp);
 375     s = fib_path_list_format(be->be_path_list, s);
 376
 377     if (flags & BIER_SHOW_DETAIL)
 378     {
 379         dpo_id_t dpo = DPO_INVALID;
 380
 381         bier_entry_contribute_forwarding(bei, &dpo);
 382
 383         s = format(s, " forwarding:\n");
 384         s = format(s, "  %U",
 385                    format_dpo_id, &dpo, 2);
 386         s = format(s, "\n");
 387     }
 388
 389     return (s);
 390 }
 391
 392 static fib_node_t *
 393 bier_entry_get_node (fib_node_index_t index)
 394 {
 395     bier_entry_t *be = bier_entry_get(index);
 396     return (&(be->be_node));
 397 }
 398
 399 static bier_entry_t*
 400 bier_entry_get_from_node (fib_node_t *node)
 401 {
 402     return ((bier_entry_t*)(((char*)node) -
 403                             STRUCT_OFFSET_OF(bier_entry_t,
 404                                              be_node)));
 405 }
 406
 407 static void
 408 bier_entry_last_lock_gone (fib_node_t *node)
 409 {
 410     /*
 411      * the lifetime of the entry is managed by the table.
 412      */
 413     ASSERT(0);
 414 }
 415
 416 /*
 417  * A back walk has reached this BIER entry
 418  */
 419 static fib_node_back_walk_rc_t
 420 bier_entry_back_walk_notify (fib_node_t *node,
 421                              fib_node_back_walk_ctx_t *ctx)
 422 {
 423     /*
 424      * re-populate the ECMP tables with new choices
 425      */
 426     bier_entry_t *be = bier_entry_get_from_node(node);
 427
 428     bier_table_ecmp_walk(be->be_bti,
 429                          bier_entry_table_ecmp_walk_add_fmask,
 430                          be);
 431
 432     /*
 433      * no need to propagate further up the graph.
 434      */
 435     return (FIB_NODE_BACK_WALK_CONTINUE);
 436 }
 437
 438 /*
 439  * The BIER fmask's graph node virtual function table
 440  */
 441 static const fib_node_vft_t bier_entry_vft = {
 442     .fnv_get = bier_entry_get_node,
 443     .fnv_last_lock = bier_entry_last_lock_gone,
 444     .fnv_back_walk = bier_entry_back_walk_notify,
 445 };
 446
 447 clib_error_t *
 448 bier_entry_module_init (vlib_main_t * vm)
 449 {
 450     fib_node_register_type (FIB_NODE_TYPE_BIER_ENTRY, &bier_entry_vft);
 451
 452     return (NULL);
 453 }
 454
 455 VLIB_INIT_FUNCTION (bier_entry_module_init);