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] [day] [month] [year] [list]

Message-ID: <a43fafea-3f35-76c2-4173-9709c1f51bb0@gmail.com>
Date:   Mon, 22 Mar 2021 09:12:21 +0900
From:   Hyeongseok Kim <hyeongseok@...il.com>
To:     Sungjong Seo <sj1557.seo@...sung.com>, namjae.jeon@...sung.com
Cc:     linux-kernel@...r.kernel.org, linux-fsdevel@...r.kernel.org
Subject: Re: [PATCH v2] exfat: speed up iterate/lookup by fixing start point
 of traversing cluster chain

Hi,
On 3/19/21 6:53 PM, Sungjong Seo wrote:
>> 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?
Agreed.
What I want to change here is very clear and any way to achieve the goal 
would be good.
>> + * @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".
Yes, but we would not need this backup any more.
>
>>   				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.
>
>
OK. I thought this routine is more straightforward to understand what is 
being done here.
But I don't have any strong opinion about this, so I'll change in that way.
BTW, I think we can do this without local variable.