[PATCH v2 7/7] async: Introduce a dependency resolver for parallel execution

[Chris Wilson]

A challenge in driver initialisation is the coordination of many small
sometimes independent, sometimes interdependent tasks. We would like to
schedule the independent tasks for execution in parallel across as many
cores as possible for rapid initialisation, and then schedule all the
dependent tasks once they have completed, again running as many of those
in parallel as is possible.

Resolving the interdependencies by hand is time consuming and error
prone. Instead, we want to declare what dependencies a particular task
has, and what that task provides, and let a runtime dependency solver
work out what tasks to run and when, and which in parallel. To this end,
we introduce the struct async_dependency_graph building upon the kfence
and async_work from the previous patches to allow for the runtime
computation of the topological task ordering.

The graph is constructed with async_dependency_graph_build(), which
takes the task, its dependencies and what it provides, and builds the
graph of kfences required for ordering. Additional kfences can be
inserted through async_dependency_depends() and
async_dependency_provides() for manual control of the execution order,
and async_dependency_get() retrieves a kfence for inspection or waiting
upon.

Signed-off-by: Chris Wilson 
Cc: Sumit Semwal 
Cc: Shuah Khan 
Cc: Tejun Heo 
Cc: Daniel Vetter 
Cc: Andrew Morton 
Cc: Ingo Molnar 
Cc: Kees Cook 
Cc: Thomas Gleixner 
Cc: "Paul E. McKenney" 
Cc: Dan Williams 
Cc: Andrey Ryabinin 
Cc: Davidlohr Bueso 
Cc: Nikolay Aleksandrov 
Cc: "David S. Miller" 
Cc: "Peter Zijlstra (Intel)" 
Cc: Rasmus Villemoes 
Cc: Andy Shevchenko 
Cc: Dmitry Vyukov 
Cc: Alexander Potapenko 
Cc: linux-kernel@vger.kernel.org
Cc: linux-me...@vger.kernel.org
Cc: dri-de...@lists.freedesktop.org
Cc: linaro-mm-...@lists.linaro.org
---
 include/linux/async.h  |  38 +++
 kernel/async.c | 250 
 lib/Kconfig.debug  |  12 +
 lib/Makefile   |   1 +
 lib/test-async-dependency-graph.c  | 316 +
 .../selftests/lib/async-dependency-graph.sh|  10 +
 6 files changed, 627 insertions(+)
 create mode 100644 lib/test-async-dependency-graph.c
 create mode 100755 tools/testing/selftests/lib/async-dependency-graph.sh

diff --git a/include/linux/async.h b/include/linux/async.h
index de44306f8cb7..0a0040d3fc01 100644
--- a/include/linux/async.h
+++ b/include/linux/async.h
@@ -15,6 +15,7 @@
 #include 
 #include 
 #include 
+#include 
 
 typedef u64 async_cookie_t;
 typedef void (*async_func_t) (void *data, async_cookie_t cookie);
@@ -101,4 +102,41 @@ extern async_cookie_t queue_async_work(struct async_domain 
*domain,
   gfp_t gfp);
 extern async_cookie_t schedule_async_work(struct async_work *work);
 
+/* Build a graph of work based on dependencies generated by keywords.
+ * The graph must be acyclic. Can be used to both generate a topological
+ * ordering of tasks, and to execute independent chains of tasks in
+ * parallel.
+ */
+
+struct async_dependency_graph {
+   struct rb_root root;
+   struct list_head list;
+};
+
+#define ASYNC_DEPENDENCY_GRAPH_INIT(_name) {   \
+   .root = RB_ROOT,\
+   .list = LIST_HEAD_INIT(_name.list), \
+}
+
+#define ASYNC_DEPENDENCY_GRAPH(_name) \
+   struct async_dependency_graph _name = ASYNC_DEPENDENCY_GRAPH_INIT(_name)
+
+extern int async_dependency_graph_build(struct async_dependency_graph *adg,
+   async_func_t fn, void *data,
+   const char *depends,
+   const char *provides);
+
+extern int async_dependency_depends(struct async_dependency_graph *adg,
+   struct kfence *fence,
+   const char *depends);
+
+extern int async_dependency_provides(struct async_dependency_graph *adg,
+struct kfence *fence,
+const char *provides);
+
+extern struct kfence *async_dependency_get(struct async_dependency_graph *adg,
+  const char *name);
+
+extern void async_dependency_graph_execute(struct async_dependency_graph *adg);
+
 #endif
diff --git a/kernel/async.c 

[PATCH v2 7/7] async: Introduce a dependency resolver for parallel execution

[Chris Wilson]

A challenge in driver initialisation is the coordination of many small
sometimes independent, sometimes interdependent tasks. We would like to
schedule the independent tasks for execution in parallel across as many
cores as possible for rapid initialisation, and then schedule all the
dependent tasks once they have completed, again running as many of those
in parallel as is possible.

Resolving the interdependencies by hand is time consuming and error
prone. Instead, we want to declare what dependencies a particular task
has, and what that task provides, and let a runtime dependency solver
work out what tasks to run and when, and which in parallel. To this end,
we introduce the struct async_dependency_graph building upon the kfence
and async_work from the previous patches to allow for the runtime
computation of the topological task ordering.

The graph is constructed with async_dependency_graph_build(), which
takes the task, its dependencies and what it provides, and builds the
graph of kfences required for ordering. Additional kfences can be
inserted through async_dependency_depends() and
async_dependency_provides() for manual control of the execution order,
and async_dependency_get() retrieves a kfence for inspection or waiting
upon.

Signed-off-by: Chris Wilson 
Cc: Sumit Semwal 
Cc: Shuah Khan 
Cc: Tejun Heo 
Cc: Daniel Vetter 
Cc: Andrew Morton 
Cc: Ingo Molnar 
Cc: Kees Cook 
Cc: Thomas Gleixner 
Cc: "Paul E. McKenney" 
Cc: Dan Williams 
Cc: Andrey Ryabinin 
Cc: Davidlohr Bueso 
Cc: Nikolay Aleksandrov 
Cc: "David S. Miller" 
Cc: "Peter Zijlstra (Intel)" 
Cc: Rasmus Villemoes 
Cc: Andy Shevchenko 
Cc: Dmitry Vyukov 
Cc: Alexander Potapenko 
Cc: linux-kernel@vger.kernel.org
Cc: linux-me...@vger.kernel.org
Cc: dri-de...@lists.freedesktop.org
Cc: linaro-mm-...@lists.linaro.org
---
 include/linux/async.h  |  38 +++
 kernel/async.c | 250 
 lib/Kconfig.debug  |  12 +
 lib/Makefile   |   1 +
 lib/test-async-dependency-graph.c  | 316 +
 .../selftests/lib/async-dependency-graph.sh|  10 +
 6 files changed, 627 insertions(+)
 create mode 100644 lib/test-async-dependency-graph.c
 create mode 100755 tools/testing/selftests/lib/async-dependency-graph.sh

diff --git a/include/linux/async.h b/include/linux/async.h
index de44306f8cb7..0a0040d3fc01 100644
--- a/include/linux/async.h
+++ b/include/linux/async.h
@@ -15,6 +15,7 @@
 #include 
 #include 
 #include 
+#include 
 
 typedef u64 async_cookie_t;
 typedef void (*async_func_t) (void *data, async_cookie_t cookie);
@@ -101,4 +102,41 @@ extern async_cookie_t queue_async_work(struct async_domain 
*domain,
   gfp_t gfp);
 extern async_cookie_t schedule_async_work(struct async_work *work);
 
+/* Build a graph of work based on dependencies generated by keywords.
+ * The graph must be acyclic. Can be used to both generate a topological
+ * ordering of tasks, and to execute independent chains of tasks in
+ * parallel.
+ */
+
+struct async_dependency_graph {
+   struct rb_root root;
+   struct list_head list;
+};
+
+#define ASYNC_DEPENDENCY_GRAPH_INIT(_name) {   \
+   .root = RB_ROOT,\
+   .list = LIST_HEAD_INIT(_name.list), \
+}
+
+#define ASYNC_DEPENDENCY_GRAPH(_name) \
+   struct async_dependency_graph _name = ASYNC_DEPENDENCY_GRAPH_INIT(_name)
+
+extern int async_dependency_graph_build(struct async_dependency_graph *adg,
+   async_func_t fn, void *data,
+   const char *depends,
+   const char *provides);
+
+extern int async_dependency_depends(struct async_dependency_graph *adg,
+   struct kfence *fence,
+   const char *depends);
+
+extern int async_dependency_provides(struct async_dependency_graph *adg,
+struct kfence *fence,
+const char *provides);
+
+extern struct kfence *async_dependency_get(struct async_dependency_graph *adg,
+  const char *name);
+
+extern void async_dependency_graph_execute(struct async_dependency_graph *adg);
+
 #endif
diff --git a/kernel/async.c b/kernel/async.c
index 5cfa398a19b2..ac12566f2e0b 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -447,3 +447,253 @@ void init_async_domain(struct async_domain *domain, bool 
registered)
domain->registered = registered;
 }
 EXPORT_SYMBOL_GPL(init_async_domain);
+
+struct async_dependency {
+   struct kfence fence;
+   struct rb_node node;
+   struct list_head link;
+   char name[0];
+};
+
+static struct async_dependency *
+__lookup_dependency(struct