FD.io VPP  v18.10-34-gcce845e
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  for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
59  {
60  s = format(s, "[%U]",
62  &path_ext->fpe_path.frp_label_stack[ii]);
63  }
64  s = format(s, "]");
65  break;
66  }
67  case FIB_PATH_EXT_ADJ: {
69 
70  if (path_ext->fpe_adj_flags)
71  {
72  s = format(s, "adj-flags:[");
74  {
75  if ((1<<attr) & path_ext->fpe_adj_flags)
76  {
77  s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
78  }
79  }
80  s = format(s, "]");
81  }
82  break;
83  }
84  }
85  return (s);
86 }
87 
88 int
90  const fib_route_path_t *rpath)
91 {
92  return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
93 }
94 
97  fib_node_index_t path_index,
98  void *ctx)
99 {
100  fib_path_ext_t *path_ext = ctx;
101 
102  if (!fib_path_cmp_w_route_path(path_index,
103  &path_ext->fpe_path))
104  {
105  path_ext->fpe_path_index = path_index;
106  return (FIB_PATH_LIST_WALK_STOP);
107  }
109 }
110 
111 void
113  fib_node_index_t path_list_index)
114 {
115  /*
116  * Find the path on the path list that this is an extension for
117  */
119  fib_path_list_walk(path_list_index,
121  path_ext);
122 }
123 
124 static void
126  fib_node_index_t path_list_index,
127  fib_path_ext_type_t ext_type,
128  const fib_route_path_t *rpath)
129 {
130  path_ext->fpe_path = *rpath;
133  path_ext->fpe_type = ext_type;
134 
135  fib_path_ext_resolve(path_ext, path_list_index);
136 }
137 
138 /**
139  * @brief Return true if the label stack is implicit null
140  * imp-null and pop equate to the same this as this level -
141  * the label is coming off.
142  */
143 static int
145 {
146  return ((1 == vec_len(path_ext->fpe_label_stack)) &&
147  ((MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0].fml_value) ||
148  (MPLS_LABEL_POP == path_ext->fpe_label_stack[0].fml_value)));
149 }
150 
153 {
155 
157  {
159  }
160 
161  return (ml_flags);
162 }
163 
166  fib_forward_chain_type_t child_fct,
167  fib_forward_chain_type_t imp_null_fct,
168  load_balance_path_t *nhs)
169 {
170  fib_forward_chain_type_t parent_fct;
172 
173  if (!fib_path_is_resolved(path_ext->fpe_path_index))
174  return (nhs);
175 
176  /*
177  * Since we are stacking this path-extension, it must have a valid out
178  * label. From the chain type request by the child, determine what
179  * chain type we will request from the parent.
180  */
181  switch (child_fct)
182  {
184  {
185  /*
186  * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
187  * the adjacency to link to without knowing what the packets payload protocol
188  * will be once the label is popped.
189  */
190  if (fib_path_ext_is_imp_null(path_ext))
191  {
192  parent_fct = imp_null_fct;
193  }
194  else
195  {
196  /*
197  * we have a label to stack. packets will thus be labelled when
198  * they encounter the child, ergo, non-eos.
199  */
201  }
202  break;
203  }
206  if (fib_path_ext_is_imp_null(path_ext))
207  {
208  /*
209  * implicit-null label for the eos or IP chain, need to pick up
210  * the IP adj
211  */
212  parent_fct = child_fct;
213  }
214  else
215  {
216  /*
217  * we have a label to stack. packets will thus be labelled when
218  * they encounter the child, ergo, non-eos.
219  */
221  }
222  break;
224  parent_fct = child_fct;
225  break;
228  break;
229  default:
230  return (nhs);
231  break;
232  }
233 
234  dpo_id_t via_dpo = DPO_INVALID;
235 
236  /*
237  * The next object in the graph after the imposition of the label
238  * will be the DPO contributed by the path through which the packets
239  * are to be sent. We stack the MPLS Label DPO on this path DPO
240  */
242  parent_fct,
243  &via_dpo);
244 
245  if (dpo_is_drop(&via_dpo) ||
246  load_balance_is_drop(&via_dpo))
247  {
248  /*
249  * don't stack a path extension on a drop. doing so will create
250  * a LB bucket entry on drop, and we will lose a percentage of traffic.
251  */
252  }
253  else
254  {
255  vec_add2(nhs, nh, 1);
257  nh->path_index = path_ext->fpe_path_index;
258  dpo_copy(&nh->path_dpo, &via_dpo);
259 
260  /*
261  * The label is stackable for this chain type
262  * construct the mpls header that will be imposed in the data-path
263  */
264  if (!fib_path_ext_is_imp_null(path_ext))
265  {
266  /*
267  * we use the parent protocol for the label so that
268  * we pickup the correct MPLS imposition nodes to do
269  * ip[46] processing.
270  */
271  dpo_id_t parent = DPO_INVALID;
272  dpo_proto_t chain_proto;
273  mpls_eos_bit_t eos;
274 
275  eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
276  MPLS_NON_EOS :
277  MPLS_EOS);
278  chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
279 
280  dpo_copy(&parent, &nh->path_dpo);
281  mpls_label_dpo_create(path_ext->fpe_label_stack,
282  eos,
283  chain_proto,
285  path_ext->fpe_mpls_flags),
286  &parent,
287  &nh->path_dpo);
288 
289  dpo_reset(&parent);
290  }
291  else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
292  {
293  /*
294  * MPLS EOS packets using an imp-null. Insert the disposition.
295  */
298  path_ext->fpe_label_stack[0].fml_mode,
299  &nh->path_dpo);
300  }
301  }
302  dpo_reset(&via_dpo);
303 
304  return (nhs);
305 }
306 
309  fib_path_ext_type_t ext_type,
310  const fib_route_path_t *rpath)
311 {
312  fib_path_ext_t *path_ext;
313 
314  vec_foreach(path_ext, list->fpel_exts)
315  {
316  if ((path_ext->fpe_type == ext_type) &&
317  !fib_path_ext_cmp(path_ext, rpath) )
318  {
319  return (path_ext);
320  }
321  }
322  return (NULL);
323 }
324 
327  fib_node_index_t path_index)
328 {
329  fib_path_ext_t *path_ext;
330 
331  vec_foreach(path_ext, list->fpel_exts)
332  {
333  if (path_ext->fpe_path_index == path_index)
334  {
335  return (path_ext);
336  }
337  }
338  return (NULL);
339 }
340 
341 
344  fib_node_index_t path_list_index,
345  fib_path_ext_type_t ext_type,
346  const fib_route_path_t *rpath)
347 {
348  fib_path_ext_t *path_ext;
349 
350  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
351 
352  if (NULL == path_ext)
353  {
354  vec_add2(list->fpel_exts, path_ext, 1);
355  fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
356  }
357 
358  return (path_ext);
359 }
360 
361 /*
362  * insert, sorted, a path extension to the entry's list.
363  * It's not strictly necessary to sort the path extensions, since each
364  * extension has the path index to which it resolves. However, by being
365  * sorted the load-balance produced has a deterministic order, not an order
366  * based on the sequence of extension additions. this is a considerable benefit.
367  */
370  fib_node_index_t path_list_index,
371  fib_path_ext_type_t ext_type,
372  const fib_route_path_t *rpath)
373 {
374  fib_path_ext_t new_path_ext, *path_ext;
375  int i = 0;
376 
377  if (0 == fib_path_ext_list_length(list))
378  {
379  return (fib_path_ext_list_push_back(list, path_list_index,
380  ext_type, rpath));
381  }
382 
383  fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
384 
385  vec_foreach(path_ext, list->fpel_exts)
386  {
387  int res = fib_path_ext_cmp(path_ext, rpath);
388 
389  if (0 == res)
390  {
391  /*
392  * don't add duplicate extensions. modify instead
393  */
394  vec_free(path_ext->fpe_label_stack);
395  *path_ext = new_path_ext;
396  goto done;
397  }
398  else if (res < 0)
399  {
400  i++;
401  }
402  else
403  {
404  break;
405  }
406  }
407  vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
408 done:
409  return (&(list->fpel_exts[i]));
410 }
411 
412 void
414  fib_node_index_t path_list_index)
415 {
416  fib_path_ext_t *path_ext;
417 
418  vec_foreach(path_ext, list->fpel_exts)
419  {
420  fib_path_ext_resolve(path_ext, path_list_index);
421  };
422 }
423 
424 void
426  fib_path_ext_type_t ext_type,
427  const fib_route_path_t *rpath)
428 {
429  fib_path_ext_t *path_ext;
430 
431  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
432 
433  if (NULL != path_ext)
434  {
435  /*
436  * delete the element moving the remaining elements down 1 position.
437  * this preserves the sorted order.
438  */
439  vec_free(path_ext->fpe_label_stack);
440  vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
441  }
442 }
443 
444 void
446 {
447  fib_path_ext_t *path_ext;
448 
449  vec_foreach(path_ext, list->fpel_exts)
450  {
451  vec_free(path_ext->fpe_label_stack);
452  };
453  vec_free(list->fpel_exts);
454  list->fpel_exts = NULL;
455 }
456 
457 u8*
458 format_fib_path_ext_list (u8 * s, va_list * args)
459 {
460  fib_path_ext_list_t *list;
461  fib_path_ext_t *path_ext;
462 
463  list = va_arg (*args, fib_path_ext_list_t *);
464 
465  if (fib_path_ext_list_length(list))
466  {
467  s = format(s, " Extensions:");
468  vec_foreach(path_ext, list->fpel_exts)
469  {
470  s = format(s, "\n %U", format_fib_path_ext, path_ext);
471  };
472  }
473 
474  return (s);
475 }
476 
477 int
479 {
480  return (vec_len(list->fpel_exts));
481 }
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2569
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:113
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:2303
void fib_path_ext_resolve(fib_path_ext_t *path_ext, fib_node_index_t path_list_index)
Definition: fib_path_ext.c:112
A representation of a path as described by a route producer.
Definition: fib_types.h:470
int fib_path_ext_cmp(fib_path_ext_t *path_ext, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:89
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:57
#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:410
#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:603
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:109
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:141
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
int load_balance_is_drop(const dpo_id_t *dpo)
Definition: load_balance.c:236
u16 fib_path_get_weight(fib_node_index_t path_index)
Definition: fib_path.c:2138
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:326
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:129
void fib_path_ext_list_flush(fib_path_ext_list_t *list)
Definition: fib_path_ext.c:445
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:96
long ctx[MAX_CONNS]
Definition: main.c:144
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:525
A list of path-extensions.
Definition: fib_types.h:601
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:2252
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:152
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:425
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:343
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
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:125
#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:478
#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:308
#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:413
#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:144
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:458
Contribute an object that is to be used to forward non-end-of-stack MPLS packets. ...
Definition: fib_types.h:118
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:1640
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:369
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:165
enum mpls_eos_bit_t_ mpls_eos_bit_t