[PATCH 0/4] fat: allocate multiple clusters in fallocate

[PATCH 0/4] fat: allocate multiple clusters in fallocate

[Matheus Alves de Almeida]

Hi,

This series adds support for allocating multiple clusters in a single
fat_add_clusters() call in fat_fallocate().

The multi-cluster TODO in inode.c is not implemented, as doing so would
require speculative preallocation or an iomap conversion.

Matheus Alves de Almeida (4):
  fat: remove cluster allocation size limit
  fat: return only first cluster when allocating
  fat: support adding multiple clusters
  fat: allocate multiple clusters in fallocate

 fs/fat/dir.c    | 20 +++++++++++++++-
 fs/fat/fat.h    |  4 ++--
 fs/fat/fatent.c | 61 ++++++++++++++++++++++++++++++++-----------------
 fs/fat/file.c   | 10 ++++----
 fs/fat/inode.c  |  8 +++----
 5 files changed, 69 insertions(+), 34 deletions(-)

-- 
2.43.0

[PATCH 1/4] fat: remove cluster allocation size limit

[Matheus Alves de Almeida]

fat_alloc_clusters() currently BUG()s when asked to allocate more than
MAX_BUF_PER_PAGE / 2 clusters. This limit comes from the buffer_head
array used to defer syncing and mirroring.

Remove the allocation size limit by doing buffer_head batching like
fat_free_clusters() does.

Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
---
 fs/fat/fatent.c | 44 +++++++++++++++++++++++++++++++-------------
 1 file changed, 31 insertions(+), 13 deletions(-)

diff --git a/fs/fat/fatent.c b/fs/fat/fatent.c
index f0801d99d..bfab8eab5 100644
--- a/fs/fat/fatent.c
+++ b/fs/fat/fatent.c
@@ -468,6 +468,26 @@ static void fat_collect_bhs(struct buffer_head **bhs, int *nr_bhs,
 	}
 }
 
+static int fat_flush_bhs(struct super_block *sb, struct buffer_head **bhs,
+			 int *nr_bhs, bool sync)
+{
+	int err, i;
+
+	if (sync) {
+		err = fat_sync_bhs(bhs, *nr_bhs);
+		if (err)
+			return err;
+	}
+	err = fat_mirror_bhs(sb, bhs, *nr_bhs);
+	if (err)
+		return err;
+	for (i = 0; i < *nr_bhs; i++)
+		brelse(bhs[i]);
+	*nr_bhs = 0;
+
+	return 0;
+}
+
 int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 {
 	struct super_block *sb = inode->i_sb;
@@ -477,8 +497,6 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
 	int i, count, err, nr_bhs, idx_clus;
 
-	BUG_ON(nr_cluster > (MAX_BUF_PER_PAGE / 2));	/* fixed limit */
-
 	lock_fat(sbi);
 	if (sbi->free_clusters != -1 && sbi->free_clus_valid &&
 	    sbi->free_clusters < nr_cluster) {
@@ -509,14 +527,21 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 				if (prev_ent.nr_bhs)
 					ops->ent_put(&prev_ent, entry);
 
-				fat_collect_bhs(bhs, &nr_bhs, &fatent);
-
 				sbi->prev_free = entry;
 				if (sbi->free_clusters != -1)
 					sbi->free_clusters--;
 
 				cluster[idx_clus] = entry;
 				idx_clus++;
+
+				if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
+					err = fat_flush_bhs(sb, bhs, &nr_bhs,
+							    inode_needs_sync(inode));
+					if (err)
+						goto out;
+				}
+				fat_collect_bhs(bhs, &nr_bhs, &fatent);
+
 				if (idx_clus == nr_cluster)
 					goto out;
 
@@ -606,17 +631,10 @@ int fat_free_clusters(struct inode *inode, int cluster)
 		}
 
 		if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
-			if (sb->s_flags & SB_SYNCHRONOUS) {
-				err = fat_sync_bhs(bhs, nr_bhs);
-				if (err)
-					goto error;
-			}
-			err = fat_mirror_bhs(sb, bhs, nr_bhs);
+			err = fat_flush_bhs(sb, bhs, &nr_bhs,
+					    sb->s_flags & SB_SYNCHRONOUS);
 			if (err)
 				goto error;
-			for (i = 0; i < nr_bhs; i++)
-				brelse(bhs[i]);
-			nr_bhs = 0;
 		}
 		fat_collect_bhs(bhs, &nr_bhs, &fatent);
 	} while (cluster != FAT_ENT_EOF);
-- 
2.43.0

[PATCH 2/4] fat: return only first cluster when allocating

[Matheus Alves de Almeida]

fat_alloc_clusters() returns every allocated cluster number in an array.
For larger allocations, like growing a file, this array would need to be
very large.

Make fat_alloc_clusters() return only the first allocated cluster in the
chain. Update fat_add_new_entries() to follow the chain when it needs
the second cluster.

Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
---
 fs/fat/dir.c    | 20 +++++++++++++++++++-
 fs/fat/fat.h    |  2 +-
 fs/fat/fatent.c | 17 +++++++++--------
 3 files changed, 29 insertions(+), 10 deletions(-)

diff --git a/fs/fat/dir.c b/fs/fat/dir.c
index 35bdb6294..672d5e392 100644
--- a/fs/fat/dir.c
+++ b/fs/fat/dir.c
@@ -1245,6 +1245,7 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
 	sector_t blknr, start_blknr, last_blknr;
 	unsigned long size, copy;
 	int err, i, n, offset, cluster[2];
+	struct fat_entry fatent;
 
 	/*
 	 * The minimum cluster size is 512bytes, and maximum entry
@@ -1255,10 +1256,26 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
 	*nr_cluster = (size + (sbi->cluster_size - 1)) >> sbi->cluster_bits;
 	BUG_ON(*nr_cluster > 2);
 
-	err = fat_alloc_clusters(dir, cluster, *nr_cluster);
+	err = fat_alloc_clusters(dir, &cluster[0], *nr_cluster);
 	if (err)
 		goto error;
 
+	if (*nr_cluster > 1) {
+		fatent_init(&fatent);
+		cluster[1] = fat_ent_read(dir, &fatent, cluster[0]);
+		fatent_brelse(&fatent);
+		if (cluster[1] == FAT_ENT_EOF || cluster[1] == FAT_ENT_FREE) {
+			fat_fs_error(sb,
+				     "%s: invalid cluster chain (i_pos %lld)",
+				     __func__, MSDOS_I(dir)->i_pos);
+			cluster[1] = -EIO;
+		}
+		if (cluster[1] < 0) {
+			err = cluster[1];
+			goto error_ent;
+		}
+	}
+
 	/*
 	 * First stage: Fill the directory entry.  NOTE: This cluster
 	 * is not referenced from any inode yet, so updates order is
@@ -1313,6 +1330,7 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
 error_nomem:
 	for (i = 0; i < n; i++)
 		bforget(bhs[i]);
+error_ent:
 	fat_free_clusters(dir, cluster[0]);
 error:
 	return err;
diff --git a/fs/fat/fat.h b/fs/fat/fat.h
index 61338413d..75ac0239a 100644
--- a/fs/fat/fat.h
+++ b/fs/fat/fat.h
@@ -393,7 +393,7 @@ extern int fat_ent_read(struct inode *inode, struct fat_entry *fatent,
 			int entry);
 extern int fat_ent_write(struct inode *inode, struct fat_entry *fatent,
 			 int new, int wait);
-extern int fat_alloc_clusters(struct inode *inode, int *cluster,
+extern int fat_alloc_clusters(struct inode *inode, int *first_cluster,
 			      int nr_cluster);
 extern int fat_free_clusters(struct inode *inode, int cluster);
 extern int fat_count_free_clusters(struct super_block *sb);
diff --git a/fs/fat/fatent.c b/fs/fat/fatent.c
index bfab8eab5..4970b1f14 100644
--- a/fs/fat/fatent.c
+++ b/fs/fat/fatent.c
@@ -488,14 +488,14 @@ static int fat_flush_bhs(struct super_block *sb, struct buffer_head **bhs,
 	return 0;
 }
 
-int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
+int fat_alloc_clusters(struct inode *inode, int *first_cluster, int nr_cluster)
 {
 	struct super_block *sb = inode->i_sb;
 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
 	const struct fatent_operations *ops = sbi->fatent_ops;
 	struct fat_entry fatent, prev_ent;
 	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
-	int i, count, err, nr_bhs, idx_clus;
+	int i, count, err, nr_bhs, clusters_done;
 
 	lock_fat(sbi);
 	if (sbi->free_clusters != -1 && sbi->free_clus_valid &&
@@ -504,7 +504,7 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 		return -ENOSPC;
 	}
 
-	err = nr_bhs = idx_clus = 0;
+	err = nr_bhs = clusters_done = 0;
 	count = FAT_START_ENT;
 	fatent_init(&prev_ent);
 	fatent_init(&fatent);
@@ -531,8 +531,9 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 				if (sbi->free_clusters != -1)
 					sbi->free_clusters--;
 
-				cluster[idx_clus] = entry;
-				idx_clus++;
+				if (!clusters_done)
+					*first_cluster = entry;
+				clusters_done++;
 
 				if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
 					err = fat_flush_bhs(sb, bhs, &nr_bhs,
@@ -542,7 +543,7 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 				}
 				fat_collect_bhs(bhs, &nr_bhs, &fatent);
 
-				if (idx_clus == nr_cluster)
+				if (clusters_done == nr_cluster)
 					goto out;
 
 				/*
@@ -575,8 +576,8 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
 	for (i = 0; i < nr_bhs; i++)
 		brelse(bhs[i]);
 
-	if (err && idx_clus)
-		fat_free_clusters(inode, cluster[0]);
+	if (err && clusters_done)
+		fat_free_clusters(inode, *first_cluster);
 
 	return err;
 }
-- 
2.43.0

[PATCH 3/4] fat: support adding multiple clusters

[Matheus Alves de Almeida]

fat_add_cluster() currently adds only 1 cluster to the file's chain.
Implement support for adding more in one call and rename the function
to reflect the new behavior.

Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
---
 fs/fat/fat.h   | 2 +-
 fs/fat/file.c  | 2 +-
 fs/fat/inode.c | 8 ++++----
 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/fs/fat/fat.h b/fs/fat/fat.h
index 75ac0239a..683fb68a7 100644
--- a/fs/fat/fat.h
+++ b/fs/fat/fat.h
@@ -440,7 +440,7 @@ static inline unsigned long fat_dir_hash(int logstart)
 {
 	return hash_32(logstart, FAT_HASH_BITS);
 }
-extern int fat_add_cluster(struct inode *inode);
+extern int fat_add_clusters(struct inode *inode, int nr_cluster);
 
 /* fat/misc.c */
 extern __printf(3, 4) __cold
diff --git a/fs/fat/file.c b/fs/fat/file.c
index 1c835ca5f..41d49e9de 100644
--- a/fs/fat/file.c
+++ b/fs/fat/file.c
@@ -292,7 +292,7 @@ static long fat_fallocate(struct file *file, int mode,
 
 		/* Start the allocation.We are not zeroing out the clusters */
 		while (nr_cluster-- > 0) {
-			err = fat_add_cluster(inode);
+			err = fat_add_clusters(inode, 1);
 			if (err)
 				goto error;
 		}
diff --git a/fs/fat/inode.c b/fs/fat/inode.c
index f775a004c..44fc9b556 100644
--- a/fs/fat/inode.c
+++ b/fs/fat/inode.c
@@ -101,16 +101,16 @@ static struct fat_floppy_defaults {
 },
 };
 
-int fat_add_cluster(struct inode *inode)
+int fat_add_clusters(struct inode *inode, int nr_cluster)
 {
 	int err, cluster;
 
-	err = fat_alloc_clusters(inode, &cluster, 1);
+	err = fat_alloc_clusters(inode, &cluster, nr_cluster);
 	if (err)
 		return err;
 	/* FIXME: this cluster should be added after data of this
 	 * cluster is writed */
-	err = fat_chain_add(inode, cluster, 1);
+	err = fat_chain_add(inode, cluster, nr_cluster);
 	if (err)
 		fat_free_clusters(inode, cluster);
 	return err;
@@ -152,7 +152,7 @@ static inline int __fat_get_block(struct inode *inode, sector_t iblock,
 	 */
 	if (!offset && !(iblock < last_block)) {
 		/* TODO: multiple cluster allocation would be desirable. */
-		err = fat_add_cluster(inode);
+		err = fat_add_clusters(inode, 1);
 		if (err)
 			return err;
 	}
-- 
2.43.0

[PATCH 4/4] fat: allocate multiple clusters in fallocate

[Matheus Alves de Almeida]

The fat_fallocate() code currently does many 1-cluster allocations when
growing a file. Make it allocate everything with one call instead.

Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
---
 fs/fat/file.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/fs/fat/file.c b/fs/fat/file.c
index 41d49e9de..3aa541c6b 100644
--- a/fs/fat/file.c
+++ b/fs/fat/file.c
@@ -290,12 +290,10 @@ static long fat_fallocate(struct file *file, int mode,
 		nr_cluster = (mm_bytes + (sbi->cluster_size - 1)) >>
 			sbi->cluster_bits;
 
-		/* Start the allocation.We are not zeroing out the clusters */
-		while (nr_cluster-- > 0) {
-			err = fat_add_clusters(inode, 1);
-			if (err)
-				goto error;
-		}
+		/* Allocate the clusters. We are not zeroing them out */
+		err = fat_add_clusters(inode, nr_cluster);
+		if (err)
+			goto error;
 	} else {
 		if ((offset + len) <= i_size_read(inode))
 			goto error;
-- 
2.43.0

Re: [PATCH 0/4] fat: allocate multiple clusters in fallocate

[OGAWA Hirofumi]

Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:

> Hi,
>
> This series adds support for allocating multiple clusters in a single
> fat_add_clusters() call in fat_fallocate().
>
> The multi-cluster TODO in inode.c is not implemented, as doing so would
> require speculative preallocation or an iomap conversion.

Is this to improve the performance of fallocate? If so, what the number
by improved bench or such?

> Matheus Alves de Almeida (4):
>   fat: remove cluster allocation size limit
>   fat: return only first cluster when allocating
>   fat: support adding multiple clusters
>   fat: allocate multiple clusters in fallocate
>
>  fs/fat/dir.c    | 20 +++++++++++++++-
>  fs/fat/fat.h    |  4 ++--
>  fs/fat/fatent.c | 61 ++++++++++++++++++++++++++++++++-----------------
>  fs/fat/file.c   | 10 ++++----
>  fs/fat/inode.c  |  8 +++----
>  5 files changed, 69 insertions(+), 34 deletions(-)

-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH 2/4] fat: return only first cluster when allocating

[OGAWA Hirofumi]

Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:

> fat_alloc_clusters() returns every allocated cluster number in an array.
> For larger allocations, like growing a file, this array would need to be
> very large.
>
> Make fat_alloc_clusters() return only the first allocated cluster in the
> chain. Update fat_add_new_entries() to follow the chain when it needs
> the second cluster.

This would be more common case than fallocate(), so penalize this part
would not be good.

Thanks.

> Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
> ---
>  fs/fat/dir.c    | 20 +++++++++++++++++++-
>  fs/fat/fat.h    |  2 +-
>  fs/fat/fatent.c | 17 +++++++++--------
>  3 files changed, 29 insertions(+), 10 deletions(-)
>
> diff --git a/fs/fat/dir.c b/fs/fat/dir.c
> index 35bdb6294..672d5e392 100644
> --- a/fs/fat/dir.c
> +++ b/fs/fat/dir.c
> @@ -1245,6 +1245,7 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
>  	sector_t blknr, start_blknr, last_blknr;
>  	unsigned long size, copy;
>  	int err, i, n, offset, cluster[2];
> +	struct fat_entry fatent;
>  
>  	/*
>  	 * The minimum cluster size is 512bytes, and maximum entry
> @@ -1255,10 +1256,26 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
>  	*nr_cluster = (size + (sbi->cluster_size - 1)) >> sbi->cluster_bits;
>  	BUG_ON(*nr_cluster > 2);
>  
> -	err = fat_alloc_clusters(dir, cluster, *nr_cluster);
> +	err = fat_alloc_clusters(dir, &cluster[0], *nr_cluster);
>  	if (err)
>  		goto error;
>  
> +	if (*nr_cluster > 1) {
> +		fatent_init(&fatent);
> +		cluster[1] = fat_ent_read(dir, &fatent, cluster[0]);
> +		fatent_brelse(&fatent);
> +		if (cluster[1] == FAT_ENT_EOF || cluster[1] == FAT_ENT_FREE) {
> +			fat_fs_error(sb,
> +				     "%s: invalid cluster chain (i_pos %lld)",
> +				     __func__, MSDOS_I(dir)->i_pos);
> +			cluster[1] = -EIO;
> +		}
> +		if (cluster[1] < 0) {
> +			err = cluster[1];
> +			goto error_ent;
> +		}
> +	}
> +
>  	/*
>  	 * First stage: Fill the directory entry.  NOTE: This cluster
>  	 * is not referenced from any inode yet, so updates order is
> @@ -1313,6 +1330,7 @@ static int fat_add_new_entries(struct inode *dir, void *slots, int nr_slots,
>  error_nomem:
>  	for (i = 0; i < n; i++)
>  		bforget(bhs[i]);
> +error_ent:
>  	fat_free_clusters(dir, cluster[0]);
>  error:
>  	return err;
> diff --git a/fs/fat/fat.h b/fs/fat/fat.h
> index 61338413d..75ac0239a 100644
> --- a/fs/fat/fat.h
> +++ b/fs/fat/fat.h
> @@ -393,7 +393,7 @@ extern int fat_ent_read(struct inode *inode, struct fat_entry *fatent,
>  			int entry);
>  extern int fat_ent_write(struct inode *inode, struct fat_entry *fatent,
>  			 int new, int wait);
> -extern int fat_alloc_clusters(struct inode *inode, int *cluster,
> +extern int fat_alloc_clusters(struct inode *inode, int *first_cluster,
>  			      int nr_cluster);
>  extern int fat_free_clusters(struct inode *inode, int cluster);
>  extern int fat_count_free_clusters(struct super_block *sb);
> diff --git a/fs/fat/fatent.c b/fs/fat/fatent.c
> index bfab8eab5..4970b1f14 100644
> --- a/fs/fat/fatent.c
> +++ b/fs/fat/fatent.c
> @@ -488,14 +488,14 @@ static int fat_flush_bhs(struct super_block *sb, struct buffer_head **bhs,
>  	return 0;
>  }
>  
> -int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
> +int fat_alloc_clusters(struct inode *inode, int *first_cluster, int nr_cluster)
>  {
>  	struct super_block *sb = inode->i_sb;
>  	struct msdos_sb_info *sbi = MSDOS_SB(sb);
>  	const struct fatent_operations *ops = sbi->fatent_ops;
>  	struct fat_entry fatent, prev_ent;
>  	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
> -	int i, count, err, nr_bhs, idx_clus;
> +	int i, count, err, nr_bhs, clusters_done;
>  
>  	lock_fat(sbi);
>  	if (sbi->free_clusters != -1 && sbi->free_clus_valid &&
> @@ -504,7 +504,7 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
>  		return -ENOSPC;
>  	}
>  
> -	err = nr_bhs = idx_clus = 0;
> +	err = nr_bhs = clusters_done = 0;
>  	count = FAT_START_ENT;
>  	fatent_init(&prev_ent);
>  	fatent_init(&fatent);
> @@ -531,8 +531,9 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
>  				if (sbi->free_clusters != -1)
>  					sbi->free_clusters--;
>  
> -				cluster[idx_clus] = entry;
> -				idx_clus++;
> +				if (!clusters_done)
> +					*first_cluster = entry;
> +				clusters_done++;
>  
>  				if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
>  					err = fat_flush_bhs(sb, bhs, &nr_bhs,
> @@ -542,7 +543,7 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
>  				}
>  				fat_collect_bhs(bhs, &nr_bhs, &fatent);
>  
> -				if (idx_clus == nr_cluster)
> +				if (clusters_done == nr_cluster)
>  					goto out;
>  
>  				/*
> @@ -575,8 +576,8 @@ int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
>  	for (i = 0; i < nr_bhs; i++)
>  		brelse(bhs[i]);
>  
> -	if (err && idx_clus)
> -		fat_free_clusters(inode, cluster[0]);
> +	if (err && clusters_done)
> +		fat_free_clusters(inode, *first_cluster);
>  
>  	return err;
>  }

-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH 0/4] fat: allocate multiple clusters in fallocate

[Matheus Alves de Almeida]

Em 2026-10-11 15:55, OGAWA Hirofumi escreveu:
> Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:
> 
>> Hi,

>> This series adds support for allocating multiple clusters in a single
>> fat_add_clusters() call in fat_fallocate().

>> The multi-cluster TODO in inode.c is not implemented, as doing so would
>> require speculative preallocation or an iomap conversion.

> Is this to improve the performance of fallocate? If so, what the number
> by improved bench or such?

Yes, it is. I ran a few benchmarks. Each run used a freshly formatted
filesystem, with no userspace processes other than init (which is the
benchmark program in this case).

The numbers below are the arithmetic mean of the samples, with
improvement calculated as before / after. The times are for the complete
loop and not an individual fallocate() call.

The benchmarks were run under QEMU/KVM with a virtio-blk device using
cache=none.

start = now_ns();
for (unsigned int i = 0; i < count; i++)
     fallocate(fds[i], FALLOC_FL_KEEP_SIZE, 0, bytes);
elapsed = now_ns() - start;

FAT32 with 512-byte clusters using count=16 files:
length    mounted sync?    before    after    improvement    samples
256MiB    no               2.328s    0.175s   13.2x          10
16MiB     no               149.659ms 14.036ms 10.7x          10
16MiB     yes              747.993s  3.445s   217.1x         3*
1MiB      yes              46.63s    0.333s   140.1x         10

FAT32 with 512-byte clusters using count=128 files:
length    mounted sync?    before    after    improvement    samples
1MiB      no               90.873ms  4.686ms  19.4x          10
16KiB     no               1.287ms   0.241ms  5.3x           10
128KiB    yes              47.284s   0.350s   135x           10
4KiB      yes              1.98s     0.144s   13.7x          10

FAT32 with 4096-byte clusters using count=16 files:
length    mounted sync?    before    after    improvement    samples
256MiB    no               295.392ms 24.733ms 11.9x          10
16MiB     no               20.509ms  1.404ms  14.6x          10
16MiB     yes              92.489s   0.348s   265.4x         10
1MiB      yes              5.837s    0.048s   121.3x         10

* it would take a lot of time to take 10 samples like the others,
   so I only took 3 here.

The improvement is large because the old fallocate path allocates one
cluster at a time, while the new path can allocate an entire chain in
one call. This is especially visible on synchronous mounts, where the
new code can batch FAT updates instead of synchronously handling each
cluster allocation separately.

Thanks,
Matheus

>> Matheus Alves de Almeida (4):
>>  fat: remove cluster allocation size limit
>>  fat: return only first cluster when allocating
>>  fat: support adding multiple clusters
>>  fat: allocate multiple clusters in fallocate
>> 
>> fs/fat/dir.c    | 20 +++++++++++++++-
>> fs/fat/fat.h    |  4 ++--
>> fs/fat/fatent.c | 61 ++++++++++++++++++++++++++++++++-----------------
>> fs/fat/file.c   | 10 ++++----
>> fs/fat/inode.c  |  8 +++----
>> 5 files changed, 69 insertions(+), 34 deletions(-)

Re: [PATCH 2/4] fat: return only first cluster when allocating

[Matheus Alves de Almeida]

Em 2026-10-11 15:57, OGAWA Hirofumi escreveu:
> Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:
> 
>> fat_alloc_clusters() returns every allocated cluster number in an array.
>> For larger allocations, like growing a file, this array would need to be
>> very large.
>> 
>> Make fat_alloc_clusters() return only the first allocated cluster in the
>> chain. Update fat_add_new_entries() to follow the chain when it needs
>> the second cluster.
> 
> This would be more common case than fallocate(), so penalize this part
> would not be good.
> 
> Thanks.

That makes sense.

I can change the approach so that fat_alloc_clusters() and the directory
entry path are left unchanged. For fat_add_clusters(), I would add a
separate fat_alloc_chain() helper which allocates the whole chain but
only returns the first cluster.

Would that approach be preferable?

Thanks,
Matheus

>> Signed-off-by: Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br>
>> ---
>>  fs/fat/dir.c    | 20 +++++++++++++++++++-
>>  fs/fat/fat.h    |  2 +-
>>  fs/fat/fatent.c | 17 +++++++++--------
>>  3 files changed, 29 insertions(+), 10 deletions(-)
>> 
>> diff --git a/fs/fat/dir.c b/fs/fat/dir.c
>> index 35bdb6294..672d5e392 100644
>> --- a/fs/fat/dir.c
>> +++ b/fs/fat/dir.c
>> @@ -1245,6 +1245,7 @@ static int fat_add_new_entries(struct inode *dir, 
>> void *slots, int nr_slots,
>>  	sector_t blknr, start_blknr, last_blknr;
>>  	unsigned long size, copy;
>>  	int err, i, n, offset, cluster[2];
>> +	struct fat_entry fatent;
>> 
>>  	/*
>>  	 * The minimum cluster size is 512bytes, and maximum entry
>> @@ -1255,10 +1256,26 @@ static int fat_add_new_entries(struct inode *dir, 
>> void *slots, int nr_slots,
>>  	*nr_cluster = (size + (sbi->cluster_size - 1)) >> sbi->cluster_bits;
>>  	BUG_ON(*nr_cluster > 2);
>> 
>> -	err = fat_alloc_clusters(dir, cluster, *nr_cluster);
>> +	err = fat_alloc_clusters(dir, &cluster[0], *nr_cluster);
>>  	if (err)
>>  		goto error;
>> 
>> +	if (*nr_cluster > 1) {
>> +		fatent_init(&fatent);
>> +		cluster[1] = fat_ent_read(dir, &fatent, cluster[0]);
>> +		fatent_brelse(&fatent);
>> +		if (cluster[1] == FAT_ENT_EOF || cluster[1] == FAT_ENT_FREE) {
>> +			fat_fs_error(sb,
>> +				     "%s: invalid cluster chain (i_pos %lld)",
>> +				     __func__, MSDOS_I(dir)->i_pos);
>> +			cluster[1] = -EIO;
>> +		}
>> +		if (cluster[1] < 0) {
>> +			err = cluster[1];
>> +			goto error_ent;
>> +		}
>> +	}
>> +
>>  	/*
>>  	 * First stage: Fill the directory entry.  NOTE: This cluster
>>  	 * is not referenced from any inode yet, so updates order is
>> @@ -1313,6 +1330,7 @@ static int fat_add_new_entries(struct inode *dir, 
>> void *slots, int nr_slots,
>>  error_nomem:
>>  	for (i = 0; i < n; i++)
>>  		bforget(bhs[i]);
>> +error_ent:
>>  	fat_free_clusters(dir, cluster[0]);
>>  error:
>>  	return err;
>> diff --git a/fs/fat/fat.h b/fs/fat/fat.h
>> index 61338413d..75ac0239a 100644
>> --- a/fs/fat/fat.h
>> +++ b/fs/fat/fat.h
>> @@ -393,7 +393,7 @@ extern int fat_ent_read(struct inode *inode, struct 
>> fat_entry *fatent,
>>  			int entry);
>>  extern int fat_ent_write(struct inode *inode, struct fat_entry *fatent,
>>  			 int new, int wait);
>> -extern int fat_alloc_clusters(struct inode *inode, int *cluster,
>> +extern int fat_alloc_clusters(struct inode *inode, int *first_cluster,
>>  			      int nr_cluster);
>>  extern int fat_free_clusters(struct inode *inode, int cluster);
>>  extern int fat_count_free_clusters(struct super_block *sb);
>> diff --git a/fs/fat/fatent.c b/fs/fat/fatent.c
>> index bfab8eab5..4970b1f14 100644
>> --- a/fs/fat/fatent.c
>> +++ b/fs/fat/fatent.c
>> @@ -488,14 +488,14 @@ static int fat_flush_bhs(struct super_block *sb, 
>> struct buffer_head **bhs,
>>  	return 0;
>>  }
>> 
>> -int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
>> +int fat_alloc_clusters(struct inode *inode, int *first_cluster, int 
>> nr_cluster)
>>  {
>>  	struct super_block *sb = inode->i_sb;
>>  	struct msdos_sb_info *sbi = MSDOS_SB(sb);
>>  	const struct fatent_operations *ops = sbi->fatent_ops;
>>  	struct fat_entry fatent, prev_ent;
>>  	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
>> -	int i, count, err, nr_bhs, idx_clus;
>> +	int i, count, err, nr_bhs, clusters_done;
>> 
>>  	lock_fat(sbi);
>>  	if (sbi->free_clusters != -1 && sbi->free_clus_valid &&
>> @@ -504,7 +504,7 @@ int fat_alloc_clusters(struct inode *inode, int 
>> *cluster, int nr_cluster)
>>  		return -ENOSPC;
>>  	}
>> 
>> -	err = nr_bhs = idx_clus = 0;
>> +	err = nr_bhs = clusters_done = 0;
>>  	count = FAT_START_ENT;
>>  	fatent_init(&prev_ent);
>>  	fatent_init(&fatent);
>> @@ -531,8 +531,9 @@ int fat_alloc_clusters(struct inode *inode, int 
>> *cluster, int nr_cluster)
>>  				if (sbi->free_clusters != -1)
>>  					sbi->free_clusters--;
>> 
>> -				cluster[idx_clus] = entry;
>> -				idx_clus++;
>> +				if (!clusters_done)
>> +					*first_cluster = entry;
>> +				clusters_done++;
>> 
>>  				if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
>>  					err = fat_flush_bhs(sb, bhs, &nr_bhs,
>> @@ -542,7 +543,7 @@ int fat_alloc_clusters(struct inode *inode, int 
>> *cluster, int nr_cluster)
>>  				}
>>  				fat_collect_bhs(bhs, &nr_bhs, &fatent);
>> 
>> -				if (idx_clus == nr_cluster)
>> +				if (clusters_done == nr_cluster)
>>  					goto out;
>> 
>>  				/*
>> @@ -575,8 +576,8 @@ int fat_alloc_clusters(struct inode *inode, int 
>> *cluster, int nr_cluster)
>>  	for (i = 0; i < nr_bhs; i++)
>>  		brelse(bhs[i]);
>> 
>> -	if (err && idx_clus)
>> -		fat_free_clusters(inode, cluster[0]);
>> +	if (err && clusters_done)
>> +		fat_free_clusters(inode, *first_cluster);
>> 
>>  	return err;
>>  }

Re: [PATCH 0/4] fat: allocate multiple clusters in fallocate

[OGAWA Hirofumi]

Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:

> Em 2026-10-11 15:55, OGAWA Hirofumi escreveu:
>> Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:
>> 
>>> Hi,
>
>>> This series adds support for allocating multiple clusters in a single
>>> fat_add_clusters() call in fat_fallocate().
>
>>> The multi-cluster TODO in inode.c is not implemented, as doing so would
>>> require speculative preallocation or an iomap conversion.
>
>> Is this to improve the performance of fallocate? If so, what the number
>> by improved bench or such?
>
> Yes, it is. I ran a few benchmarks. Each run used a freshly formatted
> filesystem, with no userspace processes other than init (which is the
> benchmark program in this case).
>
> The numbers below are the arithmetic mean of the samples, with
> improvement calculated as before / after. The times are for the complete
> loop and not an individual fallocate() call.
>
> The benchmarks were run under QEMU/KVM with a virtio-blk device using
> cache=none.
>
> start = now_ns();
> for (unsigned int i = 0; i < count; i++)
>      fallocate(fds[i], FALLOC_FL_KEEP_SIZE, 0, bytes);
> elapsed = now_ns() - start;
>
> FAT32 with 512-byte clusters using count=16 files:
> length    mounted sync?    before    after    improvement    samples
> 256MiB    no               2.328s    0.175s   13.2x          10
> 16MiB     no               149.659ms 14.036ms 10.7x          10
> 16MiB     yes              747.993s  3.445s   217.1x         3*
> 1MiB      yes              46.63s    0.333s   140.1x         10
>
> FAT32 with 512-byte clusters using count=128 files:
> length    mounted sync?    before    after    improvement    samples
> 1MiB      no               90.873ms  4.686ms  19.4x          10
> 16KiB     no               1.287ms   0.241ms  5.3x           10
> 128KiB    yes              47.284s   0.350s   135x           10
> 4KiB      yes              1.98s     0.144s   13.7x          10
>
> FAT32 with 4096-byte clusters using count=16 files:
> length    mounted sync?    before    after    improvement    samples
> 256MiB    no               295.392ms 24.733ms 11.9x          10
> 16MiB     no               20.509ms  1.404ms  14.6x          10
> 16MiB     yes              92.489s   0.348s   265.4x         10
> 1MiB      yes              5.837s    0.048s   121.3x         10
>
> * it would take a lot of time to take 10 samples like the others,
>    so I only took 3 here.
>
> The improvement is large because the old fallocate path allocates one
> cluster at a time, while the new path can allocate an entire chain in
> one call. This is especially visible on synchronous mounts, where the
> new code can batch FAT updates instead of synchronously handling each
> cluster allocation separately.

Thank you. Please add it to the commit log too.

> Thanks,
> Matheus
>
>>> Matheus Alves de Almeida (4):
>>>  fat: remove cluster allocation size limit
>>>  fat: return only first cluster when allocating
>>>  fat: support adding multiple clusters
>>>  fat: allocate multiple clusters in fallocate
>>> 
>>> fs/fat/dir.c    | 20 +++++++++++++++-
>>> fs/fat/fat.h    |  4 ++--
>>> fs/fat/fatent.c | 61 ++++++++++++++++++++++++++++++++-----------------
>>> fs/fat/file.c   | 10 ++++----
>>> fs/fat/inode.c  |  8 +++----
>>> 5 files changed, 69 insertions(+), 34 deletions(-)
>

-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

Re: [PATCH 2/4] fat: return only first cluster when allocating

[OGAWA Hirofumi]

Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:

> Em 2026-10-11 15:57, OGAWA Hirofumi escreveu:
>> Matheus Alves de Almeida <matheus.aalmeida@inf.ufrgs.br> writes:
>> 
>>> fat_alloc_clusters() returns every allocated cluster number in an array.
>>> For larger allocations, like growing a file, this array would need to be
>>> very large.
>>> 
>>> Make fat_alloc_clusters() return only the first allocated cluster in the
>>> chain. Update fat_add_new_entries() to follow the chain when it needs
>>> the second cluster.
>> 
>> This would be more common case than fallocate(), so penalize this part
>> would not be good.
>> 
>> Thanks.
>
> That makes sense.
>
> I can change the approach so that fat_alloc_clusters() and the directory
> entry path are left unchanged. For fat_add_clusters(), I would add a
> separate fat_alloc_chain() helper which allocates the whole chain but
> only returns the first cluster.
>
> Would that approach be preferable?

Sounds good if both share the almost all codes.

Thanks.
-- 
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>