Re: [PATCH] libfdt: Check node names in one pass in fdt_next_tag()

[David Gibson <david@gibson.dropbear.id.au>]

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

On Sun, Nov 01, 2026 at 08:30:51PM -0600, Kelvin Zhang wrote:
> fdt_next_tag() skips the name of a node by calling fdt_offset_ptr()
> for each byte. Unless FDT_ASSUME_MASK includes ASSUME_VALID_INPUT,
> each call reads totalsize, off_dt_struct, version and size_dt_struct
> from the header again and checks the access against them. Every walk
> over the structure block skips the name of every node it passes, so
> this dominates lookups such as fdt_path_offset() in large trees.
> 
> The structure block offset maps linearly to a pointer, so work out
> once per call where the range that fdt_offset_ptr() accepts ends.
> Check each access against that with plain comparisons, and find the
> end of the name with one memchr() over the rest of the range. The
> checks themselves don't change: a name that isn't terminated before
> the end of the structure block still makes fdt_next_tag() return
> FDT_END. The range is also capped at INT_MAX, since offsets are ints,
> so a header that claims more than 2 GiB now ends the walk instead of
> producing a negative next offset.
> 
> With a 612 KiB tree (3,012 nodes) on x86-64, built with gcc -O2 and
> the default FDT_ASSUME_MASK, a full walk with fdt_next_tag() takes
> 122 us instead of 297 us, and fdt_path_offset() of /chosen, which is
> near the end, 148 us instead of 434 us. In Android's Generic
> Bootloader on an AArch64 device at 600 MHz, also with the default
> FDT_ASSUME_MASK, the fixups made to that tree after applying overlays
> take 23.3 ms instead of 33.1 ms.

Mostly seems a reasonable idea, and good job making sure to handle
overflows and other edge cases.  Some comments and queries below,
however.

> 
> Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> ---
>  libfdt/fdt.c | 63 ++++++++++++++++++++++++++++++++++++++++++++--------
>  1 file changed, 54 insertions(+), 9 deletions(-)
> 
> diff --git a/libfdt/fdt.c b/libfdt/fdt.c
> index 56d4dcb..7325aa2 100644
> --- a/libfdt/fdt.c
> +++ b/libfdt/fdt.c
> @@ -167,15 +167,59 @@ const void *fdt_offset_ptr(const void *fdt, int
> offset, unsigned int len)
>  	return fdt_offset_ptr_(fdt, offset);
>  }
> 
> +/*
> + * End offset (exclusive, relative to the structure block) of the range that
> + * fdt_offset_ptr() accepts, capped at INT_MAX, so that callers making several
> + * accesses can check each of them with plain comparisons instead of reading
> + * the header again.
> + */
> +static unsigned int fdt_struct_limit_(const void *fdt)

I'd suggest this return an int, rather than unsigned, since int is how
offsets are generally represented in the API.

> +{
> +	unsigned int limit = INT_MAX;
> +
> +	if (!can_assume(VALID_INPUT)) {
> +		unsigned int base = fdt_off_dt_struct(fdt);
> +		unsigned int totalsize = fdt_totalsize(fdt);
> +		unsigned int avail = (base <= totalsize) ? totalsize - base : 0;

Since fdt_off_dt_struct() and fdt_totalsize() return uint32_t, it's
probably better to do the arithmetic in uint32_t, rather than plain
unsigned int (though they'll almost always be the same thing).

> +		if (avail < limit)
> +			limit = avail;
> +	}
> +
> +	if (can_assume(LATEST) || fdt_version(fdt) >= 0x11) {
> +		unsigned int size = fdt_size_dt_struct(fdt);
> +
> +		if (size < limit)
> +			limit = size;
> +	}
> +
> +	return limit;
> +}

Having created this function, it would be good to rewrite
fdt_offset_ptr() in terms of it, to avoid logic duplication.

> +
> +/*
> + * Checks @offset and @len > 0 like fdt_offset_ptr() does, against
> + * @limit = fdt_struct_limit_(@fdt).
> + */
> +static const void *fdt_offset_ptr_limit_(const void *fdt, unsigned int limit,
> +					 int offset, unsigned int len)
> +{
> +	if ((offset < 0) || (len > limit)
> +	    || ((unsigned int)offset > limit - len))
> +		return NULL;
> +
> +	return fdt_offset_ptr_(fdt, offset);
> +}
> +
>  uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
>  {
>  	const fdt32_t *tagp, *lenp;
>  	uint32_t tag, len, sum;
> +	unsigned int limit = fdt_struct_limit_(fdt);
>  	int offset = startoffset;
> -	const char *p;
> +	const char *p, *nul;
> 
>  	*nextoffset = -FDT_ERR_TRUNCATED;
> -	tagp = fdt_offset_ptr(fdt, offset, FDT_TAGSIZE);
> +	tagp = fdt_offset_ptr_limit_(fdt, limit, offset, FDT_TAGSIZE);

I'm assuming the vast majority of the speedup comes from the
FDT_BEGIN_NODE case, and these other uses of the precomputed limit are
trivial.  Given that, I'm not really sure it's worth the more awkward
interface for those other cases.

>  	if (!can_assume(VALID_DTB) && !tagp)
>  		return FDT_END; /* premature end */
>  	tag = fdt32_to_cpu(*tagp);
> @@ -184,16 +228,16 @@ uint32_t fdt_next_tag(const void *fdt, int
> startoffset, int *nextoffset)
>  	*nextoffset = -FDT_ERR_BADSTRUCTURE;
>  	switch (tag) {
>  	case FDT_BEGIN_NODE:
> -		/* skip name */
> -		do {
> -			p = fdt_offset_ptr(fdt, offset++, 1);
> -		} while (p && (*p != '\0'));
> -		if (!can_assume(VALID_DTB) && !p)
> +		/* skip name: check the rest of the block once, then scan it */
> +		p = fdt_offset_ptr_limit_(fdt, limit, offset, 1);

The 1-byte offset_ptr() is a little awkward here.  I wonder if it
would be nice to create an fdt_offset_ptr_string() which internally
computes the limit to safely pull a \0 terminated string from a given
offset.

> +		nul = p ? memchr(p, '\0', limit - offset) : NULL;
> +		if (!nul)
>  			return FDT_END; /* premature end */
> +		offset += nul - p + 1;
>  		break;
> 
>  	case FDT_PROP:
> -		lenp = fdt_offset_ptr(fdt, offset, sizeof(*lenp));
> +		lenp = fdt_offset_ptr_limit_(fdt, limit, offset, sizeof(*lenp));
>  		if (!can_assume(VALID_DTB) && !lenp)
>  			return FDT_END; /* premature end */
> 
> @@ -221,7 +265,8 @@ uint32_t fdt_next_tag(const void *fdt, int
> startoffset, int *nextoffset)
>  		return FDT_END;
>  	}
> 
> -	if (!fdt_offset_ptr(fdt, startoffset, offset - startoffset))
> +	if (!fdt_offset_ptr_limit_(fdt, limit, startoffset,
> +				   offset - startoffset))
>  		return FDT_END; /* premature end */
> 
>  	*nextoffset = FDT_TAGALIGN(offset);
> 
> base-commit: c22868416b8db8354ce5db29d3494dda688a2ae3
> -- 
> 2.56.0.385.gac671c819a-goog
> 

-- 
David Gibson (he or they)	| 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 --]