From nobody Thu Sep 24 22:13:36 2026 Received: from mail-pz2-f12.google.com (mail-pz2-f12.google.com [74.125.228.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id F1EED31717D for ; Sat, 19 Sep 2026 15:23:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.228.12 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831395; cv=none; b=p9JDzLETa+r7PxyTH7ulfpb92QdTupc0UQV8B9+71Tno7Ba2q+yGbXrpDpsFSgcFUc+5lYUGCjmGr6lwdRO+rqyNwfiZpr0KBgwqhwxYMQpRUq13QYAQXUXmLAZmre6VKHwe5WU88BvX9qJZ8qpx/2vt+6HejHHSaqVLbP1C42M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831395; c=relaxed/simple; bh=8zOL1ivn0naVv7rpLJoEerjKMFZucVAS/gXLqx9iQ0U=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=rL5egS+IRYHNPoHbhdAOJ2krnbPFTQg9LVsz07XxoHC/M1164QdjUikV0/SAe4FPob476HLQx/tevkSK19oiky2X4NGoNmnDsJCUEzbxuISBNPRK0lcbzjzjT5fZ26eNRsw2SI83lYsmsnTNCjQ+T1N/6VaJ7kvrCFCMRtYm/CU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=DGHnS8QP; arc=none smtp.client-ip=74.125.228.12 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="DGHnS8QP" Received: by mail-pz2-f12.google.com with SMTP id 41be03b00d2f7-cc4d04d740cso1047604a12.0 for ; Sat, 19 Sep 2026 08:23:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789831393; x=1790436193; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=Dx9AmecdiKVbXJ0PRpBsUyLHlsphQQwaZylDzQUAJNE=; b=DGHnS8QPiB/GDyN86427CYH6Icq0CmlvCjU9CHoIj71dyyBNA09CSwG9wWQUundPMP Ij+7ToXHlvdV5mAOAhXKKU/3xrIjkaNrc69H24kVoywPzDceIIz5qsr/9/vFUvahKelT TDRABVyvnacuuaHH4k1agHTMbUMda+2MXdN/p1lZndxF2u1CO8i71qzFGKIm5C/gifst 5cCBepW4d8pWI7QCmPFculo6SKWkh966U+cf/dl8wWqXKZRUpFXPL/TEhgT4s3FH0mx4 kBwaDHY6LaXL5danVDincesbREFEbbEUfd48Y8qtfNQMZHr1QtXILU/uVdygDPu6AeF1 gbGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789831393; x=1790436193; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=Dx9AmecdiKVbXJ0PRpBsUyLHlsphQQwaZylDzQUAJNE=; b=wiUIhISjej2dAFq4K74GnWAd/wqZbDh/rX57OLW8h8TXdfrK1EzvZLgf8MeVpgJvXH vA3HXcxDghbDju9xaRwAuVGDx18GfpnMi63J3EIgoZ6VH6+/NkC5DAzUFbm9O7SCH/KY UC9Zt971T9UbeevhtlQHZgO1gsVQtNzV4eA5PgnPj3Cazi+UvDXOlxwSJXMPvQNU5Zxb QEWbH+gUnau3sqZRv5DKDkqDWJ/CdJN+dC2mDM5myxLKZNih69VuJ88HuUKy/bUbrW+t eTU8EbawXRwiN6CJ+mLvH8P/sN6/scoi+9GMXtO2xVjwz83PcA+foLyOl20FqopRFUHX McEw== X-Forwarded-Encrypted: i=1; AKwUvBwAJYdqGzj5Qbr+WulLaMnwaJwVJZ2EaGdg47+gK0z8SGUZw8d3YrbpVjQr6GRiW6TUqLQvAIs23KqE+Ko=@vger.kernel.org X-Gm-Message-State: AFuF++l7F07W0KNQuB+HwEloLIHcLnB//L4cgO5ctTQs/Vx0/zHHOy64 t7nDr1OhFt/7B/8W1Kz2jqsbmNU6WJL8fO3mgUxEk9+EWiV1YtisQbPp X-Gm-Gg: AYBFou3AU4TO0vBgzEnaIUcuv1yS1tmX2c5+YFFrkDsfC9GR+S2czXpPgUzXbkRrwPM TiCg2sGLMT/mnhtUHZor6dOMBwGd4TRnJ3bAEORgYRmCEm0jJvVFnkEGnAm7mnnKgRQ657+VRp+ Hmzd3fyfyU6gB+Mz6yPz/taG43FWyYDlYCLDAKV1/cwIHIZFqexMGHG32BokMcSQjqisUrCBQP0 DyGunS8fBgXPQx1PrGsGpr6qWSgkX9A3qRzKwjbb+cKSCyphM/9rhW/xR/E5nphiJYKQWG+tKjS GFhMeCLegDRu0rNUJ3Ls2uSAZ5wrdf3YE4aAWTjn3HCS/2SSvLZ70GYh73gJMYIYjVs6EQoV1/+ lIqMbWsWtm0jSlGBEVygC4Wz/PBhCKzVr9Tupprbk0IYXSUM4kAjrznQa8vzKJYhV8A5CQ0iE2G vAELByLfQ8QUhaLEuunPSi1VMjrBmoYyxsRkEK/0OyBm6CJyGMzqSMA8I9fUtyWSLFxDiYj9d6w j54SAQzCzwY X-Received: by 2002:a17:90a:2cc4:b0:39e:58e4:dc2f with SMTP id 98e67ed59e1d1-39e58e4de87mr6121820a91.5.1789831393166; Sat, 19 Sep 2026 08:23:13 -0700 (PDT) Received: from localhost.localdomain ([47.100.192.162]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-3a0309d5760sm326230a91.4.2026.09.19.08.23.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 08:23:12 -0700 (PDT) From: Yang Wen To: linkinjeon@kernel.org, sj1557.seo@samsung.com, chizhiling@163.com Cc: yuezhang.mo@sony.com, exfat@lists.linux.dev, linux-kernel@vger.kernel.org, Yang Wen Subject: [PATCH v5 1/3] exfat: add a Bloom filter for negative name lookups Date: Sat, 19 Sep 2026 23:22:38 +0800 Message-Id: <20260919152240.1507914-2-anmuxixixi@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260919152240.1507914-1-anmuxixixi@gmail.com> References: <20260919152240.1507914-1-anmuxixixi@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 --- 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 46514b13bebd..0c5648e23e20 100644 --- a/fs/exfat/dir.c +++ b/fs/exfat/dir.c @@ -8,6 +8,8 @@ #include #include #include +#include +#include =20 #include "exfat_raw.h" #include "exfat_fs.h" @@ -65,6 +67,140 @@ static int exfat_get_uniname_from_ext_entry(struct supe= r_block *sb, return 0; } =20 +static u32 exfat_name_filter_hash(struct super_block *sb, + const struct exfat_uni_name *name) +{ + unsigned long hash =3D init_name_hash(NULL); + int i; + + for (i =3D 0; i < name->name_len; i++) + hash =3D 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 =3D exfat_name_filter_hash(sb, name); + + indexes[0] =3D hash_32(hash, EXFAT_NAME_FILTER_ORDER); + indexes[1] =3D hash_32(hash ^ 0x9e3779b9U, EXFAT_NAME_FILTER_ORDER); + indexes[2] =3D hash_32(rol32(hash, 16) ^ 0x85ebca6bU, + EXFAT_NAME_FILTER_ORDER); +} + +void exfat_name_filter_free(struct inode *inode) +{ + struct exfat_inode_info *ei =3D EXFAT_I(inode); + + kvfree(ei->name_filter); + ei->name_filter =3D NULL; +} + +bool exfat_name_filter_maybe_contains(struct inode *inode, + const struct exfat_uni_name *name) +{ + struct exfat_inode_info *ei =3D 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 =3D 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 trust= ed: + * 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 =3D 0; + struct inode *inode =3D &ei->vfs_inode; + struct exfat_sb_info *sbi =3D EXFAT_SB(sb); + int i; + + if (ei->name_filter || + exfat_bytes_to_dentries(i_size_read(inode)) < + EXFAT_NAME_FILTER_MIN_DENTRIES) + return; + + filter =3D kvzalloc(EXFAT_NAME_FILTER_BYTES, GFP_NOFS); + if (!filter) + return; + + exfat_chain_dup(&clu, p_dir); + while (clu.dir !=3D EXFAT_EOF_CLUSTER) { + for (i =3D 0; i < sbi->dentries_per_clu; i++) { + struct exfat_uni_name name =3D { }; + struct exfat_dentry *ep; + struct buffer_head *bh; + unsigned int type; + unsigned int indexes[3]; + int len; + + ep =3D exfat_get_dentry(sb, &clu, i, &bh); + if (!ep) + goto abort; + + type =3D exfat_get_entry_type(ep); + brelse(bh); + if (type =3D=3D TYPE_UNUSED) + goto complete; + if (type !=3D TYPE_FILE && type !=3D TYPE_DIR) + continue; + + if (exfat_get_uniname_from_ext_entry(sb, &clu, i, name.name)) + goto abort; + for (len =3D 0; len <=3D MAX_NAME_LENGTH && name.name[len]; len++) + ; + if (!len || len > MAX_NAME_LENGTH) + goto abort; + name.name_len =3D 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 =3D 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_d= ir_entry *dir_entry) { @@ -1035,6 +1171,8 @@ int exfat_find_dir_entry(struct super_block *sb, stru= ct exfat_inode_info *ei, =20 if (num_entries < 0) return num_entries; + if (!exfat_name_filter_maybe_contains(&ei->vfs_inode, p_uniname)) + return -ENOENT; =20 dentries_per_clu =3D sbi->dentries_per_clu; =20 @@ -1196,6 +1334,8 @@ int exfat_find_dir_entry(struct super_block *sb, stru= ct exfat_inode_info *ei, ei->hint_femp.count =3D 0; } =20 + exfat_build_name_filter(sb, ei, p_dir); + /* initialized hint_stat */ hint_stat->clu =3D p_dir->dir; hint_stat->eidx =3D 0; diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h index 41a2c7dfc479..899b276f105b 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) =20 +#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 =20 @@ -285,6 +290,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; =20 spinlock_t cache_lru_lock; struct list_head cache_lru; @@ -620,6 +627,12 @@ int exfat_read_volume_label(struct super_block *sb, int exfat_write_volume_label(struct super_block *sb, struct exfat_uni_name *label); =20 +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); =20 if (!inode->i_nlink) { i_size_write(inode, 0); diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c index 3c5746fc57d9..83ded3b52a8c 100644 --- a/fs/exfat/namei.c +++ b/fs/exfat/namei.c @@ -526,6 +526,7 @@ static int exfat_add_entry(struct inode *inode, const c= har *path, } =20 info->entry =3D dentry; + exfat_name_filter_add(inode, &uniname); info->flags =3D ALLOC_NO_FAT_CHAIN; info->type =3D type; =20 @@ -803,7 +804,6 @@ static int exfat_unlink(struct inode *dir, struct dentr= y *dentry) =20 /* update the directory entry */ exfat_remove_entries(inode, &es, ES_IDX_FILE, true); - err =3D exfat_put_dentry_set(&es, IS_DIRSYNC(inode)); if (err) goto unlock; @@ -958,7 +958,6 @@ static int exfat_rmdir(struct inode *dir, struct dentry= *dentry) exfat_set_volume_dirty(sb); =20 exfat_remove_entries(inode, &es, ES_IDX_FILE, true); - err =3D exfat_put_dentry_set(&es, IS_DIRSYNC(dir)); if (err) goto unlock; @@ -1216,6 +1215,8 @@ static int __exfat_rename(struct inode *old_parent_in= ode, ret =3D exfat_rename_file(new_parent_inode, &uni_name, ei); else ret =3D exfat_move_file(new_parent_inode, &uni_name, ei); + if (!ret) + exfat_name_filter_add(new_parent_inode, &uni_name); =20 if (!ret && new_inode) { struct exfat_entry_set_cache es; @@ -1228,7 +1229,6 @@ static int __exfat_rename(struct inode *old_parent_in= ode, } =20 exfat_remove_entries(new_inode, &es, ES_IDX_FILE, true); - ret =3D 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 4943cef97741..4924f0fad836 100644 --- a/fs/exfat/super.c +++ b/fs/exfat/super.c @@ -209,6 +209,7 @@ static struct inode *exfat_alloc_inode(struct super_blo= ck *sb) if (!ei) return NULL; =20 + ei->name_filter =3D NULL; return &ei->vfs_inode; } =20 --=20 2.34.1 From nobody Thu Sep 24 22:13:36 2026 Received: from mail-pj2-f43.google.com (mail-pj2-f43.google.com [74.125.227.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 31B9A2EEE76 for ; Sat, 19 Sep 2026 15:23:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.227.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831401; cv=none; b=fyQ95LD7Zp2tbhm29gM1jYRCfsj64y32E1TS9BVrOBteqGa2S5/Ar82s4R0S0RO7Zx8R0fZ7u55L7yOboXcV2N2u1X5hGLSUPXQWzDt87JYKBcmbhq36Kr95VULT/lMOneJq5Gkke85pF/zQ9EBiDNB7xGgHqnpO09iZ1mTRR7Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831401; c=relaxed/simple; bh=cIewCEDVPIV/7wNBrK2e4PdFrYXVEVX9ES+kWxB+nKU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=eehFkwWR7NdRLrNYwN5cldrjn19kmLTE0fY4SwX4KgNOP37GHLqAib/Ephk9YUiQCfIs+uJQMjjMSrxLcTgMfGT+MubjAtbYXePCHaWxYCNYo38mPPls/IO0r3mXKqRQkJvDWaMS73skpgwi+eiw71M8zBEEAV8yt7lfWrd+q3I= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=mayhLTFX; arc=none smtp.client-ip=74.125.227.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="mayhLTFX" Received: by mail-pj2-f43.google.com with SMTP id d9443c01a7336-2d90ba1d807so20806695ad.3 for ; Sat, 19 Sep 2026 08:23:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789831399; x=1790436199; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=du4V1DlmNl3hSpBenYXBBV0U8i2Xi5UFZbT98xYhvQo=; b=mayhLTFX64nXumGeeW4uZV9Uhxb1pDlbIyDrZL6zmY1kuAcf3mp9v/wjupFGT4u5+K D9GVSTUvpjsRdHXlQo46aOCKWeQMTbaXEP1Imh9O/MwEmFvKnT3i+R0iBoUGuZPWLaJL qm6QjNon7sTKqS1HH1gmYkP6gA1CMutCeF1tfO0NWcJ4X7JRott9Qnv8IBit5cgmFNI5 +6P2TzYmEk13AVXx3KU5AAB5HYUha0Lw13s8+uoDKdqqLdflpwznKashvBcl9jrayiLQ RykPZLEKkntAoqHi5/jxeGM8pQAUhGUsXhSHEepOvMX+edYY942te9hs9yVfDPk1ww3R Tk7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789831399; x=1790436199; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=du4V1DlmNl3hSpBenYXBBV0U8i2Xi5UFZbT98xYhvQo=; b=AFtiMTLx+5S+UBUu8DPycYQyLHczOWHaZMpcD0NXVMCIuwXi9n8mltDcqGICdsnaJy zefeJ/NsLhfD/lP7FSTray/MXs0/imUcpIc1exZQo/Sss2RV+7d8Gd0c4VFqjHExbgYc +nMo2YfCOIF1e3QOE196Or7JnRfd7mZT2iuS4/6D+Zgyxbd2xMSV9/K83AC/GKngIv23 l4BHILceQGC86R1XeV6gDmVvPT4SHayKarKhEfgBR2GjUREBdgpM3ppgQM+rhRuKqcCI zwtSGWHxIkM75K0uaLJ13P0VyYQW1UnAXYwRLIegznQmY//NY/7RewMleSaGFGhri3HS uS7Q== X-Forwarded-Encrypted: i=1; AKwUvBy6bwXA+f2PVoGtaYUZk/t/j4ZmYFya+kgZcWpko/KPyyoFaF1TjUIWJpkP4NK9omgAY1k3FedvSyh33yM=@vger.kernel.org X-Gm-Message-State: AFuF++n06IUBwy8OgExsnBy/hkglv79tHw5Odq8qPbztdRSq5p5CKo/z kMX5j1bLLv5YurtwTzdmG+VLFTjsAn43ZD9s5I8Qjo6L70FyTHzfpIhHVSFvuQ== X-Gm-Gg: AYBFou3unLFIC8/VRrQL2Gzfa8ozk6o7D+aU3YDWm7T232TzmC60m8ocPkPQE0ro0Pi TPL1zsllGAz3N/3CvSQ9kKASBtXULtAxAg/2GjtSgVEKt1sFDplH/HbxQAvkzh5gDnjGGlSg/9h ZGzmdpJwdepNaojlh7S6oVFJaooXS/QNpPTi+SuRLIhyEPvsCzsBXQow6lr05QKBkV8YNRnOKqy UTBfYnsBmDyeHRleOs8WcFrgm9HCEGsoZWDtAds9t9AxWhbVKAgbRtSYtMwmKbMmxTiyqeHjOif Nofk0htNs5IkALY+q7bAEV2rC00xsNhR0KNHzH6IcYPcat2CU04SvNH+UOlaHZRWPHOvzRgvIhK LqTLw40Sa+uPP29zhsxP5m4kP+HI+udzX3ILU+DdZRH660RSxmt0Tg+IsMlRHwpHO6wn6uaLYBr bXC+7YLMO9p3DRkXW52JNZ3KhPTMZZya2nJ+Iokldl+FESFqDLz7wjORJsjrDs6RLQHQkF+Qh4Y gHhwHTJ15TA X-Received: by 2002:a17:90b:5784:b0:39e:6c68:c779 with SMTP id 98e67ed59e1d1-39e6c68ca1emr4003563a91.47.1789831399409; Sat, 19 Sep 2026 08:23:19 -0700 (PDT) Received: from localhost.localdomain ([47.100.192.162]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-3a0309d5760sm326230a91.4.2026.09.19.08.23.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 08:23:18 -0700 (PDT) From: Yang Wen To: linkinjeon@kernel.org, sj1557.seo@samsung.com, chizhiling@163.com Cc: yuezhang.mo@sony.com, exfat@lists.linux.dev, linux-kernel@vger.kernel.org, Yang Wen Subject: [PATCH v5 2/3] exfat: retain the next empty directory entry hint Date: Sat, 19 Sep 2026 23:22:39 +0800 Message-Id: <20260919152240.1507914-3-anmuxixixi@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260919152240.1507914-1-anmuxixixi@gmail.com> References: <20260919152240.1507914-1-anmuxixixi@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" After a Bloom filter miss skips the name scan, empty-entry allocation can still rescan the directory from the beginning. Calculate the next empty-entry hint when a free entry set is found, but publish it only after the entry set is committed. Record the minimum entry-set size for which a saved hint is valid, so a later shorter name rescans earlier entries and can reuse smaller holes. Retain the hint while the name filter is active and invalidate it whenever create rollback, unlink, rmdir, rename, or move can free entries. Also invalidate the destination name filter on rename or move errors because the new entry may already exist on disk. This preserves the fast append path during bulk creation without allowing stale hints or filters to hide or skip reusable directory entries. Signed-off-by: Yang Wen --- fs/exfat/dir.c | 14 +++++++- fs/exfat/exfat_fs.h | 5 ++- fs/exfat/namei.c | 86 +++++++++++++++++++++++++++++++++++++++++---- 3 files changed, 96 insertions(+), 9 deletions(-) diff --git a/fs/exfat/dir.c b/fs/exfat/dir.c index 0c5648e23e20..08b7a50de871 100644 --- a/fs/exfat/dir.c +++ b/fs/exfat/dir.c @@ -1109,6 +1109,7 @@ static inline void exfat_reset_empty_hint(struct exfa= t_hint_femp *hint_femp) { hint_femp->eidx =3D EXFAT_HINT_NONE; hint_femp->count =3D 0; + hint_femp->min_entries =3D 0; } =20 static inline void exfat_set_empty_hint(struct exfat_inode_info *ei, @@ -1122,6 +1123,7 @@ static inline void exfat_set_empty_hint(struct exfat_= inode_info *ei, if (candi_empty->count =3D=3D 0) { candi_empty->cur =3D *clu; candi_empty->eidx =3D dentry; + candi_empty->min_entries =3D num_entries; } =20 if (entry_type =3D=3D TYPE_UNUSED) @@ -1332,6 +1334,7 @@ int exfat_find_dir_entry(struct super_block *sb, stru= ct exfat_inode_info *ei, ei->hint_femp.cur.dir =3D EXFAT_EOF_CLUSTER; ei->hint_femp.eidx =3D p_dir->size * dentries_per_clu; ei->hint_femp.count =3D 0; + ei->hint_femp.min_entries =3D num_entries; } =20 exfat_build_name_filter(sb, ei, p_dir); @@ -1431,6 +1434,7 @@ static int exfat_get_volume_label_dentry(struct super= _block *sb, hint_femp.cur =3D clu; hint_femp.eidx =3D dentry; hint_femp.count =3D 1; + hint_femp.min_entries =3D 1; } } =20 @@ -1464,6 +1468,7 @@ static int exfat_get_volume_label_dentry(struct super= _block *sb, hint_femp.cur.dir =3D EXFAT_EOF_CLUSTER; hint_femp.eidx =3D dentry; hint_femp.count =3D 0; + hint_femp.min_entries =3D 1; } =20 ei->hint_femp =3D hint_femp; @@ -1518,7 +1523,9 @@ int exfat_write_volume_label(struct super_block *sb, struct inode *root_inode =3D sb->s_root->d_inode; struct exfat_entry_set_cache es; struct exfat_chain clu; + struct exfat_hint_femp next_hint; struct exfat_dentry *ep; + bool entry_allocated =3D false; =20 if (label->name_len > EXFAT_VOLUME_LABEL_LEN) return -EINVAL; @@ -1533,7 +1540,10 @@ int exfat_write_volume_label(struct super_block *sb, goto unlock; } =20 - ret =3D exfat_find_empty_entry(root_inode, &clu, 1, &es); + ret =3D exfat_find_empty_entry(root_inode, &clu, 1, &es, + &next_hint); + if (ret >=3D 0) + entry_allocated =3D true; } =20 if (ret < 0) @@ -1558,6 +1568,8 @@ int exfat_write_volume_label(struct super_block *sb, es.modified =3D true; =20 ret =3D exfat_put_dentry_set(&es, IS_DIRSYNC(root_inode)); + if (!ret && entry_allocated) + EXFAT_I(root_inode)->hint_femp =3D next_hint; =20 unlock: mutex_unlock(&sbi->s_lock); diff --git a/fs/exfat/exfat_fs.h b/fs/exfat/exfat_fs.h index 899b276f105b..3bbfa7092c0d 100644 --- a/fs/exfat/exfat_fs.h +++ b/fs/exfat/exfat_fs.h @@ -154,6 +154,8 @@ struct exfat_hint_femp { int eidx; /* count of continuous empty entry */ int count; + /* minimum entry-set size for which this hint is safe */ + int min_entries; /* the cluster that first empty slot exists in */ struct exfat_chain cur; }; @@ -581,7 +583,8 @@ extern const struct dentry_operations exfat_dentry_ops; extern const struct dentry_operations exfat_utf8_dentry_ops; int exfat_find_empty_entry(struct inode *inode, struct exfat_chain *p_dir, int num_entries, - struct exfat_entry_set_cache *es); + struct exfat_entry_set_cache *es, + struct exfat_hint_femp *next_hint); =20 /* cache.c */ int exfat_cache_init(void); diff --git a/fs/exfat/namei.c b/fs/exfat/namei.c index 83ded3b52a8c..6745cbce0c6d 100644 --- a/fs/exfat/namei.c +++ b/fs/exfat/namei.c @@ -199,6 +199,54 @@ const struct dentry_operations exfat_utf8_dentry_ops = =3D { .d_compare =3D exfat_utf8_d_cmp, }; =20 +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_hint_femp *hint_femp) +{ + struct exfat_sb_info *sbi =3D EXFAT_SB(inode->i_sb); + unsigned int next =3D dentry + num_entries; + unsigned int total =3D exfat_cluster_to_dentries(sbi, p_dir->size); + struct exfat_chain cur; + + hint_femp->min_entries =3D num_entries; + + if (next >=3D total) { + exfat_chain_set(&hint_femp->cur, EXFAT_EOF_CLUSTER, 0, + p_dir->flags); + hint_femp->eidx =3D total; + hint_femp->count =3D 0; + return; + } + + cur.dir =3D exfat_sector_to_cluster(sbi, + es->bh[es->num_bh - 1]->b_blocknr); + cur.flags =3D p_dir->flags; + cur.size =3D 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)) { + hint_femp->eidx =3D EXFAT_HINT_NONE; + hint_femp->count =3D 0; + return; + } + } + + hint_femp->cur =3D cur; + hint_femp->eidx =3D next; + hint_femp->count =3D 0; +} + +static void exfat_invalidate_empty_hint(struct inode *inode) +{ + struct exfat_inode_info *ei =3D EXFAT_I(inode); + + ei->hint_femp.eidx =3D EXFAT_HINT_NONE; + ei->hint_femp.count =3D 0; + ei->hint_femp.min_entries =3D 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, @@ -295,7 +343,8 @@ static int exfat_check_max_dentries(struct inode *inode) */ int exfat_find_empty_entry(struct inode *inode, struct exfat_chain *p_dir, int num_entries, - struct exfat_entry_set_cache *es) + struct exfat_entry_set_cache *es, + struct exfat_hint_femp *next_hint) { int dentry, ret; unsigned int last_clu; @@ -309,8 +358,9 @@ int exfat_find_empty_entry(struct inode *inode, hint_femp.eidx =3D EXFAT_HINT_NONE; =20 if (ei->hint_femp.eidx !=3D EXFAT_HINT_NONE) { - hint_femp =3D ei->hint_femp; - ei->hint_femp.eidx =3D EXFAT_HINT_NONE; + if (num_entries >=3D ei->hint_femp.min_entries) + hint_femp =3D ei->hint_femp; + exfat_invalidate_empty_hint(inode); } =20 exfat_chain_set(p_dir, ei->start_clu, @@ -385,6 +435,9 @@ int exfat_find_empty_entry(struct inode *inode, inode->i_blocks +=3D sbi->cluster_size >> 9; } =20 + exfat_set_next_empty_hint(inode, p_dir, dentry, num_entries, es, + next_hint); + p_dir->dir =3D exfat_sector_to_cluster(sbi, es->bh[0]->b_blocknr); p_dir->size -=3D dentry >> sbi->dentries_per_clu_bits; =20 @@ -469,6 +522,7 @@ static int exfat_add_entry(struct inode *inode, const c= har *path, struct exfat_chain clu; struct timespec64 ts =3D current_time(inode); struct exfat_entry_set_cache es; + struct exfat_hint_femp next_hint; int clu_size =3D 0; unsigned int start_clu =3D EXFAT_FREE_CLUSTER; bool dir_allocated =3D false; @@ -484,7 +538,8 @@ static int exfat_add_entry(struct inode *inode, const c= har *path, } =20 /* exfat_find_empty_entry must be called before alloc_cluster() */ - dentry =3D exfat_find_empty_entry(inode, &info->dir, num_entries, &es); + dentry =3D exfat_find_empty_entry(inode, &info->dir, num_entries, &es, + &next_hint); if (dentry < 0) { ret =3D dentry; /* -EIO or -ENOSPC */ goto out; @@ -516,6 +571,7 @@ static int exfat_add_entry(struct inode *inode, const c= har *path, dentry, ES_ALL_ENTRIES); if (!cleanup_ret) { exfat_remove_entries(inode, &es, ES_IDX_FILE, false); + exfat_invalidate_empty_hint(inode); cleanup_ret =3D exfat_put_dentry_set(&es, IS_DIRSYNC(inode)); } @@ -524,6 +580,7 @@ static int exfat_add_entry(struct inode *inode, const c= har *path, exfat_free_cluster(inode, &clu); goto out; } + EXFAT_I(inode)->hint_femp =3D next_hint; =20 info->entry =3D dentry; exfat_name_filter_add(inode, &uniname); @@ -628,7 +685,8 @@ static int exfat_find(struct inode *dir, const struct q= str *qname, ei->hint_stat.clu =3D cdir.dir; ei->hint_stat.eidx =3D 0; ei->version =3D (inode_peek_iversion_raw(dir) & 0xffffffff); - ei->hint_femp.eidx =3D EXFAT_HINT_NONE; + if (!ei->name_filter) + ei->hint_femp.eidx =3D EXFAT_HINT_NONE; } =20 /* search the file name for directories */ @@ -804,6 +862,8 @@ static int exfat_unlink(struct inode *dir, struct dentr= y *dentry) =20 /* update the directory entry */ exfat_remove_entries(inode, &es, ES_IDX_FILE, true); + exfat_invalidate_empty_hint(dir); + err =3D exfat_put_dentry_set(&es, IS_DIRSYNC(inode)); if (err) goto unlock; @@ -958,6 +1018,8 @@ static int exfat_rmdir(struct inode *dir, struct dentr= y *dentry) exfat_set_volume_dirty(sb); =20 exfat_remove_entries(inode, &es, ES_IDX_FILE, true); + exfat_invalidate_empty_hint(dir); + err =3D exfat_put_dentry_set(&es, IS_DIRSYNC(dir)); if (err) goto unlock; @@ -1032,9 +1094,10 @@ static int exfat_rename_file(struct inode *parent_in= ode, if (old_es.num_entries < num_total_entries) { int newentry; struct exfat_chain dir; + struct exfat_hint_femp next_hint; =20 newentry =3D exfat_find_empty_entry(parent_inode, &dir, - num_total_entries, &new_es); + num_total_entries, &new_es, &next_hint); if (newentry < 0) { ret =3D newentry; /* -EIO or -ENOSPC */ goto put_old_es; @@ -1066,6 +1129,7 @@ static int exfat_rename_file(struct inode *parent_ino= de, } goto put_old_es; } + EXFAT_I(parent_inode)->hint_femp =3D next_hint; =20 exfat_remove_entries(parent_inode, &old_es, ES_IDX_FILE, false); ei->dir =3D dir; @@ -1093,6 +1157,7 @@ static int exfat_move_file(struct inode *parent_inode, struct exfat_dentry *epmov, *epnew; struct exfat_entry_set_cache mov_es, new_es; struct exfat_chain newdir; + struct exfat_hint_femp next_hint; unsigned int num_extra_entries, num_total_entries; =20 num_new_entries =3D exfat_calc_num_entries(p_uniname); @@ -1110,7 +1175,7 @@ static int exfat_move_file(struct inode *parent_inode, num_total_entries =3D num_new_entries + num_extra_entries; =20 newentry =3D exfat_find_empty_entry(parent_inode, &newdir, - num_total_entries, &new_es); + num_total_entries, &new_es, &next_hint); if (newentry < 0) { ret =3D newentry; /* -EIO or -ENOSPC */ goto put_mov_es; @@ -1139,10 +1204,12 @@ static int exfat_move_file(struct inode *parent_ino= de, 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; } + EXFAT_I(parent_inode)->hint_femp =3D next_hint; =20 exfat_remove_entries(parent_inode, &mov_es, ES_IDX_FILE, false); =20 @@ -1215,8 +1282,11 @@ static int __exfat_rename(struct inode *old_parent_i= node, ret =3D exfat_rename_file(new_parent_inode, &uni_name, ei); else ret =3D 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); + else + exfat_name_filter_free(new_parent_inode); =20 if (!ret && new_inode) { struct exfat_entry_set_cache es; @@ -1229,6 +1299,8 @@ static int __exfat_rename(struct inode *old_parent_in= ode, } =20 exfat_remove_entries(new_inode, &es, ES_IDX_FILE, true); + exfat_invalidate_empty_hint(new_parent_inode); + ret =3D exfat_put_dentry_set(&es, IS_DIRSYNC(new_inode)); if (ret) goto del_out; --=20 2.34.1 From nobody Thu Sep 24 22:13:36 2026 Received: from mail-pj2-f13.google.com (mail-pj2-f13.google.com [74.125.227.141]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A85A3363082 for ; Sat, 19 Sep 2026 15:23:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.227.141 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831408; cv=none; b=PzQXGkkStK8Y3IXr1PK50JNh3VkIbelPePbdKbJlZD1CuW0lypD1l3AY3Gl16I2v3BMhpLrYOsIv0sShmJFkThzsX3GDye1hzjniM76N0LTq0+eYMsDqIYCE++Luf1f0kAhex0WV3Ko88KzrFR3lLdBqH8ac89wpmsSmypiFzsM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789831408; c=relaxed/simple; bh=Yqaq1Hk7u4nrzYHc+3CVcf4COPL1wBi/iltVI2RQc7w=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=C+3YkrKbORO6pvMfF+MwyyVD1KISpigOA/bvsvVkd9xspLsQz8FVKMxSi8BeDGpHj50mb5WvdFN5fIHDZ3YmSOT9oTYxMH4QJgPTFWQhFWBJ+AzRCbhNQCa+y0PVS4rhaOpzRNJtKNQ8sV92qr+l8SyN5H5OkDGWX4Msrjjqn2w= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ECPgg0Ba; arc=none smtp.client-ip=74.125.227.141 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ECPgg0Ba" Received: by mail-pj2-f13.google.com with SMTP id 98e67ed59e1d1-39b5b07ec78so1191730a91.3 for ; Sat, 19 Sep 2026 08:23:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789831406; x=1790436206; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=qR79KzzQEHA1BCgom4FGsnXuKP2YSduNO1GGm9Xb7l8=; b=ECPgg0BaGm42QEN4JUQ5Oe0CGZ8IkK/Pb9i+pjmPfNu+4Es4Ddwca6MYPQy5RZUn2l 1jHh15WVKy9Y8aPg2BC7Ej7/NyBBLbixGvgaNc1mVkBh7OYbfrMIhBBHY41w+6Ka3eew sOGMh0t0F1gN9abo/BrjjExgmQ13Sb8Bj3qIAnlOyd/HhLrQZmUStD/eSZIT+FGGG4zh 98xh87wkcYwGprK+asgE0pHDTjHictQgzhGlWDt1BtA0wEPV4RiSEQL40FBuQ1zoXP6w cTOfASSjcl5QKsr2aGyqN07PVNR+EF/X838eoqGFjwRpk+7dlsPC7CvZ3hWwZg+qwmm9 cvPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789831406; x=1790436206; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=qR79KzzQEHA1BCgom4FGsnXuKP2YSduNO1GGm9Xb7l8=; b=Fov1Ik4o9x6bMXwiOB/2UZGoUJUhTY3TvXzw6YckYVRs9+HMIWuMK2jxrl0TpHbWUI SLMXLK86OXn4CzFisTG0inwmDxuGJuPKfElAwKqrLinrPg6X05Q6+/tl1ZmgKB2n1Bun f5Pl2DBuwp+cF0FGU5sgP+EwTNHzDNQQ2fVP6C+9Iwxn8f+r0C/g7cfRq2tatw8xeD9c fqxCn55OyIuQYbm8nyLRRsqi46zmGKgLq6t8PzLxwA9Mv3IQFPDaJZwNSYK56XlgkRFu QzYwn7KHM+EjS7xmR/ysN3rWhiNuxnwbWLNUdempSucF3FS+n4CWsz8gaoEPF/DQ1ltV yY2A== X-Forwarded-Encrypted: i=1; AKwUvBwtoIV9DmpDCkgFd5X/jawMDQCYp2kXSx8Og5uJISMnYwYM9ndDQ+OwVDatJp42s1SICH1pjUxnLxe6IKA=@vger.kernel.org X-Gm-Message-State: AFuF++kkdzdR/8aS25oLznPOIrWTjiPOVgXM6x5yDxm7JincnIXU1HCg lK5EYg3HcqcgFiegBa1vCd/VZLjz/R4WOgrA893tApyEOgREVxy9R5lp X-Gm-Gg: AYBFou2U5k8cJioK32Yo3w+fVaU6ArDm4R/m4x+btgBA4/ES4/g9+oZWRYmekbQ5aHN yyBgIBNaSRrn6Yw3lfs6JFcYaD74DAvp+ds8iVxhm2zr3lP+5f/uR+FCCWR6o7xs94hwnCOpHAe jAqTLwjxFLyCsnx86gGGZ3uhxof7wyBppX4gkT8DtNk7x0eX+ajiuU9hZZtPWM4zE1Crp+JaEjZ e0pUUfLNq0Yi93ZSLms2r5G7arUrIGz+lUrEumDrrxdv6hLlfULT1TEq7qPTsk9aCoiMcPSo3QZ vH3coOijcGTqMLRVr4DOmNy4VirUfNfz/dOJ44E1j5YTeqZ+Uw0PzS9Vn0ToRq+AguzZan8hgBL 07ItFT42PkhDt0/g1oaR2jwQIX7GPyChInPxhgKQWiRVvqmUbE6b6p8H4C76MTtcIE4vFW9amSb 2ZfzHDegP4I5wKotbH9xoYu70hIjORSPz/Y2WD62PYA2dotjHu5MwOa2UT5CjKPIIlUbMuaRwtS PsIHm656aBUja4VNkHsUTI= X-Received: by 2002:a17:90b:548d:b0:398:c3ca:1ebc with SMTP id 98e67ed59e1d1-39e54d11d8dmr10521409a91.18.1789831405770; Sat, 19 Sep 2026 08:23:25 -0700 (PDT) Received: from localhost.localdomain ([47.100.192.162]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-3a0309d5760sm326230a91.4.2026.09.19.08.23.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 08:23:24 -0700 (PDT) From: Yang Wen To: linkinjeon@kernel.org, sj1557.seo@samsung.com, chizhiling@163.com Cc: yuezhang.mo@sony.com, exfat@lists.linux.dev, linux-kernel@vger.kernel.org, Yang Wen Subject: [PATCH v5 3/3] exfat: reclaim name filters under memory pressure Date: Sat, 19 Sep 2026 23:22:40 +0800 Message-Id: <20260919152240.1507914-4-anmuxixixi@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20260919152240.1507914-1-anmuxixixi@gmail.com> References: <20260919152240.1507914-1-anmuxixixi@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 --- 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 08b7a50de871..013b7e43a289 100644 --- a/fs/exfat/dir.c +++ b/fs/exfat/dir.c @@ -9,6 +9,7 @@ #include #include #include +#include #include =20 #include "exfat_raw.h" @@ -91,12 +92,144 @@ static void exfat_name_filter_indexes(struct super_blo= ck *sb, EXFAT_NAME_FILTER_ORDER); } =20 +static unsigned long * +exfat_name_filter_detach_locked(struct exfat_sb_info *sbi, + struct exfat_inode_info *ei) +{ + unsigned long *filter =3D ei->name_filter; + + if (!filter) + return NULL; + + ei->name_filter =3D 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 =3D 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 =3D EXFAT_I(inode); + struct exfat_sb_info *sbi; + unsigned long *filter; =20 - kvfree(ei->name_filter); - ei->name_filter =3D NULL; + if (!READ_ONCE(ei->name_filter)) + return; + + sbi =3D EXFAT_SB(inode->i_sb); + spin_lock(&sbi->name_filter_lock); + filter =3D 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 =3D shrinker->private_data; + unsigned long count; + + spin_lock(&sbi->name_filter_lock); + count =3D 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 =3D shrinker->private_data; + unsigned long freed =3D 0; + + /* Avoid reclaim recursion from a GFP_NOFS allocation under s_lock. */ + if (!mutex_trylock(&sbi->s_lock)) { + sc->nr_scanned =3D 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 =3D list_first_entry(&sbi->name_filter_lru, + struct exfat_inode_info, + name_filter_lru); + filter =3D 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 =3D freed; + return freed; +} + +void exfat_name_filter_shrinker_register(struct super_block *sb) +{ + struct exfat_sb_info *sbi =3D EXFAT_SB(sb); + struct shrinker *shrinker; + + shrinker =3D 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 =3D exfat_name_filter_count_objects; + shrinker->scan_objects =3D exfat_name_filter_scan_objects; + shrinker->private_data =3D sbi; + shrinker_register(shrinker); + sbi->name_filter_shrinker =3D shrinker; +} + +void exfat_name_filter_shrinker_unregister(struct super_block *sb) +{ + struct exfat_sb_info *sbi =3D EXFAT_SB(sb); + struct shrinker *shrinker =3D sbi->name_filter_shrinker; + + sbi->name_filter_shrinker =3D 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 =3D list_first_entry(&sbi->name_filter_lru, + struct exfat_inode_info, + name_filter_lru); + filter =3D exfat_name_filter_detach_locked(sbi, ei); + spin_unlock(&sbi->name_filter_lock); + kvfree(filter); + } } =20 bool exfat_name_filter_maybe_contains(struct inode *inode, @@ -108,6 +241,7 @@ bool exfat_name_filter_maybe_contains(struct inode *ino= de, if (!ei->name_filter) return true; =20 + 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; =20 + 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 =3D EXFAT_SB(sb); int i; =20 - 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, } =20 complete: + spin_lock(&sbi->name_filter_lock); ei->name_filter =3D 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 3bbfa7092c0d..b3edb6fdfca6 100644 --- a/fs/exfat/exfat_fs.h +++ b/fs/exfat/exfat_fs.h @@ -14,6 +14,8 @@ #include #include =20 +struct shrinker; + #define EXFAT_ROOT_INO 1 =20 /* @@ -263,6 +265,11 @@ struct exfat_sb_info { =20 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; }; =20 @@ -294,6 +301,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; =20 spinlock_t cache_lru_lock; struct list_head cache_lru; @@ -635,6 +643,8 @@ bool exfat_name_filter_maybe_contains(struct inode *ino= de, 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); =20 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 4924f0fad836..465e33c9ba49 100644 --- a/fs/exfat/super.c +++ b/fs/exfat/super.c @@ -46,6 +46,7 @@ static void exfat_put_super(struct super_block *sb) { struct exfat_sb_info *sbi =3D EXFAT_SB(sb); =20 + exfat_name_filter_shrinker_unregister(sb); mutex_lock(&sbi->s_lock); exfat_clear_volume_dirty(sb); exfat_free_bitmap(sbi); @@ -210,6 +211,7 @@ static struct inode *exfat_alloc_inode(struct super_blo= ck *sb) return NULL; =20 ei->name_filter =3D NULL; + INIT_LIST_HEAD(&ei->name_filter_lru); return &ei->vfs_inode; } =20 @@ -746,6 +748,8 @@ static int exfat_fill_super(struct super_block *sb, str= uct fs_context *fc) goto free_table; } =20 + exfat_name_filter_shrinker_register(sb); + return 0; =20 put_inode: @@ -845,6 +849,10 @@ static int exfat_init_fs_context(struct fs_context *fc) =20 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 =3D 0; + sbi->name_filter_shrinker =3D NULL; ratelimit_state_init(&sbi->ratelimit, DEFAULT_RATELIMIT_INTERVAL, DEFAULT_RATELIMIT_BURST); =20 --=20 2.34.1