Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 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(); |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 87 | bier_bit_mask_bucket_t buckets_copy[BIER_HDR_BUCKETS_4096]; |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 88 | |
| 89 | from = vlib_frame_vector_args (from_frame); |
| 90 | n_left_from = from_frame->n_vectors; |
| 91 | next_index = BIER_LOOKUP_NEXT_DROP; |
| 92 | |
| 93 | while (n_left_from > 0) |
| 94 | { |
| 95 | u32 n_left_to_next; |
| 96 | |
| 97 | vlib_get_next_frame (vm, node, next_index, |
| 98 | to_next, n_left_to_next); |
| 99 | |
| 100 | while (n_left_from > 0 && n_left_to_next > 0) |
| 101 | { |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 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); |
Neale Ranns | 9128637 | 2017-12-05 13:24:04 -0800 | [diff] [blame] | 141 | vnet_buffer(b0)->mpls.bier.n_bytes = n_bytes; |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 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); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 181 | |
| 182 | /* |
| 183 | * use the bit-string on the fmask to reset |
| 184 | * the bits in the header we are walking |
| 185 | */ |
| 186 | bier_bit_string_clear_string( |
| 187 | &bfm0->bfm_bits.bfmb_input_reset_string, |
| 188 | &bbs); |
| 189 | bucket = ((int*)bbs.bbs_buckets)[index]; |
| 190 | |
| 191 | /* |
| 192 | * the fmask is resolved so replicate a |
| 193 | * packet its way |
| 194 | */ |
| 195 | next0 = BIER_LOOKUP_NEXT_OUTPUT; |
| 196 | |
| 197 | vec_add1 (blm->blm_fmasks[thread_index], bfmi0); |
| 198 | } else { |
| 199 | /* |
| 200 | * go to the next bit-position set |
| 201 | */ |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 202 | vlib_node_increment_counter( |
| 203 | vm, node->node_index, |
| 204 | BIER_LOOKUP_ERROR_FMASK_UNRES, 1); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 205 | bucket = ((int*)bbs.bbs_buckets)[index]; |
| 206 | continue; |
| 207 | } |
| 208 | } |
| 209 | } |
| 210 | |
| 211 | /* |
| 212 | * Full mask now processed. |
| 213 | * Create the number of clones we need based on the number |
| 214 | * of fmasks we are sending to. |
| 215 | */ |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 216 | u16 num_cloned, clone; |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 217 | u32 n_clones; |
| 218 | |
| 219 | n_clones = vec_len(blm->blm_fmasks[thread_index]); |
| 220 | |
| 221 | if (PREDICT_TRUE(0 != n_clones)) |
| 222 | { |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 223 | num_cloned = vlib_buffer_clone(vm, bi0, |
| 224 | blm->blm_clones[thread_index], |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 225 | n_clones, |
| 226 | n_bytes + 8); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 227 | |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 228 | if (num_cloned != vec_len(blm->blm_fmasks[thread_index])) |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 229 | { |
| 230 | vlib_node_increment_counter |
| 231 | (vm, node->node_index, |
| 232 | BIER_LOOKUP_ERROR_BUFFER_ALLOCATION_FAILURE, 1); |
| 233 | } |
| 234 | |
| 235 | for (clone = 0; clone < num_cloned; clone++) |
| 236 | { |
| 237 | vlib_buffer_t *c0; |
| 238 | u32 ci0; |
| 239 | |
| 240 | ci0 = blm->blm_clones[thread_index][clone]; |
| 241 | c0 = vlib_get_buffer(vm, ci0); |
Neale Ranns | 9128637 | 2017-12-05 13:24:04 -0800 | [diff] [blame] | 242 | vnet_buffer(c0)->ip.adj_index[VLIB_TX] = |
| 243 | blm->blm_fmasks[thread_index][clone]; |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 244 | |
| 245 | to_next[0] = ci0; |
| 246 | to_next += 1; |
| 247 | n_left_to_next -= 1; |
| 248 | |
| 249 | if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED)) |
| 250 | { |
| 251 | bier_lookup_trace_t *tr; |
| 252 | |
Neale Ranns | ef90ed0 | 2018-09-13 08:45:12 -0700 | [diff] [blame^] | 253 | if (c0 != b0) |
| 254 | vlib_buffer_copy_trace_flag (vm, b0, ci0); |
| 255 | |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 256 | tr = vlib_add_trace (vm, node, c0, sizeof (*tr)); |
| 257 | tr->bt_index = bti0; |
| 258 | tr->bfm_index = blm->blm_fmasks[thread_index][clone]; |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 259 | } |
| 260 | |
| 261 | vlib_validate_buffer_enqueue_x1(vm, node, next_index, |
| 262 | to_next, n_left_to_next, |
| 263 | ci0, next0); |
| 264 | |
| 265 | /* |
| 266 | * After the enqueue it is possible that we over-flow the |
| 267 | * frame of the to-next node. When this happens we need to |
| 268 | * 'put' that full frame to the node and get a fresh empty |
| 269 | * one. Note that these are macros with side effects that |
| 270 | * change to_next & n_left_to_next |
| 271 | */ |
| 272 | if (PREDICT_FALSE(0 == n_left_to_next)) |
| 273 | { |
| 274 | vlib_put_next_frame (vm, node, next_index, |
| 275 | n_left_to_next); |
| 276 | vlib_get_next_frame (vm, node, next_index, |
| 277 | to_next, n_left_to_next); |
| 278 | } |
| 279 | } |
| 280 | } |
| 281 | else |
| 282 | { |
| 283 | /* |
| 284 | * no clones/replications required. drop this packet |
| 285 | */ |
| 286 | next0 = BIER_LOOKUP_NEXT_DROP; |
| 287 | to_next[0] = bi0; |
| 288 | to_next += 1; |
| 289 | n_left_to_next -= 1; |
| 290 | |
| 291 | if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED)) |
| 292 | { |
| 293 | bier_lookup_trace_t *tr; |
| 294 | |
| 295 | tr = vlib_add_trace (vm, node, b0, sizeof (*tr)); |
| 296 | |
| 297 | tr->bt_index = bti0; |
| 298 | tr->bfm_index = ~0; |
| 299 | } |
| 300 | |
| 301 | vlib_validate_buffer_enqueue_x1(vm, node, next_index, |
| 302 | to_next, n_left_to_next, |
| 303 | bi0, next0); |
| 304 | } |
| 305 | } |
| 306 | |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 307 | vlib_put_next_frame(vm, node, next_index, n_left_to_next); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 308 | } |
| 309 | |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 310 | vlib_node_increment_counter(vm, bier_lookup_node.index, |
| 311 | BIER_LOOKUP_ERROR_NONE, |
| 312 | from_frame->n_vectors); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 313 | return (from_frame->n_vectors); |
| 314 | } |
| 315 | |
| 316 | static u8 * |
| 317 | format_bier_lookup_trace (u8 * s, va_list * args) |
| 318 | { |
| 319 | CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *); |
| 320 | CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *); |
| 321 | bier_lookup_trace_t * t = va_arg (*args, bier_lookup_trace_t *); |
| 322 | |
| 323 | s = format (s, "BIER: next [%d], tbl:%d BFM:%d", |
| 324 | t->next_index, |
| 325 | t->bt_index, |
| 326 | t->bfm_index); |
| 327 | return s; |
| 328 | } |
| 329 | |
| 330 | VLIB_REGISTER_NODE (bier_lookup_node) = { |
| 331 | .function = bier_lookup, |
| 332 | .name = "bier-lookup", |
| 333 | /* Takes a vector of packets. */ |
| 334 | .vector_size = sizeof (u32), |
| 335 | |
| 336 | .n_errors = BIER_LOOKUP_N_ERROR, |
| 337 | .error_strings = bier_lookup_error_strings, |
| 338 | |
| 339 | .format_trace = format_bier_lookup_trace, |
| 340 | .n_next_nodes = BIER_LOOKUP_N_NEXT, |
| 341 | .next_nodes = { |
| 342 | [BIER_LOOKUP_NEXT_DROP] = "bier-drop", |
| 343 | [BIER_LOOKUP_NEXT_OUTPUT] = "bier-output", |
| 344 | }, |
| 345 | }; |
| 346 | |
| 347 | clib_error_t * |
| 348 | bier_lookup_module_init (vlib_main_t * vm) |
| 349 | { |
| 350 | bier_lookup_main_t *blm = &bier_lookup_main; |
| 351 | u32 thread_index; |
| 352 | |
| 353 | vec_validate (blm->blm_clones, vlib_num_workers()); |
| 354 | vec_validate (blm->blm_fmasks, vlib_num_workers()); |
| 355 | |
| 356 | for (thread_index = 0; |
| 357 | thread_index <= vlib_num_workers(); |
| 358 | thread_index++) |
| 359 | { |
| 360 | /* |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 361 | * 1024 is the most we will ever need to support |
| 362 | * a Bit-Mask length of 1024 |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 363 | */ |
Neale Ranns | f051072 | 2018-01-31 11:35:41 -0800 | [diff] [blame] | 364 | vec_validate(blm->blm_fmasks[thread_index], 1023); |
| 365 | vec_validate(blm->blm_clones[thread_index], 1023); |
Neale Ranns | d792d9c | 2017-10-21 10:53:20 -0700 | [diff] [blame] | 366 | } |
| 367 | |
| 368 | return 0; |
| 369 | } |
| 370 | |
| 371 | VLIB_INIT_FUNCTION (bier_lookup_module_init); |