From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1759241AbaELQzD (ORCPT ); Mon, 12 May 2014 12:55:03 -0400 Received: from h1446028.stratoserver.net ([85.214.92.142]:59417 "EHLO mail.ahsoftware.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754643AbaELQzB (ORCPT ); Mon, 12 May 2014 12:55:01 -0400 From: Alexander Holler To: linux-kernel@vger.kernel.org Cc: devicetree@vger.kernel.org, linux-arm-kernel@lists.infradead.org, Greg Kroah-Hartman , Russell King , Jon Loeliger , Grant Likely , Rob Herring , Alexander Holler Subject: [RFC PATCH 3/9] dt: deps: dtc: Add option to print initialization order Date: Mon, 12 May 2014 18:47:54 +0200 Message-Id: <1399913280-6915-4-git-send-email-holler@ahsoftware.de> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1399913280-6915-1-git-send-email-holler@ahsoftware.de> References: <1399913280-6915-1-git-send-email-holler@ahsoftware.de> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- scripts/dtc/dependencies.c | 346 +++++++++++++++++++++++++++++++++++++++++++++ scripts/dtc/dtc.c | 24 +++- scripts/dtc/dtc.h | 2 + 3 files changed, 371 insertions(+), 1 deletion(-) diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c index dd4658c..8fe1a8c 100644 --- a/scripts/dtc/dependencies.c +++ b/scripts/dtc/dependencies.c @@ -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; +} diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c index fbe49d9..ac9858c 100644 --- a/scripts/dtc/dtc.c +++ b/scripts/dtc/dtc.c @@ -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 \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); } diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h index c3dbeac..b89e08a 100644 --- a/scripts/dtc/dtc.h +++ b/scripts/dtc/dtc.h @@ -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 */ -- 1.8.3.1 From mboxrd@z Thu Jan 1 00:00:00 1970 From: Alexander Holler Subject: [RFC PATCH 3/9] dt: deps: dtc: Add option to print initialization order Date: Mon, 12 May 2014 18:47:54 +0200 Message-ID: <1399913280-6915-4-git-send-email-holler@ahsoftware.de> References: <1399913280-6915-1-git-send-email-holler@ahsoftware.de> Return-path: In-Reply-To: <1399913280-6915-1-git-send-email-holler-SXC+2es9fhnfWeYVQQPykw@public.gmane.org> Sender: devicetree-owner-u79uwXL29TY76Z2rM5mHXA@public.gmane.org To: linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org Cc: devicetree-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, linux-arm-kernel-IAPFreCvJWM7uuMidbF8XUB+6BGkLq7r@public.gmane.org, Greg Kroah-Hartman , Russell King , Jon Loeliger , Grant Likely , Rob Herring , Alexander Holler List-Id: devicetree@vger.kernel.org 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 --- scripts/dtc/dependencies.c | 346 +++++++++++++++++++++++++++++++++++++++++++++ scripts/dtc/dtc.c | 24 +++- scripts/dtc/dtc.h | 2 + 3 files changed, 371 insertions(+), 1 deletion(-) diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c index dd4658c..8fe1a8c 100644 --- a/scripts/dtc/dependencies.c +++ b/scripts/dtc/dependencies.c @@ -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; +} diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c index fbe49d9..ac9858c 100644 --- a/scripts/dtc/dtc.c +++ b/scripts/dtc/dtc.c @@ -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 \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); } diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h index c3dbeac..b89e08a 100644 --- a/scripts/dtc/dtc.h +++ b/scripts/dtc/dtc.h @@ -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 */ -- 1.8.3.1 -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org More majordomo info at http://vger.kernel.org/majordomo-info.html From mboxrd@z Thu Jan 1 00:00:00 1970 From: holler@ahsoftware.de (Alexander Holler) Date: Mon, 12 May 2014 18:47:54 +0200 Subject: [RFC PATCH 3/9] dt: deps: dtc: Add option to print initialization order In-Reply-To: <1399913280-6915-1-git-send-email-holler@ahsoftware.de> References: <1399913280-6915-1-git-send-email-holler@ahsoftware.de> Message-ID: <1399913280-6915-4-git-send-email-holler@ahsoftware.de> To: linux-arm-kernel@lists.infradead.org List-Id: linux-arm-kernel.lists.infradead.org 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 --- scripts/dtc/dependencies.c | 346 +++++++++++++++++++++++++++++++++++++++++++++ scripts/dtc/dtc.c | 24 +++- scripts/dtc/dtc.h | 2 + 3 files changed, 371 insertions(+), 1 deletion(-) diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c index dd4658c..8fe1a8c 100644 --- a/scripts/dtc/dependencies.c +++ b/scripts/dtc/dependencies.c @@ -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; +} diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c index fbe49d9..ac9858c 100644 --- a/scripts/dtc/dtc.c +++ b/scripts/dtc/dtc.c @@ -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 \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); } diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h index c3dbeac..b89e08a 100644 --- a/scripts/dtc/dtc.h +++ b/scripts/dtc/dtc.h @@ -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 */ -- 1.8.3.1