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