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

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

[Hyeongseok Kim]

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@gmail.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
 					0);
 
 			*uni_name.name = 0x0;
-			exfat_get_uniname_from_ext_entry(sb, &dir, dentry,
+			exfat_get_uniname_from_ext_entry(sb, &clu, i,
 				uni_name.name);
 			exfat_utf16_to_nls(sb, &uni_name,
 				dir_entry->namebuf.lfn,
@@ -911,14 +911,24 @@ enum {
 };
 
 /*
- * return values:
- *   >= 0	: return dir entiry position with the name in dir
- *   -ENOENT	: entry with the name does not exist
- *   -EIO	: I/O error
+ * @ei:         inode info of parent directory
+ * @p_dir:      directory structure of parent directory
+ * @num_entries entry size of p_uniname
+ * @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.
+ * @return:
+ *   >= 0:      file directory entry position where the name exists
+ *   -ENOENT:   entry with the name does not exist
+ *   -EIO:      I/O error
  */
 int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 		struct exfat_chain *p_dir, struct exfat_uni_name *p_uniname,
-		int num_entries, unsigned int type)
+		int num_entries, unsigned int type, struct exfat_dir_entry *de)
 {
 	int i, rewind = 0, dentry = 0, end_eidx = 0, num_ext = 0, len;
 	int order, step, name_len = 0;
@@ -933,6 +943,7 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 	dentries_per_clu = sbi->dentries_per_clu;
 
 	exfat_chain_dup(&clu, p_dir);
+	exfat_chain_dup(&de->dir, p_dir);
 
 	if (hint_stat->eidx) {
 		clu.dir = hint_stat->clu;
@@ -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);
 				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);
+
 	/* next dentry we'll find is out of this cluster */
 	if (!((dentry + 1) & (dentries_per_clu - 1))) {
 		int ret = 0;
diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h
index 169d0b602f5e..5a524febb79b 100644
--- a/fs/exfat/exfat_fs.h
+++ b/fs/exfat/exfat_fs.h
@@ -457,7 +457,7 @@ void exfat_update_dir_chksum_with_entry_set(struct exfat_entry_set_cache *es);
 int exfat_calc_num_entries(struct exfat_uni_name *p_uniname);
 int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 		struct exfat_chain *p_dir, struct exfat_uni_name *p_uniname,
-		int num_entries, unsigned int type);
+		int num_entries, unsigned int type, struct exfat_dir_entry *de);
 int exfat_alloc_new_dir(struct inode *inode, struct exfat_chain *clu);
 int exfat_find_location(struct super_block *sb, struct exfat_chain *p_dir,
 		int entry, sector_t *sector, int *offset);
diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
index d9e8ec689c55..0c82c72d9662 100644
--- a/fs/exfat/namei.c
+++ b/fs/exfat/namei.c
@@ -596,6 +596,8 @@ static int exfat_find(struct inode *dir, struct qstr *qname,
 	struct exfat_inode_info *ei = EXFAT_I(dir);
 	struct exfat_dentry *ep, *ep2;
 	struct exfat_entry_set_cache *es;
+	/* for optimized dir & entry to prevent long traverse of cluster chain */
+	struct exfat_dir_entry de_opt;
 
 	if (qname->len == 0)
 		return -ENOENT;
@@ -619,7 +621,7 @@ static int exfat_find(struct inode *dir, struct qstr *qname,
 
 	/* search the file name for directories */
 	dentry = exfat_find_dir_entry(sb, ei, &cdir, &uni_name,
-			num_entries, TYPE_ALL);
+			num_entries, TYPE_ALL, &de_opt);
 
 	if (dentry < 0)
 		return dentry; /* -error value */
@@ -628,7 +630,7 @@ static int exfat_find(struct inode *dir, struct qstr *qname,
 	info->entry = dentry;
 	info->num_subdirs = 0;
 
-	es = exfat_get_dentry_set(sb, &cdir, dentry, ES_2_ENTRIES);
+	es = exfat_get_dentry_set(sb, &de_opt.dir, de_opt.entry, ES_2_ENTRIES);
 	if (!es)
 		return -EIO;
 	ep = exfat_get_dentry_cached(es, 0);
-- 
2.27.0.83.g0313f36

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

[Sungjong Seo]

> 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@gmail.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.

Re: [PATCH v2] exfat: speed up iterate/lookup by fixing start point of traversing cluster chain

[Hyeongseok Kim]

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@gmail.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.