src/vnet/bier/bier_fmask.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/fib/fib_entry.h>
  17 #include <vnet/fib/fib_table.h>
  18 #include <vnet/fib/fib_walk.h>
  19 #include <vnet/fib/fib_path_list.h>
  20
  21 #include <vnet/bier/bier_table.h>
  22 #include <vnet/bier/bier_fmask.h>
  23 #include <vnet/bier/bier_bit_string.h>
  24 #include <vnet/bier/bier_disp_table.h>
  25
  26 #include <vnet/mpls/mpls.h>
  27 #include <vnet/dpo/drop_dpo.h>
  28 #include <vnet/dpo/load_balance.h>
  29
  30 /*
  31  * attributes names for formatting
  32  */
  33 static const char *const bier_fmask_attr_names[] = BIER_FMASK_ATTR_NAMES;
  34
  35 /*
  36  * pool of BIER fmask objects
  37  */
  38 bier_fmask_t *bier_fmask_pool;
  39
  40 static inline index_t
  41 bier_fmask_get_index (const bier_fmask_t *bfm)
  42 {
  43     return (bfm - bier_fmask_pool);
  44 }
  45
  46 static void
  47 bier_fmask_bits_init (bier_fmask_bits_t *bits,
  48                       bier_hdr_len_id_t hlid)
  49 {
  50     bits->bfmb_refs = clib_mem_alloc(sizeof(bits->bfmb_refs[0]) *
  51                                      bier_hdr_len_id_to_num_bits(hlid));
  52     memset(bits->bfmb_refs,
  53            0,
  54            (sizeof(bits->bfmb_refs[0]) *
  55             bier_hdr_len_id_to_num_bits(hlid)));
  56
  57     bits->bfmb_input_reset_string.bbs_len =
  58         bier_hdr_len_id_to_num_buckets(hlid);
  59
  60     /*
  61      * The buckets are accessed in the switch path
  62      */
  63     bits->bfmb_input_reset_string.bbs_buckets =
  64         clib_mem_alloc_aligned(
  65             sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
  66             bier_hdr_len_id_to_num_buckets(hlid),
  67             CLIB_CACHE_LINE_BYTES);
  68     memset(bits->bfmb_input_reset_string.bbs_buckets,
  69            0,
  70            sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
  71            bier_hdr_len_id_to_num_buckets(hlid));
  72 }
  73
  74 static void
  75 bier_fmask_stack (bier_fmask_t *bfm)
  76 {
  77     dpo_id_t via_dpo = DPO_INVALID;
  78     fib_forward_chain_type_t fct;
  79
  80     if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
  81     {
  82         fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
  83     }
  84     else
  85     {
  86         fct = FIB_FORW_CHAIN_TYPE_BIER;
  87     }
  88
  89     fib_path_list_contribute_forwarding(bfm->bfm_pl, fct,
  90                                         FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
  91                                         &via_dpo);
  92
  93     /*
  94      * If the via PL entry provides no forwarding (i.e. a drop)
  95      * then neither does this fmask. That way children consider this fmask
  96      * unresolved and other ECMP options are used instead.
  97      */
  98     if (dpo_is_drop(&via_dpo))
  99     {
 100         bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING;
 101     }
 102     else
 103     {
 104         bfm->bfm_flags |= BIER_FMASK_FLAG_FORWARDING;
 105     }
 106
 107     dpo_stack(DPO_BIER_FMASK,
 108               DPO_PROTO_BIER,
 109               &bfm->bfm_dpo,
 110               &via_dpo);
 111     dpo_reset(&via_dpo);
 112 }
 113
 114 void
 115 bier_fmask_contribute_forwarding (index_t bfmi,
 116                                   dpo_id_t *dpo)
 117 {
 118     bier_fmask_t *bfm;
 119
 120     bfm = bier_fmask_get(bfmi);
 121
 122     if (bfm->bfm_flags & BIER_FMASK_FLAG_FORWARDING)
 123     {
 124         dpo_set(dpo,
 125                 DPO_BIER_FMASK,
 126                 DPO_PROTO_BIER,
 127                 bfmi);
 128     }
 129     else
 130     {
 131         dpo_copy(dpo, drop_dpo_get(DPO_PROTO_BIER));
 132     }
 133 }
 134
 135 u32
 136 bier_fmask_child_add (fib_node_index_t bfmi,
 137                      fib_node_type_t child_type,
 138                      fib_node_index_t child_index)
 139 {
 140     return (fib_node_child_add(FIB_NODE_TYPE_BIER_FMASK,
 141                                bfmi,
 142                                child_type,
 143                                child_index));
 144 };
 145
 146 void
 147 bier_fmask_child_remove (fib_node_index_t bfmi,
 148                          u32 sibling_index)
 149 {
 150     if (INDEX_INVALID == bfmi)
 151     {
 152         return;
 153     }
 154
 155     fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK,
 156                           bfmi,
 157                           sibling_index);
 158 }
 159
 160 static void
 161 bier_fmask_init (bier_fmask_t *bfm,
 162                  const bier_fmask_id_t *fmid,
 163                  const fib_route_path_t *rpaths)
 164 {
 165     const bier_table_id_t *btid;
 166     mpls_label_t olabel;
 167
 168     *bfm->bfm_id = *fmid;
 169     dpo_reset(&bfm->bfm_dpo);
 170     btid = bier_table_get_id(bfm->bfm_id->bfmi_bti);
 171     bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len);
 172
 173     if (ip46_address_is_zero(&(bfm->bfm_id->bfmi_nh)))
 174     {
 175         bfm->bfm_flags |= BIER_FMASK_FLAG_DISP;
 176     }
 177
 178     if (!(bfm->bfm_flags & BIER_FMASK_FLAG_DISP))
 179     {
 180         if (NULL != rpaths->frp_label_stack)
 181         {
 182             olabel = rpaths->frp_label_stack[0].fml_value;
 183             vnet_mpls_uc_set_label(&bfm->bfm_label, olabel);
 184             vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
 185             vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
 186             vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
 187             bfm->bfm_flags |= BIER_FMASK_FLAG_MPLS;
 188         }
 189         else
 190         {
 191             bier_bift_id_t id;
 192
 193             /*
 194              * not an MPLS label
 195              */
 196             bfm->bfm_flags &= ~BIER_FMASK_FLAG_MPLS;
 197
 198             /*
 199              * use a label as encoded for BIFT value
 200              */
 201             id = bier_bift_id_encode(btid->bti_set,
 202                                      btid->bti_sub_domain,
 203                                      btid->bti_hdr_len);
 204             vnet_mpls_uc_set_label(&bfm->bfm_label, id);
 205             vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
 206             vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
 207             vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
 208         }
 209         bfm->bfm_label = clib_host_to_net_u32(bfm->bfm_label);
 210     }
 211
 212     bfm->bfm_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
 213                                         FIB_PATH_LIST_FLAG_NO_URPF),
 214                                        rpaths);
 215     bfm->bfm_sibling = fib_path_list_child_add(bfm->bfm_pl,
 216                                                FIB_NODE_TYPE_BIER_FMASK,
 217                                                bier_fmask_get_index(bfm));
 218
 219     bier_fmask_stack(bfm);
 220 }
 221
 222 static void
 223 bier_fmask_destroy (bier_fmask_t *bfm)
 224 {
 225     clib_mem_free(bfm->bfm_bits.bfmb_refs);
 226     clib_mem_free(bfm->bfm_bits.bfmb_input_reset_string.bbs_buckets);
 227
 228     bier_fmask_db_remove(bfm->bfm_id);
 229     fib_path_list_child_remove(bfm->bfm_pl,
 230                                bfm->bfm_sibling);
 231     dpo_reset(&bfm->bfm_dpo);
 232     clib_mem_free(bfm->bfm_id);
 233     pool_put(bier_fmask_pool, bfm);
 234 }
 235
 236 void
 237 bier_fmask_unlock (index_t bfmi)
 238 {
 239     bier_fmask_t *bfm;
 240
 241     if (INDEX_INVALID == bfmi)
 242     {
 243         return;
 244     }
 245
 246     bfm = bier_fmask_get(bfmi);
 247
 248     fib_node_unlock(&bfm->bfm_node);
 249 }
 250
 251 void
 252 bier_fmask_lock (index_t bfmi)
 253 {
 254     bier_fmask_t *bfm;
 255
 256     if (INDEX_INVALID == bfmi)
 257     {
 258         return;
 259     }
 260
 261     bfm = bier_fmask_get(bfmi);
 262
 263     fib_node_lock(&bfm->bfm_node);
 264 }
 265
 266 index_t
 267 bier_fmask_create_and_lock (const bier_fmask_id_t *fmid,
 268                             const fib_route_path_t *rpaths)
 269 {
 270     bier_fmask_t *bfm;
 271
 272     pool_get_aligned(bier_fmask_pool, bfm, CLIB_CACHE_LINE_BYTES);
 273
 274     memset(bfm, 0, sizeof(*bfm));
 275
 276     bfm->bfm_id = clib_mem_alloc(sizeof(*bfm->bfm_id));
 277
 278     ASSERT(1 == vec_len(rpaths));
 279     fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK);
 280     bier_fmask_init(bfm, fmid, rpaths);
 281
 282     bier_fmask_lock(bier_fmask_get_index(bfm));
 283
 284     return (bier_fmask_get_index(bfm));
 285 }
 286
 287 void
 288 bier_fmask_link (index_t bfmi,
 289                  bier_bp_t bp)
 290 {
 291     bier_fmask_t *bfm;
 292
 293     bfm = bier_fmask_get(bfmi);
 294
 295     if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
 296     {
 297         /*
 298          * 0 -> 1 transistion - set the bit in the string
 299          */
 300         bier_bit_string_set_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
 301     }
 302
 303     ++bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
 304     ++bfm->bfm_bits.bfmb_count;
 305 }
 306
 307 void
 308 bier_fmask_unlink (index_t bfmi,
 309                    bier_bp_t bp)
 310 {
 311     bier_fmask_t *bfm;
 312
 313     bfm = bier_fmask_get(bfmi);
 314
 315     --bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
 316     --bfm->bfm_bits.bfmb_count;
 317
 318     if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
 319     {
 320         /*
 321          * 1 -> 0 transistion - clear the bit in the string
 322          */
 323         bier_bit_string_clear_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
 324     }
 325 }
 326
 327 u8*
 328 format_bier_fmask (u8 *s, va_list *ap)
 329 {
 330     index_t bfmi = va_arg(*ap, index_t);
 331     u32 indent = va_arg(*ap, u32);
 332     bier_fmask_attributes_t attr;
 333     bier_fmask_t *bfm;
 334
 335     if (pool_is_free_index(bier_fmask_pool, bfmi))
 336     {
 337         return (format(s, "No BIER f-mask %d", bfmi));
 338     }
 339
 340     bfm = bier_fmask_get(bfmi);
 341
 342     s = format(s, "fmask: nh:%U bs:%U locks:%d ",
 343                format_ip46_address, &bfm->bfm_id->bfmi_nh, IP46_TYPE_ANY,
 344                format_bier_bit_string, &bfm->bfm_bits.bfmb_input_reset_string,
 345                bfm->bfm_node.fn_locks);
 346     s = format(s, "flags:");
 347     FOR_EACH_BIER_FMASK_ATTR(attr) {
 348         if ((1<<attr) & bfm->bfm_flags) {
 349             s = format (s, "%s,", bier_fmask_attr_names[attr]);
 350         }
 351     }
 352     s = format(s, "\n");
 353     s = fib_path_list_format(bfm->bfm_pl, s);
 354
 355     if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
 356     {
 357         s = format(s, "  output-label:%U",
 358                    format_mpls_unicast_label,
 359                    vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
 360     }
 361     else
 362     {
 363         s = format(s, "  output-bfit:[%U]",
 364                    format_bier_bift_id,
 365                    vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
 366     }
 367     s = format(s, "\n %U%U",
 368                format_white_space, indent,
 369                format_dpo_id, &bfm->bfm_dpo, indent+2);
 370
 371     return (s);
 372 }
 373
 374
 375 static fib_node_t *
 376 bier_fmask_get_node (fib_node_index_t index)
 377 {
 378     bier_fmask_t *bfm = bier_fmask_get(index);
 379     return (&(bfm->bfm_node));
 380 }
 381
 382 static bier_fmask_t*
 383 bier_fmask_get_from_node (fib_node_t *node)
 384 {
 385     return ((bier_fmask_t*)(((char*)node) -
 386                             STRUCT_OFFSET_OF(bier_fmask_t,
 387                                              bfm_node)));
 388 }
 389
 390 /*
 391  * bier_fmask_last_lock_gone
 392  */
 393 static void
 394 bier_fmask_last_lock_gone (fib_node_t *node)
 395 {
 396     bier_fmask_destroy(bier_fmask_get_from_node(node));
 397 }
 398
 399 /*
 400  * bier_fmask_back_walk_notify
 401  *
 402  * A back walk has reached this BIER fmask
 403  */
 404 static fib_node_back_walk_rc_t
 405 bier_fmask_back_walk_notify (fib_node_t *node,
 406                              fib_node_back_walk_ctx_t *ctx)
 407 {
 408     /*
 409      * re-stack the fmask on the n-eos of the via
 410      */
 411     bier_fmask_t *bfm = bier_fmask_get_from_node(node);
 412
 413     bier_fmask_stack(bfm);
 414
 415     /*
 416      * propagate further up the graph.
 417      * we can do this synchronously since the fan out is small.
 418      */
 419     fib_walk_sync(FIB_NODE_TYPE_BIER_FMASK, bier_fmask_get_index(bfm), ctx);
 420
 421     return (FIB_NODE_BACK_WALK_CONTINUE);
 422 }
 423
 424 /*
 425  * The BIER fmask's graph node virtual function table
 426  */
 427 static const fib_node_vft_t bier_fmask_vft = {
 428     .fnv_get = bier_fmask_get_node,
 429     .fnv_last_lock = bier_fmask_last_lock_gone,
 430     .fnv_back_walk = bier_fmask_back_walk_notify,
 431 };
 432
 433 static void
 434 bier_fmask_dpo_lock (dpo_id_t *dpo)
 435 {
 436 }
 437
 438 static void
 439 bier_fmask_dpo_unlock (dpo_id_t *dpo)
 440 {
 441 }
 442
 443 static void
 444 bier_fmask_dpo_mem_show (void)
 445 {
 446     fib_show_memory_usage("BIER-fmask",
 447                           pool_elts(bier_fmask_pool),
 448                           pool_len(bier_fmask_pool),
 449                           sizeof(bier_fmask_t));
 450 }
 451
 452 const static dpo_vft_t bier_fmask_dpo_vft = {
 453     .dv_lock = bier_fmask_dpo_lock,
 454     .dv_unlock = bier_fmask_dpo_unlock,
 455     .dv_mem_show = bier_fmask_dpo_mem_show,
 456     .dv_format = format_bier_fmask,
 457 };
 458
 459 const static char *const bier_fmask_mpls_nodes[] =
 460 {
 461     "bier-output",
 462     NULL
 463 };
 464 const static char * const * const bier_fmask_nodes[DPO_PROTO_NUM] =
 465 {
 466     [DPO_PROTO_BIER] = bier_fmask_mpls_nodes,
 467     [DPO_PROTO_MPLS] = bier_fmask_mpls_nodes,
 468 };
 469
 470 clib_error_t *
 471 bier_fmask_module_init (vlib_main_t * vm)
 472 {
 473     fib_node_register_type (FIB_NODE_TYPE_BIER_FMASK, &bier_fmask_vft);
 474     dpo_register(DPO_BIER_FMASK, &bier_fmask_dpo_vft, bier_fmask_nodes);
 475
 476     return (NULL);
 477 }
 478
 479 VLIB_INIT_FUNCTION (bier_fmask_module_init);
 480
 481 static clib_error_t *
 482 bier_fmask_show (vlib_main_t * vm,
 483                  unformat_input_t * input,
 484                  vlib_cli_command_t * cmd)
 485 {
 486     bier_fmask_t *bfm;
 487     index_t bfmi;
 488
 489     bfmi = INDEX_INVALID;
 490
 491     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
 492         if (unformat (input, "%d", &bfmi))
 493         {
 494             ;
 495         } else
 496         {
 497             break;
 498         }
 499     }
 500
 501     if (INDEX_INVALID == bfmi)
 502     {
 503         pool_foreach(bfm, bier_fmask_pool,
 504         ({
 505             vlib_cli_output (vm, "[@%d] %U",
 506                              bier_fmask_get_index(bfm),
 507                              format_bier_fmask, bier_fmask_get_index(bfm), 0);
 508         }));
 509     }
 510     else
 511     {
 512         vlib_cli_output (vm, "%U", format_bier_fmask, bfmi, 0);
 513     }
 514
 515     return (NULL);
 516 }
 517
 518 VLIB_CLI_COMMAND (show_bier_fmask, static) = {
 519     .path = "show bier fmask",
 520     .short_help = "show bier fmask",
 521     .function = bier_fmask_show,
 522 };