On Wed, Mar 14, 2018 at 02:41:04PM +0100, Mario Six wrote:
> fdt_node_offset_by_phandle will return the offset of a node pointed to
> by a given phandle.
>
> The current implementation is wasteful: We iterate over all nodes (using
> fdt_next_node), call fdt_get_phandle on each one to read the phandle
> value (if it's there), compare it with the given phandle, and return the
> current node's offset if the values are equal.
>
> fdt_get_phandle itself may iterate over the properties of each node
> twice (and usually will, since most nodes will have neither the
> "phandle" nor the "linux,phandle" property), and advancing to the next
> node via fdt_next_node will then iterate over all properties again.
>
> Fix this by implementing a function fdt_node_offset_by_phandle_, which
> recursively walks the device tree, checks each encountered property for
> equality with either "phandle" or "linux,phandle", compares the
> found phandle's value with the given phandle, and returns the currently
> traversed node's offset if they're equal.
>
> Since the function uses fdt_next_tag, it encounters each tag at most
> once.
>
> Signed-off-by: Mario Six <mario.six@xxxxxxxx>
As with 1/2 I'm a bit dubious as to whether the increased code
complexity is worth it. But, there's a more important problem..
> ---
> libfdt/fdt_ro.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++-----------
> 1 file changed, 58 insertions(+), 14 deletions(-)
>
> diff --git a/libfdt/fdt_ro.c b/libfdt/fdt_ro.c
> index 7d049fb..51aedbb 100644
> --- a/libfdt/fdt_ro.c
> +++ b/libfdt/fdt_ro.c
> @@ -605,29 +605,73 @@ int fdt_node_offset_by_prop_value(const void *fdt, int startoffset,
> return offset; /* error from fdt_next_node() */
> }
>
> +static int fdt_node_offset_by_phandle_(const void *fdt, uint32_t phandle,
> + int *next_offset, int cur_node)
> +{
> + uint32_t tag;
> +
> + do {
> + int offset;
> + const struct fdt_property *prop;
> + const fdt32_t *php = NULL;
> + int res;
> +
> + offset = *next_offset;
> + tag = fdt_next_tag(fdt, offset, next_offset);
> +
> + switch (tag) {
> + case FDT_NOP:
> + break;
> + case FDT_END_NODE:
> + if (*next_offset > 0)
> + return -FDT_ERR_NOTFOUND;
> + break;
> + case FDT_BEGIN_NODE:
> + res = fdt_node_offset_by_phandle_(fdt, phandle,
> + next_offset, offset);
Recursion isn't ok to use here. Some environments in which libfdt
might run (like the kernel) have extremely constrained stack space.
That's why you'll find a number of libfdt functions that have rather
weird implementations that could be done much more simply with
recursion.
> + if (res >= 0)
> + return res;
> + break;
> + case FDT_END:
> + if (*next_offset >= 0 ||
> + ((*next_offset == -FDT_ERR_TRUNCATED)))
> + return -FDT_ERR_NOTFOUND;
> + break;
> + case FDT_PROP:
> + if (!(prop = fdt_get_property_by_offset(fdt, offset, NULL)))
> + return -FDT_ERR_INTERNAL;
> +
> + if (fdt_string_eq_(fdt, fdt32_to_cpu(prop->nameoff),
> + "phandle", 7))
> + php = (const fdt32_t *)prop->data;
> +
> + if (fdt_string_eq_(fdt, fdt32_to_cpu(prop->nameoff),
> + "linux,phandle", 5 + 1 + 7))
> + php = (const fdt32_t *)prop->data;
> +
> + if (php && fdt32_to_cpu(*php) == phandle)
> + return cur_node;
> +
> + break;
> + }
> + } while (tag != FDT_END);
> +
> + return -FDT_ERR_TRUNCATED;
> +}
> +
> int fdt_node_offset_by_phandle(const void *fdt, uint32_t phandle)
> {
> - int offset;
> + int res;
> + int next_offset = 0;
>
> if ((phandle == 0) || (phandle == -1))
> return -FDT_ERR_BADPHANDLE;
>
> FDT_CHECK_HEADER(fdt);
>
> - /* FIXME: The algorithm here is pretty horrible: we
> - * potentially scan each property of a node in
> - * fdt_get_phandle(), then if that didn't find what
> - * we want, we scan over them again making our way to the next
> - * node. Still it's the easiest to implement approach;
> - * performance can come later. */
> - for (offset = fdt_next_node(fdt, -1, NULL);
> - offset >= 0;
> - offset = fdt_next_node(fdt, offset, NULL)) {
> - if (fdt_get_phandle(fdt, offset) == phandle)
> - return offset;
> - }
> + res = fdt_node_offset_by_phandle_(fdt, phandle, &next_offset, -1);
>
> - return offset; /* error from fdt_next_node() */
> + return res;
> }
>
> int fdt_stringlist_contains(const char *strlist, int listlen, const char *str)
--
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:
signature.asc
Description: PGP signature
