FD.io VPP  v18.07-rc0-415-g6c78436
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 void
78 {
79  bier_entry_t *be;
80 
81  be = bier_entry_get(bei);
82 
83  /*
84  * if we still ahve a path-list, unlink from it
85  */
87  {
90  be);
92  be->be_sibling_index);
93  }
94 
95  pool_put(bier_entry_pool, be);
96 }
97 
98 static void
100  void *arg)
101 {
102  bier_entry_t *be = arg;;
103 
104  /*
105  * choose a fmask from the entry's resolved set to add
106  * to ECMP table's lookup table
107  */
109  {
110  const bier_table_id_t *btid;
111  dpo_id_t dpo = DPO_INVALID;
112  const dpo_id_t *choice;
113  load_balance_t *lb;
114 
115  btid = bier_table_get_id(btei);
116 
120  &dpo);
121 
122  /*
123  * select the appropriate bucket from the LB
124  */
125  if (dpo.dpoi_type == DPO_LOAD_BALANCE)
126  {
127  lb = load_balance_get(dpo.dpoi_index);
128  choice = load_balance_get_bucket_i(lb,
129  btid->bti_ecmp &
130  (lb->lb_n_buckets_minus_1));
131  }
132  else
133  {
134  choice = &dpo;
135  }
136 
137  if (choice->dpoi_type == DPO_BIER_FMASK)
138  {
140  choice->dpoi_index);
141  }
142  else
143  {
144  /*
145  * any other type results in a drop, which we represent
146  * with an empty bucket
147  */
149  INDEX_INVALID);
150  }
151 
152  dpo_reset(&dpo);
153  }
154  else
155  {
156  /*
157  * no fmasks left. insert a drop
158  */
160  }
161 }
162 
163 void
165  const fib_route_path_t *rpaths)
166 {
167  fib_node_index_t old_pl_index;
168  bier_entry_t *be;
169 
170  be = bier_entry_get(bei);
171  old_pl_index = be->be_path_list;
172 
173  /*
174  * lock the path-list so it does not go away before we unlink
175  * from its resolved fmasks
176  */
177  fib_path_list_lock(old_pl_index);
178 
180  {
181  old_pl_index = FIB_NODE_INDEX_INVALID;
184  rpaths);
188  }
189  else
190  {
191 
192  old_pl_index = be->be_path_list;
193 
194  be->be_path_list =
195  fib_path_list_copy_and_path_add(old_pl_index,
198  rpaths);
199 
200  fib_path_list_child_remove(old_pl_index,
201  be->be_sibling_index);
205  }
206  /*
207  * link the entry's bit-position to each fmask in the new path-list
208  * then unlink from the old.
209  */
212  be);
213  if (FIB_NODE_INDEX_INVALID != old_pl_index)
214  {
215  fib_path_list_walk(old_pl_index,
217  be);
218  }
219 
220  /*
221  * update the ECNP tables with the new choice
222  */
225  be);
226 
227  /*
228  * symmetric unlock. The old path-list may not exist hereinafter
229  */
230  fib_path_list_unlock(old_pl_index);
231 }
232 
233 int
235  const fib_route_path_t *rpaths)
236 {
237  fib_node_index_t old_pl_index;
238  bier_entry_t *be;
239 
240  be = bier_entry_get(bei);
241  old_pl_index = be->be_path_list;
242 
243  fib_path_list_lock(old_pl_index);
244 
246 
247  be->be_path_list =
251  rpaths);
252 
253  if (be->be_path_list != old_pl_index)
254  {
255  /*
256  * a path was removed
257  */
258  fib_path_list_child_remove(old_pl_index,
259  be->be_sibling_index);
260 
262  {
263  /*
264  * link the entry's bit-position to each fmask in the new path-list
265  * then unlink from the old.
266  */
269  be);
270  be->be_sibling_index =
274  }
275 
276  fib_path_list_walk(old_pl_index,
278  be);
279  }
280  fib_path_list_unlock(old_pl_index);
281 
282 
283  /*
284  * update the ECNP tables with the new choice
285  */
288  be);
289 
291 }
292 
293 void
295  dpo_id_t *dpo)
296 {
297  bier_entry_t *be = bier_entry_get(bei);
298 
302  dpo);
303 }
304 
305 u8*
306 format_bier_entry (u8* s, va_list *ap)
307 {
308  index_t bei = va_arg(*ap, index_t);
310 
311  bier_entry_t *be = bier_entry_get(bei);
312 
313  s = format(s, " bp:%d\n", be->be_bp);
315 
316  if (flags & BIER_SHOW_DETAIL)
317  {
318  dpo_id_t dpo = DPO_INVALID;
319 
321 
322  s = format(s, " forwarding:\n");
323  s = format(s, " %U",
324  format_dpo_id, &dpo, 2);
325  s = format(s, "\n");
326  }
327 
328  return (s);
329 }
330 
331 static fib_node_t *
333 {
334  bier_entry_t *be = bier_entry_get(index);
335  return (&(be->be_node));
336 }
337 
338 static bier_entry_t*
340 {
341  return ((bier_entry_t*)(((char*)node) -
343  be_node)));
344 }
345 
346 static void
348 {
349  /*
350  * the lifetime of the entry is managed by the table.
351  */
352  ASSERT(0);
353 }
354 
355 /*
356  * A back walk has reached this BIER entry
357  */
361 {
362  /*
363  * re-populate the ECMP tables with new choices
364  */
366 
369  be);
370 
371  /*
372  * no need to propagate further up the graph.
373  */
375 }
376 
377 /*
378  * The BIER fmask's graph node virtual function table
379  */
380 static const fib_node_vft_t bier_entry_vft = {
382  .fnv_last_lock = bier_entry_last_lock_gone,
383  .fnv_back_walk = bier_entry_back_walk_notify,
384 };
385 
386 clib_error_t *
388 {
390 
391  return (NULL);
392 }
393 
Contribute an object that is to be used to forward BIER packets.
Definition: fib_types.h:112
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 *rpath)
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:347
index_t fib_path_get_resolving_index(fib_node_index_t path_index)
Definition: fib_path.c:2079
A representation of a path as described by a route producer.
Definition: fib_types.h:455
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:77
#define NULL
Definition: clib.h:55
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:62
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
static bier_entry_t * bier_entry_get(index_t bei)
Definition: bier_entry.h:90
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:294
clib_error_t * bier_entry_module_init(vlib_main_t *vm)
Definition: bier_entry.c:387
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:227
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:318
#define VLIB_INIT_FUNCTION(x)
Definition: init.h:156
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:99
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:298
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:168
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:172
static const dpo_id_t * load_balance_get_bucket_i(const load_balance_t *lb, u32 bucket)
Definition: load_balance.h:209
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:273
The FIB DPO provieds;.
Definition: load_balance.h:84
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:99
An node in the FIB graph.
Definition: fib_node.h:286
int bier_entry_path_remove(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:234
static fib_node_t * bier_entry_get_node(fib_node_index_t index)
Definition: bier_entry.c:332
fib_node_t be_node
linkage into the FIB graph
Definition: bier_entry.h:50
vlib_main_t * vm
Definition: buffer.c:294
fib_node_get_t fnv_get
Definition: fib_node.h:274
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:199
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:488
long ctx[MAX_CONNS]
Definition: main.c:126
static load_balance_t * load_balance_get(index_t lbi)
Definition: load_balance.h:200
u8 * format_bier_entry(u8 *s, va_list *ap)
Definition: bier_entry.c:306
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:359
u8 * format_dpo_id(u8 *s, va_list *args)
Format a DPO_id_t oject
Definition: dpo.c:147
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:184
#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:339
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:195
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:273
void bier_entry_path_add(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:164
void dpo_reset(dpo_id_t *dpo)
reset a DPO ID The DPO will be unlocked.
Definition: dpo.c:231
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:670
void bier_table_ecmp_set_fmask(index_t bti, bier_bp_t bp, index_t bfmi)
Definition: bier_table.c:688
u32 flags
Definition: vhost-user.h:77
static index_t bier_entry_get_index(const bier_entry_t *be)
Definition: bier_entry.c:28