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

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

[Hyeongseok Kim]

When directory iterate and lookup is called, there is a buggy rewinding
of start point for traversing fat chain to the directory entry's first
cluster. This caused repeated fat chain traversing from the first entry
of the directory that would show worse performance if huge amounts of
files exist under single 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 | 42 +++++++++++++++++++++++++++++++++---------
 1 file changed, 33 insertions(+), 9 deletions(-)

diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
index e1d5536de948..59d12eaa0649 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,10 +911,15 @@ 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 directory
+ * @p_dir:      input as directory structure in which we search name
+ *              if found, output as a cluster dir where the name exists
+ *              if not found, not changed from input
+ * @num_entries entry size of p_uniname
+ * @return:
+ *   >= 0:      dir entry position from output p_dir.dir
+ *   -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,
@@ -925,14 +930,16 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 	int dentries_per_clu, num_empty = 0;
 	unsigned int entry_type;
 	unsigned short *uniname = NULL;
-	struct exfat_chain clu;
+	struct exfat_chain clu, tmp_clu;
 	struct exfat_hint *hint_stat = &ei->hint_stat;
 	struct exfat_hint_femp candi_empty;
 	struct exfat_sb_info *sbi = EXFAT_SB(sb);
+	int dentry_in_cluster = 0;
 
 	dentries_per_clu = sbi->dentries_per_clu;
 
 	exfat_chain_dup(&clu, p_dir);
+	exfat_chain_dup(&tmp_clu, p_dir);
 
 	if (hint_stat->eidx) {
 		clu.dir = hint_stat->clu;
@@ -1070,11 +1077,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(&tmp_clu, &clu);
 				clu.dir++;
+			}
 			else
 				clu.dir = EXFAT_EOF_CLUSTER;
 		} else {
+			exfat_chain_dup(&tmp_clu, &clu);
 			if (exfat_get_next_cluster(sb, &clu.dir))
 				return -EIO;
 		}
@@ -1101,6 +1111,16 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 	return -ENOENT;
 
 found:
+	/*
+	 * if dentry_set would span to the next_cluster,
+	 * e.g. (dentries_per_clu - dentry_in_cluster < num_ext + 1)
+	 * "tmp_clu" is correct which is currently saved as previous cluster,
+	 * if doesn't span as below, "clu" is correct, so update for return.
+	 */
+	dentry_in_cluster = (dentry - num_ext) & (dentries_per_clu - 1);
+	if (dentries_per_clu - dentry_in_cluster >= num_ext + 1)
+		exfat_chain_dup(&tmp_clu, &clu);
+
 	/* next dentry we'll find is out of this cluster */
 	if (!((dentry + 1) & (dentries_per_clu - 1))) {
 		int ret = 0;
@@ -1118,13 +1138,17 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 			/* just initialized hint_stat */
 			hint_stat->clu = p_dir->dir;
 			hint_stat->eidx = 0;
-			return (dentry - num_ext);
+
+			exfat_chain_dup(p_dir, &tmp_clu);
+			return dentry_in_cluster;
 		}
 	}
 
 	hint_stat->clu = clu.dir;
 	hint_stat->eidx = dentry + 1;
-	return dentry - num_ext;
+
+	exfat_chain_dup(p_dir, &tmp_clu);
+	return dentry_in_cluster;
 }
 
 int exfat_count_ext_entries(struct super_block *sb, struct exfat_chain *p_dir,
-- 
2.27.0.83.g0313f36

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

[Sungjong Seo]

> When directory iterate and lookup is called, there is a buggy rewinding of
> start point for traversing fat chain to the directory entry's first
> cluster. This caused repeated fat chain traversing from the first entry of
> the directory that would show worse performance if huge amounts of files
> exist under single 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 | 42 +++++++++++++++++++++++++++++++++---------
>  1 file changed, 33 insertions(+), 9 deletions(-)
> 
> diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c index
> e1d5536de948..59d12eaa0649 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);

Looks good. Old code looks like a bug as you said.

>  			exfat_utf16_to_nls(sb, &uni_name,
>  				dir_entry->namebuf.lfn,
> @@ -911,10 +911,15 @@ 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 directory
> + * @p_dir:      input as directory structure in which we search name
> + *              if found, output as a cluster dir where the name exists
> + *              if not found, not changed from input
> + * @num_entries entry size of p_uniname
> + * @return:
> + *   >= 0:      dir entry position from output p_dir.dir
> + *   -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,
> @@ -925,14 +930,16 @@ int exfat_find_dir_entry(struct super_block *sb,
> struct exfat_inode_info *ei,
[snip]
  			hint_stat->clu = p_dir->dir;
>  			hint_stat->eidx = 0;
> -			return (dentry - num_ext);
> +
> +			exfat_chain_dup(p_dir, &tmp_clu);
> +			return dentry_in_cluster;
>  		}
>  	}
> 
>  	hint_stat->clu = clu.dir;
>  	hint_stat->eidx = dentry + 1;
> -	return dentry - num_ext;
> +
> +	exfat_chain_dup(p_dir, &tmp_clu);
> +	return dentry_in_cluster;
>  }

Changing the functionality of exfat find_dir_entry() will affect
exfat_find() and exfat_lookup(), breaking the concept of ei->dir.dir
which should have the starting cluster of its parent directory.

Well, is there any missing patch related to exfat_find()?
It would be nice to modify the caller of this function, exfat_find(),
so that this change in functionality doesn't affect other functions.

Thanks.

> 
>  int exfat_count_ext_entries(struct super_block *sb, struct exfat_chain
> *p_dir,
> --
> 2.27.0.83.g0313f36

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

[Hyeongseok Kim]

On 3/18/21 1:07 AM, Sungjong Seo wrote:
>>   /*
>> - * 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 directory
>> + * @p_dir:      input as directory structure in which we search name
>> + *              if found, output as a cluster dir where the name exists
>> + *              if not found, not changed from input
>> + * @num_entries entry size of p_uniname
>> + * @return:
>> + *   >= 0:      dir entry position from output p_dir.dir
>> + *   -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,
>> @@ -925,14 +930,16 @@ int exfat_find_dir_entry(struct super_block *sb,
>> struct exfat_inode_info *ei,
> [snip]
>    			hint_stat->clu = p_dir->dir;
>>   			hint_stat->eidx = 0;
>> -			return (dentry - num_ext);
>> +
>> +			exfat_chain_dup(p_dir, &tmp_clu);
>> +			return dentry_in_cluster;
>>   		}
>>   	}
>>
>>   	hint_stat->clu = clu.dir;
>>   	hint_stat->eidx = dentry + 1;
>> -	return dentry - num_ext;
>> +
>> +	exfat_chain_dup(p_dir, &tmp_clu);
>> +	return dentry_in_cluster;
>>   }
> Changing the functionality of exfat find_dir_entry() will affect
> exfat_find() and exfat_lookup(), breaking the concept of ei->dir.dir
> which should have the starting cluster of its parent directory.
>
> Well, is there any missing patch related to exfat_find()?
> It would be nice to modify the caller of this function, exfat_find(),
> so that this change in functionality doesn't affect other functions.
>
> Thanks.
>
Whoops, it's a bug. I didn't catch that, thanks.
Maybe it could make exfat inode hash problem.
I wanted to reuse current function interface but, it would be better
to add an addtional parameter. I'll fix this in v2.