[PATCH] Introduce fdt_get_path_len() method

[PATCH] Introduce fdt_get_path_len() method

[Pantelis Antoniou]

This method returns the length of the full path of the node so that
it may be used without having to call fdt_get_path() using a worst
case sized buffer.

Signed-off-by: Pantelis Antoniou <pantelis.antoniou-OWPKS81ov/FWk0Htik3J/w@public.gmane.org>
---
 libfdt/fdt_ro.c | 28 ++++++++++++++++++++++++++++
 libfdt/libfdt.h | 22 ++++++++++++++++++++++
 2 files changed, 50 insertions(+)

diff --git a/libfdt/fdt_ro.c b/libfdt/fdt_ro.c
index 08de2cc..8b67f2f 100644
--- a/libfdt/fdt_ro.c
+++ b/libfdt/fdt_ro.c
@@ -438,6 +438,34 @@ int fdt_get_path(const void *fdt, int nodeoffset, char *buf, int buflen)
 	return offset; /* error from fdt_next_node() */
 }
 
+int fdt_get_path_len(const void *fdt, int nodeoffset)
+{
+	int len = 0, namelen;
+	const char *name;
+
+	FDT_CHECK_HEADER(fdt);
+
+	for (;;) {
+		name = fdt_get_name(fdt, nodeoffset, &namelen);
+		if (!name)
+			return namelen;
+
+		/* root? we're done */
+		if (namelen == 0)
+			break;
+
+		nodeoffset = fdt_parent_offset(fdt, nodeoffset);
+		if (nodeoffset < 0)
+			return nodeoffset;
+		len += namelen + 1;
+	}
+
+	/* in case of root pretend it's "/" */
+	if (len == 0)
+		len++;
+	return len;
+}
+
 int fdt_supernode_atdepth_offset(const void *fdt, int nodeoffset,
 				 int supernodedepth, int *nodedepth)
 {
diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
index e01c645..2c0b570 100644
--- a/libfdt/libfdt.h
+++ b/libfdt/libfdt.h
@@ -765,6 +765,28 @@ const char *fdt_get_alias(const void *fdt, const char *name);
 int fdt_get_path(const void *fdt, int nodeoffset, char *buf, int buflen);
 
 /**
+ * fdt_get_path_len - determine the length of the full path of a node
+ * @fdt: pointer to the device tree blob
+ * @nodeoffset: offset of the node whose path to find
+ *
+ * fdt_get_path_len() computes the size of the full path of the node at
+ * offset nodeoffset.
+ *
+ * NOTE: This function is expensive, as it must scan the device tree
+ * structure from the start to nodeoffset.
+ *
+ * returns:
+ *	> 0, on success
+ *		length of the full path of the node
+ *	-FDT_ERR_BADOFFSET, nodeoffset does not refer to a BEGIN_NODE tag
+ *	-FDT_ERR_BADMAGIC,
+ *	-FDT_ERR_BADVERSION,
+ *	-FDT_ERR_BADSTATE,
+ *	-FDT_ERR_BADSTRUCTURE, standard meanings
+ */
+int fdt_get_path_len(const void *fdt, int nodeoffset);
+
+/**
  * fdt_supernode_atdepth_offset - find a specific ancestor of a node
  * @fdt: pointer to the device tree blob
  * @nodeoffset: offset of the node whose parent to find
-- 
2.1.4

Re: [PATCH] Introduce fdt_get_path_len() method

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 3966 bytes --]

On Thu, Jul 13, 2017 at 12:23:32AM +0300, Pantelis Antoniou wrote:
> This method returns the length of the full path of the node so that
> it may be used without having to call fdt_get_path() using a worst
> case sized buffer.
> 
> Signed-off-by: Pantelis Antoniou <pantelis.antoniou-OWPKS81ov/FWk0Htik3J/w@public.gmane.org>

Hm, I can see why you want this, but the implementation is a bit
horrifyingly slow - even by the standards of the slow functions in
libfdt.

I originally intended for the get_path() function to return the path
length, even if it wouldn't all fit in the buffer.  However, I wasn't
able - the buffer into which it builds the path doubles as a sort of
stack keeping track of where we are.  It could be replaced by an
explicit stack, which might be smaller than the buffer, but it's still
a data structure of indeterminite size, which is pretty awkward here.

In most cases I'd suggest a user just use get_path(), then retry with
a larger buffer if it fails, but obviously that doesn't really work
from within the overlay application code either.  I have some ideas on
how to avoid the need for a get_path_len() which I'll expand on in
that thread.

> ---
>  libfdt/fdt_ro.c | 28 ++++++++++++++++++++++++++++
>  libfdt/libfdt.h | 22 ++++++++++++++++++++++
>  2 files changed, 50 insertions(+)
> 
> diff --git a/libfdt/fdt_ro.c b/libfdt/fdt_ro.c
> index 08de2cc..8b67f2f 100644
> --- a/libfdt/fdt_ro.c
> +++ b/libfdt/fdt_ro.c
> @@ -438,6 +438,34 @@ int fdt_get_path(const void *fdt, int nodeoffset, char *buf, int buflen)
>  	return offset; /* error from fdt_next_node() */
>  }
>  
> +int fdt_get_path_len(const void *fdt, int nodeoffset)
> +{
> +	int len = 0, namelen;
> +	const char *name;
> +
> +	FDT_CHECK_HEADER(fdt);
> +
> +	for (;;) {
> +		name = fdt_get_name(fdt, nodeoffset, &namelen);
> +		if (!name)
> +			return namelen;
> +
> +		/* root? we're done */
> +		if (namelen == 0)
> +			break;
> +
> +		nodeoffset = fdt_parent_offset(fdt, nodeoffset);

The basic problem is that fdt_parent_offset() is already a slow
function requiring a full scan of the blob, and it's called here
repeatedly.

> +		if (nodeoffset < 0)
> +			return nodeoffset;
> +		len += namelen + 1;
> +	}
> +
> +	/* in case of root pretend it's "/" */
> +	if (len == 0)
> +		len++;
> +	return len;
> +}
> +
>  int fdt_supernode_atdepth_offset(const void *fdt, int nodeoffset,
>  				 int supernodedepth, int *nodedepth)
>  {
> diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
> index e01c645..2c0b570 100644
> --- a/libfdt/libfdt.h
> +++ b/libfdt/libfdt.h
> @@ -765,6 +765,28 @@ const char *fdt_get_alias(const void *fdt, const char *name);
>  int fdt_get_path(const void *fdt, int nodeoffset, char *buf, int buflen);
>  
>  /**
> + * fdt_get_path_len - determine the length of the full path of a node
> + * @fdt: pointer to the device tree blob
> + * @nodeoffset: offset of the node whose path to find
> + *
> + * fdt_get_path_len() computes the size of the full path of the node at
> + * offset nodeoffset.
> + *
> + * NOTE: This function is expensive, as it must scan the device tree
> + * structure from the start to nodeoffset.
> + *
> + * returns:
> + *	> 0, on success
> + *		length of the full path of the node
> + *	-FDT_ERR_BADOFFSET, nodeoffset does not refer to a BEGIN_NODE tag
> + *	-FDT_ERR_BADMAGIC,
> + *	-FDT_ERR_BADVERSION,
> + *	-FDT_ERR_BADSTATE,
> + *	-FDT_ERR_BADSTRUCTURE, standard meanings
> + */
> +int fdt_get_path_len(const void *fdt, int nodeoffset);
> +
> +/**
>   * fdt_supernode_atdepth_offset - find a specific ancestor of a node
>   * @fdt: pointer to the device tree blob
>   * @nodeoffset: offset of the node whose parent to find

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]