linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain
@ 2022-11-02  7:11 ` Yuezhang.Mo
  2022-11-03 12:51   ` Sungjong Seo
  2022-11-08  8:00   ` Namjae Jeon
  0 siblings, 2 replies; 3+ messages in thread
From: Yuezhang.Mo @ 2022-11-02  7:11 UTC (permalink / raw)
  To: Namjae Jeon, Sungjong Seo
  Cc: linux-kernel, linux-fsdevel, Andy.Wu, Wataru.Aoyama

After traversing all directory entries, hint the empty directory
entry no matter whether or not there are enough empty directory
entries.

After this commit, hint the empty directory entries like this:

1. Hint the deleted directory entries if enough;
2. Hint the deleted and unused directory entries which at the
   end of the cluster chain no matter whether enough or not(Add
   by this commit);
3. If no any empty directory entries, hint the empty directory
   entries in the new cluster(Add by this commit).

This avoids repeated traversal of directory entries, reduces CPU
usage, and improves the performance of creating files and
directories(especially on low-performance CPUs).

Test create 5000 files in a class 4 SD card on imx6q-sabrelite
with:

for ((i=0;i<5;i++)); do
   sync
   time (for ((j=1;j<=1000;j++)); do touch file$((i*1000+j)); done)
done

The more files, the more performance improvements.

            Before   After    Improvement
   1~1000   25.360s  22.168s  14.40%
1001~2000   38.242s  28.72ss  33.15%
2001~3000   49.134s  35.037s  40.23%
3001~4000   62.042s  41.624s  49.05%
4001~5000   73.629s  46.772s  57.42%

Signed-off-by: Yuezhang Mo <Yuezhang.Mo@sony.com>
Reviewed-by: Andy Wu <Andy.Wu@sony.com>
Reviewed-by: Aoyama Wataru <wataru.aoyama@sony.com>
---
 fs/exfat/dir.c   | 26 ++++++++++++++++++++++----
 fs/exfat/namei.c | 33 +++++++++++++++++++++------------
 2 files changed, 43 insertions(+), 16 deletions(-)

diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
index 9f9b8435baca..5497a610808d 100644
--- a/fs/exfat/dir.c
+++ b/fs/exfat/dir.c
@@ -905,17 +905,24 @@ static inline void exfat_reset_empty_hint(struct exfat_hint_femp *hint_femp)
 
 static inline void exfat_set_empty_hint(struct exfat_inode_info *ei,
 		struct exfat_hint_femp *candi_empty, struct exfat_chain *clu,
-		int dentry, int num_entries)
+		int dentry, int num_entries, int entry_type)
 {
 	if (ei->hint_femp.eidx == EXFAT_HINT_NONE ||
 	    ei->hint_femp.eidx > dentry) {
+		int total_entries = EXFAT_B_TO_DEN(i_size_read(&ei->vfs_inode));
+
 		if (candi_empty->count == 0) {
 			candi_empty->cur = *clu;
 			candi_empty->eidx = dentry;
 		}
 
-		candi_empty->count++;
-		if (candi_empty->count == num_entries)
+		if (entry_type == TYPE_UNUSED)
+			candi_empty->count += total_entries - dentry;
+		else
+			candi_empty->count++;
+
+		if (candi_empty->count == num_entries ||
+		    candi_empty->count + candi_empty->eidx == total_entries)
 			ei->hint_femp = *candi_empty;
 	}
 }
@@ -989,7 +996,8 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 				step = DIRENT_STEP_FILE;
 
 				exfat_set_empty_hint(ei, &candi_empty, &clu,
-						dentry, num_entries);
+						dentry, num_entries,
+						entry_type);
 
 				brelse(bh);
 				if (entry_type == TYPE_UNUSED)
@@ -1100,6 +1108,16 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
 		goto rewind;
 	}
 
+	/*
+	 * set the EXFAT_EOF_CLUSTER flag to avoid search
+	 * from the beginning again when allocated a new cluster
+	 */
+	if (ei->hint_femp.eidx == EXFAT_HINT_NONE) {
+		ei->hint_femp.cur.dir = EXFAT_EOF_CLUSTER;
+		ei->hint_femp.eidx = p_dir->size * dentries_per_clu;
+		ei->hint_femp.count = 0;
+	}
+
 	/* initialized hint_stat */
 	hint_stat->clu = p_dir->dir;
 	hint_stat->eidx = 0;
diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
index b617bebc3d0f..add4893711d3 100644
--- a/fs/exfat/namei.c
+++ b/fs/exfat/namei.c
@@ -224,11 +224,18 @@ static int exfat_search_empty_slot(struct super_block *sb,
 
 	if (hint_femp->eidx != EXFAT_HINT_NONE) {
 		dentry = hint_femp->eidx;
-		if (num_entries <= hint_femp->count) {
-			hint_femp->eidx = EXFAT_HINT_NONE;
-			return dentry;
-		}
 
+		/*
+		 * If hint_femp->count is enough, it is needed to check if
+		 * there are actual empty entries.
+		 * Otherwise, and if "dentry + hint_famp->count" is also equal
+		 * to "p_dir->size * dentries_per_clu", it means ENOSPC.
+		 */
+		if (dentry + hint_femp->count == p_dir->size * dentries_per_clu
+		    && num_entries > hint_femp->count)
+			return -ENOSPC;
+
+		hint_femp->eidx = EXFAT_HINT_NONE;
 		exfat_chain_dup(&clu, &hint_femp->cur);
 	} else {
 		exfat_chain_dup(&clu, p_dir);
@@ -293,6 +300,12 @@ static int exfat_search_empty_slot(struct super_block *sb,
 		}
 	}
 
+	hint_femp->eidx = p_dir->size * dentries_per_clu - num_empty;
+	hint_femp->count = num_empty;
+	if (num_empty == 0)
+		exfat_chain_set(&hint_femp->cur, EXFAT_EOF_CLUSTER, 0,
+				clu.flags);
+
 	return -ENOSPC;
 }
 
@@ -369,15 +382,11 @@ static int exfat_find_empty_entry(struct inode *inode,
 			if (exfat_ent_set(sb, last_clu, clu.dir))
 				return -EIO;
 
-		if (hint_femp.eidx == EXFAT_HINT_NONE) {
-			/* the special case that new dentry
-			 * should be allocated from the start of new cluster
-			 */
-			hint_femp.eidx = EXFAT_B_TO_DEN_IDX(p_dir->size, sbi);
-			hint_femp.count = sbi->dentries_per_clu;
-
+		if (hint_femp.cur.dir == EXFAT_EOF_CLUSTER)
 			exfat_chain_set(&hint_femp.cur, clu.dir, 0, clu.flags);
-		}
+
+		hint_femp.count += sbi->dentries_per_clu;
+
 		hint_femp.cur.size++;
 		p_dir->size++;
 		size = EXFAT_CLU_TO_B(p_dir->size, sbi);
-- 
2.25.1

^ permalink raw reply related	[flat|nested] 3+ messages in thread

* RE: [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain
  2022-11-02  7:11 ` [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain Yuezhang.Mo
@ 2022-11-03 12:51   ` Sungjong Seo
  2022-11-08  8:00   ` Namjae Jeon
  1 sibling, 0 replies; 3+ messages in thread
From: Sungjong Seo @ 2022-11-03 12:51 UTC (permalink / raw)
  To: 'Namjae Jeon'
  Cc: 'linux-kernel', 'linux-fsdevel', sj1557.seo

> After traversing all directory entries, hint the empty directory
> entry no matter whether or not there are enough empty directory
> entries.
> 
> After this commit, hint the empty directory entries like this:
> 
> 1. Hint the deleted directory entries if enough;
> 2. Hint the deleted and unused directory entries which at the
>    end of the cluster chain no matter whether enough or not(Add
>    by this commit);
> 3. If no any empty directory entries, hint the empty directory
>    entries in the new cluster(Add by this commit).
> 
> This avoids repeated traversal of directory entries, reduces CPU
> usage, and improves the performance of creating files and
> directories(especially on low-performance CPUs).
> 
> Test create 5000 files in a class 4 SD card on imx6q-sabrelite
> with:
> 
> for ((i=0;i<5;i++)); do
>    sync
>    time (for ((j=1;j<=1000;j++)); do touch file$((i*1000+j)); done)
> done
> 
> The more files, the more performance improvements.
> 
>             Before   After    Improvement
>    1~1000   25.360s  22.168s  14.40%
> 1001~2000   38.242s  28.72ss  33.15%
> 2001~3000   49.134s  35.037s  40.23%
> 3001~4000   62.042s  41.624s  49.05%
> 4001~5000   73.629s  46.772s  57.42%
> 
> Signed-off-by: Yuezhang Mo <Yuezhang.Mo@sony.com>
> Reviewed-by: Andy Wu <Andy.Wu@sony.com>
> Reviewed-by: Aoyama Wataru <wataru.aoyama@sony.com>

Reviewed-by: Sungjong Seo <sj1557.seo@samsung.com>

Looks good. Thanks!

> ---
>  fs/exfat/dir.c   | 26 ++++++++++++++++++++++----
>  fs/exfat/namei.c | 33 +++++++++++++++++++++------------
>  2 files changed, 43 insertions(+), 16 deletions(-)
> 
> diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
> index 9f9b8435baca..5497a610808d 100644
> --- a/fs/exfat/dir.c
> +++ b/fs/exfat/dir.c
> @@ -905,17 +905,24 @@ static inline void exfat_reset_empty_hint(struct
> exfat_hint_femp *hint_femp)
> 
>  static inline void exfat_set_empty_hint(struct exfat_inode_info *ei,
>  		struct exfat_hint_femp *candi_empty, struct exfat_chain *clu,
> -		int dentry, int num_entries)
> +		int dentry, int num_entries, int entry_type)
>  {
>  	if (ei->hint_femp.eidx == EXFAT_HINT_NONE ||
>  	    ei->hint_femp.eidx > dentry) {
> +		int total_entries = EXFAT_B_TO_DEN(i_size_read(&ei-
> >vfs_inode));
> +
>  		if (candi_empty->count == 0) {
>  			candi_empty->cur = *clu;
>  			candi_empty->eidx = dentry;
>  		}
> 
> -		candi_empty->count++;
> -		if (candi_empty->count == num_entries)
> +		if (entry_type == TYPE_UNUSED)
> +			candi_empty->count += total_entries - dentry;
> +		else
> +			candi_empty->count++;
> +
> +		if (candi_empty->count == num_entries ||
> +		    candi_empty->count + candi_empty->eidx == total_entries)
>  			ei->hint_femp = *candi_empty;
>  	}
>  }
> @@ -989,7 +996,8 @@ int exfat_find_dir_entry(struct super_block *sb,
> struct exfat_inode_info *ei,
>  				step = DIRENT_STEP_FILE;
> 
>  				exfat_set_empty_hint(ei, &candi_empty, &clu,
> -						dentry, num_entries);
> +						dentry, num_entries,
> +						entry_type);
> 
>  				brelse(bh);
>  				if (entry_type == TYPE_UNUSED)
> @@ -1100,6 +1108,16 @@ int exfat_find_dir_entry(struct super_block *sb,
> struct exfat_inode_info *ei,
>  		goto rewind;
>  	}
> 
> +	/*
> +	 * set the EXFAT_EOF_CLUSTER flag to avoid search
> +	 * from the beginning again when allocated a new cluster
> +	 */
> +	if (ei->hint_femp.eidx == EXFAT_HINT_NONE) {
> +		ei->hint_femp.cur.dir = EXFAT_EOF_CLUSTER;
> +		ei->hint_femp.eidx = p_dir->size * dentries_per_clu;
> +		ei->hint_femp.count = 0;
> +	}
> +
>  	/* initialized hint_stat */
>  	hint_stat->clu = p_dir->dir;
>  	hint_stat->eidx = 0;
> diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
> index b617bebc3d0f..add4893711d3 100644
> --- a/fs/exfat/namei.c
> +++ b/fs/exfat/namei.c
> @@ -224,11 +224,18 @@ static int exfat_search_empty_slot(struct
> super_block *sb,
> 
>  	if (hint_femp->eidx != EXFAT_HINT_NONE) {
>  		dentry = hint_femp->eidx;
> -		if (num_entries <= hint_femp->count) {
> -			hint_femp->eidx = EXFAT_HINT_NONE;
> -			return dentry;
> -		}
> 
> +		/*
> +		 * If hint_femp->count is enough, it is needed to check if
> +		 * there are actual empty entries.
> +		 * Otherwise, and if "dentry + hint_famp->count" is also
> equal
> +		 * to "p_dir->size * dentries_per_clu", it means ENOSPC.
> +		 */
> +		if (dentry + hint_femp->count == p_dir->size *
> dentries_per_clu
> +		    && num_entries > hint_femp->count)
> +			return -ENOSPC;
> +
> +		hint_femp->eidx = EXFAT_HINT_NONE;
>  		exfat_chain_dup(&clu, &hint_femp->cur);
>  	} else {
>  		exfat_chain_dup(&clu, p_dir);
> @@ -293,6 +300,12 @@ static int exfat_search_empty_slot(struct super_block
> *sb,
>  		}
>  	}
> 
> +	hint_femp->eidx = p_dir->size * dentries_per_clu - num_empty;
> +	hint_femp->count = num_empty;
> +	if (num_empty == 0)
> +		exfat_chain_set(&hint_femp->cur, EXFAT_EOF_CLUSTER, 0,
> +				clu.flags);
> +
>  	return -ENOSPC;
>  }
> 
> @@ -369,15 +382,11 @@ static int exfat_find_empty_entry(struct inode
> *inode,
>  			if (exfat_ent_set(sb, last_clu, clu.dir))
>  				return -EIO;
> 
> -		if (hint_femp.eidx == EXFAT_HINT_NONE) {
> -			/* the special case that new dentry
> -			 * should be allocated from the start of new cluster
> -			 */
> -			hint_femp.eidx = EXFAT_B_TO_DEN_IDX(p_dir->size, sbi);
> -			hint_femp.count = sbi->dentries_per_clu;
> -
> +		if (hint_femp.cur.dir == EXFAT_EOF_CLUSTER)
>  			exfat_chain_set(&hint_femp.cur, clu.dir, 0, clu.flags);
> -		}
> +
> +		hint_femp.count += sbi->dentries_per_clu;
> +
>  		hint_femp.cur.size++;
>  		p_dir->size++;
>  		size = EXFAT_CLU_TO_B(p_dir->size, sbi);
> --
> 2.25.1


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain
  2022-11-02  7:11 ` [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain Yuezhang.Mo
  2022-11-03 12:51   ` Sungjong Seo
@ 2022-11-08  8:00   ` Namjae Jeon
  1 sibling, 0 replies; 3+ messages in thread
From: Namjae Jeon @ 2022-11-08  8:00 UTC (permalink / raw)
  To: Yuezhang.Mo
  Cc: Sungjong Seo, linux-kernel, linux-fsdevel, Andy.Wu, Wataru.Aoyama

2022-11-02 16:11 GMT+09:00, Yuezhang.Mo@sony.com <Yuezhang.Mo@sony.com>:
> After traversing all directory entries, hint the empty directory
> entry no matter whether or not there are enough empty directory
> entries.
>
> After this commit, hint the empty directory entries like this:
>
> 1. Hint the deleted directory entries if enough;
> 2. Hint the deleted and unused directory entries which at the
>    end of the cluster chain no matter whether enough or not(Add
>    by this commit);
> 3. If no any empty directory entries, hint the empty directory
>    entries in the new cluster(Add by this commit).
>
> This avoids repeated traversal of directory entries, reduces CPU
> usage, and improves the performance of creating files and
> directories(especially on low-performance CPUs).
>
> Test create 5000 files in a class 4 SD card on imx6q-sabrelite
> with:
>
> for ((i=0;i<5;i++)); do
>    sync
>    time (for ((j=1;j<=1000;j++)); do touch file$((i*1000+j)); done)
> done
>
> The more files, the more performance improvements.
>
>             Before   After    Improvement
>    1~1000   25.360s  22.168s  14.40%
> 1001~2000   38.242s  28.72ss  33.15%
> 2001~3000   49.134s  35.037s  40.23%
> 3001~4000   62.042s  41.624s  49.05%
> 4001~5000   73.629s  46.772s  57.42%
>
> Signed-off-by: Yuezhang Mo <Yuezhang.Mo@sony.com>
> Reviewed-by: Andy Wu <Andy.Wu@sony.com>
> Reviewed-by: Aoyama Wataru <wataru.aoyama@sony.com>
Applied. Thanks for your patch!

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2022-11-08  8:00 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <CGME20221102071138epcas1p198e20ca74ae4df32b6f754a382b9c2ba@epcas1p1.samsung.com>
2022-11-02  7:11 ` [PATCH v2 2/2] exfat: hint the empty entry which at the end of cluster chain Yuezhang.Mo
2022-11-03 12:51   ` Sungjong Seo
2022-11-08  8:00   ` Namjae Jeon

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).