From patchwork Mon May 12 16:47:54 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Holler X-Patchwork-Id: 4160281 Return-Path: X-Original-To: patchwork-linux-arm@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 632BBBFF02 for ; Mon, 12 May 2014 16:58:08 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 23CE9202DD for ; Mon, 12 May 2014 16:58:07 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.9]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id E15C12018A for ; Mon, 12 May 2014 16:58:05 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.80.1 #2 (Red Hat Linux)) id 1WjtVZ-0007wI-4b; Mon, 12 May 2014 16:55:21 +0000 Received: from h1446028.stratoserver.net ([85.214.92.142] helo=mail.ahsoftware.de) by bombadil.infradead.org with esmtps (Exim 4.80.1 #2 (Red Hat Linux)) id 1WjtVU-0006i0-5n for linux-arm-kernel@lists.infradead.org; Mon, 12 May 2014 16:55:17 +0000 Received: by mail.ahsoftware.de (Postfix, from userid 65534) id D4234423C2EA; Mon, 12 May 2014 18:54:53 +0200 (CEST) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Spam-Level: X-Spam-Status: No, score=-2.5 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 Received: from eiche.ahsoftware (p57B21A99.dip0.t-ipconnect.de [87.178.26.153]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.ahsoftware.de (Postfix) with ESMTPSA id 0A542423C2A8 for ; Mon, 12 May 2014 18:54:51 +0200 (CEST) Received: by eiche.ahsoftware (Postfix, from userid 65534) id 474B77F91E; Mon, 12 May 2014 18:54:50 +0200 (CEST) Received: from krabat.ahsoftware (unknown [192.168.207.2]) by eiche.ahsoftware (Postfix) with ESMTP id 34D0E7F921; Mon, 12 May 2014 16:48:29 +0000 (UTC) From: Alexander Holler To: linux-kernel@vger.kernel.org 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> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20140512_095516_746772_D0B31F16 X-CRM114-Status: GOOD ( 31.39 ) X-Spam-Score: -0.0 (/) Cc: devicetree@vger.kernel.org, Jon Loeliger , Russell King , Greg Kroah-Hartman , Rob Herring , Grant Likely , Alexander Holler , linux-arm-kernel@lists.infradead.org X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Virus-Scanned: ClamAV using ClamSMTP 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 */