* [PATCH v3 1/3] exfat: add a Bloom filter for negative name lookups
2026-09-02 15:24 [PATCH v3 0/3] exfat: speed up file creation in large directories Yang Wen
@ 2026-09-02 15:24 ` Yang Wen
2026-10-19 0:27 ` NeilBrown
2026-09-02 15:24 ` [PATCH v3 2/3] exfat: retain the next empty directory entry hint Yang Wen
` (2 subsequent siblings)
3 siblings, 1 reply; 7+ messages in thread
From: Yang Wen @ 2026-09-02 15:24 UTC (permalink / raw)
To: linkinjeon, sj1557.seo, chizhiling
Cc: yuezhang.mo, exfat, linux-kernel, Yang Wen
Negative name lookups scan a directory from the beginning. Repeating this
scan before creating each file makes bulk creation approach O(N^2).
Add a 64 KiB per-directory Bloom filter. Build it lazily after a directory
reaches 1024 on-disk entries. A definite miss skips the directory scan,
while a possible match follows the normal lookup path so hash collisions
cannot affect correctness.
Signed-off-by: Yang Wen <anmuxixixi@gmail.com>
---
fs/exfat/dir.c | 140 ++++++++++++++++++++++++++++++++++++++++++++
fs/exfat/exfat_fs.h | 13 ++++
fs/exfat/inode.c | 1 +
fs/exfat/namei.c | 6 +-
fs/exfat/super.c | 1 +
5 files changed, 158 insertions(+), 3 deletions(-)
diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
index fe73b1380c5d..5145f09bcee6 100644
--- a/fs/exfat/dir.c
+++ b/fs/exfat/dir.c
@@ -8,6 +8,8 @@
#include <linux/bio.h>
#include <linux/buffer_head.h>
#include <linux/filelock.h>
+#include <linux/hash.h>
+#include <linux/stringhash.h>
#include "exfat_raw.h"
#include "exfat_fs.h"
@@ -65,6 +67,140 @@ static int exfat_get_uniname_from_ext_entry(struct super_block *sb,
return 0;
}
+static u32 exfat_name_filter_hash(struct super_block *sb,
+ const struct exfat_uni_name *name)
+{
+ unsigned long hash = init_name_hash(NULL);
+ int i;
+
+ for (i = 0; i < name->name_len; i++)
+ hash = partial_name_hash(exfat_toupper(sb, name->name[i]), hash);
+
+ return end_name_hash(hash);
+}
+
+static void exfat_name_filter_indexes(struct super_block *sb,
+ const struct exfat_uni_name *name,
+ unsigned int indexes[3])
+{
+ u32 hash = exfat_name_filter_hash(sb, name);
+
+ indexes[0] = hash_32(hash, EXFAT_NAME_FILTER_ORDER);
+ indexes[1] = hash_32(hash ^ 0x9e3779b9U, EXFAT_NAME_FILTER_ORDER);
+ indexes[2] = hash_32(rol32(hash, 16) ^ 0x85ebca6bU,
+ EXFAT_NAME_FILTER_ORDER);
+}
+
+void exfat_name_filter_free(struct inode *inode)
+{
+ struct exfat_inode_info *ei = EXFAT_I(inode);
+
+ kvfree(ei->name_filter);
+ ei->name_filter = NULL;
+}
+
+bool exfat_name_filter_maybe_contains(struct inode *inode,
+ const struct exfat_uni_name *name)
+{
+ struct exfat_inode_info *ei = EXFAT_I(inode);
+ unsigned int indexes[3];
+
+ if (!ei->name_filter)
+ return true;
+
+ exfat_name_filter_indexes(inode->i_sb, name, indexes);
+ return test_bit(indexes[0], ei->name_filter) &&
+ test_bit(indexes[1], ei->name_filter) &&
+ test_bit(indexes[2], ei->name_filter);
+}
+
+void exfat_name_filter_add(struct inode *inode,
+ const struct exfat_uni_name *name)
+{
+ struct exfat_inode_info *ei = EXFAT_I(inode);
+ unsigned int indexes[3];
+
+ if (!ei->name_filter)
+ return;
+
+ exfat_name_filter_indexes(inode->i_sb, name, indexes);
+ __set_bit(indexes[0], ei->name_filter);
+ __set_bit(indexes[1], ei->name_filter);
+ __set_bit(indexes[2], ei->name_filter);
+}
+
+/*
+ * Build a complete filter only after a directory becomes large enough for
+ * repeated negative linear lookups to matter. A filter hit is never trusted:
+ * it only allows definite misses to skip the on-disk scan.
+ */
+static void exfat_build_name_filter(struct super_block *sb,
+ struct exfat_inode_info *ei,
+ struct exfat_chain *p_dir)
+{
+ unsigned long *filter;
+ struct exfat_chain clu;
+ unsigned int clu_count = 0;
+ struct inode *inode = &ei->vfs_inode;
+ struct exfat_sb_info *sbi = EXFAT_SB(sb);
+ int i;
+
+ if (ei->name_filter ||
+ exfat_bytes_to_dentries(i_size_read(inode)) <
+ EXFAT_NAME_FILTER_MIN_DENTRIES)
+ return;
+
+ filter = kvzalloc(EXFAT_NAME_FILTER_BYTES, GFP_NOFS);
+ if (!filter)
+ return;
+
+ exfat_chain_dup(&clu, p_dir);
+ while (clu.dir != EXFAT_EOF_CLUSTER) {
+ for (i = 0; i < sbi->dentries_per_clu; i++) {
+ struct exfat_uni_name name = { };
+ struct exfat_dentry *ep;
+ struct buffer_head *bh;
+ unsigned int type;
+ unsigned int indexes[3];
+ int len;
+
+ ep = exfat_get_dentry(sb, &clu, i, &bh);
+ if (!ep)
+ goto abort;
+
+ type = exfat_get_entry_type(ep);
+ brelse(bh);
+ if (type == TYPE_UNUSED)
+ goto complete;
+ if (type != TYPE_FILE && type != TYPE_DIR)
+ continue;
+
+ if (exfat_get_uniname_from_ext_entry(sb, &clu, i, name.name))
+ goto abort;
+ for (len = 0; len <= MAX_NAME_LENGTH && name.name[len]; len++)
+ ;
+ if (!len || len > MAX_NAME_LENGTH)
+ goto abort;
+ name.name_len = len;
+ exfat_name_filter_indexes(sb, &name, indexes);
+ __set_bit(indexes[0], filter);
+ __set_bit(indexes[1], filter);
+ __set_bit(indexes[2], filter);
+ }
+
+ if (exfat_chain_advance(sb, &clu, 1))
+ goto abort;
+ if (unlikely(++clu_count > EXFAT_DATA_CLUSTER_COUNT(sbi)))
+ goto abort;
+ }
+
+complete:
+ ei->name_filter = filter;
+ return;
+abort:
+ kvfree(filter);
+}
+
/* read a directory entry from the opened directory */
static int exfat_readdir(struct inode *inode, loff_t *cpos, struct exfat_dir_entry *dir_entry)
{
@@ -992,6 +1128,8 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
if (num_entries < 0)
return num_entries;
+ if (!exfat_name_filter_maybe_contains(&ei->vfs_inode, p_uniname))
+ return -ENOENT;
dentries_per_clu = sbi->dentries_per_clu;
@@ -1153,6 +1291,8 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
ei->hint_femp.count = 0;
}
+ exfat_build_name_filter(sb, ei, p_dir);
+
/* initialized hint_stat */
hint_stat->clu = p_dir->dir;
hint_stat->eidx = 0;
diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h
index a9131fe03302..5187dee47cf1 100644
--- a/fs/exfat/exfat_fs.h
+++ b/fs/exfat/exfat_fs.h
@@ -120,6 +120,11 @@ enum {
#define DIR_CACHE_SIZE \
(DIV_ROUND_UP(ES_MAX_ENTRY_NUM << DENTRY_SIZE_BITS, SECTOR_SIZE) + 1)
+#define EXFAT_NAME_FILTER_ORDER 19
+#define EXFAT_NAME_FILTER_BITS BIT(EXFAT_NAME_FILTER_ORDER)
+#define EXFAT_NAME_FILTER_BYTES (EXFAT_NAME_FILTER_BITS >> 3)
+#define EXFAT_NAME_FILTER_MIN_DENTRIES 1024
+
/* Superblock flags */
#define EXFAT_FLAGS_SHUTDOWN 1
@@ -284,6 +289,8 @@ struct exfat_inode_info {
struct exfat_hint hint_stat;
/* hint for first empty entry */
struct exfat_hint_femp hint_femp;
+ /* Complete, in-memory Bloom filter of directory names */
+ unsigned long *name_filter;
spinlock_t cache_lru_lock;
struct list_head cache_lru;
@@ -619,6 +626,12 @@ int exfat_read_volume_label(struct super_block *sb,
int exfat_write_volume_label(struct super_block *sb,
struct exfat_uni_name *label);
+bool exfat_name_filter_maybe_contains(struct inode *inode,
+ const struct exfat_uni_name *name);
+void exfat_name_filter_add(struct inode *inode,
+ const struct exfat_uni_name *name);
+void exfat_name_filter_free(struct inode *inode);
+
static inline int exfat_chain_advance(struct super_block *sb,
struct exfat_chain *chain, unsigned int step)
{
diff --git a/fs/exfat/inode.c b/fs/exfat/inode.c
index ccd13630187e..0d0c6f817775 100644
--- a/fs/exfat/inode.c
+++ b/fs/exfat/inode.c
@@ -445,6 +445,7 @@ struct inode *exfat_build_inode(struct super_block *sb,
void exfat_evict_inode(struct inode *inode)
{
truncate_inode_pages_final(&inode->i_data);
+ exfat_name_filter_free(inode);
if (!inode->i_nlink) {
i_size_write(inode, 0);
diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
index a4dc83b5949c..96f33226f2c0 100644
--- a/fs/exfat/namei.c
+++ b/fs/exfat/namei.c
@@ -526,6 +526,7 @@ static int exfat_add_entry(struct inode *inode, const char *path,
}
info->entry = dentry;
+ exfat_name_filter_add(inode, &uniname);
info->flags = ALLOC_NO_FAT_CHAIN;
info->type = type;
@@ -802,7 +803,6 @@ static int exfat_unlink(struct inode *dir, struct dentry *dentry)
/* update the directory entry */
exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
-
err = exfat_put_dentry_set(&es, IS_DIRSYNC(inode));
if (err)
goto unlock;
@@ -957,7 +957,6 @@ static int exfat_rmdir(struct inode *dir, struct dentry *dentry)
exfat_set_volume_dirty(sb);
exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
-
err = exfat_put_dentry_set(&es, IS_DIRSYNC(dir));
if (err)
goto unlock;
@@ -1215,6 +1214,8 @@ static int __exfat_rename(struct inode *old_parent_inode,
ret = exfat_rename_file(new_parent_inode, &uni_name, ei);
else
ret = exfat_move_file(new_parent_inode, &uni_name, ei);
+ if (!ret)
+ exfat_name_filter_add(new_parent_inode, &uni_name);
if (!ret && new_inode) {
struct exfat_entry_set_cache es;
@@ -1227,7 +1228,6 @@ static int __exfat_rename(struct inode *old_parent_inode,
}
exfat_remove_entries(new_inode, &es, ES_IDX_FILE, true);
-
ret = exfat_put_dentry_set(&es, IS_DIRSYNC(new_inode));
if (ret)
goto del_out;
diff --git a/fs/exfat/super.c b/fs/exfat/super.c
index a9ea36ba2693..f73cf2d02365 100644
--- a/fs/exfat/super.c
+++ b/fs/exfat/super.c
@@ -195,6 +195,7 @@ static struct inode *exfat_alloc_inode(struct super_block *sb)
if (!ei)
return NULL;
+ ei->name_filter = NULL;
return &ei->vfs_inode;
}
--
2.34.1
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 1/3] exfat: add a Bloom filter for negative name lookups
2026-09-02 15:24 ` [PATCH v3 1/3] exfat: add a Bloom filter for negative name lookups Yang Wen
@ 2026-10-19 0:27 ` NeilBrown
0 siblings, 0 replies; 7+ messages in thread
From: NeilBrown @ 2026-10-19 0:27 UTC (permalink / raw)
To: Yang Wen
Cc: linkinjeon, sj1557.seo, chizhiling, yuezhang.mo, exfat,
linux-kernel, Yang Wen
On Thu, 03 Sep 2026, Yang Wen wrote:
> Negative name lookups scan a directory from the beginning. Repeating this
> scan before creating each file makes bulk creation approach O(N^2).
>
> Add a 64 KiB per-directory Bloom filter. Build it lazily after a directory
> reaches 1024 on-disk entries. A definite miss skips the directory scan,
> while a possible match follows the normal lookup path so hash collisions
> cannot affect correctness.
>
> Signed-off-by: Yang Wen <anmuxixixi@gmail.com>
> ---
> fs/exfat/dir.c | 140 ++++++++++++++++++++++++++++++++++++++++++++
> fs/exfat/exfat_fs.h | 13 ++++
> fs/exfat/inode.c | 1 +
> fs/exfat/namei.c | 6 +-
> fs/exfat/super.c | 1 +
> 5 files changed, 158 insertions(+), 3 deletions(-)
>
> diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
> index fe73b1380c5d..5145f09bcee6 100644
> --- a/fs/exfat/dir.c
> +++ b/fs/exfat/dir.c
> @@ -8,6 +8,8 @@
> #include <linux/bio.h>
> #include <linux/buffer_head.h>
> #include <linux/filelock.h>
> +#include <linux/hash.h>
> +#include <linux/stringhash.h>
>
> #include "exfat_raw.h"
> #include "exfat_fs.h"
> @@ -65,6 +67,140 @@ static int exfat_get_uniname_from_ext_entry(struct super_block *sb,
> return 0;
> }
>
> +static u32 exfat_name_filter_hash(struct super_block *sb,
> + const struct exfat_uni_name *name)
> +{
> + unsigned long hash = init_name_hash(NULL);
> + int i;
> +
> + for (i = 0; i < name->name_len; i++)
> + hash = partial_name_hash(exfat_toupper(sb, name->name[i]), hash);
You want 3*19 or 57 bits of hash. I wonder if this is the best way to
get that from an upper-case file-name. On a 32bit host you are already
limiting yourself to 32 bits, even with long names.
I'd probably try to make each of the three hashes from different
characters in the name. So one from bytes 0,3,6,... One from 1,4,7,...
and one from 2,5,8,...
I suspect that getting 57 useful bits from an upper-case file name is
unrealistic and you could reduce EXFAT_NAME_FILTER_ORDER without losing
effectiveness of the filter. Have you done any analysis to see how much
range you are actually getting from these hash calculations?
> +
> + return end_name_hash(hash);
> +}
> +
> +static void exfat_name_filter_indexes(struct super_block *sb,
> + const struct exfat_uni_name *name,
> + unsigned int indexes[3])
> +{
> + u32 hash = exfat_name_filter_hash(sb, name);
> +
> + indexes[0] = hash_32(hash, EXFAT_NAME_FILTER_ORDER);
> + indexes[1] = hash_32(hash ^ 0x9e3779b9U, EXFAT_NAME_FILTER_ORDER);
> + indexes[2] = hash_32(rol32(hash, 16) ^ 0x85ebca6bU,
> + EXFAT_NAME_FILTER_ORDER);
I'd like to see some explanation for these magic numbers.
The idea seems sound, but I think the hash algorithm should be justified
better.
Thanks,
NeilBrown
> +}
> +
> +void exfat_name_filter_free(struct inode *inode)
> +{
> + struct exfat_inode_info *ei = EXFAT_I(inode);
> +
> + kvfree(ei->name_filter);
> + ei->name_filter = NULL;
> +}
> +
> +bool exfat_name_filter_maybe_contains(struct inode *inode,
> + const struct exfat_uni_name *name)
> +{
> + struct exfat_inode_info *ei = EXFAT_I(inode);
> + unsigned int indexes[3];
> +
> + if (!ei->name_filter)
> + return true;
> +
> + exfat_name_filter_indexes(inode->i_sb, name, indexes);
> + return test_bit(indexes[0], ei->name_filter) &&
> + test_bit(indexes[1], ei->name_filter) &&
> + test_bit(indexes[2], ei->name_filter);
> +}
> +
> +void exfat_name_filter_add(struct inode *inode,
> + const struct exfat_uni_name *name)
> +{
> + struct exfat_inode_info *ei = EXFAT_I(inode);
> + unsigned int indexes[3];
> +
> + if (!ei->name_filter)
> + return;
> +
> + exfat_name_filter_indexes(inode->i_sb, name, indexes);
> + __set_bit(indexes[0], ei->name_filter);
> + __set_bit(indexes[1], ei->name_filter);
> + __set_bit(indexes[2], ei->name_filter);
> +}
> +
> +/*
> + * Build a complete filter only after a directory becomes large enough for
> + * repeated negative linear lookups to matter. A filter hit is never trusted:
> + * it only allows definite misses to skip the on-disk scan.
> + */
> +static void exfat_build_name_filter(struct super_block *sb,
> + struct exfat_inode_info *ei,
> + struct exfat_chain *p_dir)
> +{
> + unsigned long *filter;
> + struct exfat_chain clu;
> + unsigned int clu_count = 0;
> + struct inode *inode = &ei->vfs_inode;
> + struct exfat_sb_info *sbi = EXFAT_SB(sb);
> + int i;
> +
> + if (ei->name_filter ||
> + exfat_bytes_to_dentries(i_size_read(inode)) <
> + EXFAT_NAME_FILTER_MIN_DENTRIES)
> + return;
> +
> + filter = kvzalloc(EXFAT_NAME_FILTER_BYTES, GFP_NOFS);
> + if (!filter)
> + return;
> +
> + exfat_chain_dup(&clu, p_dir);
> + while (clu.dir != EXFAT_EOF_CLUSTER) {
> + for (i = 0; i < sbi->dentries_per_clu; i++) {
> + struct exfat_uni_name name = { };
> + struct exfat_dentry *ep;
> + struct buffer_head *bh;
> + unsigned int type;
> + unsigned int indexes[3];
> + int len;
> +
> + ep = exfat_get_dentry(sb, &clu, i, &bh);
> + if (!ep)
> + goto abort;
> +
> + type = exfat_get_entry_type(ep);
> + brelse(bh);
> + if (type == TYPE_UNUSED)
> + goto complete;
> + if (type != TYPE_FILE && type != TYPE_DIR)
> + continue;
> +
> + if (exfat_get_uniname_from_ext_entry(sb, &clu, i, name.name))
> + goto abort;
> + for (len = 0; len <= MAX_NAME_LENGTH && name.name[len]; len++)
> + ;
> + if (!len || len > MAX_NAME_LENGTH)
> + goto abort;
> + name.name_len = len;
> + exfat_name_filter_indexes(sb, &name, indexes);
> + __set_bit(indexes[0], filter);
> + __set_bit(indexes[1], filter);
> + __set_bit(indexes[2], filter);
> + }
> +
> + if (exfat_chain_advance(sb, &clu, 1))
> + goto abort;
> + if (unlikely(++clu_count > EXFAT_DATA_CLUSTER_COUNT(sbi)))
> + goto abort;
> + }
> +
> +complete:
> + ei->name_filter = filter;
> + return;
> +abort:
> + kvfree(filter);
> +}
> +
> /* read a directory entry from the opened directory */
> static int exfat_readdir(struct inode *inode, loff_t *cpos, struct exfat_dir_entry *dir_entry)
> {
> @@ -992,6 +1128,8 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
>
> if (num_entries < 0)
> return num_entries;
> + if (!exfat_name_filter_maybe_contains(&ei->vfs_inode, p_uniname))
> + return -ENOENT;
>
> dentries_per_clu = sbi->dentries_per_clu;
>
> @@ -1153,6 +1291,8 @@ int exfat_find_dir_entry(struct super_block *sb, struct exfat_inode_info *ei,
> ei->hint_femp.count = 0;
> }
>
> + exfat_build_name_filter(sb, ei, p_dir);
> +
> /* initialized hint_stat */
> hint_stat->clu = p_dir->dir;
> hint_stat->eidx = 0;
> diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h
> index a9131fe03302..5187dee47cf1 100644
> --- a/fs/exfat/exfat_fs.h
> +++ b/fs/exfat/exfat_fs.h
> @@ -120,6 +120,11 @@ enum {
> #define DIR_CACHE_SIZE \
> (DIV_ROUND_UP(ES_MAX_ENTRY_NUM << DENTRY_SIZE_BITS, SECTOR_SIZE) + 1)
>
> +#define EXFAT_NAME_FILTER_ORDER 19
> +#define EXFAT_NAME_FILTER_BITS BIT(EXFAT_NAME_FILTER_ORDER)
> +#define EXFAT_NAME_FILTER_BYTES (EXFAT_NAME_FILTER_BITS >> 3)
> +#define EXFAT_NAME_FILTER_MIN_DENTRIES 1024
> +
> /* Superblock flags */
> #define EXFAT_FLAGS_SHUTDOWN 1
>
> @@ -284,6 +289,8 @@ struct exfat_inode_info {
> struct exfat_hint hint_stat;
> /* hint for first empty entry */
> struct exfat_hint_femp hint_femp;
> + /* Complete, in-memory Bloom filter of directory names */
> + unsigned long *name_filter;
>
> spinlock_t cache_lru_lock;
> struct list_head cache_lru;
> @@ -619,6 +626,12 @@ int exfat_read_volume_label(struct super_block *sb,
> int exfat_write_volume_label(struct super_block *sb,
> struct exfat_uni_name *label);
>
> +bool exfat_name_filter_maybe_contains(struct inode *inode,
> + const struct exfat_uni_name *name);
> +void exfat_name_filter_add(struct inode *inode,
> + const struct exfat_uni_name *name);
> +void exfat_name_filter_free(struct inode *inode);
> +
> static inline int exfat_chain_advance(struct super_block *sb,
> struct exfat_chain *chain, unsigned int step)
> {
> diff --git a/fs/exfat/inode.c b/fs/exfat/inode.c
> index ccd13630187e..0d0c6f817775 100644
> --- a/fs/exfat/inode.c
> +++ b/fs/exfat/inode.c
> @@ -445,6 +445,7 @@ struct inode *exfat_build_inode(struct super_block *sb,
> void exfat_evict_inode(struct inode *inode)
> {
> truncate_inode_pages_final(&inode->i_data);
> + exfat_name_filter_free(inode);
>
> if (!inode->i_nlink) {
> i_size_write(inode, 0);
> diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
> index a4dc83b5949c..96f33226f2c0 100644
> --- a/fs/exfat/namei.c
> +++ b/fs/exfat/namei.c
> @@ -526,6 +526,7 @@ static int exfat_add_entry(struct inode *inode, const char *path,
> }
>
> info->entry = dentry;
> + exfat_name_filter_add(inode, &uniname);
> info->flags = ALLOC_NO_FAT_CHAIN;
> info->type = type;
>
> @@ -802,7 +803,6 @@ static int exfat_unlink(struct inode *dir, struct dentry *dentry)
>
> /* update the directory entry */
> exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
> -
> err = exfat_put_dentry_set(&es, IS_DIRSYNC(inode));
> if (err)
> goto unlock;
> @@ -957,7 +957,6 @@ static int exfat_rmdir(struct inode *dir, struct dentry *dentry)
> exfat_set_volume_dirty(sb);
>
> exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
> -
> err = exfat_put_dentry_set(&es, IS_DIRSYNC(dir));
> if (err)
> goto unlock;
> @@ -1215,6 +1214,8 @@ static int __exfat_rename(struct inode *old_parent_inode,
> ret = exfat_rename_file(new_parent_inode, &uni_name, ei);
> else
> ret = exfat_move_file(new_parent_inode, &uni_name, ei);
> + if (!ret)
> + exfat_name_filter_add(new_parent_inode, &uni_name);
>
> if (!ret && new_inode) {
> struct exfat_entry_set_cache es;
> @@ -1227,7 +1228,6 @@ static int __exfat_rename(struct inode *old_parent_inode,
> }
>
> exfat_remove_entries(new_inode, &es, ES_IDX_FILE, true);
> -
> ret = exfat_put_dentry_set(&es, IS_DIRSYNC(new_inode));
> if (ret)
> goto del_out;
> diff --git a/fs/exfat/super.c b/fs/exfat/super.c
> index a9ea36ba2693..f73cf2d02365 100644
> --- a/fs/exfat/super.c
> +++ b/fs/exfat/super.c
> @@ -195,6 +195,7 @@ static struct inode *exfat_alloc_inode(struct super_block *sb)
> if (!ei)
> return NULL;
>
> + ei->name_filter = NULL;
> return &ei->vfs_inode;
> }
>
> --
> 2.34.1
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3 2/3] exfat: retain the next empty directory entry hint
2026-09-02 15:24 [PATCH v3 0/3] exfat: speed up file creation in large directories Yang Wen
2026-09-02 15:24 ` [PATCH v3 1/3] exfat: add a Bloom filter for negative name lookups Yang Wen
@ 2026-09-02 15:24 ` Yang Wen
2026-09-11 0:02 ` Namjae Jeon
2026-09-02 15:24 ` [PATCH v3 3/3] exfat: reclaim name filters under memory pressure Yang Wen
2026-09-03 8:41 ` [PATCH v3 0/3] exfat: speed up file creation in large directories Chi Zhiling
3 siblings, 1 reply; 7+ messages in thread
From: Yang Wen @ 2026-09-02 15:24 UTC (permalink / raw)
To: linkinjeon, sj1557.seo, chizhiling
Cc: yuezhang.mo, exfat, linux-kernel, Yang Wen
After a Bloom filter miss skips the name scan, finding an empty entry can
still rescan the directory from the beginning.
Advance the empty-entry hint past each newly allocated entry set and retain
it while the name filter is active. Invalidate the hint whenever create
rollback, unlink, rmdir, rename, or move can free entries, so the next
allocation rediscovers earlier holes.
This preserves the fast append path during bulk creation without allowing
stale hints to cause unbounded directory growth.
Signed-off-by: Yang Wen <anmuxixixi@gmail.com>
---
fs/exfat/namei.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 57 insertions(+), 1 deletion(-)
diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c
index 96f33226f2c0..56772167ba5d 100644
--- a/fs/exfat/namei.c
+++ b/fs/exfat/namei.c
@@ -199,6 +199,50 @@ const struct dentry_operations exfat_utf8_dentry_ops = {
.d_compare = exfat_utf8_d_cmp,
};
+static void exfat_set_next_empty_hint(struct inode *inode,
+ struct exfat_chain *p_dir, int dentry,
+ int num_entries,
+ struct exfat_entry_set_cache *es)
+{
+ struct exfat_inode_info *ei = EXFAT_I(inode);
+ struct exfat_sb_info *sbi = EXFAT_SB(inode->i_sb);
+ unsigned int next = dentry + num_entries;
+ unsigned int total = exfat_cluster_to_dentries(sbi, p_dir->size);
+ struct exfat_chain cur;
+
+ if (next >= total) {
+ exfat_chain_set(&ei->hint_femp.cur, EXFAT_EOF_CLUSTER, 0,
+ p_dir->flags);
+ ei->hint_femp.eidx = total;
+ ei->hint_femp.count = 0;
+ return;
+ }
+
+ cur.dir = exfat_sector_to_cluster(sbi,
+ es->bh[es->num_bh - 1]->b_blocknr);
+ cur.flags = p_dir->flags;
+ cur.size = p_dir->size - exfat_dentries_to_cluster(sbi, next);
+ if (!(next & (sbi->dentries_per_clu - 1))) {
+ cur.size++;
+ if (exfat_chain_advance(inode->i_sb, &cur, 1)) {
+ ei->hint_femp.eidx = EXFAT_HINT_NONE;
+ return;
+ }
+ }
+
+ ei->hint_femp.cur = cur;
+ ei->hint_femp.eidx = next;
+ ei->hint_femp.count = 0;
+}
+
+static void exfat_invalidate_empty_hint(struct inode *inode)
+{
+ struct exfat_inode_info *ei = EXFAT_I(inode);
+
+ ei->hint_femp.eidx = EXFAT_HINT_NONE;
+ ei->hint_femp.count = 0;
+}
+
/* search EMPTY CONTINUOUS "num_entries" entries */
static int exfat_search_empty_slot(struct super_block *sb,
struct exfat_hint_femp *hint_femp, struct exfat_chain *p_dir,
@@ -385,6 +429,8 @@ int exfat_find_empty_entry(struct inode *inode,
inode->i_blocks += sbi->cluster_size >> 9;
}
+ exfat_set_next_empty_hint(inode, p_dir, dentry, num_entries, es);
+
p_dir->dir = exfat_sector_to_cluster(sbi, es->bh[0]->b_blocknr);
p_dir->size -= dentry / sbi->dentries_per_clu;
@@ -516,6 +562,7 @@ static int exfat_add_entry(struct inode *inode, const char *path,
dentry, ES_ALL_ENTRIES);
if (!cleanup_ret) {
exfat_remove_entries(inode, &es, ES_IDX_FILE, false);
+ exfat_invalidate_empty_hint(inode);
cleanup_ret = exfat_put_dentry_set(&es,
IS_DIRSYNC(inode));
}
@@ -628,7 +675,8 @@ static int exfat_find(struct inode *dir, const struct qstr *qname,
ei->hint_stat.clu = cdir.dir;
ei->hint_stat.eidx = 0;
ei->version = (inode_peek_iversion_raw(dir) & 0xffffffff);
- ei->hint_femp.eidx = EXFAT_HINT_NONE;
+ if (!ei->name_filter)
+ ei->hint_femp.eidx = EXFAT_HINT_NONE;
}
/* search the file name for directories */
@@ -803,6 +851,8 @@ static int exfat_unlink(struct inode *dir, struct dentry *dentry)
/* update the directory entry */
exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
+ exfat_invalidate_empty_hint(dir);
+
err = exfat_put_dentry_set(&es, IS_DIRSYNC(inode));
if (err)
goto unlock;
@@ -957,6 +1007,8 @@ static int exfat_rmdir(struct inode *dir, struct dentry *dentry)
exfat_set_volume_dirty(sb);
exfat_remove_entries(inode, &es, ES_IDX_FILE, true);
+ exfat_invalidate_empty_hint(dir);
+
err = exfat_put_dentry_set(&es, IS_DIRSYNC(dir));
if (err)
goto unlock;
@@ -1138,6 +1190,7 @@ static int exfat_move_file(struct inode *parent_inode,
ES_ALL_ENTRIES)) {
exfat_remove_entries(parent_inode, &new_es,
ES_IDX_FILE, false);
+ exfat_invalidate_empty_hint(parent_inode);
exfat_put_dentry_set(&new_es, false);
}
goto put_mov_es;
@@ -1214,6 +1267,7 @@ static int __exfat_rename(struct inode *old_parent_inode,
ret = exfat_rename_file(new_parent_inode, &uni_name, ei);
else
ret = exfat_move_file(new_parent_inode, &uni_name, ei);
+ exfat_invalidate_empty_hint(old_parent_inode);
if (!ret)
exfat_name_filter_add(new_parent_inode, &uni_name);
@@ -1228,6 +1282,8 @@ static int __exfat_rename(struct inode *old_parent_inode,
}
exfat_remove_entries(new_inode, &es, ES_IDX_FILE, true);
+ exfat_invalidate_empty_hint(new_parent_inode);
+
ret = exfat_put_dentry_set(&es, IS_DIRSYNC(new_inode));
if (ret)
goto del_out;
--
2.34.1
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 2/3] exfat: retain the next empty directory entry hint
2026-09-02 15:24 ` [PATCH v3 2/3] exfat: retain the next empty directory entry hint Yang Wen
@ 2026-09-11 0:02 ` Namjae Jeon
0 siblings, 0 replies; 7+ messages in thread
From: Namjae Jeon @ 2026-09-11 0:02 UTC (permalink / raw)
To: Yang Wen; +Cc: sj1557.seo, chizhiling, yuezhang.mo, exfat, linux-kernel
> @@ -385,6 +429,8 @@ int exfat_find_empty_entry(struct inode *inode,
> inode->i_blocks += sbi->cluster_size >> 9;
> }
>
> + exfat_set_next_empty_hint(inode, p_dir, dentry, num_entries, es);
This advances hint_femp before the entry set is committed. If a later
step such as exfat_alloc_new_dir() or exfat_put_dentry_set() fails,
the slot is still empty but the hint points past it. The same applies
to the volume-label and rollback paths. Please invalidate the hint on
every post-allocation failure, or update it only after the entry is
committed.
> +
> p_dir->dir = exfat_sector_to_cluster(sbi, es->bh[0]->b_blocknr);
> p_dir->size -= dentry / sbi->dentries_per_clu;
>
> @@ -1214,6 +1267,7 @@ static int __exfat_rename(struct inode *old_parent_inode,
> ret = exfat_rename_file(new_parent_inode, &uni_name, ei);
> else
> ret = exfat_move_file(new_parent_inode, &uni_name, ei);
> + exfat_invalidate_empty_hint(old_parent_inode);
> if (!ret)
> exfat_name_filter_add(new_parent_inode, &uni_name);
If the new entry is written successfully but deleting the old entry
fails, exfat_rename_file() or exfat_move_file() returns an error and
this filter update is skipped. The new name may still exist on disk,
so a Bloom-filter miss can incorrectly return -ENOENT. Please
invalidate the destination filter on rename/move errors.
Thanks.
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3 3/3] exfat: reclaim name filters under memory pressure
2026-09-02 15:24 [PATCH v3 0/3] exfat: speed up file creation in large directories Yang Wen
2026-09-02 15:24 ` [PATCH v3 1/3] exfat: add a Bloom filter for negative name lookups Yang Wen
2026-09-02 15:24 ` [PATCH v3 2/3] exfat: retain the next empty directory entry hint Yang Wen
@ 2026-09-02 15:24 ` Yang Wen
2026-09-03 8:41 ` [PATCH v3 0/3] exfat: speed up file creation in large directories Chi Zhiling
3 siblings, 0 replies; 7+ messages in thread
From: Yang Wen @ 2026-09-02 15:24 UTC (permalink / raw)
To: linkinjeon, sj1557.seo, chizhiling
Cc: yuezhang.mo, exfat, linux-kernel, Yang Wen
Each active large directory can hold a 64 KiB name filter. Add a
per-superblock LRU and shrinker so filters can be reclaimed when memory is
tight.
Signed-off-by: Yang Wen <anmuxixixi@gmail.com>
---
fs/exfat/dir.c | 145 +++++++++++++++++++++++++++++++++++++++++++-
fs/exfat/exfat_fs.h | 10 +++
fs/exfat/super.c | 8 +++
3 files changed, 160 insertions(+), 3 deletions(-)
diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c
index 5145f09bcee6..c7aa50d41e9f 100644
--- a/fs/exfat/dir.c
+++ b/fs/exfat/dir.c
@@ -9,6 +9,7 @@
#include <linux/buffer_head.h>
#include <linux/filelock.h>
#include <linux/hash.h>
+#include <linux/shrinker.h>
#include <linux/stringhash.h>
#include "exfat_raw.h"
@@ -91,12 +92,144 @@ static void exfat_name_filter_indexes(struct super_block *sb,
EXFAT_NAME_FILTER_ORDER);
}
+static unsigned long *
+exfat_name_filter_detach_locked(struct exfat_sb_info *sbi,
+ struct exfat_inode_info *ei)
+{
+ unsigned long *filter = ei->name_filter;
+
+ if (!filter)
+ return NULL;
+
+ ei->name_filter = NULL;
+ list_del_init(&ei->name_filter_lru);
+ sbi->name_filter_count--;
+ return filter;
+}
+
+static void exfat_name_filter_touch(struct exfat_inode_info *ei)
+{
+ struct exfat_sb_info *sbi = EXFAT_SB(ei->vfs_inode.i_sb);
+
+ spin_lock(&sbi->name_filter_lock);
+ if (ei->name_filter)
+ list_move_tail(&ei->name_filter_lru, &sbi->name_filter_lru);
+ spin_unlock(&sbi->name_filter_lock);
+}
+
void exfat_name_filter_free(struct inode *inode)
{
struct exfat_inode_info *ei = EXFAT_I(inode);
+ struct exfat_sb_info *sbi;
+ unsigned long *filter;
- kvfree(ei->name_filter);
- ei->name_filter = NULL;
+ if (!READ_ONCE(ei->name_filter))
+ return;
+
+ sbi = EXFAT_SB(inode->i_sb);
+ spin_lock(&sbi->name_filter_lock);
+ filter = exfat_name_filter_detach_locked(sbi, ei);
+ spin_unlock(&sbi->name_filter_lock);
+ kvfree(filter);
+}
+
+static unsigned long
+exfat_name_filter_count_objects(struct shrinker *shrinker,
+ struct shrink_control *sc)
+{
+ struct exfat_sb_info *sbi = shrinker->private_data;
+ unsigned long count;
+
+ spin_lock(&sbi->name_filter_lock);
+ count = sbi->name_filter_count;
+ spin_unlock(&sbi->name_filter_lock);
+
+ return count ? count : SHRINK_EMPTY;
+}
+
+static unsigned long
+exfat_name_filter_scan_objects(struct shrinker *shrinker,
+ struct shrink_control *sc)
+{
+ struct exfat_sb_info *sbi = shrinker->private_data;
+ unsigned long freed = 0;
+
+ /* Avoid reclaim recursion from a GFP_NOFS allocation under s_lock. */
+ if (!mutex_trylock(&sbi->s_lock)) {
+ sc->nr_scanned = 0;
+ return SHRINK_STOP;
+ }
+
+ while (freed < sc->nr_to_scan) {
+ struct exfat_inode_info *ei;
+ unsigned long *filter;
+
+ spin_lock(&sbi->name_filter_lock);
+ if (list_empty(&sbi->name_filter_lru)) {
+ spin_unlock(&sbi->name_filter_lock);
+ break;
+ }
+
+ ei = list_first_entry(&sbi->name_filter_lru,
+ struct exfat_inode_info,
+ name_filter_lru);
+ filter = exfat_name_filter_detach_locked(sbi, ei);
+ spin_unlock(&sbi->name_filter_lock);
+
+ kvfree(filter);
+ freed++;
+ cond_resched();
+ }
+
+ mutex_unlock(&sbi->s_lock);
+ sc->nr_scanned = freed;
+ return freed;
+}
+
+void exfat_name_filter_shrinker_register(struct super_block *sb)
+{
+ struct exfat_sb_info *sbi = EXFAT_SB(sb);
+ struct shrinker *shrinker;
+
+ shrinker = shrinker_alloc(SHRINKER_NONSLAB,
+ "exfat-name-filter:%s", sb->s_id);
+ if (!shrinker) {
+ exfat_warn(sb, "failed to allocate name filter shrinker");
+ return;
+ }
+
+ shrinker->count_objects = exfat_name_filter_count_objects;
+ shrinker->scan_objects = exfat_name_filter_scan_objects;
+ shrinker->private_data = sbi;
+ shrinker_register(shrinker);
+ sbi->name_filter_shrinker = shrinker;
+}
+
+void exfat_name_filter_shrinker_unregister(struct super_block *sb)
+{
+ struct exfat_sb_info *sbi = EXFAT_SB(sb);
+ struct shrinker *shrinker = sbi->name_filter_shrinker;
+
+ sbi->name_filter_shrinker = NULL;
+ shrinker_free(shrinker);
+
+ for (;;) {
+ struct exfat_inode_info *ei;
+ unsigned long *filter;
+
+ spin_lock(&sbi->name_filter_lock);
+ if (list_empty(&sbi->name_filter_lru)) {
+ spin_unlock(&sbi->name_filter_lock);
+ break;
+ }
+
+ ei = list_first_entry(&sbi->name_filter_lru,
+ struct exfat_inode_info,
+ name_filter_lru);
+ filter = exfat_name_filter_detach_locked(sbi, ei);
+ spin_unlock(&sbi->name_filter_lock);
+ kvfree(filter);
+ }
}
bool exfat_name_filter_maybe_contains(struct inode *inode,
@@ -108,6 +241,7 @@ bool exfat_name_filter_maybe_contains(struct inode *inode,
if (!ei->name_filter)
return true;
+ exfat_name_filter_touch(ei);
exfat_name_filter_indexes(inode->i_sb, name, indexes);
return test_bit(indexes[0], ei->name_filter) &&
test_bit(indexes[1], ei->name_filter) &&
@@ -123,6 +257,7 @@ void exfat_name_filter_add(struct inode *inode,
if (!ei->name_filter)
return;
+ exfat_name_filter_touch(ei);
exfat_name_filter_indexes(inode->i_sb, name, indexes);
__set_bit(indexes[0], ei->name_filter);
__set_bit(indexes[1], ei->name_filter);
@@ -145,7 +280,7 @@ static void exfat_build_name_filter(struct super_block *sb,
struct exfat_sb_info *sbi = EXFAT_SB(sb);
int i;
- if (ei->name_filter ||
+ if (!sbi->name_filter_shrinker || ei->name_filter ||
exfat_bytes_to_dentries(i_size_read(inode)) <
EXFAT_NAME_FILTER_MIN_DENTRIES)
return;
@@ -195,7 +330,11 @@ static void exfat_build_name_filter(struct super_block *sb,
}
complete:
+ spin_lock(&sbi->name_filter_lock);
ei->name_filter = filter;
+ list_add_tail(&ei->name_filter_lru, &sbi->name_filter_lru);
+ sbi->name_filter_count++;
+ spin_unlock(&sbi->name_filter_lock);
return;
abort:
kvfree(filter);
diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h
index 5187dee47cf1..b81cfbdd117f 100644
--- a/fs/exfat/exfat_fs.h
+++ b/fs/exfat/exfat_fs.h
@@ -14,6 +14,8 @@
#include <uapi/linux/exfat.h>
#include <linux/buffer_head.h>
+struct shrinker;
+
#define EXFAT_ROOT_INO 1
/*
@@ -260,6 +262,11 @@ struct exfat_sb_info {
spinlock_t inode_hash_lock;
struct hlist_head inode_hashtable[EXFAT_HASH_SIZE];
+ /* Protects name_filter_lru and name_filter_count. */
+ spinlock_t name_filter_lock;
+ struct list_head name_filter_lru;
+ unsigned long name_filter_count;
+ struct shrinker *name_filter_shrinker;
struct rcu_head rcu;
};
@@ -291,6 +298,7 @@ struct exfat_inode_info {
struct exfat_hint_femp hint_femp;
/* Complete, in-memory Bloom filter of directory names */
unsigned long *name_filter;
+ struct list_head name_filter_lru;
spinlock_t cache_lru_lock;
struct list_head cache_lru;
@@ -631,6 +639,8 @@ bool exfat_name_filter_maybe_contains(struct inode *inode,
void exfat_name_filter_add(struct inode *inode,
const struct exfat_uni_name *name);
void exfat_name_filter_free(struct inode *inode);
+void exfat_name_filter_shrinker_register(struct super_block *sb);
+void exfat_name_filter_shrinker_unregister(struct super_block *sb);
static inline int exfat_chain_advance(struct super_block *sb,
struct exfat_chain *chain, unsigned int step)
diff --git a/fs/exfat/super.c b/fs/exfat/super.c
index f73cf2d02365..3f9d880ec363 100644
--- a/fs/exfat/super.c
+++ b/fs/exfat/super.c
@@ -45,6 +45,7 @@ static void exfat_put_super(struct super_block *sb)
{
struct exfat_sb_info *sbi = EXFAT_SB(sb);
+ exfat_name_filter_shrinker_unregister(sb);
mutex_lock(&sbi->s_lock);
exfat_clear_volume_dirty(sb);
exfat_free_bitmap(sbi);
@@ -196,6 +197,7 @@ static struct inode *exfat_alloc_inode(struct super_block *sb)
return NULL;
ei->name_filter = NULL;
+ INIT_LIST_HEAD(&ei->name_filter_lru);
return &ei->vfs_inode;
}
@@ -732,6 +734,8 @@ static int exfat_fill_super(struct super_block *sb, struct fs_context *fc)
goto free_table;
}
+ exfat_name_filter_shrinker_register(sb);
+
return 0;
put_inode:
@@ -827,6 +831,10 @@ static int exfat_init_fs_context(struct fs_context *fc)
mutex_init(&sbi->s_lock);
mutex_init(&sbi->bitmap_lock);
+ spin_lock_init(&sbi->name_filter_lock);
+ INIT_LIST_HEAD(&sbi->name_filter_lru);
+ sbi->name_filter_count = 0;
+ sbi->name_filter_shrinker = NULL;
ratelimit_state_init(&sbi->ratelimit, DEFAULT_RATELIMIT_INTERVAL,
DEFAULT_RATELIMIT_BURST);
--
2.34.1
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 0/3] exfat: speed up file creation in large directories
2026-09-02 15:24 [PATCH v3 0/3] exfat: speed up file creation in large directories Yang Wen
` (2 preceding siblings ...)
2026-09-02 15:24 ` [PATCH v3 3/3] exfat: reclaim name filters under memory pressure Yang Wen
@ 2026-09-03 8:41 ` Chi Zhiling
3 siblings, 0 replies; 7+ messages in thread
From: Chi Zhiling @ 2026-09-03 8:41 UTC (permalink / raw)
To: Yang Wen, linkinjeon, sj1557.seo, yuezhang.mo; +Cc: exfat, linux-kernel
On 9/2/26 11:24 PM, Yang Wen wrote:
> Negative name lookups and empty-entry allocation can repeatedly scan a
> directory from the beginning. Bulk creation in a large directory therefore
> approaches O(N^2).
>
> This series separates the optimization into three independently reviewable
> steps. Patch 1 adds the Bloom filter used to reject definite name misses.
> Patch 2 retains and correctly invalidates the next-empty-entry hint. Patch 3
> adds the LRU and shrinker used to reclaim filters under memory pressure.
>
> Test environment:
> QEMU TCG multi-thread, 4 vCPUs, 6 GiB RAM
> 4 GiB exFAT image, 32 KiB clusters
>
> Creating 20,000 empty files improved from 589.48 seconds to 5.33 seconds,
> which is a 110.6-fold speedup.
>
> Changes in v3:
> - Split the change into Bloom filter, empty-entry hint, and shrinker patches.
> - Accept filenames containing exactly 255 UTF-16 code units while building
> the Bloom filter.
> - Invalidate the empty-entry hint in every path that can free directory
> entries, preventing stale hints from skipping earlier holes.
>
> Changes in v2:
> - Move exfat_name_filter_free() to exfat_evict_inode() because
> ->free_inode() may run from an RCU callback in softirq context.
>
> Yang Wen (3):
> exfat: add a Bloom filter for negative name lookups
> exfat: retain the next empty directory entry hint
> exfat: reclaim name filters under memory pressure
>
> fs/exfat/dir.c | 279 ++++++++++++++++++++++++++++++++++++++++++++
> fs/exfat/exfat_fs.h | 23 ++++
> fs/exfat/inode.c | 1 +
> fs/exfat/namei.c | 58 ++++++++-
> fs/exfat/super.c | 9 ++
> 5 files changed, 369 insertions(+), 1 deletion(-)
>
This is a much better version than v2.
Reviewed-by: Chi Zhiling <chizhiling@kylinos.cn>
Thanks!
^ permalink raw reply [flat|nested] 7+ messages in thread