@@ -106,3 +106,349 @@ void add_dependencies(struct boot_info *bi)
{
process_nodes_props(bi->dt, bi->dt);
}
+
+/*
+ * The code below is in large parts a copy of drivers/of/of_dependencies.c
+ * in the Linux kernel. So both files do share the same bugs.
+ * The next few ugly defines do exist to keep the differences at a minimum.
+ */
+static struct node *tree;
+#define pr_cont(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_info(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_warn(format, ...) printf(format, ##__VA_ARGS__)
+#define pr_err(format, ...) fprintf(stderr, format, ##__VA_ARGS__)
+typedef cell_t __be32;
+#define device_node node
+#define full_name fullpath
+#define __initdata
+#define __init
+#define unlikely(a) (a)
+#define of_node_put(a)
+#define of_find_node_by_phandle(v) get_node_by_phandle(tree, v)
+#define __of_get_property(a, b, c) get_property(a, b)
+#define for_each_child_of_node(a, b) for_each_child(a, b)
+
+
+#define MAX_DT_NODES 1000 /* maximum number of vertices */
+#define MAX_EDGES (MAX_DT_NODES*2) /* maximum number of edges (dependencies) */
+
+struct edgenode {
+ uint32_t y; /* phandle */
+ struct edgenode *next; /* next edge in list */
+};
+
+/*
+ * Vertex numbers do correspond to phandle numbers. That means the graph
+ * does contain as much vertices as the maximum of all phandles.
+ * Or in other words, we assume that for all phandles in the device tree
+ * 0 < phandle < MAX_DT_NODES+1 is true.
+ */
+struct dep_graph {
+ struct edgenode edge_slots[MAX_EDGES]; /* used to avoid kmalloc */
+ struct edgenode *edges[MAX_DT_NODES+1]; /* adjacency info */
+ unsigned nvertices; /* number of vertices in graph */
+ unsigned nedges; /* number of edges in graph */
+ bool processed[MAX_DT_NODES+1]; /* which vertices have been processed */
+ bool include_node[MAX_DT_NODES+1]; /* which nodes to consider */
+ bool discovered[MAX_DT_NODES+1]; /* which vertices have been found */
+ bool finished; /* if true, cut off search immediately */
+};
+static struct dep_graph graph __initdata;
+
+struct init_order {
+ uint32_t max_phandle; /* the max used phandle */
+ uint32_t old_max_phandle; /* used to keep track of added phandles */
+ struct device_node *order[MAX_DT_NODES+1];
+ unsigned count;
+ /* Used to keep track of parent devices in regard to the DT */
+ uint32_t parent_by_phandle[MAX_DT_NODES+1];
+ struct device *device_by_phandle[MAX_DT_NODES+1];
+};
+static struct init_order order __initdata;
+
+
+/* Copied from drivers/of/base.c (because it's lockless). */
+static int __init __of_device_is_available(struct device_node *device)
+{
+ struct property *status;
+
+ if (!device)
+ return 0;
+
+ status = get_property(device, "status");
+ if (status == NULL)
+ return 1;
+
+ if (status->val.len > 0) {
+ if (!strcmp(status->val.val, "okay") ||
+ !strcmp(status->val.val, "ok"))
+ return 1;
+ }
+
+ return 0;
+}
+
+/*
+ * x is a dependant of y or in other words
+ * y will be initialized before x.
+ */
+static int __init insert_edge(uint32_t x, uint32_t y)
+{
+ struct edgenode *p; /* temporary pointer */
+
+ if (unlikely(x > MAX_DT_NODES || y > MAX_DT_NODES)) {
+ pr_err("Node found with phandle 0x%x > MAX_DT_NODES (%d)!\n",
+ x > MAX_DT_NODES ? x : y, MAX_DT_NODES);
+ return -EINVAL;
+ }
+ if (unlikely(!x || !y))
+ return 0;
+ if (unlikely(graph.nedges >= MAX_EDGES)) {
+ pr_err("Maximum number of edges (%d) reached!\n", MAX_EDGES);
+ return -EINVAL;
+ }
+ p = &graph.edge_slots[graph.nedges++];
+ graph.include_node[x] = 1;
+ graph.include_node[y] = 1;
+ p->y = y;
+ p->next = graph.edges[x];
+ graph.edges[x] = p; /* insert at head of list */
+
+ graph.nvertices = (x > graph.nvertices) ? x : graph.nvertices;
+ graph.nvertices = (y > graph.nvertices) ? y : graph.nvertices;
+ return 0;
+}
+
+static void __init print_node_name(uint32_t v)
+{
+ struct device_node *node;
+
+ node = of_find_node_by_phandle(v);
+ if (!node) {
+ pr_err("Node for phandle 0x%x not found", v);
+ return;
+ }
+ if (node->name)
+ pr_err("%s", node->name);
+ if (node->full_name)
+ pr_err(" (%s)", node->full_name);
+ of_node_put(node);
+}
+
+/*
+ * I would prefer to use the BGL (Boost Graph Library), but as I can't use it
+ * here (for obvious reasons), the next four functions below are based on
+ * code of Steven Skiena's book 'The Algorithm Design Manual'.
+ */
+
+static void __init process_edge(uint32_t x, uint32_t y)
+{
+ if (unlikely(graph.discovered[y] && !graph.processed[y])) {
+ pr_err("Cycle found 0x%x ", x);
+ print_node_name(x);
+ pr_cont(" <-> 0x%x ", y);
+ print_node_name(y);
+ pr_cont("!\n");
+ graph.finished = 1;
+ }
+}
+
+static void __init process_vertex_late(uint32_t v)
+{
+ struct device_node *node;
+
+ node = of_find_node_by_phandle(v);
+ if (!node) {
+ pr_err("No node for phandle 0x%x not found", v);
+ return;
+ }
+ order.order[order.count++] = node;
+}
+
+static void __init depth_first_search(uint32_t v)
+{
+ struct edgenode *p;
+ uint32_t y; /* successor vertex */
+
+ if (graph.finished)
+ return;
+ graph.discovered[v] = 1;
+ p = graph.edges[v];
+ while (p) {
+ y = p->y;
+ if (!graph.discovered[y]) {
+ process_edge(v, y);
+ depth_first_search(y);
+ } else
+ process_edge(v, y);
+ if (graph.finished)
+ return;
+ p = p->next;
+ }
+ process_vertex_late(v);
+ graph.processed[v] = 1;
+}
+
+static void __init topological_sort(void)
+{
+ unsigned i;
+
+ for (i = 1; i <= graph.nvertices; ++i)
+ if (!graph.discovered[i] && graph.include_node[i])
+ depth_first_search(i);
+}
+
+static int __init add_dep_list(struct device_node *node)
+{
+ const __be32 *list, *list_end;
+ uint32_t ph;
+ struct property *prop;
+ int rc = 0;
+ struct device_node *dep;
+
+ prop = get_property(node, "dependencies");
+ if (!prop || !prop->val.len || prop->val.len%sizeof(*list))
+ return 0;
+ list = (const __be32 *)prop->val.val;
+ list_end = list + prop->val.len / sizeof(*list);
+ while (list < list_end) {
+ ph = fdt32_to_cpu(*list++);
+ if (unlikely(!ph)) {
+ /* Should never happen */
+ if (node->name)
+ pr_warn("phandle == 0 for %s\n", node->name);
+ continue;
+ }
+ dep = of_find_node_by_phandle(ph);
+ if (unlikely(!dep)) {
+ pr_err("No DT node for dependency with phandle 0x%x found\n",
+ ph);
+ continue;
+ }
+ rc = insert_edge(node->phandle, ph);
+ if (rc)
+ break;
+ }
+
+ return rc;
+}
+
+/* Copied from drivers/of/base.c */
+static const char *of_prop_next_string(struct property *prop, const char *cur)
+{
+ const char *curv = cur;
+
+ if (!prop)
+ return NULL;
+
+ if (!cur)
+ return prop->val.val;
+
+ curv += strlen(cur) + 1;
+ if (curv >= prop->val.val + prop->val.len)
+ return NULL;
+
+ return curv;
+}
+
+static int __init add_deps_lnx(struct device_node *parent,
+ struct device_node *node)
+{
+ struct device_node *child;
+ int rc = 0;
+
+ if (!__of_device_is_available(node))
+ return 0;
+ if (__of_get_property(node, "compatible", NULL)) {
+ if (!parent->phandle) {
+ if (__of_get_property(parent, "compatible", NULL))
+ parent->phandle = 1 + order.max_phandle++;
+ }
+ if (!node->phandle)
+ node->phandle = 1 + order.max_phandle++;
+ rc = insert_edge(node->phandle, parent->phandle);
+ if (rc)
+ return rc;
+ if (unlikely(order.parent_by_phandle[node->phandle])) {
+ /* sanity check */
+ pr_err("0x%x already has a parent!\n", node->phandle);
+ return -EINVAL;
+ }
+ order.parent_by_phandle[node->phandle] = parent->phandle;
+ rc = add_dep_list(node);
+ if (unlikely(rc))
+ return rc;
+ parent = node; /* change the parent only if node is a driver */
+ }
+ for_each_child_of_node(node, child) {
+ rc = add_deps_lnx(parent, child);
+ if (unlikely(rc))
+ break;
+ }
+
+ return rc;
+}
+
+static void calc_max_phandle(struct node *np)
+{
+ struct node *child;
+
+ if (!np || np->deleted)
+ return;
+ if (np->phandle > order.max_phandle)
+ order.max_phandle = np->phandle;
+
+ for_each_child(np, child)
+ calc_max_phandle(child);
+
+ return;
+}
+
+void __init of_init_print_order(const char *name)
+{
+ unsigned i;
+ struct property *prop;
+ const char *cp;
+
+ pr_info("Default initialization order for %s:\n", name);
+ for (i = 0; i < order.count; ++i) {
+ pr_info("init %u 0x%x", i, order.order[i]->phandle);
+ if (order.order[i]->name)
+ pr_cont(" %s", order.order[i]->name);
+ if (order.order[i]->full_name)
+ pr_cont(" (%s)", order.order[i]->full_name);
+ prop = get_property(order.order[i], "compatible");
+ for (cp = of_prop_next_string(prop, NULL); cp;
+ cp = of_prop_next_string(prop, cp))
+ pr_cont(" %s", cp);
+ pr_cont(" (parent 0x%x)\n",
+ order.parent_by_phandle[order.order[i]->phandle]);
+ }
+}
+
+int __init of_init_build_order(struct device_node *root)
+{
+ struct device_node *child;
+ int rc = 0;
+
+ tree = root;
+ if (unlikely(!root))
+ return -EINVAL;
+
+ calc_max_phandle(root);
+ order.old_max_phandle = order.max_phandle;
+
+ for_each_child_of_node(root, child) {
+ rc = add_deps_lnx(root, child);
+ if (unlikely(rc))
+ break;
+ }
+
+ of_node_put(root);
+ topological_sort();
+
+ if (graph.finished)
+ return -EINVAL; /* cycle found */
+
+ return rc;
+}
@@ -88,6 +88,8 @@ static void __attribute__ ((noreturn)) usage(void)
fprintf(stderr, "\t\tSort nodes and properties before outputting (only useful for\n\t\tcomparing trees)\n");
fprintf(stderr, "\t-D\n");
fprintf(stderr, "\t\tDo not automatically add dependencies for phandle references\n");
+ fprintf(stderr, "\t-t\n");
+ fprintf(stderr, "\t\tPrint (default) initialization order\n");
fprintf(stderr, "\t-v\n");
fprintf(stderr, "\t\tPrint DTC version and exit\n");
fprintf(stderr, "\t-H <phandle format>\n");
@@ -110,6 +112,7 @@ int main(int argc, char *argv[])
const char *depname = NULL;
int force = 0, sort = 0;
int dependencies = 1;
+ int init_order = 0;
const char *arg;
int opt;
FILE *outf = NULL;
@@ -121,7 +124,7 @@ int main(int argc, char *argv[])
minsize = 0;
padsize = 0;
- while ((opt = getopt(argc, argv, "hI:O:o:V:d:R:S:p:fqb:i:vH:sDW:E:"))
+ while ((opt = getopt(argc, argv, "hI:O:o:V:d:R:S:p:fqb:i:vH:sDtW:E:"))
!= EOF) {
switch (opt) {
case 'I':
@@ -183,6 +186,10 @@ int main(int argc, char *argv[])
dependencies = false;
break;
+ case 't':
+ init_order = true;
+ break;
+
case 'W':
parse_checks_option(true, false, optarg);
break;
@@ -245,6 +252,13 @@ int main(int argc, char *argv[])
if (dependencies)
add_dependencies(bi);
+ if (init_order) {
+ if (of_init_build_order(bi->dt))
+ exit(2);
+ of_init_print_order(arg);
+ exit(0);
+ }
+
if (streq(outname, "-")) {
outf = stdout;
} else {
@@ -266,5 +280,13 @@ int main(int argc, char *argv[])
die("Unknown output format \"%s\"\n", outform);
}
+ /*
+ * Check for cycles by building the initialzation order.
+ * This is done after the output was saved because it
+ * changes the tree slightly.
+ */
+ if (of_init_build_order(bi->dt))
+ exit(2);
+
exit(0);
}
@@ -269,5 +269,7 @@ struct boot_info *dt_from_fs(const char *dirname);
/* Dependencies */
void add_dependencies(struct boot_info *bi);
+void of_init_print_order(const char *name);
+int of_init_build_order(struct node *root);
#endif /* _DTC_H */
Add option -t to print the default initialization order. No other output will be generated. To print the order, just use something like this: CROSS_COMPILE=gcc-foo ARCH=arm make foo.dtb scripts/dtc/dtc -I dtb -t arch/arm/boot/dts/foo.dtb Since it's now possible to check to for cycles in the dependency graph, this is now done too. Signed-off-by: Alexander Holler <holler@ahsoftware.de> --- scripts/dtc/dependencies.c | 346 +++++++++++++++++++++++++++++++++++++++++++++ scripts/dtc/dtc.c | 24 +++- scripts/dtc/dtc.h | 2 + 3 files changed, 371 insertions(+), 1 deletion(-)