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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vnet/vnet.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/mpls/mpls.h>
22 * @brief Feature Subgraph Ordering.
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.
28 Use the topological sort result to set up vnet_config_main_t's for
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.
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
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,
45 \#include <vnet/feature/feature.h>
48 and add the new feature as shown:
51 VNET_FEATURE_INIT (ip4_lookup, static) =
53 .arch_name = "ip4-unicast",
54 .node_name = "my-ip4-unicast-feature",
55 .runs_before = VLIB_FEATURES ("ip4-lookup")
59 Here's the standard coding pattern to enable / disable
60 @c my-ip4-unicast-feature on an interface:
64 sw_if_index = <interface-handle>
65 vnet_feature_enable_disable ("ip4-unicast", "my-ip4-unicast-feature",
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:
73 vnet_feature_next (sw_if_index0, &next0, b0);
77 Nodes are free to drop or otherwise redirect packets. Packets
78 which "pass" should be enqueued via the next0 arc computed by
84 comma_split (u8 * s, u8 ** a, u8 ** b)
88 while (*s && *s != ',')
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
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
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
121 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,
126 vnet_feature_registration_t * first_reg,
127 vnet_feature_constraint_registration_t *
128 first_const_set, char ***in_feature_nodes)
130 uword *index_by_name;
135 char **these_constraints;
136 char *this_constraint_c;
137 u8 **constraints = 0;
138 u8 *constraint_tuple;
140 u8 **orig, **closure;
144 int a_index, b_index;
147 vnet_feature_registration_t *this_reg = 0;
148 vnet_feature_constraint_registration_t *this_const_set = 0;
149 char **feature_nodes = 0;
151 u8 **keys_to_delete = 0;
153 index_by_name = hash_create_string (0, sizeof (uword));
154 reg_by_index = hash_create (0, sizeof (uword));
156 this_reg = first_reg;
158 /* Autogenerate <node> before <last-in-arc> constraints */
163 /* If this isn't the last node in the arc... */
164 if (clib_strcmp (this_reg->node_name, last_in_arc))
167 * Add an explicit constraint so this feature will run
168 * before the last node in the arc
170 constraint_tuple = format (0, "%s,%s%c", this_reg->node_name,
172 vec_add1 (constraints, constraint_tuple);
174 this_reg = this_reg->next_in_arc;
176 this_reg = first_reg;
179 /* pass 1, collect feature node names, construct a before b pairs */
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);
185 hash_set_mem (index_by_name, node_name, vec_len (node_names));
187 vec_add1 (node_names, node_name);
189 these_constraints = this_reg->runs_before;
190 while (these_constraints && these_constraints[0])
192 this_constraint_c = these_constraints[0];
194 constraint_tuple = format (0, "%s,%s%c", node_name,
195 this_constraint_c, 0);
196 vec_add1 (constraints, constraint_tuple);
200 these_constraints = this_reg->runs_after;
201 while (these_constraints && these_constraints[0])
203 this_constraint_c = these_constraints[0];
205 constraint_tuple = format (0, "%s,%s%c",
206 this_constraint_c, node_name, 0);
207 vec_add1 (constraints, constraint_tuple);
211 this_reg = this_reg->next_in_arc;
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)
218 these_constraints = this_const_set->node_names;
221 /* Across the list of constraints */
222 while (these_constraints && these_constraints[0])
224 this_constraint_c = these_constraints[0];
225 p = hash_get_mem (index_by_name, this_constraint_c);
229 ("bulk constraint feature node '%s' not found for arc '%s'",
237 prev_name = this_constraint_c;
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;
249 this_const_set = this_const_set->next_in_arc;
252 n_features = vec_len (node_names);
253 orig = clib_ptclosure_alloc (n_features);
255 for (i = 0; i < vec_len (constraints); i++)
257 this_constraint = constraints[i];
259 if (comma_split (this_constraint, &a_name, &b_name))
260 return clib_error_return (0, "comma_split failed!");
262 p = hash_get_mem (index_by_name, a_name);
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.
271 clib_warning ("feature node '%s' not found (before '%s', arc '%s')",
272 a_name, b_name, first_reg->arc_name);
277 p = hash_get_mem (index_by_name, b_name);
280 clib_warning ("feature node '%s' not found (after '%s', arc '%s')",
281 b_name, a_name, first_reg->arc_name);
286 /* add a before b to the original set of constraints */
287 orig[a_index][b_index] = 1;
288 vec_free (this_constraint);
291 /* Compute the positive transitive closure of the original constraints */
292 closure = clib_ptclosure (orig);
294 /* Compute a partial order across feature nodes, if one exists. */
296 for (i = 0; i < n_features; i++)
298 for (j = 0; j < n_features; j++)
301 goto item_constrained;
303 /* Item i can be output */
304 vec_add1 (result, i);
306 for (k = 0; k < n_features; k++)
309 * Add a "Magic" a before a constraint.
310 * This means we'll never output it again
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);
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.
333 for (i = n_features - 1; i >= 0; i--)
335 p = hash_get (reg_by_index, result[i]);
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);
344 /* Set up the config infrastructure */
345 vnet_config_init (vm, vcm,
347 num_feature_start_nodes,
348 feature_nodes, vec_len (feature_nodes));
350 /* Save a copy for show command */
351 *in_feature_nodes = feature_nodes;
353 /* Finally, clean up all the shit we allocated */
355 hash_foreach_pair (hp, index_by_name,
357 vec_add1 (keys_to_delete, (u8 *)hp->key);
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);
366 clib_ptclosure_free (orig);
367 clib_ptclosure_free (closure);
372 * fd.io coding-style-patch-verification: ON
375 * eval: (c-set-style "gnu")