【小ネタ】Linux 6.15でExFATのファイル削除が高速化された話

今回はLinux 6.15で高速化されたexFATのファイル削除処理について、ソースコードベースで改善点を解説します。

結論

  • exFATかつdiscardオプションをつけてマウントした場合のファイル削除が高速化
    • そんな場面はほとんど無さそうなので実際の恩恵は…🤔
  • 80GBのファイルを削除するのに5分弱かかっていたのが1.6秒に短縮

だれも使わないから数年放置されてきたのが修正されただけのように見えるが…一応調べてみる。

LinuxにおけるexFATの利用について

一般的にLinuxのファイルシステムではext4やxfsがメインで使われます。
特にext4は最も広く使われる汎用ジャーナリングファイルシステムで、Ubuntu、Debian、Linux Mint など多くのLinuxディストリビューションでrootパーティションのデフォルトとして採用されています。
他にもRHEL系ではxfsがデフォルトで使われていたり、より高機能なファイルシステムとしてBtrfs、Bcachefsなども開発・利用されています。

一方でexFATについては、主にUSBメモリやSDカードといった外部リムーバブルメディアでよく利用されます。Windows/MacOS/Linuxでネイティブ対応されておりクロスプラットフォーム間で大容量ファイルをやりとりする場合に便利です。
とはいえexFATをrootパーティションとして利用することは基本的にありません。

マウントにおけるdiscardオプションとは

discard オプションを指定してマウントすると、ファイルを削除した際に自動的に TRIM コマンドが発行され、SSD 上の未使用ブロックが速やかに解放されます。

TRIM コマンドとは

TRIMコマンドはSSDのガベージコレクション効率を高め、書き込み性能の劣化やセル摩耗を抑えるためにOS側が「このブロックはもう使わない」とストレージに通知するATA/SCSIコマンドです。

OSがファイル削除やファイルシステム上でのブロック解放を行った際、対応する未使用ブロックをSSDコントローラに即座に知らせ内部的に消去(discard)させます。
これにより後続の書き込みで不要なガベージコレクションを回避し、書き込み遅延を減少させます。

fstrimとの選択

discardオプションを指定してマウントする場合、ファイルを削除した際に自動的に TRIM コマンドが発行されます。この場合 I/O ごとにコマンドが走るため、動作中のパフォーマンス低下を招くことがあります。
代替としてnodiscardでマウントして定期的に fstrim を実行する方法もあります。
この場合I/O毎にTRIMコマンドは実行されませんが、fstrimを実行した際に大きなフリーズが発生します。どちらを利用するかはシステムに応じて使い分ける形になると思います。
参考) https://tagomoris.hatenablog.com/entry/2019/06/24/110537

USBメモリ/SDカードにおけるTRIM

多くの USB メモリや SD カード(特に低価格帯の製品)は TRIM に非対応のため、discard を指定しても効果が現れません。
効果を得たい場合は NVMe SSD や eMMC など TRIM 対応ストレージ上で有効ですが、これらのストレージを exFAT で利用する機会は多くないと思います。

高速化の中身

ここからが本題です。
Linux 6.15ではdiscardオプションでマウントしたexFATのファイル削除が高速化されています。

FATのクラスタについて

まずはFATのクラスタ(cluster)について簡潔に解説します。
クラスタはFAT系ファイルシステムにおける最小の割り当て単位です。

1クラスタは複数のセクタから構成されており、exFATでは通常1クラスタ=8〜128セクタ(4KB〜64KB程度)です。ファイルのデータはクラスタ単位でストレージ上に割り当てられ、サイズが小さくても1クラスタ分は確保されます。

FATのFile Allocation Tableについて

FATの名前の由来となっているFAT (File Allocation Table)についても簡潔に解説します。

FATは、ストレージ上の全クラスタの「つながり」を管理する配列です。
構造としては各クラスタ番号に対応したエントリを持ちます。

例)クラスタ#5に対応するのはFAT[5]
FAT[5] = 6 → 意味:クラスタ5の次はクラスタ6
FAT[6] = 7 → 意味:クラスタ6の次はクラスタ7
FAT[7] = 0xFFFFFFFF → ここで終了(EOF)

このように、FATは単方向リスト構造のチェーンでファイルのデータ位置を表します。
なおexFATでは、従来のFATに加えてフリービットマップ領域も導入しています。
各クラスタが未使用(free)かどうかを1ビットで保持し、より高速な「空きクラスタ探索」に使われます。

Linux 6.14までの挙動

exfat: support batch discard of clusters when freeing clusters

簡単にまとめると exfat_clear_bitmap() からdiscard処理を切り出し、一つ上の__exfat_free_cluster()から呼び出すように変更した。
関数のコールグラフは以下の通りです。

exfat_clear_bitmap()
 -> __exfat_free_cluster()
  -> exfat_free_cluster()
   -> __exfat_truncate()
    -> exfat_evict_inode() // fs/exfat/inode.c
     -> evict() // fs/inode.c

exfat_clear_bitmap()

int exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync)
{
	int i, b;
	unsigned int ent_idx;
	struct super_block *sb = inode->i_sb;
	struct exfat_sb_info *sbi = EXFAT_SB(sb);
	struct exfat_mount_options *opts = &sbi->options;

	if (!is_valid_cluster(sbi, clu))
		return -EIO;

	ent_idx = CLUSTER_TO_BITMAP_ENT(clu);
	i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx);
	b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx);

	if (!test_bit_le(b, sbi->vol_amap[i]->b_data))
		return -EIO;

	clear_bit_le(b, sbi->vol_amap[i]->b_data);

	exfat_update_bh(sbi->vol_amap[i], sync);

	if (opts->discard) {
		int ret_discard;

		ret_discard = sb_issue_discard(sb,
			exfat_cluster_to_sector(sbi, clu),
			(1 << sbi->sect_per_clus_bits), GFP_NOFS, 0);

		if (ret_discard == -EOPNOTSUPP) {
			exfat_err(sb, "discard not supported by device, disabling");
			opts->discard = 0;
		}
	}

	return 0;
}

exfat_clear_bitmap() は、引数で指定されたクラスタ clu をビットマップから解放します。

12-14: クラスタ番号からビットマップ内のエントリ位置 ent_idx、セクタインデックス i 、ビット位置 b を計算します。
19-21: ビットが立っていれば clear_bit_le() でクリアし、exfat_update_bh() でビットマップバッファを更新します。第三引数 sync が真の場合は、即座にディスクへ反映されます。

23-28: マウントオプションで discard が有効な場合は、TRIM命令をデバイスに発行します。
デバイスがTRIM非対応なら、エラーメッセージを出して以降のdiscard処理を無効化します。

__exfat_free_cluster()

/* This function must be called with bitmap_lock held */
static int __exfat_free_cluster(struct inode *inode, struct exfat_chain *p_chain)
{
	struct super_block *sb = inode->i_sb;
	struct exfat_sb_info *sbi = EXFAT_SB(sb);
	int cur_cmap_i, next_cmap_i;
	unsigned int num_clusters = 0;
	unsigned int clu;
...
	if (p_chain->flags == ALLOC_NO_FAT_CHAIN) {
		int err;
		unsigned int last_cluster = p_chain->dir + p_chain->size - 1;
		do {
			bool sync = false;

			if (clu < last_cluster)
				next_cmap_i =
				  BITMAP_OFFSET_SECTOR_INDEX(sb, CLUSTER_TO_BITMAP_ENT(clu+1));

			/* flush bitmap only if index would be changed or for last cluster */
			if (clu == last_cluster || cur_cmap_i != next_cmap_i) {
				sync = true;
				cur_cmap_i = next_cmap_i;
			}

			err = exfat_clear_bitmap(inode, clu, (sync && IS_DIRSYNC(inode)));
			if (err)
				break;
			clu++;
			num_clusters++;
		} while (num_clusters < p_chain->size);
	} else {
		do {
			bool sync = false;
			unsigned int n_clu = clu;
			int err = exfat_get_next_cluster(sb, &n_clu);

			if (err || n_clu == EXFAT_EOF_CLUSTER)
				sync = true;
			else
				next_cmap_i =
				  BITMAP_OFFSET_SECTOR_INDEX(sb, CLUSTER_TO_BITMAP_ENT(n_clu));

			if (cur_cmap_i != next_cmap_i) {
				sync = true;
				cur_cmap_i = next_cmap_i;
			}

			if (exfat_clear_bitmap(inode, clu, (sync && IS_DIRSYNC(inode))))
				break;
			clu = n_clu;
			num_clusters++;

			if (err)
				break;

			if (num_clusters >= sbi->num_clusters - EXFAT_FIRST_CLUSTER) {
				/*
				 * The cluster chain includes a loop, scan the
				 * bitmap to get the number of used clusters.
				 */
				exfat_count_used_clusters(sb, &sbi->used_clusters);

				return 0;
			}
		} while (clu != EXFAT_EOF_CLUSTER);
	}

	sbi->used_clusters -= num_clusters;
	return 0;
}

ALLOC_NO_FAT_CHAIN フラグが立っている場合は、クラスタが連続しているとみなして単純なループでビットマップをクリアします。
各クラスタごとに、ビットマップセクタが変わるタイミングや最後のクラスタでのみ同期を行い、無駄なI/Oを抑えています。
一方で、TRIM命令は各クラスタのビットマップをクリアする度に発行されます。

FATチェーンの場合は、FATテーブルを辿って次のクラスタを取得しながら解放します。
こちらも同様にクラスタのビットマップをクリアする度にTRIM命令が発行されます。

sb_issue_discard()

exfat_clear_bitmap() 内部で呼ばれているTRIM命令を発行する sb_issue_discard() について。
sb_issue_discard() は第二引数に開始セクタ、第三引数にdiscardするセクタ数を取ります。
呼び出しでは第三引数に sbi->sect_per_clus_bits 1クラスタ分のセクタ数を渡していますが、連続したセクタであればまとめることができそうです。

int exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync)
{
	int i, b;
	unsigned int ent_idx;
	struct super_block *sb = inode->i_sb;
	struct exfat_sb_info *sbi = EXFAT_SB(sb);
...
	if (opts->discard) {
...
		ret_discard = sb_issue_discard(sb,
			exfat_cluster_to_sector(sbi, clu),
			(1 << sbi->sect_per_clus_bits), GFP_NOFS, 0);
...
}

static inline int sb_issue_discard(struct super_block *sb, sector_t block,
		sector_t nr_blocks, gfp_t gfp_mask, unsigned long flags)
{
	return blkdev_issue_discard(sb->s_bdev,
				    block << (sb->s_blocksize_bits -
					      SECTOR_SHIFT),
				    nr_blocks << (sb->s_blocksize_bits -
						  SECTOR_SHIFT),
				    gfp_mask);
}

/**
 * blkdev_issue_discard - queue a discard
 * @bdev:	blockdev to issue discard for
 * @sector:	start sector
 * @nr_sects:	number of sectors to discard
 * @gfp_mask:	memory allocation flags (for bio_alloc)
 *
 * Description:
 *    Issue a discard request for the sectors in question.
 */
int blkdev_issue_discard(struct block_device *bdev, sector_t sector,
		sector_t nr_sects, gfp_t gfp_mask)
{
	struct bio *bio = NULL;
	struct blk_plug plug;
	int ret;

	blk_start_plug(&plug);
	ret = __blkdev_issue_discard(bdev, sector, nr_sects, gfp_mask, &bio);
	if (!ret && bio) {
		ret = submit_bio_wait(bio);
		if (ret == -EOPNOTSUPP)
			ret = 0;
		bio_put(bio);
	}
	blk_finish_plug(&plug);

	return ret;
}

sbi->sect_per_clus_bits は1クラスタのセクタ数をbitで表現したものです。
基本的には0~25で、1クラスタ=1セクタ(512B)~1^25セクタ(32MB)で表現されます。
https://elm-chan.org/docs/exfat_e.html

// fs/exfat/exfat_raw.h
/* EXFAT: Main and Backup Boot Sector (512 bytes) */
struct boot_sector {
	__u8	jmp_boot[BOOTSEC_JUMP_BOOT_LEN];
	__u8	fs_name[BOOTSEC_FS_NAME_LEN];
	__u8	must_be_zero[BOOTSEC_OLDBPB_LEN];
	__le64	partition_offset;
	__le64	vol_length;
	__le32	fat_offset;
	__le32	fat_length;
	__le32	clu_offset;
	__le32	clu_count;
	__le32	root_cluster;
	__le32	vol_serial;
	__u8	fs_revision[2];
	__le16	vol_flags;
	__u8	sect_size_bits;
	__u8	sect_per_clus_bits;
	__u8	num_fats;
	__u8	drv_sel;
	__u8	percent_in_use;
	__u8	reserved[7];
	__u8	boot_code[390];
	__le16	signature;
} __packed;

// fs/exfat/super.c
if (p_boot->sect_per_clus_bits > EXFAT_MAX_SECT_PER_CLUS_BITS(p_boot)) {
	exfat_err(sb, "bogus sectors bits per cluster : %u",
			p_boot->sect_per_clus_bits);
	return -EINVAL;
}
sbi->sect_per_clus_bits = p_boot->sect_per_clus_bits;

修正パッチの内容

まずは exfat_clear_bitmap() から sb_issue_discard() の呼び出し部分を削除します。

diff --git a/fs/exfat/balloc.c b/fs/exfat/balloc.c
index 9ff825f1502d..cc01556c9d9b 100644
--- a/fs/exfat/balloc.c
+++ b/fs/exfat/balloc.c
@@ -147,7 +147,6 @@  int exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync)
 	unsigned int ent_idx;
 	struct super_block *sb = inode->i_sb;
 	struct exfat_sb_info *sbi = EXFAT_SB(sb);
-	struct exfat_mount_options *opts = &sbi->options;
 
 	if (!is_valid_cluster(sbi, clu))
 		return -EIO;
@@ -163,19 +162,6 @@  int exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync)
 
 	exfat_update_bh(sbi->vol_amap[i], sync);
 
-	if (opts->discard) {
-		int ret_discard;
-
-		ret_discard = sb_issue_discard(sb,
-			exfat_cluster_to_sector(sbi, clu),
-			(1 << sbi->sect_per_clus_bits), GFP_NOFS, 0);
-
-		if (ret_discard == -EOPNOTSUPP) {
-			exfat_err(sb, "discard not supported by device, disabling");
-			opts->discard = 0;
-		}
-	}
-
 	return 0;
 }

次に削除した部分を exfat_discard_cluster() として切り出し、__exfat_free_cluster() から呼び出すようにします。
この際に処理を追加し、連続したセクタに対してまとめてTRIM命令を発行するようにします。

 diff --git a/fs/exfat/fatent.c b/fs/exfat/fatent.c
index 6f3651c6ca91..b9473a69f104 100644
--- a/fs/exfat/fatent.c
+++ b/fs/exfat/fatent.c
@@ -144,6 +144,20 @@  int exfat_chain_cont_cluster(struct super_block *sb, unsigned int chain,
 	return 0;
 }
 
+static inline void exfat_discard_cluster(struct super_block *sb,
+		unsigned int clu, unsigned int num_clusters)
+{
+	int ret;
+	struct exfat_sb_info *sbi = EXFAT_SB(sb);
+
+	ret = sb_issue_discard(sb, exfat_cluster_to_sector(sbi, clu),
+			sbi->sect_per_clus * num_clusters, GFP_NOFS, 0);
+	if (ret == -EOPNOTSUPP) {
+		exfat_err(sb, "discard not supported by device, disabling");
+		sbi->options.discard = 0;
+	}
+}
+
 /* This function must be called with bitmap_lock held */
 static int __exfat_free_cluster(struct inode *inode, struct exfat_chain *p_chain)
 {
@@ -196,7 +210,12 @@  static int __exfat_free_cluster(struct inode *inode, struct exfat_chain *p_chain
 			clu++;
 			num_clusters++;
 		} while (num_clusters < p_chain->size);
+
+		if (sbi->options.discard)
+			exfat_discard_cluster(sb, p_chain->dir, p_chain->size);
 	} else {
+		unsigned int nr_clu = 1;
+
 		do {
 			bool sync = false;
 			unsigned int n_clu = clu;
@@ -215,6 +234,16 @@  static int __exfat_free_cluster(struct inode *inode, struct exfat_chain *p_chain
 
 			if (exfat_clear_bitmap(inode, clu, (sync && IS_DIRSYNC(inode))))
 				break;
+
+			if (sbi->options.discard) {
+				if (n_clu == clu + 1)
+					nr_clu++;
+				else {
+					exfat_discard_cluster(sb, clu - nr_clu + 1, nr_clu);
+					nr_clu = 1;
+				}
+			}
+
 			clu = n_clu;
 			num_clusters++;

改善結果

80GBのファイル削除が5分弱から1.6秒になったようです。すごい
けどやっぱりこれ誰も使わない組み合わせだから今まで気付かれず放置されてただけのような…🤔

> Measure the performance by:
>
>   # truncate -s 80G /mnt/file
>   # time rm /mnt/file
>
> Without this commit:
>
>   real    4m46.183s
>   user    0m0.000s
>   sys     0m12.863s
>
> With this commit:
>
>   real    0m1.661s
>   user    0m0.000s
>   sys     0m0.017s

参考サイト

シェアする

  • このエントリーをはてなブックマークに追加

フォローする