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

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

[Kelvin Zhang]

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.

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)
+{
+	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;
+
+		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;
+}
+
+/*
+ * 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);
 	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);
+		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

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

[David Gibson]

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

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

[Kelvin Zhang]

Hi David,

Thanks for the thorough review!

> I'd suggest this return an int, rather than unsigned, since int is how
> offsets are generally represented in the API.
...
> 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).
...
> Having created this function, it would be good to rewrite
> fdt_offset_ptr() in terms of it, to avoid logic duplication.

Done in v2: fdt_struct_limit_() now uses uint32_t internally and returns
int (-1 when off_dt_struct > totalsize, so even len == 0 is rejected),
and fdt_offset_ptr() is rewritten as:

	return fdt_offset_ptr_limit_(fdt, fdt_struct_limit_(fdt), offset, len);

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

I measured the breakdown on the 612 KiB tree (3,012 nodes, 17,899
properties):

- Unpatched fdt_next_tag() full walk: 291 us
- Only FDT_BEGIN_NODE using the precomputed limit (other three checks
  calling fdt_offset_ptr()): 227 us
- All four checks in fdt_next_tag() sharing the precomputed limit: 131 us

So ~60% of the full-walk speedup actually comes from those other three
checks (tagp, lenp, and the final offset - startoffset check). Because
the tree has ~6x as many properties as nodes, those three sites run
65,745 times during the walk (vs ~36,000 byte checks in FDT_BEGIN_NODE),
and the compiler does not inline/hoist fdt_offset_ptr() across the
*nextoffset stores in fdt_next_tag().

In addition, when the bootloader is built with stack protection enabled
(e.g. -fstack-protector-strong), those out-of-line bounds-check calls
become noticeably more expensive, especially on our test device where
the CPU runs at a relatively low clock frequency (600 MHz) during boot.

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

Agreed that passing len = 1 was awkward. Since fdt_next_tag() already
has limit in hand, v2 checks offset < 0 || offset >= limit directly in
FDT_BEGIN_NODE before calling fdt_offset_ptr_(fdt, offset) and memchr().

Sending v2 shortly (also stripping the function names from @@ hunk
headers so Gmail's outbound gateway doesn't wrap long hunk header lines).

Best regards,
Kelvin

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

[David Gibson]

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

On Sun, Nov 01, 2026 at 08:50:01PM -0800, Kelvin Zhang wrote:
> Hi David,
> 
> Thanks for the thorough review!
> 
> > I'd suggest this return an int, rather than unsigned, since int is how
> > offsets are generally represented in the API.
> ...
> > 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).
> ...
> > Having created this function, it would be good to rewrite
> > fdt_offset_ptr() in terms of it, to avoid logic duplication.
> 
> Done in v2: fdt_struct_limit_() now uses uint32_t internally and returns
> int (-1 when off_dt_struct > totalsize, so even len == 0 is rejected),
> and fdt_offset_ptr() is rewritten as:
> 
> 	return fdt_offset_ptr_limit_(fdt, fdt_struct_limit_(fdt), offset, len);
> 
> > 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.
> 
> I measured the breakdown on the 612 KiB tree (3,012 nodes, 17,899
> properties):
> 
> - Unpatched fdt_next_tag() full walk: 291 us
> - Only FDT_BEGIN_NODE using the precomputed limit (other three checks
>   calling fdt_offset_ptr()): 227 us
> - All four checks in fdt_next_tag() sharing the precomputed limit: 131 us
> 
> So ~60% of the full-walk speedup actually comes from those other three
> checks (tagp, lenp, and the final offset - startoffset check). Because
> the tree has ~6x as many properties as nodes, those three sites run
> 65,745 times during the walk (vs ~36,000 byte checks in FDT_BEGIN_NODE),
> and the compiler does not inline/hoist fdt_offset_ptr() across the
> *nextoffset stores in fdt_next_tag().

Huh, interesting.  Thanks for checking.

> In addition, when the bootloader is built with stack protection enabled
> (e.g. -fstack-protector-strong), those out-of-line bounds-check calls
> become noticeably more expensive, especially on our test device where
> the CPU runs at a relatively low clock frequency (600 MHz) during boot.
> 
> > 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.
> 
> Agreed that passing len = 1 was awkward. Since fdt_next_tag() already
> has limit in hand, v2 checks offset < 0 || offset >= limit directly in
> FDT_BEGIN_NODE before calling fdt_offset_ptr_(fdt, offset) and memchr().
> 
> Sending v2 shortly (also stripping the function names from @@ hunk
> headers so Gmail's outbound gateway doesn't wrap long hunk header
> lines).

Ok.

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