libfdt: Check node names in one pass in fdt_next_tag() 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, and also calls fdt_offset_ptr() two or three more times per tag, so this dominates lookups such as fdt_path_offset() in large trees. The structure block offset maps linearly to a pointer, so work out where the range that fdt_offset_ptr() accepts ends in fdt_struct_limit_(), rewrite fdt_offset_ptr() in terms of it, and compute that limit once per fdt_next_tag() call. Check each access against it 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, 17,899 properties) on x86-64, built with gcc -O2 and the default FDT_ASSUME_MASK, a full walk with fdt_next_tag() takes 131 us instead of 291 us (227 us if only FDT_BEGIN_NODE uses the precomputed limit, as the other three checks run 65,745 times during the walk), and fdt_path_offset() of /chosen, which is near the end, takes 142 us instead of 382 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> Message-ID: <CAOSmRziU5g9WO2R86d3w0mBgNmtwpdHfKu9EXTSD9d5cw-pNcw@mail.gmail.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
diff --git a/libfdt/fdt.c b/libfdt/fdt.c index 56d4dcb..d9ccb70 100644 --- a/libfdt/fdt.c +++ b/libfdt/fdt.c
@@ -145,37 +145,59 @@ return 0; } -const void *fdt_offset_ptr(const void *fdt, int offset, unsigned int len) +/* + * End offset (exclusive, relative to the structure block) of the range that + * fdt_offset_ptr() accepts, capped at INT_MAX. + */ +static int fdt_struct_limit_(const void *fdt) { - unsigned int uoffset = offset; - unsigned int absoffset = offset + fdt_off_dt_struct(fdt); + uint32_t limit = INT_MAX; - if (offset < 0) + if (!can_assume(VALID_INPUT)) { + uint32_t base = fdt_off_dt_struct(fdt); + uint32_t totalsize = fdt_totalsize(fdt); + + if (base > totalsize) + return 0; + if (totalsize - base < limit) + limit = totalsize - base; + } + + if (can_assume(LATEST) || fdt_version(fdt) >= 0x11) { + uint32_t size = fdt_size_dt_struct(fdt); + + if (size < limit) + limit = size; + } + + return limit; +} + +static const void *fdt_offset_ptr_limit_(const void *fdt, int limit, + int offset, unsigned int len) +{ + if ((offset < 0) || (offset > limit) + || (len > (unsigned int)(limit - offset))) return NULL; - if (!can_assume(VALID_INPUT)) - if ((absoffset < uoffset) - || ((absoffset + len) < absoffset) - || (absoffset + len) > fdt_totalsize(fdt)) - return NULL; - - if (can_assume(LATEST) || fdt_version(fdt) >= 0x11) - if (((uoffset + len) < uoffset) - || ((offset + len) > fdt_size_dt_struct(fdt))) - return NULL; - return fdt_offset_ptr_(fdt, offset); } +const void *fdt_offset_ptr(const void *fdt, int offset, unsigned int len) +{ + return fdt_offset_ptr_limit_(fdt, fdt_struct_limit_(fdt), offset, len); +} + uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset) { const fdt32_t *tagp, *lenp; uint32_t tag, len, sum; + 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 +206,18 @@ *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 */ + if (offset < 0 || offset >= limit) return FDT_END; /* premature end */ + p = fdt_offset_ptr_(fdt, offset); + nul = memchr(p, '\0', limit - offset); + 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 +245,8 @@ 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);