init / exit function ordering
The vlib init function subsystem now supports a mix of procedural and
formally-specified ordering constraints. We should eliminate procedural
knowledge wherever possible.
The following schemes are *roughly* equivalent:
static clib_error_t *init_runs_first (vlib_main_t *vm)
{
clib_error_t *error;
... do some stuff...
if ((error = vlib_call_init_function (init_runs_next)))
return error;
...
}
VLIB_INIT_FUNCTION (init_runs_first);
and
static clib_error_t *init_runs_first (vlib_main_t *vm)
{
... do some stuff...
}
VLIB_INIT_FUNCTION (init_runs_first) =
{
.runs_before = VLIB_INITS("init_runs_next"),
};
The first form will [most likely] call "init_runs_next" on the
spot. The second form means that "init_runs_first" runs before
"init_runs_next," possibly much earlier in the sequence.
Please DO NOT construct sets of init functions where A before B
actually means A *right before* B. It's not necessary - simply combine
A and B - and it leads to hugely annoying debugging exercises when
trying to switch from ad-hoc procedural ordering constraints to formal
ordering constraints.
Change-Id: I5e4353503bf43b4acb11a45fb33c79a5ade8426c
Signed-off-by: Dave Barach <dave@barachs.net>
diff --git a/src/vlib/init.c b/src/vlib/init.c
index 8d47845..8010e9e 100644
--- a/src/vlib/init.c
+++ b/src/vlib/init.c
@@ -38,16 +38,309 @@
*/
#include <vlib/vlib.h>
+#include <vppinfra/ptclosure.h>
+
+/**
+ * @file
+ * @brief Init function ordering and execution implementation
+ * Topological sort for all classes of init functions, and
+ * a relatively simple API routine to invoke them.
+ */
+
+/*? %%clicmd:group_label Init functions %% ?*/
+
+static int
+comma_split (u8 * s, u8 ** a, u8 ** b)
+{
+ *a = s;
+
+ while (*s && *s != ',')
+ s++;
+
+ if (*s == ',')
+ *s = 0;
+ else
+ return 1;
+
+ *b = (u8 *) (s + 1);
+ return 0;
+}
+
+/**
+ * @brief Topological sorter for init function chains.
+ * @param head [in/out] address of the listhead to be sorted
+ * @returns 0 on success, otherwise a clib_error_t *.
+ */
+
+static clib_error_t *init_exit_function_sort
+ (_vlib_init_function_list_elt_t ** head)
+{
+ uword *index_by_name;
+ uword *reg_by_index;
+ u8 **init_f_names = 0;
+ u8 *init_f_name;
+ char **these_constraints;
+ char *this_constraint_c;
+ u8 **constraints = 0;
+ u8 *constraint_tuple;
+ u8 *this_constraint;
+ char *prev_name;
+ u8 **orig, **closure;
+ uword *p;
+ int i, j, k;
+ u8 *a_name, *b_name;
+ int a_index, b_index;
+ int n_init_fns;
+ u32 *result = 0;
+ _vlib_init_function_list_elt_t *this_reg = 0;
+ hash_pair_t *hp;
+ u8 **keys_to_delete = 0;
+
+ /*
+ * two hash tables: name to index in init_f_names, and
+ * init function registration pointer by index
+ */
+ index_by_name = hash_create_string (0, sizeof (uword));
+ reg_by_index = hash_create (0, sizeof (uword));
+
+ this_reg = *head;
+
+ /* pass 1, collect init fcn names, construct a before b pairs */
+ while (this_reg)
+ {
+ init_f_name = format (0, "%s%c", this_reg->name, 0);
+ hash_set (reg_by_index, vec_len (init_f_names), (uword) this_reg);
+
+ hash_set_mem (index_by_name, init_f_name, vec_len (init_f_names));
+
+ vec_add1 (init_f_names, init_f_name);
+
+ these_constraints = this_reg->runs_before;
+ while (these_constraints && these_constraints[0])
+ {
+ this_constraint_c = these_constraints[0];
+
+ constraint_tuple = format (0, "%s,%s%c", init_f_name,
+ this_constraint_c, 0);
+ vec_add1 (constraints, constraint_tuple);
+ these_constraints++;
+ }
+
+ these_constraints = this_reg->runs_after;
+ while (these_constraints && these_constraints[0])
+ {
+ this_constraint_c = these_constraints[0];
+
+ constraint_tuple = format (0, "%s,%s%c",
+ this_constraint_c, init_f_name, 0);
+ vec_add1 (constraints, constraint_tuple);
+ these_constraints++;
+ }
+
+ this_reg = this_reg->next_init_function;
+ }
+
+ /*
+ * pass 2: collect "a then b then c then d" constraints.
+ * all init fcns must be known at this point.
+ */
+ this_reg = *head;
+ while (this_reg)
+ {
+ these_constraints = this_reg->init_order;
+
+ prev_name = 0;
+ /* Across the list of constraints */
+ while (these_constraints && these_constraints[0])
+ {
+ this_constraint_c = these_constraints[0];
+ p = hash_get_mem (index_by_name, this_constraint_c);
+ if (p == 0)
+ {
+ clib_warning
+ ("order constraint fcn '%s' not found", this_constraint_c);
+ these_constraints++;
+ continue;
+ }
+
+ if (prev_name == 0)
+ {
+ prev_name = this_constraint_c;
+ these_constraints++;
+ continue;
+ }
+
+ constraint_tuple = format (0, "%s,%s%c", prev_name,
+ this_constraint_c, 0);
+ vec_add1 (constraints, constraint_tuple);
+ prev_name = this_constraint_c;
+ these_constraints++;
+ }
+ this_reg = this_reg->next_init_function;
+ }
+
+ n_init_fns = vec_len (init_f_names);
+ orig = clib_ptclosure_alloc (n_init_fns);
+
+ for (i = 0; i < vec_len (constraints); i++)
+ {
+ this_constraint = constraints[i];
+
+ if (comma_split (this_constraint, &a_name, &b_name))
+ return clib_error_return (0, "comma_split failed!");
+
+ p = hash_get_mem (index_by_name, a_name);
+ /*
+ * Note: the next two errors mean that something is
+ * b0rked. As in: if you code "A runs before on B," and you type
+ * B incorrectly, you lose. Nonexistent init functions are tolerated.
+ */
+ if (p == 0)
+ {
+ clib_warning ("init function '%s' not found (before '%s')",
+ a_name, b_name);
+ continue;
+ }
+ a_index = p[0];
+
+ p = hash_get_mem (index_by_name, b_name);
+ if (p == 0)
+ {
+ clib_warning ("init function '%s' not found (after '%s')",
+ b_name, a_name);
+ continue;
+ }
+ b_index = p[0];
+
+ /* add a before b to the original set of constraints */
+ orig[a_index][b_index] = 1;
+ vec_free (this_constraint);
+ }
+
+ /* Compute the positive transitive closure of the original constraints */
+ closure = clib_ptclosure (orig);
+
+ /* Compute a partial order across feature nodes, if one exists. */
+again:
+ for (i = 0; i < n_init_fns; i++)
+ {
+ for (j = 0; j < n_init_fns; j++)
+ {
+ if (closure[i][j])
+ goto item_constrained;
+ }
+ /* Item i can be output */
+ vec_add1 (result, i);
+ {
+ for (k = 0; k < n_init_fns; k++)
+ closure[k][i] = 0;
+ /*
+ * Add a "Magic" a before a constraint.
+ * This means we'll never output it again
+ */
+ closure[i][i] = 1;
+ goto again;
+ }
+ item_constrained:
+ ;
+ }
+
+ /* see if we got a partial order... */
+ if (vec_len (result) != n_init_fns)
+ return clib_error_return
+ (0, "Failed to find a suitable init function order!");
+
+ /*
+ * We win.
+ * Bind the index variables, and output the feature node name vector
+ * using the partial order we just computed. Result is in stack
+ * order, because the entry with the fewest constraints (e.g. none)
+ * is output first, etc.
+ * Reset the listhead, and add items in result (aka reverse) order.
+ */
+ *head = 0;
+ for (i = 0; i < n_init_fns; i++)
+ {
+ p = hash_get (reg_by_index, result[i]);
+ ASSERT (p != 0);
+ this_reg = (_vlib_init_function_list_elt_t *) p[0];
+
+ this_reg->next_init_function = *head;
+ *head = this_reg;
+ }
+
+ /* Finally, clean up all the fine data we allocated */
+ /* *INDENT-OFF* */
+ hash_foreach_pair (hp, index_by_name,
+ ({
+ vec_add1 (keys_to_delete, (u8 *)hp->key);
+ }));
+ /* *INDENT-ON* */
+ hash_free (index_by_name);
+ for (i = 0; i < vec_len (keys_to_delete); i++)
+ vec_free (keys_to_delete[i]);
+ vec_free (keys_to_delete);
+ hash_free (reg_by_index);
+ vec_free (result);
+ clib_ptclosure_free (orig);
+ clib_ptclosure_free (closure);
+ return 0;
+}
+
+/**
+ * @brief call a set of init / exit / main-loop enter functions
+ * @param vm vlib_main_t
+ * @param head address of the listhead to sort and then invoke
+ * @returns 0 on success, clib_error_t * on error
+ *
+ * The "init_functions_called" hash supports a subtle mix of procedural
+ * and formally-specified ordering constraints. The following schemes
+ * are *roughly* equivalent:
+ *
+ * static clib_error_t *init_runs_first (vlib_main_t *vm)
+ * {
+ * clib_error_t *error;
+ *
+ * ... do some stuff...
+ *
+ * if ((error = vlib_call_init_function (init_runs_next)))
+ * return error;
+ * ...
+ * }
+ * VLIB_INIT_FUNCTION (init_runs_first);
+ *
+ * and
+ *
+ * static clib_error_t *init_runs_first (vlib_main_t *vm)
+ * {
+ * ... do some stuff...
+ * }
+ * VLIB_INIT_FUNCTION (init_runs_first) =
+ * {
+ * .runs_before = VLIB_INITS("init_runs_next"),
+ * };
+ *
+ * The first form will [most likely] call "init_runs_next" on the
+ * spot. The second form means that "init_runs_first" runs before
+ * "init_runs_next," possibly much earlier in the sequence.
+ *
+ * Please DO NOT construct sets of init functions where A before B
+ * actually means A *right before* B. It's not necessary - simply combine
+ * A and B - and it leads to hugely annoying debugging exercises.
+ */
clib_error_t *
vlib_call_init_exit_functions (vlib_main_t * vm,
- _vlib_init_function_list_elt_t * head,
+ _vlib_init_function_list_elt_t ** headp,
int call_once)
{
clib_error_t *error = 0;
_vlib_init_function_list_elt_t *i;
- i = head;
+ if ((error = init_exit_function_sort (headp)))
+ return (error);
+
+ i = *headp;
while (i)
{
if (call_once && !hash_get (vm->init_functions_called, i->f))
@@ -73,21 +366,21 @@
#undef _
return vlib_call_init_exit_functions
- (vm, vm->init_function_registrations, 1 /* call_once */ );
+ (vm, &vm->init_function_registrations, 1 /* call_once */ );
}
clib_error_t *
vlib_call_all_main_loop_enter_functions (vlib_main_t * vm)
{
return vlib_call_init_exit_functions
- (vm, vm->main_loop_enter_function_registrations, 1 /* call_once */ );
+ (vm, &vm->main_loop_enter_function_registrations, 1 /* call_once */ );
}
clib_error_t *
vlib_call_all_main_loop_exit_functions (vlib_main_t * vm)
{
return vlib_call_init_exit_functions
- (vm, vm->main_loop_exit_function_registrations, 1 /* call_once */ );
+ (vm, &vm->main_loop_exit_function_registrations, 1 /* call_once */ );
}
clib_error_t *
@@ -159,6 +452,204 @@
return error;
}
+void
+vlib_init_dump (void)
+{
+ vlib_main_t *vm = vlib_get_main ();
+ int i = 0;
+
+ _vlib_init_function_list_elt_t *head, *this;
+ head = vm->init_function_registrations;
+
+ this = head;
+ while (this)
+ {
+ fformat (stdout, "[%d]: %s\n", i++, this->name);
+ this = this->next_init_function;
+ }
+}
+
+static clib_error_t *
+show_init_function_command_fn (vlib_main_t * vm,
+ unformat_input_t * input,
+ vlib_cli_command_t * cmd)
+{
+ int which = 1;
+ int verbose = 0;
+ int i, n_init_fns;
+ _vlib_init_function_list_elt_t *head, *this;
+ uword *index_by_name;
+ uword *reg_by_index;
+ u8 **init_f_names = 0;
+ u8 *init_f_name;
+ uword *p;
+ _vlib_init_function_list_elt_t *this_reg = 0;
+ hash_pair_t *hp;
+ u8 **keys_to_delete = 0;
+
+ while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+ {
+ if (unformat (input, "init"))
+ which = 1;
+ else if (unformat (input, "enter"))
+ which = 2;
+ else if (unformat (input, "exit"))
+ which = 3;
+ else if (unformat (input, "verbose %d", &verbose))
+ ;
+ else if (unformat (input, "verbose"))
+ verbose = 1;
+ else
+ break;
+ }
+
+ switch (which)
+ {
+ case 1:
+ head = vm->init_function_registrations;
+ break;
+ case 2:
+ head = vm->main_loop_enter_function_registrations;
+ break;
+ case 3:
+ head = vm->main_loop_exit_function_registrations;
+ break;
+ default:
+ return clib_error_return (0, "BUG");
+ }
+
+ if (verbose == 0)
+ {
+ this = head;
+ i = 0;
+ while (this)
+ {
+ vlib_cli_output (vm, "[%d]: %s", i++, this->name);
+ this = this->next_init_function;
+ }
+ return 0;
+ }
+
+ index_by_name = hash_create_string (0, sizeof (uword));
+ reg_by_index = hash_create (0, sizeof (uword));
+
+ this_reg = head;
+ n_init_fns = 0;
+ /* collect init fcn names */
+ while (this_reg)
+ {
+ init_f_name = format (0, "%s%c", this_reg->name, 0);
+ hash_set (reg_by_index, vec_len (init_f_names), (uword) this_reg);
+
+ hash_set_mem (index_by_name, init_f_name, vec_len (init_f_names));
+ vec_add1 (init_f_names, init_f_name);
+ n_init_fns++;
+ this_reg = this_reg->next_init_function;
+ }
+
+ for (i = 0; i < n_init_fns; i++)
+ {
+ p = hash_get (reg_by_index, i);
+ ASSERT (p != 0);
+ this_reg = (_vlib_init_function_list_elt_t *) p[0];
+ vlib_cli_output (vm, "[%d] %s", i, this_reg->name);
+ {
+ char **runs_before, **runs_after, **init_order;
+ runs_before = this_reg->runs_before;
+ while (runs_before && runs_before[0])
+ {
+ _vlib_init_function_list_elt_t *successor;
+ uword successor_index;
+ p = hash_get_mem (index_by_name, runs_before[0]);
+ if (p == 0)
+ {
+ clib_warning ("couldn't find successor '%s'", runs_before[0]);
+ runs_before++;
+ continue;
+ }
+ successor_index = p[0];
+ p = hash_get (reg_by_index, p[0]);
+ ASSERT (p != 0);
+ successor = (_vlib_init_function_list_elt_t *) p[0];
+ vlib_cli_output (vm, " before '%s' [%lld]",
+ successor->name, successor_index);
+ runs_before++;
+ }
+ runs_after = this_reg->runs_after;
+ while (runs_after && runs_after[0])
+ {
+ _vlib_init_function_list_elt_t *predecessor;
+ uword predecessor_index;
+ p = hash_get_mem (index_by_name, runs_after[0]);
+ if (p == 0)
+ {
+ clib_warning ("couldn't find predecessor '%s'",
+ runs_after[0]);
+ runs_after++;
+ continue;
+ }
+ predecessor_index = p[0];
+ p = hash_get (reg_by_index, p[0]);
+ ASSERT (p != 0);
+ predecessor = (_vlib_init_function_list_elt_t *) p[0];
+ vlib_cli_output (vm, " after '%s' [%lld]",
+ predecessor->name, predecessor_index);
+ runs_after++;
+ }
+ init_order = this_reg->init_order;
+ while (init_order && init_order[0])
+ {
+ _vlib_init_function_list_elt_t *inorder;
+ uword inorder_index;
+ p = hash_get_mem (index_by_name, init_order[0]);
+ if (p == 0)
+ {
+ clib_warning ("couldn't find order element'%s'",
+ init_order[0]);
+ init_order++;
+ continue;
+ }
+ inorder_index = p[0];
+ p = hash_get (reg_by_index, p[0]);
+ ASSERT (p != 0);
+ inorder = (_vlib_init_function_list_elt_t *) p[0];
+ vlib_cli_output (vm, " in order '%s' [%lld]",
+ inorder->name, inorder_index);
+ init_order++;
+ }
+ }
+ }
+ /* *INDENT-OFF* */
+ hash_foreach_pair (hp, index_by_name,
+ ({
+ vec_add1 (keys_to_delete, (u8 *)hp->key);
+ }));
+ /* *INDENT-ON* */
+ hash_free (index_by_name);
+ for (i = 0; i < vec_len (keys_to_delete); i++)
+ vec_free (keys_to_delete[i]);
+ vec_free (keys_to_delete);
+ hash_free (reg_by_index);
+
+ return 0;
+}
+
+/*?
+ * Show init function order
+ *
+ * @cliexpar
+ * @cliexstart{show init-function [init | enter | exit] [verbose [nn]]}
+ * @cliexend
+ ?*/
+/* *INDENT-OFF* */
+VLIB_CLI_COMMAND (show_init_function, static) = {
+ .path = "show init-function",
+ .short_help = "show init-function [init | enter | exit][verbose [nn]]",
+ .function = show_init_function_command_fn,
+};
+/* *INDENT-ON* */
+
+
/*
* fd.io coding-style-patch-verification: ON
*