Line data Source code
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 : .arc_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 239807 : comma_split (u8 * s, u8 ** a, u8 ** b)
85 : {
86 239807 : *a = s;
87 :
88 4436100 : while (*s && *s != ',')
89 4196290 : s++;
90 :
91 239807 : if (*s == ',')
92 239807 : *s = 0;
93 : else
94 0 : return 1;
95 :
96 239807 : *b = (u8 *) (s + 1);
97 239807 : 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 *
121 14950 : vnet_feature_arc_init (vlib_main_t * vm,
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,
127 : vnet_feature_constraint_registration_t *
128 : first_const_set, char ***in_feature_nodes)
129 : {
130 : uword *index_by_name;
131 : uword *reg_by_index;
132 14950 : u8 **node_names = 0;
133 : u8 *node_name;
134 : char *prev_name;
135 : char **these_constraints;
136 : char *this_constraint_c;
137 14950 : 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 14950 : u32 *result = 0;
147 14950 : vnet_feature_registration_t *this_reg = 0;
148 14950 : vnet_feature_constraint_registration_t *this_const_set = 0;
149 14950 : char **feature_nodes = 0;
150 : hash_pair_t *hp;
151 14950 : u8 **keys_to_delete = 0;
152 :
153 14950 : index_by_name = hash_create_string (0, sizeof (uword));
154 14950 : reg_by_index = hash_create (0, sizeof (uword));
155 :
156 14950 : this_reg = first_reg;
157 :
158 : /* Autogenerate <node> before <last-in-arc> constraints */
159 14950 : if (last_in_arc)
160 : {
161 129399 : while (this_reg)
162 : {
163 : /* If this isn't the last node in the arc... */
164 121924 : 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 114449 : constraint_tuple = format (0, "%s,%s%c", this_reg->node_name,
171 : last_in_arc, 0);
172 114449 : vec_add1 (constraints, constraint_tuple);
173 : }
174 121924 : this_reg = this_reg->next_in_arc;
175 : }
176 7475 : this_reg = first_reg;
177 : }
178 :
179 : /* pass 1, collect feature node names, construct a before b pairs */
180 155278 : while (this_reg)
181 : {
182 140328 : node_name = format (0, "%s%c", this_reg->node_name, 0);
183 140328 : hash_set (reg_by_index, vec_len (node_names), (uword) this_reg);
184 :
185 280656 : hash_set_mem (index_by_name, node_name, vec_len (node_names));
186 :
187 140328 : vec_add1 (node_names, node_name);
188 :
189 140328 : these_constraints = this_reg->runs_before;
190 220261 : while (these_constraints && these_constraints[0])
191 : {
192 79933 : this_constraint_c = these_constraints[0];
193 :
194 79933 : constraint_tuple = format (0, "%s,%s%c", node_name,
195 : this_constraint_c, 0);
196 79933 : vec_add1 (constraints, constraint_tuple);
197 79933 : these_constraints++;
198 : }
199 :
200 140328 : these_constraints = this_reg->runs_after;
201 185753 : while (these_constraints && these_constraints[0])
202 : {
203 45425 : this_constraint_c = these_constraints[0];
204 :
205 45425 : constraint_tuple = format (0, "%s,%s%c",
206 : this_constraint_c, node_name, 0);
207 45425 : vec_add1 (constraints, constraint_tuple);
208 45425 : these_constraints++;
209 : }
210 :
211 140328 : this_reg = this_reg->next_in_arc;
212 : }
213 :
214 : /* pass 2, collect bulk "a then b then c then d" constraints */
215 14950 : this_const_set = first_const_set;
216 14950 : while (this_const_set)
217 : {
218 0 : these_constraints = this_const_set->node_names;
219 :
220 0 : prev_name = 0;
221 : /* Across the list of constraints */
222 0 : while (these_constraints && these_constraints[0])
223 : {
224 0 : this_constraint_c = these_constraints[0];
225 0 : p = hash_get_mem (index_by_name, this_constraint_c);
226 0 : if (p == 0)
227 : {
228 0 : clib_warning
229 : ("bulk constraint feature node '%s' not found for arc '%s'",
230 : this_constraint_c);
231 0 : these_constraints++;
232 0 : continue;
233 : }
234 :
235 0 : if (prev_name == 0)
236 : {
237 0 : prev_name = this_constraint_c;
238 0 : these_constraints++;
239 0 : continue;
240 : }
241 :
242 0 : constraint_tuple = format (0, "%s,%s%c", prev_name,
243 : this_constraint_c, 0);
244 0 : vec_add1 (constraints, constraint_tuple);
245 0 : prev_name = this_constraint_c;
246 0 : these_constraints++;
247 : }
248 :
249 0 : this_const_set = this_const_set->next_in_arc;
250 : }
251 :
252 14950 : n_features = vec_len (node_names);
253 14950 : orig = clib_ptclosure_alloc (n_features);
254 :
255 254757 : for (i = 0; i < vec_len (constraints); i++)
256 : {
257 239807 : this_constraint = constraints[i];
258 :
259 239807 : if (comma_split (this_constraint, &a_name, &b_name))
260 0 : return clib_error_return (0, "comma_split failed!");
261 :
262 479614 : 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 239807 : if (p == 0)
270 : {
271 0 : clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
272 : a_name, b_name, first_reg->arc_name);
273 0 : continue;
274 : }
275 239807 : a_index = p[0];
276 :
277 479614 : p = hash_get_mem (index_by_name, b_name);
278 239807 : if (p == 0)
279 : {
280 0 : clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
281 : b_name, a_name, first_reg->arc_name);
282 0 : continue;
283 : }
284 239807 : b_index = p[0];
285 :
286 : /* add a before b to the original set of constraints */
287 239807 : orig[a_index][b_index] = 1;
288 239807 : vec_free (this_constraint);
289 : }
290 :
291 : /* Compute the positive transitive closure of the original constraints */
292 14950 : closure = clib_ptclosure (orig);
293 :
294 : /* Compute a partial order across feature nodes, if one exists. */
295 155278 : again:
296 2436390 : for (i = 0; i < n_features; i++)
297 : {
298 44546400 : for (j = 0; j < n_features; j++)
299 : {
300 44406100 : if (closure[i][j])
301 2281110 : goto item_constrained;
302 : }
303 : /* Item i can be output */
304 140328 : vec_add1 (result, i);
305 : {
306 4562220 : for (k = 0; k < n_features; k++)
307 4421890 : closure[k][i] = 0;
308 : /*
309 : * Add a "Magic" a before a constraint.
310 : * This means we'll never output it again
311 : */
312 140328 : closure[i][i] = 1;
313 140328 : goto again;
314 : }
315 2281110 : item_constrained:
316 : ;
317 : }
318 :
319 : /* see if we got a partial order... */
320 14950 : if (vec_len (result) != n_features)
321 0 : 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 155278 : for (i = n_features - 1; i >= 0; i--)
334 : {
335 140328 : p = hash_get (reg_by_index, result[i]);
336 140328 : ASSERT (p != 0);
337 140328 : this_reg = (vnet_feature_registration_t *) p[0];
338 140328 : if (this_reg->feature_index_ptr)
339 0 : *this_reg->feature_index_ptr = n_features - (i + 1);
340 140328 : this_reg->feature_index = n_features - (i + 1);
341 140328 : vec_add1 (feature_nodes, this_reg->node_name);
342 : }
343 :
344 : /* Set up the config infrastructure */
345 14950 : vnet_config_init (vm, vcm,
346 : feature_start_nodes,
347 : num_feature_start_nodes,
348 14950 : feature_nodes, vec_len (feature_nodes));
349 :
350 : /* Save a copy for show command */
351 14950 : *in_feature_nodes = feature_nodes;
352 :
353 : /* Finally, clean up all the shit we allocated */
354 : /* *INDENT-OFF* */
355 1185100 : hash_foreach_pair (hp, index_by_name,
356 : ({
357 : vec_add1 (keys_to_delete, (u8 *)hp->key);
358 : }));
359 : /* *INDENT-ON* */
360 14950 : hash_free (index_by_name);
361 154703 : for (i = 0; i < vec_len (keys_to_delete); i++)
362 139753 : vec_free (keys_to_delete[i]);
363 14950 : vec_free (keys_to_delete);
364 14950 : hash_free (reg_by_index);
365 14950 : vec_free (result);
366 14950 : clib_ptclosure_free (orig);
367 14950 : clib_ptclosure_free (closure);
368 14950 : 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 : */
|
