In ext4, the file inode can store up to 4 extents. If a file requires
more (due to size or fragmentation), an extent index tree is used.
Currently, u-boot reads a node from each level of the extent tree
for every block read, which is very inefficient when extent tree
depth is > 0.
This patch adds a cache for the extent tree. We cache the 1
most-recently-seen node at each extent tree level. The typical workload
is sequential block access, so once we leave a given tree node, it will
not be revisited. Therefore, it makes sense to just cache one node
per tree level.
Cached blocks are lazily allocated. The typical case is extent tree
depth = 0, in which case no caching is needed and no allocations will
occur.
For files with extent tree depth = 1, this patch produces a ~10x
improvement in read speed. For deeper extent trees, the improvement is
larger. On my test device, a 3MB file which previously took 9s to read
now takes 150ms.
Cache size is configurable with CONFIG_EXT4_EXTENT_CACHE_SIZE. However
the default of 5 (the maximum depth of well-formed extent trees) is
recommended.
Signed-off-by: Evan Thompson <evan.thompson@flukenetworks.com>
Reviewed-by: Tom Rini <trini@konsulko.com>
Cherry-picked-by: Alexandre Bard <alexandre.bard@netmodule.com>
BugzID: 57904
631ba313ea