[RFC] dtc: Optionally sort nodes and properties

[RFC] dtc: Optionally sort nodes and properties

[David Gibson]

Hi folks,

Here's a patch I made for dtc a little while ago, and I'm not sure if
it's something that sensibly ought to be merged into mainline dtc.

The patch adds a '-s' option to dtc, which causes it to "sort" the
tree before output.  That is, it sorts the reserve entries, it sorts
the properties within each node by name, and it sorts nodes by name
within their parent.

The main use for this is when looking at the differences between two
device trees which are similar, except for semantically null internal
rearrangements.  Directly diffing the dts files will give a lot of
noise due to the order changes, but running both trees through dtc -s
then diffing will usually give a pretty sensible summary of the
changes (it can still be confused by node name changes, of course).

Index: dtc/dtc.c
===================================================================
--- dtc.orig/dtc.c	2010-08-30 12:55:18.209765942 +1000
+++ dtc/dtc.c	2010-08-30 14:03:46.457785218 +1000
@@ -81,6 +81,8 @@ static void  __attribute__ ((noreturn)) 
 	fprintf(stderr, "\t\tSet the physical boot cpu\n");
 	fprintf(stderr, "\t-f\n");
 	fprintf(stderr, "\t\tForce - try to produce output even if the input tree has errors\n");
+	fprintf(stderr, "\t-s\n");
+	fprintf(stderr, "\t\tSort nodes and properties before outputting\n");
 	fprintf(stderr, "\t-v\n");
 	fprintf(stderr, "\t\tPrint DTC version and exit\n");
 	fprintf(stderr, "\t-H <phandle format>\n");
@@ -97,7 +99,7 @@ int main(int argc, char *argv[])
 	const char *inform = "dts";
 	const char *outform = "dts";
 	const char *outname = "-";
-	int force = 0, check = 0;
+	int force = 0, check = 0, sort = 0;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -109,7 +111,7 @@ int main(int argc, char *argv[])
 	minsize    = 0;
 	padsize    = 0;
 
-	while ((opt = getopt(argc, argv, "hI:O:o:V:R:S:p:fcqb:vH:")) != EOF) {
+	while ((opt = getopt(argc, argv, "hI:O:o:V:R:S:p:fcqb:vH:s")) != EOF) {
 		switch (opt) {
 		case 'I':
 			inform = optarg;
@@ -159,6 +161,10 @@ int main(int argc, char *argv[])
 				    optarg);
 			break;
 
+		case 's':
+			sort = 1;
+			break;
+
 		case 'h':
 		default:
 			usage();
@@ -197,6 +203,8 @@ int main(int argc, char *argv[])
 	fill_fullpaths(bi->dt, "");
 	process_checks(force, bi);
 
+	if (sort)
+		sort_tree(bi);
 
 	if (streq(outname, "-")) {
 		outf = stdout;
Index: dtc/dtc.h
===================================================================
--- dtc.orig/dtc.h	2010-08-30 13:55:02.577766011 +1000
+++ dtc/dtc.h	2010-08-30 14:03:46.457785218 +1000
@@ -223,6 +223,7 @@ struct boot_info {
 
 struct boot_info *build_boot_info(struct reserve_info *reservelist,
 				  struct node *tree, uint32_t boot_cpuid_phys);
+void sort_tree(struct boot_info *bi);
 
 /* Checks */
 
Index: dtc/livetree.c
===================================================================
--- dtc.orig/livetree.c	2010-08-30 13:55:02.577766011 +1000
+++ dtc/livetree.c	2010-08-30 14:03:46.461763776 +1000
@@ -505,3 +505,140 @@ uint32_t guess_boot_cpuid(struct node *t
 
 	return propval_cell(reg);
 }
+
+static int cmp_reserve_info(const void *ax, const void *bx)
+{
+	const struct reserve_info *a, *b;
+
+	a = *((const struct reserve_info * const *)ax);
+	b = *((const struct reserve_info * const *)bx);
+
+	if (a->re.address < b->re.address)
+		return -1;
+	else if (a->re.address > b->re.address)
+		return 1;
+	else if (a->re.size < b->re.size)
+		return -1;
+	else if (a->re.size > b->re.size)
+		return 1;
+	else
+		return 0;
+}
+
+static void sort_reserve_entries(struct boot_info *bi)
+{
+	struct reserve_info *ri, **tbl;
+	int n = 0, i = 0;
+
+	for (ri = bi->reservelist;
+	     ri;
+	     ri = ri->next)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for (ri = bi->reservelist;
+	     ri;
+	     ri = ri->next)
+		tbl[i++] = ri;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
+
+	bi->reservelist = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next = tbl[i+1];
+	tbl[n-1]->next = NULL;
+
+	free(tbl);
+}
+
+static int cmp_prop(const void *ax, const void *bx)
+{
+	const struct property *a, *b;
+
+	a = *((const struct property * const *)ax);
+	b = *((const struct property * const *)bx);
+
+	return strcmp(a->name, b->name);
+}
+
+static void sort_properties(struct node *node)
+{
+	int n = 0, i = 0;
+	struct property *prop, **tbl;
+
+	for_each_property(node, prop)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for_each_property(node, prop)
+		tbl[i++] = prop;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_prop);
+
+	node->proplist = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next = tbl[i+1];
+	tbl[n-1]->next = NULL;
+
+	free(tbl);
+}
+
+static int cmp_subnode(const void *ax, const void *bx)
+{
+	const struct node *a, *b;
+
+	a = *((const struct node * const *)ax);
+	b = *((const struct node * const *)bx);
+
+	return strcmp(a->name, b->name);
+}
+
+static void sort_subnodes(struct node *node)
+{
+	int n = 0, i = 0;
+	struct node *subnode, **tbl;
+
+	for_each_child(node, subnode)
+		n++;
+
+	if (n == 0)
+		return;
+
+	tbl = xmalloc(n * sizeof(*tbl));
+
+	for_each_child(node, subnode)
+		tbl[i++] = subnode;
+
+	qsort(tbl, n, sizeof(*tbl), cmp_subnode);
+
+	node->children = tbl[0];
+	for (i = 0; i < (n-1); i++)
+		tbl[i]->next_sibling = tbl[i+1];
+	tbl[n-1]->next_sibling = NULL;
+
+	free(tbl);
+}
+
+static void sort_node(struct node *node)
+{
+	struct node *c;
+
+	sort_properties(node);
+	sort_subnodes(node);
+	for_each_child(node, c)
+		sort_node(c);
+}
+
+void sort_tree(struct boot_info *bi)
+{
+	sort_reserve_entries(bi);
+	sort_node(bi->dt);
+}
Index: dtc/tests/run_tests.sh
===================================================================
--- dtc.orig/tests/run_tests.sh	2010-08-30 14:03:42.218764527 +1000
+++ dtc/tests/run_tests.sh	2010-08-30 14:03:46.461763776 +1000
@@ -377,6 +377,13 @@ cmp_tests () {
     for tree in $wrongtrees; do
 	run_test dtbs_equal_unordered -n $basetree $tree
     done
+
+    # now dtc --sort
+    run_dtc_test -I dtb -O dtb -s -o $basetree.sorted.test.dtb $basetree
+    run_test dtbs_equal_unordered $basetree $basetree.sorted.test.dtb
+    run_dtc_test -I dtb -O dtb -s -o $basetree.reversed.sorted.test.dtb $basetree.reversed.test.dtb
+    run_test dtbs_equal_unordered $basetree.reversed.test.dtb $basetree.reversed.sorted.test.dtb
+    run_test dtbs_equal_ordered $basetree.sorted.test.dtb $basetree.reversed.sorted.test.dtb
 }
 
 dtbs_equal_tests () {



-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

Re: [RFC] dtc: Optionally sort nodes and properties

[Grant Likely]

On Wed, Sep 01, 2010 at 12:47:18PM +1000, David Gibson wrote:
> Hi folks,
> 
> Here's a patch I made for dtc a little while ago, and I'm not sure if
> it's something that sensibly ought to be merged into mainline dtc.
> 
> The patch adds a '-s' option to dtc, which causes it to "sort" the
> tree before output.  That is, it sorts the reserve entries, it sorts
> the properties within each node by name, and it sorts nodes by name
> within their parent.
> 
> The main use for this is when looking at the differences between two
> device trees which are similar, except for semantically null internal
> rearrangements.  Directly diffing the dts files will give a lot of
> noise due to the order changes, but running both trees through dtc -s
> then diffing will usually give a pretty sensible summary of the
> changes (it can still be confused by node name changes, of course).

As discussed on IRC, I'm not thrilled with adding this as a
user-visible option because sorted trees aren't actually useful or
desirable (and in some cases undesireable) except for the use-case of
comparing trees.  However, being able to compare unsorted trees is
still a use case that is very much needed, so I'm okay with this patch
until we come up with something better.

Although maybe the -s option should remain undocumented; or at least
warn people away from using it.

g.

> 
> Index: dtc/dtc.c
> ===================================================================
> --- dtc.orig/dtc.c	2010-08-30 12:55:18.209765942 +1000
> +++ dtc/dtc.c	2010-08-30 14:03:46.457785218 +1000
> @@ -81,6 +81,8 @@ static void  __attribute__ ((noreturn)) 
>  	fprintf(stderr, "\t\tSet the physical boot cpu\n");
>  	fprintf(stderr, "\t-f\n");
>  	fprintf(stderr, "\t\tForce - try to produce output even if the input tree has errors\n");
> +	fprintf(stderr, "\t-s\n");
> +	fprintf(stderr, "\t\tSort nodes and properties before outputting\n");
>  	fprintf(stderr, "\t-v\n");
>  	fprintf(stderr, "\t\tPrint DTC version and exit\n");
>  	fprintf(stderr, "\t-H <phandle format>\n");
> @@ -97,7 +99,7 @@ int main(int argc, char *argv[])
>  	const char *inform = "dts";
>  	const char *outform = "dts";
>  	const char *outname = "-";
> -	int force = 0, check = 0;
> +	int force = 0, check = 0, sort = 0;
>  	const char *arg;
>  	int opt;
>  	FILE *outf = NULL;
> @@ -109,7 +111,7 @@ int main(int argc, char *argv[])
>  	minsize    = 0;
>  	padsize    = 0;
>  
> -	while ((opt = getopt(argc, argv, "hI:O:o:V:R:S:p:fcqb:vH:")) != EOF) {
> +	while ((opt = getopt(argc, argv, "hI:O:o:V:R:S:p:fcqb:vH:s")) != EOF) {
>  		switch (opt) {
>  		case 'I':
>  			inform = optarg;
> @@ -159,6 +161,10 @@ int main(int argc, char *argv[])
>  				    optarg);
>  			break;
>  
> +		case 's':
> +			sort = 1;
> +			break;
> +
>  		case 'h':
>  		default:
>  			usage();
> @@ -197,6 +203,8 @@ int main(int argc, char *argv[])
>  	fill_fullpaths(bi->dt, "");
>  	process_checks(force, bi);
>  
> +	if (sort)
> +		sort_tree(bi);
>  
>  	if (streq(outname, "-")) {
>  		outf = stdout;
> Index: dtc/dtc.h
> ===================================================================
> --- dtc.orig/dtc.h	2010-08-30 13:55:02.577766011 +1000
> +++ dtc/dtc.h	2010-08-30 14:03:46.457785218 +1000
> @@ -223,6 +223,7 @@ struct boot_info {
>  
>  struct boot_info *build_boot_info(struct reserve_info *reservelist,
>  				  struct node *tree, uint32_t boot_cpuid_phys);
> +void sort_tree(struct boot_info *bi);
>  
>  /* Checks */
>  
> Index: dtc/livetree.c
> ===================================================================
> --- dtc.orig/livetree.c	2010-08-30 13:55:02.577766011 +1000
> +++ dtc/livetree.c	2010-08-30 14:03:46.461763776 +1000
> @@ -505,3 +505,140 @@ uint32_t guess_boot_cpuid(struct node *t
>  
>  	return propval_cell(reg);
>  }
> +
> +static int cmp_reserve_info(const void *ax, const void *bx)
> +{
> +	const struct reserve_info *a, *b;
> +
> +	a = *((const struct reserve_info * const *)ax);
> +	b = *((const struct reserve_info * const *)bx);
> +
> +	if (a->re.address < b->re.address)
> +		return -1;
> +	else if (a->re.address > b->re.address)
> +		return 1;
> +	else if (a->re.size < b->re.size)
> +		return -1;
> +	else if (a->re.size > b->re.size)
> +		return 1;
> +	else
> +		return 0;
> +}
> +
> +static void sort_reserve_entries(struct boot_info *bi)
> +{
> +	struct reserve_info *ri, **tbl;
> +	int n = 0, i = 0;
> +
> +	for (ri = bi->reservelist;
> +	     ri;
> +	     ri = ri->next)
> +		n++;
> +
> +	if (n == 0)
> +		return;
> +
> +	tbl = xmalloc(n * sizeof(*tbl));
> +
> +	for (ri = bi->reservelist;
> +	     ri;
> +	     ri = ri->next)
> +		tbl[i++] = ri;
> +
> +	qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
> +
> +	bi->reservelist = tbl[0];
> +	for (i = 0; i < (n-1); i++)
> +		tbl[i]->next = tbl[i+1];
> +	tbl[n-1]->next = NULL;
> +
> +	free(tbl);
> +}
> +
> +static int cmp_prop(const void *ax, const void *bx)
> +{
> +	const struct property *a, *b;
> +
> +	a = *((const struct property * const *)ax);
> +	b = *((const struct property * const *)bx);
> +
> +	return strcmp(a->name, b->name);
> +}
> +
> +static void sort_properties(struct node *node)
> +{
> +	int n = 0, i = 0;
> +	struct property *prop, **tbl;
> +
> +	for_each_property(node, prop)
> +		n++;
> +
> +	if (n == 0)
> +		return;
> +
> +	tbl = xmalloc(n * sizeof(*tbl));
> +
> +	for_each_property(node, prop)
> +		tbl[i++] = prop;
> +
> +	qsort(tbl, n, sizeof(*tbl), cmp_prop);
> +
> +	node->proplist = tbl[0];
> +	for (i = 0; i < (n-1); i++)
> +		tbl[i]->next = tbl[i+1];
> +	tbl[n-1]->next = NULL;
> +
> +	free(tbl);
> +}
> +
> +static int cmp_subnode(const void *ax, const void *bx)
> +{
> +	const struct node *a, *b;
> +
> +	a = *((const struct node * const *)ax);
> +	b = *((const struct node * const *)bx);
> +
> +	return strcmp(a->name, b->name);
> +}
> +
> +static void sort_subnodes(struct node *node)
> +{
> +	int n = 0, i = 0;
> +	struct node *subnode, **tbl;
> +
> +	for_each_child(node, subnode)
> +		n++;
> +
> +	if (n == 0)
> +		return;
> +
> +	tbl = xmalloc(n * sizeof(*tbl));
> +
> +	for_each_child(node, subnode)
> +		tbl[i++] = subnode;
> +
> +	qsort(tbl, n, sizeof(*tbl), cmp_subnode);
> +
> +	node->children = tbl[0];
> +	for (i = 0; i < (n-1); i++)
> +		tbl[i]->next_sibling = tbl[i+1];
> +	tbl[n-1]->next_sibling = NULL;
> +
> +	free(tbl);
> +}
> +
> +static void sort_node(struct node *node)
> +{
> +	struct node *c;
> +
> +	sort_properties(node);
> +	sort_subnodes(node);
> +	for_each_child(node, c)
> +		sort_node(c);
> +}
> +
> +void sort_tree(struct boot_info *bi)
> +{
> +	sort_reserve_entries(bi);
> +	sort_node(bi->dt);
> +}
> Index: dtc/tests/run_tests.sh
> ===================================================================
> --- dtc.orig/tests/run_tests.sh	2010-08-30 14:03:42.218764527 +1000
> +++ dtc/tests/run_tests.sh	2010-08-30 14:03:46.461763776 +1000
> @@ -377,6 +377,13 @@ cmp_tests () {
>      for tree in $wrongtrees; do
>  	run_test dtbs_equal_unordered -n $basetree $tree
>      done
> +
> +    # now dtc --sort
> +    run_dtc_test -I dtb -O dtb -s -o $basetree.sorted.test.dtb $basetree
> +    run_test dtbs_equal_unordered $basetree $basetree.sorted.test.dtb
> +    run_dtc_test -I dtb -O dtb -s -o $basetree.reversed.sorted.test.dtb $basetree.reversed.test.dtb
> +    run_test dtbs_equal_unordered $basetree.reversed.test.dtb $basetree.reversed.sorted.test.dtb
> +    run_test dtbs_equal_ordered $basetree.sorted.test.dtb $basetree.reversed.sorted.test.dtb
>  }
>  
>  dtbs_equal_tests () {
> 
> 
> 
> -- 
> David Gibson			| I'll have my music baroque, and my code
> david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
> 				| _way_ _around_!
> http://www.ozlabs.org/~dgibson

Re: [RFC] dtc: Optionally sort nodes and properties

[Scott Wood]

On Wed, 8 Sep 2010 14:25:30 -0600
Grant Likely <grant.likely-s3s/WqlpOiPyB63q8FvJNQ@public.gmane.org> wrote:

> On Wed, Sep 01, 2010 at 12:47:18PM +1000, David Gibson wrote:
> > Hi folks,
> > 
> > Here's a patch I made for dtc a little while ago, and I'm not sure if
> > it's something that sensibly ought to be merged into mainline dtc.
> > 
> > The patch adds a '-s' option to dtc, which causes it to "sort" the
> > tree before output.  That is, it sorts the reserve entries, it sorts
> > the properties within each node by name, and it sorts nodes by name
> > within their parent.
> > 
> > The main use for this is when looking at the differences between two
> > device trees which are similar, except for semantically null internal
> > rearrangements.  Directly diffing the dts files will give a lot of
> > noise due to the order changes, but running both trees through dtc -s
> > then diffing will usually give a pretty sensible summary of the
> > changes (it can still be confused by node name changes, of course).
> 
> As discussed on IRC, I'm not thrilled with adding this as a
> user-visible option because sorted trees aren't actually useful or
> desirable (and in some cases undesireable) except for the use-case of
> comparing trees.  However, being able to compare unsorted trees is
> still a use case that is very much needed, so I'm okay with this patch
> until we come up with something better.
> 
> Although maybe the -s option should remain undocumented; or at least
> warn people away from using it.

If it's undocumented, how would people find out how to compare device
trees?

Maybe just add a "(for comparing trees)" note in the help text to
clarify the intended purpose?

-Scott

Re: [RFC] dtc: Optionally sort nodes and properties

[Grant Likely]

On Wed, Sep 08, 2010 at 03:39:52PM -0500, Scott Wood wrote:
> On Wed, 8 Sep 2010 14:25:30 -0600
> Grant Likely <grant.likely-s3s/WqlpOiPyB63q8FvJNQ@public.gmane.org> wrote:
> 
> > On Wed, Sep 01, 2010 at 12:47:18PM +1000, David Gibson wrote:
> > > Hi folks,
> > > 
> > > Here's a patch I made for dtc a little while ago, and I'm not sure if
> > > it's something that sensibly ought to be merged into mainline dtc.
> > > 
> > > The patch adds a '-s' option to dtc, which causes it to "sort" the
> > > tree before output.  That is, it sorts the reserve entries, it sorts
> > > the properties within each node by name, and it sorts nodes by name
> > > within their parent.
> > > 
> > > The main use for this is when looking at the differences between two
> > > device trees which are similar, except for semantically null internal
> > > rearrangements.  Directly diffing the dts files will give a lot of
> > > noise due to the order changes, but running both trees through dtc -s
> > > then diffing will usually give a pretty sensible summary of the
> > > changes (it can still be confused by node name changes, of course).
> > 
> > As discussed on IRC, I'm not thrilled with adding this as a
> > user-visible option because sorted trees aren't actually useful or
> > desirable (and in some cases undesireable) except for the use-case of
> > comparing trees.  However, being able to compare unsorted trees is
> > still a use case that is very much needed, so I'm okay with this patch
> > until we come up with something better.
> > 
> > Although maybe the -s option should remain undocumented; or at least
> > warn people away from using it.
> 
> If it's undocumented, how would people find out how to compare device
> trees?

Comparing trees should be its own documented command.  If it happens
to be implemented as a shell script using this option, then that is
just fine by me.

What I don't want is people thinking that sorting their trees by
default is a good idea.  (Although the idea of randomly sorting trees
is vaguely interesting.  It would certainly expose all kinds of weird
bugs in the kernel where we depend on the natural sorting for driver
probe order)

> Maybe just add a "(for comparing trees)" note in the help text to
> clarify the intended purpose?

That's fine too.  It's not something worth debating a long time over.

g.

Re: [RFC] dtc: Optionally sort nodes and properties

[Timur Tabi]

On Wed, Sep 8, 2010 at 3:39 PM, Scott Wood <scottwood-KZfg59tc24xl57MIdRCFDg@public.gmane.org> wrote:

> If it's undocumented, how would people find out how to compare device
> trees?
>
> Maybe just add a "(for comparing trees)" note in the help text to
> clarify the intended purpose?

I agree with Scott.  It should be documented, but we should clearly
state everywhere when this option should not be used.

-- 
Timur Tabi
Linux kernel developer at Freescale