FD.io VPP  v18.07-34-g55fbdb9
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 [out] in_feature_nodes returned vector of
111  * topologically-sorted feature node names, for use in
112  * show commands
113  * @returns 0 on success, otherwise an error message. Errors
114  * are fatal since they invariably involve mistyped node-names, or
115  * genuinely missing node-names
116  */
117 clib_error_t *
119  vnet_config_main_t * vcm,
120  char **feature_start_nodes,
121  int num_feature_start_nodes,
122  vnet_feature_registration_t * first_reg,
123  char ***in_feature_nodes)
124 {
125  uword *index_by_name;
126  uword *reg_by_index;
127  u8 **node_names = 0;
128  u8 *node_name;
129  char **these_constraints;
130  char *this_constraint_c;
131  u8 **constraints = 0;
132  u8 *constraint_tuple;
133  u8 *this_constraint;
134  u8 **orig, **closure;
135  uword *p;
136  int i, j, k;
137  u8 *a_name, *b_name;
138  int a_index, b_index;
139  int n_features;
140  u32 *result = 0;
141  vnet_feature_registration_t *this_reg = 0;
142  char **feature_nodes = 0;
143  hash_pair_t *hp;
144  u8 **keys_to_delete = 0;
145 
146  index_by_name = hash_create_string (0, sizeof (uword));
147  reg_by_index = hash_create (0, sizeof (uword));
148 
149  this_reg = first_reg;
150 
151  /* pass 1, collect feature node names, construct a before b pairs */
152  while (this_reg)
153  {
154  node_name = format (0, "%s%c", this_reg->node_name, 0);
155  hash_set (reg_by_index, vec_len (node_names), (uword) this_reg);
156 
157  hash_set_mem (index_by_name, node_name, vec_len (node_names));
158 
159  vec_add1 (node_names, node_name);
160 
161  these_constraints = this_reg->runs_before;
162  while (these_constraints && these_constraints[0])
163  {
164  this_constraint_c = these_constraints[0];
165 
166  constraint_tuple = format (0, "%s,%s%c", node_name,
167  this_constraint_c, 0);
168  vec_add1 (constraints, constraint_tuple);
169  these_constraints++;
170  }
171 
172  these_constraints = this_reg->runs_after;
173  while (these_constraints && these_constraints[0])
174  {
175  this_constraint_c = these_constraints[0];
176 
177  constraint_tuple = format (0, "%s,%s%c",
178  this_constraint_c, node_name, 0);
179  vec_add1 (constraints, constraint_tuple);
180  these_constraints++;
181  }
182 
183  this_reg = this_reg->next_in_arc;
184  }
185 
186  n_features = vec_len (node_names);
187  orig = clib_ptclosure_alloc (n_features);
188 
189  for (i = 0; i < vec_len (constraints); i++)
190  {
191  this_constraint = constraints[i];
192 
193  if (comma_split (this_constraint, &a_name, &b_name))
194  return clib_error_return (0, "comma_split failed!");
195 
196  p = hash_get_mem (index_by_name, a_name);
197  /*
198  * Note: the next two errors mean that something is
199  * b0rked. As in: if you code "A depends on B," and you forget
200  * to define a FEATURE_INIT macro for B, you lose.
201  * Nonexistent graph nodes are tolerated.
202  */
203  if (p == 0)
204  {
205  clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
206  a_name, b_name, first_reg->arc_name);
207  continue;
208  }
209  a_index = p[0];
210 
211  p = hash_get_mem (index_by_name, b_name);
212  if (p == 0)
213  {
214  clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
215  b_name, a_name, first_reg->arc_name);
216  continue;
217  }
218  b_index = p[0];
219 
220  /* add a before b to the original set of constraints */
221  orig[a_index][b_index] = 1;
222  vec_free (this_constraint);
223  }
224 
225  /* Compute the positive transitive closure of the original constraints */
226  closure = clib_ptclosure (orig);
227 
228  /* Compute a partial order across feature nodes, if one exists. */
229 again:
230  for (i = 0; i < n_features; i++)
231  {
232  for (j = 0; j < n_features; j++)
233  {
234  if (closure[i][j])
235  goto item_constrained;
236  }
237  /* Item i can be output */
238  vec_add1 (result, i);
239  {
240  for (k = 0; k < n_features; k++)
241  closure[k][i] = 0;
242  /*
243  * Add a "Magic" a before a constraint.
244  * This means we'll never output it again
245  */
246  closure[i][i] = 1;
247  goto again;
248  }
249  item_constrained:
250  ;
251  }
252 
253  /* see if we got a partial order... */
254  if (vec_len (result) != n_features)
255  return clib_error_return (0, "%d feature_init_cast no partial order!");
256 
257  /*
258  * We win.
259  * Bind the index variables, and output the feature node name vector
260  * using the partial order we just computed. Result is in stack
261  * order, because the entry with the fewest constraints (e.g. none)
262  * is output first, etc.
263  */
264 
265  for (i = n_features - 1; i >= 0; i--)
266  {
267  p = hash_get (reg_by_index, result[i]);
268  ASSERT (p != 0);
269  this_reg = (vnet_feature_registration_t *) p[0];
270  if (this_reg->feature_index_ptr)
271  *this_reg->feature_index_ptr = n_features - (i + 1);
272  this_reg->feature_index = n_features - (i + 1);
273  vec_add1 (feature_nodes, this_reg->node_name);
274  }
275 
276  /* Set up the config infrastructure */
277  vnet_config_init (vm, vcm,
278  feature_start_nodes,
279  num_feature_start_nodes,
280  feature_nodes, vec_len (feature_nodes));
281 
282  /* Save a copy for show command */
283  *in_feature_nodes = feature_nodes;
284 
285  /* Finally, clean up all the shit we allocated */
286  /* *INDENT-OFF* */
287  hash_foreach_pair (hp, index_by_name,
288  ({
289  vec_add1 (keys_to_delete, (u8 *)hp->key);
290  }));
291  /* *INDENT-ON* */
292  hash_free (index_by_name);
293  for (i = 0; i < vec_len (keys_to_delete); i++)
294  vec_free (keys_to_delete[i]);
295  vec_free (keys_to_delete);
296  hash_free (reg_by_index);
297  vec_free (result);
298  clib_ptclosure_free (orig);
299  clib_ptclosure_free (closure);
300  return 0;
301 }
302 
303 /*
304  * fd.io coding-style-patch-verification: ON
305  *
306  * Local Variables:
307  * eval: (c-set-style "gnu")
308  * End:
309  */
#define hash_set(h, key, value)
Definition: hash.h:255
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:419
unsigned char u8
Definition: types.h:56
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, char ***in_feature_nodes)
Initialize a feature graph arc.
Definition: registration.c:118
#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:294
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:339
#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)
#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