FD.io VPP  v19.08-27-gf4dcae4
Vector Packet Processing
bier_entry.c
Go to the documentation of this file.
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 
22 #include <vnet/bier/bier_fmask.h>
23 #include <vnet/bier/bier_table.h>
24 
26 
27 static index_t
29 {
30  return (be - bier_entry_pool);
31 }
32 
35  fib_node_index_t path_index,
36  void *arg)
37 {
38  bier_entry_t *be = arg;
39  index_t bfmi;
40 
41  bfmi = fib_path_get_resolving_index(path_index);
42  bier_fmask_link(bfmi, be->be_bp);
43 
45 }
46 
49  fib_node_index_t path_index,
50  void *arg)
51 {
52  bier_entry_t *be = arg;
53  index_t bfmi;
54 
55  bfmi = fib_path_get_resolving_index(path_index);
56  bier_fmask_unlink(bfmi, be->be_bp);
57 
59 }
60 
61 index_t
63  bier_bp_t bp)
64 {
65  bier_entry_t *be;
66 
67  pool_get(bier_entry_pool, be);
68 
69  be->be_bp = bp;
70  be->be_bti = bti;
72 
73  return (bier_entry_get_index(be));
74 }
75 
76 
77 static void
79  void *arg)
80 {
81  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  */
88  {
89  const bier_table_id_t *btid;
90  dpo_id_t dpo = DPO_INVALID;
91  const dpo_id_t *choice;
92  load_balance_t *lb;
93 
94  btid = bier_table_get_id(btei);
95 
99  &dpo);
100 
101  /*
102  * select the appropriate bucket from the LB
103  */
104  if (dpo.dpoi_type == DPO_LOAD_BALANCE)
105  {
106  lb = load_balance_get(dpo.dpoi_index);
107  choice = load_balance_get_bucket_i(lb,
108  btid->bti_ecmp &
109  (lb->lb_n_buckets_minus_1));
110  }
111  else
112  {
113  choice = &dpo;
114  }
115 
116  if (choice->dpoi_type == DPO_BIER_FMASK)
117  {
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  */
128  INDEX_INVALID);
129  }
130 
131  dpo_reset(&dpo);
132  }
133  else
134  {
135  /*
136  * no fmasks left. insert a drop
137  */
139  }
140 }
141 
142 void
144 {
145  bier_entry_t *be;
146 
147  be = bier_entry_get(bei);
148 
149  /*
150  * if we still have a path-list, unlink from it
151  */
153  {
156  be);
158  be->be_sibling_index);
159 
163  be);
164  }
165 
166  pool_put(bier_entry_pool, be);
167 }
168 
169 void
171  const fib_route_path_t *rpaths)
172 {
173  fib_node_index_t old_pl_index;
174  bier_entry_t *be;
175 
176  be = bier_entry_get(bei);
177  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  fib_path_list_lock(old_pl_index);
184 
186  {
187  old_pl_index = FIB_NODE_INDEX_INVALID;
190  rpaths);
194  }
195  else
196  {
197 
198  old_pl_index = be->be_path_list;
199 
200  be->be_path_list =
201  fib_path_list_copy_and_path_add(old_pl_index,
204  rpaths);
205 
206  fib_path_list_child_remove(old_pl_index,
207  be->be_sibling_index);
211  }
212  /*
213  * link the entry's bit-position to each fmask in the new path-list
214  * then unlink from the old.
215  */
218  be);
219  if (FIB_NODE_INDEX_INVALID != old_pl_index)
220  {
221  fib_path_list_walk(old_pl_index,
223  be);
224  }
225 
226  /*
227  * update the ECMP tables with the new choice
228  */
231  be);
232 
233  /*
234  * symmetric unlock. The old path-list may not exist hereinafter
235  */
236  fib_path_list_unlock(old_pl_index);
237 }
238 
239 void
241  const fib_route_path_t *rpaths)
242 {
243  fib_node_index_t old_pl_index;
244  bier_entry_t *be;
245 
246  be = bier_entry_get(bei);
247  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  fib_path_list_lock(old_pl_index);
254 
255  if (FIB_NODE_INDEX_INVALID != old_pl_index)
256  {
257  fib_path_list_child_remove(old_pl_index,
258  be->be_sibling_index);
259  }
260 
263  rpaths);
267 
268  /*
269  * link the entry's bit-position to each fmask in the new path-list
270  * then unlink from the old.
271  */
274  be);
275  if (FIB_NODE_INDEX_INVALID != old_pl_index)
276  {
277  fib_path_list_walk(old_pl_index,
279  be);
280  }
281 
282  /*
283  * update the ECMP tables with the new choice
284  */
287  be);
288 
289  /*
290  * symmetric unlock. The old path-list may not exist hereinafter
291  */
292  fib_path_list_unlock(old_pl_index);
293 }
294 
295 int
297  const fib_route_path_t *rpaths)
298 {
299  fib_node_index_t old_pl_index;
300  bier_entry_t *be;
301 
302  be = bier_entry_get(bei);
303  old_pl_index = be->be_path_list;
304 
305  fib_path_list_lock(old_pl_index);
306 
308 
309  be->be_path_list =
313  rpaths);
314 
315  if (be->be_path_list != old_pl_index)
316  {
317  /*
318  * a path was removed
319  */
320  fib_path_list_child_remove(old_pl_index,
321  be->be_sibling_index);
322 
324  {
325  /*
326  * link the entry's bit-position to each fmask in the new path-list
327  * then unlink from the old.
328  */
331  be);
332  be->be_sibling_index =
336  }
337 
338  fib_path_list_walk(old_pl_index,
340  be);
341  }
342  fib_path_list_unlock(old_pl_index);
343 
344  /*
345  * update the ECMP tables with the new choice
346  */
349  be);
350 
352 }
353 
354 void
356  dpo_id_t *dpo)
357 {
358  bier_entry_t *be = bier_entry_get(bei);
359 
363  dpo);
364 }
365 
366 u8*
367 format_bier_entry (u8* s, va_list *ap)
368 {
369  index_t bei = va_arg(*ap, index_t);
371 
372  bier_entry_t *be = bier_entry_get(bei);
373 
374  s = format(s, " bp:%d\n", be->be_bp);
376 
377  if (flags & BIER_SHOW_DETAIL)
378  {
379  dpo_id_t dpo = DPO_INVALID;
380 
382 
383  s = format(s, " forwarding:\n");
384  s = format(s, " %U",
385  format_dpo_id, &dpo, 2);
386  s = format(s, "\n");
387  }
388 
389  return (s);
390 }
391 
392 static fib_node_t *
394 {
395  bier_entry_t *be = bier_entry_get(index);
396  return (&(be->be_node));
397 }
398 
399 static bier_entry_t*
401 {
402  return ((bier_entry_t*)(((char*)node) -
404  be_node)));
405 }
406 
407 static void
409 {
410  /*
411  * the lifetime of the entry is managed by the table.
412  */
413  ASSERT(0);
414 }
415 
416 /*
417  * A back walk has reached this BIER entry
418  */
422 {
423  /*
424  * re-populate the ECMP tables with new choices
425  */
427 
430  be);
431 
432  /*
433  * no need to propagate further up the graph.
434  */
436 }
437 
438 /*
439  * The BIER fmask's graph node virtual function table
440  */
441 static const fib_node_vft_t bier_entry_vft = {
443  .fnv_last_lock = bier_entry_last_lock_gone,
444  .fnv_back_walk = bier_entry_back_walk_notify,
445 };
446 
447 clib_error_t *
449 {
451 
452  return (NULL);
453 }
454 
void bier_entry_path_update(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:240
Contribute an object that is to be used to forward BIER packets.
Definition: fib_types.h:122
u32 flags
Definition: vhost_user.h:141
void fib_path_list_child_remove(fib_node_index_t path_list_index, u32 si)
static void bier_entry_last_lock_gone(fib_node_t *node)
Definition: bier_entry.c:408
index_t fib_path_get_resolving_index(fib_node_index_t path_index)
Definition: fib_path.c:2178
A representation of a path as described by a route producer.
Definition: fib_types.h:479
enum bier_show_flags_t_ bier_show_flags_t
Flags to control show output.
void bier_entry_delete(index_t bei)
Definition: bier_entry.c:143
#define NULL
Definition: clib.h:58
enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
Return code from a back walk function.
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
index_t be_bti
The index of the BIER table in which this entry resides.
Definition: bier_entry.h:55
index_t bier_entry_create(index_t bti, bier_bp_t bp)
Definition: bier_entry.c:62
fib_node_index_t be_path_list
the FIB path-list this entry resolves through.
Definition: bier_entry.h:67
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:65
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static bier_entry_t * bier_entry_get(index_t bei)
Definition: bier_entry.h:93
static fib_path_list_walk_rc_t bier_entry_unlink_walk(fib_node_index_t pl_index, fib_node_index_t path_index, void *arg)
Definition: bier_entry.c:48
void bier_entry_contribute_forwarding(index_t bei, dpo_id_t *dpo)
Definition: bier_entry.c:355
clib_error_t * bier_entry_module_init(vlib_main_t *vm)
Definition: bier_entry.c:448
The ID of a table.
Definition: bier_types.h:394
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
bier_bp_t be_bp
the bit position this entry represents.
Definition: bier_entry.h:61
u32 fib_path_list_child_add(fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t child_index)
unsigned char u8
Definition: types.h:56
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
Definition: fib_node.c:60
void bier_fmask_unlink(index_t bfmi, bier_bp_t bp)
Definition: bier_fmask.c:324
#define VLIB_INIT_FUNCTION(x)
Definition: init.h:173
bier_table_ecmp_id_t bti_ecmp
The SUB/ECMP-ID Constructed by FIB to achieve ECMP between BFR-NBRs.
Definition: bier_types.h:414
u16 lb_n_buckets_minus_1
number of buckets in the load-balance - 1.
Definition: load_balance.h:121
fib_node_index_t be_sibling_index
sibling index on the path list
Definition: bier_entry.h:71
u32 bier_bp_t
A bit positon as assigned to egress PEs.
Definition: bier_types.h:294
void bier_fmask_link(index_t bfmi, bier_bp_t bp)
Definition: bier_fmask.c:304
fib_node_index_t fib_path_list_copy_and_path_add(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:170
fib_node_index_t fib_path_list_create(fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
dpo_type_t dpoi_type
the type
Definition: dpo.h:174
static const dpo_id_t * load_balance_get_bucket_i(const load_balance_t *lb, u32 bucket)
Definition: load_balance.h:229
long ctx[MAX_CONNS]
Definition: main.c:144
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:102
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
The FIB DPO provieds;.
Definition: load_balance.h:106
void fib_path_list_lock(fib_node_index_t path_list_index)
static void bier_entry_table_ecmp_walk_add_fmask(index_t btei, void *arg)
Definition: bier_entry.c:78
An node in the FIB graph.
Definition: fib_node.h:295
fib_node_index_t fib_path_list_copy_and_path_remove(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
int bier_entry_path_remove(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:296
static fib_node_t * bier_entry_get_node(fib_node_index_t index)
Definition: bier_entry.c:393
fib_node_t be_node
linkage into the FIB graph
Definition: bier_entry.h:50
vlib_main_t * vm
Definition: buffer.c:312
fib_node_get_t fnv_get
Definition: fib_node.h:283
u32 fib_path_list_get_n_paths(fib_node_index_t path_list_index)
static fib_path_list_walk_rc_t bier_entry_link_walk(fib_node_index_t pl_index, fib_node_index_t path_index, void *arg)
Definition: bier_entry.c:34
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
void fib_path_list_unlock(fib_node_index_t path_list_index)
Context passed between object during a back walk.
Definition: fib_node.h:208
The BIER entry.
Definition: bier_entry.h:46
#define ASSERT(truth)
const bier_table_id_t * bier_table_get_id(index_t bti)
Definition: bier_table.c:524
static load_balance_t * load_balance_get(index_t lbi)
Definition: load_balance.h:220
u8 * format_bier_entry(u8 *s, va_list *ap)
Definition: bier_entry.c:367
static fib_node_back_walk_rc_t bier_entry_back_walk_notify(fib_node_t *node, fib_node_back_walk_ctx_t *ctx)
Definition: bier_entry.c:420
u8 * format_dpo_id(u8 *s, va_list *args)
Format a DPO_id_t oject
Definition: dpo.c:148
enum fib_path_list_walk_rc_t_ fib_path_list_walk_rc_t
return code to control pat-hlist walk
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:186
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
u8 * fib_path_list_format(fib_node_index_t path_list_index, u8 *s)
static bier_entry_t * bier_entry_get_from_node(fib_node_t *node)
Definition: bier_entry.c:400
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:197
void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t fct, fib_path_list_fwd_flags_t flags, dpo_id_t *dpo)
A FIB graph nodes virtual function table.
Definition: fib_node.h:282
void bier_entry_path_add(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:170
void dpo_reset(dpo_id_t *dpo)
reset a DPO ID The DPO will be unlocked.
Definition: dpo.c:232
bier_entry_t * bier_entry_pool
Definition: bier_entry.c:25
void bier_table_ecmp_walk(index_t bti, bier_table_ecmp_walk_fn_t fn, void *ctx)
Definition: bier_table.c:770
void bier_table_ecmp_set_fmask(index_t bti, bier_bp_t bp, index_t bfmi)
Definition: bier_table.c:791
static index_t bier_entry_get_index(const bier_entry_t *be)
Definition: bier_entry.c:28