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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vnet/buffer.h>
17 #include <vnet/vnet.h>
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>
25 * Struct maintaining the per-worker thread data for BIER lookups
27 typedef struct bier_lookup_main_t_
29 /* per-cpu vector of cloned packets */
31 /* per-cpu vector of BIER fmasks */
36 * Single instance of the lookup main
38 static bier_lookup_main_t bier_lookup_main;
40 static char * bier_lookup_error_strings[] = {
41 #define bier_error(n,s) s,
42 #include <vnet/bier/bier_lookup_error.def>
47 * Keep these values semantically the same as BIER lookup
49 #define foreach_bier_lookup_next \
50 _(DROP, "bier-drop") \
51 _(OUTPUT, "bier-output")
54 #define _(s,n) BIER_LOOKUP_NEXT_##s,
55 foreach_bier_lookup_next
61 #define bier_error(n,s) BIER_LOOKUP_ERROR_##n,
62 #include <vnet/bier/bier_lookup_error.def>
65 } bier_lookup_error_t;
67 vlib_node_registration_t bier_lookup_node;
70 * @brief Packet trace record for a BIER lookup
72 typedef struct bier_lookup_trace_t_
77 } bier_lookup_trace_t;
80 bier_lookup (vlib_main_t * vm,
81 vlib_node_runtime_t * node,
82 vlib_frame_t * from_frame)
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 bier_bit_mask_bucket_t buckets_copy[BIER_HDR_BUCKETS_4096];
89 from = vlib_frame_vector_args (from_frame);
90 n_left_from = from_frame->n_vectors;
91 next_index = BIER_LOOKUP_NEXT_DROP;
93 while (n_left_from > 0)
97 vlib_get_next_frame (vm, node, next_index,
98 to_next, n_left_to_next);
100 while (n_left_from > 0 && n_left_to_next > 0)
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;
116 b0 = vlib_get_buffer (vm, bi0);
117 bh0 = vlib_buffer_get_current (b0);
118 bti0 = vnet_buffer(b0)->ip.adj_index[VLIB_TX];
121 * default to drop so that if no bits are matched then
122 * that is where we go - DROP.
124 next0 = BIER_LOOKUP_NEXT_DROP;
127 * At the imposition or input node,
128 * we stored the BIER Table index in the TX adjacency
130 bt0 = bier_table_get(vnet_buffer(b0)->ip.adj_index[VLIB_TX]);
133 * we should only forward via one for the ECMP tables
135 ASSERT(!bier_table_is_main(bt0));
138 * number of integer sized buckets
140 n_bytes = bier_hdr_len_id_to_num_buckets(bt0->bt_id.bti_hdr_len);
141 vnet_buffer(b0)->mpls.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,
147 memcpy(bbs.bbs_buckets, bh0->bh_bit_string, bbs.bbs_len);
150 * reset the fmask storage vector
152 vec_reset_length (blm->blm_fmasks[thread_index]);
155 * Loop through the buckets in the header
157 for (index = 0; index < num_buckets; index++) {
159 * loop through each bit in the bucket
161 bucket = ((int*)bbs.bbs_buckets)[index];
164 fbs = bier_find_first_bit_string_set(bucket);
165 fbs += (((num_buckets - 1) - index) *
166 BIER_BIT_MASK_BITS_PER_INT);
168 bfmi0 = bier_table_fwd_lookup(bt0, fbs);
171 * whatever happens, the bit we just looked for
172 * MUST be cleared from the packet
173 * otherwise we could be in this loop a while ...
175 bier_bit_string_clear_bit(&bbs, fbs);
177 if (PREDICT_TRUE(INDEX_INVALID != bfmi0))
179 bfm0 = bier_fmask_get(bfmi0);
182 * use the bit-string on the fmask to reset
183 * the bits in the header we are walking
185 bier_bit_string_clear_string(
186 &bfm0->bfm_bits.bfmb_input_reset_string,
188 bucket = ((int*)bbs.bbs_buckets)[index];
191 * the fmask is resolved so replicate a
194 next0 = BIER_LOOKUP_NEXT_OUTPUT;
196 vec_add1 (blm->blm_fmasks[thread_index], bfmi0);
199 * go to the next bit-position set
201 vlib_node_increment_counter(
202 vm, node->node_index,
203 BIER_LOOKUP_ERROR_FMASK_UNRES, 1);
204 bucket = ((int*)bbs.bbs_buckets)[index];
211 * Full mask now processed.
212 * Create the number of clones we need based on the number
213 * of fmasks we are sending to.
215 u16 num_cloned, clone;
218 n_clones = vec_len(blm->blm_fmasks[thread_index]);
220 if (PREDICT_TRUE(0 != n_clones))
222 num_cloned = vlib_buffer_clone(vm, bi0,
223 blm->blm_clones[thread_index],
225 VLIB_BUFFER_CLONE_HEAD_SIZE);
227 vec_set_len(blm->blm_clones[thread_index], num_cloned);
229 if (num_cloned != n_clones)
231 vlib_node_increment_counter
232 (vm, node->node_index,
233 BIER_LOOKUP_ERROR_BUFFER_ALLOCATION_FAILURE, 1);
236 for (clone = 0; clone < num_cloned; clone++)
241 ci0 = blm->blm_clones[thread_index][clone];
242 c0 = vlib_get_buffer(vm, ci0);
243 vnet_buffer(c0)->ip.adj_index[VLIB_TX] =
244 blm->blm_fmasks[thread_index][clone];
250 if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
252 bier_lookup_trace_t *tr;
254 tr = vlib_add_trace (vm, node, c0, sizeof (*tr));
256 tr->bfm_index = blm->blm_fmasks[thread_index][clone];
259 vlib_validate_buffer_enqueue_x1(vm, node, next_index,
260 to_next, n_left_to_next,
264 * After the enqueue it is possible that we over-flow the
265 * frame of the to-next node. When this happens we need to
266 * 'put' that full frame to the node and get a fresh empty
267 * one. Note that these are macros with side effects that
268 * change to_next & n_left_to_next
270 if (PREDICT_FALSE(0 == n_left_to_next))
272 vlib_put_next_frame (vm, node, next_index,
274 vlib_get_next_frame (vm, node, next_index,
275 to_next, n_left_to_next);
282 * no clones/replications required. drop this packet
284 next0 = BIER_LOOKUP_NEXT_DROP;
289 if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
291 bier_lookup_trace_t *tr;
293 tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
299 vlib_validate_buffer_enqueue_x1(vm, node, next_index,
300 to_next, n_left_to_next,
305 vlib_put_next_frame(vm, node, next_index, n_left_to_next);
308 vlib_node_increment_counter(vm, bier_lookup_node.index,
309 BIER_LOOKUP_ERROR_NONE,
310 from_frame->n_vectors);
311 return (from_frame->n_vectors);
315 format_bier_lookup_trace (u8 * s, va_list * args)
317 CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
318 CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
319 bier_lookup_trace_t * t = va_arg (*args, bier_lookup_trace_t *);
321 s = format (s, "BIER: next [%d], tbl:%d BFM:%d",
328 VLIB_REGISTER_NODE (bier_lookup_node) = {
329 .function = bier_lookup,
330 .name = "bier-lookup",
331 /* Takes a vector of packets. */
332 .vector_size = sizeof (u32),
334 .n_errors = BIER_LOOKUP_N_ERROR,
335 .error_strings = bier_lookup_error_strings,
337 .format_trace = format_bier_lookup_trace,
338 .n_next_nodes = BIER_LOOKUP_N_NEXT,
340 [BIER_LOOKUP_NEXT_DROP] = "bier-drop",
341 [BIER_LOOKUP_NEXT_OUTPUT] = "bier-output",
346 bier_lookup_module_init (vlib_main_t * vm)
348 bier_lookup_main_t *blm = &bier_lookup_main;
351 vec_validate (blm->blm_clones, vlib_num_workers());
352 vec_validate (blm->blm_fmasks, vlib_num_workers());
354 for (thread_index = 0;
355 thread_index <= vlib_num_workers();
359 * 1024 is the most we will ever need to support
360 * a Bit-Mask length of 1024
362 vec_validate(blm->blm_fmasks[thread_index], 1023);
363 vec_validate(blm->blm_clones[thread_index], 1023);
369 VLIB_INIT_FUNCTION (bier_lookup_module_init);