FD.io VPP  v18.07.1-19-g511ce25
Vector Packet Processing
fib_path_ext.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/mpls/mpls.h>
18 #include <vnet/dpo/load_balance.h>
19 #include <vnet/dpo/drop_dpo.h>
20 
21 #include <vnet/fib/fib_path_ext.h>
22 #include <vnet/fib/fib_entry_src.h>
23 #include <vnet/fib/fib_path.h>
24 #include <vnet/fib/fib_path_list.h>
25 #include <vnet/fib/fib_internal.h>
26 
29 
30 u8 *
31 format_fib_path_ext (u8 * s, va_list * args)
32 {
33  fib_path_ext_t *path_ext;
34  u32 ii;
35 
36  path_ext = va_arg (*args, fib_path_ext_t *);
37 
38  s = format(s, "path:%d ", path_ext->fpe_path_index);
39 
40  switch (path_ext->fpe_type)
41  {
42  case FIB_PATH_EXT_MPLS: {
44 
45  if (path_ext->fpe_mpls_flags)
46  {
47  s = format(s, "mpls-flags:[");
48 
50  {
51  if ((1<<attr) & path_ext->fpe_mpls_flags) {
52  s = format(s, "%s", fib_path_ext_mpls_flags_names[attr]);
53  }
54  }
55  s = format(s, "]");
56  }
57  s = format(s, " labels:[",
58  path_ext->fpe_path_index);
59  for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
60  {
61  s = format(s, "[%U]",
63  &path_ext->fpe_path.frp_label_stack[ii]);
64  }
65  s = format(s, "]");
66  break;
67  }
68  case FIB_PATH_EXT_ADJ: {
70 
71  if (path_ext->fpe_adj_flags)
72  {
73  s = format(s, "adj-flags:[");
75  {
76  if ((1<<attr) & path_ext->fpe_adj_flags)
77  {
78  s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
79  }
80  }
81  s = format(s, "]");
82  }
83  break;
84  }
85  }
86  return (s);
87 }
88 
89 int
91  const fib_route_path_t *rpath)
92 {
93  return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
94 }
95 
98  fib_node_index_t path_index,
99  void *ctx)
100 {
101  fib_path_ext_t *path_ext = ctx;
102 
103  if (!fib_path_cmp_w_route_path(path_index,
104  &path_ext->fpe_path))
105  {
106  path_ext->fpe_path_index = path_index;
107  return (FIB_PATH_LIST_WALK_STOP);
108  }
110 }
111 
112 void
114  fib_node_index_t path_list_index)
115 {
116  /*
117  * Find the path on the path list that this is an extension for
118  */
120  fib_path_list_walk(path_list_index,
122  path_ext);
123 }
124 
125 static void
127  fib_node_index_t path_list_index,
128  fib_path_ext_type_t ext_type,
129  const fib_route_path_t *rpath)
130 {
131  path_ext->fpe_path = *rpath;
134  path_ext->fpe_type = ext_type;
135 
136  fib_path_ext_resolve(path_ext, path_list_index);
137 }
138 
139 /**
140  * @brief Return true if the label stack is implicit null
141  * imp-null and pop equate to the same this as this level -
142  * the label is coming off.
143  */
144 static int
146 {
147  return ((1 == vec_len(path_ext->fpe_label_stack)) &&
148  ((MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0].fml_value) ||
149  (MPLS_LABEL_POP == path_ext->fpe_label_stack[0].fml_value)));
150 }
151 
154 {
156 
158  {
160  }
161 
162  return (ml_flags);
163 }
164 
167  fib_forward_chain_type_t child_fct,
168  fib_forward_chain_type_t imp_null_fct,
169  load_balance_path_t *nhs)
170 {
171  fib_forward_chain_type_t parent_fct;
173 
174  if (!fib_path_is_resolved(path_ext->fpe_path_index))
175  return (nhs);
176 
177  /*
178  * Since we are stacking this path-extension, it must have a valid out
179  * label. From the chain type request by the child, determine what
180  * chain type we will request from the parent.
181  */
182  switch (child_fct)
183  {
185  {
186  /*
187  * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
188  * the adjacency to link to without knowing what the packets payload protocol
189  * will be once the label is popped.
190  */
191  if (fib_path_ext_is_imp_null(path_ext))
192  {
193  parent_fct = imp_null_fct;
194  }
195  else
196  {
197  /*
198  * we have a label to stack. packets will thus be labelled when
199  * they encounter the child, ergo, non-eos.
200  */
202  }
203  break;
204  }
207  if (fib_path_ext_is_imp_null(path_ext))
208  {
209  /*
210  * implicit-null label for the eos or IP chain, need to pick up
211  * the IP adj
212  */
213  parent_fct = child_fct;
214  }
215  else
216  {
217  /*
218  * we have a label to stack. packets will thus be labelled when
219  * they encounter the child, ergo, non-eos.
220  */
222  }
223  break;
225  parent_fct = child_fct;
226  break;
229  break;
230  default:
231  return (nhs);
232  break;
233  }
234 
235  dpo_id_t via_dpo = DPO_INVALID;
236 
237  /*
238  * The next object in the graph after the imposition of the label
239  * will be the DPO contributed by the path through which the packets
240  * are to be sent. We stack the MPLS Label DPO on this path DPO
241  */
243  parent_fct,
244  &via_dpo);
245 
246  if (dpo_is_drop(&via_dpo) ||
247  load_balance_is_drop(&via_dpo))
248  {
249  /*
250  * don't stack a path extension on a drop. doing so will create
251  * a LB bucket entry on drop, and we will lose a percentage of traffic.
252  */
253  }
254  else
255  {
256  vec_add2(nhs, nh, 1);
258  nh->path_index = path_ext->fpe_path_index;
259  dpo_copy(&nh->path_dpo, &via_dpo);
260 
261  /*
262  * The label is stackable for this chain type
263  * construct the mpls header that will be imposed in the data-path
264  */
265  if (!fib_path_ext_is_imp_null(path_ext))
266  {
267  /*
268  * we use the parent protocol for the label so that
269  * we pickup the correct MPLS imposition nodes to do
270  * ip[46] processing.
271  */
272  dpo_id_t parent = DPO_INVALID;
273  dpo_proto_t chain_proto;
274  mpls_eos_bit_t eos;
275 
276  eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
277  MPLS_NON_EOS :
278  MPLS_EOS);
279  chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
280 
281  dpo_copy(&parent, &nh->path_dpo);
282  mpls_label_dpo_create(path_ext->fpe_label_stack,
283  eos,
284  chain_proto,
286  path_ext->fpe_mpls_flags),
287  &parent,
288  &nh->path_dpo);
289 
290  dpo_reset(&parent);
291  }
292  else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
293  {
294  /*
295  * MPLS EOS packets using an imp-null. Insert the disposition.
296  */
299  path_ext->fpe_label_stack[0].fml_mode,
300  &nh->path_dpo);
301  }
302  }
303  dpo_reset(&via_dpo);
304 
305  return (nhs);
306 }
307 
310  fib_path_ext_type_t ext_type,
311  const fib_route_path_t *rpath)
312 {
313  fib_path_ext_t *path_ext;
314 
315  vec_foreach(path_ext, list->fpel_exts)
316  {
317  if ((path_ext->fpe_type == ext_type) &&
318  !fib_path_ext_cmp(path_ext, rpath) )
319  {
320  return (path_ext);
321  }
322  }
323  return (NULL);
324 }
325 
328  fib_node_index_t path_index)
329 {
330  fib_path_ext_t *path_ext;
331 
332  vec_foreach(path_ext, list->fpel_exts)
333  {
334  if (path_ext->fpe_path_index == path_index)
335  {
336  return (path_ext);
337  }
338  }
339  return (NULL);
340 }
341 
342 
345  fib_node_index_t path_list_index,
346  fib_path_ext_type_t ext_type,
347  const fib_route_path_t *rpath)
348 {
349  fib_path_ext_t *path_ext;
350 
351  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
352 
353  if (NULL == path_ext)
354  {
355  vec_add2(list->fpel_exts, path_ext, 1);
356  fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
357  }
358 
359  return (path_ext);
360 }
361 
362 /*
363  * insert, sorted, a path extension to the entry's list.
364  * It's not strictly necessary to sort the path extensions, since each
365  * extension has the path index to which it resolves. However, by being
366  * sorted the load-balance produced has a deterministic order, not an order
367  * based on the sequence of extension additions. this is a considerable benefit.
368  */
371  fib_node_index_t path_list_index,
372  fib_path_ext_type_t ext_type,
373  const fib_route_path_t *rpath)
374 {
375  fib_path_ext_t new_path_ext, *path_ext;
376  int i = 0;
377 
378  if (0 == fib_path_ext_list_length(list))
379  {
380  return (fib_path_ext_list_push_back(list, path_list_index,
381  ext_type, rpath));
382  }
383 
384  fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
385 
386  vec_foreach(path_ext, list->fpel_exts)
387  {
388  int res = fib_path_ext_cmp(path_ext, rpath);
389 
390  if (0 == res)
391  {
392  /*
393  * don't add duplicate extensions. modify instead
394  */
395  vec_free(path_ext->fpe_label_stack);
396  *path_ext = new_path_ext;
397  goto done;
398  }
399  else if (res < 0)
400  {
401  i++;
402  }
403  else
404  {
405  break;
406  }
407  }
408  vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
409 done:
410  return (&(list->fpel_exts[i]));
411 }
412 
413 void
415  fib_node_index_t path_list_index)
416 {
417  fib_path_ext_t *path_ext;
418 
419  vec_foreach(path_ext, list->fpel_exts)
420  {
421  fib_path_ext_resolve(path_ext, path_list_index);
422  };
423 }
424 
425 void
427  fib_path_ext_type_t ext_type,
428  const fib_route_path_t *rpath)
429 {
430  fib_path_ext_t *path_ext;
431 
432  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
433 
434  if (NULL != path_ext)
435  {
436  /*
437  * delete the element moving the remaining elements down 1 position.
438  * this preserves the sorted order.
439  */
440  vec_free(path_ext->fpe_label_stack);
441  vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
442  }
443 }
444 
445 void
447 {
448  fib_path_ext_t *path_ext;
449 
450  vec_foreach(path_ext, list->fpel_exts)
451  {
452  vec_free(path_ext->fpe_label_stack);
453  };
454  vec_free(list->fpel_exts);
455  list->fpel_exts = NULL;
456 }
457 
458 u8*
459 format_fib_path_ext_list (u8 * s, va_list * args)
460 {
461  fib_path_ext_list_t *list;
462  fib_path_ext_t *path_ext;
463 
464  list = va_arg (*args, fib_path_ext_list_t *);
465 
466  if (fib_path_ext_list_length(list))
467  {
468  s = format(s, " Extensions:");
469  vec_foreach(path_ext, list->fpel_exts)
470  {
471  s = format(s, "\n %U", format_fib_path_ext, path_ext);
472  };
473  }
474 
475  return (s);
476 }
477 
478 int
480 {
481  return (vec_len(list->fpel_exts));
482 }
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2557
enum fib_path_ext_type_t_ fib_path_ext_type_t
A description of the type of path extension.
fib_path_ext_type_t fpe_type
The type of path extension.
Definition: fib_path_ext.h:126
Contribute an object that is to be used to forward IP6 packets.
Definition: fib_types.h:103
fib_node_index_t path_index
The index of the FIB path.
Definition: load_balance.h:71
void fib_path_contribute_forwarding(fib_node_index_t path_index, fib_forward_chain_type_t fct, dpo_id_t *dpo)
Definition: fib_path.c:2291
void fib_path_ext_resolve(fib_path_ext_t *path_ext, fib_node_index_t path_list_index)
Definition: fib_path_ext.c:113
A representation of a path as described by a route producer.
Definition: fib_types.h:460
int fib_path_ext_cmp(fib_path_ext_t *path_ext, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:90
dpo_id_t path_dpo
ID of the Data-path object.
Definition: load_balance.h:66
int fib_route_path_cmp(const fib_route_path_t *rpath1, const fib_route_path_t *rpath2)
Definition: fib_types.c:214
const char * fib_path_ext_adj_flags_names[]
Definition: fib_path_ext.c:27
#define NULL
Definition: clib.h:55
#define FIB_PATH_EXT_ADJ_ATTR_NAMES
Definition: fib_path_ext.h:53
An MPLS extension that maintains the path&#39;s outgoing labels,.
Definition: fib_path_ext.h:31
dpo_proto_t fib_forw_chain_type_to_dpo_proto(fib_forward_chain_type_t fct)
Convert from a chain type to the DPO proto it will install.
Definition: fib_types.c:376
#define MPLS_IETF_IMPLICIT_NULL_LABEL
Definition: mpls_types.h:30
void dpo_copy(dpo_id_t *dst, const dpo_id_t *src)
atomic copy a data-plane object.
Definition: dpo.c:261
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:562
struct fib_path_ext_t_ * fpel_exts
Definition: fib_types.h:588
int i
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
Contribute an object that is to be used to forward IP4 packets.
Definition: fib_types.h:99
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
unsigned char u8
Definition: types.h:56
#define FOR_EACH_PATH_EXT_MPLS_ATTR(_item)
Definition: fib_path_ext.h:83
unsigned int u32
Definition: types.h:88
Contribute an object that is to be used to forward Ethernet packets.
Definition: fib_types.h:131
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
int load_balance_is_drop(const dpo_id_t *dpo)
Definition: load_balance.c:227
u16 fib_path_get_weight(fib_node_index_t path_index)
Definition: fib_path.c:2126
fib_path_ext_t * fib_path_ext_list_find_by_path_index(const fib_path_ext_list_t *list, fib_node_index_t path_index)
Definition: fib_path_ext.c:327
enum mpls_label_dpo_flags_t_ mpls_label_dpo_flags_t
fib_path_ext_mpls_flags_t fpe_mpls_flags
For an MPLS type extension.
Definition: fib_path_ext.h:120
A adj-source extension indicating the path&#39;s refinement criteria result.
Definition: fib_path_ext.h:36
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
Contribute an object that is to be used to forward end-of-stack MPLS packets.
Definition: fib_types.h:119
void fib_path_ext_list_flush(fib_path_ext_list_t *list)
Definition: fib_path_ext.c:446
static fib_path_list_walk_rc_t fib_path_ext_match(fib_node_index_t pl_index, fib_node_index_t path_index, void *ctx)
Definition: fib_path_ext.c:97
void mpls_label_dpo_create(fib_mpls_label_t *label_stack, mpls_eos_bit_t eos, dpo_proto_t payload_proto, mpls_label_dpo_flags_t flags, const dpo_id_t *parent, dpo_id_t *dpo)
Create an MPLS label object.
fib_mpls_label_t * frp_label_stack
The outgoing MPLS label Stack.
Definition: fib_types.h:515
A list of path-extensions.
Definition: fib_types.h:586
void fib_path_stack_mpls_disp(fib_node_index_t path_index, dpo_proto_t payload_proto, fib_mpls_lsp_mode_t mode, dpo_id_t *dpo)
Definition: fib_path.c:2240
mpls_label_dpo_flags_t fib_path_ext_mpls_flags_to_mpls_label(fib_path_ext_mpls_flags_t fpe_flags)
Definition: fib_path_ext.c:153
u8 * format_fib_path_ext(u8 *s, va_list *args)
Definition: fib_path_ext.c:31
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:339
void fib_path_ext_list_remove(fib_path_ext_list_t *list, fib_path_ext_type_t ext_type, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:426
fib_path_ext_t * fib_path_ext_list_push_back(fib_path_ext_list_t *list, fib_node_index_t path_list_index, fib_path_ext_type_t ext_type, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:344
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
enum fib_path_ext_mpls_attr_t_ fib_path_ext_mpls_attr_t
Flags present on an MPLS label sourced path-extension.
#define vec_delete(V, N, M)
Delete N elements starting at element M.
Definition: vec.h:786
long ctx[MAX_CONNS]
Definition: main.c:126
static void fib_path_ext_init(fib_path_ext_t *path_ext, fib_node_index_t path_list_index, fib_path_ext_type_t ext_type, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:126
#define vec_insert_elts(V, E, N, M)
Insert N vector elements starting at element M, insert given elements (no header, unspecified alignme...
Definition: vec.h:765
enum fib_forward_chain_type_t_ fib_forward_chain_type_t
FIB output chain type.
int fib_path_ext_list_length(const fib_path_ext_list_t *list)
Definition: fib_path_ext.c:479
#define MPLS_LABEL_POP
A value that is explicit about the end of the LSP.
Definition: mpls_types.h:56
#define FIB_PATH_EXT_MPLS_ATTR_NAMES
Definition: fib_path_ext.h:79
enum fib_path_ext_mpls_flags_t_ fib_path_ext_mpls_flags_t
fib_path_ext_adj_flags_t fpe_adj_flags
For an ADJ type extension.
Definition: fib_path_ext.h:114
#define FOR_EACH_PATH_EXT_ADJ_ATTR(_item)
Definition: fib_path_ext.h:57
enum fib_path_list_walk_rc_t_ fib_path_list_walk_rc_t
return code to control pat-hlist walk
fib_path_ext_t * fib_path_ext_list_find(const fib_path_ext_list_t *list, fib_path_ext_type_t ext_type, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:309
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
void fib_path_ext_list_resolve(fib_path_ext_list_t *list, fib_node_index_t path_list_index)
Definition: fib_path_ext.c:414
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u32 path_weight
weight for the path.
Definition: load_balance.h:76
fib_node_index_t fpe_path_index
The index of the path.
Definition: fib_path_ext.h:132
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:195
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:62
u8 * format_fib_mpls_label(u8 *s, va_list *ap)
Format an MPLS label.
Definition: fib_types.c:64
static int fib_path_ext_is_imp_null(fib_path_ext_t *path_ext)
Return true if the label stack is implicit null imp-null and pop equate to the same this as this leve...
Definition: fib_path_ext.c:145
int dpo_is_drop(const dpo_id_t *dpo)
The Drop DPO will drop all packets, no questions asked.
Definition: drop_dpo.c:33
void dpo_reset(dpo_id_t *dpo)
reset a DPO ID The DPO will be unlocked.
Definition: dpo.c:231
#define vec_foreach(var, vec)
Vector iterator.
A path extension is a per-entry addition to the forwarding information when packets are sent for that...
Definition: fib_path_ext.h:98
u8 * format_fib_path_ext_list(u8 *s, va_list *args)
Definition: fib_path_ext.c:459
Contribute an object that is to be used to forward non-end-of-stack MPLS packets. ...
Definition: fib_types.h:108
const char * fib_path_ext_mpls_flags_names[]
Definition: fib_path_ext.c:28
enum fib_path_ext_adj_attr_t_ fib_path_ext_adj_attr_t
Flags present on an ADJ sourced path-extension.
int fib_path_cmp_w_route_path(fib_node_index_t path_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1633
fib_route_path_t fpe_path
A description of the path that is being extended.
Definition: fib_path_ext.h:105
fib_path_ext_t * fib_path_ext_list_insert(fib_path_ext_list_t *list, fib_node_index_t path_list_index, fib_path_ext_type_t ext_type, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:370
load_balance_path_t * fib_path_ext_stack(fib_path_ext_t *path_ext, fib_forward_chain_type_t child_fct, fib_forward_chain_type_t imp_null_fct, load_balance_path_t *nhs)
Definition: fib_path_ext.c:166
enum mpls_eos_bit_t_ mpls_eos_bit_t