[PATCH] dtc: check for duplicate labels when they are defined

[PATCH] dtc: check for duplicate labels when they are defined

[Stephen Warren]

Currently, the DT is checked for duplicate labels after the entire DT has
been parsed. However, once parts of the DT can be deleted, some entities
with labels may have been deleted by this time, thus making those labels
invisible to the duplicate label check, which can then lead to false
negatives.

Instead, maintain a list of all known labels, from which entries are
never deleted, and check against this list for duplicates when adding
labels.

Signed-off-by: Stephen Warren <swarren-3lzwWm7+Weoh9ZMKESR00Q@public.gmane.org>
---
This patch should be applied before my previously posted "dtc: Add
ability to delete nodes and properties". I believe it addresses David's
concerns with that patch re: the assumption that labels are immutable.

 checks.c           |   58 ----------------------------------------------------
 data.c             |    3 ++
 dtc.h              |    1 +
 livetree.c         |   18 ++++++++++++---
 tests/run_tests.sh |   12 +++++-----
 5 files changed, 24 insertions(+), 68 deletions(-)

diff --git a/checks.c b/checks.c
index a662a00..a625e29 100644
--- a/checks.c
+++ b/checks.c
@@ -278,62 +278,6 @@ static void check_property_name_chars(struct check *c, struct node *dt,
 }
 PROP_CHECK(property_name_chars, PROPNODECHARS, ERROR);
 
-#define DESCLABEL_FMT	"%s%s%s%s%s"
-#define DESCLABEL_ARGS(node,prop,mark)		\
-	((mark) ? "value of " : ""),		\
-	((prop) ? "'" : ""), \
-	((prop) ? (prop)->name : ""), \
-	((prop) ? "' in " : ""), (node)->fullpath
-
-static void check_duplicate_label(struct check *c, struct node *dt,
-				  const char *label, struct node *node,
-				  struct property *prop, struct marker *mark)
-{
-	struct node *othernode = NULL;
-	struct property *otherprop = NULL;
-	struct marker *othermark = NULL;
-
-	othernode = get_node_by_label(dt, label);
-
-	if (!othernode)
-		otherprop = get_property_by_label(dt, label, &othernode);
-	if (!othernode)
-		othermark = get_marker_label(dt, label, &othernode,
-					       &otherprop);
-
-	if (!othernode)
-		return;
-
-	if ((othernode != node) || (otherprop != prop) || (othermark != mark))
-		FAIL(c, "Duplicate label '%s' on " DESCLABEL_FMT
-		     " and " DESCLABEL_FMT,
-		     label, DESCLABEL_ARGS(node, prop, mark),
-		     DESCLABEL_ARGS(othernode, otherprop, othermark));
-}
-
-static void check_duplicate_label_node(struct check *c, struct node *dt,
-				       struct node *node)
-{
-	struct label *l;
-
-	for_each_label(node->labels, l)
-		check_duplicate_label(c, dt, l->label, node, NULL, NULL);
-}
-static void check_duplicate_label_prop(struct check *c, struct node *dt,
-				       struct node *node, struct property *prop)
-{
-	struct marker *m = prop->val.markers;
-	struct label *l;
-
-	for_each_label(prop->labels, l)
-		check_duplicate_label(c, dt, l->label, node, prop, NULL);
-
-	for_each_marker_of_type(m, LABEL)
-		check_duplicate_label(c, dt, m->ref, node, prop, m);
-}
-CHECK(duplicate_label, NULL, check_duplicate_label_node,
-      check_duplicate_label_prop, NULL, ERROR);
-
 static void check_explicit_phandles(struct check *c, struct node *root,
 				    struct node *node, struct property *prop)
 {
@@ -630,8 +574,6 @@ static struct check *check_table[] = {
 	&node_name_chars, &node_name_format, &property_name_chars,
 	&name_is_string, &name_properties,
 
-	&duplicate_label,
-
 	&explicit_phandles,
 	&phandle_references, &path_references,
 
diff --git a/data.c b/data.c
index 4a40c5b..16091c1 100644
--- a/data.c
+++ b/data.c
@@ -241,6 +241,9 @@ struct data data_add_marker(struct data d, enum markertype type, char *ref)
 {
 	struct marker *m;
 
+	if (type == LABEL)
+		add_label(NULL, ref);
+
 	m = xmalloc(sizeof(*m));
 	m->offset = d.len;
 	m->type = type;
diff --git a/dtc.h b/dtc.h
index 7b4c65b..bcd5913 100644
--- a/dtc.h
+++ b/dtc.h
@@ -129,6 +129,7 @@ int data_is_one_string(struct data d);
 struct label {
 	char *label;
 	struct label *next;
+	struct label *all_next;
 };
 
 struct property {
diff --git a/livetree.c b/livetree.c
index c9209d5..f12f2c9 100644
--- a/livetree.c
+++ b/livetree.c
@@ -24,19 +24,29 @@
  * Tree building functions
  */
 
+struct label *all_labels;
+
+extern void print_error(char const *fmt, ...);
+
 void add_label(struct label **labels, char *label)
 {
 	struct label *new;
 
 	/* Make sure the label isn't already there */
-	for_each_label(*labels, new)
+	for_each_label(all_labels, new)
 		if (streq(new->label, label))
-			return;
+			print_error("Duplicate label '%s'", label);
 
 	new = xmalloc(sizeof(*new));
 	new->label = label;
-	new->next = *labels;
-	*labels = new;
+	if (labels)
+		new->next = *labels;
+	else
+		new->next = NULL;
+	new->all_next = all_labels;
+	if (labels)
+		*labels = new;
+	all_labels = new;
 }
 
 struct property *build_property(char *name, struct data val)
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index e470b82..006e5fb 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -391,12 +391,12 @@ dtc_tests () {
     run_sh_test dtc-checkfails.sh node_name_format -- -I dtb -O dtb bad_node_format.dtb
     run_sh_test dtc-checkfails.sh prop_name_chars -- -I dtb -O dtb bad_prop_char.dtb
 
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label1.dts
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label2.dts
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label3.dts
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label4.dts
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label5.dts
-    run_sh_test dtc-checkfails.sh duplicate_label -- -I dts -O dtb reuse-label6.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label1.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label2.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label3.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label4.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label5.dts
+    run_sh_test dtc-fatal.sh -I dts -O dtb reuse-label6.dts
 
     # Check for proper behaviour reading from stdin
     run_dtc_test -I dts -O dtb -o stdin_dtc_tree1.test.dtb - < test_tree1.dts
-- 
1.7.5.4

Re: [PATCH] dtc: check for duplicate labels when they are defined

[David Gibson]

On Tue, Mar 27, 2012 at 09:39:44PM -0600, Stephen Warren wrote:
> Currently, the DT is checked for duplicate labels after the entire DT has
> been parsed. However, once parts of the DT can be deleted, some entities
> with labels may have been deleted by this time, thus making those labels
> invisible to the duplicate label check, which can then lead to false
> negatives.
> 
> Instead, maintain a list of all known labels, from which entries are
> never deleted, and check against this list for duplicates when adding
> labels.
> 
> Signed-off-by: Stephen Warren <swarren-3lzwWm7+Weoh9ZMKESR00Q@public.gmane.org>
> ---
> This patch should be applied before my previously posted "dtc: Add
> ability to delete nodes and properties". I believe it addresses David's
> concerns with that patch re: the assumption that labels are
> immutable.

Hm, I suppose it does.  Or at least it removes the more complex
objections.  I'd still want to relook at the deletion patch to
convince myself that the syntax is as good as we can reasonably make
it.

This patch is a bit of a hack, and I'm not thrilled at the loss of
information from the error message, but I can live wth it.

The other approach I was thinking of, which is hacky in different
ways, would be to change the deletion patch so that instead of
actually removing the deleted nodes from the tree, just marks them as
deleted.  They'd then be omitted from the output pass, but the labels
attached therein can still be found.

-- 
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: [PATCH] dtc: check for duplicate labels when they are defined

[Stephen Warren]

On 04/02/2012 08:46 PM, David Gibson wrote:
> On Tue, Mar 27, 2012 at 09:39:44PM -0600, Stephen Warren wrote:
>> Currently, the DT is checked for duplicate labels after the entire DT has
>> been parsed. However, once parts of the DT can be deleted, some entities
>> with labels may have been deleted by this time, thus making those labels
>> invisible to the duplicate label check, which can then lead to false
>> negatives.
>>
>> Instead, maintain a list of all known labels, from which entries are
>> never deleted, and check against this list for duplicates when adding
>> labels.
>>
>> Signed-off-by: Stephen Warren <swarren-3lzwWm7+Weoh9ZMKESR00Q@public.gmane.org>
>> ---
>> This patch should be applied before my previously posted "dtc: Add
>> ability to delete nodes and properties". I believe it addresses David's
>> concerns with that patch re: the assumption that labels are
>> immutable.
> 
> Hm, I suppose it does.  Or at least it removes the more complex
> objections.  I'd still want to relook at the deletion patch to
> convince myself that the syntax is as good as we can reasonably make
> it.
> 
> This patch is a bit of a hack, and I'm not thrilled at the loss of
> information from the error message, but I can live wth it.
> 
> The other approach I was thinking of, which is hacky in different
> ways, would be to change the deletion patch so that instead of
> actually removing the deleted nodes from the tree, just marks them as
> deleted.  They'd then be omitted from the output pass, but the labels
> attached therein can still be found.

So is this patch good to be applied, or would you rather it was reworked
according the other approach you mentioned?