[PATCH 00/16] deps: deterministic driver initialization order

[PATCH 00/16] deps: deterministic driver initialization order

[Alexander Holler]

Hello,

I've already written a lot on that topic, therefor this introductory
mail doesn't explain everything.

Please have a look at the threads

"dt: dependencies (for deterministic driver initialization order based on
the DT)"

and

"On-demand device registration"

on LKML for previous discussions.

In short, the current init system is quiet old and doesn't really match
todays HW which needs much more drivers than 20 years ago.

As I've mentioned in those threads, initcalls should be identifiable
in order to sort them. My previous attempt intercepted the driver
registrations in order to do that, which unfortunately ended up with
having to deal how drivers are creating devices.

I've now spend some more time and this partly new approach now annotates
the initcalls directly, by storing a pointer to a struct device_driver in
addition to the pointer to the initcall.

This makes my previous patches smaller, cleaner and better to understand,
the result which you can see in this little patch series.

The whole patch series is made up of several parts.

The first 4 patches are modifying dtc to include dependencies (type
information for phandles).

The next 3 patches are the ones which are implementing those annotated
initcalls and the driver sort algorithm.

Then there are 3 patches with small changes on some dts.

The following 4 patches with the WIP (Work In Progress) are changing
some initcalls to annotated initcalls. I would split them up in
a bunch of patches (one for each driver), if I get the promise that
the other patches will be merged into mainline (but not without that
promise).

The final 2 patches are fixes which should end up in mainline, regardless
if this feature is merged or not.

Some numbers (5 boots on each board, without and with ordering drivers),
all times are seconds.

Kirkwood (dockstar, armv5):

Boot to "Freeing unused kernel memory" (includes mounting the rootfs),
unordered:
4.456016 3.937801 4.114788 4.114526 3.949480 (average 4.1145222)
ordered:
3.173054 3.164045 3.141418 3.480679 3.459298 (3.2836988)
Time needed to sort (of_init_build_order()):
0.003024
Time needed to match drivers to the order (without calling them):
0.002884

Beagleboard (rev C4, armv7):

unordered:
6.706024 6.821746 6.696014 6.673675 6.769866 (6.733465)
ordered:
5.544860 5.514160 5.505859 5.527374 5.496795 (5.5178096)
sorting: 0.021209
matching: 0.006165

Beaglebone Black (rev A5, armv7):

unordered:
3.826531 3.825662 3.826648 3.825434 3.825263 (3.8259076)
ordered:
2.838554 2.838322 2.839459 2.838467 2.838421 (2.8386446)
sorting: 0.004769
matching: 0.004860

imx6q (armv7):

unordered:
3.451998 3.418864 3.446952 3.429974 3.440996 (3.4377568)
ordered:
3.538312 3.549019 3.538105 3.515916 3.555715 (3.5394134)
sorting: 0.004622
matching: 0.003868


Because I'm using different configuration options on these boards,
the absolute times aren't comparable.

But in conclusion, most boards are booting faster when the initcalls
have been ordered.

In addition, ordering the initcalls makes the initialization sequence
more deterministic (it can even be seen without booting a machine).

But I still think the most benefit of these little series is by not having
to use in-driver hacks or that ugly brute force trial-and-error deferred
probing in order to fix a wrong default call order of initcalls.

Further improvements could be to initialize drivers in parallel (using
multiple cores) and/or to use this stuff on x86 (ACPI) too (e.g. by using a
minimal DT which just includes dependencies).


To test this series with any other DT enabled board, look at which
drivers are referenced in the DT (see patch 2 or 3), annotate these
drivers (trivial, see patch 5 or the examples with WIP in the subject),
turn on CONFIG_OF_DEPENDENCIES, compile and boot.


Just to mention it, unless CONFIG_OF_DEPENDENCIES is turned on (which is
marked as experimental), nothing will change, even if you've annotated
some drivers (the new macros will just map to the old ones).


Regards,

Alexander Holler

PS: Please keep in mind that these patches are an offer. I'm already
100+ patches above mainline and don't really care to maintain some more
for myself.
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 01/16] deps: dtc: Automatically add new property 'dependencies' which contains a list of referenced phandles

[Alexander Holler]

During the step from .dts to .dtb the information about dependcies
contained in the .dts through phandle references is lost. This makes it
impossible to use the binary blob to create a dependency graph without
knowing the semantic of all cell arrays.

Therefor automatically add a new property called 'dependencies' to all
nodes which have phandle references in one of their properties.

This new property will contain an array of phandles with one value for
every phandle referenced by other properties in the node.

If such a property already exists (e.g. to manually add dependencies
through the .dts), the existing list will be expanded.

Added phandles will be the phandle of either the referenced node itself
(if it has a property named 'compatible', or of the next parent of the
referenced node which as property named 'compatible'. This ensures only
dependencies to drivers will be added.

References to phandles of parent or child nodes will not be added to this
property, because this information is already contained in the blob (in
the form of the tree itself).

No dependencies to disabled nodes will be added.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/Makefile       |   3 +-
 scripts/dtc/Makefile.dtc   |   1 +
 scripts/dtc/dependencies.c | 108 +++++++++++++++++++++++++++++++++++++++++++++
 scripts/dtc/dtc.c          |  12 ++++-
 scripts/dtc/dtc.h          |   3 ++
 5 files changed, 125 insertions(+), 2 deletions(-)
 create mode 100644 scripts/dtc/dependencies.c

diff --git a/scripts/dtc/Makefile b/scripts/dtc/Makefile
index 2a48022..1174cf9 100644
--- a/scripts/dtc/Makefile
+++ b/scripts/dtc/Makefile
@@ -4,7 +4,7 @@ hostprogs-y	:= dtc
 always		:= $(hostprogs-y)
 
 dtc-objs	:= dtc.o flattree.o fstree.o data.o livetree.o treesource.o \
-		   srcpos.o checks.o util.o
+		   srcpos.o checks.o util.o dependencies.o
 dtc-objs	+= dtc-lexer.lex.o dtc-parser.tab.o
 
 # Source files need to get at the userspace version of libfdt_env.h to compile
@@ -13,6 +13,7 @@ HOSTCFLAGS_DTC := -I$(src) -I$(src)/libfdt
 
 HOSTCFLAGS_checks.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_data.o := $(HOSTCFLAGS_DTC)
+HOSTCFLAGS_dependencies.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_dtc.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_flattree.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_fstree.o := $(HOSTCFLAGS_DTC)
diff --git a/scripts/dtc/Makefile.dtc b/scripts/dtc/Makefile.dtc
index bece49b..5fb5343 100644
--- a/scripts/dtc/Makefile.dtc
+++ b/scripts/dtc/Makefile.dtc
@@ -6,6 +6,7 @@
 DTC_SRCS = \
 	checks.c \
 	data.c \
+	dependencies.c \
 	dtc.c \
 	flattree.c \
 	fstree.c \
diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
new file mode 100644
index 0000000..dd4658c
--- /dev/null
+++ b/scripts/dtc/dependencies.c
@@ -0,0 +1,108 @@
+/*
+ * Code to add a property which contains dependencies (used phandle references)
+ * to all (driver) nodes which are having phandle references.
+ *
+ * Copyright (C) 2014 Alexander Holler <holler@ahsoftware.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <dtc.h>
+
+/* Searches upwards for a node with a property 'compatible' */
+static struct node *find_compatible_not_disabled(struct node *node)
+{
+	struct property *prop;
+
+	while (node) {
+		prop = get_property(node, "compatible");
+		if (prop) {
+			prop = get_property(node, "status");
+			if (prop)
+				if (!prop->val.len ||
+					(strcmp(prop->val.val, "okay") &&
+						strcmp(prop->val.val, "ok")))
+					return NULL; /* disabled */
+			return node;
+		}
+		node = node->parent;
+	}
+	return NULL;
+}
+
+static bool is_parent_of(struct node *node1, struct node *node2)
+{
+	while (node2) {
+		if (node2->parent == node1)
+			return true;
+		node2 = node2->parent;
+	}
+	return false;
+
+}
+
+static void add_deps(struct node *dt, struct node *node, struct property *prop)
+{
+	struct marker *m = prop->val.markers;
+	struct node *refnode;
+	cell_t phandle;
+	struct property *prop_deps;
+	unsigned i;
+	cell_t *cell;
+	struct node *source;
+	struct node *target;
+
+	for_each_marker_of_type(m, REF_PHANDLE) {
+		assert(m->offset + sizeof(cell_t) <= prop->val.len);
+
+		refnode = get_node_by_ref(dt, m->ref);
+		if (!refnode) {
+			fprintf(stderr,
+				"ERROR: Reference to non-existent node or label \"%s\"\n",
+				m->ref);
+			continue;
+		}
+
+		source = find_compatible_not_disabled(node);
+		target = find_compatible_not_disabled(refnode);
+		if (!source || !target || source == target ||
+				is_parent_of(source, target) ||
+				is_parent_of(target, source))
+			continue;
+		phandle = get_node_phandle(dt, target);
+		prop_deps = get_property(source, "dependencies");
+		if (!prop_deps) {
+			add_property(source,
+			     build_property("dependencies",
+				data_append_cell(empty_data, phandle)));
+			continue;
+		}
+		cell = (cell_t *)prop_deps->val.val;
+		for (i = 0; i < prop_deps->val.len/4; ++i)
+			if (*cell++ == cpu_to_fdt32(phandle))
+				break;
+		if (i < prop_deps->val.len/4)
+			continue; /* avoid duplicates */
+		prop_deps->val = data_append_cell(prop_deps->val, phandle);
+	}
+}
+
+static void process_nodes_props(struct node *dt, struct node *node)
+{
+	struct node *child;
+	struct property *prop;
+
+	for_each_property(node, prop)
+		add_deps(dt, node, prop);
+
+	for_each_child(node, child)
+		process_nodes_props(dt, child);
+}
+
+void add_dependencies(struct boot_info *bi)
+{
+	process_nodes_props(bi->dt, bi->dt);
+}
diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c
index 8c4add6..28def27 100644
--- a/scripts/dtc/dtc.c
+++ b/scripts/dtc/dtc.c
@@ -51,7 +51,7 @@ static void fill_fullpaths(struct node *tree, const char *prefix)
 #define FDT_VERSION(version)	_FDT_VERSION(version)
 #define _FDT_VERSION(version)	#version
 static const char usage_synopsis[] = "dtc [options] <input file>";
-static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sW:E:hv";
+static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDW:E:hv";
 static struct option const usage_long_opts[] = {
 	{"quiet",            no_argument, NULL, 'q'},
 	{"in-format",         a_argument, NULL, 'I'},
@@ -66,6 +66,7 @@ static struct option const usage_long_opts[] = {
 	{"force",            no_argument, NULL, 'f'},
 	{"include",           a_argument, NULL, 'i'},
 	{"sort",             no_argument, NULL, 's'},
+	{"no-deps",          no_argument, NULL, 'D'},
 	{"phandle",           a_argument, NULL, 'H'},
 	{"warning",           a_argument, NULL, 'W'},
 	{"error",             a_argument, NULL, 'E'},
@@ -93,6 +94,7 @@ static const char * const usage_opts_help[] = {
 	"\n\tTry to produce output even if the input tree has errors",
 	"\n\tAdd a path to search for include files",
 	"\n\tSort nodes and properties before outputting (useful for comparing trees)",
+	"\n\tDo not automatically add dependencies for phandle references",
 	"\n\tValid phandle formats are:\n"
 	 "\t\tlegacy - \"linux,phandle\" properties only\n"
 	 "\t\tepapr  - \"phandle\" properties only\n"
@@ -112,6 +114,7 @@ int main(int argc, char *argv[])
 	const char *outname = "-";
 	const char *depname = NULL;
 	bool force = false, sort = false;
+	bool dependencies = true;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -179,6 +182,10 @@ int main(int argc, char *argv[])
 			sort = true;
 			break;
 
+		case 'D':
+			dependencies = false;
+			break;
+
 		case 'W':
 			parse_checks_option(true, false, optarg);
 			break;
@@ -236,6 +243,9 @@ int main(int argc, char *argv[])
 	if (sort)
 		sort_tree(bi);
 
+	if (dependencies)
+		add_dependencies(bi);
+
 	if (streq(outname, "-")) {
 		outf = stdout;
 	} else {
diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h
index 56212c8..6facad1 100644
--- a/scripts/dtc/dtc.h
+++ b/scripts/dtc/dtc.h
@@ -266,4 +266,7 @@ struct boot_info *dt_from_source(const char *f);
 
 struct boot_info *dt_from_fs(const char *dirname);
 
+/* Dependencies */
+void add_dependencies(struct boot_info *bi);
+
 #endif /* _DTC_H */
-- 
2.1.0

[PATCH 03/16] deps: dtc: Add option to print dependency graph as dot (Graphviz)

[Alexander Holler]

Add option -T do print a dependency graph in dot format for
generating a picture with Graphviz.

E.g.

	dtc -T foo.dts | dot -T svg -o foo.svg

would generate the picture foo.png with the dependency graph.

Convential dependencies (those based on the tree structure) are having
black arrows, dependencies based on the property 'dependencies' are
having cyan arrows.

Option -D to not automatically add dependencies does still work, so
you could build a classic dependency graph with

	dtc -D -T foo.dts | dot -T png -o foo_no_auto_deps.png

This works with binary blobs as input too. E.g.

	CROSS_COMPILE=gcc-foo ARCH=arm make foo.dtb
	scripts/dtc/dtc -I dtb -T arch/arm/boot/dts/foo.dtb

would print the dot file.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/dependencies.c | 49 ++++++++++++++++++++++++++++++++++++++++------
 scripts/dtc/dtc.c          | 19 +++++++++++++++---
 scripts/dtc/dtc.h          |  2 +-
 3 files changed, 60 insertions(+), 10 deletions(-)

diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
index 3fb5cef..2c1e0d4 100644
--- a/scripts/dtc/dependencies.c
+++ b/scripts/dtc/dependencies.c
@@ -298,7 +298,7 @@ static void __init topological_sort(void)
 			depth_first_search(i);
 }
 
-static int __init add_dep_list(struct device_node *node)
+static int __init add_dep_list(struct device_node *node, bool print_dot)
 {
 	const __be32 *list, *list_end;
 	uint32_t ph;
@@ -328,6 +328,9 @@ static int __init add_dep_list(struct device_node *node)
 		rc = insert_edge(node->phandle, ph);
 		if (rc)
 			break;
+		if (print_dot)
+			printf("      node0x%x -> node0x%x [color=cyan]\n",
+				node->phandle, ph);
 	}
 
 	return rc;
@@ -352,9 +355,10 @@ static const char *of_prop_next_string(struct property *prop, const char *cur)
 }
 
 static int __init add_deps_lnx(struct device_node *parent,
-				struct device_node *node)
+				struct device_node *node, bool print_dot)
 {
 	struct device_node *child;
+	const char *cp;
 	int rc = 0;
 
 	if (!__of_device_is_available(node))
@@ -375,13 +379,34 @@ static int __init add_deps_lnx(struct device_node *parent,
 			return -EINVAL;
 		}
 		order.parent_by_phandle[node->phandle] = parent->phandle;
-		rc = add_dep_list(node);
+		if (print_dot) {
+			struct property *prop;
+
+			printf("    node0x%x [label=\"0x%x %s", node->phandle,
+						node->phandle, node->name);
+			if (node->full_name)
+				printf(" (%s)", node->full_name);
+			prop = get_property(node, "compatible");
+			if (prop) {
+				printf("\\n");
+				for (cp = of_prop_next_string(prop, NULL); cp;
+				     cp = of_prop_next_string(prop, cp)) {
+					if (cp != prop->val.val)
+						putchar(' ');
+					printf("%s", cp);
+				}
+			}
+			printf("\"];\n");
+			printf("      node0x%x -> node0x%x\n", node->phandle,
+							parent->phandle);
+		}
+		rc = add_dep_list(node, print_dot);
 		if (unlikely(rc))
 			return rc;
 		parent = node; /* change the parent only if node is a driver */
 	}
 	for_each_child_of_node(node, child) {
-		rc = add_deps_lnx(parent, child);
+		rc = add_deps_lnx(parent, child, print_dot);
 		if (unlikely(rc))
 			break;
 	}
@@ -424,7 +449,7 @@ void __init of_init_print_order(const char *name)
 	}
 }
 
-int __init of_init_build_order(struct device_node *root)
+int __init of_init_build_order(struct device_node *root, const char *print_dot)
 {
 	struct device_node *child;
 	int rc = 0;
@@ -436,12 +461,24 @@ int __init of_init_build_order(struct device_node *root)
 	calc_max_phandle(root);
 	order.old_max_phandle = order.max_phandle;
 
+	if (print_dot) {
+		printf("digraph G {\n");
+		printf("    node0x%x [label=\"0x%x root (/)\"];\n",
+			order.max_phandle+1, order.max_phandle+1);
+	}
+
 	for_each_child_of_node(root, child) {
-		rc = add_deps_lnx(root, child);
+		rc = add_deps_lnx(root, child, print_dot);
 		if (unlikely(rc))
 			break;
 	}
 
+	if (print_dot) {
+		printf("  graph [label=\"Dependency Graph for %s (%u nodes, %u edges)\"];\n",
+			print_dot, graph.nvertices, graph.nedges);
+		printf("}\n");
+	}
+
 	of_node_put(root);
 	topological_sort();
 
diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c
index 494c531..b1ca363 100644
--- a/scripts/dtc/dtc.c
+++ b/scripts/dtc/dtc.c
@@ -51,7 +51,7 @@ static void fill_fullpaths(struct node *tree, const char *prefix)
 #define FDT_VERSION(version)	_FDT_VERSION(version)
 #define _FDT_VERSION(version)	#version
 static const char usage_synopsis[] = "dtc [options] <input file>";
-static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDtW:E:hv";
+static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDtTW:E:hv";
 static struct option const usage_long_opts[] = {
 	{"quiet",            no_argument, NULL, 'q'},
 	{"in-format",         a_argument, NULL, 'I'},
@@ -68,6 +68,7 @@ static struct option const usage_long_opts[] = {
 	{"sort",             no_argument, NULL, 's'},
 	{"no-deps",          no_argument, NULL, 'D'},
 	{"initialization-order", no_argument, NULL, 't'},
+	{"dot",              no_argument, NULL, 'T'},
 	{"phandle",           a_argument, NULL, 'H'},
 	{"warning",           a_argument, NULL, 'W'},
 	{"error",             a_argument, NULL, 'E'},
@@ -97,6 +98,7 @@ static const char * const usage_opts_help[] = {
 	"\n\tSort nodes and properties before outputting (useful for comparing trees)",
 	"\n\tDo not automatically add dependencies for phandle references",
 	"\n\tPrint (default) initialization order",
+	"\n\tPrint dot with dependency graph (for use with Graphviz)",
 	"\n\tValid phandle formats are:\n"
 	 "\t\tlegacy - \"linux,phandle\" properties only\n"
 	 "\t\tepapr  - \"phandle\" properties only\n"
@@ -118,6 +120,7 @@ int main(int argc, char *argv[])
 	bool force = false, sort = false;
 	bool dependencies = true;
 	bool init_order = false;
+	bool print_dot = false;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -193,6 +196,10 @@ int main(int argc, char *argv[])
 			init_order = true;
 			break;
 
+		case 'T':
+			print_dot = true;
+			break;
+
 		case 'W':
 			parse_checks_option(true, false, optarg);
 			break;
@@ -254,12 +261,18 @@ int main(int argc, char *argv[])
 		add_dependencies(bi);
 
 	if (init_order) {
-		if (of_init_build_order(bi->dt))
+		if (of_init_build_order(bi->dt, 0))
 			exit(2);
 		of_init_print_order(arg);
 		exit(0);
 	}
 
+	if (print_dot) {
+		if (of_init_build_order(bi->dt, arg))
+			exit(2);
+		exit(0);
+	}
+
 	if (streq(outname, "-")) {
 		outf = stdout;
 	} else {
@@ -286,7 +299,7 @@ int main(int argc, char *argv[])
 	 * This is done after the output was saved because it
 	 * changes the tree slightly.
 	 */
-	if (of_init_build_order(bi->dt))
+	if (of_init_build_order(bi->dt, 0))
 		exit(2);
 
 	exit(0);
diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h
index 9ae4bfc..8ef8e6f 100644
--- a/scripts/dtc/dtc.h
+++ b/scripts/dtc/dtc.h
@@ -269,6 +269,6 @@ struct boot_info *dt_from_fs(const char *dirname);
 /* Dependencies */
 void add_dependencies(struct boot_info *bi);
 void of_init_print_order(const char *name);
-int of_init_build_order(struct node *root);
+int of_init_build_order(struct node *root, const char *print_dot);
 
 #endif /* _DTC_H */
-- 
2.1.0

[PATCH 04/16] deps: dtc: introduce new (virtual) property no-dependencies

[Alexander Holler]

In some cases it makes sense to handle some phandles not as dependencies.

This is escpecially true for 'remote-endpoint' properties, because these
otherwise introducing dependency cycles into the graph. To avoid these,
one end of each remote-endpoint pairs has not to be handled as a
dependency.

The syntax is like

	foo {
		remote-endpoint = <&bar>;
	};
	bar {
		remote-endpoint = <&foo>;
		no-dependencies = <&foo>;
	};

Without that 'no-dependencies' property dtc would automatically add a
dependency to foo to the property 'dependencies' of the node bar.
But with that 'no-dependencies' it will not automatically add the
listed dependencies.

The property 'no-dependencies' is virtual property and will not be added
to any output file.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/dependencies.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
index 2c1e0d4..76e4d91 100644
--- a/scripts/dtc/dependencies.c
+++ b/scripts/dtc/dependencies.c
@@ -44,6 +44,23 @@ static bool is_parent_of(struct node *node1, struct node *node2)
 
 }
 
+static bool is_no_dependency(struct node *dt, struct property *prop, cell_t ph)
+{
+	struct node *node;
+	unsigned i;
+	cell_t *cell = (cell_t *)(prop->val.val);
+
+	for (i = 0; i < prop->val.len/4; ++i) {
+		node = get_node_by_phandle(dt, cpu_to_fdt32(*cell++));
+		if (node) {
+			node = find_compatible_not_disabled(node);
+			if (node && get_node_phandle(dt, node) == ph)
+				return true;
+		}
+	}
+	return false;
+}
+
 static void add_deps(struct node *dt, struct node *node, struct property *prop)
 {
 	struct marker *m = prop->val.markers;
@@ -73,6 +90,10 @@ static void add_deps(struct node *dt, struct node *node, struct property *prop)
 				is_parent_of(target, source))
 			continue;
 		phandle = get_node_phandle(dt, target);
+		prop_deps = get_property(node, "no-dependencies");
+		if (prop_deps && is_no_dependency(dt, prop_deps, phandle))
+			/* avoid adding non-dependencies */
+			continue;
 		prop_deps = get_property(source, "dependencies");
 		if (!prop_deps) {
 			add_property(source,
@@ -102,9 +123,21 @@ static void process_nodes_props(struct node *dt, struct node *node)
 		process_nodes_props(dt, child);
 }
 
+static void del_prop_no_dependencies(struct node *node)
+{
+	struct node *child;
+
+	if (!node)
+		return;
+	delete_property_by_name(node, "no-dependencies");
+	for_each_child(node, child)
+		del_prop_no_dependencies(child);
+}
+
 void add_dependencies(struct boot_info *bi)
 {
 	process_nodes_props(bi->dt, bi->dt);
+	del_prop_no_dependencies(bi->dt);
 }
 
 /*
-- 
2.1.0

[PATCH 05/16] deps: introduce initcalls annotated with a struct device_driver

[Alexander Holler]

Make it possible to identify initcalls before calling them by adding
a pointer to a struct device_driver to the stored pointer to an initcall.

This is e.g. necessary in order to sort initcalls by whatever means
before calling them.

To annotate an initcall, the following changes are necessary on
drivers which want to offer that feature:

now				annotated
--------------------------------------------------------------------------
pure_initcall(fn)		annotated_initcall(pure, fn, dev_drv)
core_initcall(fn)		annotated_initcall(core, fn, dev_drv)
core_initcall_sync(fn)		annotated_initcall_sync(core, fn, dev_drv)
...
late_initcall(fn)		annotated_initcall(late, fn, dev_drv)
module_init(fn)			annotated_module_init(fn, dev_drv)

module_platform_driver(drv)	no changes necessary, done automatically
module_platform_driver_probe(drv, probe)	no changes necessary
module_i2c_driver(i2c_drv)	no changes necessary, done automatically

E.g. to make the driver sram offering an annotated initcall the
following patch is necessary:

----
-postcore_initcall(sram_init);
+annotated_initcall(postcore, sram_init, sram_driver.driver);
----

These changes can be done without any fear. If the feature is disabled,
which is the default, the new macros will just map to the old ones and
nothing is changed at all.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/kernel/vmlinux.lds.S     |  1 +
 include/asm-generic/vmlinux.lds.h |  6 ++++++
 include/linux/device.h            | 12 ++++++++++++
 include/linux/i2c.h               |  2 +-
 include/linux/init.h              | 33 +++++++++++++++++++++++++++++++++
 include/linux/module.h            |  2 ++
 include/linux/platform_device.h   | 16 ++++++++++++----
 init/Kconfig                      |  3 +++
 8 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
index 8b60fde..10a328f 100644
--- a/arch/arm/kernel/vmlinux.lds.S
+++ b/arch/arm/kernel/vmlinux.lds.S
@@ -213,6 +213,7 @@ SECTIONS
 #endif
 		INIT_SETUP(16)
 		INIT_CALLS
+		ANNOTATED_INITCALL
 		CON_INITCALL
 		SECURITY_INITCALL
 		INIT_RAM_FS
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h
index 8bd374d..7318ba7 100644
--- a/include/asm-generic/vmlinux.lds.h
+++ b/include/asm-generic/vmlinux.lds.h
@@ -660,6 +660,11 @@
 		INIT_CALLS_LEVEL(7)					\
 		VMLINUX_SYMBOL(__initcall_end) = .;
 
+#define ANNOTATED_INITCALL						\
+		VMLINUX_SYMBOL(__annotated_initcall_start) = .;		\
+		*(.annotated_initcall.init)				\
+		VMLINUX_SYMBOL(__annotated_initcall_end) = .;
+
 #define CON_INITCALL							\
 		VMLINUX_SYMBOL(__con_initcall_start) = .;		\
 		*(.con_initcall.init)					\
@@ -816,6 +821,7 @@
 		INIT_DATA						\
 		INIT_SETUP(initsetup_align)				\
 		INIT_CALLS						\
+		ANNOTATED_INITCALL					\
 		CON_INITCALL						\
 		SECURITY_INITCALL					\
 		INIT_RAM_FS						\
diff --git a/include/linux/device.h b/include/linux/device.h
index a2b4ea7..128fddd 100644
--- a/include/linux/device.h
+++ b/include/linux/device.h
@@ -1321,4 +1321,16 @@ static int __init __driver##_init(void) \
 } \
 device_initcall(__driver##_init);
 
+#define annotated_module_driver(__driver, __register, __unregister, ...) \
+static int __init __driver##_init(void) \
+{ \
+	return __register(&(__driver), ##__VA_ARGS__); \
+} \
+annotated_module_init(__driver##_init, __driver.driver); \
+static void __exit __driver##_exit(void) \
+{ \
+	__unregister(&(__driver), ##__VA_ARGS__); \
+} \
+module_exit(__driver##_exit)
+
 #endif /* _DEVICE_H_ */
diff --git a/include/linux/i2c.h b/include/linux/i2c.h
index e83a738..fa63ec1 100644
--- a/include/linux/i2c.h
+++ b/include/linux/i2c.h
@@ -626,7 +626,7 @@ static inline int i2c_adapter_id(struct i2c_adapter *adap)
  * use this macro once, and calling it replaces module_init() and module_exit()
  */
 #define module_i2c_driver(__i2c_driver) \
-	module_driver(__i2c_driver, i2c_add_driver, \
+	annotated_module_driver(__i2c_driver, i2c_add_driver, \
 			i2c_del_driver)
 
 #endif /* I2C */
diff --git a/include/linux/init.h b/include/linux/init.h
index b449f37..52ea986 100644
--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -124,6 +124,15 @@
 typedef int (*initcall_t)(void);
 typedef void (*exitcall_t)(void);
 
+struct device_driver;
+
+struct _annotated_initcall {
+	initcall_t initcall;
+	struct device_driver *driver;
+};
+extern struct _annotated_initcall __annotated_initcall_start[],
+				  __annotated_initcall_end[];
+
 extern initcall_t __con_initcall_start[], __con_initcall_end[];
 extern initcall_t __security_initcall_start[], __security_initcall_end[];
 
@@ -184,6 +193,11 @@ extern bool initcall_debug;
 	__attribute__((__section__(".initcall" #id ".init"))) = fn; \
 	LTO_REFERENCE_INITCALL(__initcall_##fn##id)
 
+#define __define_annotated_initcall(fn, drv) \
+	static struct _annotated_initcall __annotated_initcall_##fn __used \
+	__attribute__((__section__(".annotated_initcall.init"))) = \
+							{ fn, &(drv) }
+
 /*
  * Early initcalls run before initializing SMP.
  *
@@ -216,6 +230,25 @@ extern bool initcall_debug;
 #define late_initcall(fn)		__define_initcall(fn, 7)
 #define late_initcall_sync(fn)		__define_initcall(fn, 7s)
 
+/*
+ * Annotated initcalls are accompanied by a struct device_driver.
+ * This makes initcalls identifiable and is used to order initcalls.
+ *
+ * If disabled, nothing is changed and the classic level based
+ * initialization sequence is in use.
+ */
+#ifdef CONFIG_ANNOTATED_INITCALLS
+#define annotated_module_init(fn, drv)	__define_annotated_initcall(fn, drv)
+#define annotated_initcall(level, fn, drv) \
+					__define_annotated_initcall(fn, drv)
+#define annotated_initcall_sync(level, fn, drv) \
+					__define_annotated_initcall(fn, drv)
+#else
+#define annotated_module_init(fn, drv)	module_init(fn)
+#define annotated_initcall(level, fn, drv)	level ## _initcall(fn)
+#define annotated_initcall_sync(level, fn, drv)	level ## _initcall_sync(fn)
+#endif
+
 #define __initcall(fn) device_initcall(fn)
 
 #define __exitcall(fn) \
diff --git a/include/linux/module.h b/include/linux/module.h
index 3a19c79..6079d28 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -119,6 +119,8 @@ extern void cleanup_module(void);
 #define device_initcall_sync(fn)	module_init(fn)
 #define late_initcall(fn)		module_init(fn)
 #define late_initcall_sync(fn)		module_init(fn)
+#define annotated_initcall(level, fn, drv)	module_init(fn)
+#define annotated_module_init(fn, drv)	module_init(fn)
 
 #define console_initcall(fn)		module_init(fn)
 #define security_initcall(fn)		module_init(fn)
diff --git a/include/linux/platform_device.h b/include/linux/platform_device.h
index bba08f4..baa5a66 100644
--- a/include/linux/platform_device.h
+++ b/include/linux/platform_device.h
@@ -218,9 +218,17 @@ static inline void platform_set_drvdata(struct platform_device *pdev,
  * boilerplate.  Each module may only use this macro once, and
  * calling it replaces module_init() and module_exit()
  */
-#define module_platform_driver(__platform_driver) \
-	module_driver(__platform_driver, platform_driver_register, \
-			platform_driver_unregister)
+#define module_platform_driver(__driver) \
+static int __init __driver##_init(void) \
+{ \
+	return platform_driver_register(&(__driver)); \
+} \
+annotated_module_init(__driver##_init, __driver.driver); \
+static void __exit __driver##_exit(void) \
+{ \
+	platform_driver_unregister(&(__driver)); \
+} \
+module_exit(__driver##_exit)
 
 /* builtin_platform_driver() - Helper macro for builtin drivers that
  * don't do anything special in driver init.  This eliminates some
@@ -242,7 +250,7 @@ static int __init __platform_driver##_init(void) \
 	return platform_driver_probe(&(__platform_driver), \
 				     __platform_probe);    \
 } \
-module_init(__platform_driver##_init); \
+annotated_module_init(__platform_driver##_init, __platform_driver.driver); \
 static void __exit __platform_driver##_exit(void) \
 { \
 	platform_driver_unregister(&(__platform_driver)); \
diff --git a/init/Kconfig b/init/Kconfig
index af09b4f..5cfd7c4 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -26,6 +26,9 @@ config IRQ_WORK
 config BUILDTIME_EXTABLE_SORT
 	bool
 
+config ANNOTATED_INITCALLS
+	bool
+
 menu "General setup"
 
 config BROKEN
-- 
2.1.0

[PATCH 06/16] deps: deterministic driver initialization sequence based on dependencies from the DT

[Alexander Holler]

Use annotated initcalls along with dependencies found in the DT to sort
the initialization of drivers.

This makes stuff like in-driver hacks (e.g. omap), bruteforce
trial-and-error (deferred probe calls which are killing error messages)
and similar workarounds to circumvent the limited level based
driver initialization sequence unnecessary.

If enabled, this changes the driver initialization sequence as
described in the following table.

old (level based)	new (ordered, in parts)
-------------------------------------------------------------
early			early
pure (0)		pure (0)
core (1, 1s)		core (1, 1s)
postcore (2, 2s)	postcore (2, 2s)
arch (3, 3s)		arch (3, 3s)
subsys (4. 4s)		subsys (4, 4s)
fs (5, 5s)		fs (5, 5s)
rootfs			rootfs
device (6. 6s)		annotated initcalls (ordered by DT)
			annotated initcalls (not found in DT)
			device (6. 6s)
late (7, 7s)		late (7, 7s)

To use this feature new binary DT blobs which are including dependencies
(type information for phandles) have to be used and most drivers found
in the DT should have been annotated.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/of/Kconfig              |  12 ++
 drivers/of/Makefile             |   1 +
 drivers/of/of_dependencies.c    | 410 ++++++++++++++++++++++++++++++++++++++++
 include/linux/of_dependencies.h |  20 ++
 init/main.c                     |  11 +-
 5 files changed, 453 insertions(+), 1 deletion(-)
 create mode 100644 drivers/of/of_dependencies.c
 create mode 100644 include/linux/of_dependencies.h

diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
index 59bb855..9bf6c73 100644
--- a/drivers/of/Kconfig
+++ b/drivers/of/Kconfig
@@ -102,4 +102,16 @@ config OF_OVERLAY
 	  While this option is selected automatically when needed, you can
 	  enable it manually to improve device tree unit test coverage.
 
+config OF_DEPENDENCIES
+	bool "Device Tree dependency based initialization order (EXPERIMENTAL)"
+	select ANNOTATED_INITCALLS
+	help
+	  Enables dependency based initialization order of drivers.
+
+	  For correct operation the binary DT blob should have been
+	  populated with properties of type "dependencies" and the
+	  drivers referenced in the DT should have been annotated.
+
+	  If unsure, say N here.
+
 endif # OF
diff --git a/drivers/of/Makefile b/drivers/of/Makefile
index 156c072..05ced0d 100644
--- a/drivers/of/Makefile
+++ b/drivers/of/Makefile
@@ -14,5 +14,6 @@ obj-$(CONFIG_OF_MTD)	+= of_mtd.o
 obj-$(CONFIG_OF_RESERVED_MEM) += of_reserved_mem.o
 obj-$(CONFIG_OF_RESOLVE)  += resolver.o
 obj-$(CONFIG_OF_OVERLAY) += overlay.o
+obj-$(CONFIG_OF_DEPENDENCIES)	+= of_dependencies.o
 
 obj-$(CONFIG_OF_UNITTEST) += unittest-data/
diff --git a/drivers/of/of_dependencies.c b/drivers/of/of_dependencies.c
new file mode 100644
index 0000000..64ed049
--- /dev/null
+++ b/drivers/of/of_dependencies.c
@@ -0,0 +1,410 @@
+/*
+ * Code for building a deterministic initialization order based on dependencies
+ * defined in the device tree.
+ *
+ * Copyright (C) 2014 Alexander Holler <holler@ahsoftware.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <linux/of_dependencies.h>
+
+#define MAX_DT_NODES 1000 /* maximum number of vertices */
+#define MAX_EDGES (MAX_DT_NODES*2) /* maximum number of edges (dependencies) */
+
+struct edgenode {
+	uint32_t y; /* phandle */
+	struct edgenode *next; /* next edge in list */
+};
+
+/*
+ * Vertex numbers do correspond to phandle numbers. That means the graph
+ * does contain as much vertices as the maximum of all phandles.
+ * Or in other words, we assume that for all phandles in the device tree
+ * 0 < phandle < MAX_DT_NODES+1 is true.
+ */
+struct dep_graph {
+	struct edgenode edge_slots[MAX_EDGES]; /* used to avoid kmalloc */
+	struct edgenode *edges[MAX_DT_NODES+1]; /* adjacency info */
+	unsigned nvertices; /* number of vertices in graph */
+	unsigned nedges; /* number of edges in graph */
+	bool processed[MAX_DT_NODES+1]; /* which vertices have been processed */
+	bool include_node[MAX_DT_NODES+1]; /* which nodes to consider */
+	bool discovered[MAX_DT_NODES+1]; /* which vertices have been found */
+	bool finished; /* if true, cut off search immediately */
+};
+static struct dep_graph graph __initdata;
+
+struct init_order {
+	uint32_t max_phandle; /* the max used phandle */
+	uint32_t old_max_phandle; /* used to keep track of added phandles */
+	struct device_node *order[MAX_DT_NODES+1];
+	unsigned count;
+	uint32_t ph_root; /* the phandle of the root */
+};
+static struct init_order order __initdata;
+
+/* Copied from drivers/of/base.c (because it's lockless). */
+static struct property * __init __of_find_property(const struct device_node *np,
+					   const char *name, int *lenp)
+{
+	struct property *pp;
+
+	if (!np)
+		return NULL;
+
+	for (pp = np->properties; pp; pp = pp->next) {
+		if (of_prop_cmp(pp->name, name) == 0) {
+			if (lenp)
+				*lenp = pp->length;
+			break;
+		}
+	}
+
+	return pp;
+}
+
+/* Copied from drivers/of/base.c (because it's lockless). */
+static const void * __init __of_get_property(const struct device_node *np,
+				     const char *name, int *lenp)
+{
+	struct property *pp = __of_find_property(np, name, lenp);
+
+	return pp ? pp->value : NULL;
+}
+
+/* Copied from drivers/of/base.c (because it's lockless). */
+static int __init __of_device_is_available(const struct device_node *device)
+{
+	const char *status;
+	int statlen;
+
+	if (!device)
+		return 0;
+
+	status = __of_get_property(device, "status", &statlen);
+	if (status == NULL)
+		return 1;
+
+	if (statlen > 0) {
+		if (!strcmp(status, "okay") || !strcmp(status, "ok"))
+			return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * x is a dependant of y or in other words
+ * y will be initialized before x.
+ */
+static int __init insert_edge(uint32_t x, uint32_t y)
+{
+	struct edgenode *p; /* temporary pointer */
+
+	if (unlikely(x > MAX_DT_NODES || y > MAX_DT_NODES)) {
+		pr_err("Node found with phandle 0x%x > MAX_DT_NODES (%d)!\n",
+			x > MAX_DT_NODES ? x : y, MAX_DT_NODES);
+		return -EINVAL;
+	}
+	if (unlikely(!x || !y))
+		return 0;
+	if (unlikely(graph.nedges >= MAX_EDGES)) {
+		pr_err("Maximum number of edges (%d) reached!\n", MAX_EDGES);
+		return -EINVAL;
+	}
+	p = &graph.edge_slots[graph.nedges++];
+	graph.include_node[x] = 1;
+	graph.include_node[y] = 1;
+	p->y = y;
+	p->next = graph.edges[x];
+	graph.edges[x] = p; /* insert at head of list */
+
+	graph.nvertices = (x > graph.nvertices) ? x : graph.nvertices;
+	graph.nvertices = (y > graph.nvertices) ? y : graph.nvertices;
+	return 0;
+}
+
+static void __init print_node_name(uint32_t v)
+{
+	struct device_node *node;
+
+	node = of_find_node_by_phandle(v);
+	if (!node) {
+		pr_cont("Node for phandle 0x%x not found", v);
+		return;
+	}
+	if (node->name)
+		pr_cont("%s", node->name);
+	if (node->full_name)
+		pr_cont(" (%s)", node->full_name);
+	of_node_put(node);
+}
+
+/*
+ * I would prefer to use the BGL (Boost Graph Library), but as I can't use it
+ * here (for obvious reasons), the next four functions below are based on
+ * code of Steven Skiena's book 'The Algorithm Design Manual'.
+ */
+
+static void __init process_edge(uint32_t x, uint32_t y)
+{
+	if (unlikely(graph.discovered[y] && !graph.processed[y])) {
+		pr_err("Cycle found 0x%x ", x);
+		print_node_name(x);
+		pr_cont(" <-> 0x%x ", y);
+		print_node_name(y);
+		pr_cont("!\n");
+		graph.finished = 1;
+	}
+}
+
+static void __init process_vertex_late(uint32_t v)
+{
+	struct device_node *node;
+
+	node = of_find_node_by_phandle(v);
+	if (!node) {
+		pr_err("No node for phandle 0x%x not found", v);
+		return;
+	}
+	order.order[order.count++] = node;
+}
+
+static void __init depth_first_search(uint32_t v)
+{
+	struct edgenode *p;
+	uint32_t y; /* successor vertex */
+
+	if (graph.finished)
+		return;
+	graph.discovered[v] = 1;
+	p = graph.edges[v];
+	while (p) {
+		y = p->y;
+		if (!graph.discovered[y]) {
+			process_edge(v, y);
+			depth_first_search(y);
+		} else
+			process_edge(v, y);
+		if (graph.finished)
+			return;
+		p = p->next;
+	}
+	process_vertex_late(v);
+	graph.processed[v] = 1;
+}
+
+static void __init topological_sort(void)
+{
+	unsigned i;
+
+	for (i = 1; i <= graph.nvertices; ++i)
+		if (!graph.discovered[i] && graph.include_node[i])
+			depth_first_search(i);
+}
+
+static int __init add_dep_list(struct device_node *node)
+{
+	const __be32 *list, *list_end;
+	uint32_t ph;
+	int size;
+	int rc = 0;
+	struct device_node *dep;
+
+	list = __of_get_property(node, "dependencies", &size);
+	if (!list || !size || size%sizeof(*list))
+		return 0;
+	list_end = list + size / sizeof(*list);
+	while (list < list_end) {
+		ph = be32_to_cpup(list++);
+		if (unlikely(!ph)) {
+			/* Should never happen */
+			if (node->name)
+				pr_warn("phandle == 0 for %s\n", node->name);
+			continue;
+		}
+		dep = of_find_node_by_phandle(ph);
+		if (unlikely(!dep)) {
+			pr_err("No DT node for dependency with phandle 0x%x found\n",
+				ph);
+			continue;
+		}
+		rc = insert_edge(node->phandle, ph);
+		if (rc)
+			break;
+	}
+
+	return rc;
+}
+
+static int __init add_deps(struct device_node *parent, struct device_node *node)
+{
+	struct device_node *child;
+	int rc = 0;
+
+	if (!__of_device_is_available(node))
+		return 0;
+	if (__of_get_property(node, "compatible", NULL)) {
+		if (!parent->phandle) {
+			if (__of_get_property(parent, "compatible", NULL))
+				parent->phandle = 1 + order.max_phandle++;
+		}
+		if (!node->phandle)
+			node->phandle = 1 + order.max_phandle++;
+		rc = insert_edge(node->phandle, parent->phandle);
+		if (rc)
+			return rc;
+		rc = add_dep_list(node);
+		if (unlikely(rc))
+			return rc;
+		parent = node; /* change the parent only if node is a driver */
+	}
+	for_each_child_of_node(node, child) {
+		rc = add_deps(parent, child);
+		if (unlikely(rc))
+			break;
+	}
+
+	return rc;
+}
+
+static void __init calc_max_phandle(void)
+{
+	struct device_node *np;
+	uint32_t t = 0;
+
+	for_each_of_allnodes(np)
+		if (np->phandle > t)
+			t = np->phandle;
+	order.max_phandle = t;
+}
+
+static bool __init all_compatibles_same(struct device_node *node1,
+					struct device_node *node2)
+{
+	const char *cp1;
+	const char *cp2;
+	unsigned count1 = 0;
+	unsigned count2 = 0;
+	struct property *prop1;
+	struct property *prop2;
+
+	prop1 = __of_find_property(node1, "compatible", NULL);
+	prop2 = __of_find_property(node2, "compatible", NULL);
+	for (cp1 = of_prop_next_string(prop1, NULL); cp1;
+					cp1 = of_prop_next_string(prop1, cp1)) {
+		++count1;
+		for (cp2 = of_prop_next_string(prop2, NULL); cp2;
+					cp2 = of_prop_next_string(prop2, cp2))
+			if (!strcmp(cp1, cp2))
+				break;
+		if (!cp2)
+			return 0;
+	}
+	for (cp2 = of_prop_next_string(prop2, NULL); cp2;
+					cp2 = of_prop_next_string(prop2, cp2))
+		++count2;
+	if (count1 == count2)
+		return 1;
+	return 0;
+}
+
+/*
+ * The order is based on devices but we are calling drivers.
+ * Therefor the order contains some drivers more than once.
+ * Remove the duplicates.
+ */
+static void __init of_init_remove_duplicates(void)
+{
+	unsigned i, j;
+
+	for (i = 1; i < order.count; ++i)
+		for (j = 0; j < i; ++j) {
+			if (all_compatibles_same(order.order[j],
+							order.order[i])) {
+				--order.count;
+				memmove(&order.order[i], &order.order[i+1],
+					(order.count - i) *
+						sizeof(order.order[0]));
+				--i;
+				break;
+			}
+		}
+}
+
+static int __init of_init_build_order(void)
+{
+	int rc = 0;
+	struct device_node *child;
+	struct device_node *root =  of_find_node_by_path("/");
+
+	if (unlikely(!root))
+		return -EINVAL;
+
+	calc_max_phandle();
+	order.old_max_phandle = order.max_phandle;
+
+	for_each_child_of_node(root, child) {
+		rc = add_deps(root, child);
+		if (unlikely(rc))
+			break;
+	}
+
+	order.ph_root = root->phandle;
+
+	of_node_put(root);
+	topological_sort();
+
+	if (graph.finished)
+		return -EINVAL; /* cycle found */
+
+	of_init_remove_duplicates();
+
+	return rc;
+}
+
+static void __init of_init_free_order(void)
+{
+	unsigned i;
+
+	for (i = 0; i < order.count; ++i)
+		of_node_put(order.order[i]);
+	order.count = 0;
+	/* remove_new_phandles(); */
+}
+
+static void __init init_if_matched(struct device_node *node)
+{
+	struct _annotated_initcall *ac;
+
+	ac = __annotated_initcall_start;
+	for (; ac < __annotated_initcall_end; ++ac) {
+		if (ac->initcall && ac->driver->of_match_table)
+			if (of_match_node(ac->driver->of_match_table,
+					 node)) {
+				do_one_initcall(*ac->initcall);
+				ac->initcall = 0;
+			}
+	}
+}
+
+void __init of_init_drivers(void)
+{
+	unsigned i;
+	struct _annotated_initcall *ac;
+
+	if (!of_init_build_order()) {
+		for (i = 0; i < order.count; ++i)
+			init_if_matched(order.order[i]);
+		of_init_free_order();
+	}
+	ac = __annotated_initcall_start;
+	for (; ac < __annotated_initcall_end; ++ac) {
+		if (ac->initcall)
+			do_one_initcall(*ac->initcall);
+	}
+}
diff --git a/include/linux/of_dependencies.h b/include/linux/of_dependencies.h
new file mode 100644
index 0000000..1c8c20a
--- /dev/null
+++ b/include/linux/of_dependencies.h
@@ -0,0 +1,20 @@
+#ifndef _LINUX_OF_DEPENDENCIES_H
+#define _LINUX_OF_DEPENDENCIES_H
+/*
+ * Definitions for building a deterministic initialization order based on
+ * dependencies defined in the device tree.
+ *
+ * Copyright (C) 2014 Alexander Holler <holler@ahsoftware.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <linux/of_platform.h>
+
+/* Calls annotated initcalls in an ordered way based on dependencies. */
+extern void of_init_drivers(void);
+
+#endif	/* _LINUX_OF_DEPENDENCIES_H */
diff --git a/init/main.c b/init/main.c
index 5650655..532b330 100644
--- a/init/main.c
+++ b/init/main.c
@@ -81,6 +81,7 @@
 #include <linux/integrity.h>
 #include <linux/proc_ns.h>
 #include <linux/io.h>
+#include <linux/of_dependencies.h>
 
 #include <asm/io.h>
 #include <asm/bugs.h>
@@ -863,8 +864,16 @@ static void __init do_initcalls(void)
 {
 	int level;
 
-	for (level = 0; level < ARRAY_SIZE(initcall_levels) - 1; level++)
+	for (level = 0; level < ARRAY_SIZE(initcall_levels) - 3; level++)
 		do_initcall_level(level);
+#ifdef CONFIG_OF_DEPENDENCIES
+	/* call annotated drivers (sorted) */
+	of_init_drivers();
+#endif
+	/* call normal and not annoted drivers (not sorted) */
+	do_initcall_level(level++);
+	/* call late drivers */
+	do_initcall_level(level);
 }
 
 /*
-- 
2.1.0

[PATCH 07/16] deps: add debug configuration options

[Alexander Holler]

Add some debug options to print annotated initcalls, the ordered list of
annotated initcalls and to print a message right before an annotated
initcall is called.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/of/Kconfig           | 18 ++++++++++++++
 drivers/of/of_dependencies.c | 57 ++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 73 insertions(+), 2 deletions(-)

diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
index 9bf6c73..26c4b1a 100644
--- a/drivers/of/Kconfig
+++ b/drivers/of/Kconfig
@@ -114,4 +114,22 @@ config OF_DEPENDENCIES
 
 	  If unsure, say N here.
 
+config OF_DEPENDENCIES_PRINT_INIT_ORDER
+	bool "Print dependency based initialization order"
+	depends on OF_DEPENDENCIES
+	help
+	  Used for debugging purposes.
+
+config OF_DEPENDENCIES_PRINT_ANNOTATED_INITCALLS
+	bool "Print names of annotated drivers"
+	depends on OF_DEPENDENCIES
+	help
+	  Used for debugging purposes.
+
+config OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
+	bool "Show when annotated initcalls are actually called"
+	depends on OF_DEPENDENCIES
+	help
+	  Used for debugging purposes.
+
 endif # OF
diff --git a/drivers/of/of_dependencies.c b/drivers/of/of_dependencies.c
index 64ed049..06435d5 100644
--- a/drivers/of/of_dependencies.c
+++ b/drivers/of/of_dependencies.c
@@ -336,6 +336,41 @@ static void __init of_init_remove_duplicates(void)
 		}
 }
 
+#ifdef CONFIG_OF_DEPENDENCIES_PRINT_INIT_ORDER
+static void __init of_init_print_order(void)
+{
+	unsigned i;
+	struct property *prop;
+	const char *cp;
+
+	pr_info("Initialization order:\n");
+	for (i = 0; i < order.count; ++i) {
+		pr_info("init %u 0x%x", i, order.order[i]->phandle);
+		if (order.order[i]->name)
+			pr_cont(" %s", order.order[i]->name);
+		if (order.order[i]->full_name)
+			pr_cont(" (%s)", order.order[i]->full_name);
+		prop = __of_find_property(order.order[i], "compatible", NULL);
+		for (cp = of_prop_next_string(prop, NULL); cp;
+		     cp = of_prop_next_string(prop, cp))
+			pr_cont(" %s", cp);
+	}
+}
+#endif
+
+#ifdef CONFIG_OF_DEPENDENCIES_PRINT_ANNOTATED_INITCALLS
+static void __init of_init_print_annotated(void)
+{
+	struct _annotated_initcall *ac;
+
+	pr_info("Annotated drivers:\n");
+	ac = __annotated_initcall_start;
+	for (; ac < __annotated_initcall_end; ++ac)
+		pr_info("Driver '%s' (%s)\n", ac->driver->name,
+				ac->driver->of_match_table->compatible);
+}
+#endif
+
 static int __init of_init_build_order(void)
 {
 	int rc = 0;
@@ -363,7 +398,12 @@ static int __init of_init_build_order(void)
 		return -EINVAL; /* cycle found */
 
 	of_init_remove_duplicates();
-
+#ifdef CONFIG_OF_DEPENDENCIES_PRINT_INIT_ORDER
+	of_init_print_order();
+#endif
+#ifdef CONFIG_OF_DEPENDENCIES_PRINT_ANNOTATED_INITCALLS
+	of_init_print_annotated();
+#endif
 	return rc;
 }
 
@@ -386,6 +426,12 @@ static void __init init_if_matched(struct device_node *node)
 		if (ac->initcall && ac->driver->of_match_table)
 			if (of_match_node(ac->driver->of_match_table,
 					 node)) {
+#ifdef CONFIG_OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
+				pr_info("Calling (ordered) initcall for driver %s (%s)\n",
+					ac->driver->name,
+					ac->driver->of_match_table ?
+						ac->driver->of_match_table->compatible : "");
+#endif
 				do_one_initcall(*ac->initcall);
 				ac->initcall = 0;
 			}
@@ -404,7 +450,14 @@ void __init of_init_drivers(void)
 	}
 	ac = __annotated_initcall_start;
 	for (; ac < __annotated_initcall_end; ++ac) {
-		if (ac->initcall)
+		if (ac->initcall) {
+#ifdef CONFIG_OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
+			pr_info("Calling (unordered) initcall for driver %s (%s)\n",
+				ac->driver->name,
+				ac->driver->of_match_table ?
+					ac->driver->of_match_table->compatible : "");
+#endif
 			do_one_initcall(*ac->initcall);
+		}
 	}
 }
-- 
2.1.0

[PATCH 08/16] deps: dts: kirkwood: dockstar: add dependency ehci -> usb power regulator

[Alexander Holler]

This serves as an example how easy it is to fix an initialization order
if the order depends on the DT. No source code changes will be necessary.

If you look at the dependency graph for the dockstar, you will see that
there is no dependency between ehci and the usb power regulator. This
ends up with the fact that the regulator will be initialized after ehci.

Fix this by adding one dependency to the .dts.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/boot/dts/kirkwood-dockstar.dts | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/arm/boot/dts/kirkwood-dockstar.dts b/arch/arm/boot/dts/kirkwood-dockstar.dts
index 8497363..426d8840 100644
--- a/arch/arm/boot/dts/kirkwood-dockstar.dts
+++ b/arch/arm/boot/dts/kirkwood-dockstar.dts
@@ -107,3 +107,7 @@
 		phy-handle = <&ethphy0>;
 	};
 };
+
+&usb0 {
+	dependencies = <&usb_power>;
+};
-- 
2.1.0

[PATCH 09/16] deps: dts: imx6q: make some remote-endpoints non-dependencies

[Alexander Holler]

This is necessary to remove dependency cycles introduced by
'remote-endpoints'.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/boot/dts/imx6q.dtsi   | 2 ++
 arch/arm/boot/dts/imx6qdl.dtsi | 4 ++++
 2 files changed, 6 insertions(+)

diff --git a/arch/arm/boot/dts/imx6q.dtsi b/arch/arm/boot/dts/imx6q.dtsi
index 399103b..8db7f25 100644
--- a/arch/arm/boot/dts/imx6q.dtsi
+++ b/arch/arm/boot/dts/imx6q.dtsi
@@ -184,6 +184,7 @@
 
 				ipu2_di0_hdmi: endpoint@1 {
 					remote-endpoint = <&hdmi_mux_2>;
+					no-dependencies = <&hdmi_mux_2>;
 				};
 
 				ipu2_di0_mipi: endpoint@2 {
@@ -205,6 +206,7 @@
 
 				ipu2_di1_hdmi: endpoint@1 {
 					remote-endpoint = <&hdmi_mux_3>;
+					no-dependencies = <&hdmi_mux_3>;
 				};
 
 				ipu2_di1_mipi: endpoint@2 {
diff --git a/arch/arm/boot/dts/imx6qdl.dtsi b/arch/arm/boot/dts/imx6qdl.dtsi
index b57033e..db3d0d0 100644
--- a/arch/arm/boot/dts/imx6qdl.dtsi
+++ b/arch/arm/boot/dts/imx6qdl.dtsi
@@ -1150,10 +1150,12 @@
 
 				ipu1_di0_hdmi: endpoint@1 {
 					remote-endpoint = <&hdmi_mux_0>;
+					no-dependencies = <&hdmi_mux_0>;
 				};
 
 				ipu1_di0_mipi: endpoint@2 {
 					remote-endpoint = <&mipi_mux_0>;
+					no-dependencies = <&mipi_mux_0>;
 				};
 
 				ipu1_di0_lvds0: endpoint@3 {
@@ -1175,10 +1177,12 @@
 
 				ipu1_di1_hdmi: endpoint@1 {
 					remote-endpoint = <&hdmi_mux_1>;
+					no-dependencies = <&hdmi_mux_1>;
 				};
 
 				ipu1_di1_mipi: endpoint@2 {
 					remote-endpoint = <&mipi_mux_1>;
+					no-dependencies = <&mipi_mux_1>;
 				};
 
 				ipu1_di1_lvds0: endpoint@3 {
-- 
2.1.0

[PATCH 10/16] deps: dts: omap: beagle: make some remote-endpoints non-dependencies

[Alexander Holler]

This is necessary to remove dependency cycles introduced by
'remote-endpoints'.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/boot/dts/omap3-beagle.dts | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/arch/arm/boot/dts/omap3-beagle.dts b/arch/arm/boot/dts/omap3-beagle.dts
index a547411..78ba39e 100644
--- a/arch/arm/boot/dts/omap3-beagle.dts
+++ b/arch/arm/boot/dts/omap3-beagle.dts
@@ -101,6 +101,7 @@
 
 				tfp410_in: endpoint@0 {
 					remote-endpoint = <&dpi_out>;
+					no-dependencies = <&dpi_out>;
 				};
 			};
 
@@ -109,6 +110,7 @@
 
 				tfp410_out: endpoint@0 {
 					remote-endpoint = <&dvi_connector_in>;
+					no-dependencies = <&dvi_connector_in>;
 				};
 			};
 		};
@@ -150,6 +152,7 @@
 			etb_in: endpoint {
 				slave-mode;
 				remote-endpoint = <&etm_out>;
+				no-dependencies = <&etm_out>;
 			};
 		};
 	};
@@ -373,6 +376,7 @@
 	port {
 		venc_out: endpoint {
 			remote-endpoint = <&tv_connector_in>;
+			no-dependencies = <&tv_connector_in>;
 			ti,channels = <2>;
 		};
 	};
-- 
2.1.0

[PATCH 11/16] deps: WIP: generic: annotate some initcalls

[Alexander Holler]

WIP means Work In Progress.

Change some generic drivers to offer annotated initcalls.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/input/keyboard/gpio_keys.c | 2 +-
 drivers/misc/sram.c                | 2 +-
 drivers/regulator/fixed.c          | 3 ++-
 drivers/usb/phy/phy-generic.c      | 2 +-
 4 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/drivers/input/keyboard/gpio_keys.c b/drivers/input/keyboard/gpio_keys.c
index ddf4045..319bcf7 100644
--- a/drivers/input/keyboard/gpio_keys.c
+++ b/drivers/input/keyboard/gpio_keys.c
@@ -855,7 +855,7 @@ static void __exit gpio_keys_exit(void)
 	platform_driver_unregister(&gpio_keys_device_driver);
 }
 
-late_initcall(gpio_keys_init);
+annotated_initcall(late, gpio_keys_init, gpio_keys_device_driver.driver);
 module_exit(gpio_keys_exit);
 
 MODULE_LICENSE("GPL");
diff --git a/drivers/misc/sram.c b/drivers/misc/sram.c
index 15c33cc..eb662bd 100644
--- a/drivers/misc/sram.c
+++ b/drivers/misc/sram.c
@@ -243,4 +243,4 @@ static int __init sram_init(void)
 	return platform_driver_register(&sram_driver);
 }
 
-postcore_initcall(sram_init);
+annotated_initcall(postcore, sram_init, sram_driver.driver);
diff --git a/drivers/regulator/fixed.c b/drivers/regulator/fixed.c
index ff62d69..ec35d10 100644
--- a/drivers/regulator/fixed.c
+++ b/drivers/regulator/fixed.c
@@ -221,7 +221,8 @@ static int __init regulator_fixed_voltage_init(void)
 {
 	return platform_driver_register(&regulator_fixed_voltage_driver);
 }
-subsys_initcall(regulator_fixed_voltage_init);
+annotated_initcall(subsys, regulator_fixed_voltage_init,
+					regulator_fixed_voltage_driver.driver);
 
 static void __exit regulator_fixed_voltage_exit(void)
 {
diff --git a/drivers/usb/phy/phy-generic.c b/drivers/usb/phy/phy-generic.c
index deee68e..baf95d0 100644
--- a/drivers/usb/phy/phy-generic.c
+++ b/drivers/usb/phy/phy-generic.c
@@ -360,7 +360,7 @@ static int __init usb_phy_generic_init(void)
 {
 	return platform_driver_register(&usb_phy_generic_driver);
 }
-subsys_initcall(usb_phy_generic_init);
+annotated_initcall(subsys, usb_phy_generic_init, usb_phy_generic_driver.driver);
 
 static void __exit usb_phy_generic_exit(void)
 {
-- 
2.1.0

[PATCH 12/16] deps: WIP: imx: annotate some initcalls

[Alexander Holler]

WIP means Work In Progress.

Change some imx drivers to offer annotated initcalls.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/mach-imx/gpc.c                   | 2 +-
 arch/arm/mach-imx/mmdc.c                  | 2 +-
 drivers/dma/mxs-dma.c                     | 2 +-
 drivers/gpio/gpio-mxc.c                   | 2 +-
 drivers/i2c/busses/i2c-imx.c              | 2 +-
 drivers/pinctrl/freescale/pinctrl-imx6q.c | 2 +-
 drivers/power/reset/imx-snvs-poweroff.c   | 2 +-
 drivers/regulator/anatop-regulator.c      | 3 ++-
 drivers/tty/serial/imx.c                  | 2 +-
 drivers/usb/phy/phy-mxs-usb.c             | 2 +-
 sound/soc/fsl/imx-audmux.c                | 2 +-
 11 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/arch/arm/mach-imx/gpc.c b/arch/arm/mach-imx/gpc.c
index 8c4467f..3802614 100644
--- a/arch/arm/mach-imx/gpc.c
+++ b/arch/arm/mach-imx/gpc.c
@@ -468,4 +468,4 @@ static int __init imx_pgc_init(void)
 {
 	return platform_driver_register(&imx_gpc_driver);
 }
-subsys_initcall(imx_pgc_init);
+annotated_initcall(subsys, imx_pgc_init, imx_gpc_driver.driver);
diff --git a/arch/arm/mach-imx/mmdc.c b/arch/arm/mach-imx/mmdc.c
index db9621c..cf84c03 100644
--- a/arch/arm/mach-imx/mmdc.c
+++ b/arch/arm/mach-imx/mmdc.c
@@ -87,4 +87,4 @@ static int __init imx_mmdc_init(void)
 {
 	return platform_driver_register(&imx_mmdc_driver);
 }
-postcore_initcall(imx_mmdc_init);
+annotated_initcall(postcore, imx_mmdc_init, imx_mmdc_driver.driver);
diff --git a/drivers/dma/mxs-dma.c b/drivers/dma/mxs-dma.c
index 60de352..5bfa232 100644
--- a/drivers/dma/mxs-dma.c
+++ b/drivers/dma/mxs-dma.c
@@ -884,4 +884,4 @@ static int __init mxs_dma_module_init(void)
 {
 	return platform_driver_probe(&mxs_dma_driver, mxs_dma_probe);
 }
-subsys_initcall(mxs_dma_module_init);
+annotated_initcall(subsys, mxs_dma_module_init, mxs_dma_driver.driver);
diff --git a/drivers/gpio/gpio-mxc.c b/drivers/gpio/gpio-mxc.c
index ec1eb1b..0a22a62 100644
--- a/drivers/gpio/gpio-mxc.c
+++ b/drivers/gpio/gpio-mxc.c
@@ -506,7 +506,7 @@ static int __init gpio_mxc_init(void)
 {
 	return platform_driver_register(&mxc_gpio_driver);
 }
-postcore_initcall(gpio_mxc_init);
+annotated_initcall(postcore, gpio_mxc_init, mxc_gpio_driver.driver);
 
 MODULE_AUTHOR("Freescale Semiconductor, "
 	      "Daniel Mack <danielncaiaq.de>, "
diff --git a/drivers/i2c/busses/i2c-imx.c b/drivers/i2c/busses/i2c-imx.c
index 785aa67..c20d03c 100644
--- a/drivers/i2c/busses/i2c-imx.c
+++ b/drivers/i2c/busses/i2c-imx.c
@@ -1110,7 +1110,7 @@ static int __init i2c_adap_imx_init(void)
 {
 	return platform_driver_register(&i2c_imx_driver);
 }
-subsys_initcall(i2c_adap_imx_init);
+annotated_initcall(subsys, i2c_adap_imx_init, i2c_imx_driver.driver);
 
 static void __exit i2c_adap_imx_exit(void)
 {
diff --git a/drivers/pinctrl/freescale/pinctrl-imx6q.c b/drivers/pinctrl/freescale/pinctrl-imx6q.c
index 4d1fcb8..77a1ffd 100644
--- a/drivers/pinctrl/freescale/pinctrl-imx6q.c
+++ b/drivers/pinctrl/freescale/pinctrl-imx6q.c
@@ -489,7 +489,7 @@ static int __init imx6q_pinctrl_init(void)
 {
 	return platform_driver_register(&imx6q_pinctrl_driver);
 }
-arch_initcall(imx6q_pinctrl_init);
+annotated_initcall(arch, imx6q_pinctrl_init, imx6q_pinctrl_driver.driver);
 
 static void __exit imx6q_pinctrl_exit(void)
 {
diff --git a/drivers/power/reset/imx-snvs-poweroff.c b/drivers/power/reset/imx-snvs-poweroff.c
index ad6ce50..57a06dc 100644
--- a/drivers/power/reset/imx-snvs-poweroff.c
+++ b/drivers/power/reset/imx-snvs-poweroff.c
@@ -63,4 +63,4 @@ static int __init imx_poweroff_init(void)
 {
 	return platform_driver_register(&imx_poweroff_driver);
 }
-device_initcall(imx_poweroff_init);
+annotated_initcall(device, imx_poweroff_init, imx_poweroff_driver.driver);
diff --git a/drivers/regulator/anatop-regulator.c b/drivers/regulator/anatop-regulator.c
index 738adfa..97808da 100644
--- a/drivers/regulator/anatop-regulator.c
+++ b/drivers/regulator/anatop-regulator.c
@@ -331,7 +331,8 @@ static int __init anatop_regulator_init(void)
 {
 	return platform_driver_register(&anatop_regulator_driver);
 }
-postcore_initcall(anatop_regulator_init);
+annotated_initcall(postcore, anatop_regulator_init,
+					anatop_regulator_driver.driver);
 
 static void __exit anatop_regulator_exit(void)
 {
diff --git a/drivers/tty/serial/imx.c b/drivers/tty/serial/imx.c
index 54fdc78..c79e19b 100644
--- a/drivers/tty/serial/imx.c
+++ b/drivers/tty/serial/imx.c
@@ -2024,7 +2024,7 @@ static void __exit imx_serial_exit(void)
 	uart_unregister_driver(&imx_reg);
 }
 
-module_init(imx_serial_init);
+annotated_module_init(imx_serial_init, serial_imx_driver.driver);
 module_exit(imx_serial_exit);
 
 MODULE_AUTHOR("Sascha Hauer");
diff --git a/drivers/usb/phy/phy-mxs-usb.c b/drivers/usb/phy/phy-mxs-usb.c
index 3fcc048..dd2768d 100644
--- a/drivers/usb/phy/phy-mxs-usb.c
+++ b/drivers/usb/phy/phy-mxs-usb.c
@@ -577,7 +577,7 @@ static int __init mxs_phy_module_init(void)
 {
 	return platform_driver_register(&mxs_phy_driver);
 }
-postcore_initcall(mxs_phy_module_init);
+annotated_initcall(postcore, mxs_phy_module_init, mxs_phy_driver.driver);
 
 static void __exit mxs_phy_module_exit(void)
 {
diff --git a/sound/soc/fsl/imx-audmux.c b/sound/soc/fsl/imx-audmux.c
index fc57da3..19fd729 100644
--- a/sound/soc/fsl/imx-audmux.c
+++ b/sound/soc/fsl/imx-audmux.c
@@ -364,7 +364,7 @@ static int __init imx_audmux_init(void)
 {
 	return platform_driver_register(&imx_audmux_driver);
 }
-subsys_initcall(imx_audmux_init);
+annotated_initcall(subsys, imx_audmux_init, imx_audmux_driver.driver);
 
 static void __exit imx_audmux_exit(void)
 {
-- 
2.1.0

[PATCH 13/16] deps: WIP: omap: annotate some initcalls

[Alexander Holler]

WIP means Work In Progress.

Change some omap drivers to offer annotated initcalls.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 arch/arm/common/edma.c                 | 2 +-
 drivers/bus/omap_l3_smx.c              | 2 +-
 drivers/dma/omap-dma.c                 | 2 +-
 drivers/gpio/gpio-twl4030.c            | 2 +-
 drivers/gpu/drm/tilcdc/tilcdc_drv.c    | 2 +-
 drivers/i2c/busses/i2c-omap.c          | 2 +-
 drivers/iommu/omap-iommu.c             | 2 +-
 drivers/mailbox/omap-mailbox.c         | 2 +-
 drivers/memory/omap-gpmc.c             | 2 +-
 drivers/mfd/omap-usb-host.c            | 2 +-
 drivers/mfd/omap-usb-tll.c             | 2 +-
 drivers/mfd/tps65217.c                 | 2 +-
 drivers/net/ethernet/ti/cpsw.c         | 2 +-
 drivers/net/ethernet/ti/davinci_mdio.c | 2 +-
 drivers/phy/phy-twl4030-usb.c          | 2 +-
 drivers/regulator/twl-regulator.c      | 2 +-
 drivers/tty/serial/omap-serial.c       | 2 +-
 drivers/usb/host/ehci-omap.c           | 2 +-
 drivers/usb/host/ohci-omap3.c          | 2 +-
 drivers/usb/musb/omap2430.c            | 2 +-
 20 files changed, 20 insertions(+), 20 deletions(-)

diff --git a/arch/arm/common/edma.c b/arch/arm/common/edma.c
index 873dbfc..29f363c 100644
--- a/arch/arm/common/edma.c
+++ b/arch/arm/common/edma.c
@@ -1872,5 +1872,5 @@ static int __init edma_init(void)
 {
 	return platform_driver_probe(&edma_driver, edma_probe);
 }
-arch_initcall(edma_init);
+annotated_initcall(arch, edma_init, edma_driver.driver);
 
diff --git a/drivers/bus/omap_l3_smx.c b/drivers/bus/omap_l3_smx.c
index 360a5c0..e2172b8 100644
--- a/drivers/bus/omap_l3_smx.c
+++ b/drivers/bus/omap_l3_smx.c
@@ -302,7 +302,7 @@ static int __init omap3_l3_init(void)
 {
 	return platform_driver_register(&omap3_l3_driver);
 }
-postcore_initcall_sync(omap3_l3_init);
+annotated_initcall_sync(postcore, omap3_l3_init, omap3_l3_driver.driver);
 
 static void __exit omap3_l3_exit(void)
 {
diff --git a/drivers/dma/omap-dma.c b/drivers/dma/omap-dma.c
index 249445c..0866ae9 100644
--- a/drivers/dma/omap-dma.c
+++ b/drivers/dma/omap-dma.c
@@ -1285,7 +1285,7 @@ static int omap_dma_init(void)
 {
 	return platform_driver_register(&omap_dma_driver);
 }
-subsys_initcall(omap_dma_init);
+annotated_initcall(subsys, omap_dma_init, omap_dma_driver.driver);
 
 static void __exit omap_dma_exit(void)
 {
diff --git a/drivers/gpio/gpio-twl4030.c b/drivers/gpio/gpio-twl4030.c
index 9e1dbb9..60c0d1a 100644
--- a/drivers/gpio/gpio-twl4030.c
+++ b/drivers/gpio/gpio-twl4030.c
@@ -615,7 +615,7 @@ static int __init gpio_twl4030_init(void)
 {
 	return platform_driver_register(&gpio_twl4030_driver);
 }
-subsys_initcall(gpio_twl4030_init);
+annotated_initcall(subsys, gpio_twl4030_init, gpio_twl4030_driver.driver);
 
 static void __exit gpio_twl4030_exit(void)
 {
diff --git a/drivers/gpu/drm/tilcdc/tilcdc_drv.c b/drivers/gpu/drm/tilcdc/tilcdc_drv.c
index 0f283a3..8c50f23 100644
--- a/drivers/gpu/drm/tilcdc/tilcdc_drv.c
+++ b/drivers/gpu/drm/tilcdc/tilcdc_drv.c
@@ -715,7 +715,7 @@ static void __exit tilcdc_drm_fini(void)
 	tilcdc_tfp410_fini();
 }
 
-module_init(tilcdc_drm_init);
+annotated_module_init(tilcdc_drm_init, tilcdc_platform_driver.driver);
 module_exit(tilcdc_drm_fini);
 
 MODULE_AUTHOR("Rob Clark <robdclark@gmail.com");
diff --git a/drivers/i2c/busses/i2c-omap.c b/drivers/i2c/busses/i2c-omap.c
index fc9bf7f..0a5d63b 100644
--- a/drivers/i2c/busses/i2c-omap.c
+++ b/drivers/i2c/busses/i2c-omap.c
@@ -1541,7 +1541,7 @@ omap_i2c_init_driver(void)
 {
 	return platform_driver_register(&omap_i2c_driver);
 }
-subsys_initcall(omap_i2c_init_driver);
+annotated_initcall(subsys, omap_i2c_init_driver, omap_i2c_driver.driver);
 
 static void __exit omap_i2c_exit_driver(void)
 {
diff --git a/drivers/iommu/omap-iommu.c b/drivers/iommu/omap-iommu.c
index a22c33d..cf2ef44 100644
--- a/drivers/iommu/omap-iommu.c
+++ b/drivers/iommu/omap-iommu.c
@@ -1406,7 +1406,7 @@ static int __init omap_iommu_init(void)
 	return platform_driver_register(&omap_iommu_driver);
 }
 /* must be ready before omap3isp is probed */
-subsys_initcall(omap_iommu_init);
+annotated_initcall(subsys, omap_iommu_init, omap_iommu_driver.driver);
 
 static void __exit omap_iommu_exit(void)
 {
diff --git a/drivers/mailbox/omap-mailbox.c b/drivers/mailbox/omap-mailbox.c
index a3dbfd9..ac12306 100644
--- a/drivers/mailbox/omap-mailbox.c
+++ b/drivers/mailbox/omap-mailbox.c
@@ -883,7 +883,7 @@ static int __init omap_mbox_init(void)
 
 	return platform_driver_register(&omap_mbox_driver);
 }
-subsys_initcall(omap_mbox_init);
+annotated_initcall(subsys, omap_mbox_init, omap_mbox_driver.driver);
 
 static void __exit omap_mbox_exit(void)
 {
diff --git a/drivers/memory/omap-gpmc.c b/drivers/memory/omap-gpmc.c
index 9426276..65b0138 100644
--- a/drivers/memory/omap-gpmc.c
+++ b/drivers/memory/omap-gpmc.c
@@ -2217,7 +2217,7 @@ static __exit void gpmc_exit(void)
 
 }
 
-postcore_initcall(gpmc_init);
+annotated_initcall(postcore, gpmc_init, gpmc_driver.driver);
 module_exit(gpmc_exit);
 
 static irqreturn_t gpmc_handle_irq(int irq, void *dev)
diff --git a/drivers/mfd/omap-usb-host.c b/drivers/mfd/omap-usb-host.c
index 1d924d1..c996f45 100644
--- a/drivers/mfd/omap-usb-host.c
+++ b/drivers/mfd/omap-usb-host.c
@@ -896,7 +896,7 @@ static int __init omap_usbhs_drvinit(void)
  * This usbhs core driver should be initialized after
  * usb tll driver
  */
-fs_initcall_sync(omap_usbhs_drvinit);
+annotated_initcall_sync(fs, omap_usbhs_drvinit, usbhs_omap_driver.driver);
 
 static void __exit omap_usbhs_drvexit(void)
 {
diff --git a/drivers/mfd/omap-usb-tll.c b/drivers/mfd/omap-usb-tll.c
index b7b3e8e..ac5d393 100644
--- a/drivers/mfd/omap-usb-tll.c
+++ b/drivers/mfd/omap-usb-tll.c
@@ -475,7 +475,7 @@ static int __init omap_usbtll_drvinit(void)
  * The usbtll driver should be initialized before
  * the usbhs core driver probe function is called.
  */
-fs_initcall(omap_usbtll_drvinit);
+annotated_initcall(fs, omap_usbtll_drvinit, usbtll_omap_driver.driver);
 
 static void __exit omap_usbtll_drvexit(void)
 {
diff --git a/drivers/mfd/tps65217.c b/drivers/mfd/tps65217.c
index 7d1cfc1..386dd15 100644
--- a/drivers/mfd/tps65217.c
+++ b/drivers/mfd/tps65217.c
@@ -260,7 +260,7 @@ static int __init tps65217_init(void)
 {
 	return i2c_add_driver(&tps65217_driver);
 }
-subsys_initcall(tps65217_init);
+annotated_initcall(subsys, tps65217_init, tps65217_driver.driver);
 
 static void __exit tps65217_exit(void)
 {
diff --git a/drivers/net/ethernet/ti/cpsw.c b/drivers/net/ethernet/ti/cpsw.c
index d155bf2..6b772b5 100644
--- a/drivers/net/ethernet/ti/cpsw.c
+++ b/drivers/net/ethernet/ti/cpsw.c
@@ -2524,7 +2524,7 @@ static int __init cpsw_init(void)
 {
 	return platform_driver_register(&cpsw_driver);
 }
-late_initcall(cpsw_init);
+annotated_initcall(late, cpsw_init, cpsw_driver.driver);
 
 static void __exit cpsw_exit(void)
 {
diff --git a/drivers/net/ethernet/ti/davinci_mdio.c b/drivers/net/ethernet/ti/davinci_mdio.c
index c00084d..32e0269 100644
--- a/drivers/net/ethernet/ti/davinci_mdio.c
+++ b/drivers/net/ethernet/ti/davinci_mdio.c
@@ -493,7 +493,7 @@ static int __init davinci_mdio_init(void)
 {
 	return platform_driver_register(&davinci_mdio_driver);
 }
-device_initcall(davinci_mdio_init);
+annotated_initcall(device, davinci_mdio_init, davinci_mdio_driver.driver);
 
 static void __exit davinci_mdio_exit(void)
 {
diff --git a/drivers/phy/phy-twl4030-usb.c b/drivers/phy/phy-twl4030-usb.c
index 3a707dd..b3bba7a 100644
--- a/drivers/phy/phy-twl4030-usb.c
+++ b/drivers/phy/phy-twl4030-usb.c
@@ -801,7 +801,7 @@ static int __init twl4030_usb_init(void)
 {
 	return platform_driver_register(&twl4030_usb_driver);
 }
-subsys_initcall(twl4030_usb_init);
+annotated_initcall(subsys, twl4030_usb_init, twl4030_usb_driver.driver);
 
 static void __exit twl4030_usb_exit(void)
 {
diff --git a/drivers/regulator/twl-regulator.c b/drivers/regulator/twl-regulator.c
index 955a6fb..356066b 100644
--- a/drivers/regulator/twl-regulator.c
+++ b/drivers/regulator/twl-regulator.c
@@ -1229,7 +1229,7 @@ static int __init twlreg_init(void)
 {
 	return platform_driver_register(&twlreg_driver);
 }
-subsys_initcall(twlreg_init);
+annotated_initcall(subsys, twlreg_init, twlreg_driver.driver);
 
 static void __exit twlreg_exit(void)
 {
diff --git a/drivers/tty/serial/omap-serial.c b/drivers/tty/serial/omap-serial.c
index 7a2172b..b78b4d7 100644
--- a/drivers/tty/serial/omap-serial.c
+++ b/drivers/tty/serial/omap-serial.c
@@ -1889,7 +1889,7 @@ static void __exit serial_omap_exit(void)
 	uart_unregister_driver(&serial_omap_reg);
 }
 
-module_init(serial_omap_init);
+annotated_module_init(serial_omap_init, serial_omap_driver.driver);
 module_exit(serial_omap_exit);
 
 MODULE_DESCRIPTION("OMAP High Speed UART driver");
diff --git a/drivers/usb/host/ehci-omap.c b/drivers/usb/host/ehci-omap.c
index a24720b..1e4076d 100644
--- a/drivers/usb/host/ehci-omap.c
+++ b/drivers/usb/host/ehci-omap.c
@@ -310,7 +310,7 @@ static int __init ehci_omap_init(void)
 	ehci_init_driver(&ehci_omap_hc_driver, &ehci_omap_overrides);
 	return platform_driver_register(&ehci_hcd_omap_driver);
 }
-module_init(ehci_omap_init);
+annotated_module_init(ehci_omap_init, ehci_hcd_omap_driver.driver);
 
 static void __exit ehci_omap_cleanup(void)
 {
diff --git a/drivers/usb/host/ohci-omap3.c b/drivers/usb/host/ohci-omap3.c
index ec15aeb..bcb1a1b 100644
--- a/drivers/usb/host/ohci-omap3.c
+++ b/drivers/usb/host/ohci-omap3.c
@@ -197,7 +197,7 @@ static int __init ohci_omap3_init(void)
 	ohci_init_driver(&ohci_omap3_hc_driver, NULL);
 	return platform_driver_register(&ohci_hcd_omap3_driver);
 }
-module_init(ohci_omap3_init);
+annotated_module_init(ohci_omap3_init, ohci_hcd_omap3_driver.driver);
 
 static void __exit ohci_omap3_cleanup(void)
 {
diff --git a/drivers/usb/musb/omap2430.c b/drivers/usb/musb/omap2430.c
index 70f2b8a..6a13f0b 100644
--- a/drivers/usb/musb/omap2430.c
+++ b/drivers/usb/musb/omap2430.c
@@ -725,7 +725,7 @@ static int __init omap2430_init(void)
 {
 	return platform_driver_register(&omap2430_driver);
 }
-subsys_initcall(omap2430_init);
+annotated_initcall(subsys, omap2430_init, omap2430_driver.driver);
 
 static void __exit omap2430_exit(void)
 {
-- 
2.1.0

[PATCH 14/16] deps: WIP: kirkwood: annotate some initcalls

[Alexander Holler]

WIP means Work In Progress.

Change some kirkwood drivers to offer annotated initcalls.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/dma/mv_xor.c                       | 2 +-
 drivers/net/ethernet/marvell/mv643xx_eth.c | 3 ++-
 drivers/usb/host/ehci-orion.c              | 2 +-
 3 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/drivers/dma/mv_xor.c b/drivers/dma/mv_xor.c
index f1325f6..e766ab2 100644
--- a/drivers/dma/mv_xor.c
+++ b/drivers/dma/mv_xor.c
@@ -1295,7 +1295,7 @@ static int __init mv_xor_init(void)
 {
 	return platform_driver_register(&mv_xor_driver);
 }
-module_init(mv_xor_init);
+annotated_module_init(mv_xor_init, mv_xor_driver.driver);
 
 /* it's currently unsafe to unload this module */
 #if 0
diff --git a/drivers/net/ethernet/marvell/mv643xx_eth.c b/drivers/net/ethernet/marvell/mv643xx_eth.c
index d52639b..5eec4d8 100644
--- a/drivers/net/ethernet/marvell/mv643xx_eth.c
+++ b/drivers/net/ethernet/marvell/mv643xx_eth.c
@@ -3239,7 +3239,8 @@ static int __init mv643xx_eth_init_module(void)
 
 	return rc;
 }
-module_init(mv643xx_eth_init_module);
+annotated_module_init(mv643xx_eth_init_module,
+		      mv643xx_eth_shared_driver.driver);
 
 static void __exit mv643xx_eth_cleanup_module(void)
 {
diff --git a/drivers/usb/host/ehci-orion.c b/drivers/usb/host/ehci-orion.c
index bfcbb9a..28f8793 100644
--- a/drivers/usb/host/ehci-orion.c
+++ b/drivers/usb/host/ehci-orion.c
@@ -333,7 +333,7 @@ static int __init ehci_orion_init(void)
 	ehci_init_driver(&ehci_orion_hc_driver, &orion_overrides);
 	return platform_driver_register(&ehci_orion_driver);
 }
-module_init(ehci_orion_init);
+annotated_module_init(ehci_orion_init, ehci_orion_driver.driver);
 
 static void __exit ehci_orion_cleanup(void)
 {
-- 
2.1.0

[PATCH 15/16] mtd: mtdcore: fix initcall level

[Alexander Holler]

The mtd-core has to be initialized before other dependent mtd-drivers,
otherwise a crash might occur.

Currently mtd_init() is called in the initcall-level device, which is the
same level where most mtd-drivers will end up. By luck this seemed to have
been called most of the time before other mtd-drivers without having been
explicitly enforced. But if mtd_init() is not called before a dependent
driver, a null-pointer exception might occur (e.g. because the mtd device
class isn't registered).

To fix this, mtd-init() is moved to the initcall-level fs (right before
the standard initcall level device).

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/mtd/mtdcore.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/mtd/mtdcore.c b/drivers/mtd/mtdcore.c
index 8bbbb75..fa8e6452 100644
--- a/drivers/mtd/mtdcore.c
+++ b/drivers/mtd/mtdcore.c
@@ -1303,7 +1303,7 @@ static void __exit cleanup_mtd(void)
 	bdi_destroy(&mtd_bdi);
 }
 
-module_init(init_mtd);
+fs_initcall_sync(init_mtd);
 module_exit(cleanup_mtd);
 
 MODULE_LICENSE("GPL");
-- 
2.1.0

Re: [PATCH 15/16] mtd: mtdcore: fix initcall level

[Brian Norris]

Hi Alexander,

No judgment here for the rest of this series, but for this patch:

On Wed, Aug 26, 2015 at 02:28:27PM +0200, Alexander Holler wrote:
> The mtd-core has to be initialized before other dependent mtd-drivers,
> otherwise a crash might occur.
> 
> Currently mtd_init() is called in the initcall-level device, which is the
> same level where most mtd-drivers will end up. By luck this seemed to have
> been called most of the time before other mtd-drivers without having been
> explicitly enforced.

I can't really speak for the original authors, but it does not appear to
be entirely "by luck." Link order was one of the de facto ways to get
this ordering (though it's not really a great one), and mtdcore was
always linked first within the drivers/mtd/ directory structure.

But that's just background, I think this is worth fixing anyway. It
could, for instance, become a problem if drivers are located outside
drivers/mtd/; I see random board files in arch/ that register with MTD,
and I'm actually not sure how they have never tripped on this.

> But if mtd_init() is not called before a dependent
> driver, a null-pointer exception might occur (e.g. because the mtd device
> class isn't registered).
> 
> To fix this, mtd-init() is moved to the initcall-level fs (right before
> the standard initcall level device).

Is there a good reason we shouldn't just make this a subsys_initcall()?
That would match the naming better, and it mirrors what, e.g.,
block/genhd uses. It would also allow flexibility if there are other
current/future use cases that might need to sit between the subsystem
and the drivers.

> Signed-off-by: Alexander Holler <holler-SXC+2es9fhnfWeYVQQPykw@public.gmane.org>
> ---
>  drivers/mtd/mtdcore.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/drivers/mtd/mtdcore.c b/drivers/mtd/mtdcore.c
> index 8bbbb75..fa8e6452 100644
> --- a/drivers/mtd/mtdcore.c
> +++ b/drivers/mtd/mtdcore.c
> @@ -1303,7 +1303,7 @@ static void __exit cleanup_mtd(void)
>  	bdi_destroy(&mtd_bdi);
>  }
>  
> -module_init(init_mtd);
> +fs_initcall_sync(init_mtd);

Why the *_sync() version? init_mtd() is very simple and doesn't have any
multithreading issues to handle.

>  module_exit(cleanup_mtd);
>  
>  MODULE_LICENSE("GPL");
> -- 
> 2.1.0
> 

Regards,
Brian
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 15/16] mtd: mtdcore: fix initcall level

[Alexander Holler]

Am 01.09.2015 um 23:19 schrieb Brian Norris:
> Hi Alexander,
>
> No judgment here for the rest of this series, but for this patch:
>
> On Wed, Aug 26, 2015 at 02:28:27PM +0200, Alexander Holler wrote:
>> The mtd-core has to be initialized before other dependent mtd-drivers,
>> otherwise a crash might occur.
>>
>> Currently mtd_init() is called in the initcall-level device, which is the
>> same level where most mtd-drivers will end up. By luck this seemed to have
>> been called most of the time before other mtd-drivers without having been
>> explicitly enforced.
>
> I can't really speak for the original authors, but it does not appear to
> be entirely "by luck." Link order was one of the de facto ways to get
> this ordering (though it's not really a great one), and mtdcore was
> always linked first within the drivers/mtd/ directory structure.
>
> But that's just background, I think this is worth fixing anyway. It
> could, for instance, become a problem if drivers are located outside
> drivers/mtd/; I see random board files in arch/ that register with MTD,
> and I'm actually not sure how they have never tripped on this.

I've already found at least a half a dozen other drivers with the same 
problem through my shuffling of the drivers which all end up in the 
standard initcall level device. I'm aware that this is based on the link 
order, which itself is based on linker behaviour (and maybe other things 
like make or other build tools). I'm just calling it luck, because this 
is nowhere explicitly stated, at least I've never seen such a statement, 
neither in any source, nor somewhere in Documentation. So I've choosen 
the term "by luck" in order to provoke a bit (or to stimulate a 
discussion about that widespread problem).

>
>> But if mtd_init() is not called before a dependent
>> driver, a null-pointer exception might occur (e.g. because the mtd device
>> class isn't registered).
>>
>> To fix this, mtd-init() is moved to the initcall-level fs (right before
>> the standard initcall level device).
>
> Is there a good reason we shouldn't just make this a subsys_initcall()?
> That would match the naming better, and it mirrors what, e.g.,
> block/genhd uses. It would also allow flexibility if there are other
> current/future use cases that might need to sit between the subsystem
> and the drivers.

No real reason here. The names for the initcall levels seem to be 
outdated since a long time anyway, and I think just speaking about the 
numbers 1-7 (or 0-14) would be better anyways. The only reason why I've 
used the fs (sync) level is because I was too lazy to check out if 
mtdcore might depend on something else in any other level. Therefor I've 
used the one most close to were it was before.

Also I've an idea about how to fix that in general for all drivers (by 
using the same algorithm I've now introduced just for DT-based drivers 
with a device description). Wouldn't be that hard to use that for all 
drivers, but as I've written in a follow up to the introductory mail, 
one step after another.

Regards,

Alexander Holler

Re: [PATCH 15/16] mtd: mtdcore: fix initcall level

[Alexander Holler]

Am 02.09.2015 um 07:34 schrieb Alexander Holler:
> Am 01.09.2015 um 23:19 schrieb Brian Norris:
>> Hi Alexander,
>>
>> No judgment here for the rest of this series, but for this patch:
>>
>> On Wed, Aug 26, 2015 at 02:28:27PM +0200, Alexander Holler wrote:
>>> The mtd-core has to be initialized before other dependent mtd-drivers,
>>> otherwise a crash might occur.
>>>
>>> Currently mtd_init() is called in the initcall-level device, which is
>>> the
>>> same level where most mtd-drivers will end up. By luck this seemed to
>>> have
>>> been called most of the time before other mtd-drivers without having
>>> been
>>> explicitly enforced.
>>
>> I can't really speak for the original authors, but it does not appear to
>> be entirely "by luck." Link order was one of the de facto ways to get
>> this ordering (though it's not really a great one), and mtdcore was
>> always linked first within the drivers/mtd/ directory structure.
>>
>> But that's just background, I think this is worth fixing anyway. It
>> could, for instance, become a problem if drivers are located outside
>> drivers/mtd/; I see random board files in arch/ that register with MTD,
>> and I'm actually not sure how they have never tripped on this.
>
> I've already found at least a half a dozen other drivers with the same
> problem through my shuffling of the drivers which all end up in the
> standard initcall level device. I'm aware that this is based on the link
> order, which itself is based on linker behaviour (and maybe other things
> like make or other build tools). I'm just calling it luck, because this
> is nowhere explicitly stated, at least I've never seen such a statement,
> neither in any source, nor somewhere in Documentation. So I've choosen
> the term "by luck" in order to provoke a bit (or to stimulate a
> discussion about that widespread problem).

A good example why "luck" might not be far away from the truth is what 
happens when a drivers moves e.g. from staging to it's real position. 
Also the position will stay inside the same initcall level, the move of 
the driver into another directory (maybe together with a rename) will 
likely change its position in the initcall-sequence, without anyone 
really expecting this.

>>> But if mtd_init() is not called before a dependent
>>> driver, a null-pointer exception might occur (e.g. because the mtd
>>> device
>>> class isn't registered).
>>>
>>> To fix this, mtd-init() is moved to the initcall-level fs (right before
>>> the standard initcall level device).
>>
>> Is there a good reason we shouldn't just make this a subsys_initcall()?
>> That would match the naming better, and it mirrors what, e.g.,
>> block/genhd uses. It would also allow flexibility if there are other
>> current/future use cases that might need to sit between the subsystem
>> and the drivers.
>
> No real reason here. The names for the initcall levels seem to be
> outdated since a long time anyway, and I think just speaking about the
> numbers 1-7 (or 0-14) would be better anyways. The only reason why I've
> used the fs (sync) level is because I was too lazy to check out if
> mtdcore might depend on something else in any other level. Therefor I've
> used the one most close to were it was before.

Lazy was the wrong term. It is time consuming, cumbersome and therefor 
error-prone to check on what other stuff a driver depends. One reason 
why choosing the right place in the initcall sequence isn't that easy 
and why some automation make sense.

> Also I've an idea about how to fix that in general for all drivers (by
> using the same algorithm I've now introduced just for DT-based drivers
> with a device description). Wouldn't be that hard to use that for all
> drivers, but as I've written in a follow up to the introductory mail,
> one step after another.
>
> Regards,
>
> Alexander Holler

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 15/16] mtd: mtdcore: fix initcall level

[Alexander Holler]

Am 04.09.2015 um 06:00 schrieb Alexander Holler:
> Am 02.09.2015 um 07:34 schrieb Alexander Holler:
>> Am 01.09.2015 um 23:19 schrieb Brian Norris:
>>> Hi Alexander,
>>>
>>> No judgment here for the rest of this series, but for this patch:
>>>
>>> On Wed, Aug 26, 2015 at 02:28:27PM +0200, Alexander Holler wrote:
>>>> The mtd-core has to be initialized before other dependent mtd-drivers,
>>>> otherwise a crash might occur.
>>>>
>>>> Currently mtd_init() is called in the initcall-level device, which is
>>>> the
>>>> same level where most mtd-drivers will end up. By luck this seemed to
>>>> have
>>>> been called most of the time before other mtd-drivers without having
>>>> been
>>>> explicitly enforced.
>>>
>>> I can't really speak for the original authors, but it does not appear to
>>> be entirely "by luck." Link order was one of the de facto ways to get
>>> this ordering (though it's not really a great one), and mtdcore was
>>> always linked first within the drivers/mtd/ directory structure.
>>>
>>> But that's just background, I think this is worth fixing anyway. It
>>> could, for instance, become a problem if drivers are located outside
>>> drivers/mtd/; I see random board files in arch/ that register with MTD,
>>> and I'm actually not sure how they have never tripped on this.

As I've just had a look at my patches in order to clean up the patch for 
parallel initialization (to post it here too):

drivers/mtd/ofparts.c has the same problem. In order to let the 
NAND-driver see the partitions defined in the DT I had to move this into 
another initcall level (fs sync) too.

Regards,

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 16/16] phy: phy-core: fix initcall level

[Alexander Holler]

The phy-core has to be initialized before other dependent usb-drivers,
otherwise a crash might occur.

Currently phy_core_init() is called in the initcall-level device, which is
the same level where most usb-drivers will end up. By luck this seemed to
have been called most of the time before other usb-drivers without having
been explicitly enforced. But if phy_core_init() is not called before a
dependent driver, a null-pointer exception might occur (e.g. because the
phy device class isn't registered).

To fix this, phy_core_init() is moved to the initcall-level fs (right
before the standard initcall level device).

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/phy/phy-core.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/phy/phy-core.c b/drivers/phy/phy-core.c
index fc48fac..4945029 100644
--- a/drivers/phy/phy-core.c
+++ b/drivers/phy/phy-core.c
@@ -930,7 +930,7 @@ static int __init phy_core_init(void)
 
 	return 0;
 }
-module_init(phy_core_init);
+fs_initcall_sync(phy_core_init);
 
 static void __exit phy_core_exit(void)
 {
-- 
2.1.0

Re: [PATCH 16/16] phy: phy-core: fix initcall level

[Kishon Vijay Abraham I]

Hi,

On Wednesday 26 August 2015 05:58 PM, Alexander Holler wrote:
> The phy-core has to be initialized before other dependent usb-drivers,
> otherwise a crash might occur.
> 
> Currently phy_core_init() is called in the initcall-level device, which is
> the same level where most usb-drivers will end up. By luck this seemed to
> have been called most of the time before other usb-drivers without having
> been explicitly enforced. But if phy_core_init() is not called before a
> dependent driver, a null-pointer exception might occur (e.g. because the
> phy device class isn't registered).

Did you actually face a problem? IIUC the modules get loaded based on
the drivers/Makefile order (unless the other modules are in a different
initcall table).

IMHO the fix should be in the module that caused the crash. Change it to
use module_init?

Thanks
Kishon

> 
> To fix this, phy_core_init() is moved to the initcall-level fs (right
> before the standard initcall level device).
> 
> Signed-off-by: Alexander Holler <holler-SXC+2es9fhnfWeYVQQPykw@public.gmane.org>
> ---
>  drivers/phy/phy-core.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/drivers/phy/phy-core.c b/drivers/phy/phy-core.c
> index fc48fac..4945029 100644
> --- a/drivers/phy/phy-core.c
> +++ b/drivers/phy/phy-core.c
> @@ -930,7 +930,7 @@ static int __init phy_core_init(void)
>  
>  	return 0;
>  }
> -module_init(phy_core_init);
> +fs_initcall_sync(phy_core_init);
>  
>  static void __exit phy_core_exit(void)
>  {
> 
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 16/16] phy: phy-core: fix initcall level

[Alexander Holler]

Am 18.09.2015 um 08:16 schrieb Kishon Vijay Abraham I:
> Hi,
>
> On Wednesday 26 August 2015 05:58 PM, Alexander Holler wrote:
>> The phy-core has to be initialized before other dependent usb-drivers,
>> otherwise a crash might occur.
>>
>> Currently phy_core_init() is called in the initcall-level device, which is
>> the same level where most usb-drivers will end up. By luck this seemed to
>> have been called most of the time before other usb-drivers without having
>> been explicitly enforced. But if phy_core_init() is not called before a
>> dependent driver, a null-pointer exception might occur (e.g. because the
>> phy device class isn't registered).
>
> Did you actually face a problem? IIUC the modules get loaded based on
> the drivers/Makefile order (unless the other modules are in a different
> initcall table).

I had a problem while playing with a modified init-system (based on 
dependencies). So not an actual problem.

> IMHO the fix should be in the module that caused the crash. Change it to
> use module_init?

The problem arises if the init-system ignores the link order and assumes 
all drivers in the same initcall level can be called without any special 
ordering.
The problem might also appear if a driver changes its name, directory or 
position in file system. E.g. how to you make sure that a driver in 
staging will be linked after the phy-core? Actually this happens, but I 
would assume its by luck. I assume if staging would be renamed to 
'beta-quality' a lot of stuff would actually fail because of the problem 
with the implicit link order.

Anyway, nothing which really has to be fixed. It's just a notice that 
maybe another initcall level of 'subsys' or something else before 
'device' might be a better place for phy-core. I've chosen fs_sync 
instead of subsys because otherwise I would have had to look up if 
phy-core depends on another subsystem and therefore has to be 
initialized after subsys.

Regards,

Alexander Holler

>
> Thanks
> Kishon
>
>>
>> To fix this, phy_core_init() is moved to the initcall-level fs (right
>> before the standard initcall level device).
>>
>> Signed-off-by: Alexander Holler <holler-SXC+2es9fhnfWeYVQQPykw@public.gmane.org>
>> ---
>>   drivers/phy/phy-core.c | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/drivers/phy/phy-core.c b/drivers/phy/phy-core.c
>> index fc48fac..4945029 100644
>> --- a/drivers/phy/phy-core.c
>> +++ b/drivers/phy/phy-core.c
>> @@ -930,7 +930,7 @@ static int __init phy_core_init(void)
>>
>>   	return 0;
>>   }
>> -module_init(phy_core_init);
>> +fs_initcall_sync(phy_core_init);
>>
>>   static void __exit phy_core_exit(void)
>>   {
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 00/16] deps: deterministic driver initialization order

[Alexander Holler]

Am 26.08.2015 um 14:28 schrieb Alexander Holler:

> The final 2 patches are fixes which should end up in mainline, regardless
> if this feature is merged or not.

Just in case your serial or MTD-NAND partitions don't work, the drivers
drivers/tty/serial/8250/8250_core.c and drivers/mtd/ofpart.c need the 
same trivial fix for their initcall level as found in the last two 
patches of my series. I'm not going to post these patches now until I've 
got some feedback for the other stuff.

Regards,

Alexander Holler

Re: [PATCH 00/16] deps: deterministic driver initialization order

[Alexander Holler]

Am 27.08.2015 um 21:01 schrieb Alexander Holler:
> Am 26.08.2015 um 14:28 schrieb Alexander Holler:
>
>> The final 2 patches are fixes which should end up in mainline, regardless
>> if this feature is merged or not.
>
> Just in case your serial or MTD-NAND partitions don't work, the drivers
> drivers/tty/serial/8250/8250_core.c and drivers/mtd/ofpart.c need the
> same trivial fix for their initcall level as found in the last two
> patches of my series. I'm not going to post these patches now until I've
> got some feedback for the other stuff.

And just in case, I also have an idea how to fix such dependencies for 
drivers without DT (by adding hard-wired dependencies directly to 
drivers). That would also be usable for ACPI and x86.

But one step after another. Based on my past experiences, I don't even 
think the stuff I've just posted will ever end up in the kernel.

> Regards,
>
> Alexander Holler

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 02/16] deps: dtc: Add option to print initialization order

[Alexander Holler]

Add option -t to print the default initialization order.
No other output will be generated.

To print the order, just use something like this:

	CROSS_COMPILE=gcc-foo ARCH=arm make foo.dtb
	scripts/dtc/dtc -I dtb -t arch/arm/boot/dts/foo.dtb

Since it's now possible to check to for cycles in the dependency graph,
this is now done too.

Signed-off-by: Alexander Holler <holler-SXC+2es9fhnfWeYVQQPykw@public.gmane.org>
---
 scripts/dtc/dependencies.c | 344 +++++++++++++++++++++++++++++++++++++++++++++
 scripts/dtc/dtc.c          |  24 +++-
 scripts/dtc/dtc.h          |   2 +
 3 files changed, 369 insertions(+), 1 deletion(-)

diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
index dd4658c..3fb5cef 100644
--- a/scripts/dtc/dependencies.c
+++ b/scripts/dtc/dependencies.c
@@ -106,3 +106,347 @@ void add_dependencies(struct boot_info *bi)
 {
 	process_nodes_props(bi->dt, bi->dt);
 }
+
+/*
+ * The code below is in large parts a copy of drivers/of/of_dependencies.c
+ * in the Linux kernel. So both files do share the same bugs.
+ * The next few ugly defines do exist to keep the differences at a minimum.
+ */
+static struct node *tree;
+#define pr_cont(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_info(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_warn(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_err(format, ...) fprintf(stderr, format, ##__VA_ARGS__)
+typedef cell_t __be32;
+#define device_node node
+#define full_name fullpath
+#define __initdata
+#define __init
+#define unlikely(a) (a)
+#define of_node_put(a)
+#define of_find_node_by_phandle(v) get_node_by_phandle(tree, v)
+#define __of_get_property(a, b, c) get_property(a, b)
+#define for_each_child_of_node(a, b) for_each_child(a, b)
+
+
+#define MAX_DT_NODES 1000 /* maximum number of vertices */
+#define MAX_EDGES (MAX_DT_NODES*2) /* maximum number of edges (dependencies) */
+
+struct edgenode {
+	uint32_t y; /* phandle */
+	struct edgenode *next; /* next edge in list */
+};
+
+/*
+ * Vertex numbers do correspond to phandle numbers. That means the graph
+ * does contain as much vertices as the maximum of all phandles.
+ * Or in other words, we assume that for all phandles in the device tree
+ * 0 < phandle < MAX_DT_NODES+1 is true.
+ */
+struct dep_graph {
+	struct edgenode edge_slots[MAX_EDGES]; /* used to avoid kmalloc */
+	struct edgenode *edges[MAX_DT_NODES+1]; /* adjacency info */
+	unsigned nvertices; /* number of vertices in graph */
+	unsigned nedges; /* number of edges in graph */
+	bool processed[MAX_DT_NODES+1]; /* which vertices have been processed */
+	bool include_node[MAX_DT_NODES+1]; /* which nodes to consider */
+	bool discovered[MAX_DT_NODES+1]; /* which vertices have been found */
+	bool finished; /* if true, cut off search immediately */
+};
+static struct dep_graph graph __initdata;
+
+struct init_order {
+	uint32_t max_phandle; /* the max used phandle */
+	uint32_t old_max_phandle; /* used to keep track of added phandles */
+	struct device_node *order[MAX_DT_NODES+1];
+	unsigned count;
+	/* Used to keep track of parent devices in regard to the DT */
+	uint32_t parent_by_phandle[MAX_DT_NODES+1];
+	struct device *device_by_phandle[MAX_DT_NODES+1];
+};
+static struct init_order order __initdata;
+
+
+/* Copied from drivers/of/base.c (because it's lockless). */
+static int __init __of_device_is_available(struct device_node *device)
+{
+	struct property *status;
+
+	if (!device)
+		return 0;
+
+	status = get_property(device, "status");
+	if (status == NULL)
+		return 1;
+
+	if (status->val.len > 0) {
+		if (!strcmp(status->val.val, "okay") ||
+				!strcmp(status->val.val, "ok"))
+			return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * x is a dependant of y or in other words
+ * y will be initialized before x.
+ */
+static int __init insert_edge(uint32_t x, uint32_t y)
+{
+	struct edgenode *p; /* temporary pointer */
+
+	if (unlikely(x > MAX_DT_NODES || y > MAX_DT_NODES)) {
+		pr_err("Node found with phandle 0x%x > MAX_DT_NODES (%d)!\n",
+			x > MAX_DT_NODES ? x : y, MAX_DT_NODES);
+		return -EINVAL;
+	}
+	if (unlikely(!x || !y))
+		return 0;
+	if (unlikely(graph.nedges >= MAX_EDGES)) {
+		pr_err("Maximum number of edges (%d) reached!\n", MAX_EDGES);
+		return -EINVAL;
+	}
+	p = &graph.edge_slots[graph.nedges++];
+	graph.include_node[x] = 1;
+	graph.include_node[y] = 1;
+	p->y = y;
+	p->next = graph.edges[x];
+	graph.edges[x] = p; /* insert at head of list */
+
+	graph.nvertices = (x > graph.nvertices) ? x : graph.nvertices;
+	graph.nvertices = (y > graph.nvertices) ? y : graph.nvertices;
+	return 0;
+}
+
+static void __init print_node_name(uint32_t v)
+{
+	struct device_node *node;
+
+	node = of_find_node_by_phandle(v);
+	if (!node) {
+		pr_err("Node for phandle 0x%x not found", v);
+		return;
+	}
+	if (node->name)
+		pr_err("%s", node->name);
+	if (node->full_name)
+		pr_err(" (%s)", node->full_name);
+	of_node_put(node);
+}
+
+/*
+ * I would prefer to use the BGL (Boost Graph Library), but as I can't use it
+ * here (for obvious reasons), the next four functions below are based on
+ * code of Steven Skiena's book 'The Algorithm Design Manual'.
+ */
+
+static void __init process_edge(uint32_t x, uint32_t y)
+{
+	if (unlikely(graph.discovered[y] && !graph.processed[y])) {
+		pr_err("Cycle found 0x%x ", x);
+		print_node_name(x);
+		pr_cont(" <-> 0x%x ", y);
+		print_node_name(y);
+		pr_cont("!\n");
+		graph.finished = 1;
+	}
+}
+
+static void __init process_vertex_late(uint32_t v)
+{
+	struct device_node *node;
+
+	node = of_find_node_by_phandle(v);
+	if (!node) {
+		pr_err("No node for phandle 0x%x not found", v);
+		return;
+	}
+	order.order[order.count++] = node;
+}
+
+static void __init depth_first_search(uint32_t v)
+{
+	struct edgenode *p;
+	uint32_t y; /* successor vertex */
+
+	if (graph.finished)
+		return;
+	graph.discovered[v] = 1;
+	p = graph.edges[v];
+	while (p) {
+		y = p->y;
+		if (!graph.discovered[y]) {
+			process_edge(v, y);
+			depth_first_search(y);
+		} else
+			process_edge(v, y);
+		if (graph.finished)
+			return;
+		p = p->next;
+	}
+	process_vertex_late(v);
+	graph.processed[v] = 1;
+}
+
+static void __init topological_sort(void)
+{
+	unsigned i;
+
+	for (i = 1; i <= graph.nvertices; ++i)
+		if (!graph.discovered[i] && graph.include_node[i])
+			depth_first_search(i);
+}
+
+static int __init add_dep_list(struct device_node *node)
+{
+	const __be32 *list, *list_end;
+	uint32_t ph;
+	struct property *prop;
+	int rc = 0;
+	struct device_node *dep;
+
+	prop = get_property(node, "dependencies");
+	if (!prop || !prop->val.len || prop->val.len%sizeof(*list))
+		return 0;
+	list = (const __be32 *)prop->val.val;
+	list_end = list + prop->val.len / sizeof(*list);
+	while (list < list_end) {
+		ph = fdt32_to_cpu(*list++);
+		if (unlikely(!ph)) {
+			/* Should never happen */
+			if (node->name)
+				pr_warn("phandle == 0 for %s\n", node->name);
+			continue;
+		}
+		dep = of_find_node_by_phandle(ph);
+		if (unlikely(!dep)) {
+			pr_err("No DT node for dependency with phandle 0x%x found\n",
+				ph);
+			continue;
+		}
+		rc = insert_edge(node->phandle, ph);
+		if (rc)
+			break;
+	}
+
+	return rc;
+}
+
+/* Copied from drivers/of/base.c */
+static const char *of_prop_next_string(struct property *prop, const char *cur)
+{
+	const char *curv = cur;
+
+	if (!prop)
+		return NULL;
+
+	if (!cur)
+		return prop->val.val;
+
+	curv += strlen(cur) + 1;
+	if (curv >= prop->val.val + prop->val.len)
+		return NULL;
+
+	return curv;
+}
+
+static int __init add_deps_lnx(struct device_node *parent,
+				struct device_node *node)
+{
+	struct device_node *child;
+	int rc = 0;
+
+	if (!__of_device_is_available(node))
+		return 0;
+	if (__of_get_property(node, "compatible", NULL)) {
+		if (!parent->phandle) {
+			if (__of_get_property(parent, "compatible", NULL))
+				parent->phandle = 1 + order.max_phandle++;
+		}
+		if (!node->phandle)
+			node->phandle = 1 + order.max_phandle++;
+		rc = insert_edge(node->phandle, parent->phandle);
+		if (rc)
+			return rc;
+		if (unlikely(order.parent_by_phandle[node->phandle])) {
+			/* sanity check */
+			pr_err("0x%x already has a parent!\n", node->phandle);
+			return -EINVAL;
+		}
+		order.parent_by_phandle[node->phandle] = parent->phandle;
+		rc = add_dep_list(node);
+		if (unlikely(rc))
+			return rc;
+		parent = node; /* change the parent only if node is a driver */
+	}
+	for_each_child_of_node(node, child) {
+		rc = add_deps_lnx(parent, child);
+		if (unlikely(rc))
+			break;
+	}
+
+	return rc;
+}
+
+static void calc_max_phandle(struct node *np)
+{
+	struct node *child;
+
+	if (!np || np->deleted)
+		return;
+	if (np->phandle > order.max_phandle)
+		order.max_phandle = np->phandle;
+
+	for_each_child(np, child)
+		calc_max_phandle(child);
+}
+
+void __init of_init_print_order(const char *name)
+{
+	unsigned i;
+	struct property *prop;
+	const char *cp;
+
+	pr_info("Default initialization order for %s:\n", name);
+	for (i = 0; i < order.count; ++i) {
+		pr_info("init %u 0x%x", i, order.order[i]->phandle);
+		if (order.order[i]->name)
+			pr_cont(" %s", order.order[i]->name);
+		if (order.order[i]->full_name)
+			pr_cont(" (%s)", order.order[i]->full_name);
+		prop = get_property(order.order[i], "compatible");
+		for (cp = of_prop_next_string(prop, NULL); cp;
+		     cp = of_prop_next_string(prop, cp))
+			pr_cont(" %s", cp);
+		pr_cont(" (parent 0x%x)\n",
+			order.parent_by_phandle[order.order[i]->phandle]);
+	}
+}
+
+int __init of_init_build_order(struct device_node *root)
+{
+	struct device_node *child;
+	int rc = 0;
+
+	tree = root;
+	if (unlikely(!root))
+		return -EINVAL;
+
+	calc_max_phandle(root);
+	order.old_max_phandle = order.max_phandle;
+
+	for_each_child_of_node(root, child) {
+		rc = add_deps_lnx(root, child);
+		if (unlikely(rc))
+			break;
+	}
+
+	of_node_put(root);
+	topological_sort();
+
+	if (graph.finished)
+		return -EINVAL; /* cycle found */
+
+	return rc;
+}
diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c
index 28def27..494c531 100644
--- a/scripts/dtc/dtc.c
+++ b/scripts/dtc/dtc.c
@@ -51,7 +51,7 @@ static void fill_fullpaths(struct node *tree, const char *prefix)
 #define FDT_VERSION(version)	_FDT_VERSION(version)
 #define _FDT_VERSION(version)	#version
 static const char usage_synopsis[] = "dtc [options] <input file>";
-static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDW:E:hv";
+static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDtW:E:hv";
 static struct option const usage_long_opts[] = {
 	{"quiet",            no_argument, NULL, 'q'},
 	{"in-format",         a_argument, NULL, 'I'},
@@ -67,6 +67,7 @@ static struct option const usage_long_opts[] = {
 	{"include",           a_argument, NULL, 'i'},
 	{"sort",             no_argument, NULL, 's'},
 	{"no-deps",          no_argument, NULL, 'D'},
+	{"initialization-order", no_argument, NULL, 't'},
 	{"phandle",           a_argument, NULL, 'H'},
 	{"warning",           a_argument, NULL, 'W'},
 	{"error",             a_argument, NULL, 'E'},
@@ -95,6 +96,7 @@ static const char * const usage_opts_help[] = {
 	"\n\tAdd a path to search for include files",
 	"\n\tSort nodes and properties before outputting (useful for comparing trees)",
 	"\n\tDo not automatically add dependencies for phandle references",
+	"\n\tPrint (default) initialization order",
 	"\n\tValid phandle formats are:\n"
 	 "\t\tlegacy - \"linux,phandle\" properties only\n"
 	 "\t\tepapr  - \"phandle\" properties only\n"
@@ -115,6 +117,7 @@ int main(int argc, char *argv[])
 	const char *depname = NULL;
 	bool force = false, sort = false;
 	bool dependencies = true;
+	bool init_order = false;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -186,6 +189,10 @@ int main(int argc, char *argv[])
 			dependencies = false;
 			break;
 
+		case 't':
+			init_order = true;
+			break;
+
 		case 'W':
 			parse_checks_option(true, false, optarg);
 			break;
@@ -246,6 +253,13 @@ int main(int argc, char *argv[])
 	if (dependencies)
 		add_dependencies(bi);
 
+	if (init_order) {
+		if (of_init_build_order(bi->dt))
+			exit(2);
+		of_init_print_order(arg);
+		exit(0);
+	}
+
 	if (streq(outname, "-")) {
 		outf = stdout;
 	} else {
@@ -267,5 +281,13 @@ int main(int argc, char *argv[])
 		die("Unknown output format \"%s\"\n", outform);
 	}
 
+	/*
+	 * Check for cycles by building the initialzation order.
+	 * This is done after the output was saved because it
+	 * changes the tree slightly.
+	 */
+	if (of_init_build_order(bi->dt))
+		exit(2);
+
 	exit(0);
 }
diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h
index 6facad1..9ae4bfc 100644
--- a/scripts/dtc/dtc.h
+++ b/scripts/dtc/dtc.h
@@ -268,5 +268,7 @@ struct boot_info *dt_from_fs(const char *dirname);
 
 /* Dependencies */
 void add_dependencies(struct boot_info *bi);
+void of_init_print_order(const char *name);
+int of_init_build_order(struct node *root);
 
 #endif /* _DTC_H */
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

deps: update in regard to parallel initialization of static linked drivers

[Alexander Holler]

Am 26.08.2015 um 14:28 schrieb Alexander Holler:
> Hello,

(...)

> Some numbers (5 boots on each board, without and with ordering drivers),
> all times are seconds.

(...)

> imx6q (armv7):
>
> unordered:
> 3.451998 3.418864 3.446952 3.429974 3.440996 (3.4377568)
> ordered:
> 3.538312 3.549019 3.538105 3.515916 3.555715 (3.5394134)

(...)

> Further improvements could be to initialize drivers in parallel (using
> multiple cores) and/or to use this stuff on x86 (ACPI) too (e.g. by using a
> minimal DT which just includes dependencies).

I've now made a quick implementation which uses multiple threads to 
initialize annotated drivers in parallel. It worked out of the box.

Here are the times (dmesg | grep Freeing) I've now measured on the imx6q 
(4 cores):

3.388273 3.399892 3.411615 3.410523 3.388802 (3.399821)

So it's now at least as fast as without ordering the drivers. Even on 
the one system where ordering didn't help without parallel 
initialization (likely because the unordered sequence of initcalls is 
already quiet good on that system, in comparison to the other systems 
I've tested).

And my current implementation for the parallel stuff is far from being 
perfect and can be optimized much more (enough to not post a patch 
here). In addition I've added another driver to my config since I 
measure the old times, so the new times are including one more 
initialization of a driver (it now calls 30 annotated (static linked) 
drivers at boot, most stuff is still in modules (and some not annotated 
static linked drivers) on that system).

Maybe this helps raising interest enough that someone else will test and 
maybe give some (reasonable, not about style) feedback on my patches.

> Regards,
>
> Alexander Holler

--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 0/2] deps: parallel initialization of (device-)drivers

[Alexander Holler]

Hello,

as already mentioned, I've implemented the stuff to initialize drivers
in parallel. What follows are two patches to be used on top of my
already posted series (for 4.2) which implements annotated initcalls
and DT based dependencies.

But be warned: many drivers which are in the same initcall level
still depend on the link order given by the Makefile and directoy
(-name) and therefor will fail. That means without moving them to other
initcall levels or explicit dependencies (which are a TODO) for these
drivers, the whole stuff currently works only for some configurations
and you likely will need to add several patches for your board.

I've already posted two patches to move two drivers into another
initcall level. While playing with the stuff, I've found several
more drivers which are suffering under the same problem and need
the same modification:

block/noop-iosched.c
crypto/hmac.c
cryoto/sha_generic.c
drivers/mtd/ofpart.c
drivers/tty/serial/8250/8250_core.c

To offer an impression how this patch series might work in action,
below is the relevant part from the kernel log for a configuration
I'm using successfully on an imx6q.

Maybe someone has interest in that stuff.

Regards,

Alexander Holler

-----------
(...)
[    2.628325] Thread 0 calling (ordered) initcall for driver reg-fixed-voltage (regulator-fixed)
[    2.629196] Thread 3 calling (ordered) initcall for driver imx6q-pinctrl (fsl,imx6q-iomuxc)
[    2.629331] Thread 0 calling (ordered) initcall for driver gpio-mxc (fsl,imx1-gpio)
[    2.630276] imx6q-pinctrl 20e0000.iomuxc: initialized IMX pinctrl driver
[    2.632543] Thread 0 calling (ordered) initcall for driver anatop_regulator (fsl,anatop-regulator)
[    2.632556] Thread 1 calling (ordered) initcall for driver imx-sdma (fsl,imx6q-sdma)
[    2.632563] Thread 2 calling (ordered) initcall for driver mxs-dma (fsl,imx23-dma-apbh)
[    2.632598] Thread 3 calling (ordered) initcall for driver sram (mmio-sram)
[    2.634502] mxs-dma 110000.dma-apbh: initialized
[    2.634848] Thread 3 calling (ordered) initcall for driver mxs_phy (fsl,imx6sx-usbphy)
[    2.635165] Thread 0 calling (ordered) initcall for driver imx2-wdt (fsl,imx21-wdt)
[    2.635181] Thread 2 calling (ordered) initcall for driver snvs_rtc (fsl,sec-v4.0-mon-rtc-lp)
[    2.635493] snvs_rtc 20cc034.snvs-rtc-lp: rtc core: setting system clock to 2015-09-09 16:37:09 UTC (1441816629)
[    2.635813] snvs_rtc 20cc034.snvs-rtc-lp: rtc core: registered 20cc034.snvs-rtc-lp as rtc0
[    2.635978] Thread 2 calling (ordered) initcall for driver ahci-imx (fsl,imx53-ahci)
[    2.636317] imx-sdma 20ec000.sdma: initialized
[    2.636322] ahci-imx 2200000.sata: fsl,transmit-level-mV not specified, using 00000024
[    2.636332] ahci-imx 2200000.sata: fsl,transmit-boost-mdB not specified, using 00000480
[    2.636338] ahci-imx 2200000.sata: fsl,transmit-atten-16ths not specified, using 00002000
[    2.636347] ahci-imx 2200000.sata: fsl,receive-eq-mdB not specified, using 05000000
[    2.636690] Thread 1 calling (ordered) initcall for driver wandboard-rfkill (wand,imx6q-wandboard-rfkill)
[    2.637160] imx-sdma 20ec000.sdma: loaded firmware 1.1
[    2.637166] imx2-wdt 20bc000.wdog: timeout 60 sec (nowayout=0)
[    2.637283] wandboard-rfkill rfkill: Wandboard rfkill initialization
[    2.637402] Thread 0 calling (ordered) initcall for driver leds-gpio (gpio-leds)
[    2.637422] wandboard-rfkill rfkill: Turning of power
[    2.639193] ahci-imx 2200000.sata: SSS flag set, parallel bus scan disabled
[    2.639253] ahci-imx 2200000.sata: AHCI 0001.0300 32 slots 1 ports 3 Gbps 0x1 impl platform mode
[    2.639299] ahci-imx 2200000.sata: flags: ncq sntf stag pm led clo only pmp pio slum part ccc apst
[    2.640579] scsi host0: ahci-imx
[    2.640902] ata1: SATA max UDMA/133 mmio [mem 0x02200000-0x02203fff] port 0x100 irq 67
[    2.663463] wandboard-rfkill rfkill: initialize wifi chip
[    2.663642] wandboard-rfkill rfkill: wifi-rfkill registered.
[    2.663720] wandboard-rfkill rfkill: initialize bluetooth chip
[    2.663919] wandboard-rfkill rfkill: bluetooth-rfkill registered.
[    2.664289] Thread 1 calling (ordered) initcall for driver imx-gpc (fsl,imx6q-gpc)
[    2.664335] Thread 3 calling (ordered) initcall for driver imx-uart (fsl,imx6q-uart)
[    2.664769] 2020000.serial: ttymxc0 at MMIO 0x2020000 (irq = 23, base_baud = 5000000) is a IMX
[    2.983471] ata1: SATA link up 1.5 Gbps (SStatus 113 SControl 300)
[    2.984610] ata1.00: ATA-8: Hitachi HTS542525K9SA00, BBFOC31P, max UDMA/133
[    2.984620] ata1.00: 488397168 sectors, multi 0: LBA48 NCQ (depth 31/32)
[    2.985793] ata1.00: configured for UDMA/133
[    2.985912] Default I/O scheduler not found. Using noop.
[    2.986213] scsi 0:0:0:0: Direct-Access     ATA      Hitachi HTS54252 C31P PQ: 0 ANSI: 5
[    2.986776] scsi 0:0:0:0: Failed to register bsg queue, errno=-19
[    3.734832] console [ttymxc0] enabled
[    3.739241] 21ec000.serial: ttymxc2 at MMIO 0x21ec000 (irq = 64, base_baud = 5000000) is a IMX
[    3.748368] Thread 3 calling (ordered) initcall for driver imx-i2c (fsl,imx1-i2c)
[    3.748396] Thread 2 calling (ordered) initcall for driver imx-mmdc (fsl,imx6q-mmdc)
[    3.748413] Thread 1 calling (ordered) initcall for driver fec (fsl,imx25-fec)
[    3.748424] Thread 0 calling (ordered) initcall for driver sdhci-esdhc-imx (fsl,imx25-esdhc)
[    3.749226] 2188000.ethernet supply phy not found, using dummy regulator
[    3.763882] pps pps0: new PPS source ptp0
[    3.776095] libphy: fec_enet_mii_bus: probed
[    3.776656] fec 2188000.ethernet eth0: registered PHC device 0
[    3.776854] Thread 1 calling (ordered) initcall for driver imx-weim (fsl,imx1-weim)
[    3.777206] /soc/aips-bus@02100000/usdhc@02190000: voltage-ranges unspecified
[    3.777216] sdhci-esdhc-imx 2190000.usdhc: could not get ultra high speed state, work on normal mode
[    3.777239] sdhci-esdhc-imx 2190000.usdhc: Got CD GPIO
[    3.778409] sdhci-esdhc-imx 2190000.usdhc: No vmmc regulator found
[    3.778415] sdhci-esdhc-imx 2190000.usdhc: No vqmmc regulator found
[    3.823587] mmc0: SDHCI controller on 2190000.usdhc [2190000.usdhc] using ADMA
[    3.823687] imx-weim 21b8000.weim: Driver registered.
[    3.824015] /soc/aips-bus@02100000/usdhc@02194000: voltage-ranges unspecified
[    3.824024] sdhci-esdhc-imx 2194000.usdhc: could not get ultra high speed state, work on normal mode
[    3.825203] sdhci-esdhc-imx 2194000.usdhc: No vmmc regulator found
[    3.825209] sdhci-esdhc-imx 2194000.usdhc: No vqmmc regulator found
[    3.873515] mmc1: SDHCI controller on 2194000.usdhc [2194000.usdhc] using ADMA
[    3.873884] /soc/aips-bus@02100000/usdhc@02198000: voltage-ranges unspecified
[    3.873894] sdhci-esdhc-imx 2198000.usdhc: could not get ultra high speed state, work on normal mode
[    3.873917] sdhci-esdhc-imx 2198000.usdhc: Got CD GPIO
[    3.875982] sdhci-esdhc-imx 2198000.usdhc: No vmmc regulator found
[    3.875988] sdhci-esdhc-imx 2198000.usdhc: No vqmmc regulator found
[    3.896409] mmc1: queuing unknown CIS tuple 0x80 (2 bytes)
[    3.898115] mmc1: queuing unknown CIS tuple 0x80 (3 bytes)
[    3.899819] mmc1: queuing unknown CIS tuple 0x80 (3 bytes)
[    3.902883] mmc1: queuing unknown CIS tuple 0x80 (7 bytes)
[    3.907303] mmc1: queuing unknown CIS tuple 0x80 (11 bytes)
[    3.913585] mmc2: SDHCI controller on 2198000.usdhc [2198000.usdhc] using ADMA
[    3.957288] mmc1: new high speed SDIO card at address 0001
[    3.965448] i2c i2c-0: IMX I2C adapter registered
[    3.970194] i2c i2c-0: can't use DMA
[    3.974279] i2c i2c-1: IMX I2C adapter registered
[    3.979026] i2c i2c-1: can't use DMA
[    3.983582] Thread 2 calling (unordered) initcall for driver imx-pwm (fsl,imx1-pwm)
[    3.983589] Thread 3 calling (unordered) initcall for driver ahci (generic-ahci)
[    3.983595] Thread 1 calling (unordered) initcall for driver spi_imx (fsl,imx1-cspi)
[    3.983601] Thread 0 calling (unordered) initcall for driver usb_phy_generic (usb-nop-xceiv)
[    3.984137] Thread 3 calling (unordered) initcall for driver mxc_rtc ()
[    3.984142] Thread 1 calling (unordered) initcall for driver ir-kbd-i2c ()
[    3.984147] Thread 0 calling (unordered) initcall for driver imx-snvs-poweroff (fsl,sec-v4.0-poweroff)
[    3.984200] Thread 1 calling (unordered) initcall for driver imx6q-cpufreq ()
[    3.984239] Thread 3 calling (unordered) initcall for driver hdmi-audio-codec (linux,hdmi-audio)
[    3.984289] Thread 1 calling (unordered) initcall for driver rfkill_gpio ()
(...)
-----------

[PATCH 1/2] deps: parallel initialization of (device-)drivers

[Alexander Holler]

This initializes drivers (annotated or in the initcall level device)
in parallel.

Which drivers can be initialized in parallel is calculated by using
the dependencies. That means, currently, only annotated drivers which
are are referenced in the used DT will be in order. For all others it
is assumed that, as long as they belong to the same initcall level
(device), they can be called in any order.

Unfortunately this isn't allways true and several drivers are depending
on the link-order (based on the Makefile and the directory). This is,
imho, a bug or at least a very fragile way to do such and should be,
again imho, fixed. Otherwise problems might arise if e.g. a driver is
moved from staging to its final position (which changes its place in
the list of initcalls too).
But this isn't really the topic of this patch and I'm mentioning this
here just as a warning or as hint in case someone experiences problems
when enabling the feature this patch provides.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/of/Kconfig           |  20 ++++
 drivers/of/of_dependencies.c | 245 ++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 261 insertions(+), 4 deletions(-)

diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
index 26c4b1a..7e6e910 100644
--- a/drivers/of/Kconfig
+++ b/drivers/of/Kconfig
@@ -132,4 +132,24 @@ config OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
 	help
 	  Used for debugging purposes.
 
+config OF_DEPENDENCIES_PARALLEL
+	bool "Initialize annotated initcalls in parallel"
+	depends on OF_DEPENDENCIES
+	help
+	  Calculates which (annotated) initcalls can be called in parallel
+	  and calls them using multiple threads. Be warned, this doesn't
+	  work always as it should because of missing dependencies and
+	  because it assumes that drivers belonging to the same initcall
+	  level can be called in an order different than the order they
+	  are linked.
+
+config OF_DEPENDENCIES_THREADS
+	int "Number of threads to use for parallel initialization"
+	depends on OF_DEPENDENCIES_PARALLEL
+	default 0
+	help
+	  0 means the number of threads used for parallel initialization
+	  of drivers equals the number of online CPUs.
+	  1 means the threaded initialization is disabled.
+
 endif # OF
diff --git a/drivers/of/of_dependencies.c b/drivers/of/of_dependencies.c
index 06435d5..85cef84 100644
--- a/drivers/of/of_dependencies.c
+++ b/drivers/of/of_dependencies.c
@@ -11,12 +11,16 @@
  */
 
 #include <linux/of_dependencies.h>
+#include <linux/kthread.h>
 
 #define MAX_DT_NODES 1000 /* maximum number of vertices */
 #define MAX_EDGES (MAX_DT_NODES*2) /* maximum number of edges (dependencies) */
 
 struct edgenode {
 	uint32_t y; /* phandle */
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+	uint32_t x;
+#endif
 	struct edgenode *next; /* next edge in list */
 };
 
@@ -120,6 +124,9 @@ static int __init insert_edge(uint32_t x, uint32_t y)
 	graph.include_node[x] = 1;
 	graph.include_node[y] = 1;
 	p->y = y;
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+	p->x = x;
+#endif
 	p->next = graph.edges[x];
 	graph.edges[x] = p; /* insert at head of list */
 
@@ -336,6 +343,90 @@ static void __init of_init_remove_duplicates(void)
 		}
 }
 
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+/*
+ * The algorithm I've used below to calculate the max. distance for
+ * nodes to the root node likely isn't the fasted. But based on the
+ * already done implementation of the topological sort, this is an
+ * easy way to achieve this. Instead of first doing an topological
+ * sort and then using the stuff below to calculate the distances,
+ * using an algorithm which does spit out distances directly would
+ * be likely faster.
+ * If you want to spend the time, you could have a look e.g. at the
+ * topic 'layered graph drawing'.
+ */
+/* max. distance from a node to root */
+static unsigned distance[MAX_DT_NODES+1] __initdata;
+static struct device_node *order_by_distance[MAX_DT_NODES+1] __initdata;
+
+static void __init calc_max_distance(uint32_t v)
+{
+	unsigned i;
+	unsigned max_dist = 0;
+
+	for (i = 0; i < graph.nedges; ++i)
+		if (graph.edge_slots[i].x == v)
+			max_dist = max(max_dist,
+				distance[graph.edge_slots[i].y] + 1);
+	distance[v] = max_dist;
+}
+
+static void __init calc_distances(void)
+{
+	unsigned i;
+
+	for (i = 0; i < order.count; ++i)
+		calc_max_distance(order.order[i]->phandle);
+}
+
+static void __init build_order_by_distance(void)
+{
+	unsigned i, j;
+	unsigned max_distance = 0;
+	unsigned new_order_count = 0;
+
+	calc_distances();
+	order_by_distance[new_order_count++] = order.order[0];
+	for (i = 1; i < order.count; ++i) {
+		if (distance[order.order[i]->phandle] == 1)
+			order_by_distance[new_order_count++] = order.order[i];
+		max_distance = max(max_distance,
+				   distance[order.order[i]->phandle]);
+	}
+	for (j = 2; j <= max_distance; ++j)
+		for (i = 1; i < order.count; ++i)
+			if (distance[order.order[i]->phandle] == j)
+				order_by_distance[new_order_count++] =
+							order.order[i];
+	memcpy(order.order, order_by_distance,
+		sizeof(order.order[0]) * order.count);
+}
+
+struct thread_group {
+	unsigned start;
+	unsigned length;
+};
+
+static struct thread_group tgroup[20] __initdata;
+static unsigned count_groups __initdata;
+
+static void __init build_tgroups(void)
+{
+	unsigned i;
+	unsigned dist = 0;
+
+	for (i = 0; i < order.count; ++i) {
+		if (distance[order.order[i]->phandle] != dist) {
+			dist = distance[order.order[i]->phandle];
+			count_groups++;
+			tgroup[count_groups].start = i;
+		}
+		tgroup[count_groups].length++;
+	}
+	count_groups++;
+}
+#endif /* CONFIG_OF_DEPENDENCIES_PARALLEL */
+
 #ifdef CONFIG_OF_DEPENDENCIES_PRINT_INIT_ORDER
 static void __init of_init_print_order(void)
 {
@@ -345,7 +436,13 @@ static void __init of_init_print_order(void)
 
 	pr_info("Initialization order:\n");
 	for (i = 0; i < order.count; ++i) {
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+		pr_info("init %u 0x%x (group %u)", i,
+			order.order[i]->phandle,
+			distance[order.order[i]->phandle]);
+#else
 		pr_info("init %u 0x%x", i, order.order[i]->phandle);
+#endif
 		if (order.order[i]->name)
 			pr_cont(" %s", order.order[i]->name);
 		if (order.order[i]->full_name)
@@ -397,7 +494,14 @@ static int __init of_init_build_order(void)
 	if (graph.finished)
 		return -EINVAL; /* cycle found */
 
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+	build_order_by_distance();
 	of_init_remove_duplicates();
+	build_tgroups();
+#else
+	of_init_remove_duplicates();
+#endif
+
 #ifdef CONFIG_OF_DEPENDENCIES_PRINT_INIT_ORDER
 	of_init_print_order();
 #endif
@@ -417,7 +521,7 @@ static void __init of_init_free_order(void)
 	/* remove_new_phandles(); */
 }
 
-static void __init init_if_matched(struct device_node *node)
+static void __init init_if_matched(struct device_node *node, unsigned thread_nr)
 {
 	struct _annotated_initcall *ac;
 
@@ -427,7 +531,8 @@ static void __init init_if_matched(struct device_node *node)
 			if (of_match_node(ac->driver->of_match_table,
 					 node)) {
 #ifdef CONFIG_OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
-				pr_info("Calling (ordered) initcall for driver %s (%s)\n",
+				pr_info("Thread %u calling (ordered) initcall for driver %s (%s)\n",
+					thread_nr,
 					ac->driver->name,
 					ac->driver->of_match_table ?
 						ac->driver->of_match_table->compatible : "");
@@ -438,14 +543,93 @@ static void __init init_if_matched(struct device_node *node)
 	}
 }
 
-void __init of_init_drivers(void)
+#ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
+
+static __initdata DECLARE_COMPLETION(initcall_thread_done);
+static __initdata DECLARE_WAIT_QUEUE_HEAD(group_waitqueue);
+
+static atomic_t shared_counter __initdata;
+static atomic_t count_initcall_threads __initdata;
+static atomic_t ostart __initdata;
+static atomic_t ocount __initdata;
+static unsigned num_threads __initdata;
+
+static atomic_t current_group __initdata;
+
+static int __init initcall_thread_unordered(void *thread_nr)
+{
+	struct _annotated_initcall *ac;
+	int i;
+	int count_initcalls =
+		__annotated_initcall_end - __annotated_initcall_start;
+
+	while ((i = atomic_dec_return(&shared_counter)) >= 0) {
+		ac = &__annotated_initcall_start[count_initcalls - 1 - i];
+		if (ac->initcall) {
+#ifdef CONFIG_OF_DEPENDENCIES_DEBUG_CALLS_OF_ANNOTATED_INITCALLS
+			pr_info("Thread %u calling (unordered) initcall for driver %s (%s)\n",
+				(unsigned)thread_nr, ac->driver->name,
+				ac->driver->of_match_table ?
+					ac->driver->of_match_table->compatible : "");
+#endif
+			do_one_initcall(*ac->initcall);
+		}
+	}
+	if (atomic_dec_and_test(&count_initcall_threads))
+		complete(&initcall_thread_done);
+	do_exit(0);
+	return 0;
+}
+
+static int __init initcall_thread(void *thread_nr)
+{
+	int i;
+	unsigned group;
+	int start, count;
+
+	DEFINE_WAIT(wait);
+
+	while ((group = atomic_read(&current_group)) < count_groups) {
+		start = atomic_read(&ostart);
+		count = atomic_read(&ocount);
+		while ((i = atomic_dec_return(&shared_counter)) >= 0)
+			init_if_matched(order.order[start + count - 1 - i],
+					(unsigned)thread_nr);
+		prepare_to_wait(&group_waitqueue, &wait, TASK_UNINTERRUPTIBLE);
+		if (!atomic_dec_and_test(&count_initcall_threads)) {
+			schedule();
+			finish_wait(&group_waitqueue, &wait);
+			continue;
+		}
+		atomic_inc(&current_group);
+		atomic_set(&count_initcall_threads, num_threads);
+		if (++group >= count_groups) {
+			/* all thread groups processed */
+			atomic_set(&shared_counter,
+				__annotated_initcall_end -
+					__annotated_initcall_start);
+			wake_up_all(&group_waitqueue);
+			finish_wait(&group_waitqueue, &wait);
+			break;
+		}
+		atomic_set(&ostart, tgroup[group].start);
+		atomic_set(&ocount, tgroup[group].length);
+		atomic_set(&shared_counter, tgroup[group].length);
+		wake_up_all(&group_waitqueue);
+		finish_wait(&group_waitqueue, &wait);
+	}
+	return initcall_thread_unordered(thread_nr);
+}
+#endif
+
+static void __init of_init_drivers_non_threaded(void)
 {
 	unsigned i;
 	struct _annotated_initcall *ac;
 
 	if (!of_init_build_order()) {
 		for (i = 0; i < order.count; ++i)
-			init_if_matched(order.order[i]);
+			init_if_matched(order.order[i], 0);
 		of_init_free_order();
 	}
 	ac = __annotated_initcall_start;
@@ -461,3 +645,56 @@ void __init of_init_drivers(void)
 		}
 	}
 }
+
+void __init of_init_drivers(void)
+{
+	unsigned count_annotated;
+
+	count_annotated = __annotated_initcall_end - __annotated_initcall_start;
+	if (!count_annotated)
+		return;
+
+#ifndef CONFIG_OF_DEPENDENCIES_PARALLEL
+	of_init_drivers_non_threaded();
+#else
+	if (CONFIG_OF_DEPENDENCIES_THREADS == 0)
+		num_threads = num_online_cpus();
+	else
+		num_threads = CONFIG_OF_DEPENDENCIES_THREADS;
+	if (num_threads < 2) {
+		of_init_drivers_non_threaded();
+		return;
+	}
+	if (!of_init_build_order()) {
+		if (count_groups > 1) {
+			unsigned i;
+
+			atomic_set(&count_initcall_threads, num_threads);
+			atomic_set(&ostart, tgroup[1].start);
+			atomic_set(&ocount, tgroup[1].length);
+			atomic_set(&shared_counter, tgroup[1].length);
+			atomic_set(&current_group, 1);
+			for (i = 0; i < num_threads; ++i)
+				kthread_run(initcall_thread, (void *)i,
+							"initcalls");
+			wait_for_completion(&initcall_thread_done);
+			reinit_completion(&initcall_thread_done);
+		}
+		of_init_free_order();
+	} else {
+		/*
+		 * Building order failed (dependency circle).
+		 * Try to boot anyway by calling all initcalls unordered.
+		 */
+		unsigned i;
+
+		atomic_set(&shared_counter, count_annotated);
+		num_threads = min(count_annotated, num_threads);
+		atomic_set(&count_initcall_threads, num_threads);
+		for (i = 0; i < num_threads; ++i)
+			kthread_run(initcall_thread_unordered, (void *)i,
+							"initcalls");
+		wait_for_completion(&initcall_thread_done);
+	}
+#endif
+}
-- 
2.1.0

[PATCH 2/2] deps: avoid multiple calls to memmove by just setting duplicates to 0

[Alexander Holler]

Besides make the code (almost unmeasurable) faster, this makes the
ugly looking loop I've used to remove duplicates cleaner.
Disadvantage is that the ordered array now contains 'holes' and the
number of elements in the array doesn't really match the number
of ordered elements. But this only makes a difference for debugging.

This patch also adds an of_node_put() for duplicate dt nodes, something
I previously had forgotten.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/of/of_dependencies.c | 34 ++++++++++++++++++++--------------
 1 file changed, 20 insertions(+), 14 deletions(-)

diff --git a/drivers/of/of_dependencies.c b/drivers/of/of_dependencies.c
index 85cef84..ac0c0f5 100644
--- a/drivers/of/of_dependencies.c
+++ b/drivers/of/of_dependencies.c
@@ -323,21 +323,20 @@ static bool __init all_compatibles_same(struct device_node *node1,
 /*
  * The order is based on devices but we are calling drivers.
  * Therefor the order contains some drivers more than once.
- * Remove the duplicates.
+ * Disable the duplicates by setting them to 0.
  */
-static void __init of_init_remove_duplicates(void)
+static void __init of_init_disable_duplicates(void)
 {
 	unsigned i, j;
 
 	for (i = 1; i < order.count; ++i)
 		for (j = 0; j < i; ++j) {
+			if (!order.order[j])
+				continue;
 			if (all_compatibles_same(order.order[j],
 							order.order[i])) {
-				--order.count;
-				memmove(&order.order[i], &order.order[i+1],
-					(order.count - i) *
-						sizeof(order.order[0]));
-				--i;
+				of_node_put(order.order[i]);
+				order.order[i] = 0;
 				break;
 			}
 		}
@@ -416,7 +415,8 @@ static void __init build_tgroups(void)
 	unsigned dist = 0;
 
 	for (i = 0; i < order.count; ++i) {
-		if (distance[order.order[i]->phandle] != dist) {
+		if (order.order[i] &&
+				distance[order.order[i]->phandle] != dist) {
 			dist = distance[order.order[i]->phandle];
 			count_groups++;
 			tgroup[count_groups].start = i;
@@ -436,6 +436,8 @@ static void __init of_init_print_order(void)
 
 	pr_info("Initialization order:\n");
 	for (i = 0; i < order.count; ++i) {
+		if (!order.order[i])
+			continue;
 #ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
 		pr_info("init %u 0x%x (group %u)", i,
 			order.order[i]->phandle,
@@ -496,10 +498,10 @@ static int __init of_init_build_order(void)
 
 #ifdef CONFIG_OF_DEPENDENCIES_PARALLEL
 	build_order_by_distance();
-	of_init_remove_duplicates();
+	of_init_disable_duplicates();
 	build_tgroups();
 #else
-	of_init_remove_duplicates();
+	of_init_disable_duplicates();
 #endif
 
 #ifdef CONFIG_OF_DEPENDENCIES_PRINT_INIT_ORDER
@@ -516,7 +518,8 @@ static void __init of_init_free_order(void)
 	unsigned i;
 
 	for (i = 0; i < order.count; ++i)
-		of_node_put(order.order[i]);
+		if (order.order[i])
+			of_node_put(order.order[i]);
 	order.count = 0;
 	/* remove_new_phandles(); */
 }
@@ -593,8 +596,10 @@ static int __init initcall_thread(void *thread_nr)
 		start = atomic_read(&ostart);
 		count = atomic_read(&ocount);
 		while ((i = atomic_dec_return(&shared_counter)) >= 0)
-			init_if_matched(order.order[start + count - 1 - i],
-					(unsigned)thread_nr);
+			if (order.order[start + count - 1 - i])
+				init_if_matched(
+					order.order[start + count - 1 - i],
+					 (unsigned)thread_nr);
 		prepare_to_wait(&group_waitqueue, &wait, TASK_UNINTERRUPTIBLE);
 		if (!atomic_dec_and_test(&count_initcall_threads)) {
 			schedule();
@@ -629,7 +634,8 @@ static void __init of_init_drivers_non_threaded(void)
 
 	if (!of_init_build_order()) {
 		for (i = 0; i < order.count; ++i)
-			init_if_matched(order.order[i], 0);
+			if (order.order[i])
+				init_if_matched(order.order[i], 0);
 		of_init_free_order();
 	}
 	ac = __annotated_initcall_start;
-- 
2.1.0

Re: [PATCH 0/2] deps: parallel initialization of (device-)drivers

[Alexander Holler]

Am 09.09.2015 um 20:35 schrieb Alexander Holler:
> Hello,
>
> as already mentioned, I've implemented the stuff to initialize drivers
> in parallel. What follows are two patches to be used on top of my
> already posted series (for 4.2) which implements annotated initcalls
> and DT based dependencies.
>
> But be warned: many drivers which are in the same initcall level
> still depend on the link order given by the Makefile and directoy
> (-name) and therefor will fail. That means without moving them to other
> initcall levels or explicit dependencies (which are a TODO) for these
> drivers, the whole stuff currently works only for some configurations
> and you likely will need to add several patches for your board.

Another update: I've now did what I've described as TODO above. That 
means I have everything working to parallelize the (whole) init-system 
regardless the arch or DT/ACPI or whatever.

Cleaning up the new stuff to post it here will need some time. And 
collecting the _mandatory_ dependencies to parallelize all static linked 
drivers (from all initcall levels) will need much more time. Even on 
systems where most stuff is build as a module, the list of drivers 
initialized through initcalls is usually several dozens or even 
hundreds. You might use 'grep initcall_ System.map | wc -l' to get an idea.

Therefor I don't know when I will post cleaned up patches and/or some 
benchmark times. The interest seems rather low.

Regards,

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html