[U-Boot] [PATCH] ext4fs: Add ext4 extent tree cache

[Tom Rini]

On Mon, Mar 26, 2018 at 04:05:24PM -0700, evan.g.thompson at gmail.com wrote:

> From: Evan Thompson <evan.thompson at flukenetworks.com>
> 
> 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 at flukenetworks.com>
> ---
>  doc/README.ext4       |  7 +++++
>  fs/ext4/ext4_common.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++----
>  2 files changed, 76 insertions(+), 5 deletions(-)
> 
> diff --git a/doc/README.ext4 b/doc/README.ext4
> index 8ecd21eee3..a501b92396 100644
> --- a/doc/README.ext4
> +++ b/doc/README.ext4
> @@ -33,6 +33,13 @@ In addition, to get the write access command "ext4write", enable:
>  which automatically selects CONFIG_EXT4_WRITE if it wasn't defined
>  already.
>  
> +For files with extents, an ext4 extent tree cache improves performance:
> +
> +  CONFIG_EXT4_EXTENT_CACHE_SIZE <#>
> +
> +The above cache size defaults to 5 if not defined. This default is
> +strongly recommended. 0 will turn off extent caching.
> +
>  Also relevant are the generic filesystem commands, selected by:
>  
>    CONFIG_CMD_FS_GENERIC
> diff --git a/fs/ext4/ext4_common.c b/fs/ext4/ext4_common.c
> index e3cc30a1e0..61aade1ced 100644
> --- a/fs/ext4/ext4_common.c
> +++ b/fs/ext4/ext4_common.c
> @@ -1523,6 +1523,47 @@ void ext4fs_allocate_blocks(struct ext2_inode *file_inode,
>  
>  #endif
>  
> +/* Extent tree cache caches one entry per tree level
> + * eg, ext_block->eh_depth is used as the index into the cache
> + *
> + * If the tree is deeper than CONFIG_EXT4_EXTENT_CACHE_SIZE (very unlikely),
> + * file read performance will be impacted by repeated re-reads
> + * of those index nodes.
> + */
> +
> +#ifndef CONFIG_EXT4_EXTENT_CACHE_SIZE
> +#define CONFIG_EXT4_EXTENT_CACHE_SIZE 5
> +#endif

This needs to be done in Kconfig.  Also, is there any sort of testing we
could add to test/fs/fs-test.sh for this code?  Thanks!

-- 
Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.denx.de/pipermail/u-boot/attachments/20180510/733aa878/attachment.sig>