FD.io VPP  v18.01.2-1-g9b554f3
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 
28 
29 u8 *
30 format_fib_path_ext (u8 * s, va_list * args)
31 {
32  fib_path_ext_t *path_ext;
33  u32 ii;
34 
35  path_ext = va_arg (*args, fib_path_ext_t *);
36 
37  s = format(s, "path:%d ", path_ext->fpe_path_index);
38 
39  switch (path_ext->fpe_type)
40  {
41  case FIB_PATH_EXT_MPLS:
42  s = format(s, "labels:",
43  path_ext->fpe_path_index);
44  for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
45  {
46  s = format(s, "%U ",
48  path_ext->fpe_path.frp_label_stack[ii]);
49  }
50  break;
51  case FIB_PATH_EXT_ADJ: {
53 
54  s = format(s, "adj-flags:");
55  if (path_ext->fpe_adj_flags)
56  {
58  {
59  s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
60  }
61  }
62  else
63  {
64  s = format(s, "None");
65  }
66  break;
67  }
68  }
69  return (s);
70 }
71 
72 int
74  const fib_route_path_t *rpath)
75 {
76  return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
77 }
78 
81  fib_node_index_t path_index,
82  void *ctx)
83 {
84  fib_path_ext_t *path_ext = ctx;
85 
86  if (!fib_path_cmp_w_route_path(path_index,
87  &path_ext->fpe_path))
88  {
89  path_ext->fpe_path_index = path_index;
90  return (FIB_PATH_LIST_WALK_STOP);
91  }
93 }
94 
95 void
97  fib_node_index_t path_list_index)
98 {
99  /*
100  * Find the path on the path list that this is an extension for
101  */
103  fib_path_list_walk(path_list_index,
105  path_ext);
106 }
107 
108 static void
110  fib_node_index_t path_list_index,
111  fib_path_ext_type_t ext_type,
112  const fib_route_path_t *rpath)
113 {
114  path_ext->fpe_path = *rpath;
117  path_ext->fpe_type = ext_type;
118 
119  fib_path_ext_resolve(path_ext, path_list_index);
120 }
121 
122 /**
123  * @brief Return true if the label stack is implicit null
124  */
125 static int
127 {
128  return ((1 == vec_len(path_ext->fpe_label_stack)) &&
129  (MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0]));
130 }
131 
134  fib_forward_chain_type_t child_fct,
135  fib_forward_chain_type_t imp_null_fct,
136  load_balance_path_t *nhs)
137 {
138  fib_forward_chain_type_t parent_fct;
140 
141  if (!fib_path_is_resolved(path_ext->fpe_path_index))
142  return (nhs);
143 
144  /*
145  * Since we are stacking this path-extension, it must have a valid out
146  * label. From the chain type request by the child, determine what
147  * chain type we will request from the parent.
148  */
149  switch (child_fct)
150  {
152  {
153  /*
154  * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
155  * the adjacency to link to without knowing what the packets payload protocol
156  * will be once the label is popped.
157  */
158  if (fib_path_ext_is_imp_null(path_ext))
159  {
160  parent_fct = imp_null_fct;
161  }
162  else
163  {
164  /*
165  * we have a label to stack. packets will thus be labelled when
166  * they encounter the child, ergo, non-eos.
167  */
169  }
170  break;
171  }
174  if (fib_path_ext_is_imp_null(path_ext))
175  {
176  /*
177  * implicit-null label for the eos or IP chain, need to pick up
178  * the IP adj
179  */
180  parent_fct = child_fct;
181  }
182  else
183  {
184  /*
185  * we have a label to stack. packets will thus be labelled when
186  * they encounter the child, ergo, non-eos.
187  */
189  }
190  break;
192  parent_fct = child_fct;
193  break;
196  break;
197  default:
198  return (nhs);
199  break;
200  }
201 
202  dpo_id_t via_dpo = DPO_INVALID;
203 
204  /*
205  * The next object in the graph after the imposition of the label
206  * will be the DPO contributed by the path through which the packets
207  * are to be sent. We stack the MPLS Label DPO on this path DPO
208  */
210  parent_fct,
211  &via_dpo);
212 
213  if (dpo_is_drop(&via_dpo) ||
214  load_balance_is_drop(&via_dpo))
215  {
216  /*
217  * don't stack a path extension on a drop. doing so will create
218  * a LB bucket entry on drop, and we will lose a percentage of traffic.
219  */
220  }
221  else
222  {
223  vec_add2(nhs, nh, 1);
225  nh->path_index = path_ext->fpe_path_index;
226  dpo_copy(&nh->path_dpo, &via_dpo);
227 
228  /*
229  * The label is stackable for this chain type
230  * construct the mpls header that will be imposed in the data-path
231  */
232  if (!fib_path_ext_is_imp_null(path_ext))
233  {
234  /*
235  * we use the parent protocol for the label so that
236  * we pickup the correct MPLS imposition nodes to do
237  * ip[46] processing.
238  */
239  dpo_proto_t chain_proto;
240  mpls_eos_bit_t eos;
241  index_t mldi;
242 
243  eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
244  MPLS_NON_EOS :
245  MPLS_EOS);
246  chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);
247 
248  mldi = mpls_label_dpo_create(path_ext->fpe_label_stack,
249  eos, 255, 0,
250  chain_proto,
251  &nh->path_dpo);
252 
253  dpo_set(&nh->path_dpo,
255  chain_proto,
256  mldi);
257  }
258  else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
259  {
260  /*
261  * MPLS EOS packets using an imp-null. Insert the disposition.
262  */
265  &nh->path_dpo);
266  }
267  }
268  dpo_reset(&via_dpo);
269 
270  return (nhs);
271 }
272 
275  fib_path_ext_type_t ext_type,
276  const fib_route_path_t *rpath)
277 {
278  fib_path_ext_t *path_ext;
279 
280  vec_foreach(path_ext, list->fpel_exts)
281  {
282  if ((path_ext->fpe_type == ext_type) &&
283  !fib_path_ext_cmp(path_ext, rpath) )
284  {
285  return (path_ext);
286  }
287  }
288  return (NULL);
289 }
290 
293  fib_node_index_t path_index)
294 {
295  fib_path_ext_t *path_ext;
296 
297  vec_foreach(path_ext, list->fpel_exts)
298  {
299  if (path_ext->fpe_path_index == path_index)
300  {
301  return (path_ext);
302  }
303  }
304  return (NULL);
305 }
306 
307 
310  fib_node_index_t path_list_index,
311  fib_path_ext_type_t ext_type,
312  const fib_route_path_t *rpath)
313 {
314  fib_path_ext_t *path_ext;
315 
316  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
317 
318  if (NULL == path_ext)
319  {
320  vec_add2(list->fpel_exts, path_ext, 1);
321  fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
322  }
323 
324  return (path_ext);
325 }
326 
327 /*
328  * insert, sorted, a path extension to the entry's list.
329  * It's not strictly necessary to sort the path extensions, since each
330  * extension has the path index to which it resolves. However, by being
331  * sorted the load-balance produced has a deterministic order, not an order
332  * based on the sequence of extension additions. this is a considerable benefit.
333  */
336  fib_node_index_t path_list_index,
337  fib_path_ext_type_t ext_type,
338  const fib_route_path_t *rpath)
339 {
340  fib_path_ext_t new_path_ext, *path_ext;
341  int i = 0;
342 
343  if (0 == fib_path_ext_list_length(list))
344  {
345  return (fib_path_ext_list_push_back(list, path_list_index,
346  ext_type, rpath));
347  }
348 
349  fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);
350 
351  vec_foreach(path_ext, list->fpel_exts)
352  {
353  int res = fib_path_ext_cmp(path_ext, rpath);
354 
355  if (0 == res)
356  {
357  /*
358  * don't add duplicate extensions. modify instead
359  */
360  vec_free(path_ext->fpe_label_stack);
361  *path_ext = new_path_ext;
362  goto done;
363  }
364  else if (res < 0)
365  {
366  i++;
367  }
368  else
369  {
370  break;
371  }
372  }
373  vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
374 done:
375  return (&(list->fpel_exts[i]));
376 }
377 
378 void
380  fib_node_index_t path_list_index)
381 {
382  fib_path_ext_t *path_ext;
383 
384  vec_foreach(path_ext, list->fpel_exts)
385  {
386  fib_path_ext_resolve(path_ext, path_list_index);
387  };
388 }
389 
390 void
392  fib_path_ext_type_t ext_type,
393  const fib_route_path_t *rpath)
394 {
395  fib_path_ext_t *path_ext;
396 
397  path_ext = fib_path_ext_list_find(list, ext_type, rpath);
398 
399  if (NULL != path_ext)
400  {
401  /*
402  * delete the element moving the remaining elements down 1 position.
403  * this preserves the sorted order.
404  */
405  vec_free(path_ext->fpe_label_stack);
406  vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
407  }
408 }
409 
410 void
412 {
413  fib_path_ext_t *path_ext;
414 
415  vec_foreach(path_ext, list->fpel_exts)
416  {
417  vec_free(path_ext->fpe_label_stack);
418  };
419  vec_free(list->fpel_exts);
420  list->fpel_exts = NULL;
421 }
422 
423 u8*
424 format_fib_path_ext_list (u8 * s, va_list * args)
425 {
426  fib_path_ext_list_t *list;
427  fib_path_ext_t *path_ext;
428 
429  list = va_arg (*args, fib_path_ext_list_t *);
430 
431  if (fib_path_ext_list_length(list))
432  {
433  s = format(s, " Extensions:");
434  vec_foreach(path_ext, list->fpel_exts)
435  {
436  s = format(s, "\n %U", format_fib_path_ext, path_ext);
437  };
438  }
439 
440  return (s);
441 }
442 
443 int
445 {
446  return (vec_len(list->fpel_exts));
447 }
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2528
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:94
Contribute an object that is to be used to forward IP6 packets.
Definition: fib_types.h:92
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
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:2258
void fib_path_ext_resolve(fib_path_ext_t *path_ext, fib_node_index_t path_list_index)
Definition: fib_path_ext.c:96
A representation of a path as described by a route producer.
Definition: fib_types.h:377
int fib_path_ext_cmp(fib_path_ext_t *path_ext, const fib_route_path_t *rpath)
Definition: fib_path_ext.c:73
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:188
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:311
#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:258
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
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:557
struct fib_path_ext_t_ * fpel_exts
Definition: fib_types.h:505
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:88
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
index_t mpls_label_dpo_create(mpls_label_t *label_stack, mpls_eos_bit_t eos, u8 ttl, u8 exp, dpo_proto_t payload_proto, const dpo_id_t *dpo)
Create an MPLS label object.
mpls_label_t * frp_label_stack
The outgoing MPLS label Stack.
Definition: fib_types.h:432
Contribute an object that is to be used to forward Ethernet packets.
Definition: fib_types.h:120
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
int load_balance_is_drop(const dpo_id_t *dpo)
Definition: load_balance.c:237
u16 fib_path_get_weight(fib_node_index_t path_index)
Definition: fib_path.c:2094
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:292
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:166
Contribute an object that is to be used to forward end-of-stack MPLS packets.
Definition: fib_types.h:108
void fib_path_ext_list_flush(fib_path_ext_list_t *list)
Definition: fib_path_ext.c:411
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:80
A list of path-extensions.
Definition: fib_types.h:503
u8 * format_fib_path_ext(u8 *s, va_list *args)
Definition: fib_path_ext.c:30
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:336
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:391
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:309
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:29
void dpo_set(dpo_id_t *dpo, dpo_type_t type, dpo_proto_t proto, index_t index)
Set/create a DPO ID The DPO will be locked.
Definition: dpo.c:182
unsigned int u32
Definition: types.h:88
#define vec_delete(V, N, M)
Delete N elements starting at element M.
Definition: vec.h:781
long ctx[MAX_CONNS]
Definition: main.c:122
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:109
#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:760
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:444
format_function_t format_mpls_unicast_label
Definition: mpls.h:69
fib_path_ext_adj_flags_t fpe_adj_flags
For an ADJ type extension.
Definition: fib_path_ext.h:88
#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:274
void fib_path_stack_mpls_disp(fib_node_index_t path_index, dpo_proto_t payload_proto, dpo_id_t *dpo)
Definition: fib_path.c:2205
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:30
void fib_path_ext_list_resolve(fib_path_ext_list_t *list, fib_node_index_t path_list_index)
Definition: fib_path_ext.c:379
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
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:100
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:193
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:62
static int fib_path_ext_is_imp_null(fib_path_ext_t *path_ext)
Return true if the label stack is implicit null.
Definition: fib_path_ext.c:126
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:228
#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:72
u8 * format_fib_path_ext_list(u8 *s, va_list *args)
Definition: fib_path_ext.c:424
Contribute an object that is to be used to forward non-end-of-stack MPLS packets. ...
Definition: fib_types.h:97
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:1605
fib_route_path_t fpe_path
A description of the path that is being extended.
Definition: fib_path_ext.h:79
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:335
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:133
enum mpls_eos_bit_t_ mpls_eos_bit_t