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>

1 files changed, 496 insertions, 5 deletions

diff --git a/src/vlib/init.c b/src/vlib/init.c
index 8d4784513ab..8010e9e97cd 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 @@ vlib_call_all_init_functions (vlib_main_t * vm)
 #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 @@ done:
   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
  *