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