linux-kernel - [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-Id: <20210315043316.54508-1-hyeongseok@gmail.com>
Date:   Mon, 15 Mar 2021 13:33:16 +0900
From:   Hyeongseok Kim <hyeongseok@...il.com>
To:     namjae.jeon@...sung.com, sj1557.seo@...sung.com
Cc:     linux-kernel@...r.kernel.org, linux-fsdevel@...r.kernel.org,
        Hyeongseok Kim <hyeongseok@...il.com>
Subject: [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain

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