Line data Source code
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 maintaining 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 semantically 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 record 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 20 : 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 20 : bier_lookup_main_t *blm = &bier_lookup_main;
86 20 : u32 thread_index = vlib_get_thread_index();
87 : bier_bit_mask_bucket_t buckets_copy[BIER_HDR_BUCKETS_4096];
88 :
89 20 : from = vlib_frame_vector_args (from_frame);
90 20 : n_left_from = from_frame->n_vectors;
91 20 : next_index = BIER_LOOKUP_NEXT_DROP;
92 :
93 40 : while (n_left_from > 0)
94 : {
95 : u32 n_left_to_next;
96 :
97 20 : vlib_get_next_frame (vm, node, next_index,
98 : to_next, n_left_to_next);
99 :
100 1193 : while (n_left_from > 0 && n_left_to_next > 0)
101 : {
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 1173 : bi0 = from[0];
113 1173 : from += 1;
114 1173 : n_left_from -= 1;
115 :
116 1173 : b0 = vlib_get_buffer (vm, bi0);
117 1173 : bh0 = vlib_buffer_get_current (b0);
118 1173 : 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 1173 : 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 1173 : 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 1173 : ASSERT(!bier_table_is_main(bt0));
136 :
137 : /*
138 : * number of integer sized buckets
139 : */
140 1173 : n_bytes = bier_hdr_len_id_to_num_buckets(bt0->bt_id.bti_hdr_len);
141 1173 : vnet_buffer(b0)->mpls.bier.n_bytes = n_bytes;
142 1173 : vnet_buffer(b0)->sw_if_index[VLIB_TX] = ~0;
143 1173 : num_buckets = n_bytes / sizeof(int);
144 1173 : bier_bit_string_init(&bbs,
145 1173 : bt0->bt_id.bti_hdr_len,
146 : buckets_copy);
147 1173 : memcpy(bbs.bbs_buckets, bh0->bh_bit_string, bbs.bbs_len);
148 :
149 : /*
150 : * reset the fmask storage vector
151 : */
152 1173 : vec_reset_length (blm->blm_fmasks[thread_index]);
153 :
154 : /*
155 : * Loop through the buckets in the header
156 : */
157 3567 : for (index = 0; index < num_buckets; index++) {
158 : /*
159 : * loop through each bit in the bucket
160 : */
161 2394 : bucket = ((int*)bbs.bbs_buckets)[index];
162 :
163 70310 : while (bucket) {
164 67916 : fbs = bier_find_first_bit_string_set(bucket);
165 67916 : fbs += (((num_buckets - 1) - index) *
166 : BIER_BIT_MASK_BITS_PER_INT);
167 :
168 67916 : bfmi0 = bier_table_fwd_lookup(bt0, fbs);
169 :
170 : /*
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 ...
174 : */
175 67916 : bier_bit_string_clear_bit(&bbs, fbs);
176 :
177 67916 : if (PREDICT_TRUE(INDEX_INVALID != bfmi0))
178 : {
179 1042 : bfm0 = bier_fmask_get(bfmi0);
180 :
181 : /*
182 : * use the bit-string on the fmask to reset
183 : * the bits in the header we are walking
184 : */
185 1042 : bier_bit_string_clear_string(
186 : &bfm0->bfm_bits.bfmb_input_reset_string,
187 : &bbs);
188 1042 : bucket = ((int*)bbs.bbs_buckets)[index];
189 :
190 : /*
191 : * the fmask is resolved so replicate a
192 : * packet its way
193 : */
194 1042 : next0 = BIER_LOOKUP_NEXT_OUTPUT;
195 :
196 1042 : vec_add1 (blm->blm_fmasks[thread_index], bfmi0);
197 : } else {
198 : /*
199 : * go to the next bit-position set
200 : */
201 66874 : vlib_node_increment_counter(
202 : vm, node->node_index,
203 : BIER_LOOKUP_ERROR_FMASK_UNRES, 1);
204 66874 : bucket = ((int*)bbs.bbs_buckets)[index];
205 66874 : continue;
206 : }
207 : }
208 : }
209 :
210 : /*
211 : * Full mask now processed.
212 : * Create the number of clones we need based on the number
213 : * of fmasks we are sending to.
214 : */
215 : u16 num_cloned, clone;
216 : u32 n_clones;
217 :
218 1173 : n_clones = vec_len(blm->blm_fmasks[thread_index]);
219 :
220 1173 : if (PREDICT_TRUE(0 != n_clones))
221 : {
222 915 : vec_set_len(blm->blm_clones[thread_index], n_clones);
223 915 : num_cloned = vlib_buffer_clone(vm, bi0,
224 915 : blm->blm_clones[thread_index],
225 : n_clones,
226 : VLIB_BUFFER_CLONE_HEAD_SIZE);
227 :
228 :
229 915 : if (num_cloned != n_clones)
230 : {
231 0 : vec_set_len(blm->blm_clones[thread_index], num_cloned);
232 0 : vlib_node_increment_counter
233 : (vm, node->node_index,
234 : BIER_LOOKUP_ERROR_BUFFER_ALLOCATION_FAILURE, 1);
235 : }
236 :
237 1957 : for (clone = 0; clone < num_cloned; clone++)
238 : {
239 : vlib_buffer_t *c0;
240 : u32 ci0;
241 :
242 1042 : ci0 = blm->blm_clones[thread_index][clone];
243 1042 : c0 = vlib_get_buffer(vm, ci0);
244 1042 : vnet_buffer(c0)->ip.adj_index[VLIB_TX] =
245 1042 : blm->blm_fmasks[thread_index][clone];
246 :
247 1042 : to_next[0] = ci0;
248 1042 : to_next += 1;
249 1042 : n_left_to_next -= 1;
250 :
251 1042 : if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
252 : {
253 : bier_lookup_trace_t *tr;
254 :
255 1042 : tr = vlib_add_trace (vm, node, c0, sizeof (*tr));
256 1042 : tr->bt_index = bti0;
257 1042 : tr->bfm_index = blm->blm_fmasks[thread_index][clone];
258 : }
259 :
260 1042 : vlib_validate_buffer_enqueue_x1(vm, node, next_index,
261 : to_next, n_left_to_next,
262 : ci0, next0);
263 :
264 : /*
265 : * After the enqueue it is possible that we over-flow the
266 : * frame of the to-next node. When this happens we need to
267 : * 'put' that full frame to the node and get a fresh empty
268 : * one. Note that these are macros with side effects that
269 : * change to_next & n_left_to_next
270 : */
271 1042 : if (PREDICT_FALSE(0 == n_left_to_next))
272 : {
273 3 : vlib_put_next_frame (vm, node, next_index,
274 : n_left_to_next);
275 3 : vlib_get_next_frame (vm, node, next_index,
276 : to_next, n_left_to_next);
277 : }
278 : }
279 : }
280 : else
281 : {
282 : /*
283 : * no clones/replications required. drop this packet
284 : */
285 258 : next0 = BIER_LOOKUP_NEXT_DROP;
286 258 : to_next[0] = bi0;
287 258 : to_next += 1;
288 258 : n_left_to_next -= 1;
289 :
290 258 : if (PREDICT_FALSE(b0->flags & VLIB_BUFFER_IS_TRACED))
291 : {
292 : bier_lookup_trace_t *tr;
293 :
294 258 : tr = vlib_add_trace (vm, node, b0, sizeof (*tr));
295 :
296 258 : tr->bt_index = bti0;
297 258 : tr->bfm_index = ~0;
298 : }
299 :
300 258 : vlib_validate_buffer_enqueue_x1(vm, node, next_index,
301 : to_next, n_left_to_next,
302 : bi0, next0);
303 : }
304 : }
305 :
306 20 : vlib_put_next_frame(vm, node, next_index, n_left_to_next);
307 : }
308 :
309 20 : vlib_node_increment_counter(vm, bier_lookup_node.index,
310 : BIER_LOOKUP_ERROR_NONE,
311 20 : from_frame->n_vectors);
312 20 : return (from_frame->n_vectors);
313 : }
314 :
315 : static u8 *
316 700 : format_bier_lookup_trace (u8 * s, va_list * args)
317 : {
318 700 : CLIB_UNUSED (vlib_main_t * vm) = va_arg (*args, vlib_main_t *);
319 700 : CLIB_UNUSED (vlib_node_t * node) = va_arg (*args, vlib_node_t *);
320 700 : bier_lookup_trace_t * t = va_arg (*args, bier_lookup_trace_t *);
321 :
322 700 : s = format (s, "BIER: next [%d], tbl:%d BFM:%d",
323 : t->next_index,
324 : t->bt_index,
325 : t->bfm_index);
326 700 : return s;
327 : }
328 :
329 183788 : VLIB_REGISTER_NODE (bier_lookup_node) = {
330 : .function = bier_lookup,
331 : .name = "bier-lookup",
332 : /* Takes a vector of packets. */
333 : .vector_size = sizeof (u32),
334 :
335 : .n_errors = BIER_LOOKUP_N_ERROR,
336 : .error_strings = bier_lookup_error_strings,
337 :
338 : .format_trace = format_bier_lookup_trace,
339 : .n_next_nodes = BIER_LOOKUP_N_NEXT,
340 : .next_nodes = {
341 : [BIER_LOOKUP_NEXT_DROP] = "bier-drop",
342 : [BIER_LOOKUP_NEXT_OUTPUT] = "bier-output",
343 : },
344 : };
345 :
346 : clib_error_t *
347 575 : bier_lookup_module_init (vlib_main_t * vm)
348 : {
349 575 : bier_lookup_main_t *blm = &bier_lookup_main;
350 : u32 thread_index;
351 :
352 575 : vec_validate (blm->blm_clones, vlib_num_workers());
353 575 : vec_validate (blm->blm_fmasks, vlib_num_workers());
354 :
355 1780 : for (thread_index = 0;
356 1205 : thread_index <= vlib_num_workers();
357 630 : thread_index++)
358 : {
359 : /*
360 : * 1024 is the most we will ever need to support
361 : * a Bit-Mask length of 1024
362 : */
363 630 : vec_validate(blm->blm_fmasks[thread_index], 1023);
364 630 : vec_validate(blm->blm_clones[thread_index], 1023);
365 : }
366 :
367 575 : return 0;
368 : }
369 :
370 91583 : VLIB_INIT_FUNCTION (bier_lookup_module_init);
|
