FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
registration.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/vnet.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/mpls/mpls.h>
19 
20 /**
21  * @file
22  * @brief Feature Subgraph Ordering.
23 
24  Dynamically compute feature subgraph ordering by performing a
25  topological sort across a set of "feature A before feature B" and
26  "feature C after feature B" constraints.
27 
28  Use the topological sort result to set up vnet_config_main_t's for
29  use at runtime.
30 
31  Feature subgraph arcs are simple enough. They start at specific
32  fixed nodes, and end at specific fixed nodes. In between, a
33  per-interface current feature configuration dictates which
34  additional nodes each packet visits. Each so-called feature node
35  can [of course] drop any specific packet.
36 
37  See ip4_forward.c, ip6_forward.c in this directory to see the
38  current rx-unicast, rx-multicast, and tx feature subgraph arc
39  definitions.
40 
41  Let's say that we wish to add a new feature to the ip4 unicast
42  feature subgraph arc, which needs to run before @c ip4-lookup. In
43  either base code or a plugin,
44  <CODE><PRE>
45  \#include <vnet/feature/feature.h>
46  </PRE></CODE>
47 
48  and add the new feature as shown:
49 
50  <CODE><PRE>
51  VNET_FEATURE_INIT (ip4_lookup, static) =
52  {
53  .arch_name = "ip4-unicast",
54  .node_name = "my-ip4-unicast-feature",
55  .runs_before = VLIB_FEATURES ("ip4-lookup")
56  };
57  </PRE></CODE>
58 
59  Here's the standard coding pattern to enable / disable
60  @c my-ip4-unicast-feature on an interface:
61 
62  <CODE><PRE>
63 
64  sw_if_index = <interface-handle>
65  vnet_feature_enable_disable ("ip4-unicast", "my-ip4-unicast-feature",
66  sw_if_index, 1 );
67  </PRE></CODE>
68 
69  Here's how to obtain the correct next node index in packet
70  processing code, aka in the implementation of @c my-ip4-unicast-feature:
71 
72  <CODE><PRE>
73  vnet_feature_next (sw_if_index0, &next0, b0);
74 
75  </PRE></CODE>
76 
77  Nodes are free to drop or otherwise redirect packets. Packets
78  which "pass" should be enqueued via the next0 arc computed by
79  vnet_feature_next.
80 */
81 
82 
83 static int
84 comma_split (u8 * s, u8 ** a, u8 ** b)
85 {
86  *a = s;
87 
88  while (*s && *s != ',')
89  s++;
90 
91  if (*s == ',')
92  *s = 0;
93  else
94  return 1;
95 
96  *b = (u8 *) (s + 1);
97  return 0;
98 }
99 
100 /**
101  * @brief Initialize a feature graph arc
102  * @param vm vlib main structure pointer
103  * @param vcm vnet config main structure pointer
104  * @param feature_start_nodes names of start-nodes which use this
105  * feature graph arc
106  * @param num_feature_start_nodes number of start-nodes
107  * @param first_reg first element in
108  * [an __attribute__((constructor)) function built, or
109  * otherwise created] singly-linked list of feature registrations
110  * @param first_const first element in
111  * [an __attribute__((constructor)) function built, or
112  * otherwise created] singly-linked list of bulk order constraints
113  * @param [out] in_feature_nodes returned vector of
114  * topologically-sorted feature node names, for use in
115  * show commands
116  * @returns 0 on success, otherwise an error message. Errors
117  * are fatal since they invariably involve mistyped node-names, or
118  * genuinely missing node-names
119  */
120 clib_error_t *
122  vnet_config_main_t * vcm,
123  char **feature_start_nodes,
124  int num_feature_start_nodes,
125  char *last_in_arc,
126  vnet_feature_registration_t * first_reg,
128  first_const_set, char ***in_feature_nodes)
129 {
130  uword *index_by_name;
131  uword *reg_by_index;
132  u8 **node_names = 0;
133  u8 *node_name;
134  char *prev_name;
135  char **these_constraints;
136  char *this_constraint_c;
137  u8 **constraints = 0;
138  u8 *constraint_tuple;
139  u8 *this_constraint;
140  u8 **orig, **closure;
141  uword *p;
142  int i, j, k;
143  u8 *a_name, *b_name;
144  int a_index, b_index;
145  int n_features;
146  u32 *result = 0;
147  vnet_feature_registration_t *this_reg = 0;
148  vnet_feature_constraint_registration_t *this_const_set = 0;
149  char **feature_nodes = 0;
150  hash_pair_t *hp;
151  u8 **keys_to_delete = 0;
152 
153  index_by_name = hash_create_string (0, sizeof (uword));
154  reg_by_index = hash_create (0, sizeof (uword));
155 
156  this_reg = first_reg;
157 
158  /* Autogenerate <node> before <last-in-arc> constraints */
159  if (last_in_arc)
160  {
161  while (this_reg)
162  {
163  /* If this isn't the last node in the arc... */
164  if (clib_strcmp (this_reg->node_name, last_in_arc))
165  {
166  /*
167  * Add an explicit constraint so this feature will run
168  * before the last node in the arc
169  */
170  constraint_tuple = format (0, "%s,%s%c", this_reg->node_name,
171  last_in_arc, 0);
172  vec_add1 (constraints, constraint_tuple);
173  }
174  this_reg = this_reg->next_in_arc;
175  }
176  this_reg = first_reg;
177  }
178 
179  /* pass 1, collect feature node names, construct a before b pairs */
180  while (this_reg)
181  {
182  node_name = format (0, "%s%c", this_reg->node_name, 0);
183  hash_set (reg_by_index, vec_len (node_names), (uword) this_reg);
184 
185  hash_set_mem (index_by_name, node_name, vec_len (node_names));
186 
187  vec_add1 (node_names, node_name);
188 
189  these_constraints = this_reg->runs_before;
190  while (these_constraints && these_constraints[0])
191  {
192  this_constraint_c = these_constraints[0];
193 
194  constraint_tuple = format (0, "%s,%s%c", node_name,
195  this_constraint_c, 0);
196  vec_add1 (constraints, constraint_tuple);
197  these_constraints++;
198  }
199 
200  these_constraints = this_reg->runs_after;
201  while (these_constraints && these_constraints[0])
202  {
203  this_constraint_c = these_constraints[0];
204 
205  constraint_tuple = format (0, "%s,%s%c",
206  this_constraint_c, node_name, 0);
207  vec_add1 (constraints, constraint_tuple);
208  these_constraints++;
209  }
210 
211  this_reg = this_reg->next_in_arc;
212  }
213 
214  /* pass 2, collect bulk "a then b then c then d" constraints */
215  this_const_set = first_const_set;
216  while (this_const_set)
217  {
218  these_constraints = this_const_set->node_names;
219 
220  prev_name = 0;
221  /* Across the list of constraints */
222  while (these_constraints && these_constraints[0])
223  {
224  this_constraint_c = these_constraints[0];
225  p = hash_get_mem (index_by_name, this_constraint_c);
226  if (p == 0)
227  {
229  ("bulk constraint feature node '%s' not found for arc '%s'",
230  this_constraint_c);
231  these_constraints++;
232  continue;
233  }
234 
235  if (prev_name == 0)
236  {
237  prev_name = this_constraint_c;
238  these_constraints++;
239  continue;
240  }
241 
242  constraint_tuple = format (0, "%s,%s%c", prev_name,
243  this_constraint_c, 0);
244  vec_add1 (constraints, constraint_tuple);
245  prev_name = this_constraint_c;
246  these_constraints++;
247  }
248 
249  this_const_set = this_const_set->next_in_arc;
250  }
251 
252  n_features = vec_len (node_names);
253  orig = clib_ptclosure_alloc (n_features);
254 
255  for (i = 0; i < vec_len (constraints); i++)
256  {
257  this_constraint = constraints[i];
258 
259  if (comma_split (this_constraint, &a_name, &b_name))
260  return clib_error_return (0, "comma_split failed!");
261 
262  p = hash_get_mem (index_by_name, a_name);
263  /*
264  * Note: the next two errors mean that something is
265  * b0rked. As in: if you code "A depends on B," and you forget
266  * to define a FEATURE_INIT macro for B, you lose.
267  * Nonexistent graph nodes are tolerated.
268  */
269  if (p == 0)
270  {
271  clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
272  a_name, b_name, first_reg->arc_name);
273  continue;
274  }
275  a_index = p[0];
276 
277  p = hash_get_mem (index_by_name, b_name);
278  if (p == 0)
279  {
280  clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
281  b_name, a_name, first_reg->arc_name);
282  continue;
283  }
284  b_index = p[0];
285 
286  /* add a before b to the original set of constraints */
287  orig[a_index][b_index] = 1;
288  vec_free (this_constraint);
289  }
290 
291  /* Compute the positive transitive closure of the original constraints */
292  closure = clib_ptclosure (orig);
293 
294  /* Compute a partial order across feature nodes, if one exists. */
295 again:
296  for (i = 0; i < n_features; i++)
297  {
298  for (j = 0; j < n_features; j++)
299  {
300  if (closure[i][j])
301  goto item_constrained;
302  }
303  /* Item i can be output */
304  vec_add1 (result, i);
305  {
306  for (k = 0; k < n_features; k++)
307  closure[k][i] = 0;
308  /*
309  * Add a "Magic" a before a constraint.
310  * This means we'll never output it again
311  */
312  closure[i][i] = 1;
313  goto again;
314  }
315  item_constrained:
316  ;
317  }
318 
319  /* see if we got a partial order... */
320  if (vec_len (result) != n_features)
321  return clib_error_return
322  (0, "Arc '%s': failed to find a suitable feature order!",
323  first_reg->arc_name);
324 
325  /*
326  * We win.
327  * Bind the index variables, and output the feature node name vector
328  * using the partial order we just computed. Result is in stack
329  * order, because the entry with the fewest constraints (e.g. none)
330  * is output first, etc.
331  */
332 
333  for (i = n_features - 1; i >= 0; i--)
334  {
335  p = hash_get (reg_by_index, result[i]);
336  ASSERT (p != 0);
337  this_reg = (vnet_feature_registration_t *) p[0];
338  if (this_reg->feature_index_ptr)
339  *this_reg->feature_index_ptr = n_features - (i + 1);
340  this_reg->feature_index = n_features - (i + 1);
341  vec_add1 (feature_nodes, this_reg->node_name);
342  }
343 
344  /* Set up the config infrastructure */
345  vnet_config_init (vm, vcm,
346  feature_start_nodes,
347  num_feature_start_nodes,
348  feature_nodes, vec_len (feature_nodes));
349 
350  /* Save a copy for show command */
351  *in_feature_nodes = feature_nodes;
352 
353  /* Finally, clean up all the shit we allocated */
354  /* *INDENT-OFF* */
355  hash_foreach_pair (hp, index_by_name,
356  ({
357  vec_add1 (keys_to_delete, (u8 *)hp->key);
358  }));
359  /* *INDENT-ON* */
360  hash_free (index_by_name);
361  for (i = 0; i < vec_len (keys_to_delete); i++)
362  vec_free (keys_to_delete[i]);
363  vec_free (keys_to_delete);
364  hash_free (reg_by_index);
365  vec_free (result);
366  clib_ptclosure_free (orig);
367  clib_ptclosure_free (closure);
368  return 0;
369 }
370 
371 /*
372  * fd.io coding-style-patch-verification: ON
373  *
374  * Local Variables:
375  * eval: (c-set-style "gnu")
376  * End:
377  */
#define hash_set(h, key, value)
Definition: hash.h:255
struct _vnet_feature_constraint_registration vnet_feature_constraint_registration_t
constraint registration object
void vnet_config_init(vlib_main_t *vm, vnet_config_main_t *cm, char *start_node_names[], int n_start_node_names, char *feature_node_names[], int n_feature_node_names)
Definition: config.c:161
a
Definition: bitmap.h:538
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:523
int i
#define hash_set_mem(h, key, value)
Definition: hash.h:275
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
unsigned char u8
Definition: types.h:56
#define clib_error_return(e, args...)
Definition: error.h:99
unsigned int u32
Definition: types.h:88
#define hash_create_string(elts, value_bytes)
Definition: hash.h:690
#define hash_get(h, key)
Definition: hash.h:249
#define hash_free(h)
Definition: hash.h:310
u8 ** clib_ptclosure_alloc(int n)
Definition: ptclosure.c:19
vlib_main_t * vm
Definition: in2out_ed.c:1810
void clib_ptclosure_free(u8 **ptc)
Definition: ptclosure.c:39
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:342
#define clib_warning(format, args...)
Definition: error.h:59
#define hash_create(elts, value_bytes)
Definition: hash.h:696
#define ASSERT(truth)
static int comma_split(u8 *s, u8 **a, u8 **b)
Definition: registration.c:84
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
clib_error_t * vnet_feature_arc_init(vlib_main_t *vm, vnet_config_main_t *vcm, char **feature_start_nodes, int num_feature_start_nodes, char *last_in_arc, vnet_feature_registration_t *first_reg, vnet_feature_constraint_registration_t *first_const_set, char ***in_feature_nodes)
Initialize a feature graph arc.
Definition: registration.c:121
#define hash_foreach_pair(p, v, body)
Iterate over hash pairs.
Definition: hash.h:373
u64 uword
Definition: types.h:112
u8 ** clib_ptclosure(u8 **orig)
Definition: ptclosure.c:90
#define hash_get_mem(h, key)
Definition: hash.h:269
#define clib_strcmp(s1, s2)
Definition: string.h:826
uword key
Definition: hash.h:162
struct _vnet_feature_registration vnet_feature_registration_t
feature registration object