libfdt: Property iteration

libfdt: Property iteration

[Scott Wood]

A while back when discussing property iterators
(http://ozlabs.org/pipermail/linuxppc-dev/2008-January/049891.html), you
said that you'd prefer not to expose property offsets, because more
common uses would be affected by changing offsets.  I'm looking again at
this, and was wondering what alternative and would-be-broken use cases
you were thinking of?

We could operate on property indices or names at an efficiency cost. 
Most nodes should be small enough that the cost isn't too much, but I'd
like to know which use cases really need it.  The ones I'd use it for
involve reading from one tree and adding to another, so moving offsets
aren't an issue.

Even in a use case where one makes in-place changes while iterating over
properties, changes to the property currently being iterated over should
only move later properties -- the next call to fdt_next_prop would be
based on the start of the property that was modified, which did not
change.

-Scott

Re: libfdt: Property iteration

[David Gibson]

On Mon, Oct 27, 2008 at 05:14:41PM -0500, Scott Wood wrote:
> A while back when discussing property iterators
> (http://ozlabs.org/pipermail/linuxppc-dev/2008-January/049891.html), you
> said that you'd prefer not to expose property offsets, because more
> common uses would be affected by changing offsets.  I'm looking again at
> this, and was wondering what alternative and would-be-broken use cases
> you were thinking of?

Hrm, well I didn't have things in mind all that precisely.  I was just
thinking that it's fairly common to grab a node, then manipulate
various properties within it in a more-or-less random-access sort of
way.

Whereas when finding nodes, ofetn one tends to work down the tree to a
particular node, and the only things you're interested in keeping tabs
on (for a little while at least) are some of the ancestors of this
node - whose offsets are guaranteed not to be messed with by
manipulations within the descendant.

> We could operate on property indices or names at an efficiency cost. 
> Most nodes should be small enough that the cost isn't too much, but I'd
> like to know which use cases really need it.  The ones I'd use it for
> involve reading from one tree and adding to another, so moving offsets
> aren't an issue.

I don't think indices buy us much over offsets.  They can still change
with node insertions or deletions.

> Even in a use case where one makes in-place changes while iterating over
> properties, changes to the property currently being iterated over should
> only move later properties -- the next call to fdt_next_prop would be
> based on the start of the property that was modified, which did not
> change.

That's true; unless you delete the property entirely.  Inserting an
unrelated property is also potentially dangerous, though from the
looks of it we always insert properties at the end in libfdt, so that
should work ok.

Fwiw, I (somewhat reluctantly) accepted the need for property offsets,
in the prototype patch for property iteration I had.  I was going to
polish it up and push it out, but got sidetracked by other things.
I've included it below, maybe you'll get to the polishing before I do.

Index: dtc/libfdt/fdt.c
===================================================================
--- dtc.orig/libfdt/fdt.c	2008-02-14 11:20:40.000000000 +1100
+++ dtc/libfdt/fdt.c	2008-02-14 14:17:19.000000000 +1100
@@ -90,6 +90,31 @@
 	return p;
 }
 
+const struct fdt_property *_fdt_offset_property(const void *fdt, int offset,
+					       int *lenp)
+{
+	const struct fdt_property *prop;
+	int len;
+
+	if (lenp)
+		*lenp = -FDT_ERR_BADSTRUCTURE;
+
+	prop = fdt_offset_ptr(fdt, offset, sizeof(*prop));
+	if (!prop)
+		return NULL;
+
+	len = fdt32_to_cpu(prop->len);
+
+	prop = fdt_offset_ptr(fdt, offset, sizeof(*prop)+len);
+	if (!prop)
+		return NULL;
+
+	if (lenp)
+		*lenp = len;
+
+	return prop;
+}
+
 uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset)
 {
 	const uint32_t *tagp, *lenp;
@@ -170,6 +195,46 @@
 	return offset;
 }
 
+int _fdt_next_property(const void *fdt, int offset)
+{
+	uint32_t tag;
+	int nextoffset;
+	int err;
+
+	if ((err = fdt_check_header(fdt)) != 0)
+		return err;
+
+	if (offset % FDT_TAGSIZE)
+		return -FDT_ERR_BADOFFSET;
+
+	tag = fdt_next_tag(fdt, offset, &nextoffset);
+	if ((tag != FDT_BEGIN_NODE) && (tag != FDT_PROP))
+		return -FDT_ERR_BADOFFSET;
+
+	do {
+		offset = nextoffset;
+
+		tag = fdt_next_tag(fdt, offset, &nextoffset);
+		switch (tag) {
+		case FDT_END:
+			return -FDT_ERR_TRUNCATED;
+
+		case FDT_BEGIN_NODE:
+		case FDT_END_NODE:
+		case FDT_NOP:
+			break;
+
+		case FDT_PROP:
+			return offset;
+
+		default:
+			return -FDT_ERR_BADSTRUCTURE;
+		}
+	} while (tag == FDT_NOP);
+
+	return -FDT_ERR_NOTFOUND;
+}
+
 const char *_fdt_find_string(const char *strtab, int tabsize, const char *s)
 {
 	int len = strlen(s) + 1;
Index: dtc/libfdt/fdt_ro.c
===================================================================
--- dtc.orig/libfdt/fdt_ro.c	2008-02-14 11:20:40.000000000 +1100
+++ dtc/libfdt/fdt_ro.c	2008-02-14 13:18:21.000000000 +1100
@@ -190,68 +190,22 @@
 					    int nodeoffset,
 					    const char *name, int *lenp)
 {
-	uint32_t tag;
 	const struct fdt_property *prop;
-	int namestroff;
-	int offset, nextoffset;
-	int err;
+	const char *pname;
+	int offset = nodeoffset;
 
-	if ((err = fdt_check_header(fdt)) != 0)
-		goto fail;
-
-	err = -FDT_ERR_BADOFFSET;
-	if (nodeoffset % FDT_TAGSIZE)
-		goto fail;
-
-	tag = fdt_next_tag(fdt, nodeoffset, &nextoffset);
-	if (tag != FDT_BEGIN_NODE)
-		goto fail;
-
-	do {
-		offset = nextoffset;
-
-		tag = fdt_next_tag(fdt, offset, &nextoffset);
-		switch (tag) {
-		case FDT_END:
-			err = -FDT_ERR_TRUNCATED;
-			goto fail;
-
-		case FDT_BEGIN_NODE:
-		case FDT_END_NODE:
-		case FDT_NOP:
-			break;
-
-		case FDT_PROP:
-			err = -FDT_ERR_BADSTRUCTURE;
-			prop = fdt_offset_ptr(fdt, offset, sizeof(*prop));
-			if (! prop)
-				goto fail;
-			namestroff = fdt32_to_cpu(prop->nameoff);
-			if (streq(fdt_string(fdt, namestroff), name)) {
-				/* Found it! */
-				int len = fdt32_to_cpu(prop->len);
-				prop = fdt_offset_ptr(fdt, offset,
-						      sizeof(*prop)+len);
-				if (! prop)
-					goto fail;
-
-				if (lenp)
-					*lenp = len;
-
-				return prop;
-			}
-			break;
-
-		default:
-			err = -FDT_ERR_BADSTRUCTURE;
-			goto fail;
-		}
-	} while ((tag != FDT_BEGIN_NODE) && (tag != FDT_END_NODE));
+	while ((offset = _fdt_next_property(fdt, offset)) >= 0) {
+		prop = fdt_offset_property(fdt, offset, lenp);
+		if (!prop)
+			return NULL;
+		pname = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
+		if (streq(pname, name))
+			/* Found it! */
+			return prop;
+	}
 
-	err = -FDT_ERR_NOTFOUND;
- fail:
 	if (lenp)
-		*lenp = err;
+		*lenp = offset;
 	return NULL;
 }
 
Index: dtc/libfdt/libfdt_internal.h
===================================================================
--- dtc.orig/libfdt/libfdt_internal.h	2008-02-14 11:20:40.000000000 +1100
+++ dtc/libfdt/libfdt_internal.h	2008-02-14 13:18:21.000000000 +1100
@@ -59,6 +59,7 @@
 #define streq(p, q)	(strcmp((p), (q)) == 0)
 
 uint32_t _fdt_next_tag(const void *fdt, int startoffset, int *nextoffset);
+int _fdt_next_property(const void *fdt, int offset);
 const char *_fdt_find_string(const char *strtab, int tabsize, const char *s);
 int _fdt_node_end_offset(void *fdt, int nodeoffset);
 
Index: dtc/libfdt/libfdt.h
===================================================================
--- dtc.orig/libfdt/libfdt.h	2008-02-14 11:20:40.000000000 +1100
+++ dtc/libfdt/libfdt.h	2008-02-14 14:19:20.000000000 +1100
@@ -128,6 +128,9 @@
 	return (void *)fdt_offset_ptr(fdt, offset, checklen);
 }
 
+const struct fdt_property *_fdt_offset_property(const void *fdt, int offset,
+						int *lenp);
+
 uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset);
 
 /**********************************************************************/
@@ -136,6 +139,11 @@
 
 int fdt_next_node(const void *fdt, int offset, int *depth);
 
+#define for_each_property(fdt, node, prop, len) \
+	for (int _off = fdt_next_property((fdt), (node)); \
+	     (_off >= 0) && \
+		     (((prop) = fdt_offset_property((fdt), _off, &(len))) >= 0);)
+
 /**********************************************************************/
 /* General functions                                                  */
 /**********************************************************************/
@@ -256,6 +264,7 @@
  */
 int fdt_get_mem_rsv(const void *fdt, int n, uint64_t *address, uint64_t *size);
 
+
 /**
  * fdt_subnode_offset_namelen - find a subnode based on substring
  * @fdt: pointer to the device tree blob


-- 
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: libfdt: Property iteration

[David Gibson]

On Fri, Nov 07, 2008 at 01:54:44PM +1100, David Gibson wrote:
> On Mon, Oct 27, 2008 at 05:14:41PM -0500, Scott Wood wrote:
> > A while back when discussing property iterators
> > (http://ozlabs.org/pipermail/linuxppc-dev/2008-January/049891.html), you
> > said that you'd prefer not to expose property offsets, because more
> > common uses would be affected by changing offsets.  I'm looking again at
> > this, and was wondering what alternative and would-be-broken use cases
> > you were thinking of?
> 
> Hrm, well I didn't have things in mind all that precisely.  I was just
> thinking that it's fairly common to grab a node, then manipulate
> various properties within it in a more-or-less random-access sort of
> way.
> 
> Whereas when finding nodes, ofetn one tends to work down the tree to a
> particular node, and the only things you're interested in keeping tabs
> on (for a little while at least) are some of the ancestors of this
> node - whose offsets are guaranteed not to be messed with by
> manipulations within the descendant.
> 
> > We could operate on property indices or names at an efficiency cost. 
> > Most nodes should be small enough that the cost isn't too much, but I'd
> > like to know which use cases really need it.  The ones I'd use it for
> > involve reading from one tree and adding to another, so moving offsets
> > aren't an issue.
> 
> I don't think indices buy us much over offsets.  They can still change
> with node insertions or deletions.
> 
> > Even in a use case where one makes in-place changes while iterating over
> > properties, changes to the property currently being iterated over should
> > only move later properties -- the next call to fdt_next_prop would be
> > based on the start of the property that was modified, which did not
> > change.
> 
> That's true; unless you delete the property entirely.  Inserting an
> unrelated property is also potentially dangerous, though from the
> looks of it we always insert properties at the end in libfdt, so that
> should work ok.
> 
> Fwiw, I (somewhat reluctantly) accepted the need for property offsets,
> in the prototype patch for property iteration I had.  I was going to
> polish it up and push it out, but got sidetracked by other things.
> I've included it below, maybe you'll get to the polishing before I
> do.

Uh.. here's a version that's been fixed up to at least apply to the
current tree.

Index: dtc/libfdt/fdt.c
===================================================================
--- dtc.orig/libfdt/fdt.c	2008-11-07 14:32:36.000000000 +1100
+++ dtc/libfdt/fdt.c	2008-11-07 14:32:48.000000000 +1100
@@ -90,6 +90,31 @@ const void *fdt_offset_ptr(const void *f
 	return p;
 }
 
+const struct fdt_property *_fdt_offset_property(const void *fdt, int offset,
+					       int *lenp)
+{
+	const struct fdt_property *prop;
+	int len;
+
+	if (lenp)
+		*lenp = -FDT_ERR_BADSTRUCTURE;
+
+	prop = fdt_offset_ptr(fdt, offset, sizeof(*prop));
+	if (!prop)
+		return NULL;
+
+	len = fdt32_to_cpu(prop->len);
+
+	prop = fdt_offset_ptr(fdt, offset, sizeof(*prop)+len);
+	if (!prop)
+		return NULL;
+
+	if (lenp)
+		*lenp = len;
+
+	return prop;
+}
+
 uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset)
 {
 	const uint32_t *tagp, *lenp;
@@ -177,6 +202,46 @@ int fdt_next_node(const void *fdt, int o
 	return offset;
 }
 
+int _fdt_next_property(const void *fdt, int offset)
+{
+	uint32_t tag;
+	int nextoffset;
+	int err;
+
+	if ((err = fdt_check_header(fdt)) != 0)
+		return err;
+
+	if (offset % FDT_TAGSIZE)
+		return -FDT_ERR_BADOFFSET;
+
+	tag = fdt_next_tag(fdt, offset, &nextoffset);
+	if ((tag != FDT_BEGIN_NODE) && (tag != FDT_PROP))
+		return -FDT_ERR_BADOFFSET;
+
+	do {
+		offset = nextoffset;
+
+		tag = fdt_next_tag(fdt, offset, &nextoffset);
+		switch (tag) {
+		case FDT_END:
+			return -FDT_ERR_TRUNCATED;
+
+		case FDT_BEGIN_NODE:
+		case FDT_END_NODE:
+		case FDT_NOP:
+			break;
+
+		case FDT_PROP:
+			return offset;
+
+		default:
+			return -FDT_ERR_BADSTRUCTURE;
+		}
+	} while (tag == FDT_NOP);
+
+	return -FDT_ERR_NOTFOUND;
+}
+
 const char *_fdt_find_string(const char *strtab, int tabsize, const char *s)
 {
 	int len = strlen(s) + 1;
Index: dtc/libfdt/fdt_ro.c
===================================================================
--- dtc.orig/libfdt/fdt_ro.c	2008-11-07 14:32:36.000000000 +1100
+++ dtc/libfdt/fdt_ro.c	2008-11-07 14:38:59.000000000 +1100
@@ -203,62 +203,20 @@ const struct fdt_property *fdt_get_prope
 						    const char *name,
 						    int namelen, int *lenp)
 {
-	uint32_t tag;
 	const struct fdt_property *prop;
-	int namestroff;
-	int offset, nextoffset;
-	int err;
-
-	if (((err = fdt_check_header(fdt)) != 0)
-	    || ((err = _fdt_check_node_offset(fdt, nodeoffset)) < 0))
-			goto fail;
-
-	nextoffset = err;
-	do {
-		offset = nextoffset;
-
-		tag = fdt_next_tag(fdt, offset, &nextoffset);
-		switch (tag) {
-		case FDT_END:
-			err = -FDT_ERR_TRUNCATED;
-			goto fail;
-
-		case FDT_BEGIN_NODE:
-		case FDT_END_NODE:
-		case FDT_NOP:
-			break;
-
-		case FDT_PROP:
-			err = -FDT_ERR_BADSTRUCTURE;
-			prop = fdt_offset_ptr(fdt, offset, sizeof(*prop));
-			if (! prop)
-				goto fail;
-			namestroff = fdt32_to_cpu(prop->nameoff);
-			if (_fdt_string_eq(fdt, namestroff, name, namelen)) {
-				/* Found it! */
-				int len = fdt32_to_cpu(prop->len);
-				prop = fdt_offset_ptr(fdt, offset,
-						      sizeof(*prop)+len);
-				if (! prop)
-					goto fail;
+	int offset = nodeoffset;
 
-				if (lenp)
-					*lenp = len;
-
-				return prop;
-			}
-			break;
-
-		default:
-			err = -FDT_ERR_BADSTRUCTURE;
-			goto fail;
-		}
-	} while ((tag != FDT_BEGIN_NODE) && (tag != FDT_END_NODE));
+	while ((offset = _fdt_next_property(fdt, offset)) >= 0) {
+		prop = _fdt_offset_property(fdt, offset, lenp);
+		if (!prop)
+			return NULL;
+		if (_fdt_string_eq(fdt, fdt32_to_cpu(prop->nameoff), name, namelen))
+			/* Found it! */
+			return prop;
+	}
 
-	err = -FDT_ERR_NOTFOUND;
- fail:
 	if (lenp)
-		*lenp = err;
+		*lenp = offset;
 	return NULL;
 }
 
Index: dtc/libfdt/libfdt_internal.h
===================================================================
--- dtc.orig/libfdt/libfdt_internal.h	2008-11-07 14:32:36.000000000 +1100
+++ dtc/libfdt/libfdt_internal.h	2008-11-07 14:32:48.000000000 +1100
@@ -63,6 +63,7 @@
 	}
 
 uint32_t _fdt_next_tag(const void *fdt, int startoffset, int *nextoffset);
+int _fdt_next_property(const void *fdt, int offset);
 int _fdt_check_node_offset(const void *fdt, int offset);
 const char *_fdt_find_string(const char *strtab, int tabsize, const char *s);
 int _fdt_node_end_offset(void *fdt, int nodeoffset);
Index: dtc/libfdt/libfdt.h
===================================================================
--- dtc.orig/libfdt/libfdt.h	2008-11-07 14:32:48.000000000 +1100
+++ dtc/libfdt/libfdt.h	2008-11-07 14:32:48.000000000 +1100
@@ -128,6 +128,9 @@ static inline void *fdt_offset_ptr_w(voi
 	return (void *)(uintptr_t)fdt_offset_ptr(fdt, offset, checklen);
 }
 
+const struct fdt_property *_fdt_offset_property(const void *fdt, int offset,
+						int *lenp);
+
 uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset);
 
 /**********************************************************************/
@@ -136,6 +139,11 @@ uint32_t fdt_next_tag(const void *fdt, i
 
 int fdt_next_node(const void *fdt, int offset, int *depth);
 
+#define for_each_property(fdt, node, prop, len) \
+	for (int _off = fdt_next_property((fdt), (node)); \
+	     (_off >= 0) && \
+		     (((prop) = fdt_offset_property((fdt), _off, &(len))) >= 0);)
+
 /**********************************************************************/
 /* General functions                                                  */
 /**********************************************************************/
@@ -256,6 +264,7 @@ int fdt_num_mem_rsv(const void *fdt);
  */
 int fdt_get_mem_rsv(const void *fdt, int n, uint64_t *address, uint64_t *size);
 
+
 /**
  * fdt_subnode_offset_namelen - find a subnode based on substring
  * @fdt: pointer to the device tree blob


-- 
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