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/bier/bier_entry.h>
17 : #include <vnet/bier/bier_update.h>
18 :
19 : #include <vnet/fib/fib_path_list.h>
20 :
21 : #include <vnet/bier/bier_fmask_db.h>
22 : #include <vnet/bier/bier_fmask.h>
23 : #include <vnet/bier/bier_table.h>
24 :
25 : bier_entry_t *bier_entry_pool;
26 :
27 : static index_t
28 158 : bier_entry_get_index (const bier_entry_t *be)
29 : {
30 158 : return (be - bier_entry_pool);
31 : }
32 :
33 : static fib_path_list_walk_rc_t
34 90 : bier_entry_link_walk (fib_node_index_t pl_index,
35 : fib_node_index_t path_index,
36 : void *arg)
37 : {
38 90 : bier_entry_t *be = arg;
39 : index_t bfmi;
40 :
41 90 : bfmi = fib_path_get_resolving_index(path_index);
42 90 : bier_fmask_link(bfmi, be->be_bp);
43 :
44 90 : return (FIB_PATH_LIST_WALK_CONTINUE);
45 : }
46 :
47 : static fib_path_list_walk_rc_t
48 90 : bier_entry_unlink_walk (fib_node_index_t pl_index,
49 : fib_node_index_t path_index,
50 : void *arg)
51 : {
52 90 : bier_entry_t *be = arg;
53 : index_t bfmi;
54 :
55 90 : bfmi = fib_path_get_resolving_index(path_index);
56 90 : bier_fmask_unlink(bfmi, be->be_bp);
57 :
58 90 : return (FIB_PATH_LIST_WALK_CONTINUE);
59 : }
60 :
61 : index_t
62 76 : bier_entry_create (index_t bti,
63 : bier_bp_t bp)
64 : {
65 : bier_entry_t *be;
66 :
67 76 : pool_get(bier_entry_pool, be);
68 :
69 76 : be->be_bp = bp;
70 76 : be->be_bti = bti;
71 76 : be->be_path_list = FIB_NODE_INDEX_INVALID;
72 :
73 76 : return (bier_entry_get_index(be));
74 : }
75 :
76 :
77 : static void
78 3760 : bier_entry_table_ecmp_walk_add_fmask (index_t btei,
79 : void *arg)
80 : {
81 3760 : bier_entry_t *be = arg;;
82 :
83 : /*
84 : * choose a fmask from the entry's resolved set to add
85 : * to ECMP table's lookup table
86 : */
87 3760 : if (FIB_NODE_INDEX_INVALID != be->be_path_list)
88 : {
89 : const bier_table_id_t *btid;
90 2544 : dpo_id_t dpo = DPO_INVALID;
91 : const dpo_id_t *choice;
92 : load_balance_t *lb;
93 :
94 2544 : btid = bier_table_get_id(btei);
95 :
96 2544 : fib_path_list_contribute_forwarding(be->be_path_list,
97 : FIB_FORW_CHAIN_TYPE_BIER,
98 : FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
99 : &dpo);
100 :
101 : /*
102 : * select the appropriate bucket from the LB
103 : */
104 2544 : if (dpo.dpoi_type == DPO_LOAD_BALANCE)
105 : {
106 96 : lb = load_balance_get(dpo.dpoi_index);
107 96 : choice = load_balance_get_bucket_i(lb,
108 96 : btid->bti_ecmp &
109 96 : (lb->lb_n_buckets_minus_1));
110 : }
111 : else
112 : {
113 2448 : choice = &dpo;
114 : }
115 :
116 2544 : if (choice->dpoi_type == DPO_BIER_FMASK)
117 : {
118 2432 : bier_table_ecmp_set_fmask(btei, be->be_bp,
119 : choice->dpoi_index);
120 : }
121 : else
122 : {
123 : /*
124 : * any other type results in a drop, which we represent
125 : * with an empty bucket
126 : */
127 112 : bier_table_ecmp_set_fmask(btei, be->be_bp,
128 : INDEX_INVALID);
129 : }
130 :
131 2544 : dpo_reset(&dpo);
132 : }
133 : else
134 : {
135 : /*
136 : * no fmasks left. insert a drop
137 : */
138 1216 : bier_table_ecmp_set_fmask(btei, be->be_bp, INDEX_INVALID);
139 : }
140 3760 : }
141 :
142 : void
143 76 : bier_entry_delete (index_t bei)
144 : {
145 : bier_entry_t *be;
146 :
147 76 : be = bier_entry_get(bei);
148 :
149 : /*
150 : * if we still have a path-list, unlink from it
151 : */
152 76 : if (FIB_NODE_INDEX_INVALID != be->be_path_list)
153 : {
154 2 : fib_path_list_walk(be->be_path_list,
155 : bier_entry_unlink_walk,
156 : be);
157 2 : fib_path_list_child_remove(be->be_path_list,
158 : be->be_sibling_index);
159 :
160 2 : be->be_path_list = FIB_NODE_INDEX_INVALID;
161 2 : bier_table_ecmp_walk(be->be_bti,
162 : bier_entry_table_ecmp_walk_add_fmask,
163 : be);
164 : }
165 :
166 76 : pool_put(bier_entry_pool, be);
167 76 : }
168 :
169 : void
170 77 : bier_entry_path_add (index_t bei,
171 : const fib_route_path_t *rpaths)
172 : {
173 : fib_node_index_t old_pl_index;
174 : bier_entry_t *be;
175 :
176 77 : be = bier_entry_get(bei);
177 77 : old_pl_index = be->be_path_list;
178 :
179 : /*
180 : * lock the path-list so it does not go away before we unlink
181 : * from its resolved fmasks
182 : */
183 77 : fib_path_list_lock(old_pl_index);
184 :
185 77 : if (FIB_NODE_INDEX_INVALID == be->be_path_list)
186 : {
187 75 : old_pl_index = FIB_NODE_INDEX_INVALID;
188 75 : be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
189 : FIB_PATH_LIST_FLAG_NO_URPF),
190 : rpaths);
191 75 : be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
192 : FIB_NODE_TYPE_BIER_ENTRY,
193 : bier_entry_get_index(be));
194 : }
195 : else
196 : {
197 :
198 2 : old_pl_index = be->be_path_list;
199 :
200 2 : be->be_path_list =
201 2 : fib_path_list_copy_and_path_add(old_pl_index,
202 : (FIB_PATH_LIST_FLAG_SHARED |
203 : FIB_PATH_LIST_FLAG_NO_URPF),
204 : rpaths);
205 :
206 2 : fib_path_list_child_remove(old_pl_index,
207 : be->be_sibling_index);
208 2 : be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
209 : FIB_NODE_TYPE_BIER_ENTRY,
210 : bier_entry_get_index(be));
211 : }
212 : /*
213 : * link the entry's bit-position to each fmask in the new path-list
214 : * then unlink from the old.
215 : */
216 77 : fib_path_list_walk(be->be_path_list,
217 : bier_entry_link_walk,
218 : be);
219 77 : if (FIB_NODE_INDEX_INVALID != old_pl_index)
220 : {
221 2 : fib_path_list_walk(old_pl_index,
222 : bier_entry_unlink_walk,
223 : be);
224 : }
225 :
226 : /*
227 : * update the ECMP tables with the new choice
228 : */
229 77 : bier_table_ecmp_walk(be->be_bti,
230 : bier_entry_table_ecmp_walk_add_fmask,
231 : be);
232 :
233 : /*
234 : * symmetric unlock. The old path-list may not exist hereinafter
235 : */
236 77 : fib_path_list_unlock(old_pl_index);
237 77 : }
238 :
239 : void
240 2 : bier_entry_path_update (index_t bei,
241 : const fib_route_path_t *rpaths)
242 : {
243 : fib_node_index_t old_pl_index;
244 : bier_entry_t *be;
245 :
246 2 : be = bier_entry_get(bei);
247 2 : old_pl_index = be->be_path_list;
248 :
249 : /*
250 : * lock the path-list so it does not go away before we unlink
251 : * from its resolved fmasks
252 : */
253 2 : fib_path_list_lock(old_pl_index);
254 :
255 2 : if (FIB_NODE_INDEX_INVALID != old_pl_index)
256 : {
257 1 : fib_path_list_child_remove(old_pl_index,
258 : be->be_sibling_index);
259 : }
260 :
261 2 : be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
262 : FIB_PATH_LIST_FLAG_NO_URPF),
263 : rpaths);
264 2 : be->be_sibling_index = fib_path_list_child_add(be->be_path_list,
265 : FIB_NODE_TYPE_BIER_ENTRY,
266 : bier_entry_get_index(be));
267 :
268 : /*
269 : * link the entry's bit-position to each fmask in the new path-list
270 : * then unlink from the old.
271 : */
272 2 : fib_path_list_walk(be->be_path_list,
273 : bier_entry_link_walk,
274 : be);
275 2 : if (FIB_NODE_INDEX_INVALID != old_pl_index)
276 : {
277 1 : fib_path_list_walk(old_pl_index,
278 : bier_entry_unlink_walk,
279 : be);
280 : }
281 :
282 : /*
283 : * update the ECMP tables with the new choice
284 : */
285 2 : bier_table_ecmp_walk(be->be_bti,
286 : bier_entry_table_ecmp_walk_add_fmask,
287 : be);
288 :
289 : /*
290 : * symmetric unlock. The old path-list may not exist hereinafter
291 : */
292 2 : fib_path_list_unlock(old_pl_index);
293 2 : }
294 :
295 : int
296 77 : bier_entry_path_remove (index_t bei,
297 : const fib_route_path_t *rpaths)
298 : {
299 : fib_node_index_t old_pl_index;
300 : bier_entry_t *be;
301 :
302 77 : be = bier_entry_get(bei);
303 77 : old_pl_index = be->be_path_list;
304 :
305 77 : fib_path_list_lock(old_pl_index);
306 :
307 77 : ASSERT (FIB_NODE_INDEX_INVALID != be->be_path_list);
308 :
309 77 : be->be_path_list =
310 77 : fib_path_list_copy_and_path_remove(old_pl_index,
311 : (FIB_PATH_LIST_FLAG_SHARED |
312 : FIB_PATH_LIST_FLAG_NO_URPF),
313 : rpaths);
314 :
315 77 : if (be->be_path_list != old_pl_index)
316 : {
317 : /*
318 : * a path was removed
319 : */
320 77 : fib_path_list_child_remove(old_pl_index,
321 : be->be_sibling_index);
322 :
323 77 : if (FIB_NODE_INDEX_INVALID != be->be_path_list)
324 : {
325 : /*
326 : * link the entry's bit-position to each fmask in the new path-list
327 : * then unlink from the old.
328 : */
329 3 : fib_path_list_walk(be->be_path_list,
330 : bier_entry_link_walk,
331 : be);
332 3 : be->be_sibling_index =
333 3 : fib_path_list_child_add(be->be_path_list,
334 : FIB_NODE_TYPE_BIER_ENTRY,
335 : bier_entry_get_index(be));
336 : }
337 :
338 77 : fib_path_list_walk(old_pl_index,
339 : bier_entry_unlink_walk,
340 : be);
341 : }
342 77 : fib_path_list_unlock(old_pl_index);
343 :
344 : /*
345 : * update the ECMP tables with the new choice
346 : */
347 77 : bier_table_ecmp_walk(be->be_bti,
348 : bier_entry_table_ecmp_walk_add_fmask,
349 : be);
350 :
351 77 : return (fib_path_list_get_n_paths(be->be_path_list));
352 : }
353 :
354 : void
355 8 : bier_entry_contribute_forwarding(index_t bei,
356 : dpo_id_t *dpo)
357 : {
358 8 : bier_entry_t *be = bier_entry_get(bei);
359 :
360 8 : fib_path_list_contribute_forwarding(be->be_path_list,
361 : FIB_FORW_CHAIN_TYPE_BIER,
362 : FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
363 : dpo);
364 8 : }
365 :
366 : u8*
367 0 : format_bier_entry (u8* s, va_list *ap)
368 : {
369 0 : index_t bei = va_arg(*ap, index_t);
370 0 : bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
371 :
372 0 : bier_entry_t *be = bier_entry_get(bei);
373 :
374 0 : s = format(s, " bp:%d\n", be->be_bp);
375 0 : s = fib_path_list_format(be->be_path_list, s);
376 :
377 0 : if (flags & BIER_SHOW_DETAIL)
378 : {
379 0 : dpo_id_t dpo = DPO_INVALID;
380 :
381 0 : bier_entry_contribute_forwarding(bei, &dpo);
382 :
383 0 : s = format(s, " forwarding:\n");
384 0 : s = format(s, " %U",
385 : format_dpo_id, &dpo, 2);
386 0 : s = format(s, "\n");
387 : }
388 :
389 0 : return (s);
390 : }
391 :
392 : static fib_node_t *
393 77 : bier_entry_get_node (fib_node_index_t index)
394 : {
395 77 : bier_entry_t *be = bier_entry_get(index);
396 77 : return (&(be->be_node));
397 : }
398 :
399 : static bier_entry_t*
400 77 : bier_entry_get_from_node (fib_node_t *node)
401 : {
402 77 : return ((bier_entry_t*)(((char*)node) -
403 : STRUCT_OFFSET_OF(bier_entry_t,
404 : be_node)));
405 : }
406 :
407 : static void
408 0 : bier_entry_last_lock_gone (fib_node_t *node)
409 : {
410 : /*
411 : * the lifetime of the entry is managed by the table.
412 : */
413 0 : ASSERT(0);
414 0 : }
415 :
416 : /*
417 : * A back walk has reached this BIER entry
418 : */
419 : static fib_node_back_walk_rc_t
420 77 : bier_entry_back_walk_notify (fib_node_t *node,
421 : fib_node_back_walk_ctx_t *ctx)
422 : {
423 : /*
424 : * re-populate the ECMP tables with new choices
425 : */
426 77 : bier_entry_t *be = bier_entry_get_from_node(node);
427 :
428 77 : bier_table_ecmp_walk(be->be_bti,
429 : bier_entry_table_ecmp_walk_add_fmask,
430 : be);
431 :
432 : /*
433 : * no need to propagate further up the graph.
434 : */
435 77 : return (FIB_NODE_BACK_WALK_CONTINUE);
436 : }
437 :
438 : /*
439 : * The BIER fmask's graph node virtual function table
440 : */
441 : static const fib_node_vft_t bier_entry_vft = {
442 : .fnv_get = bier_entry_get_node,
443 : .fnv_last_lock = bier_entry_last_lock_gone,
444 : .fnv_back_walk = bier_entry_back_walk_notify,
445 : };
446 :
447 : clib_error_t *
448 559 : bier_entry_module_init (vlib_main_t * vm)
449 : {
450 559 : fib_node_register_type (FIB_NODE_TYPE_BIER_ENTRY, &bier_entry_vft);
451 :
452 559 : return (NULL);
453 : }
454 :
455 87919 : VLIB_INIT_FUNCTION (bier_entry_module_init);
|
