| Message ID | 1399913280-6915-3-git-send-email-holler@ahsoftware.de (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > 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@ahsoftware.de> Hi Alexander, Thanks for looking at this. It is a difficult problem. I've made comments below, but first I've got some general comments... First, I'm going to be very cautious about this. It is a complicated piece of code making the device initialization process a lot more complicated than it already is. I'm the first one to admit that deferred probe handles the problem in quite a naive manner, but it is simple, correct (when drivers support deferred probe) and easy to audit. This series digs deep into the registration order of *both* devices and drivers which gives me the heebee jeebees. Personally, I think the parts of this patch that manipulate the device registration order is entirely the wrong way to handle it. If anything, I would say continue to register the devices, even if the dependencies are unmet. Instead, I would focus on the driver core (drivers/base) to catch device probe attempts when a known dependency is not met, remember it, and perform the probe after the other driver shows up. That is also going to be a complicated bit of code, but it works for every kind of device, not just platform_devices, and has far less impact on the platform setup code. BTW, this has to be able to work at the level of struct device instead of struct platform_device. There are far more kinds of devices than just platform_device, and they all have the same problem. Also, may I suggest that the more pieces that you can break this series up into, the greater chance you'll have of getting a smaller subset merged earlier if it can be proven to be useful on its own. > --- > 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(); What happens when of_init_build_order() fails? Does the whole system fall over? > +#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 Stale hunk left in patch? > 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@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) */ Is it possible for this to be dynamic? DT platforms range from small to very very large. > + > +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; I would suggest splitting the core graph support into a separate patch to keep things smaller and to keep the behaviour changes separate from the support function additions. > + > + > +/* Copied from drivers/of/base.c (because it's lockless). */ Copying isn't a good idea. The function will need to be made accessible to other files in the drivers/of directory. > +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(); Can the sort be performed incrementally? The DT is a dynamic structure on some platforms. Search for OF_RECONFIG_. There is work in progress to add overlay support to the device tree so that batches of new nodes can be added to the tree after userspace has started. The dependency code will need to handle that situation gracefully. > + > + if (graph.finished) > + return -EINVAL; /* cycle found */ > + > + /* of_init_print_order(); */ If you wrap of_init_print_order with a #ifdef DEBUG/#else/#endif, then you don't need to comment out the call to 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; I don't like that of_init_create_devices() has a completely different calling convention from of_platform_populate(). of_platform_populate() is passed a match table for devices that are to act as buses (which means register the children also). This function is passed a blacklist instead which is a completely different semantic. That means it cannot be used by device drivers that register their own children and it has to make a lot of assumptions about what should and should not be registered as platform_devices. How does the dependency code decide which devices can be platform_devices? It's not clear to me from what I've read so far. > + > + 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(); */ > +} I could use some help understanding what is being done here. It looks like it is going through and only registering devices that have a dependency parent already created, or don't have a parent at all. Am I correct? It looks like this patch alone will break the kernel because it depends also on the functionality in patch 5. The patches would need to be reordered to handle that situation. > +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 This change has been proposed many times in several forms. I've pushed back hard against it because it is absolutely normal for multiple struct devices to reference the same device tree node. There is a patch that Pawel has submitted which sets a flag in the of_node if the of_platform_populate() path has been used to create a struct device. It's a little crude, but it does handle the problem of multiple passes through of_platform_populate(). I expect it will show up in mainline in v3.16 > }; > > #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@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> > + > +/* > + * 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. > + */ Note: Convention in the kernel (maybe not everywhere, but certainly in the DT code) is for function documentation to be in the .c file, not the header. We use the kerneldoc format. Documentation/kernel-doc-nano-HOWTO.txt > +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 linux-kernel" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > Please read the FAQ at http://www.tux.org/lkml/
Am 14.05.2014 16:05, schrieb Grant Likely: > On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> 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@ahsoftware.de> > > Hi Alexander, > > Thanks for looking at this. It is a difficult problem. I've made > comments below, but first I've got some general comments... > > First, I'm going to be very cautious about this. It is a complicated > piece of code making the device initialization process a lot more > complicated than it already is. I'm the first one to admit that deferred > probe handles the problem in quite a naive manner, but it is simple, > correct (when drivers support deferred probe) and easy to audit. This > series digs deep into the registration order of *both* devices and > drivers which gives me the heebee jeebees. Sure, but the approach I present is deterministic. The deferred stuff, while it's simple and works, is imho just a workaround. Besides that this series isn't about pro or cons of the deferred probe, the deferred probes I have seen where just the reason why I had a look at what happens. To conclude, I like the deferred probe because it fixes problems, but trying to do things right is much better. And there are already many workarounds trying fix the initialization order (e.g. drivers which classify themself as a subsys), so starting do it right makes imho sense. So, I'm sorry if you see this feature as an attack on the deferred probe stuff, it isn't meant as such, no offense here or there. > Personally, I think the parts of this patch that manipulate the device registration > order is entirely the wrong way to handle it. If anything, I would say > continue to register the devices, even if the dependencies are unmet. That would just be a removal of 2 lines. I've no problem with that. ;) > Instead, I would focus on the driver core (drivers/base) to catch > device probe attempts when a known dependency is not met, remember it, > and perform the probe after the other driver shows up. That is also > going to be a complicated bit of code, but it works for every kind of > device, not just platform_devices, and has far less impact on the > platform setup code. > > BTW, this has to be able to work at the level of struct device instead > of struct platform_device. There are far more kinds of devices than just > platform_device, and they all have the same problem. Changing to care for devices instead of just drivers is easy to do. > Also, may I suggest that the more pieces that you can break this series > up into, the greater chance you'll have of getting a smaller subset > merged earlier if it can be proven to be useful on its own. Hmm, I don't really care if that will be merged. I have no motivation to fight with Linux kernel maintainers and I don't know if I will spend the necessary time to do so. >> +#ifdef CONFIG_OF_DEPENDENCIES >> + if (!of_init_build_order(NULL, NULL)) >> + of_init_create_devices(NULL, NULL); >> + else >> + of_init_free_order(); > > What happens when of_init_build_order() fails? Does the whole system > fall over? Yes. The only reason it can fail is when there is a cycle, and dtc checks (and fails) for that when building the blob (dtb). > >> +#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 > > Stale hunk left in patch? See here: https://lkml.org/lkml/2014/5/14/102 This are NOT patches meant for final merging! > I would suggest splitting the core graph support into a separate patch > to keep things smaller and to keep the behaviour changes separate from > the support function additions. Could be done. > >> + >> + >> +/* Copied from drivers/of/base.c (because it's lockless). */ > > Copying isn't a good idea. The function will need to be made accessible > to other files in the drivers/of directory. See above. >> +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(); > > Can the sort be performed incrementally? The DT is a dynamic structure > on some platforms. Search for OF_RECONFIG_. There is work in progress to > add overlay support to the device tree so that batches of new nodes can > be added to the tree after userspace has started. The dependency code > will need to handle that situation gracefully. The stuff I present is only about what happens before userspace starts and is all gone away when userspace start. I know about the overlay support (e.g. for bbb-capes), but I don't care. So there is no need to think about what happens if such happens. > I don't like that of_init_create_devices() has a completely different > calling convention from of_platform_populate(). of_platform_populate() > is passed a match table for devices that are to act as buses (which > means register the children also). This function is passed a blacklist > instead which is a completely different semantic. Acting on buses is a workaround. > > That means it cannot be used by device drivers that register their own > children and it has to make a lot of assumptions about what should and > should not be registered as platform_devices. > > How does the dependency code decide which devices can be > platform_devices? It's not clear to me from what I've read so far. Dependencies currently are only considered on stuff which has a "compatibility" property, thus drivers. I wanted to get the drivers loaded in order, not really caring for devices. Let me quote from (outdated) ldd3: "For the most part, the Linux device model code takes care of all these considerations without imposing itself upon driver authors. It sits mostly in the background; direct interaction with the device model is generally handled by bus-level logic and various other kernel subsystems. As a result, many driver authors can ignore the device model entirely, and trust it to take care of itself." So do I. ;) > >> + >> + 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(); */ >> +} > > I could use some help understanding what is being done here. It looks > like it is going through and only registering devices that have a > dependency parent already created, or don't have a parent at all. Am I > correct? Yes, that part assumes that if a parent is present, the parent is needed and it doesn't make sense to create a device if the parent already failed. That are those two lines I mentioned above. > > It looks like this patch alone will break the kernel because it depends > also on the functionality in patch 5. The patches would need to be > reordered to handle that situation. I currently don't care if this feature breaks something. Therefor it is marked in big letters as experimental. But I already see you don't want it and you see it all as an offense. Regards, Alexander Holler
Am 14.05.2014 16:05, schrieb Grant Likely: >> + >> + if (graph.finished) >> + return -EINVAL; /* cycle found */ >> + >> + /* of_init_print_order(); */ > > If you wrap of_init_print_order with a #ifdef DEBUG/#else/#endif, then > you don't need to comment out the call to of_init_print_order(). To explain why I didn't use DEBUG here: DEBUG enables a lot of distracting messages. which is true for CONFIG_DEBUG_DRIVER too. Therefor I often prefer to use just pr_info("AHO: ..."); with which I print only stuff I want (and can easily grep for). And as said, the patches I presented are meant for evaluation. I did patches without discussing them before in order to avoid endless discussion which likely never would have found an end and therfor would have prevented a start. So now you already have some to play and test with, without anyone had to discuss stuff before. ;) Regards, Alexander Holler
Am 14.05.2014 16:49, schrieb Alexander Holler: > Am 14.05.2014 16:05, schrieb Grant Likely: >> On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler >> <holler@ahsoftware.de> wrote: >> Personally, I think the parts of this patch that manipulate the device >> registration >> order is entirely the wrong way to handle it. If anything, I would say >> continue to register the devices, even if the dependencies are unmet. (...) >> How does the dependency code decide which devices can be >> platform_devices? It's not clear to me from what I've read so far. > > Dependencies currently are only considered on stuff which has a > "compatibility" property, thus drivers. I wanted to get the drivers > loaded in order, not really caring for devices. Let me quote from > (outdated) ldd3: > > "For the most part, the Linux device model code takes care of all these > considerations without imposing itself upon driver authors. It sits > mostly in the background; direct interaction with the device model is > generally handled by bus-level logic and various other kernel > subsystems. As a result, many driver authors can ignore the device model > entirely, and trust it to take care of itself." > > So do I. ;) To explain a bit further, I've started with totally ignoring the device model just careing for the order in why drivers will be initialized. Than the device model did come into my way. ;) But it isn't any problem at all to extend the stuff to care for devices. That even would reduce some code in dtc with the disadvantage that the sizes of blobs will slightly increase a bit more, because they then would include dependencies to devices too (instead of just dependencies between drivers). So I'm absolutely open here. If using dependencies between devices is necessary or has advantages, that could be changed with changing a few lines. Regards, Alexander Holler
On Wed, 14 May 2014 16:49:05 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > Am 14.05.2014 16:05, schrieb Grant Likely: > > On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > >> 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@ahsoftware.de> > > > > Hi Alexander, > > > > Thanks for looking at this. It is a difficult problem. I've made > > comments below, but first I've got some general comments... > > > > First, I'm going to be very cautious about this. It is a complicated > > piece of code making the device initialization process a lot more > > complicated than it already is. I'm the first one to admit that deferred > > probe handles the problem in quite a naive manner, but it is simple, > > correct (when drivers support deferred probe) and easy to audit. This > > series digs deep into the registration order of *both* devices and > > drivers which gives me the heebee jeebees. > > Sure, but the approach I present is deterministic. The deferred stuff, > while it's simple and works, is imho just a workaround. Besides that > this series isn't about pro or cons of the deferred probe, the deferred > probes I have seen where just the reason why I had a look at what > happens. To conclude, I like the deferred probe because it fixes > problems, but trying to do things right is much better. And there are > already many workarounds trying fix the initialization order (e.g. > drivers which classify themself as a subsys), so starting do it right > makes imho sense. > > So, I'm sorry if you see this feature as an attack on the deferred probe > stuff, it isn't meant as such, no offense here or there. Hahaha, calm down. I'm not upset nor do I see it as an attack on deferred probe.... Okay, maybe I do, but I've been asking people to attack deferred probe for years! It works, but it is by no means optimized. > > Personally, I think the parts of this patch that manipulate the device registration > > order is entirely the wrong way to handle it. If anything, I would say > > continue to register the devices, even if the dependencies are unmet. > > That would just be a removal of 2 lines. I've no problem with that. ;) > > > Instead, I would focus on the driver core (drivers/base) to catch > > device probe attempts when a known dependency is not met, remember it, > > and perform the probe after the other driver shows up. That is also > > going to be a complicated bit of code, but it works for every kind of > > device, not just platform_devices, and has far less impact on the > > platform setup code. > > > > BTW, this has to be able to work at the level of struct device instead > > of struct platform_device. There are far more kinds of devices than just > > platform_device, and they all have the same problem. > > Changing to care for devices instead of just drivers is easy to do. > > > Also, may I suggest that the more pieces that you can break this series > > up into, the greater chance you'll have of getting a smaller subset > > merged earlier if it can be proven to be useful on its own. > > Hmm, I don't really care if that will be merged. I have no motivation to > fight with Linux kernel maintainers and I don't know if I will spend the > necessary time to do so. The people you need to convince are Rob, Greg, and me, and you've got my attention. If I'm convinced, then I can probably convince Greg also. You've got an interesting approach, and I hope you won't give up on it. > >> +#ifdef CONFIG_OF_DEPENDENCIES > >> + if (!of_init_build_order(NULL, NULL)) > >> + of_init_create_devices(NULL, NULL); > >> + else > >> + of_init_free_order(); > > > > What happens when of_init_build_order() fails? Does the whole system > > fall over? > > Yes. The only reason it can fail is when there is a cycle, and dtc > checks (and fails) for that when building the blob (dtb). > > > > >> +#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 > > > > Stale hunk left in patch? > > See here: https://lkml.org/lkml/2014/5/14/102 > > This are NOT patches meant for final merging! Understood. No malice is intended. That's just the normal stuff that comes up in review. > > I would suggest splitting the core graph support into a separate patch > > to keep things smaller and to keep the behaviour changes separate from > > the support function additions. > > Could be done. > > > > >> + > >> + > >> +/* Copied from drivers/of/base.c (because it's lockless). */ > > > > Copying isn't a good idea. The function will need to be made accessible > > to other files in the drivers/of directory. > > See above. > > > >> +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(); > > > > Can the sort be performed incrementally? The DT is a dynamic structure > > on some platforms. Search for OF_RECONFIG_. There is work in progress to > > add overlay support to the device tree so that batches of new nodes can > > be added to the tree after userspace has started. The dependency code > > will need to handle that situation gracefully. > > The stuff I present is only about what happens before userspace starts > and is all gone away when userspace start. I know about the overlay > support (e.g. for bbb-capes), but I don't care. So there is no need to > think about what happens if such happens. ok. As long as there is no impact, then I don't have an issue. > > > I don't like that of_init_create_devices() has a completely different > > calling convention from of_platform_populate(). of_platform_populate() > > is passed a match table for devices that are to act as buses (which > > means register the children also). This function is passed a blacklist > > instead which is a completely different semantic. > > Acting on buses is a workaround. Can you elaborate on what you mean? The of_platform_populate() semantics are quite specific because they are the filter for which devices are going to be platform_devices. > > > > > That means it cannot be used by device drivers that register their own > > children and it has to make a lot of assumptions about what should and > > should not be registered as platform_devices. > > > > How does the dependency code decide which devices can be > > platform_devices? It's not clear to me from what I've read so far. > > Dependencies currently are only considered on stuff which has a > "compatibility" property, thus drivers. I wanted to get the drivers > loaded in order, not really caring for devices. Let me quote from > (outdated) ldd3: > > "For the most part, the Linux device model code takes care of all these > considerations without imposing itself upon driver authors. It sits > mostly in the background; direct interaction with the device model is > generally handled by bus-level logic and various other kernel > subsystems. As a result, many driver authors can ignore the device model > entirely, and trust it to take care of itself." > > So do I. ;) of_platform_populate() currently makes the decision for platform_devices. Other busses do the same for their own child devices. In this case after calculating the dependency information we would want to make it available to all bus types so that they to can take advantage of dependency information. > > > > >> + > >> + 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(); */ > >> +} > > > > I could use some help understanding what is being done here. It looks > > like it is going through and only registering devices that have a > > dependency parent already created, or don't have a parent at all. Am I > > correct? > > Yes, that part assumes that if a parent is present, the parent is needed > and it doesn't make sense to create a device if the parent already > failed. That are those two lines I mentioned above. Ah, so it is just the normal node's parent, not a dependency link. okay. > > It looks like this patch alone will break the kernel because it depends > > also on the functionality in patch 5. The patches would need to be > > reordered to handle that situation. > > I currently don't care if this feature breaks something. Therefor it is > marked in big letters as experimental. But I already see you don't want > it and you see it all as an offense. I'm sorry you feel that way. I actually have quite the opposite opinion. I'm asking the questions and pushing back to a) make sure I understand what you're doing, and b) figure out wether it can be brought into a state where it can be merged. g.
Am 14.05.2014 22:06, schrieb Grant Likely: > On Wed, 14 May 2014 16:49:05 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> Am 14.05.2014 16:05, schrieb Grant Likely: >>> On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> Hmm, I don't really care if that will be merged. I have no motivation to >> fight with Linux kernel maintainers and I don't know if I will spend the >> necessary time to do so. > > The people you need to convince are Rob, Greg, and me, and you've got my > attention. If I'm convinced, then I can probably convince Greg also. > You've got an interesting approach, and I hope you won't give up on it. Sorry, but that point of the view is already a problem. Why do I have to convince you people? To summarize: Linux kernel maintainers - don't like code they haven't written theirself, - don't like code which doesn't look like they have written it theirself, - don't like ideas they haven't had themself, - do feel good in their closed group they have formed, ... You see, I long have given up. The reason I still posted these patches is just because I don't care anymore about Linux kernel maintainers at all. I was prepared that I do that just for the fun of annoying some Linux kernel maintainers. I've already decided some time ago that I just will post my patches once to the LKML (so that other poor Linux kernel users may find them) and will ignore Linux kernel maintainers. Sorry, but I have a long and very unpleasant history in dealing with Linux kernel maintainers, and they already have called me almost anything like "ugly code writer", "frustrated" and such things more. Fortunately I'm too old to care about such, that's why I still post patches (besides that I like to solve problems and help other people). ;) Regards, Alexander Holler
On Wed, 14 May 2014 23:10:39 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > Am 14.05.2014 22:06, schrieb Grant Likely: > > On Wed, 14 May 2014 16:49:05 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > >> Am 14.05.2014 16:05, schrieb Grant Likely: > >>> On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > > >> Hmm, I don't really care if that will be merged. I have no motivation to > >> fight with Linux kernel maintainers and I don't know if I will spend the > >> necessary time to do so. > > > > The people you need to convince are Rob, Greg, and me, and you've got my > > attention. If I'm convinced, then I can probably convince Greg also. > > You've got an interesting approach, and I hope you won't give up on it. > > Sorry, but that point of the view is already a problem. Why do I have to > convince you people? > > To summarize: > > Linux kernel maintainers > > - don't like code they haven't written theirself, > - don't like code which doesn't look like they have written it theirself, > - don't like ideas they haven't had themself, > - do feel good in their closed group they have formed, I'm sorry that you feel that way and that you don't want to continue with this. Best wishes. g.
Wed, 14 May 2014 23:10:39 +0200 ?? Alexander Holler <holler@ahsoftware.de>: > Am 14.05.2014 22:06, schrieb Grant Likely: > > On Wed, 14 May 2014 16:49:05 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > >> Am 14.05.2014 16:05, schrieb Grant Likely: > >>> On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > > >> Hmm, I don't really care if that will be merged. I have no motivation to > >> fight with Linux kernel maintainers and I don't know if I will spend the > >> necessary time to do so. > > > > The people you need to convince are Rob, Greg, and me, and you've got my > > attention. If I'm convinced, then I can probably convince Greg also. > > You've got an interesting approach, and I hope you won't give up on it. > > Sorry, but that point of the view is already a problem. Why do I have to > convince you people? > > To summarize: > > Linux kernel maintainers > > - don't like code they haven't written theirself, > - don't like code which doesn't look like they have written it theirself, > - don't like ideas they haven't had themself, > - do feel good in their closed group they have formed, > ... Very correct and well said. For many subsystems is it as is, we cannot break these barriers. ---
Hi, On 14.05.2014 16:05, Grant Likely wrote: > On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> 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@ahsoftware.de> > > Hi Alexander, > > Thanks for looking at this. It is a difficult problem. I've made > comments below, but first I've got some general comments... > > First, I'm going to be very cautious about this. It is a complicated > piece of code making the device initialization process a lot more > complicated than it already is. I'm the first one to admit that deferred > probe handles the problem in quite a naive manner, but it is simple, > correct (when drivers support deferred probe) and easy to audit. This > series digs deep into the registration order of *both* devices and > drivers which gives me the heebee jeebees. > > Personally, I think the parts of this patch that manipulate the device registration > order is entirely the wrong way to handle it. If anything, I would say > continue to register the devices, even if the dependencies are unmet. > Instead, I would focus on the driver core (drivers/base) to catch > device probe attempts when a known dependency is not met, remember it, > and perform the probe after the other driver shows up. That is also > going to be a complicated bit of code, but it works for every kind of > device, not just platform_devices, and has far less impact on the > platform setup code. Grant, I tend to disagree with you on this. While Alexander's solution has certain flaws (that I'm going to list further in my reply), I also believe that an approach based on device registration order is most likely the way to go. As compared to other possible approaches, here is the list of advantages I can see (in random order): 1) If compared with resource-based approach, when you detect dependencies at runtime, based on existing resource specifiers (GPIOs, clocks, etc.), you don't need to change anything in the implementation whenever a new kind of resources is introduced. Moreover, there is no need to make device probing code aware of any resources or dependencies, because all you need to do is to register devices in certain order, as defined by precompiled dependency lists. 2) If implemented properly, it helps solving problem of binding proper driver to a device with multiple compatible strings. Current way of handling this by Linux is _broken_, because the device will be bound to first driver that shows up and contains matching compatible string in its match table. Notice that this way the whole idea of having multiple compatible strings specified from most specific to most generic is made useless. Now you may wonder how both problems relate. Basically in both cases you need to wait until drivers for devices are available (e.g. registered in system-wide list), either to guarantee that registering a device means probing it (in first case) or to look through the list of available drivers and select the one that is a best match (in second case). 3) DeviceTree is not the only firmware "interface" supported by Linux and so I'd be careful with pushing this into generic driver core that is also shared with board files and ACPI and possibly something else I'm not aware of. Moreover, I think the existing driver core is already quite complex and complicating it even more might not be the best idea, unless really the only option. 4) This approach is far less complicated than anything mentioned above. What's so complicated in creating a graph of devices and registering them in certain order? > > BTW, this has to be able to work at the level of struct device instead > of struct platform_device. There are far more kinds of devices than just > platform_device, and they all have the same problem. Agreed. > Also, may I suggest that the more pieces that you can break this series > up into, the greater chance you'll have of getting a smaller subset > merged earlier if it can be proven to be useful on its own. Agreed. It is usually a good idea to separate things that could live on their own and be useful. Now, I'll spare myself from judging the code, as until we get an accepted design, I don't think there is any point in discussing about implementation details, not even mentioning things like coding style (which is important, but not when much of the code might still be rewritten completely). OK, so I mentioned above what I like in this kind of approach. Now let's move to what I don't like. I think the part that alters driver registration and initcalls isn't really necessary. With current code, we can see that initcalls themselves (not driver code in terms of driver model) are already well ordered, as things happening there seems to work, without any need to defer anything. Now Alexander's approach relies on module_platform_driver() and similar macros to obtain the list of platform_drivers in the system, but I think this isn't necessary either. Now this is just a bit of guessing, as I still haven't been able to allocate time to take a deeper look into initcall and driver code, but what if we let the initcalls do their work, let's say up to late_initcall level and only then register drivers in our precomputed order? We seem to be already relying an assumption that on late_initcall level the devices should be already probed, as we have various calls disabling unused resources, such as regulators and clocks, at this level. I can see certain drivers being registered in late_initcalls, but this would be after our device registration, so most of dependencies should be already there and if not, we still have deferred probing. With such design in place, we would be able to also solve the other problem I mentioned above, the problem of matching devices with most appropriate drivers. Since at device registration and probing time, (almost) all the drivers would be already available, the matching code could select the right one to bind. Alright, that's my take on this. Looking forward to your comments. Best regards, Tomasz
Am 16.05.2014 13:00, schrieb Grant Likely: > On Wed, 14 May 2014 23:10:39 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> Am 14.05.2014 22:06, schrieb Grant Likely: >>> On Wed, 14 May 2014 16:49:05 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >>>> Am 14.05.2014 16:05, schrieb Grant Likely: >>>>> On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: >> >>>> Hmm, I don't really care if that will be merged. I have no motivation to >>>> fight with Linux kernel maintainers and I don't know if I will spend the >>>> necessary time to do so. >>> >>> The people you need to convince are Rob, Greg, and me, and you've got my >>> attention. If I'm convinced, then I can probably convince Greg also. >>> You've got an interesting approach, and I hope you won't give up on it. >> >> Sorry, but that point of the view is already a problem. Why do I have to >> convince you people? >> >> To summarize: >> >> Linux kernel maintainers >> >> - don't like code they haven't written theirself, >> - don't like code which doesn't look like they have written it theirself, >> - don't like ideas they haven't had themself, >> - do feel good in their closed group they have formed, > > I'm sorry that you feel that way and that you don't want to continue > with this. Best wishes. Sorry to hit you with reality, but it just will not happen that I will try to convience any Linux kernel maintainer (anymore). It is their job to decide what they want and not mine to convince them. I offer code and arguments, but I will not offer my pride, ego or how you want to name it. If Linux kernel maintainers are unable to deal with the power they've got, that isn't my problem. Regards, Alexander Holler
Hi Tomasz, Thanks for weighing in on this. Thoughts and comments below. On Sat, 17 May 2014 16:24:19 +0200, Tomasz Figa <tomasz.figa@gmail.com> wrote: > Hi, > > On 14.05.2014 16:05, Grant Likely wrote: > > On Mon, 12 May 2014 18:47:53 +0200, Alexander Holler <holler@ahsoftware.de> wrote: > >> 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@ahsoftware.de> > > > > Hi Alexander, > > > > Thanks for looking at this. It is a difficult problem. I've made > > comments below, but first I've got some general comments... > > > > First, I'm going to be very cautious about this. It is a complicated > > piece of code making the device initialization process a lot more > > complicated than it already is. I'm the first one to admit that deferred > > probe handles the problem in quite a naive manner, but it is simple, > > correct (when drivers support deferred probe) and easy to audit. This > > series digs deep into the registration order of *both* devices and > > drivers which gives me the heebee jeebees. > > > > Personally, I think the parts of this patch that manipulate the device registration > > order is entirely the wrong way to handle it. If anything, I would say > > continue to register the devices, even if the dependencies are unmet. > > Instead, I would focus on the driver core (drivers/base) to catch > > device probe attempts when a known dependency is not met, remember it, > > and perform the probe after the other driver shows up. That is also > > going to be a complicated bit of code, but it works for every kind of > > device, not just platform_devices, and has far less impact on the > > platform setup code. > > Grant, I tend to disagree with you on this. While Alexander's solution > has certain flaws (that I'm going to list further in my reply), I also > believe that an approach based on device registration order is most > likely the way to go. As compared to other possible approaches, here is > the list of advantages I can see (in random order): > > 1) If compared with resource-based approach, when you detect > dependencies at runtime, based on existing resource specifiers (GPIOs, > clocks, etc.), you don't need to change anything in the implementation > whenever a new kind of resources is introduced. Moreover, there is no > need to make device probing code aware of any resources or dependencies, > because all you need to do is to register devices in certain order, as > defined by precompiled dependency lists. I think we can handle the source of dependencies separately from how those depenencies are used. I would rather not have a separate set of properties for dependency tracking because of the possiblity of it being made inconsistent, but I'm not flat out refusing. > 2) If implemented properly, it helps solving problem of binding proper > driver to a device with multiple compatible strings. Current way of > handling this by Linux is _broken_, because the device will be bound to > first driver that shows up and contains matching compatible string in > its match table. Notice that this way the whole idea of having multiple > compatible strings specified from most specific to most generic is made > useless. Now you may wonder how both problems relate. Basically in both > cases you need to wait until drivers for devices are available (e.g. > registered in system-wide list), either to guarantee that registering a > device means probing it (in first case) or to look through the list of > available drivers and select the one that is a best match (in second case). No argument here. > 3) DeviceTree is not the only firmware "interface" supported by Linux > and so I'd be careful with pushing this into generic driver core that is > also shared with board files and ACPI and possibly something else I'm > not aware of. Competely agree. Anything that goes in to driver core cannot be OF specific. If the driver core is modified, then it needs to be generically useful regardless of firmware interface. > Moreover, I think the existing driver core is already > quite complex and complicating it even more might not be the best idea, > unless really the only option. I think it actually is the only option. More below. > 4) This approach is far less complicated than anything mentioned above. > What's so complicated in creating a graph of devices and registering > them in certain order? As Alexander's patch series shows, merely manipulating the registration order of devices doesn't actually solve anything. For most platform devices, link order has a far large impact on probe order than registration order. Alexander had to hook into the driver registration patch to get the optimal probe order. For device order to be effective, all driver registration would need to occur before devices are registered (opposite of what we do now). The driver core is very simple in this regard. It accepts device and driver registration. When one gets registered, it immediately attempts to match against one of the others. Simple and easy to understand, but very non-deterministic behaviour. A lot of devices gets registered well before the driver, platform_devices especially. Other devices may very well show up afterwards, such as anything registered by another driver. For example, it is the responsibility of an i2c bus driver to register all the child i2c devices. By the time the i2c bus driver gets probed, the i2c drivers may already be available. And to make things worse, any device could depend on any other regardless of bus type. To actually solve the problem we need to deal with dependencies across all devices, regardless of bus type and regardless of whether or not the driver gets registered first. Tackling only device order, or only driver order misses a whole bunch of situations. Alexander's patch is the right idea here. It collects a bunch of driver registrations for an initcall without calling probe so that a sorting pass can be performed first. That approach can solve both the dependency order and the compatible list problems, and I think it is worth exploring. Having said that, there are some things that I worry about. I worry about the cost of doing dependency sorting, both in calculating the dependency tree and in pushing back probe calls to the end of initcalls. I worry that incorrect dependency information will cause some devices to not get bound (say because the kernel things the dependency isn't met when it actually is). Again, that doesn't mean I'm saying "don't do this, it is bad". It just means those are the corner cases and performance issues that I want to make sure are handled well. They are the questions I'll be asking before I merge anything. I'd be thrilled for someone to continue this work. > > Also, may I suggest that the more pieces that you can break this series > > up into, the greater chance you'll have of getting a smaller subset > > merged earlier if it can be proven to be useful on its own. > > I think the part that alters driver registration and initcalls isn't > really necessary. With current code, we can see that initcalls > themselves (not driver code in terms of driver model) are already well > ordered, as things happening there seems to work, without any need to > defer anything. Now Alexander's approach relies on > module_platform_driver() and similar macros to obtain the list of > platform_drivers in the system, but I think this isn't necessary either. Hahaha, as described above, this is where I think Alexander is on the right path!!! > Now this is just a bit of guessing, as I still haven't been able to > allocate time to take a deeper look into initcall and driver code, but > what if we let the initcalls do their work, let's say up to > late_initcall level and only then register drivers in our precomputed > order? If we can compute an ideal driver registration order, then this will always be a helpful thing to do. It doesn't catch everything, but it can make a lot of things better. Cheers, g. > We seem to be already relying an assumption that on late_initcall > level the devices should be already probed, as we have various calls > disabling unused resources, such as regulators and clocks, at this > level. I can see certain drivers being registered in late_initcalls, but > this would be after our device registration, so most of dependencies > should be already there and if not, we still have deferred probing. > > With such design in place, we would be able to also solve the other > problem I mentioned above, the problem of matching devices with most > appropriate drivers. Since at device registration and probing time, > (almost) all the drivers would be already available, the matching code > could select the right one to bind. > > Alright, that's my take on this. Looking forward to your comments. > > Best regards, > Tomasz
Am 18.05.2014 16:59, schrieb Grant Likely: > Hi Tomasz, > > Thanks for weighing in on this. Thoughts and comments below. > > On Sat, 17 May 2014 16:24:19 +0200, Tomasz Figa <tomasz.figa@gmail.com> wrote: > registration order. Alexander had to hook into the driver registration > patch to get the optimal probe order. For device order to be effective, I had to hook into the driver registration to get information about the (available) drivers. Without the hook it is currently impossible to identify drivers before they start doing things. To reccover, I had to solve several problems: - Getting dependencies (happens almost automatically by using phandle references) - Get them to the kernel (done by using a new property) - Build order (already a solved problem, think at make) - Identify available drivers (invented hook, "well done" is meant in regard to this feature, I needed a name and found "well done" apropriate because it too might stimulate driver authors to use it) - Check out how to handle/start/register devices and drivers (in order). I think the last one is the most unfinished and questionable part. The part to identify drivers could be done much better by linking an array of struct platform_driver, but in order to use such an array, drivers have to be done "well done" too (which means no action before probe). So that well-done hook can be seen as an intermediate step. > Having said that, there are some things that I worry about. I worry > about the cost of doing dependency sorting, both in calculating the > dependency tree and in pushing back probe calls to the end of initcalls. Building and calculating the dependency tree just needs a few ms and I think it's much faster than what is necessary afterwards, all those string compares to match drivers/devices. But this string compares already do happen, and I think this part could optimized a lot, when a list of drivers and their compatibility strings is available. Then it's possible to build a hash or e.g. radix tree which leads from the compatibility string to the available driver(s). > I worry that incorrect dependency information will cause some devices to > not get bound (say because the kernel things the dependency isn't met > when it actually is). All (not started) drivers and (unbounded) devices can still be registered/bound after those which appear in the order. That would be just like before. But as said, the whole handling which happens after the order was build is done quick & dirty, done with missing knownledge about the device model, and might contain a lot of bugs and even might need that some drivers will be changed. Therefor all changes disappear when CONFIG_OF_DEPENDENCIES is disabled. So tested platforms might use it (taking advantage of a deterministic order in order to get rid of hardcoded stuff to fix the order) and others don't have to care. So, as already said, I've posted these patches to make evaluation easy, without the need to discuss just ideas but something real to play with (in order to get something happen on this front, not just hardcoded hacks done in individual drivers because such passes maintainers easier). I didn't cared much about form or how to split those patches into more convenient parts. That is stuff where I just do it like a maintainer does want it. I did them as I like them, and I don't want to end up in a time wasting discussions about form, style or similiar questions. So if anyone would be comfortable to merge these patches (for evaluation by others) in other form or splitted in more parts, I will just hear and do. I also don't have any objections in changes in the stuff which happens after the order was build. In fact I would even like it if someone with more experience with the driver model would do it. I just had to do something there too, otherwise it would still have been just an idea which wouldn't offer much motivation to actually look at it. Regards, Alexander Holler
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@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; + /* 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@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> + +/* + * 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 */
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@ahsoftware.de> --- 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