Use the properties named 'dependencies' in binary device tree blobs to build
a dependency based initialization order for platform devices and drivers.
This is done by building a directed acyclic graph using an adjacency list
and doing a topological sort to retrieve the order in which devices/drivers
should be created/initialized.
Signed-off-by: Alexander Holler <holler@xxxxxxxxxxxxx>
---
arch/arm/kernel/setup.c | 20 +-
drivers/of/Kconfig | 10 +
drivers/of/Makefile | 1 +
drivers/of/of_dependencies.c | 403 ++++++++++++++++++++++++++++++++++++++++
drivers/of/platform.c | 32 +++-
include/linux/of.h | 15 ++
include/linux/of_dependencies.h | 61 ++++++
include/linux/of_platform.h | 5 +
8 files changed, 543 insertions(+), 4 deletions(-)
create mode 100644 drivers/of/of_dependencies.c
create mode 100644 include/linux/of_dependencies.h
diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
index 1e8b030..f67387d 100644
--- a/arch/arm/kernel/setup.c
+++ b/arch/arm/kernel/setup.c
@@ -19,6 +19,7 @@
#include <linux/seq_file.h>
#include <linux/screen_info.h>
#include <linux/of_platform.h>
+#include <linux/of_dependencies.h>
#include <linux/init.h>
#include <linux/kexec.h>
#include <linux/of_fdt.h>
@@ -787,10 +788,19 @@ static int __init customize_machine(void)
if (machine_desc->init_machine)
machine_desc->init_machine();
#ifdef CONFIG_OF
- else
+ else {
+#ifdef CONFIG_OF_DEPENDENCIES
+ if (!of_init_build_order(NULL, NULL))
+ of_init_create_devices(NULL, NULL);
+ else
+ of_init_free_order();
+#else
of_platform_populate(NULL, of_default_bus_match_table,
NULL, NULL);
#endif
+ }
+#endif
+
return 0;
}
arch_initcall(customize_machine);
@@ -914,7 +924,13 @@ void __init setup_arch(char **cmdline_p)
arm_pm_restart = mdesc->restart;
unflatten_device_tree();
-
+#ifdef CONFIG_OF_DEPENDENCIES
+ /*
+ * No alloc used in of_init_build_order(), therefor it would work
+ * already here too.
+ */
+ /* of_init_build_order(NULL, NULL); */
+#endif
arm_dt_init_cpu_maps();
psci_init();
#ifdef CONFIG_SMP
diff --git a/drivers/of/Kconfig b/drivers/of/Kconfig
index c6973f1..a7e1614 100644
--- a/drivers/of/Kconfig
+++ b/drivers/of/Kconfig
@@ -75,4 +75,14 @@ config OF_MTD
depends on MTD
def_bool y
+config OF_DEPENDENCIES
+ bool "Device Tree dependency based initialization order (EXPERIMENTAL)"
+ help
+ Enables dependency based initialization order of platform drivers.
+
+ For correct operation the binary DT blob should have been
+ populated with properties of type "dependencies".
+
+ If unsure, say N here.
+
endmenu # OF
diff --git a/drivers/of/Makefile b/drivers/of/Makefile
index efd0510..3888d9c 100644
--- a/drivers/of/Makefile
+++ b/drivers/of/Makefile
@@ -9,3 +9,4 @@ obj-$(CONFIG_OF_MDIO) += of_mdio.o
obj-$(CONFIG_OF_PCI) += of_pci.o
obj-$(CONFIG_OF_PCI_IRQ) += of_pci_irq.o
obj-$(CONFIG_OF_MTD) += of_mtd.o
+obj-$(CONFIG_OF_DEPENDENCIES) += of_dependencies.o
diff --git a/drivers/of/of_dependencies.c b/drivers/of/of_dependencies.c
new file mode 100644
index 0000000..7905172
--- /dev/null
+++ b/drivers/of/of_dependencies.c
@@ -0,0 +1,403 @@
+/*
+ * Code for building a deterministic initialization order based on dependencies
+ * defined in the device tree.
+ *
+ * Copyright (C) 2014 Alexander Holler <holler@xxxxxxxxxxxxx>
+ *
+ * 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;
+ /* 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 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 struct of_device_id *matches)
+{
+ 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;
+ }
+ if (unlikely(matches && !of_match_node(matches, dep)))
+ 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,
+ const struct of_device_id *matches)
+{
+ 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, matches);
+ if (unlikely(rc))
+ return rc;
+ parent = node; /* change the parent only if node is a driver */
+ }
+ if (unlikely(matches && !of_match_node(matches, node)))
+ return rc;
+ for_each_child_of_node(node, child) {
+ rc = add_deps(parent, child, matches);
+ if (unlikely(rc))
+ break;
+ }
+
+ return rc;
+}
+
+static void __init calc_max_phandle(void)
+{
+ struct device_node *np;
+ uint32_t t = 0;
+
+ for (np = of_allnodes; np; np = np->allnext)
+ if (np->phandle > t)
+ t = np->phandle;
+ order.max_phandle = t;
+ return;
+}
+
+/*
+static void __init remove_new_phandles(void)
+{
+ struct device_node *np;
+
+ for (np = of_allnodes; np; np = np->allnext)
+ if (np->phandle > order.old_max_phandle)
+ np->phandle = 0;
+}
+
+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);
+ pr_cont(" (parent 0x%x)\n",
+ order.parent_by_phandle[order.order[i]->phandle]);
+ }
+}
+*/
+
+int __init of_init_build_order(struct device_node *root,
+ const struct of_device_id *matches)
+{
+ struct device_node *child;
+ int rc = 0;
+
+ root = root ? of_node_get(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, matches);
+ if (unlikely(rc))
+ break;
+ }
+
+ of_node_put(root);
+ topological_sort();
+
+ if (graph.finished)
+ return -EINVAL; /* cycle found */
+
+ /* of_init_print_order(); */
+
+ return rc;
+}
+
+void __init of_init_create_devices(const struct of_device_id *blacklist,
+ const struct of_dev_auxdata *lookup)
+{
+ unsigned i;
+ struct platform_device *dev;
+
+ for (i = 0; i < order.count; ++i) {
+ struct device_node *node = order.order[i];
+ uint32_t parent_ph = order.parent_by_phandle[node->phandle];
+
+ if (unlikely(blacklist &&
+ of_match_node(blacklist, node))) {
+ of_node_put(node);
+ continue;
+ }
+ if (unlikely(parent_ph &&
+ !order.device_by_phandle[parent_ph])) {
+ /* init of parent failed */
+ of_node_put(node);
+ continue;
+ }
+ dev = of_dependencies_device_create(node, lookup,
+ order.device_by_phandle[parent_ph]);
+ if (dev)
+ order.device_by_phandle[node->phandle] = &dev->dev;
+ of_node_put(node);
+ }
+ /* remove_new_phandles(); */
+}
+
+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(); */
+}
diff --git a/drivers/of/platform.c b/drivers/of/platform.c
index 404d1da..0fe03ad 100644
--- a/drivers/of/platform.c
+++ b/drivers/of/platform.c
@@ -204,9 +204,13 @@ static struct platform_device *of_platform_device_create_pdata(
{
struct platform_device *dev;
+#ifdef CONFIG_OF_DEPENDENCIES
+ /* WARN_ON(np->dev_created); */
+ if (np->dev_created)
+ return np->dev_created;
+#endif
if (!of_device_is_available(np))
return NULL;
-
dev = of_device_alloc(np, bus_id, parent);
if (!dev)
return NULL;
@@ -229,7 +233,9 @@ static struct platform_device *of_platform_device_create_pdata(
platform_device_put(dev);
return NULL;
}
-
+#ifdef CONFIG_OF_DEPENDENCIES
+ np->dev_created = dev;
+#endif
return dev;
}
@@ -486,3 +492,25 @@ int of_platform_populate(struct device_node *root,
}
EXPORT_SYMBOL_GPL(of_platform_populate);
#endif /* CONFIG_OF_ADDRESS */
+
+#ifdef CONFIG_OF_DEPENDENCIES
+struct platform_device * __init of_dependencies_device_create(
+ struct device_node *bus,
+ const struct of_dev_auxdata *lookup,
+ struct device *parent)
+{
+ const struct of_dev_auxdata *auxdata;
+ const char *bus_id = NULL;
+ void *platform_data = NULL;
+
+ if (lookup) {
+ auxdata = of_dev_lookup(lookup, bus);
+ if (auxdata) {
+ bus_id = auxdata->name;
+ platform_data = auxdata->platform_data;
+ }
+ }
+ return of_platform_device_create_pdata(bus, bus_id, platform_data,
+ parent);
+}
+#endif
diff --git a/include/linux/of.h b/include/linux/of.h
index 435cb99..0bf0341 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -65,6 +65,21 @@ struct device_node {
unsigned int unique_id;
struct of_irq_controller *irq_trans;
#endif
+#ifdef CONFIG_OF_DEPENDENCIES
+ /*
+ * This is needed to keep track of already created devices.
+ * The reason is that some drivers call of_platform_populate()
+ * themself to populate e.g. their subtree. This would end up
+ * that some devices would be initialzed twice with a dependency
+ * based initialization. So instead of registering a device a second
+ * time, the second call to of_platform_device_create_pdata() just
+ * returns this pointer.
+ * If the feature of dependency based initialization will end up
+ * in mainline (and drivers will have fixed), this helper could
+ * be removed.
+ */
+ struct platform_device *dev_created;
+#endif
};
#define MAX_PHANDLE_ARGS 8
diff --git a/include/linux/of_dependencies.h b/include/linux/of_dependencies.h
new file mode 100644
index 0000000..e046ce2
--- /dev/null
+++ b/include/linux/of_dependencies.h
@@ -0,0 +1,61 @@
+#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@xxxxxxxxxxxxx>
+ *
+ * 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>
+
+/*
+ * Builds the initialization order.
+ *
+ * In favor of speed this function doesn't lock anything, so make sure nothing
+ * modifies the device tree while this functions runs.
+ *
+ * Will raise the refcount of all device tree nodes which ended up in the final
+ * initialization order by one.
+ *
+ * The phandle of some nodes will be modified (from 0 to a number) without
+ * adding a phandle property. But as this should not disturb anything, this
+ * change is not reversed after building the init order (for which the new
+ * phandles are temporarily necessary).
+ *
+ * This function is meant to be called only once.
+ */
+extern int of_init_build_order(struct device_node *root,
+ const struct of_device_id *matches);
+
+/*
+ * Replacement for of_platform_populate(). Creates all devices.
+ *
+ * By default it should be called with matches = NULL in order to create
+ * all devices. Reasoning is that every device contained in the DT which
+ * isn't disabled actually does exist (regardless if a driver is available
+ * or not).
+ *
+ * Decreases the node count of all nodes contained in the initialization order
+ * by one.
+ *
+ * This function is meant to be called only once.
+ */
+extern void of_init_create_devices(const struct of_device_id *matches,
+ const struct of_dev_auxdata *lookup);
+
+/*
+ * Decreases the node count of all nodes contained in the initialization order
+ * by one.
+ *
+ * This function is meant to be called only once instead of
+ * of_init_create_devices().
+ */
+extern void of_init_free_order(void);
+
+#endif /* _LINUX_OF_DEPENDENCIES_H */
diff --git a/include/linux/of_platform.h b/include/linux/of_platform.h
index 05cb4a9..04357ac 100644
--- a/include/linux/of_platform.h
+++ b/include/linux/of_platform.h
@@ -82,4 +82,9 @@ static inline int of_platform_populate(struct device_node *root,
}
#endif
+extern struct platform_device *of_dependencies_device_create(
+ struct device_node *bus,
+ const struct of_dev_auxdata *lookup,
+ struct device *parent);
+
#endif /* _LINUX_OF_PLATFORM_H */
--
1.8.3.1
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
