linux-kernel - RE: [PATCH v2] exfat: speed up iterate/lookup by fixing start point of traversing cluster chain

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <b88e01d71ca5$a6e424b0$f4ac6e10$@samsung.com>
Date:   Fri, 19 Mar 2021 18:53:02 +0900
From:   "Sungjong Seo" <sj1557.seo@...sung.com>
To:     "'Hyeongseok Kim'" <hyeongseok@...il.com>,
        <namjae.jeon@...sung.com>
Cc:     <linux-kernel@...r.kernel.org>, <linux-fsdevel@...r.kernel.org>,
        <sj1557.seo@...sung.com>
Subject: RE: [PATCH v2] exfat: speed up iterate/lookup by fixing start point
 of traversing cluster chain

> When directory iterate and lookup is called, there's a buggy rewinding of
> start point for traversing cluster chain to the parent directory entry's
> first cluster. This caused repeated cluster chain traversing from the
> first entry of the parent directory that would show worse performance if
> huge amounts of files exist under the parent directory.
> Fix not to rewind, make continue from currently referenced cluster and dir
> entry.
> 
> Tested with 50,000 files under single directory / 256GB sdcard, with
> command "time ls -l > /dev/null",
> Before :     0m08.69s real     0m00.27s user     0m05.91s system
> After  :     0m07.01s real     0m00.25s user     0m04.34s system
> 
> Signed-off-by: Hyeongseok Kim <hyeongseok@...il.com>
> ---
>  fs/exfat/dir.c      | 39 ++++++++++++++++++++++++++++++++-------
>  fs/exfat/exfat_fs.h |  2 +-
>  fs/exfat/namei.c    |  6 ++++--
>  3 files changed, 37 insertions(+), 10 deletions(-)
> 
> diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c index
> e1d5536de948..63f08987a8fe 100644
> --- a/fs/exfat/dir.c
> +++ b/fs/exfat/dir.c
> @@ -147,7 +147,7 @@ static int exfat_readdir(struct inode *inode, loff_t
> *cpos, struct exfat_dir_ent
[snip]
> + * @de:         If p_uniname is found, filled with optimized dir/entry
> + *              for traversing cluster chain. Basically,
> + *              (p_dir.dir+return entry) and (de.dir.dir+de.entry) are
> + *              pointing the same physical directory entry, but if
> + *              caller needs to start to traverse cluster chain,
> + *              it's better option to choose the information in de.
> + *              Caller could only trust .dir and .entry field.

exfat-fs has exfat_hint structure for keeping clusters and entries as hints.
Of course, the caller, exfat_find(), should adjust exfat_chain with
hint value just before calling exfat_get_dentry_set() as follows.

        /* adjust cdir to the optimized value */
        cdir.dir = hint_opt.clu;
        if (cdir.flag & ALLOC_NO_FAT_CHAIN) {
                cdir.size -= dentry / sbi->dentries_per_clu;
        dentry = hint_opt.eidx;

What do you think about using it?

> + * @return:
> + *   >= 0:      file directory entry position where the name exists
> + *   -ENOENT:   entry with the name does not exist
> + *   -EIO:      I/O error
>   */
[snip]
> @@ -1070,11 +1081,14 @@ int exfat_find_dir_entry(struct super_block *sb,
> struct exfat_inode_info *ei,
>  		}
> 
>  		if (clu.flags == ALLOC_NO_FAT_CHAIN) {
> -			if (--clu.size > 0)
> +			if (--clu.size > 0) {
> +				exfat_chain_dup(&de->dir, &clu);

If you want to make a backup of the clu, it seems more appropriate to move
exfat_chain_dup() right above the "if".

>  				clu.dir++;
> +			}
>  			else
>  				clu.dir = EXFAT_EOF_CLUSTER;
>  		} else {
> +			exfat_chain_dup(&de->dir, &clu);
>  			if (exfat_get_next_cluster(sb, &clu.dir))
>  				return -EIO;
>  		}
> @@ -1101,6 +1115,17 @@ int exfat_find_dir_entry(struct super_block *sb,
> struct exfat_inode_info *ei,
>  	return -ENOENT;
> 
>  found:
> +	/* set as dentry in cluster */
> +	de->entry = (dentry - num_ext) & (dentries_per_clu - 1);
> +	/*
> +	 * if dentry_set spans to the next_cluster,
> +	 * e.g. (de->entry + num_ext + 1 > dentries_per_clu)
> +	 * current de->dir is correct which have previous cluster info,
> +	 * but if it doesn't span as below, "clu" is correct, so update.
> +	 */
> +	if (de->entry + num_ext + 1 <= dentries_per_clu)
> +		exfat_chain_dup(&de->dir, &clu);
> +

Let it be simple.
1. Keep an old value in the stack variable, when it found a FILE or DIR
entry.
2. And just copy that here.

There are more assignments, but I think its impact might be negligible.
Thanks.