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/bier/bier_entry.h>
17 #include <vnet/bier/bier_update.h>
19 #include <vnet/fib/fib_path_list.h>
21 #include <vnet/bier/bier_fmask_db.h>
22 #include <vnet/bier/bier_fmask.h>
23 #include <vnet/bier/bier_table.h>
25 bier_entry_t *bier_entry_pool;
28 bier_entry_get_index (const bier_entry_t *be)
30 return (be - bier_entry_pool);
33 static fib_path_list_walk_rc_t
34 bier_entry_link_walk (fib_node_index_t pl_index,
35 fib_node_index_t path_index,
38 bier_entry_t *be = arg;
41 bfmi = fib_path_get_resolving_index(path_index);
42 bier_fmask_link(bfmi, be->be_bp);
44 return (FIB_PATH_LIST_WALK_CONTINUE);
47 static fib_path_list_walk_rc_t
48 bier_entry_unlink_walk (fib_node_index_t pl_index,
49 fib_node_index_t path_index,
52 bier_entry_t *be = arg;
55 bfmi = fib_path_get_resolving_index(path_index);
56 bier_fmask_unlink(bfmi, be->be_bp);
58 return (FIB_PATH_LIST_WALK_CONTINUE);
62 bier_entry_create (index_t bti,
67 pool_get(bier_entry_pool, be);
71 be->be_path_list = FIB_NODE_INDEX_INVALID;
73 return (bier_entry_get_index(be));
78 bier_entry_table_ecmp_walk_add_fmask (index_t btei,
81 bier_entry_t *be = arg;;
84 * choose a fmask from the entry's resolved set to add
85 * to ECMP table's lookup table
87 if (FIB_NODE_INDEX_INVALID != be->be_path_list)
89 const bier_table_id_t *btid;
90 dpo_id_t dpo = DPO_INVALID;
91 const dpo_id_t *choice;
94 btid = bier_table_get_id(btei);
96 fib_path_list_contribute_forwarding(be->be_path_list,
97 FIB_FORW_CHAIN_TYPE_BIER,
98 FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
102 * select the appropriate bucket from the LB
104 if (dpo.dpoi_type == DPO_LOAD_BALANCE)
106 lb = load_balance_get(dpo.dpoi_index);
107 choice = load_balance_get_bucket_i(lb,
109 (lb->lb_n_buckets_minus_1));
116 if (choice->dpoi_type == DPO_BIER_FMASK)
118 bier_table_ecmp_set_fmask(btei, be->be_bp,
124 * any other type results in a drop, which we represent
125 * with an empty bucket
127 bier_table_ecmp_set_fmask(btei, be->be_bp,
136 * no fmasks left. insert a drop
138 bier_table_ecmp_set_fmask(btei, be->be_bp, INDEX_INVALID);
143 bier_entry_delete (index_t bei)
147 be = bier_entry_get(bei);
150 * if we still ahve a path-list, unlink from it
152 if (FIB_NODE_INDEX_INVALID != be->be_path_list)
154 fib_path_list_walk(be->be_path_list,
155 bier_entry_unlink_walk,
157 fib_path_list_child_remove(be->be_path_list,
158 be->be_sibling_index);
160 be->be_path_list = FIB_NODE_INDEX_INVALID;
161 bier_table_ecmp_walk(be->be_bti,
162 bier_entry_table_ecmp_walk_add_fmask,
166 pool_put(bier_entry_pool, be);
170 bier_entry_path_add (index_t bei,
171 const fib_route_path_t *rpaths)
173 fib_node_index_t old_pl_index;
176 be = bier_entry_get(bei);
177 old_pl_index = be->be_path_list;
180 * lock the path-list so it does not go away before we unlink
181 * from its resolved fmasks
183 fib_path_list_lock(old_pl_index);
185 if (FIB_NODE_INDEX_INVALID == be->be_path_list)
187 old_pl_index = FIB_NODE_INDEX_INVALID;
188 be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
189 FIB_PATH_LIST_FLAG_NO_URPF),
191 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));
198 old_pl_index = be->be_path_list;
201 fib_path_list_copy_and_path_add(old_pl_index,
202 (FIB_PATH_LIST_FLAG_SHARED |
203 FIB_PATH_LIST_FLAG_NO_URPF),
206 fib_path_list_child_remove(old_pl_index,
207 be->be_sibling_index);
208 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));
213 * link the entry's bit-position to each fmask in the new path-list
214 * then unlink from the old.
216 fib_path_list_walk(be->be_path_list,
217 bier_entry_link_walk,
219 if (FIB_NODE_INDEX_INVALID != old_pl_index)
221 fib_path_list_walk(old_pl_index,
222 bier_entry_unlink_walk,
227 * update the ECNP tables with the new choice
229 bier_table_ecmp_walk(be->be_bti,
230 bier_entry_table_ecmp_walk_add_fmask,
234 * symmetric unlock. The old path-list may not exist hereinafter
236 fib_path_list_unlock(old_pl_index);
240 bier_entry_path_update (index_t bei,
241 const fib_route_path_t *rpaths)
243 fib_node_index_t old_pl_index;
246 be = bier_entry_get(bei);
247 old_pl_index = be->be_path_list;
250 * lock the path-list so it does not go away before we unlink
251 * from its resolved fmasks
253 fib_path_list_lock(old_pl_index);
255 if (FIB_NODE_INDEX_INVALID != old_pl_index)
257 fib_path_list_child_remove(old_pl_index,
258 be->be_sibling_index);
261 be->be_path_list = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
262 FIB_PATH_LIST_FLAG_NO_URPF),
264 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));
269 * link the entry's bit-position to each fmask in the new path-list
270 * then unlink from the old.
272 fib_path_list_walk(be->be_path_list,
273 bier_entry_link_walk,
275 if (FIB_NODE_INDEX_INVALID != old_pl_index)
277 fib_path_list_walk(old_pl_index,
278 bier_entry_unlink_walk,
283 * update the ECNP tables with the new choice
285 bier_table_ecmp_walk(be->be_bti,
286 bier_entry_table_ecmp_walk_add_fmask,
290 * symmetric unlock. The old path-list may not exist hereinafter
292 fib_path_list_unlock(old_pl_index);
296 bier_entry_path_remove (index_t bei,
297 const fib_route_path_t *rpaths)
299 fib_node_index_t old_pl_index;
302 be = bier_entry_get(bei);
303 old_pl_index = be->be_path_list;
305 fib_path_list_lock(old_pl_index);
307 ASSERT (FIB_NODE_INDEX_INVALID != be->be_path_list);
310 fib_path_list_copy_and_path_remove(old_pl_index,
311 (FIB_PATH_LIST_FLAG_SHARED |
312 FIB_PATH_LIST_FLAG_NO_URPF),
315 if (be->be_path_list != old_pl_index)
320 fib_path_list_child_remove(old_pl_index,
321 be->be_sibling_index);
323 if (FIB_NODE_INDEX_INVALID != be->be_path_list)
326 * link the entry's bit-position to each fmask in the new path-list
327 * then unlink from the old.
329 fib_path_list_walk(be->be_path_list,
330 bier_entry_link_walk,
332 be->be_sibling_index =
333 fib_path_list_child_add(be->be_path_list,
334 FIB_NODE_TYPE_BIER_ENTRY,
335 bier_entry_get_index(be));
338 fib_path_list_walk(old_pl_index,
339 bier_entry_unlink_walk,
342 fib_path_list_unlock(old_pl_index);
345 * update the ECNP tables with the new choice
347 bier_table_ecmp_walk(be->be_bti,
348 bier_entry_table_ecmp_walk_add_fmask,
351 return (fib_path_list_get_n_paths(be->be_path_list));
355 bier_entry_contribute_forwarding(index_t bei,
358 bier_entry_t *be = bier_entry_get(bei);
360 fib_path_list_contribute_forwarding(be->be_path_list,
361 FIB_FORW_CHAIN_TYPE_BIER,
362 FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
367 format_bier_entry (u8* s, va_list *ap)
369 index_t bei = va_arg(*ap, index_t);
370 bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
372 bier_entry_t *be = bier_entry_get(bei);
374 s = format(s, " bp:%d\n", be->be_bp);
375 s = fib_path_list_format(be->be_path_list, s);
377 if (flags & BIER_SHOW_DETAIL)
379 dpo_id_t dpo = DPO_INVALID;
381 bier_entry_contribute_forwarding(bei, &dpo);
383 s = format(s, " forwarding:\n");
385 format_dpo_id, &dpo, 2);
393 bier_entry_get_node (fib_node_index_t index)
395 bier_entry_t *be = bier_entry_get(index);
396 return (&(be->be_node));
400 bier_entry_get_from_node (fib_node_t *node)
402 return ((bier_entry_t*)(((char*)node) -
403 STRUCT_OFFSET_OF(bier_entry_t,
408 bier_entry_last_lock_gone (fib_node_t *node)
411 * the lifetime of the entry is managed by the table.
417 * A back walk has reached this BIER entry
419 static fib_node_back_walk_rc_t
420 bier_entry_back_walk_notify (fib_node_t *node,
421 fib_node_back_walk_ctx_t *ctx)
424 * re-populate the ECMP tables with new choices
426 bier_entry_t *be = bier_entry_get_from_node(node);
428 bier_table_ecmp_walk(be->be_bti,
429 bier_entry_table_ecmp_walk_add_fmask,
433 * no need to propagate further up the graph.
435 return (FIB_NODE_BACK_WALK_CONTINUE);
439 * The BIER fmask's graph node virtual function table
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,
448 bier_entry_module_init (vlib_main_t * vm)
450 fib_node_register_type (FIB_NODE_TYPE_BIER_ENTRY, &bier_entry_vft);
455 VLIB_INIT_FUNCTION (bier_entry_module_init);