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 void
  77 bier_entry_delete (index_t bei)
  78 {
  79     bier_entry_t *be;
  80
  81     be = bier_entry_get(bei);
  82
  83     /*
  84      * if we still ahve a path-list, unlink from it
  85      */
  86     if (FIB_NODE_INDEX_INVALID != be->be_path_list)
  87     {
  88         fib_path_list_walk(be->be_path_list,
  89                            bier_entry_unlink_walk,
  90                            be);
  91         fib_path_list_child_remove(be->be_path_list,
  92                                    be->be_sibling_index);
  93     }
  94
  95     pool_put(bier_entry_pool, be);
  96 }
  97
  98 static void
  99 bier_entry_table_ecmp_walk_add_fmask (index_t btei,
 100                                       void *arg)
 101 {
 102     bier_entry_t *be = arg;;
 103
 104     /*
 105      * choose a fmask from the entry's resolved set to add
 106      * to ECMP table's lookup table
 107      */
 108     if (FIB_NODE_INDEX_INVALID != be->be_path_list)
 109     {
 110         const bier_table_id_t *btid;
 111         dpo_id_t dpo = DPO_INVALID;
 112         const dpo_id_t *choice;
 113         load_balance_t *lb;
 114
 115         btid = bier_table_get_id(btei);
 116
 117         fib_path_list_contribute_forwarding(be->be_path_list,
 118                                             FIB_FORW_CHAIN_TYPE_BIER,
 119                                             &dpo);
 120
 121         /*
 122          * select the appropriate bucket from the LB
 123          */
 124         ASSERT(dpo.dpoi_type == DPO_LOAD_BALANCE);
 125
 126         lb = load_balance_get(dpo.dpoi_index);
 127
 128         choice = load_balance_get_bucket_i(lb,
 129                                            btid->bti_ecmp &
 130                                            (lb->lb_n_buckets_minus_1));
 131
 132         if (choice->dpoi_type == DPO_BIER_FMASK)
 133         {
 134             bier_table_ecmp_set_fmask(btei, be->be_bp,
 135                                       choice->dpoi_index);
 136         }
 137         else
 138         {
 139             /*
 140              * any other type results in a drop, which we represent
 141              * with an empty bucket
 142              */
 143             bier_table_ecmp_set_fmask(btei, be->be_bp,
 144                                       INDEX_INVALID);
 145         }
 146
 147         dpo_reset(&dpo);
 148     }
 149     else
 150     {
 151         /*
 152          * no fmasks left. insert a drop
 153          */
 154         bier_table_ecmp_set_fmask(btei, be->be_bp, INDEX_INVALID);
 155     }
 156 }
 157
 158 void
 159 bier_entry_path_add (index_t bei,
 160                      const fib_route_path_t *rpaths)
 161 {
 162     fib_node_index_t old_pl_index;
 163     bier_entry_t *be;
 164
 165     be = bier_entry_get(bei);
 166     old_pl_index = be->be_path_list;
 167
 168     /*
 169      * lock the path-list so it does not go away before we unlink
 170      * from its resolved fmasks
 171      */
 172     fib_path_list_lock(old_pl_index);
 173
 174     if (FIB_NODE_INDEX_INVALID == be->be_path_list)
 175     {
 176         old_pl_index = FIB_NODE_INDEX_INVALID;
 177         be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
 178                                                  FIB_PATH_LIST_FLAG_NO_URPF),
 179                                                 rpaths);
 180         be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
 181                                                        FIB_NODE_TYPE_BIER_ENTRY,
 182                                                        bier_entry_get_index(be));
 183     }
 184     else
 185     {
 186
 187         old_pl_index = be->be_path_list;
 188
 189         be->be_path_list =
 190             fib_path_list_copy_and_path_add(old_pl_index,
 191                                             (FIB_PATH_LIST_FLAG_SHARED |
 192                                              FIB_PATH_LIST_FLAG_NO_URPF),
 193                                             rpaths);
 194
 195         fib_path_list_child_remove(old_pl_index,
 196                                    be->be_sibling_index);
 197         be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
 198                                                        FIB_NODE_TYPE_BIER_ENTRY,
 199                                                        bier_entry_get_index(be));
 200     }
 201     /*
 202      * link the entry's bit-position to each fmask in the new path-list
 203      * then unlink from the old.
 204      */
 205     fib_path_list_walk(be->be_path_list,
 206                        bier_entry_link_walk,
 207                        be);
 208     if (FIB_NODE_INDEX_INVALID != old_pl_index)
 209     {
 210         fib_path_list_walk(old_pl_index,
 211                            bier_entry_unlink_walk,
 212                            be);
 213     }
 214
 215     /*
 216      * update the ECNP tables with the new choice
 217      */
 218     bier_table_ecmp_walk(be->be_bti,
 219                          bier_entry_table_ecmp_walk_add_fmask,
 220                          be);
 221
 222     /*
 223      * symmetric unlock. The old path-list may not exist hereinafter
 224      */
 225     fib_path_list_unlock(old_pl_index);
 226 }
 227
 228 int
 229 bier_entry_path_remove (index_t bei,
 230                         const fib_route_path_t *rpaths)
 231 {
 232     fib_node_index_t old_pl_index;
 233     bier_entry_t *be;
 234
 235     be = bier_entry_get(bei);
 236     old_pl_index = be->be_path_list;
 237
 238     fib_path_list_lock(old_pl_index);
 239
 240     ASSERT (FIB_NODE_INDEX_INVALID != be->be_path_list);
 241
 242     be->be_path_list =
 243         fib_path_list_copy_and_path_remove(old_pl_index,
 244                                            (FIB_PATH_LIST_FLAG_SHARED |
 245                                             FIB_PATH_LIST_FLAG_NO_URPF),
 246                                            rpaths);
 247
 248     if (be->be_path_list != old_pl_index)
 249     {
 250         /*
 251          * a path was removed
 252          */
 253         fib_path_list_child_remove(old_pl_index,
 254                                    be->be_sibling_index);
 255
 256         if (FIB_NODE_INDEX_INVALID != be->be_path_list)
 257         {
 258             /*
 259              * link the entry's bit-position to each fmask in the new path-list
 260              * then unlink from the old.
 261              */
 262             fib_path_list_walk(be->be_path_list,
 263                                bier_entry_link_walk,
 264                                be);
 265             be->be_sibling_index =
 266                 fib_path_list_child_add(be->be_path_list,
 267                                         FIB_NODE_TYPE_BIER_ENTRY,
 268                                         bier_entry_get_index(be));
 269         }
 270
 271         fib_path_list_walk(old_pl_index,
 272                            bier_entry_unlink_walk,
 273                            be);
 274     }
 275     fib_path_list_unlock(old_pl_index);
 276
 277
 278     /*
 279      * update the ECNP tables with the new choice
 280      */
 281     bier_table_ecmp_walk(be->be_bti,
 282                          bier_entry_table_ecmp_walk_add_fmask,
 283                          be);
 284
 285     return (fib_path_list_get_n_paths(be->be_path_list));
 286 }
 287
 288 void
 289 bier_entry_contribute_forwarding(index_t bei,
 290                                  dpo_id_t *dpo)
 291 {
 292     bier_entry_t *be = bier_entry_get(bei);
 293
 294     fib_path_list_contribute_forwarding(be->be_path_list,
 295                                         FIB_FORW_CHAIN_TYPE_BIER,
 296                                         dpo);
 297 }
 298
 299 u8*
 300 format_bier_entry (u8* s, va_list *ap)
 301 {
 302     index_t bei = va_arg(*ap, index_t);
 303     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 304
 305     bier_entry_t *be = bier_entry_get(bei);
 306
 307     s = format(s, " bp:%d\n", be->be_bp);
 308     s = fib_path_list_format(be->be_path_list, s);
 309
 310     if (flags & BIER_SHOW_DETAIL)
 311     {
 312         dpo_id_t dpo = DPO_INVALID;
 313
 314         bier_entry_contribute_forwarding(bei, &dpo);
 315
 316         s = format(s, " forwarding:\n");
 317         s = format(s, "  %U",
 318                    format_dpo_id, &dpo, 2);
 319         s = format(s, "\n");
 320     }
 321
 322     return (s);
 323 }
 324
 325 static fib_node_t *
 326 bier_entry_get_node (fib_node_index_t index)
 327 {
 328     bier_entry_t *be = bier_entry_get(index);
 329     return (&(be->be_node));
 330 }
 331
 332 static bier_entry_t*
 333 bier_entry_get_from_node (fib_node_t *node)
 334 {
 335     return ((bier_entry_t*)(((char*)node) -
 336                             STRUCT_OFFSET_OF(bier_entry_t,
 337                                              be_node)));
 338 }
 339
 340 static void
 341 bier_entry_last_lock_gone (fib_node_t *node)
 342 {
 343     /*
 344      * the lifetime of the entry is managed by the table.
 345      */
 346     ASSERT(0);
 347 }
 348
 349 /*
 350  * A back walk has reached this BIER entry
 351  */
 352 static fib_node_back_walk_rc_t
 353 bier_entry_back_walk_notify (fib_node_t *node,
 354                              fib_node_back_walk_ctx_t *ctx)
 355 {
 356     /*
 357      * re-populate the ECMP tables with new choices
 358      */
 359     bier_entry_t *be = bier_entry_get_from_node(node);
 360
 361     bier_table_ecmp_walk(be->be_bti,
 362                          bier_entry_table_ecmp_walk_add_fmask,
 363                          be);
 364
 365     /*
 366      * no need to propagate further up the graph.
 367      */
 368     return (FIB_NODE_BACK_WALK_CONTINUE);
 369 }
 370
 371 /*
 372  * The BIER fmask's graph node virtual function table
 373  */
 374 static const fib_node_vft_t bier_entry_vft = {
 375     .fnv_get = bier_entry_get_node,
 376     .fnv_last_lock = bier_entry_last_lock_gone,
 377     .fnv_back_walk = bier_entry_back_walk_notify,
 378 };
 379
 380 clib_error_t *
 381 bier_entry_module_init (vlib_main_t * vm)
 382 {
 383     fib_node_register_type (FIB_NODE_TYPE_BIER_ENTRY, &bier_entry_vft);
 384
 385     return (NULL);
 386 }
 387
 388 VLIB_INIT_FUNCTION (bier_entry_module_init);