[PATCH 0/3 ver. 7] Ext3/Ext4 Batched discard support

[PATCH 0/3 ver. 7] Ext3/Ext4 Batched discard support

[Lukas Czerner]

Hi all,

this is "hopefully" the final version of the patch set, since it looks like
everyone agree with this. Since the last version some simple fixes was done.

- As Jan noticed it should subtract the s_first_data_block before modulo when
computing the group starting block.
- As Dimitry proposed cond_reshed() is really useless in the ext4_trim_extent
and rescheduling should be done in the ext4_trim_all_free.

Also from previous version it supports "partial" fs discard see [PATCH 1/3].

The patch set consist of these three patches. Second and third patch are
independent on each other and dependent on the first patch.

[PATCH 1/3] Add ioctl FITRIM.
[PATCH 2/3] Add batched discard support for ext3
[PATCH 3/3] Add batched discard support for ext4

Regards
-Lukas

---
 fs/ext3/balloc.c        |  250 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 fs/ext4/ext4.h          |    2 +
 fs/ext4/mballoc.c       |  200 +++++++++++++++++++++++++++++++++++++
 fs/ext4/super.c         |    1 +
 fs/ioctl.c              |   34 +++++++
 include/linux/ext3_fs.h |    1 +
 include/linux/fs.h      |    2 +
 8 files changed, 491 insertions(+), 0 deletions(-)

[PATCH 1/3] Add ioctl FITRIM.

[Lukas Czerner]

Adds an filesystem independent ioctl to allow implementation of file
system batched discard support. It takes an array of three uint64_t
as an argument, the meaning of each item is as follows:

array[0] - (start) first Byte to trim
array[1] - (len) number of Bytes to trim from start
array[2] - (minlen) minimum extent length to trim, free extents shorter
than this number of Bytes will be ignored. This number will be rounded
up to the block size.

It is also possible to specify NULL as an argument. In this case the
arguments will set itself as follows:

args[0] = 0;
args[1] = ULLONG_MAX;
args[2] = 0;

So it will trim the whole file system at one run.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Reviewed-by: Dmitry Monakhov <dmonakhov@openvz.org>
---
 fs/ioctl.c         |   34 ++++++++++++++++++++++++++++++++++
 include/linux/fs.h |    2 ++
 2 files changed, 36 insertions(+), 0 deletions(-)

diff --git a/fs/ioctl.c b/fs/ioctl.c
index 2d140a7..a0e243c 100644
--- a/fs/ioctl.c
+++ b/fs/ioctl.c
@@ -540,6 +540,36 @@ static int ioctl_fsthaw(struct file *filp)
 	return thaw_super(sb);
 }
 
+static int ioctl_fstrim(struct file *filp, void __user *argp)
+{
+	struct super_block *sb = filp->f_path.dentry->d_inode->i_sb;
+	uint64_t args[3];
+	int err;
+
+	if (!capable(CAP_SYS_ADMIN))
+		return -EPERM;
+
+	/* If filesystem doesn't support trim feature, return. */
+	if (sb->s_op->trim_fs == NULL)
+		return -EOPNOTSUPP;
+
+	/* If a blockdevice-backed filesystem isn't specified, return EINVAL. */
+	if (sb->s_bdev == NULL)
+		return -EINVAL;
+
+	if (argp == NULL) {
+		args[0] = 0;
+		args[1] = ULLONG_MAX;
+		args[2] = 0;
+	} else if (copy_from_user(args, argp, sizeof(args)))
+		return -EFAULT;
+
+	err = sb->s_op->trim_fs(sb, args[0], args[1], args[2]);
+	if (err)
+		return err;
+	return 0;
+}
+
 /*
  * When you add any new common ioctls to the switches above and below
  * please update compat_sys_ioctl() too.
@@ -590,6 +620,10 @@ int do_vfs_ioctl(struct file *filp, unsigned int fd, unsigned int cmd,
 		error = ioctl_fsthaw(filp);
 		break;
 
+	case FITRIM:
+		error = ioctl_fstrim(filp, argp);
+		break;
+
 	case FS_IOC_FIEMAP:
 		return ioctl_fiemap(filp, arg);
 
diff --git a/include/linux/fs.h b/include/linux/fs.h
index e5106e4..0cc196f 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -316,6 +316,7 @@ struct inodes_stat_t {
 #define FIGETBSZ   _IO(0x00,2)	/* get the block size used for bmap */
 #define FIFREEZE	_IOWR('X', 119, int)	/* Freeze */
 #define FITHAW		_IOWR('X', 120, int)	/* Thaw */
+#define FITRIM		_IOW('X', 121, uint64_t)/* Trim */
 
 #define	FS_IOC_GETFLAGS			_IOR('f', 1, long)
 #define	FS_IOC_SETFLAGS			_IOW('f', 2, long)
@@ -1582,6 +1583,7 @@ struct super_operations {
 	ssize_t (*quota_write)(struct super_block *, int, const char *, size_t, loff_t);
 #endif
 	int (*bdev_try_to_free_page)(struct super_block*, struct page*, gfp_t);
+	int (*trim_fs) (struct super_block *, uint64_t, uint64_t, uint64_t);
 };
 
 /*
-- 
1.7.2.1

[PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

Walk through allocation groups and trim all free extents. It can be
invoked through FITRIM ioctl on the file system. The main idea is to
provide a way to trim the whole file system if needed, since some SSD's
may suffer from performance loss after the whole device was filled (it
does not mean that fs is full!).

It search for free extents in allocation groups specified by Byte range
start -> start+len. When the free extent is within this range, blocks are
marked as used and then trimmed. Afterwards these blocks are marked as
free in per-group bitmap.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Reviewed-by: Jan Kara <jack@suse.cz>
Reviewed-by: Dmitry Monakhov <dmonakhov@openvz.org>
---
 fs/ext3/balloc.c        |  250 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 include/linux/ext3_fs.h |    1 +
 3 files changed, 252 insertions(+), 0 deletions(-)

diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index 4a32511..2e3f291 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -20,6 +20,7 @@
 #include <linux/ext3_jbd.h>
 #include <linux/quotaops.h>
 #include <linux/buffer_head.h>
+#include <linux/blkdev.h>
 
 /*
  * balloc.c contains the blocks allocation and deallocation routines
@@ -1882,3 +1883,252 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
 	return ext3_bg_num_gdb_meta(sb,group);
 
 }
+
+/**
+ * ext3_trim_all_free -- function to trim all free space in alloc. group
+ * @sb:			super block for file system
+ * @group:		allocation group to trim
+ * @start:		first group block to examine
+ * @max:		last group block to examine
+ * @gdp:		allocation group description structure
+ * @minblocks:		minimum extent block count
+ *
+ * ext3_trim_all_free walks through group's block bitmap searching for free
+ * blocks. When the free block is found, it tries to allocate this block and
+ * consequent free block to get the biggest free extent possible, until it
+ * reaches any used block. Then issue a TRIM command on this extent and free
+ * the extent in the block bitmap. This is done until whole group is scanned.
+ */
+ext3_grpblk_t ext3_trim_all_free(struct super_block *sb, unsigned int group,
+				ext3_grpblk_t start, ext3_grpblk_t max,
+				ext3_grpblk_t minblocks)
+{
+	handle_t *handle;
+	ext3_grpblk_t next, count = 0, bit;
+	struct ext3_sb_info *sbi;
+	ext3_fsblk_t discard_block;
+	struct buffer_head *bitmap_bh = NULL;
+	struct buffer_head *gdp_bh;
+	ext3_grpblk_t free_blocks;
+	struct ext3_group_desc *gdp;
+	int err = 0, ret = 0;
+	ext3_grpblk_t freed;
+
+	/*
+	 * We will update one block bitmap, and one group descriptor
+	 */
+	handle = ext3_journal_start_sb(sb, 2);
+	if (IS_ERR(handle)) {
+		err = PTR_ERR(handle);
+		return err;
+	}
+
+	bitmap_bh = read_block_bitmap(sb, group);
+	if (!bitmap_bh)
+		goto err_out;
+
+	BUFFER_TRACE(bitmap_bh, "getting undo access");
+	err = ext3_journal_get_undo_access(handle, bitmap_bh);
+	if (err)
+		goto err_out;
+
+	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
+	if (!gdp)
+		goto err_out;
+
+	BUFFER_TRACE(gdp_bh, "get_write_access");
+	err = ext3_journal_get_write_access(handle, gdp_bh);
+	if (err)
+		goto err_out;
+
+	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+	sbi = EXT3_SB(sb);
+
+	 /* Walk through the whole group */
+	while (start < max) {
+
+		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
+		if (start < 0)
+			break;
+		next = start;
+
+		/*
+		 * Allocate contiguous free extents by setting bits in the
+		 * block bitmap
+		 */
+		while (next < max
+			&& claim_block(sb_bgl_lock(sbi, group),
+					next, bitmap_bh)) {
+			next++;
+		}
+
+		 /* We did not claim any blocks */
+		if (next == start)
+			continue;
+
+		discard_block = (ext3_fsblk_t)start +
+				ext3_group_first_block_no(sb, group);
+
+		/* Update counters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
+
+		/* Do not issue a TRIM on extents smaller than minblocks */
+		if ((next - start) < minblocks)
+			goto free_extent;
+
+		 /* Send the TRIM command down to the device */
+		ret = sb_issue_discard(sb, discard_block, next - start);
+		count += (next - start);
+
+free_extent:
+		freed = 0;
+
+		/*
+		 * Clear bits in the bitmap
+		 */
+		for (bit = start; bit < next; bit++) {
+			BUFFER_TRACE(bitmap_bh, "clear bit");
+			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
+						bit, bitmap_bh->b_data)) {
+				ext3_error(sb, __func__,
+					"bit already cleared for block "E3FSBLK,
+					 (unsigned long)bit);
+				BUFFER_TRACE(bitmap_bh, "bit already cleared");
+			} else {
+				freed++;
+			}
+		}
+
+		/* Update couters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
+
+		start = next;
+
+		if (ret < 0) {
+			if (ret == -EOPNOTSUPP) {
+				ext3_warning(sb, __func__,
+					"discard not supported!");
+				count = ret;
+				break;
+			}
+			err = ret;
+			break;
+		}
+
+		if (signal_pending(current)) {
+			count = -ERESTARTSYS;
+			break;
+		}
+
+		cond_resched();
+
+		/* No more suitable extents */
+		if ((free_blocks - count) < minblocks)
+			break;
+	}
+
+	/* We dirtied the bitmap block */
+	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
+	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
+
+	/* And the group descriptor block */
+	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
+	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
+	if (!err)
+		err = ret;
+
+	ext3_debug("trimmed %d blocks in the group %d\n",
+		count, group);
+
+err_out:
+	if (err) {
+		ext3_std_error(sb, err);
+		count = err;
+	}
+
+	ext3_journal_stop(handle);
+	brelse(bitmap_bh);
+
+	return count;
+}
+
+/**
+ * ext3_trim_fs() -- trim ioctl handle function
+ * @sb:			superblock for filesystem
+ * @start:		First Byte to trim
+ * @len:		number of Bytes to trim from start
+ * @minlen:		minimum extent length in Bytes
+ *
+ * ext3_trim_fs goes through all allocation groups containing Bytes from
+ * start to start+len. For each such a group ext3_trim_all_free function
+ * is invoked to trim all free space.
+ */
+int ext3_trim_fs(struct super_block *sb, uint64_t start, uint64_t len,
+		uint64_t minlen)
+{
+	ext3_grpblk_t last_block, first_block, free_blocks;
+	unsigned long long first_group, last_group;
+	unsigned long group, ngroups;
+	struct ext3_group_desc *gdp;
+	struct ext3_super_block *es;
+	int ret = 0;
+
+	start >>= sb->s_blocksize_bits;
+	len >>= sb->s_blocksize_bits;
+	minlen >>= sb->s_blocksize_bits;
+
+	if (unlikely(minlen > EXT3_BLOCKS_PER_GROUP(sb)))
+		return -EINVAL;
+
+	es = EXT3_SB(sb)->s_es;
+	ngroups = EXT3_SB(sb)->s_groups_count;
+	smp_rmb();
+
+	/* Determine first and last group to examine based on start and len */
+	first_group = (start - le32_to_cpu(es->s_first_data_block)) /
+		      EXT3_BLOCKS_PER_GROUP(sb);
+	last_group = (start + len - le32_to_cpu(es->s_first_data_block)) /
+		     EXT3_BLOCKS_PER_GROUP(sb);
+	last_group = (last_group > ngroups - 1) ? ngroups - 1 : last_group;
+
+	if (first_group > last_group)
+		return -EINVAL;
+
+	first_block = (start - le32_to_cpu(es->s_first_data_block)) %
+			EXT3_BLOCKS_PER_GROUP(sb);
+	last_block = EXT3_BLOCKS_PER_GROUP(sb);
+
+	for (group = first_group; group <= last_group; group++) {
+
+		gdp = ext3_get_group_desc(sb, group, NULL);
+		if (!gdp)
+			break;
+
+		free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+		if (free_blocks < minlen)
+			continue;
+
+		if (len >= EXT3_BLOCKS_PER_GROUP(sb))
+			len -= (EXT3_BLOCKS_PER_GROUP(sb) - first_block);
+		else
+			last_block = len;
+
+		ret = ext3_trim_all_free(sb, group, first_block,
+					last_block, minlen);
+		if (ret < 0)
+			break;
+
+		first_block = 0;
+	}
+
+	if (ret >= 0)
+		ret = 0;
+
+	return ret;
+}
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 6c953bb..b172c88 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -797,6 +797,7 @@ static const struct super_operations ext3_sops = {
 	.quota_write	= ext3_quota_write,
 #endif
 	.bdev_try_to_free_page = bdev_try_to_free_page,
+	.trim_fs	= ext3_trim_fs,
 };
 
 static const struct export_operations ext3_export_ops = {
diff --git a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
index 7fc62d4..9afacd4 100644
--- a/include/linux/ext3_fs.h
+++ b/include/linux/ext3_fs.h
@@ -857,6 +857,7 @@ extern struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
 extern int ext3_should_retry_alloc(struct super_block *sb, int *retries);
 extern void ext3_init_block_alloc_info(struct inode *);
 extern void ext3_rsv_window_add(struct super_block *sb, struct ext3_reserve_window_node *rsv);
+extern int ext3_trim_fs(struct super_block *, uint64_t, uint64_t, uint64_t);
 
 /* dir.c */
 extern int ext3_check_dir_entry(const char *, struct inode *,
-- 
1.7.2.1

[PATCH 3/3] Add batched discard support for ext4

[Lukas Czerner]

Walk through allocation groups and trim all free extents. It can be
invoked through FITRIM ioctl on the file system. The main idea is to
provide a way to trim the whole file system if needed, since some SSD's
may suffer from performance loss after the whole device was filled (it
does not mean that fs is full!).

It search for free extents in allocation groups specified by Byte range
start -> start+len. When the free extent is within this range, blocks
are marked as used and then trimmed. Afterwards these blocks are marked
as free in per-group bitmap.

Since fstrim is a long operation it is good to have an ability to
interrupt it by a signal. This was added by Dmitry Monakhov.
Thanks Dimitry.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: Dmitry Monakhov <dmonakhov@openvz.org>
Reviewed-by: Jan Kara <jack@suse.cz>
Reviewed-by: Dmitry Monakhov <dmonakhov@openvz.org>
---
 fs/ext4/ext4.h    |    2 +
 fs/ext4/mballoc.c |  200 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext4/super.c   |    1 +
 3 files changed, 203 insertions(+), 0 deletions(-)

diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 19a4de5..2f96dc5 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1558,6 +1558,8 @@ extern int ext4_mb_add_groupinfo(struct super_block *sb,
 extern int ext4_mb_get_buddy_cache_lock(struct super_block *, ext4_group_t);
 extern void ext4_mb_put_buddy_cache_lock(struct super_block *,
 						ext4_group_t, int);
+extern int ext4_trim_fs(struct super_block *, uint64_t, uint64_t, uint64_t);
+
 /* inode.c */
 struct buffer_head *ext4_getblk(handle_t *, struct inode *,
 						ext4_lblk_t, int, int *);
diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 0e83dfd..4c4132b 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -4690,3 +4690,203 @@ error_return:
 		kmem_cache_free(ext4_ac_cachep, ac);
 	return;
 }
+
+/**
+ * ext4_trim_extent -- function to TRIM one single free extent in the group
+ * @sb:		super block for the file system
+ * @start:	starting block of the free extent in the alloc. group
+ * @count:	number of blocks to TRIM
+ * @group:	alloc. group we are working with
+ * @e4b:	ext4 buddy for the group
+ *
+ * Trim "count" blocks starting at "start" in the "group". To assure that no
+ * one will allocate those blocks, mark it as used in buddy bitmap. This must
+ * be called with under the group lock.
+ */
+static int ext4_trim_extent(struct super_block *sb, int start, int count,
+		ext4_group_t group, struct ext4_buddy *e4b)
+{
+	ext4_fsblk_t discard_block;
+	struct ext4_super_block *es = EXT4_SB(sb)->s_es;
+	struct ext4_free_extent ex;
+	int ret = 0;
+
+	assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+	ex.fe_start = start;
+	ex.fe_group = group;
+	ex.fe_len = count;
+
+	/*
+	 * Mark blocks used, so no one can reuse them while
+	 * being trimmed.
+	 */
+	mb_mark_used(e4b, &ex);
+	ext4_unlock_group(sb, group);
+
+	discard_block = (ext4_fsblk_t)group *
+			EXT4_BLOCKS_PER_GROUP(sb)
+			+ start
+			+ le32_to_cpu(es->s_first_data_block);
+	trace_ext4_discard_blocks(sb,
+			(unsigned long long)discard_block,
+			count);
+	ret = sb_issue_discard(sb, discard_block, count);
+	if (ret == -EOPNOTSUPP) {
+		ext4_warning(sb,
+			"discard not supported!");
+	} else if (ret < 0) {
+		ext4_std_error(sb, ret);
+	}
+
+	ext4_lock_group(sb, group);
+	mb_free_blocks(NULL, e4b, start, ex.fe_len);
+	return ret;
+}
+
+/**
+ * ext4_trim_all_free -- function to trim all free space in alloc. group
+ * @sb:			super block for file system
+ * @e4b:		ext4 buddy
+ * @start:		first group block to examine
+ * @max:		last group block to examine
+ * @minblocks:		minimum extent block count
+ *
+ * ext4_trim_all_free walks through group's buddy bitmap searching for free
+ * extents. When the free block is found, ext4_trim_extent is called to TRIM
+ * the extent.
+ *
+ *
+ * ext4_trim_all_free walks through group's block bitmap searching for free
+ * extents. When the free extent is found, mark it as used in group buddy
+ * bitmap. Then issue a TRIM command on this extent and free the extent in
+ * the group buddy bitmap. This is done until whole group is scanned.
+ */
+ext4_grpblk_t ext4_trim_all_free(struct super_block *sb, struct ext4_buddy *e4b,
+		ext4_grpblk_t start, ext4_grpblk_t max, ext4_grpblk_t minblocks)
+{
+	void *bitmap;
+	ext4_grpblk_t next, count = 0;
+	ext4_group_t group;
+	int ret = 0;
+
+	BUG_ON(e4b == NULL);
+
+	bitmap = e4b->bd_bitmap;
+	group = e4b->bd_group;
+	start = (e4b->bd_info->bb_first_free > start) ?
+		e4b->bd_info->bb_first_free : start;
+	ext4_lock_group(sb, group);
+
+	while (start < max) {
+
+		start = mb_find_next_zero_bit(bitmap, max, start);
+		if (start >= max)
+			break;
+		next = mb_find_next_bit(bitmap, max, start);
+
+		if ((next - start) >= minblocks) {
+			ret = ext4_trim_extent(sb, start,
+				next - start, group, e4b);
+			if (ret < 0)
+				break;
+			count += next - start;
+		}
+		start = next + 1;
+
+		if (signal_pending(current)) {
+			count = -ERESTARTSYS;
+			break;
+		}
+
+		if (need_resched()) {
+			ext4_unlock_group(sb, group);
+			cond_resched();
+			ext4_lock_group(sb, group);
+		}
+
+		if ((e4b->bd_info->bb_free - count) < minblocks)
+			break;
+	}
+	ext4_unlock_group(sb, group);
+
+	ext4_debug("trimmed %d blocks in the group %d\n",
+		count, group);
+
+	if (ret < 0)
+		count = ret;
+
+	return count;
+}
+
+/**
+ * ext4_trim_fs() -- trim ioctl handle function
+ * @sb:			superblock for filesystem
+ * @start:		First Byte to trim
+ * @len:		number of Bytes to trim from start
+ * @minlen:		minimum extent length in Bytes
+ *
+ * ext4_trim_fs goes through all allocation groups containing Bytes from
+ * start to start+len. For each such a group ext4_trim_all_free function
+ * is invoked to trim all free space.
+ */
+int ext4_trim_fs(struct super_block *sb, uint64_t start, uint64_t len,
+		uint64_t minlen)
+{
+	struct ext4_buddy e4b;
+	ext4_fsblk_t first_group, last_group;
+	ext4_group_t group, ngroups = ext4_get_groups_count(sb);
+	ext4_grpblk_t cnt, first_block, last_block;
+	struct ext4_super_block *es = EXT4_SB(sb)->s_es;
+	int ret = 0;
+
+	start >>= sb->s_blocksize_bits;
+	len >>= sb->s_blocksize_bits;
+	minlen >>= sb->s_blocksize_bits;
+
+	if (unlikely(minlen > EXT4_BLOCKS_PER_GROUP(sb)))
+		return -EINVAL;
+
+	/* Determine first and last group to examine based on start and len */
+	first_group = (start - le32_to_cpu(es->s_first_data_block)) /
+		      EXT4_BLOCKS_PER_GROUP(sb);
+	last_group = (start + len - le32_to_cpu(es->s_first_data_block)) /
+		     EXT4_BLOCKS_PER_GROUP(sb);
+	last_group = (last_group > ngroups - 1) ? ngroups - 1 : last_group;
+
+	if (first_group > last_group)
+		return -EINVAL;
+
+	first_block = (start - le32_to_cpu(es->s_first_data_block)) %
+			EXT4_BLOCKS_PER_GROUP(sb);
+	last_block = EXT4_BLOCKS_PER_GROUP(sb);
+
+	for (group = first_group; group <= last_group; group++) {
+
+		ret = ext4_mb_load_buddy(sb, group, &e4b);
+		if (ret) {
+			ext4_error(sb, "Error in loading buddy "
+					"information for %u", group);
+			break;
+		}
+
+		if (len >= EXT4_BLOCKS_PER_GROUP(sb))
+			len -= (EXT4_BLOCKS_PER_GROUP(sb) - first_block);
+		else
+			last_block = len;
+
+		if (e4b.bd_info->bb_free >= minlen) {
+			cnt = ext4_trim_all_free(sb, &e4b, first_block,
+						last_block, minlen);
+			if (cnt < 0) {
+				ret = cnt;
+				ext4_mb_unload_buddy(&e4b);
+				break;
+			}
+		}
+		ext4_mb_unload_buddy(&e4b);
+
+		first_block = 0;
+	}
+	return ret;
+}
diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index e72d323..3b05b3a 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -1114,6 +1114,7 @@ static const struct super_operations ext4_sops = {
 	.quota_write	= ext4_quota_write,
 #endif
 	.bdev_try_to_free_page = bdev_try_to_free_page,
+	.trim_fs	= ext4_trim_fs
 };
 
 static const struct super_operations ext4_nojournal_sops = {
-- 
1.7.2.1

[PATCH 0/3] Batched discard support

[Lukas Czerner]

Hi, all

because people were worried about possibly long stalls appearing
when FITRIM ioctl is working, I have changed the FITRIM interface
as Dimitry suggested. Now you can choose whether to trim whole
file system or just a part of it, resp. you can specify the range
of Bytes to trim.

To be specific you can create something like this:

int main(int argc, char **argv)
{
	int fd;
	uint64_t range[3];

	range[0] = 40960;
	range[1] = 134217728;
	range[2] = 4096;

	fd = open(argv[1], O_RDONLY);
	if (fd < 0) {
		perror("open");
		return 1;
	}

	if (ioctl(fd, FITRIM, range)) {
		if (errno == EOPNOTSUPP)
			fprintf(stderr, "FITRIM not supported\n");
		else
			perror("FITRIM");
		return 1;
	}

	return 0;
}

Range items have following meaning:

range[0] - (start) first Byte to trim
range[1] - (len) number of Bytes to trim from start
range[2] - (minlen) minimum extent length to trim, free extents shorter
than this number of Bytes will be ignored. This number will be rounded
up to the block size.

So in my example it will trim all free extents from block 10 of first
alloc. group to block 10 of second alloc. group, assuming we have
block_size = 4096.

Also, when you want to trim the whole fs, you can simply pass NULL
instead of range into the ioctl, or you can specify the range correctly
to cover the whole fs.

Regards
-Lukas

[PATCH 1/3] Add ioctl FITRIM.
[PATCH 2/3] Add batched discard support for ext3
[PATCH 3/3] Add batched discard support for ext4

 fs/ext3/balloc.c        |  249 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 fs/ext4/ext4.h          |    2 +
 fs/ext4/mballoc.c       |  194 ++++++++++++++++++++++++++++++++++++
 fs/ext4/super.c         |    1 +
 fs/ioctl.c              |   34 +++++++
 include/linux/ext3_fs.h |    1 +
 include/linux/fs.h      |    2 +
 8 files changed, 484 insertions(+), 0 deletions(-)

[PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

Walk through allocation groups and trim all free extents. It can be
invoked through FITRIM ioctl on the file system. The main idea is to
provide a way to trim the whole file system if needed, since some SSD's
may suffer from performance loss after the whole device was filled (it
does not mean that fs is full!).

It search for free extents in allocation groups specified by Byte range
start -> start+len. When the free extent is within this range, blocks are
marked as used and then trimmed. Afterwards these blocks are marked as
free in per-group bitmap.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Reviewed-by: Jan Kara <jack@suse.cz>
---
 fs/ext3/balloc.c        |  249 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 include/linux/ext3_fs.h |    1 +
 3 files changed, 251 insertions(+), 0 deletions(-)

diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index 4a32511..72a9242 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -20,6 +20,7 @@
 #include <linux/ext3_jbd.h>
 #include <linux/quotaops.h>
 #include <linux/buffer_head.h>
+#include <linux/blkdev.h>
 
 /*
  * balloc.c contains the blocks allocation and deallocation routines
@@ -1882,3 +1883,251 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
 	return ext3_bg_num_gdb_meta(sb,group);
 
 }
+
+/**
+ * ext3_trim_all_free -- function to trim all free space in alloc. group
+ * @sb:			super block for file system
+ * @group:		allocation group to trim
+ * @start:		first group block to examine
+ * @max:		last group block to examine
+ * @gdp:		allocation group description structure
+ * @minblocks:		minimum extent block count
+ *
+ * ext3_trim_all_free walks through group's block bitmap searching for free
+ * blocks. When the free block is found, it tries to allocate this block and
+ * consequent free block to get the biggest free extent possible, until it
+ * reaches any used block. Then issue a TRIM command on this extent and free
+ * the extent in the block bitmap. This is done until whole group is scanned.
+ */
+ext3_grpblk_t ext3_trim_all_free(struct super_block *sb, unsigned int group,
+				ext3_grpblk_t start, ext3_grpblk_t max,
+				ext3_grpblk_t minblocks)
+{
+	handle_t *handle;
+	ext3_grpblk_t next, count = 0, bit;
+	struct ext3_sb_info *sbi;
+	ext3_fsblk_t discard_block;
+	struct buffer_head *bitmap_bh = NULL;
+	struct buffer_head *gdp_bh;
+	ext3_grpblk_t free_blocks;
+	struct ext3_group_desc *gdp;
+	int err = 0, ret = 0;
+	ext3_grpblk_t freed;
+
+	/*
+	 * We will update one block bitmap, and one group descriptor
+	 */
+	handle = ext3_journal_start_sb(sb, 2);
+	if (IS_ERR(handle)) {
+		err = PTR_ERR(handle);
+		return err;
+	}
+
+	bitmap_bh = read_block_bitmap(sb, group);
+	if (!bitmap_bh)
+		goto err_out;
+
+	BUFFER_TRACE(bitmap_bh, "getting undo access");
+	err = ext3_journal_get_undo_access(handle, bitmap_bh);
+	if (err)
+		goto err_out;
+
+	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
+	if (!gdp)
+		goto err_out;
+
+	BUFFER_TRACE(gdp_bh, "get_write_access");
+	err = ext3_journal_get_write_access(handle, gdp_bh);
+	if (err)
+		goto err_out;
+
+	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+	sbi = EXT3_SB(sb);
+
+	 /* Walk through the whole group */
+	while (start < max) {
+
+		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
+		if (start < 0)
+			break;
+		next = start;
+
+		/*
+		 * Allocate contiguous free extents by setting bits in the
+		 * block bitmap
+		 */
+		while (next < max
+			&& claim_block(sb_bgl_lock(sbi, group),
+					next, bitmap_bh)) {
+			next++;
+		}
+
+		 /* We did not claim any blocks */
+		if (next == start)
+			continue;
+
+		discard_block = (ext3_fsblk_t)start +
+				ext3_group_first_block_no(sb, group);
+
+		/* Update counters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
+
+		/* Do not issue a TRIM on extents smaller than minblocks */
+		if ((next - start) < minblocks)
+			goto free_extent;
+
+		 /* Send the TRIM command down to the device */
+		ret = sb_issue_discard(sb, discard_block, next - start);
+		count += (next - start);
+
+free_extent:
+		freed = 0;
+
+		/*
+		 * Clear bits in the bitmap
+		 */
+		for (bit = start; bit < next; bit++) {
+			BUFFER_TRACE(bitmap_bh, "clear bit");
+			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
+						bit, bitmap_bh->b_data)) {
+				ext3_error(sb, __func__,
+					"bit already cleared for block "E3FSBLK,
+					 (unsigned long)bit);
+				BUFFER_TRACE(bitmap_bh, "bit already cleared");
+			} else {
+				freed++;
+			}
+		}
+
+		/* Update couters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
+
+		start = next;
+
+		if (ret < 0) {
+			if (ret == -EOPNOTSUPP) {
+				ext3_warning(sb, __func__,
+					"discard not supported!");
+				count = ret;
+				break;
+			}
+			err = ret;
+			break;
+		}
+
+		if (signal_pending(current)) {
+			count = -ERESTARTSYS;
+			break;
+		}
+
+		cond_resched();
+
+		/* No more suitable extents */
+		if ((free_blocks - count) < minblocks)
+			break;
+	}
+
+	/* We dirtied the bitmap block */
+	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
+	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
+
+	/* And the group descriptor block */
+	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
+	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
+	if (!err)
+		err = ret;
+
+	ext3_debug("trimmed %d blocks in the group %d\n",
+		count, group);
+
+err_out:
+	if (err) {
+		ext3_std_error(sb, err);
+		count = err;
+	}
+
+	ext3_journal_stop(handle);
+	brelse(bitmap_bh);
+
+	return count;
+}
+
+/**
+ * ext3_trim_fs() -- trim ioctl handle function
+ * @sb:			superblock for filesystem
+ * @start:		First Byte to trim
+ * @len:		number of Bytes to trim from start
+ * @minlen:		minimum extent length in Bytes
+ *
+ * ext3_trim_fs goes through all allocation groups containing Bytes from
+ * start to start+len. For each such a group ext3_trim_all_free function
+ * is invoked to trim all free space.
+ */
+int ext3_trim_fs(struct super_block *sb, uint64_t start, uint64_t len,
+		uint64_t minlen)
+{
+	ext3_grpblk_t last_block, first_block, free_blocks;
+	unsigned long long first_group, last_group;
+	unsigned long group, ngroups;
+	struct ext3_group_desc *gdp;
+	struct ext3_super_block *es;
+	int ret = 0;
+
+	start >>= sb->s_blocksize_bits;
+	len >>= sb->s_blocksize_bits;
+	minlen >>= sb->s_blocksize_bits;
+
+	if (unlikely(minlen > EXT3_BLOCKS_PER_GROUP(sb)))
+		return -EINVAL;
+
+	es = EXT3_SB(sb)->s_es;
+	ngroups = EXT3_SB(sb)->s_groups_count;
+	smp_rmb();
+
+	/* Determine first and last group to examine based on start and len */
+	first_group = (start - le32_to_cpu(es->s_first_data_block)) /
+		      EXT3_BLOCKS_PER_GROUP(sb);
+	last_group = (start + len - le32_to_cpu(es->s_first_data_block)) /
+		     EXT3_BLOCKS_PER_GROUP(sb);
+	last_group = (last_group > ngroups - 1) ? ngroups - 1 : last_group;
+
+	if (first_group > last_group)
+		return -EINVAL;
+
+	first_block = start % EXT3_BLOCKS_PER_GROUP(sb);
+	last_block = EXT3_BLOCKS_PER_GROUP(sb);
+
+	for (group = first_group; group <= last_group; group++) {
+
+		gdp = ext3_get_group_desc(sb, group, NULL);
+		if (!gdp)
+			break;
+
+		free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+		if (free_blocks < minlen)
+			continue;
+
+		if (len >= EXT3_BLOCKS_PER_GROUP(sb))
+			len -= (EXT3_BLOCKS_PER_GROUP(sb) - first_block);
+		else
+			last_block = len;
+
+		ret = ext3_trim_all_free(sb, group, first_block,
+					last_block, minlen);
+		if (ret < 0)
+			break;
+
+		first_block = 0;
+	}
+
+	if (ret >= 0)
+		ret = 0;
+
+	return ret;
+}
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 6c953bb..b172c88 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -797,6 +797,7 @@ static const struct super_operations ext3_sops = {
 	.quota_write	= ext3_quota_write,
 #endif
 	.bdev_try_to_free_page = bdev_try_to_free_page,
+	.trim_fs	= ext3_trim_fs,
 };
 
 static const struct export_operations ext3_export_ops = {
diff --git a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
index 7fc62d4..9afacd4 100644
--- a/include/linux/ext3_fs.h
+++ b/include/linux/ext3_fs.h
@@ -857,6 +857,7 @@ extern struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
 extern int ext3_should_retry_alloc(struct super_block *sb, int *retries);
 extern void ext3_init_block_alloc_info(struct inode *);
 extern void ext3_rsv_window_add(struct super_block *sb, struct ext3_reserve_window_node *rsv);
+extern int ext3_trim_fs(struct super_block *, uint64_t, uint64_t, uint64_t);
 
 /* dir.c */
 extern int ext3_check_dir_entry(const char *, struct inode *,
-- 
1.7.2

[PATCH 1/3] Add ioctl FITRIM.

[Lukas Czerner]

Adds an filesystem independent ioctl to allow implementation of file
system batched discard support.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
 fs/ioctl.c         |   31 +++++++++++++++++++++++++++++++
 include/linux/fs.h |    2 ++
 2 files changed, 33 insertions(+), 0 deletions(-)

diff --git a/fs/ioctl.c b/fs/ioctl.c
index 2d140a7..6c01c3c 100644
--- a/fs/ioctl.c
+++ b/fs/ioctl.c
@@ -540,6 +540,33 @@ static int ioctl_fsthaw(struct file *filp)
 	return thaw_super(sb);
 }
 
+static int ioctl_fstrim(struct file *filp, unsigned long arg)
+{
+	struct super_block *sb = filp->f_path.dentry->d_inode->i_sb;
+	unsigned int minlen;
+	int err;
+
+	if (!capable(CAP_SYS_ADMIN))
+		return -EPERM;
+
+	/* If filesystem doesn't support trim feature, return. */
+	if (sb->s_op->trim_fs == NULL)
+		return -EOPNOTSUPP;
+
+	/* If a blockdevice-backed filesystem isn't specified, return EINVAL. */
+	if (sb->s_bdev == NULL)
+		return -EINVAL;
+
+	err = get_user(minlen, (unsigned int __user *) arg);
+	if (err)
+		return err;
+
+	err = sb->s_op->trim_fs(minlen, sb);
+	if (err)
+		return err;
+	return 0;
+}
+
 /*
  * When you add any new common ioctls to the switches above and below
  * please update compat_sys_ioctl() too.
@@ -590,6 +617,10 @@ int do_vfs_ioctl(struct file *filp, unsigned int fd, unsigned int cmd,
 		error = ioctl_fsthaw(filp);
 		break;
 
+	case FITRIM:
+		error = ioctl_fstrim(filp, arg);
+		break;
+
 	case FS_IOC_FIEMAP:
 		return ioctl_fiemap(filp, arg);
 
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 68ca1b0..01632e4 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -315,6 +315,7 @@ struct inodes_stat_t {
 #define FIGETBSZ   _IO(0x00,2)	/* get the block size used for bmap */
 #define FIFREEZE	_IOWR('X', 119, int)	/* Freeze */
 #define FITHAW		_IOWR('X', 120, int)	/* Thaw */
+#define FITRIM		_IOWR('X', 121, int)	/* Trim */
 
 #define	FS_IOC_GETFLAGS			_IOR('f', 1, long)
 #define	FS_IOC_SETFLAGS			_IOW('f', 2, long)
@@ -1580,6 +1581,7 @@ struct super_operations {
 	ssize_t (*quota_write)(struct super_block *, int, const char *, size_t, loff_t);
 #endif
 	int (*bdev_try_to_free_page)(struct super_block*, struct page*, gfp_t);
+	int (*trim_fs) (unsigned int, struct super_block *);
 };
 
 /*
-- 
1.7.2

[PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

Walk through each allocation group and trim all free extents. It can be
invoked through FITRIM ioctl on the file system. The main idea is to
provide a way to trim the whole file system if needed, since some SSD's
may suffer from performance loss after the whole device was filled (it
does not mean that fs is full!).

It search for free extents in each allocation group. When the free
extent is found, blocks are marked as used and then trimmed. Afterwards
these blocks are marked as free in per-group bitmap.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
 fs/ext3/balloc.c        |  217 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 include/linux/ext3_fs.h |    1 +
 3 files changed, 219 insertions(+), 0 deletions(-)

diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index 4a32511..dffc2e2 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -20,6 +20,7 @@
 #include <linux/ext3_jbd.h>
 #include <linux/quotaops.h>
 #include <linux/buffer_head.h>
+#include <linux/blkdev.h>
 
 /*
  * balloc.c contains the blocks allocation and deallocation routines
@@ -1882,3 +1883,219 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
 	return ext3_bg_num_gdb_meta(sb,group);
 
 }
+
+/**
+ * ext3_trim_all_free -- function to trim all free space in alloc. group
+ * @sb:			super block for file system
+ * @group:		allocation group to trim
+ * @gdp:		allocation group description structure
+ * @minblocks:		minimum extent block count
+ *
+ * ext3_trim_all_free walks through group's block bitmap searching for free
+ * blocks. When the free block is found, it tries to allocate this block and
+ * consequent free block to get the biggest free extent possible, until it
+ * reaches any used block. Then issue a TRIM command on this extent and free
+ * the extent in the block bitmap. This is done until whole group is scanned.
+ */
+ext3_grpblk_t ext3_trim_all_free(struct super_block *sb,
+			unsigned int group, ext3_grpblk_t minblocks)
+{
+	handle_t *handle;
+	ext3_grpblk_t max = EXT3_BLOCKS_PER_GROUP(sb);
+	ext3_grpblk_t next, count = 0, start, bit;
+	struct ext3_sb_info *sbi;
+	ext3_fsblk_t discard_block;
+	struct buffer_head *bitmap_bh = NULL;
+	struct buffer_head *gdp_bh;
+	ext3_grpblk_t free_blocks;
+	struct ext3_group_desc *gdp;
+	int err = 0, ret;
+	ext3_grpblk_t freed;
+
+	/*
+	 * We will update one block bitmap, and one group descriptor
+	 */
+	handle = ext3_journal_start_sb(sb, 2);
+	if (IS_ERR(handle)) {
+		err = PTR_ERR(handle);
+		return err;
+	}
+
+	bitmap_bh = read_block_bitmap(sb, group);
+	if (!bitmap_bh)
+		goto err_out;
+
+	BUFFER_TRACE(bitmap_bh, "getting undo access");
+	err = ext3_journal_get_undo_access(handle, bitmap_bh);
+	if (err)
+		goto err_out;
+
+	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
+	if (!gdp)
+		goto err_out;
+
+	BUFFER_TRACE(gd_bh, "get_write_access");
+	err = ext3_journal_get_write_access(handle, gdp_bh);
+	if (err)
+		goto err_out;
+
+	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+	sbi = EXT3_SB(sb);
+
+	 /* Walk through the whole group */
+	start = 0;
+	while (start < max) {
+
+		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
+		if (start < 0)
+			break;
+		next = start;
+
+		/*
+		 * Allocate contiguous free extents by setting bits in the
+		 * block bitmap
+		 */
+		while (next < max
+			&& claim_block(sb_bgl_lock(sbi, group),
+					next, bitmap_bh)) {
+			next++;
+		}
+
+		 /* We did not claim any blocks */
+		if (next == start)
+			continue;
+
+		discard_block = (ext3_fsblk_t)start +
+				ext3_group_first_block_no(sb, group);
+
+		/* Update counters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
+
+		/* Do not issue a TRIM on extents smaller than minblocks */
+		if ((next - start) < minblocks)
+			goto free_extent;
+
+		 /* Send the TRIM command down to the device */
+		ret = sb_issue_discard(sb, discard_block, next - start);
+		count += (next - start);
+
+free_extent:
+		freed = 0;
+
+		/*
+		 * Clear bits in the bitmap
+		 */
+		for (bit = start; bit < next; bit++) {
+			BUFFER_TRACE(bitmap_bh, "clear bit");
+			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
+						bit, bitmap_bh->b_data)) {
+				ext3_error(sb, __func__,
+					"bit already cleared for block "E3FSBLK,
+					 (unsigned long)bit);
+				BUFFER_TRACE(bitmap_bh, "bit already cleared");
+			} else {
+				freed++;
+			}
+		}
+
+		/* Update couters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
+
+		start = next;
+
+		if (ret == EOPNOTSUPP) {
+			ext3_warning(sb, __func__,
+				"discard not supported!");
+			count = -EOPNOTSUPP;
+			break;
+
+		}
+
+		if (signal_pending(current)) {
+			count = -ERESTARTSYS;
+			break;
+		}
+
+		cond_resched();
+
+		/* No more suitable extents */
+		if ((free_blocks - count) < minblocks)
+			break;
+	}
+
+	/* We dirtied the bitmap block */
+	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
+	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
+
+	/* And the group descriptor block */
+	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
+	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
+	if (!err)
+		err = ret;
+
+	ext3_debug("trimmed %d blocks in the group %d\n",
+		count, group);
+
+err_out:
+	if (err) {
+		ext3_std_error(sb, err);
+		count = -err;
+	}
+
+	ext3_journal_stop(handle);
+	brelse(bitmap_bh);
+
+	return count;
+}
+
+/**
+ * ext3_trim_fs() -- trim ioctl handle function
+ * @minlen:		minimum extent length in Bytes
+ * @sb:			superblock for filesystem
+ *
+ * ext3_trim_fs goes through all allocation group searching for groups with more
+ * free space than minlen. For such a group ext3_trim_all_free function is
+ * invoked to trim all free space.
+ */
+int ext3_trim_fs(unsigned int minlen, struct super_block *sb)
+{
+	ext3_grpblk_t minblocks;
+	unsigned long ngroups;
+	unsigned int group;
+	struct ext3_group_desc *gdp;
+	ext3_grpblk_t free_blocks;
+	int ret = 0;
+
+	minblocks = DIV_ROUND_UP(minlen, sb->s_blocksize);
+	if (unlikely(minblocks > EXT3_BLOCKS_PER_GROUP(sb)))
+		return -EINVAL;
+
+	ngroups = EXT3_SB(sb)->s_groups_count;
+	smp_rmb();
+
+	for (group = 0; group < ngroups; group++) {
+
+		gdp = ext3_get_group_desc(sb, group, NULL);
+		if (!gdp)
+			break;
+
+		free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+		if (free_blocks < minblocks)
+			continue;
+
+		ret = ext3_trim_all_free(sb, group, minblocks);
+		if (ret < 0)
+			break;
+	}
+
+	if (ret >= 0)
+		ret = 0;
+
+	return ret;
+}
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 6c953bb..b172c88 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -797,6 +797,7 @@ static const struct super_operations ext3_sops = {
 	.quota_write	= ext3_quota_write,
 #endif
 	.bdev_try_to_free_page = bdev_try_to_free_page,
+	.trim_fs	= ext3_trim_fs,
 };
 
 static const struct export_operations ext3_export_ops = {
diff --git a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
index 7fc62d4..9083e16 100644
--- a/include/linux/ext3_fs.h
+++ b/include/linux/ext3_fs.h
@@ -857,6 +857,7 @@ extern struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
 extern int ext3_should_retry_alloc(struct super_block *sb, int *retries);
 extern void ext3_init_block_alloc_info(struct inode *);
 extern void ext3_rsv_window_add(struct super_block *sb, struct ext3_reserve_window_node *rsv);
+extern int ext3_trim_fs(unsigned int minlen, struct super_block *sb);
 
 /* dir.c */
 extern int ext3_check_dir_entry(const char *, struct inode *,
-- 
1.7.2

Re: [PATCH 2/3] Add batched discard support for ext3

[Jan Kara]

  Hi,

  The patch looks good. Just one small thing:

On Wed 04-08-10 15:44:34, Lukas Czerner wrote:
> +	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
> +	if (!gdp)
> +		goto err_out;
> +
> +	BUFFER_TRACE(gd_bh, "get_write_access");
                     ^^^^^ gdp_bh

  So you can add: Reviewed-by: Jan Kara <jack@suse.cz>

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

On Wed, 4 Aug 2010, Jan Kara wrote:

>   Hi,
> 
>   The patch looks good. Just one small thing:
> 
> On Wed 04-08-10 15:44:34, Lukas Czerner wrote:
> > +	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
> > +	if (!gdp)
> > +		goto err_out;
> > +
> > +	BUFFER_TRACE(gd_bh, "get_write_access");
>                      ^^^^^ gdp_bh
> 
>   So you can add: Reviewed-by: Jan Kara <jack@suse.cz>
> 
> 								Honza
> 

Hi,

thanks a lot for your review. I will resend both patches shortly.

Regards.

-Lukas

Re: [PATCH 2/3] Add batched discard support for ext3

[Andreas Dilger]

On 2010-08-04, at 07:44, Lukas Czerner wrote:
> +		/*
> +		 * Clear bits in the bitmap
> +		 */
> +		for (bit = start; bit < next; bit++) {
> +			BUFFER_TRACE(bitmap_bh, "clear bit");
> +			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
> +						bit, bitmap_bh->b_data)) {
> +				ext3_error(sb, __func__,
> +					"bit already cleared for block "E3FSBLK,
> +					 (unsigned long)bit);
> +				BUFFER_TRACE(bitmap_bh, "bit already cleared");
> +			} else {
> +				freed++;
> +			}
> +		}
> +
> +		/* Update couters */
> +		spin_lock(sb_bgl_lock(sbi, group));
> +		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
> +		spin_unlock(sb_bgl_lock(sbi, group));
> +		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);

It wouldn't be a terrible idea to put this code into a helper function that is shared with ext3_free_blocks_sb() so that it is kept in sync.  There are a lot of places that need to be kept coordinated (disk bitmap, memory bitmap, group descriptor, percpu counter) so I'd like that to be localized to one part of the code.


Cheers, Andreas

Re: [PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

On Wed, 4 Aug 2010, Andreas Dilger wrote:

> On 2010-08-04, at 07:44, Lukas Czerner wrote:
> > +		/*
> > +		 * Clear bits in the bitmap
> > +		 */
> > +		for (bit = start; bit < next; bit++) {
> > +			BUFFER_TRACE(bitmap_bh, "clear bit");
> > +			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
> > +						bit, bitmap_bh->b_data)) {
> > +				ext3_error(sb, __func__,
> > +					"bit already cleared for block "E3FSBLK,
> > +					 (unsigned long)bit);
> > +				BUFFER_TRACE(bitmap_bh, "bit already cleared");
> > +			} else {
> > +				freed++;
> > +			}
> > +		}
> > +
> > +		/* Update couters */
> > +		spin_lock(sb_bgl_lock(sbi, group));
> > +		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
> > +		spin_unlock(sb_bgl_lock(sbi, group));
> > +		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
> 
> It wouldn't be a terrible idea to put this code into a helper function that is shared with ext3_free_blocks_sb() so that it is kept in sync.  There are a lot of places that need to be kept coordinated (disk bitmap, memory bitmap, group descriptor, percpu counter) so I'd like that to be localized to one part of the code.
> 
> 
> Cheers, Andreas
> 

Ok, I will see what I can do with that.

Thanks.

-Lukas

[PATCH 0/3 v3] Batched discard support for Ext3/Ext4

[Lukas Czerner]

Hi all,

since my last post I have changed those patches slightly. Ext3 patch does
not introduce DISCARD/NODISCARD mount option, so there is just FITRIM
ioctl which can be invoked only by user with CAP_SYS_ADMIN.

Ext3 patch also involves journaling because as Jan pointed out not using
journal can cause problems when system crashes. Jan please look at this
I hope it is ok now. Also I am not sure if it would not be better to close
the journal after allocating free space and then start new one after
the TRIM (this was proposed by Josef Bacik).

Ext4 patch does not remove old "online" discard implementation and does not
check for DISCARD mount option. To avoid journaling I have used alloc_sem
semaphore to prevent allocations from the group while it is being trimmed.
It seems sufficient to me.

The general idea of batched discards stays the same. So when FITRIM ioctl
is invoked upon the mount point, it walks through all allocation groups
searching for free extents bigger than minlen, then trim those extents. In
ext3 consistency is assured by allocating these free extents in alloc. group
(with journal involved). In ext4 consistency is assured by use of alloc_sem
semaphore.

-Lukas

[PATCH 1/3] Add ioctl FITRIM.
[PATCH 2/3] Add batched discard support for ext3
[PATCH 3/3] Add batched discard support for ext4

[PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

Walk through each allocation group and trim all free extents. It can be
invoked through TRIM ioctl on the file system. The main idea is to
provide a way to trim the whole file system if needed, since some SSD's
may suffer from performance loss after the whole device was filled (it
does not mean that fs is full!).

It search for free extents in each allocation group. When the free
extent is found, blocks are marked as used and then trimmed. Afterwards
these blocks are marked as free in per-group bitmap.

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
---
 fs/ext3/balloc.c        |  229 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext3/super.c         |    1 +
 include/linux/ext3_fs.h |    1 +
 3 files changed, 231 insertions(+), 0 deletions(-)

diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
index a177122..97c6867 100644
--- a/fs/ext3/balloc.c
+++ b/fs/ext3/balloc.c
@@ -20,6 +20,7 @@
 #include <linux/ext3_jbd.h>
 #include <linux/quotaops.h>
 #include <linux/buffer_head.h>
+#include <linux/blkdev.h>
 
 /*
  * balloc.c contains the blocks allocation and deallocation routines
@@ -1876,3 +1877,231 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
 	return ext3_bg_num_gdb_meta(sb,group);
 
 }
+
+/**
+ * ext3_trim_all_free -- function to trim all free space in alloc. group
+ * @sb:			super block for file system
+ * @group:		allocation group to trim
+ * @gdp:		allocation group description structure
+ * @minblocks:		minimum extent block count
+ *
+ * ext3_trim_all_free walks through group's block bitmap searching for free
+ * blocks. When the free block is found, it tries to allocate this block and
+ * consequent free block to get the biggest free extent possible, until it
+ * reaches any used block. Then issue a TRIM command on this extent and free
+ * the extent in the block bitmap. This is done until whole group is scanned.
+ */
+ext3_grpblk_t ext3_trim_all_free(struct super_block *sb,
+			unsigned int group, ext3_grpblk_t minblocks)
+{
+	handle_t *handle;
+	ext3_grpblk_t max = EXT3_BLOCKS_PER_GROUP(sb);
+	ext3_grpblk_t next, count = 0, start, bit;
+	struct ext3_sb_info *sbi;
+	ext3_fsblk_t discard_block;
+	struct buffer_head *bitmap_bh = NULL;
+	struct buffer_head *gdp_bh;
+	ext3_grpblk_t free_blocks;
+	struct ext3_group_desc *gdp;
+	int err = 0, ret;
+	ext3_grpblk_t freed;
+
+	/**
+	 * We will update one block bitmap, and one group descriptor
+	 */
+	handle = ext3_journal_start_sb(sb, 2);
+	if (IS_ERR(handle)) {
+		err = PTR_ERR(handle);
+		ext3_warning(sb, __func__, "error %d on journal start", err);
+		return err;
+	}
+
+	bitmap_bh = read_block_bitmap(sb, group);
+	if (!bitmap_bh)
+		goto err_out;
+
+	BUFFER_TRACE(bitmap_bh, "getting undo access");
+	err = ext3_journal_get_undo_access(handle, bitmap_bh);
+	if (err)
+		goto err_out;
+
+	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
+	if (!gdp)
+		goto err_out;
+
+	BUFFER_TRACE(gd_bh, "get_write_access");
+	err = ext3_journal_get_write_access(handle, gdp_bh);
+	if (err)
+		goto err_out;
+
+	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+	sbi = EXT3_SB(sb);
+
+	 /* Walk through the whole group */
+	start = 0;
+	while (start < max) {
+
+		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
+		if (start < 0)
+			break;
+		next = start;
+
+		/**
+		 * Allocate contiguous free extents by setting bits in the
+		 * block bitmap
+		 */
+		while (next < max
+			&& claim_block(sb_bgl_lock(sbi, group),
+					next, bitmap_bh)) {
+			next++;
+		}
+
+		 /* We did not claimed any blocks */
+		if (next == start)
+			continue;
+
+		discard_block = (ext3_fsblk_t)start +
+				ext3_group_first_block_no(sb, group);
+
+		/* Update counters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
+
+		/* Do not issue a TRIM on extents smaller than minblocks */
+		if ((next - start) < minblocks)
+			goto free_extent;
+
+		 /* Send the TRIM command down to the device */
+		sb_issue_discard(sb, discard_block, next - start);
+		count += (next - start);
+		cond_resched();
+
+free_extent:
+
+		freed = 0;
+		jbd_lock_bh_state(bitmap_bh);
+
+		for (bit = start; bit < next; bit++) {
+
+			/**
+			 * @@@ This prevents newly-allocated data from being
+			 * freed and then reallocated within the same
+			 * transaction.
+			 */
+			BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
+			J_ASSERT_BH(bitmap_bh,
+				bh2jh(bitmap_bh)->b_committed_data != NULL);
+			ext3_set_bit_atomic(sb_bgl_lock(sbi, group), bit,
+				bh2jh(bitmap_bh)->b_committed_data);
+
+			/**
+			 * We clear the bit in the bitmap after setting the
+			 * committed data bit, because this is the reverse
+			 * order to that which the allocator uses.
+			 */
+			BUFFER_TRACE(bitmap_bh, "clear bit");
+			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
+						bit, bitmap_bh->b_data)) {
+				jbd_unlock_bh_state(bitmap_bh);
+				ext3_error(sb, __func__,
+					"bit already cleared for block "E3FSBLK,
+					 (unsigned long)bit);
+				jbd_lock_bh_state(bitmap_bh);
+				BUFFER_TRACE(bitmap_bh, "bit already cleared");
+			} else {
+				freed++;
+			}
+		}
+
+		jbd_unlock_bh_state(bitmap_bh);
+
+		/* Update couters */
+		spin_lock(sb_bgl_lock(sbi, group));
+		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
+		spin_unlock(sb_bgl_lock(sbi, group));
+		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
+
+		start = next;
+
+		if (signal_pending(current)) {
+			count = -ERESTARTSYS;
+			break;
+		}
+
+		/* No more suitable extents */
+		if ((free_blocks - count) < minblocks)
+			break;
+	}
+
+	/* We dirtied the bitmap block */
+	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
+	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
+
+	/* And the group descriptor block */
+	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
+	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
+	if (!err)
+		err = ret;
+
+	ext3_debug("trimmed %d blocks in the group %d\n",
+		count, group);
+
+err_out:
+	if (err) {
+		ext3_std_error(sb, err);
+		count = -err;
+	}
+
+	ext3_journal_stop(handle);
+	brelse(bitmap_bh);
+
+	return count;
+}
+
+/**
+ * ext3_trim_fs() -- trim ioctl handle function
+ * @minlen:		minimum extent length in Bytes
+ * @sb:			superblock for filesystem
+ *
+ * ext3_trim_fs goes through all allocation group searching for groups with more
+ * free space than minlen. For such a group ext3_trim_all_free function is
+ * invoked to trim all free space.
+ */
+int ext3_trim_fs(unsigned int minlen, struct super_block *sb)
+{
+	ext3_grpblk_t minblocks;
+	unsigned long ngroups;
+	unsigned int group;
+	struct ext3_group_desc *gdp;
+	ext3_grpblk_t free_blocks;
+	int ret = 0;
+
+	minblocks = DIV_ROUND_UP(minlen, sb->s_blocksize);
+	if (unlikely(minblocks > EXT3_BLOCKS_PER_GROUP(sb)))
+		return -EINVAL;
+
+	ngroups = EXT3_SB(sb)->s_groups_count;
+	smp_rmb();
+
+	for (group = 0; group < ngroups; group++) {
+
+		gdp = ext3_get_group_desc(sb, group, NULL);
+		if (!gdp)
+			break;
+
+		free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
+		if (free_blocks < minblocks)
+			continue;
+
+		ret = ext3_trim_all_free(sb, group, minblocks);
+		if (ret < 0)
+			break;
+	}
+
+	if (ret >= 0)
+		ret = 0;
+
+	return ret;
+}
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 1bee604..75688f3 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -791,6 +791,7 @@ static const struct super_operations ext3_sops = {
 	.quota_write	= ext3_quota_write,
 #endif
 	.bdev_try_to_free_page = bdev_try_to_free_page,
+	.trim_fs	= ext3_trim_fs,
 };
 
 static const struct export_operations ext3_export_ops = {
diff --git a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
index 5f494b4..6e3fefc 100644
--- a/include/linux/ext3_fs.h
+++ b/include/linux/ext3_fs.h
@@ -857,6 +857,7 @@ extern struct ext3_group_desc * ext3_get_group_desc(struct super_block * sb,
 extern int ext3_should_retry_alloc(struct super_block *sb, int *retries);
 extern void ext3_init_block_alloc_info(struct inode *);
 extern void ext3_rsv_window_add(struct super_block *sb, struct ext3_reserve_window_node *rsv);
+extern int ext3_trim_fs(unsigned int minlen, struct super_block *sb);
 
 /* dir.c */
 extern int ext3_check_dir_entry(const char *, struct inode *,
-- 
1.7.1.1

Re: [PATCH 2/3] Add batched discard support for ext3

[Jan Kara]

On Tue 27-07-10 14:41:53, Lukas Czerner wrote:
> Walk through each allocation group and trim all free extents. It can be
> invoked through TRIM ioctl on the file system. The main idea is to
> provide a way to trim the whole file system if needed, since some SSD's
> may suffer from performance loss after the whole device was filled (it
> does not mean that fs is full!).
> 
> It search for free extents in each allocation group. When the free
> extent is found, blocks are marked as used and then trimmed. Afterwards
> these blocks are marked as free in per-group bitmap.
  Thanks for the patch. It looks much better than the previous one. Some
comments below.

> Signed-off-by: Lukas Czerner <lczerner@redhat.com>
> ---
>  fs/ext3/balloc.c        |  229 +++++++++++++++++++++++++++++++++++++++++++++++
>  fs/ext3/super.c         |    1 +
>  include/linux/ext3_fs.h |    1 +
>  3 files changed, 231 insertions(+), 0 deletions(-)
> 
> diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
> index a177122..97c6867 100644
> --- a/fs/ext3/balloc.c
> +++ b/fs/ext3/balloc.c
> @@ -20,6 +20,7 @@
>  #include <linux/ext3_jbd.h>
>  #include <linux/quotaops.h>
>  #include <linux/buffer_head.h>
> +#include <linux/blkdev.h>
>  
>  /*
>   * balloc.c contains the blocks allocation and deallocation routines
> @@ -1876,3 +1877,231 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
>  	return ext3_bg_num_gdb_meta(sb,group);
>  
>  }
> +
> +/**
> + * ext3_trim_all_free -- function to trim all free space in alloc. group
> + * @sb:			super block for file system
> + * @group:		allocation group to trim
> + * @gdp:		allocation group description structure
> + * @minblocks:		minimum extent block count
> + *
> + * ext3_trim_all_free walks through group's block bitmap searching for free
> + * blocks. When the free block is found, it tries to allocate this block and
> + * consequent free block to get the biggest free extent possible, until it
> + * reaches any used block. Then issue a TRIM command on this extent and free
> + * the extent in the block bitmap. This is done until whole group is scanned.
> + */
> +ext3_grpblk_t ext3_trim_all_free(struct super_block *sb,
> +			unsigned int group, ext3_grpblk_t minblocks)
> +{
> +	handle_t *handle;
> +	ext3_grpblk_t max = EXT3_BLOCKS_PER_GROUP(sb);
> +	ext3_grpblk_t next, count = 0, start, bit;
> +	struct ext3_sb_info *sbi;
> +	ext3_fsblk_t discard_block;
> +	struct buffer_head *bitmap_bh = NULL;
> +	struct buffer_head *gdp_bh;
> +	ext3_grpblk_t free_blocks;
> +	struct ext3_group_desc *gdp;
> +	int err = 0, ret;
> +	ext3_grpblk_t freed;
> +
> +	/**
> +	 * We will update one block bitmap, and one group descriptor
> +	 */
> +	handle = ext3_journal_start_sb(sb, 2);
> +	if (IS_ERR(handle)) {
> +		err = PTR_ERR(handle);
> +		ext3_warning(sb, __func__, "error %d on journal start", err);
  I think there's no need to issue another warning here... When
journal_start fails there should be notices about this in the log already.

> +		return err;
> +	}
> +
> +	bitmap_bh = read_block_bitmap(sb, group);
> +	if (!bitmap_bh)
> +		goto err_out;
> +
> +	BUFFER_TRACE(bitmap_bh, "getting undo access");
> +	err = ext3_journal_get_undo_access(handle, bitmap_bh);
> +	if (err)
> +		goto err_out;
> +
> +	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
> +	if (!gdp)
> +		goto err_out;
> +
> +	BUFFER_TRACE(gd_bh, "get_write_access");
> +	err = ext3_journal_get_write_access(handle, gdp_bh);
> +	if (err)
> +		goto err_out;
> +
> +	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
> +	sbi = EXT3_SB(sb);
> +
> +	 /* Walk through the whole group */
> +	start = 0;
> +	while (start < max) {
> +
> +		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
> +		if (start < 0)
> +			break;
> +		next = start;
> +
> +		/**
                ^^^ Use just /*. /** is reserved for comments processed by
  kernel documentation generator and they have to have special format...

> +		 * Allocate contiguous free extents by setting bits in the
> +		 * block bitmap
> +		 */
> +		while (next < max
> +			&& claim_block(sb_bgl_lock(sbi, group),
> +					next, bitmap_bh)) {
> +			next++;
> +		}
> +
> +		 /* We did not claimed any blocks */
                               ^^^^ claim

> +		if (next == start)
> +			continue;
> +
> +		discard_block = (ext3_fsblk_t)start +
> +				ext3_group_first_block_no(sb, group);
> +
> +		/* Update counters */
> +		spin_lock(sb_bgl_lock(sbi, group));
> +		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
> +		spin_unlock(sb_bgl_lock(sbi, group));
> +		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
> +
> +		/* Do not issue a TRIM on extents smaller than minblocks */
> +		if ((next - start) < minblocks)
> +			goto free_extent;
> +
> +		 /* Send the TRIM command down to the device */
> +		sb_issue_discard(sb, discard_block, next - start);
> +		count += (next - start);
> +		cond_resched();
  Maybe you could cond_resched() after freeing the blocks instead of here?
So that we don't sleep with blocks unnecessarily allocated?

> +
> +free_extent:
> +
> +		freed = 0;
> +		jbd_lock_bh_state(bitmap_bh);
> +
> +		for (bit = start; bit < next; bit++) {
> +
> +			/**
> +			 * @@@ This prevents newly-allocated data from being
> +			 * freed and then reallocated within the same
> +			 * transaction.
> +			 */
> +			BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
> +			J_ASSERT_BH(bitmap_bh,
> +				bh2jh(bitmap_bh)->b_committed_data != NULL);
> +			ext3_set_bit_atomic(sb_bgl_lock(sbi, group), bit,
> +				bh2jh(bitmap_bh)->b_committed_data);
  You don't have to do this. Since you didn't really allocate the blocks
(you are actually never going to commit bitmap changes to the journal)
blocks can be happily reallocated just after you clear the bits in the
bitmap. There's no problem with that. Also you don't have to hold bh_state
lock at all.

> +
> +			/**
> +			 * We clear the bit in the bitmap after setting the
> +			 * committed data bit, because this is the reverse
> +			 * order to that which the allocator uses.
> +			 */
> +			BUFFER_TRACE(bitmap_bh, "clear bit");
> +			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
> +						bit, bitmap_bh->b_data)) {
> +				jbd_unlock_bh_state(bitmap_bh);
> +				ext3_error(sb, __func__,
> +					"bit already cleared for block "E3FSBLK,
> +					 (unsigned long)bit);
> +				jbd_lock_bh_state(bitmap_bh);
> +				BUFFER_TRACE(bitmap_bh, "bit already cleared");
> +			} else {
> +				freed++;
> +			}
> +		}
> +
> +		jbd_unlock_bh_state(bitmap_bh);
> +
> +		/* Update couters */
> +		spin_lock(sb_bgl_lock(sbi, group));
> +		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
> +		spin_unlock(sb_bgl_lock(sbi, group));
> +		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
> +
> +		start = next;
> +
> +		if (signal_pending(current)) {
> +			count = -ERESTARTSYS;
> +			break;
> +		}
> +
> +		/* No more suitable extents */
> +		if ((free_blocks - count) < minblocks)
> +			break;
> +	}
> +
> +	/* We dirtied the bitmap block */
> +	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
> +	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
> +
> +	/* And the group descriptor block */
> +	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
> +	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
> +	if (!err)
> +		err = ret;
> +
> +	ext3_debug("trimmed %d blocks in the group %d\n",
> +		count, group);
> +
> +err_out:
> +	if (err) {
> +		ext3_std_error(sb, err);
> +		count = -err;
> +	}
> +
> +	ext3_journal_stop(handle);
> +	brelse(bitmap_bh);
> +
> +	return count;
> +}
  Otherwise the patch looks OK.

								Honza
-- 
Jan Kara <jack@suse.cz>
SUSE Labs, CR

Re: [PATCH 2/3] Add batched discard support for ext3

[Lukas Czerner]

On Tue, 27 Jul 2010, Jan Kara wrote:

> On Tue 27-07-10 14:41:53, Lukas Czerner wrote:
> > Walk through each allocation group and trim all free extents. It can be
> > invoked through TRIM ioctl on the file system. The main idea is to
> > provide a way to trim the whole file system if needed, since some SSD's
> > may suffer from performance loss after the whole device was filled (it
> > does not mean that fs is full!).
> > 
> > It search for free extents in each allocation group. When the free
> > extent is found, blocks are marked as used and then trimmed. Afterwards
> > these blocks are marked as free in per-group bitmap.
>   Thanks for the patch. It looks much better than the previous one. Some
> comments below.
> 
> > Signed-off-by: Lukas Czerner <lczerner@redhat.com>
> > ---
> >  fs/ext3/balloc.c        |  229 +++++++++++++++++++++++++++++++++++++++++++++++
> >  fs/ext3/super.c         |    1 +
> >  include/linux/ext3_fs.h |    1 +
> >  3 files changed, 231 insertions(+), 0 deletions(-)
> > 
> > diff --git a/fs/ext3/balloc.c b/fs/ext3/balloc.c
> > index a177122..97c6867 100644
> > --- a/fs/ext3/balloc.c
> > +++ b/fs/ext3/balloc.c
> > @@ -20,6 +20,7 @@
> >  #include <linux/ext3_jbd.h>
> >  #include <linux/quotaops.h>
> >  #include <linux/buffer_head.h>
> > +#include <linux/blkdev.h>
> >  
> >  /*
> >   * balloc.c contains the blocks allocation and deallocation routines
> > @@ -1876,3 +1877,231 @@ unsigned long ext3_bg_num_gdb(struct super_block *sb, int group)
> >  	return ext3_bg_num_gdb_meta(sb,group);
> >  
> >  }
> > +
> > +/**
> > + * ext3_trim_all_free -- function to trim all free space in alloc. group
> > + * @sb:			super block for file system
> > + * @group:		allocation group to trim
> > + * @gdp:		allocation group description structure
> > + * @minblocks:		minimum extent block count
> > + *
> > + * ext3_trim_all_free walks through group's block bitmap searching for free
> > + * blocks. When the free block is found, it tries to allocate this block and
> > + * consequent free block to get the biggest free extent possible, until it
> > + * reaches any used block. Then issue a TRIM command on this extent and free
> > + * the extent in the block bitmap. This is done until whole group is scanned.
> > + */
> > +ext3_grpblk_t ext3_trim_all_free(struct super_block *sb,
> > +			unsigned int group, ext3_grpblk_t minblocks)
> > +{
> > +	handle_t *handle;
> > +	ext3_grpblk_t max = EXT3_BLOCKS_PER_GROUP(sb);
> > +	ext3_grpblk_t next, count = 0, start, bit;
> > +	struct ext3_sb_info *sbi;
> > +	ext3_fsblk_t discard_block;
> > +	struct buffer_head *bitmap_bh = NULL;
> > +	struct buffer_head *gdp_bh;
> > +	ext3_grpblk_t free_blocks;
> > +	struct ext3_group_desc *gdp;
> > +	int err = 0, ret;
> > +	ext3_grpblk_t freed;
> > +
> > +	/**
> > +	 * We will update one block bitmap, and one group descriptor
> > +	 */
> > +	handle = ext3_journal_start_sb(sb, 2);
> > +	if (IS_ERR(handle)) {
> > +		err = PTR_ERR(handle);
> > +		ext3_warning(sb, __func__, "error %d on journal start", err);
>   I think there's no need to issue another warning here... When
> journal_start fails there should be notices about this in the log already.

That's right, thanks.

> 
> > +		return err;
> > +	}
> > +
> > +	bitmap_bh = read_block_bitmap(sb, group);
> > +	if (!bitmap_bh)
> > +		goto err_out;
> > +
> > +	BUFFER_TRACE(bitmap_bh, "getting undo access");
> > +	err = ext3_journal_get_undo_access(handle, bitmap_bh);
> > +	if (err)
> > +		goto err_out;
> > +
> > +	gdp = ext3_get_group_desc(sb, group, &gdp_bh);
> > +	if (!gdp)
> > +		goto err_out;
> > +
> > +	BUFFER_TRACE(gd_bh, "get_write_access");
> > +	err = ext3_journal_get_write_access(handle, gdp_bh);
> > +	if (err)
> > +		goto err_out;
> > +
> > +	free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
> > +	sbi = EXT3_SB(sb);
> > +
> > +	 /* Walk through the whole group */
> > +	start = 0;
> > +	while (start < max) {
> > +
> > +		start = bitmap_search_next_usable_block(start, bitmap_bh, max);
> > +		if (start < 0)
> > +			break;
> > +		next = start;
> > +
> > +		/**
>                 ^^^ Use just /*. /** is reserved for comments processed by
>   kernel documentation generator and they have to have special format...

Ok.

> 
> > +		 * Allocate contiguous free extents by setting bits in the
> > +		 * block bitmap
> > +		 */
> > +		while (next < max
> > +			&& claim_block(sb_bgl_lock(sbi, group),
> > +					next, bitmap_bh)) {
> > +			next++;
> > +		}
> > +
> > +		 /* We did not claimed any blocks */
>                                ^^^^ claim

Oh, that is my astonishing English skills ;). Thanks.

> 
> > +		if (next == start)
> > +			continue;
> > +
> > +		discard_block = (ext3_fsblk_t)start +
> > +				ext3_group_first_block_no(sb, group);
> > +
> > +		/* Update counters */
> > +		spin_lock(sb_bgl_lock(sbi, group));
> > +		le16_add_cpu(&gdp->bg_free_blocks_count, start - next);
> > +		spin_unlock(sb_bgl_lock(sbi, group));
> > +		percpu_counter_sub(&sbi->s_freeblocks_counter, next - start);
> > +
> > +		/* Do not issue a TRIM on extents smaller than minblocks */
> > +		if ((next - start) < minblocks)
> > +			goto free_extent;
> > +
> > +		 /* Send the TRIM command down to the device */
> > +		sb_issue_discard(sb, discard_block, next - start);
> > +		count += (next - start);
> > +		cond_resched();
>   Maybe you could cond_resched() after freeing the blocks instead of here?
> So that we don't sleep with blocks unnecessarily allocated?

Of course, that would be better.

> 
> > +
> > +free_extent:
> > +
> > +		freed = 0;
> > +		jbd_lock_bh_state(bitmap_bh);
> > +
> > +		for (bit = start; bit < next; bit++) {
> > +
> > +			/**
> > +			 * @@@ This prevents newly-allocated data from being
> > +			 * freed and then reallocated within the same
> > +			 * transaction.
> > +			 */
> > +			BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
> > +			J_ASSERT_BH(bitmap_bh,
> > +				bh2jh(bitmap_bh)->b_committed_data != NULL);
> > +			ext3_set_bit_atomic(sb_bgl_lock(sbi, group), bit,
> > +				bh2jh(bitmap_bh)->b_committed_data);
>   You don't have to do this. Since you didn't really allocate the blocks
> (you are actually never going to commit bitmap changes to the journal)
> blocks can be happily reallocated just after you clear the bits in the
> bitmap. There's no problem with that. Also you don't have to hold bh_state
> lock at all.

Thanks.

> 
> > +
> > +			/**
> > +			 * We clear the bit in the bitmap after setting the
> > +			 * committed data bit, because this is the reverse
> > +			 * order to that which the allocator uses.
> > +			 */
> > +			BUFFER_TRACE(bitmap_bh, "clear bit");
> > +			if (!ext3_clear_bit_atomic(sb_bgl_lock(sbi, group),
> > +						bit, bitmap_bh->b_data)) {
> > +				jbd_unlock_bh_state(bitmap_bh);
> > +				ext3_error(sb, __func__,
> > +					"bit already cleared for block "E3FSBLK,
> > +					 (unsigned long)bit);
> > +				jbd_lock_bh_state(bitmap_bh);
> > +				BUFFER_TRACE(bitmap_bh, "bit already cleared");
> > +			} else {
> > +				freed++;
> > +			}
> > +		}
> > +
> > +		jbd_unlock_bh_state(bitmap_bh);
> > +
> > +		/* Update couters */
> > +		spin_lock(sb_bgl_lock(sbi, group));
> > +		le16_add_cpu(&gdp->bg_free_blocks_count, freed);
> > +		spin_unlock(sb_bgl_lock(sbi, group));
> > +		percpu_counter_add(&sbi->s_freeblocks_counter, next - start);
> > +
> > +		start = next;
> > +
> > +		if (signal_pending(current)) {
> > +			count = -ERESTARTSYS;
> > +			break;
> > +		}
> > +
> > +		/* No more suitable extents */
> > +		if ((free_blocks - count) < minblocks)
> > +			break;
> > +	}
> > +
> > +	/* We dirtied the bitmap block */
> > +	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
> > +	err = ext3_journal_dirty_metadata(handle, bitmap_bh);
> > +
> > +	/* And the group descriptor block */
> > +	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");
> > +	ret = ext3_journal_dirty_metadata(handle, gdp_bh);
> > +	if (!err)
> > +		err = ret;
> > +
> > +	ext3_debug("trimmed %d blocks in the group %d\n",
> > +		count, group);
> > +
> > +err_out:
> > +	if (err) {
> > +		ext3_std_error(sb, err);
> > +		count = -err;
> > +	}
> > +
> > +	ext3_journal_stop(handle);
> > +	brelse(bitmap_bh);
> > +
> > +	return count;
> > +}
>   Otherwise the patch looks OK.

Great, thanks for looking at this. I will resend the patch shortly.

> 
> 								Honza
> 

-Lukas