* [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain @ 2021-03-15 4:33 ` Hyeongseok Kim 2021-03-17 16:07 ` Sungjong Seo 0 siblings, 1 reply; 3+ messages in thread From: Hyeongseok Kim @ 2021-03-15 4:33 UTC (permalink / raw) To: namjae.jeon, sj1557.seo; +Cc: linux-kernel, linux-fsdevel, 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 ^ permalink raw reply related [flat|nested] 3+ messages in thread
* RE: [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain 2021-03-15 4:33 ` [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain Hyeongseok Kim @ 2021-03-17 16:07 ` Sungjong Seo 2021-03-18 1:02 ` Hyeongseok Kim 0 siblings, 1 reply; 3+ messages in thread From: Sungjong Seo @ 2021-03-17 16:07 UTC (permalink / raw) To: 'Hyeongseok Kim', namjae.jeon Cc: linux-kernel, linux-fsdevel, sj1557.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 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain 2021-03-17 16:07 ` Sungjong Seo @ 2021-03-18 1:02 ` Hyeongseok Kim 0 siblings, 0 replies; 3+ messages in thread From: Hyeongseok Kim @ 2021-03-18 1:02 UTC (permalink / raw) To: Sungjong Seo, namjae.jeon; +Cc: linux-kernel, linux-fsdevel 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. ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2021-03-18 1:03 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <CGME20210315043335epcas1p2bf257806e9ba1c2a492739a6424a2b44@epcas1p2.samsung.com> 2021-03-15 4:33 ` [PATCH] exfat: speed up iterate/lookup by fixing start point of traversing fat chain Hyeongseok Kim 2021-03-17 16:07 ` Sungjong Seo 2021-03-18 1:02 ` Hyeongseok Kim
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).