src/vnet/bier/bier_lookup.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/buffer.h>
  17 #include <vnet/vnet.h>
  18
  19 #include <vnet/bier/bier_fmask.h>
  20 #include <vnet/bier/bier_hdr_inlines.h>
  21 #include <vnet/bier/bier_table.h>
  22 #include <vnet/bier/bier_fmask.h>
  23
  24 /**
  25  * Struct maintining the per-worker thread data for BIER lookups
  26  */
  27 typedef struct bier_lookup_main_t_
  28 {
  29     /* per-cpu vector of cloned packets */
  30     u32 **blm_clones;
  31     /* per-cpu vector of BIER fmasks */
  32     u32 **blm_fmasks;
  33 } bier_lookup_main_t;
  34
  35 /**
  36  * Single instance of the lookup main
  37  */
  38 static bier_lookup_main_t bier_lookup_main;
  39
  40 static char * bier_lookup_error_strings[] = {
  41 #define bier_error(n,s) s,
  42 #include <vnet/bier/bier_lookup_error.def>
  43 #undef bier_error
  44 };
  45
  46 /*
  47  * Keep these values sematically the same as BIER lookup
  48  */
  49 #define foreach_bier_lookup_next                \
  50     _(DROP, "bier-drop")                        \
  51     _(OUTPUT, "bier-output")
  52
  53 typedef enum {
  54 #define _(s,n) BIER_LOOKUP_NEXT_##s,
  55     foreach_bier_lookup_next
  56 #undef _
  57     BIER_LOOKUP_N_NEXT,
  58 } bier_lookup_next_t;
  59
  60 typedef enum {
  61 #define bier_error(n,s) BIER_LOOKUP_ERROR_##n,
  62 #include <vnet/bier/bier_lookup_error.def>
  63 #undef bier_error
  64     BIER_LOOKUP_N_ERROR,
  65 } bier_lookup_error_t;
  66
  67 vlib_node_registration_t bier_lookup_node;
  68
  69 /**
  70  * @brief Packet trace recoed for a BIER lookup
  71  */
  72 typedef struct bier_lookup_trace_t_
  73 {
  74     u32 next_index;
  75     index_t bt_index;
  76     index_t bfm_index;
  77 } bier_lookup_trace_t;
  78
  79 static uword
  80 bier_lookup (vlib_main_t * vm,
  81              vlib_node_runtime_t * node,
  82              vlib_frame_t * from_frame)
  83 {
  84     u32 n_left_from, next_index, * from, * to_next;
  85     bier_lookup_main_t *blm = &bier_lookup_main;
  86     u32 thread_index = vlib_get_thread_index();
  87
  88     from = vlib_frame_vector_args (from_frame);
  89     n_left_from = from_frame->n_vectors;
  90     next_index = BIER_LOOKUP_NEXT_DROP;
  91
  92     while (n_left_from > 0)
  93     {
  94         u32 n_left_to_next;
  95
  96         vlib_get_next_frame (vm, node, next_index,
  97                              to_next, n_left_to_next);
  98
  99         while (n_left_from > 0 && n_left_to_next > 0)
 100         {
 101             bier_bit_mask_bucket_t buckets_copy[BIER_HDR_BUCKETS_256];
 102             u32 next0, bi0, n_bytes, bti0, bfmi0;
 103             const bier_fmask_t *bfm0;
 104             const bier_table_t *bt0;
 105             u16 index, num_buckets;
 106             const bier_hdr_t *bh0;
 107             bier_bit_string_t bbs;
 108             vlib_buffer_t *b0;
 109             bier_bp_t fbs;
 110             int bucket;
 111
 112             bi0 = from[0];
 113             from += 1;
 114             n_left_from -= 1;
 115
 116             b0 = vlib_get_buffer (vm, bi0);
 117             bh0 = vlib_buffer_get_current (b0);
 118             bti0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
 119
 120             /*
 121              * default to drop so that if no bits are matched then
 122              * that is where we go - DROP.
 123              */
 124             next0 = BIER_LOOKUP_NEXT_DROP;
 125
 126             /*
 127              * At the imposition or input node,
 128              * we stored the BIER Table index in the TX adjacency
 129              */
 130             bt0 = bier_table_get(vnet_buffer(b0)->ip.adj_index[VLIB_TX]);
 131
 132             /*
 133              * we should only forward via one for the ECMP tables
 134              */
 135             ASSERT(!bier_table_is_main(bt0));
 136
 137             /*
 138              * number of integer sized buckets
 139              */
 140             n_bytes = bier_hdr_len_id_to_num_buckets(bt0->bt_id.bti_hdr_len);
 141             vnet_buffer(b0)->bier.n_bytes = n_bytes;
 142             vnet_buffer(b0)->sw_if_index[VLIB_TX] = ~0;
 143             num_buckets = n_bytes / sizeof(int);
 144             bier_bit_string_init(&bbs,
 145                                  bt0->bt_id.bti_hdr_len,
 146                                  buckets_copy);
 147             memcpy(bbs.bbs_buckets, bh0->bh_bit_string, bbs.bbs_len);
 148
 149             /*
 150              * reset the fmask and clone storage vectors
 151              */
 152             vec_reset_length (blm->blm_fmasks[thread_index]);
 153             vec_reset_length (blm->blm_clones[thread_index]);
 154
 155             /*
 156              * Loop through the buckets in the header
 157              */
 158             for (index = 0; index < num_buckets; index++) {
 159                 /*
 160                  * loop through each bit in the bucket
 161                  */
 162                 bucket = ((int*)bbs.bbs_buckets)[index];
 163
 164                 while (bucket) {
 165                     fbs  = bier_find_first_bit_string_set(bucket);
 166                     fbs += (((num_buckets - 1) - index) *
 167                             BIER_BIT_MASK_BITS_PER_INT);
 168
 169                     bfmi0 = bier_table_fwd_lookup(bt0, fbs);
 170
 171                     /*
 172                      * whatever happens, the bit we just looked for
 173                      * MUST be cleared from the packet
 174                      * otherwise we could be in this loop a while ...
 175                      */
 176                     bier_bit_string_clear_bit(&bbs, fbs);
 177
 178                     if (PREDICT_TRUE(INDEX_INVALID != bfmi0))
 179                     {
 180                         bfm0 = bier_fmask_get(bfmi0);
 181                         vnet_buffer (b0)->ip.adj_index[VLIB_TX] = bfmi0;
 182
 183                         /*
 184                          * use the bit-string on the fmask to reset
 185                          * the bits in the header we are walking
 186                          */
 187                         bier_bit_string_clear_string(
 188                             &bfm0->bfm_bits.bfmb_input_reset_string,
 189                             &bbs);
 190                         bucket = ((int*)bbs.bbs_buckets)[index];
 191
 192                         /*
 193                          * the fmask is resolved so replicate a
 194                          * packet its way
 195                          */
 196                         next0 = BIER_LOOKUP_NEXT_OUTPUT;
 197
 198                         vec_add1 (blm->blm_fmasks[thread_index], bfmi0);
 199                     } else {
 200                         /*
 201                          * go to the next bit-position set
 202                          */
 203                         bucket = ((int*)bbs.bbs_buckets)[index];
 204                         continue;
 205                     }
 206                 }
 207             }
 208
 209             /*
 210              * Full mask now processed.
 211              * Create the number of clones we need based on the number
 212              * of fmasks we are sending to.
 213              */
 214             u8 num_cloned, clone;
 215             u32 n_clones;
 216
 217             n_clones = vec_len(blm->blm_fmasks[thread_index]);
 218
 219             if (PREDICT_TRUE(0 != n_clones))
 220             {
 221                 ASSERT(n_clones < 256);
 222                 num_cloned = vlib_buffer_clone(vm, bi0,
 223                                                blm->blm_clones[thread_index],
 224                                                n_clones, 128);
 225
 226                 if (num_cloned != n_clones)
 227                 {
 228                     vlib_node_increment_counter
 229                         (vm, node->node_index,
 230                          BIER_LOOKUP_ERROR_BUFFER_ALLOCATION_FAILURE, 1);
 231                 }
 232
 233                 for (clone = 0; clone < num_cloned; clone++)
 234                 {
 235                     vlib_buffer_t *c0;
 236                     u32 ci0;
 237
 238                     ci0 = blm->blm_clones[thread_index][clone];
 239                     c0 = vlib_get_buffer(vm, ci0);
 240
 241                     to_next[0] = ci0;
 242                     to_next += 1;
 243                     n_left_to_next -= 1;
 244
 245                     if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
 246                     {
 247                         bier_lookup_trace_t *tr;
 248
 249                         vlib_trace_buffer (vm, node, next0, c0, 0);
 250                         tr = vlib_add_trace (vm, node, c0, sizeof (*tr));
 251                         tr->bt_index = bti0;
 252                         tr->bfm_index = blm->blm_fmasks[thread_index][clone];
 253
 254                         c0->flags |= VLIB_BUFFER_IS_TRACED;
 255                     }
 256
 257                     vlib_validate_buffer_enqueue_x1(vm, node, next_index,
 258                                                     to_next, n_left_to_next,
 259                                                     ci0, next0);
 260
 261                     /*
 262                      * After the enqueue it is possible that we over-flow the
 263                      * frame of the to-next node. When this happens we need to
 264                      * 'put' that full frame to the node and get a fresh empty
 265                      * one. Note that these are macros with side effects that
 266                      * change to_next & n_left_to_next
 267                      */
 268                     if (PREDICT_FALSE(0 == n_left_to_next))
 269                     {
 270                         vlib_put_next_frame (vm, node, next_index,
 271                                              n_left_to_next);
 272                         vlib_get_next_frame (vm, node, next_index,
 273                                              to_next, n_left_to_next);
 274                     }
 275                 }
 276             }
 277             else
 278             {
 279                 /*
 280                  * no clones/replications required. drop this packet
 281                  */
 282                 next0 = BIER_LOOKUP_NEXT_DROP;
 283                 to_next[0] = bi0;
 284                 to_next += 1;
 285                 n_left_to_next -= 1;
 286
 287                 if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
 288                 {
 289                     bier_lookup_trace_t *tr;
 290
 291                     tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
 292
 293                     tr->bt_index = bti0;
 294                     tr->bfm_index = ~0;
 295                 }
 296
 297                 vlib_validate_buffer_enqueue_x1(vm, node, next_index,
 298                                                 to_next, n_left_to_next,
 299                                                 bi0, next0);
 300             }
 301         }
 302
 303         vlib_put_next_frame (vm, node, next_index, n_left_to_next);
 304     }
 305
 306     vlib_node_increment_counter (vm, bier_lookup_node.index,
 307                                  BIER_LOOKUP_ERROR_NONE,
 308                                  from_frame->n_vectors);
 309     return (from_frame->n_vectors);
 310 }
 311
 312 static u8 *
 313 format_bier_lookup_trace (u8 * s, va_list * args)
 314 {
 315     CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
 316     CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
 317     bier_lookup_trace_t * t = va_arg (*args, bier_lookup_trace_t *);
 318
 319     s = format (s, "BIER: next [%d], tbl:%d BFM:%d",
 320                 t->next_index,
 321                 t->bt_index,
 322                 t->bfm_index);
 323     return s;
 324 }
 325
 326 VLIB_REGISTER_NODE (bier_lookup_node) = {
 327     .function = bier_lookup,
 328     .name = "bier-lookup",
 329     /* Takes a vector of packets. */
 330     .vector_size = sizeof (u32),
 331
 332     .n_errors = BIER_LOOKUP_N_ERROR,
 333     .error_strings = bier_lookup_error_strings,
 334
 335     .format_trace = format_bier_lookup_trace,
 336     .n_next_nodes = BIER_LOOKUP_N_NEXT,
 337     .next_nodes = {
 338         [BIER_LOOKUP_NEXT_DROP] = "bier-drop",
 339         [BIER_LOOKUP_NEXT_OUTPUT] = "bier-output",
 340     },
 341 };
 342
 343 clib_error_t *
 344 bier_lookup_module_init (vlib_main_t * vm)
 345 {
 346     bier_lookup_main_t *blm = &bier_lookup_main;
 347     u32 thread_index;
 348
 349     vec_validate (blm->blm_clones, vlib_num_workers());
 350     vec_validate (blm->blm_fmasks, vlib_num_workers());
 351
 352     for (thread_index = 0;
 353          thread_index <= vlib_num_workers();
 354          thread_index++)
 355     {
 356         /*
 357          *  4096 is the most we will ever need to support
 358          * a Bit-Mask length of 4096
 359          */
 360         vec_validate(blm->blm_fmasks[thread_index], 4095);
 361         vec_validate(blm->blm_clones[thread_index], 4095);
 362     }
 363
 364     return 0;
 365 }
 366
 367 VLIB_INIT_FUNCTION (bier_lookup_module_init);