FD.io VPP  v19.01.3-6-g70449b9b9
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  vnet_feature_registration_t * first_reg,
127  first_const_set, char ***in_feature_nodes)
128 {
129  uword *index_by_name;
130  uword *reg_by_index;
131  u8 **node_names = 0;
132  u8 *node_name;
133  char *prev_name;
134  char **these_constraints;
135  char *this_constraint_c;
136  u8 **constraints = 0;
137  u8 *constraint_tuple;
138  u8 *this_constraint;
139  u8 **orig, **closure;
140  uword *p;
141  int i, j, k;
142  u8 *a_name, *b_name;
143  int a_index, b_index;
144  int n_features;
145  u32 *result = 0;
146  vnet_feature_registration_t *this_reg = 0;
147  vnet_feature_constraint_registration_t *this_const_set = 0;
148  char **feature_nodes = 0;
149  hash_pair_t *hp;
150  u8 **keys_to_delete = 0;
151 
152  index_by_name = hash_create_string (0, sizeof (uword));
153  reg_by_index = hash_create (0, sizeof (uword));
154 
155  this_reg = first_reg;
156 
157  /* pass 1, collect feature node names, construct a before b pairs */
158  while (this_reg)
159  {
160  node_name = format (0, "%s%c", this_reg->node_name, 0);
161  hash_set (reg_by_index, vec_len (node_names), (uword) this_reg);
162 
163  hash_set_mem (index_by_name, node_name, vec_len (node_names));
164 
165  vec_add1 (node_names, node_name);
166 
167  these_constraints = this_reg->runs_before;
168  while (these_constraints && these_constraints[0])
169  {
170  this_constraint_c = these_constraints[0];
171 
172  constraint_tuple = format (0, "%s,%s%c", node_name,
173  this_constraint_c, 0);
174  vec_add1 (constraints, constraint_tuple);
175  these_constraints++;
176  }
177 
178  these_constraints = this_reg->runs_after;
179  while (these_constraints && these_constraints[0])
180  {
181  this_constraint_c = these_constraints[0];
182 
183  constraint_tuple = format (0, "%s,%s%c",
184  this_constraint_c, node_name, 0);
185  vec_add1 (constraints, constraint_tuple);
186  these_constraints++;
187  }
188 
189  this_reg = this_reg->next_in_arc;
190  }
191 
192  /* pass 2, collect bulk "a then b then c then d" constraints */
193  this_const_set = first_const_set;
194  while (this_const_set)
195  {
196  these_constraints = this_const_set->node_names;
197 
198  prev_name = 0;
199  /* Across the list of constraints */
200  while (these_constraints && these_constraints[0])
201  {
202  this_constraint_c = these_constraints[0];
203  p = hash_get_mem (index_by_name, this_constraint_c);
204  if (p == 0)
205  {
207  ("bulk constraint feature node '%s' not found for arc '%s'",
208  this_constraint_c);
209  these_constraints++;
210  continue;
211  }
212 
213  if (prev_name == 0)
214  {
215  prev_name = this_constraint_c;
216  these_constraints++;
217  continue;
218  }
219 
220  constraint_tuple = format (0, "%s,%s%c", prev_name,
221  this_constraint_c, 0);
222  vec_add1 (constraints, constraint_tuple);
223  prev_name = this_constraint_c;
224  these_constraints++;
225  }
226 
227  this_const_set = this_const_set->next_in_arc;
228  }
229 
230  n_features = vec_len (node_names);
231  orig = clib_ptclosure_alloc (n_features);
232 
233  for (i = 0; i < vec_len (constraints); i++)
234  {
235  this_constraint = constraints[i];
236 
237  if (comma_split (this_constraint, &a_name, &b_name))
238  return clib_error_return (0, "comma_split failed!");
239 
240  p = hash_get_mem (index_by_name, a_name);
241  /*
242  * Note: the next two errors mean that something is
243  * b0rked. As in: if you code "A depends on B," and you forget
244  * to define a FEATURE_INIT macro for B, you lose.
245  * Nonexistent graph nodes are tolerated.
246  */
247  if (p == 0)
248  {
249  clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
250  a_name, b_name, first_reg->arc_name);
251  continue;
252  }
253  a_index = p[0];
254 
255  p = hash_get_mem (index_by_name, b_name);
256  if (p == 0)
257  {
258  clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
259  b_name, a_name, first_reg->arc_name);
260  continue;
261  }
262  b_index = p[0];
263 
264  /* add a before b to the original set of constraints */
265  orig[a_index][b_index] = 1;
266  vec_free (this_constraint);
267  }
268 
269  /* Compute the positive transitive closure of the original constraints */
270  closure = clib_ptclosure (orig);
271 
272  /* Compute a partial order across feature nodes, if one exists. */
273 again:
274  for (i = 0; i < n_features; i++)
275  {
276  for (j = 0; j < n_features; j++)
277  {
278  if (closure[i][j])
279  goto item_constrained;
280  }
281  /* Item i can be output */
282  vec_add1 (result, i);
283  {
284  for (k = 0; k < n_features; k++)
285  closure[k][i] = 0;
286  /*
287  * Add a "Magic" a before a constraint.
288  * This means we'll never output it again
289  */
290  closure[i][i] = 1;
291  goto again;
292  }
293  item_constrained:
294  ;
295  }
296 
297  /* see if we got a partial order... */
298  if (vec_len (result) != n_features)
299  return clib_error_return
300  (0, "Arc '%s': failed to find a suitable feature order!",
301  first_reg->arc_name);
302 
303  /*
304  * We win.
305  * Bind the index variables, and output the feature node name vector
306  * using the partial order we just computed. Result is in stack
307  * order, because the entry with the fewest constraints (e.g. none)
308  * is output first, etc.
309  */
310 
311  for (i = n_features - 1; i >= 0; i--)
312  {
313  p = hash_get (reg_by_index, result[i]);
314  ASSERT (p != 0);
315  this_reg = (vnet_feature_registration_t *) p[0];
316  if (this_reg->feature_index_ptr)
317  *this_reg->feature_index_ptr = n_features - (i + 1);
318  this_reg->feature_index = n_features - (i + 1);
319  vec_add1 (feature_nodes, this_reg->node_name);
320  }
321 
322  /* Set up the config infrastructure */
323  vnet_config_init (vm, vcm,
324  feature_start_nodes,
325  num_feature_start_nodes,
326  feature_nodes, vec_len (feature_nodes));
327 
328  /* Save a copy for show command */
329  *in_feature_nodes = feature_nodes;
330 
331  /* Finally, clean up all the shit we allocated */
332  /* *INDENT-OFF* */
333  hash_foreach_pair (hp, index_by_name,
334  ({
335  vec_add1 (keys_to_delete, (u8 *)hp->key);
336  }));
337  /* *INDENT-ON* */
338  hash_free (index_by_name);
339  for (i = 0; i < vec_len (keys_to_delete); i++)
340  vec_free (keys_to_delete[i]);
341  vec_free (keys_to_delete);
342  hash_free (reg_by_index);
343  vec_free (result);
344  clib_ptclosure_free (orig);
345  clib_ptclosure_free (closure);
346  return 0;
347 }
348 
349 /*
350  * fd.io coding-style-patch-verification: ON
351  *
352  * Local Variables:
353  * eval: (c-set-style "gnu")
354  * End:
355  */
#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:525
int i
#define hash_set_mem(h, key, value)
Definition: hash.h:275
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
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
void clib_ptclosure_free(u8 **ptc)
Definition: ptclosure.c:39
vlib_main_t * vm
Definition: buffer.c:301
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
#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
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, 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 vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#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
uword key
Definition: hash.h:162
struct _vnet_feature_registration vnet_feature_registration_t
feature registration object