Ext4: batched discard support

Create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents.

Signed-off-by Lukas Czerner <[email protected]>

---
 fs/ext4/ext4.h    |    4 +
 fs/ext4/mballoc.c |  207 ++++++++++++++++++++++++++++++++++++++++++++++++++--- fs/ext4/super.c   |    1 +

 3 files changed, 202 insertions(+), 10 deletions(-)

fs/ext4/ext4.h +4 -0

index bf938cf..e25f672 100644
@@ -1437,6 +1437,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(unsigned int, struct super_block *);
+
  /* inode.c */
  struct buffer_head *ext4_getblk(handle_t *, struct inode *,
                                                ext4_lblk_t, int, int *);

@@ -1682,6 +1684,8 @@ struct ext4_group_info {
  #ifdef DOUBLE_CHECK
        void            *bb_bitmap;
  #endif
+       void            *bb_bitmap_deleted;
+       ext4_grpblk_t   bb_deleted;
        struct rw_semaphore alloc_sem;

       ext4_grpblk_t   bb_counters[];  /* Nr of free power-of-two-block
                                        * regions, index is order.

fs/ext4/mballoc.c +52 -10

index bde9d0b..fbc83fe 100644
@@ -2255,6 +2255,9 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
        INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
        init_rwsem(&meta_group_info[i]->alloc_sem);
        meta_group_info[i]->bb_free_root = RB_ROOT;
+       meta_group_info[i]->bb_deleted = -1;
+
+
 
  #ifdef DOUBLE_CHECK
        {

@@ -2469,6 +2472,7 @@ int ext4_mb_release(struct super_block *sb)
  #ifdef DOUBLE_CHECK
                        kfree(grinfo->bb_bitmap);
  #endif
+                       kfree(grinfo->bb_bitmap_deleted);
                        ext4_lock_group(sb, i);
                        ext4_mb_cleanup_pa(grinfo);
                        ext4_unlock_group(sb, i);

@@ -2528,6 +2532,7 @@ static void release_blocks_on_commit(journal_t *journal, transaction_t *txn)
        int err, count = 0, count2 = 0;
        struct ext4_free_data *entry;
        struct list_head *l, *ltmp;
+       void *bitmap_deleted = NULL;
 
        list_for_each_safe(l, ltmp, &txn->t_private_list) {
                entry = list_entry(l, struct ext4_free_data, list);

@@ -2543,6 +2548,14 @@ static void release_blocks_on_commit(journal_t *journal, transaction_t *txn)
                /* there are blocks to put in buddy to make them really free */
                count += entry->count;
                count2++;
+
+               if (test_opt(sb, DISCARD) &&
+                       (db->bb_bitmap_deleted == NULL) &&
+                       (db->bb_deleted >= 0)) {
+                       bitmap_deleted =
+                               kmalloc(sb->s_blocksize, GFP_KERNEL);
+               }
+
                ext4_lock_group(sb, entry->group);
                /* Take it out of per group rb tree */
                rb_erase(&entry->node, &(db->bb_free_root));

@@ -2555,17 +2568,24 @@ static void release_blocks_on_commit(journal_t *journal, transaction_t *txn)
                        page_cache_release(e4b.bd_buddy_page);
                        page_cache_release(e4b.bd_bitmap_page);
                }
-               ext4_unlock_group(sb, entry->group);
-               if (test_opt(sb, DISCARD)) {
-                       ext4_fsblk_t discard_block;
-
-                       discard_block = entry->start_blk +
-                               ext4_group_first_block_no(sb, entry->group);
-                       trace_ext4_discard_blocks(sb,
-                                       (unsigned long long)discard_block,
-                                       entry->count);
-                       sb_issue_discard(sb, discard_block, entry->count);
+               if (test_opt(sb, DISCARD) && (db->bb_deleted >= 0)) {
+                       if (db->bb_bitmap_deleted == NULL) {
+                               db->bb_bitmap_deleted = bitmap_deleted;
+                               BUG_ON(db->bb_bitmap_deleted == NULL);
+
+                               bitmap_deleted = NULL;
+                               mb_clear_bits(db->bb_bitmap_deleted,
+                                       0, EXT4_BLOCKS_PER_GROUP(sb));
+                       }
+
+                       db->bb_deleted += entry->count;
+                       mb_set_bits(db->bb_bitmap_deleted, entry->start_blk,
+                                entry->count);
                }
+               ext4_unlock_group(sb, entry->group);
+
+               kfree(bitmap_deleted);
+
                kmem_cache_free(ext4_free_ext_cachep, entry);
                ext4_mb_release_desc(&e4b);
        }

@@ -4639,3 +4659,170 @@ error_return:
                kmem_cache_free(ext4_ac_cachep, ac);
        return;
  }
+
+/* Trim "count" blocks starting at "start" in "group"
+ * This must be called under group lock
+ */
+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       mb_mark_used(e4b, &ex);
+       ext4_unlock_group(sb, group);
+
+       discard_block = (ext4_fsblk_t)group *
+                       EXT4_BLOCKS_PER_GROUP(sb)

fs/ext4/mballoc.c +135 -0

+
+/* Trim all free blocks, which have at least minlen length */
+ext4_grpblk_t ext4_trim_all_free(struct super_block *sb, struct ext4_buddy *e4b,
+               ext4_grpblk_t minblocks)
+{
+       void *bitmap;
+       ext4_grpblk_t max = EXT4_BLOCKS_PER_GROUP(sb);
+       ext4_grpblk_t start, next, count = 0;
+       ext4_group_t group;
+
+       BUG_ON(e4b == NULL);
+
+       bitmap = e4b->bd_bitmap;
+       group = e4b->bd_group;
+       start = 0;
+       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) {
+
+                       count += next - start;
+                       ext4_trim_extent(sb, start,
+                               next - start, group, e4b);
+
+               }
+               start = next + 1;
+       }
+
+       e4b->bd_info->bb_deleted = 0;
+       ext4_unlock_group(sb, group);
+
+       return count;
+}
+
+/* Trim only blocks which is free and in bb_bitmap_deleted */
+ext4_grpblk_t ext4_trim_deleted(struct super_block *sb, struct ext4_buddy *e4b,
+               ext4_grpblk_t minblocks)
+{
+       void *bitmap;
+       struct ext4_group_info *grp;
+       ext4_group_t group;
+       ext4_grpblk_t max, next, count = 0, start = 0;
+
+       BUG_ON(e4b == NULL);
+
+       bitmap = e4b->bd_bitmap;
+       group = e4b->bd_group;
+       grp = ext4_get_group_info(sb, group);
+
+       if (grp->bb_deleted < minblocks)
+               return 0;
+
+       ext4_lock_group(sb, group);
+
+       while (start < EXT4_BLOCKS_PER_GROUP(sb)) {
+               start = mb_find_next_bit(grp->bb_bitmap_deleted,
+                       EXT4_BLOCKS_PER_GROUP(sb), start);
+               max = mb_find_next_zero_bit(grp->bb_bitmap_deleted,
+                       EXT4_BLOCKS_PER_GROUP(sb), start);
+
+               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 > max)
+                               next = max;
+
+                       if ((next - start) >= minblocks) {
+                               count += next - start;
+
+                               ext4_trim_extent(sb, start,
+                                       next - start, group, e4b);
+
+                               mb_clear_bits(grp->bb_bitmap_deleted,
+                                       start, next - start);
+                       }
+                       start = next + 1;
+               }
+       }
+       grp->bb_deleted -= count;
+
+       ext4_unlock_group(sb, group);
+
+       ext4_debug("trimmed %d blocks in the group %d\n",
+               count, group);
+
+       return count;
+}
+
+int ext4_trim_fs(unsigned int minlen, struct super_block *sb)
+{
+       struct ext4_buddy e4b;
+       struct ext4_group_info *grp;
+       ext4_group_t group;
+       ext4_group_t ngroups = ext4_get_groups_count(sb);
+       ext4_grpblk_t minblocks;
+
+       if (!test_opt(sb, DISCARD))
+               return 0;
+
+       minblocks = DIV_ROUND_UP(minlen, sb->s_blocksize);
+       if (unlikely(minblocks > EXT4_BLOCKS_PER_GROUP(sb)))
+               return -EINVAL;
+
+       for (group = 0; group < ngroups; group++) {
+               int err;
+
+               err = ext4_mb_load_buddy(sb, group, &e4b);
+               if (err) {
+                       ext4_error(sb, "Error in loading buddy "
+                                       "information for %u", group);
+                       continue;
+               }
+               grp = ext4_get_group_info(sb, group);
+
+               if (grp->bb_deleted < 0) {
+                       /* First run after mount */
+                       ext4_trim_all_free(sb, &e4b, minblocks);
+               } else if (grp->bb_deleted >= minblocks) {
+                       /* Trim only blocks deleted since first run */
+                       ext4_trim_deleted(sb, &e4b, minblocks);
+               }
+
+               ext4_mb_release_desc(&e4b);
+       }
+
+       return 0;
+}

fs/ext4/super.c +1 -1

index e14d22c..253eb98 100644
@@ -1109,6 +1109,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.6.6.1

Mark,

This is the patch implementing the new discard logic.

Signed-off-by Lukas Czerner <[email protected]>

Quoted 26 lines

fs/ext4/mballoc.c +26 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       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);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);

Review

Quoted 2 lines

(quoted diff) +2 -0

+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range. I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner <[email protected]>

..

Quoted 26 lines

Quoted 26 lines

fs/ext4/mballoc.c +26 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       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);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);

Quoted 8 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range. I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Lukas ?

Quoted 47 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner <[email protected]>

..

Quoted 26 lines

Quoted 26 lines

fs/ext4/mballoc.c +26 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       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);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);

Quoted 8 lines

Quoted 2 lines

+       mb_free_blocks(NULL, e4b, start, ex.fe_len); +}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range.  I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Quoted 1 line

Lukas ?

I'm confused; do we have an interface to send a trim command for multiple ranges?

I didn't think so ...  Lukas' patch is finding free ranges (above a size threshold) to discard; it's not doing it a block at a time, if that's the concern.

-Eric

Quoted 55 lines · Eric Sandeen

Quoted 41 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner<[email protected]>

..

Quoted 26 lines

Quoted 26 lines

fs/ext4/mballoc.c +26 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       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);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);

Quoted 8 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range. I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 7 lines

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Lukas ?

I'm confused; do we have an interface to send a trim command for multiple ranges?

I didn't think so ... Lukas' patch is finding free ranges (above a size threshold) to discard; it's not doing it a block at a time, if that's the concern.

Quoted 1 line

-Eric

Eric,

I don't know what kernel APIs have been created to support discard, but the ATA8 draft spec. allows for specifying multiple ranges in one trim command.

Quoted 43 lines · Greg Freemyer

Quoted 42 lines · Eric Sandeen

Quoted 41 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner<[email protected]>

..

Quoted 34 lines

Quoted 18 lines

fs/ext4/mballoc.c +18 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       mb_mark_used(e4b,&ex);
+       ext4_unlock_group(sb, group);
+
+       discard_block = (ext4_fsblk_t)group *
+                       EXT4_BLOCKS_PER_GROUP(sb)

fs/ext4/mballoc.c error_return: · line 4693

Quoted 10 lines

fs/ext4/mballoc.c +10 -0

+                       + start
+                       + le32_to_cpu(es->s_first_data_block);
+       trace_ext4_discard_blocks(sb,
+                       (unsigned long long)discard_block,
+                       count);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);
+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range. I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Quoted 7 lines

Quoted 7 lines

Quoted 1 line

Lukas ?

I'm confused; do we have an interface to send a trim command for multiple ranges?

I didn't think so ... Lukas' patch is finding free ranges (above a size threshold) to discard; it's not doing it a block at a time, if that's the concern.

Quoted 7 lines

Quoted 1 line

-Eric

Eric,

I don't know what kernel APIs have been created to support discard, but the ATA8 draft spec. allows for specifying multiple ranges in one trim command.

Greg,

We have full support for this in the "discard" support at the file system layer for several file systems.

The block layer effectively muxes the "discard" into the right target device command. TRIM for ATA, WRITE_SAME (with unmap) or UNMAP for SCSI...

If your favourite fs supports this, you can enable this feature with "-o
discard" for fine grained discards,

From the file system, you want to discard discrete ranges of blocks.

Quoted 44 lines · Ric Wheeler

Quoted 43 lines · Greg Freemyer

Quoted 42 lines · Eric Sandeen

Quoted 41 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner<[email protected]>

..

Quoted 34 lines

Quoted 18 lines

(quoted diff) +18 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       mb_mark_used(e4b,&ex);
+       ext4_unlock_group(sb, group);
+
+       discard_block = (ext4_fsblk_t)group *
+                       EXT4_BLOCKS_PER_GROUP(sb)

Review

Quoted 10 lines

(quoted diff) +10 -0

+                       + start
+                       + le32_to_cpu(es->s_first_data_block);
+       trace_ext4_discard_blocks(sb,
+                       (unsigned long long)discard_block,
+                       count);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);
+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range.  I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Except it doesn't.  Lukas did provide numbers in his original email.

Quoted 46 lines · Jeff Moyer

Quoted 44 lines · Ric Wheeler

Quoted 43 lines · Greg Freemyer

Quoted 42 lines · Eric Sandeen

Quoted 41 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner<[email protected]>

..

Quoted 34 lines

Quoted 18 lines

(quoted diff) +18 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       mb_mark_used(e4b,&ex);
+       ext4_unlock_group(sb, group);
+
+       discard_block = (ext4_fsblk_t)group *
+                       EXT4_BLOCKS_PER_GROUP(sb)

Review

Quoted 10 lines

(quoted diff) +10 -0

+                       + start
+                       + le32_to_cpu(es->s_first_data_block);
+       trace_ext4_discard_blocks(sb,
+                       (unsigned long long)discard_block,
+                       count);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);
+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range.  I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 8 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Except it doesn't.  Lukas did provide numbers in his original email.

Looking at the benchmarks (for the first time) at
http://people.redhat.com/jmoyer/discard/ext4_batched_discard/

I don't see anything that says how long the proposed trim ioctl takes to complete on the full filesystem.

What they do show is that with the 3 test SSDs used for this benchmark, the current released discard implementation is a net loss. ie. You are better off running without the discards for all 3 vendors. (at least under the conditions tested.)

After the patch is applied and optimizing the discards to large free extents only, it works out to same performance with or without the discards.  ie. no net gain or loss.

That is extremely cool because one assumes that the non-discard case would degrade over time, but that the discard case will not.

So that argues for the current proposed patch going in.

But quoting from the first email:

==
The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further. ==

The above seems to argue against the patch going in until the mount/umount issues are addressed.

So in addition to this patch, Lukas is proposing a on disk change to address the fact that calling trim upteen times at mount time is too slow.

Per Mark's testing of last summer, an alternative solution is to use a vectored trim approach that is far more efficient.

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Greg

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Quoted 3 lines · Greg Freemyer

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

All the other things aside, mount-time is interesting, but it's an infrequent operation, at least in my world. I think we need something that can be done runtime.

For anything with uptime, I don't think it's acceptable to wait until the next mount to trim unused blocks.

But as long as the mechanism can be called either at mount time and/or kicked off runtime somehow, I'm happy.

-Eric

Quoted 13 lines · Eric Sandeen

Quoted 4 lines · Greg Freemyer

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

All the other things aside, mount-time is interesting, but it's an infrequent operation, at least in my world.  I think we need something that can be done runtime.

Quoted 8 lines

For anything with uptime, I don't think it's acceptable to wait until the next mount to trim unused blocks.

But as long as the mechanism can be called either at mount time and/or kicked off runtime somehow, I'm happy.

-Eric

That makes sense to me.  Most enterprise servers will go without remounting a file system for (hopefully!) a very long time.

It is really important to keep in mind that this is not just a laptop feature for laptop SSD's, this is also used by high end arrays and *could* be useful for virt IO, etc as well :-)

ric

Adding James Bottomley because high-end scsi is entering the discussion. James, I have a couple scsi questions for you at the end.

Quoted 16 lines · Ric Wheeler

Quoted 15 lines · Eric Sandeen

Quoted 4 lines · Greg Freemyer

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

All the other things aside, mount-time is interesting, but it's an infrequent operation, at least in my world. I think we need something that can be done runtime.

For anything with uptime, I don't think it's acceptable to wait until the next mount to trim unused blocks.

Quoted 6 lines

Quoted 5 lines

But as long as the mechanism can be called either at mount time and/or kicked off runtime somehow, I'm happy.

-Eric

Quoted 8 lines

That makes sense to me. Most enterprise servers will go without remounting a file system for (hopefully!) a very long time.

It is really important to keep in mind that this is not just a laptop feature for laptop SSD's, this is also used by high end arrays and *could* be useful for virt IO, etc as well :-)

ric

I'm not arguing that a runtime solution is not needed.

I'm arguing that at least for SSD backed filesystems Mark's userspace implementation shows how the mount time initialization of the runtime bitmap can be accomplished in a few seconds by leveraging the hardware and using vector'ed trims as opposed to having to build an additional on-disk structure.

At least for SSDs, the primary purpose of the proposed on-disk structure seems to be to overcome the current lack of a vector'ed discard implementation.

If it is too difficult to implement a fully functional vector'ed discard in the block layer due to locking issues, possibly a special purpose version could be written that is only used at mount time when one can be assured no other i/o is occurring to the filesystem.

James,

The ATA-8 spec. supports vectored trims and requires a minimum of 255 sectors worth of range payload be supported. That equates to a single trim being able to trim thousands of ranges in one command.

Mark Lord has benchmarked in found a vectored trim to be drastically faster than calling trim individually for each of those ranges.

Does scsi support vector'ed discard? (ie. write-same commands)

Or are high-end scsi arrays so fast they can process tens of thousands of discard commands in a reasonable amount of time, unlike the SSDs have so far proven to do.

It would be interesting to find out that a SSD can discard thousands of ranges drastically faster than a high-end scsi device can. But if true, that might argue for the on-disk bitmap to track previously discarded blocks/extents.

The ATA-8 spec. supports vectored trims and requires a minimum of 255 sectors worth of range payload be supported. That equates to a single trim being able to trim thousands of ranges in one command.

Mark Lord has benchmarked in found a vectored trim to be drastically faster than calling trim individually for each of those ranges.

Quoted 4 lines

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Quoted 2 lines

Except it doesn't.  Lukas did provide numbers in his original email.

Looking at the benchmarks (for the first time) at
http://people.redhat.com/jmoyer/discard/ext4_batched_discard/

I don't see anything that says how long the proposed trim ioctl takes to complete on the full filesystem.

What they do show is that with the 3 test SSDs used for this benchmark, the current released discard implementation is a net loss. ie. You are better off running without the discards for all 3 vendors.
(at least under the conditions tested.)

After the patch is applied and optimizing the discards to large free extents only, it works out to same performance with or without the discards. ie. no net gain or loss.

That is extremely cool because one assumes that the non-discard case would degrade over time, but that the discard case will not.

So that argues for the current proposed patch going in.

But quoting from the first email:

==
The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further. ==

The above seems to argue against the patch going in until the mount/umount issues are addressed.

So in addition to this patch, Lukas is proposing a on disk change to address the fact that calling trim upteen times at mount time is too slow.

Per Mark's testing of last summer, an alternative solution is to use a vectored trim approach that is far more efficient.

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Greg

Quoted 4 lines · Greg Freemyer

Quoted 4 lines

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Quoted 8 lines

Quoted 2 lines

Except it doesn't.  Lukas did provide numbers in his original email.

Looking at the benchmarks (for the first time) at
http://people.redhat.com/jmoyer/discard/ext4_batched_discard/

I don't see anything that says how long the proposed trim ioctl takes to complete on the full filesystem.

Well, it strongly depends on how is the file system fragmented. On the fresh file system (147G) the initial ioctl takes 2 seconds to finish (it may be worth to mention that on another SSD (111G) it takes 56s). I will try to get some numbers for the "usual" file system (not full, not fresh).

Quoted 42 lines

What they do show is that with the 3 test SSDs used for this benchmark, the current released discard implementation is a net loss. ie. You are better off running without the discards for all 3 vendors. (at least under the conditions tested.)

After the patch is applied and optimizing the discards to large free extents only, it works out to same performance with or without the discards.  ie. no net gain or loss.

That is extremely cool because one assumes that the non-discard case would degrade over time, but that the discard case will not.

So that argues for the current proposed patch going in.

But quoting from the first email:

==
The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further. ==

Quoted 2 lines

The above seems to argue against the patch going in until the mount/umount issues are addressed.

I do not know much about how production system is being used, but I doubt this is that big issue. Sure the initial ioctl takes long to finish and there is a place for improvement, there was a proposal to do the initial trim at mount time. I do not think that it is wise, why to block mount, when the trim can be run at background when the fs is mounted ? Of course there will be some performance loss, while ioctl will be in progress, but it will not block.

There are also another way to overcome this problem. We can assure that the file system is left trimmed after umount. To do this, we can simply trim the fs at umount time. I think this won't be any problem and we even do not prolong the umount time too much, because we will not trim whole fs, but just recently freed blocks.

This of course bring another problem, when the system is not properly terminated and the umount is not properly finished (or done at all). But this can be solved in fsck at boot time I think. This will entirely eliminate the need to trim the whole fs (except the fsck obviously), since it is done when fs is created.

Quoted 7 lines

So in addition to this patch, Lukas is proposing a on disk change to address the fact that calling trim upteen times at mount time is too slow.

Per Mark's testing of last summer, an alternative solution is to use a vectored trim approach that is far more efficient.

Vectored trim will be great, I did not tested anything like that but obviously it will strongly reduce time needed to trim the fs. But we do not have this support just yet.

Quoted 6 lines

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Greg

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 107 lines · Lukas Czerner

Quoted 4 lines · Greg Freemyer

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Quoted 9 lines

Quoted 3 lines

Except it doesn't. Lukas did provide numbers in his original email.

Looking at the benchmarks (for the first time) at
http://people.redhat.com/jmoyer/discard/ext4_batched_discard/

I don't see anything that says how long the proposed trim ioctl takes to complete on the full filesystem.

Well, it strongly depends on how is the file system fragmented. On the fresh file system (147G) the initial ioctl takes 2 seconds to finish (it may be worth to mention that on another SSD (111G) it takes 56s). I will try to get some numbers for the "usual" file system (not full, not fresh).

Quoted 41 lines

What they do show is that with the 3 test SSDs used for this benchmark, the current released discard implementation is a net loss. ie. You are better off running without the discards for all 3 vendors.
(at least under the conditions tested.)

After the patch is applied and optimizing the discards to large free extents only, it works out to same performance with or without the discards. ie. no net gain or loss.

That is extremely cool because one assumes that the non-discard case would degrade over time, but that the discard case will not.

So that argues for the current proposed patch going in.

But quoting from the first email:

==
The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further. ==

Quoted 3 lines

The above seems to argue against the patch going in until the mount/umount issues are addressed.

I do not know much about how production system is being used, but I doubt this is that big issue. Sure the initial ioctl takes long to finish and there is a place for improvement, there was a proposal to do the initial trim at mount time. I do not think that it is wise, why to block mount, when the trim can be run at background when the fs is mounted ? Of course there will be some performance loss, while ioctl will be in progress, but it will not block.

There are also another way to overcome this problem. We can assure that the file system is left trimmed after umount. To do this, we can simply trim the fs at umount time. I think this won't be any problem and we even do not prolong the umount time too much, because we will not trim whole fs, but just recently freed blocks.

This of course bring another problem, when the system is not properly terminated and the umount is not properly finished (or done at all). But this can be solved in fsck at boot time I think. This will entirely eliminate the need to trim the whole fs (except the fsck obviously), since it is done when fs is created.

Quoted 7 lines

So in addition to this patch, Lukas is proposing a on disk change to address the fact that calling trim upteen times at mount time is too slow.

Per Mark's testing of last summer, an alternative solution is to use a vectored trim approach that is far more efficient.

Vectored trim will be great, I did not tested anything like that but obviously it will strongly reduce time needed to trim the fs. But we do not have this support just yet.

Quoted 6 lines

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Greg

Quoted 7 lines

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

I know I've been arguing against this patch for the single SSD case and I still think that use case should be handled by userspace as hdparm/wiper.sh currently does. In particular for those extreme scenarios with JBOD SSDs, the user space solution wins because it knows how to optimize the trim calls via vectorized ranges in the payload.

Thus I think the community and distro's should be testing that pair and pushing it out in the distro's for typical laptop use.

But, that still leaves high-end external raid arrays, mdraid, and lvm unaddressed.

Those use cases will likely benefit from the approach this patch takes the most. In particular, mdraid with raid 5/6 requires an approach like this patch provides, or it has to create its own in kernel discard aggregator which seems like a waste of time.

In general, those use cases have large minimum discard units. Thus I think this patch should be tuned to work with large discard units and ignore small ones. That means it needs to get the underlying block layer topology and ignore unused space smaller than underlying layers minimum discard unit. That should allow a rb tree to be used and eliminate the extreme scenarios. (ie. I assume your extreme scenarios involve large numbers of very small unused ranges.)

That may mean the topology information needs to grow some discard info. Does anyone know if that info is easily derived from the currently existing topo info?

Greg

Quoted 130 lines · Greg Freemyer

Quoted 118 lines · Lukas Czerner

Quoted 10 lines · Greg Freemyer

Quoted 9 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Except it doesn't.  Lukas did provide numbers in his original email.

Quoted 6 lines

Looking at the benchmarks (for the first time) at
http://people.redhat.com/jmoyer/discard/ext4_batched_discard/

I don't see anything that says how long the proposed trim ioctl takes to complete on the full filesystem.

Well, it strongly depends on how is the file system fragmented. On the fresh file system (147G) the initial ioctl takes 2 seconds to finish (it may be worth to mention that on another SSD (111G) it takes 56s). I will try to get some numbers for the "usual" file system (not full, not fresh).

Quoted 43 lines

What they do show is that with the 3 test SSDs used for this benchmark, the current released discard implementation is a net loss. ie. You are better off running without the discards for all 3 vendors. (at least under the conditions tested.)

After the patch is applied and optimizing the discards to large free extents only, it works out to same performance with or without the discards.  ie. no net gain or loss.

That is extremely cool because one assumes that the non-discard case would degrade over time, but that the discard case will not.

So that argues for the current proposed patch going in.

But quoting from the first email:

==
The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further. ==

Quoted 3 lines

The above seems to argue against the patch going in until the mount/umount issues are addressed.

I do not know much about how production system is being used, but I doubt this is that big issue. Sure the initial ioctl takes long to finish and there is a place for improvement, there was a proposal to do the initial trim at mount time. I do not think that it is wise, why to block mount, when the trim can be run at background when the fs is mounted ? Of course there will be some performance loss, while ioctl will be in progress, but it will not block.

There are also another way to overcome this problem. We can assure that the file system is left trimmed after umount. To do this, we can simply trim the fs at umount time. I think this won't be any problem and we even do not prolong the umount time too much, because we will not trim whole fs, but just recently freed blocks.

This of course bring another problem, when the system is not properly terminated and the umount is not properly finished (or done at all). But this can be solved in fsck at boot time I think. This will entirely eliminate the need to trim the whole fs (except the fsck obviously), since it is done when fs is created.

Quoted 8 lines

So in addition to this patch, Lukas is proposing a on disk change to address the fact that calling trim upteen times at mount time is too slow.

Per Mark's testing of last summer, an alternative solution is to use a vectored trim approach that is far more efficient.

Vectored trim will be great, I did not tested anything like that but obviously it will strongly reduce time needed to trim the fs. But we do not have this support just yet.

Quoted 7 lines

Mark's benchmarks showed this as doable in seconds which seems like a reasonable amount of time for a mount time operation.

Greg

Quoted 7 lines

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 7 lines

I know I've been arguing against this patch for the single SSD case and I still think that use case should be handled by userspace as hdparm/wiper.sh currently does.  In particular for those extreme scenarios with JBOD SSDs, the user space solution wins because it knows how to optimize the trim calls via vectorized ranges in the payload.

I think that you have missed the broader point. This is not on by default, so you can mount without discard and use whatever user space utility you like at your discretion.

ric

Quoted 1 line · Ric Wheeler

On 04/24/2010 09:24 AM, Greg Freemyer wrote:

Quoted 7 lines

Quoted 7 lines

I know I've been arguing against this patch for the single SSD case and I still think that use case should be handled by userspace as hdparm/wiper.sh currently does. In particular for those extreme scenarios with JBOD SSDs, the user space solution wins because it knows how to optimize the trim calls via vectorized ranges in the payload.

Quoted 5 lines

I think that you have missed the broader point. This is not on by default, so you can mount without discard and use whatever user space utility you like at your discretion.

ric

Ric,

I was trying to say the design should be driven by the large discard range use case, not the potentially pathological small discard range use case that would only benefit SSDs.

Greg

Quoted 2 lines · Greg Freemyer

Quoted 1 line · Ric Wheeler

On 04/24/2010 09:24 AM, Greg Freemyer wrote:

...

Quoted 13 lines

Quoted 7 lines

Quoted 7 lines

I know I've been arguing against this patch for the single SSD case and I still think that use case should be handled by userspace as hdparm/wiper.sh currently does.  In particular for those extreme scenarios with JBOD SSDs, the user space solution wins because it knows how to optimize the trim calls via vectorized ranges in the payload.

Quoted 5 lines

I think that you have missed the broader point. This is not on by default, so you can mount without discard and use whatever user space utility you like at your discretion.

ric

Quoted 7 lines

Ric,

I was trying to say the design should be driven by the large discard range use case, not the potentially pathological small discard range use case that would only benefit SSDs.

Greg

Bear in mind that this patch makes the discard range requests substantially -larger- than what mount -o discard does on ext4 today, in fact that was a main goal.

If the kernel could assemble vectors of ranges and pass them down, I think it could be extended to use that as well.

-Eric

Quoted 31 lines · Eric Sandeen

Quoted 4 lines · Greg Freemyer

Quoted 2 lines · Ric Wheeler

On 04/24/2010 09:24 AM, Greg Freemyer wrote:

...

Quoted 14 lines

Quoted 8 lines

Quoted 8 lines

I know I've been arguing against this patch for the single SSD case and I still think that use case should be handled by userspace as hdparm/wiper.sh currently does. In particular for those extreme scenarios with JBOD SSDs, the user space solution wins because it knows how to optimize the trim calls via vectorized ranges in the payload.

Quoted 6 lines

I think that you have missed the broader point. This is not on by default, so you can mount without discard and use whatever user space utility you like at your discretion.

ric

Quoted 8 lines

Ric,

I was trying to say the design should be driven by the large discard range use case, not the potentially pathological small discard range use case that would only benefit SSDs.

Greg

Quoted 10 lines

Bear in mind that this patch makes the discard range requests substantially -larger- than what mount -o discard does on ext4 today, in fact that was a main goal.

If the kernel could assemble vectors of ranges and pass them down, I think it could be extended to use that as well.

-Eric

Eric/Ric,

I was responding to the Lukas latest post which stated:

==
And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?
==

If one optimizes for large discard ranges and ignores the pathological cases only beneficial to SSDs, then a rbtree wins.

Correct?

Greg

Let's summarize.

1. Everyone agrees that doing larger discard instead of little discards is a good thing.

2. Some devices care about this more than others (various types of SSD's and arrays have different designs and performance with discards). Some devices do small discards well, others don't.

3. How you get to those bigger discards in our implementation - using a series of single range requests, using vectored requests, tracking extents that can be combined in an rbtree or not - is something that we are working on. Using rbtrees versus a bitmap efficiency is about DRAM consumption, not performance of the resulting discard on the target.

4. Devices (some devices) can export their preferences in a standard way (look in /sys/block/....).

If you want to influence the code, please do try the various options on devices you have at hand and report results.  That is what we are doing (we includes Lukas, Eric, Jeff and others on this thread) will real devices from vendors that have given us access. We are talking to them directly and trying out different work loads but certainly welcome real world results and suggestions.

Thanks!

Ric

On Sat, Apr 24, 2010 at 1:04 PM, Ric Wheeler<[email protected]> wrote:
<snip>

Quoted 25 lines

Let's summarize.

1. Everyone agrees that doing larger discard instead of little discards is a good thing.

2. Some devices care about this more than others (various types of SSD's and arrays have different designs and performance with discards). Some devices do small discards well, others don't.

3. How you get to those bigger discards in our implementation - using a series of single range requests, using vectored requests, tracking extents that can be combined in an rbtree or not - is something that we are working on. Using rbtrees versus a bitmap efficiency is about DRAM consumption, not performance of the resulting discard on the target.

4. Devices (some devices) can export their preferences in a standard way (look in /sys/block/....).

If you want to influence the code, please do try the various options on devices you have at hand and report results. That is what we are doing (we includes Lukas, Eric, Jeff and others on this thread) will real devices from vendors that have given us access. We are talking to them directly and trying out different work loads but certainly welcome real world results and suggestions.

Quoted 4 lines

Thanks!

Ric

Ric,

Is it also agreed by all that the current ext4 kernel implementation of calling discard is a poor solution for most hardware / block layers stacks / workloads and therefore is not worth retaining nor performing further benchmarks?

I've not seen anyone arguing to keep the current kernel implementation and I for one accept the previously posted benchmarks that show it is not adding any value relative to the traditional non-discard case.

Therefore benchmarks between the current hdparm/wiper.sh userspace implementation and a proposed new kernel implementation would be the most beneficial?

I have yet to see any of those benchmarks posted.

Greg

I don't like the user space wiper.sh approach in general, but running wiper.sh is entirely your choice.

Most users prefer having the file system and the IO stack take care of this for them, but again, entirely configurable.

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Mark" == Mark Lord <[email protected]> writes:

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Mark" == Mark Lord <[email protected]> writes:

Mark> So.. again.. in an ideal kernel, I'd like to see use of larger Mark> ranges (and _multiple_ ranges) per TRIM command.  And options for Mark> the kernel to do it automatically (-o discard), as well as an Mark> ioctl() interface for userspace to "scrub" (or "wipe") all free Mark> ranges in a gradual fashion.

Again: Discard splitting, merging, and coalescing is coming.  I'm working on it.  It's not exactly trivial.

My objection was purely wrt. nuking realtime discard in favor of scrubbing.  We absolutely need both approaches.

But I'm not going to let crappy SSD firmware implementations set the direction for what I'm working on.  It is much more interesting to ensure that we work well for the devices that'll be shipping 6-12 months from now (at the time where this stuff will realistically end up in distro kernels).

--
Martin K. Petersen      Oracle Linux Engineering

Quoted 14 lines · Martin K. Petersen

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Mark" == Mark Lord <[email protected]> writes:

Mark> So.. again.. in an ideal kernel, I'd like to see use of larger Mark> ranges (and _multiple_ ranges) per TRIM command.  And options for Mark> the kernel to do it automatically (-o discard), as well as an Mark> ioctl() interface for userspace to "scrub" (or "wipe") all free Mark> ranges in a gradual fashion.

Again: Discard splitting, merging, and coalescing is coming.  I'm working on it.  It's not exactly trivial.

My objection was purely wrt. nuking realtime discard in favor of scrubbing.  We absolutely need both approaches.

Quoted 9 lines

But I'm not going to let crappy SSD firmware implementations set the direction for what I'm working on.  It is much more interesting to ensure that we work well for the devices that'll be shipping 6-12 months from now (at the time where this stuff will realistically end up in distro kernels).

--
Martin K. Petersen      Oracle Linux Engineering

Is this an agreed summary as relates to ext4:

1) Current "-o discard" causes real-time calls to discard. Although not optimized for current generation hardware, both block-layer optimizations and new hardware are coming, so it needs to be kept.

2) Kernel based discard scrubbing - Doesn't currently exist in 2.6.34, all agree that for the LVM, mdraid, btrfs cases it is needed and there is no linux tool (kernel or userspace) at present. The Lukas proposed patch is userspace invoked so a mount option is not needed.

3) Userspace discard is available today and works well with ext4 on a single JBOD SSD which will be the typical laptop use as one example.

Mark, or anyone, do you think it would be a bad idea for me to push for Opensuse 11.3 (2.6.34 based) to use wiper.sh as a standard ext4 discard tool? hdparm and wiper.sh are already in the distro, it just needs a cron entry and maybe some basic management infrastructure. They're at feature freeze for 11.3, so I don't know if I can get it in or not.

If and when the suse team want to move to the kernel based scrubber, they can. ie. a year from now when the next release after 11.3 comes out.

Greg

Mark, or anyone, do you think it would be a bad idea for me to push for Opensuse 11.3 (2.6.34 based) to use wiper.sh as a standard ext4 discard tool? hdparm and wiper.sh are already in the distro, it just needs a cron entry and maybe some basic management infrastructure. They're at feature freeze for 11.3, so I don't know if I can get it in or not.

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Mark" == Mark Lord<[email protected]> writes:

Mark>  So.. again.. in an ideal kernel, I'd like to see use of larger
Mark>  ranges (and _multiple_ ranges) per TRIM command.  And options for
Mark>  the kernel to do it automatically (-o discard), as well as an
Mark>  ioctl() interface for userspace to "scrub" (or "wipe") all free
Mark>  ranges in a gradual fashion.

Again: Discard splitting, merging, and coalescing is coming. I'm working on it. It's not exactly trivial.

My objection was purely wrt. nuking realtime discard in favor of scrubbing. We absolutely need both approaches.

But I'm not going to let crappy SSD firmware implementations set the direction for what I'm working on. It is much more interesting to ensure that we work well for the devices that'll be shipping 6-12 months from now (at the time where this stuff will realistically end up in distro kernels).

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Greg" == Greg Freemyer <[email protected]> writes:

Our discard implementation is meant to accommodate a wide range of devices. Just because some of the currently shipping low-end consumer SSDs implement TRIM poorly does not mean we're going to scrap what we have.

We are not in the business of designing for the past. Especially not when the past can be handled by a shell script.

Quoted 1 line

Quoted 1 line

Quoted 1 line

Quoted 1 line

"Greg" == Greg Freemyer <[email protected]> writes:

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 7 lines · Greg Freemyer

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

I see two possible improvements here:
a) At a cost of some code complexity, you can bound the worst case by combining RB-trees with bitmaps. The basic idea is that when space to TRIM gets too fragmented (memory to keep to-TRIM blocks in RB-tree for a given group exceeds the memory needed to keep it in a bitmap), you convert RB-tree for a problematic group to a bitmap and attach it to an appropriate RB-node. If you track with a bitmap also a number of to-TRIM extents in the bitmap, you can also decide whether it's benefitial to switch back to an RB-tree.

b) Another idea might be: When to-TRIM space is fragmented (again, let's say in some block group), there's not much point in sending tiny trim commands anyway (at least that's what I've understood from this discussion). So you might as well stop maintaining information which blocks we need to trim for that group. When the situation gets better, you can always walk block bitmap and issue trim commands. You might even trigger this rescan from kernel - if you'd maintain number of free block extents for each block group (which is rather easy), you could trigger the bitmap rescan and trim as soon as ratio number of free blocks / number of extents gets above a reasonable threshold.

Honza

Quoted 7 lines · Jan Kara

Quoted 7 lines · Greg Freemyer

And also, currently I am rewriting the patch do use rbtree instead of the bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 8 lines

I see two possible improvements here:
a) At a cost of some code complexity, you can bound the worst case by combining RB-trees with bitmaps. The basic idea is that when space to TRIM gets too fragmented (memory to keep to-TRIM blocks in RB-tree for a given group exceeds the memory needed to keep it in a bitmap), you convert RB-tree for a problematic group to a bitmap and attach it to an appropriate RB-node. If you track with a bitmap also a number of to-TRIM extents in the bitmap, you can also decide whether it's benefitial to switch back to an RB-tree.

This sounds like a good idea, but I wonder if it is worth it :
1. The tree will have very short life, because with next ioctl all stored deleted extents will be trimmed and removed from the tree.
2. Also note, that the longer it lives the less fragmented it possibly became.
3. I do not expect, that deleted ranges can be too fragmented, and even if it is, it will be probably merged into one big extent very soon.

Quoted 12 lines

b) Another idea might be: When to-TRIM space is fragmented (again, let's say in some block group), there's not much point in sending tiny trim commands anyway (at least that's what I've understood from this discussion). So you might as well stop maintaining information which blocks we need to trim for that group. When the situation gets better, you can always walk block bitmap and issue trim commands. You might even trigger this rescan from kernel - if you'd maintain number of free block extents for each block group (which is rather easy), you could trigger the bitmap rescan and trim as soon as ratio number of free blocks / number of extents gets above a reasonable threshold.

Quoted 2 lines

Honza

In what I am preparing now, I simple ignore small extents, which would be created by splitting the deleted extent into smaller pieces by chunks of used blocks. This, in my opinion, will prevent the fragmentation, which otherwise may occur in the longer term (between ioctl calls).

Thanks for suggestions.
-Lukas

Quoted 51 lines · Lukas Czerner

Quoted 9 lines · Jan Kara

Quoted 9 lines · Greg Freemyer

And also, currently I am rewriting the patch do use rbtree instead of the
bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some
extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 12 lines

I see two possible improvements here:
a) At a cost of some code complexity, you can bound the worst case by combining
RB-trees with bitmaps. The basic idea is that when space to TRIM gets too fragmented (memory to keep to-TRIM blocks in RB-tree for a given group exceeds
the memory needed to keep it in a bitmap), you convert RB-tree for a problematic group to a bitmap and attach it to an appropriate RB-node. If you
track with a bitmap also a number of to-TRIM extents in the bitmap, you can
also decide whether it's benefitial to switch back to an RB-tree.

This sounds like a good idea, but I wonder if it is worth it :
1. The tree will have very short life, because with next ioctl all stored deleted extents will be trimmed and removed from the tree.
2. Also note, that the longer it lives the less fragmented it possibly became.
3. I do not expect, that deleted ranges can be too fragmented, and even if it is, it will be probably merged into one big extent very soon.

Quoted 15 lines

b) Another idea might be: When to-TRIM space is fragmented (again, let's say
in some block group), there's not much point in sending tiny trim commands anyway (at least that's what I've understood from this discussion). So you might as well stop maintaining information which blocks we need to trim for that group. When the situation gets better, you can always walk block bitmap and issue trim commands. You might even trigger this rescan from kernel - if you'd maintain number of free block extents for each block group
(which is rather easy), you could trigger the bitmap rescan and trim as soon
as ratio number of free blocks / number of extents gets above a reasonable threshold.

Quoted 2 lines

Honza

Quoted 7 lines

In what I am preparing now, I simple ignore small extents, which would be created by splitting the deleted extent into smaller pieces by chunks of used blocks. This, in my opinion, will prevent the fragmentation, which otherwise may occur in the longer term (between ioctl calls).

Thanks for suggestions.
-Lukas

I am not convinced that ignoring small extents is a good idea. Remember that for SSD's specifically, they remap *everything* internally so our "fragmentation" set of small spaces could be useful for them.

That does not mean that we should not try to send larger requests down to the target device which is always a good idea I think :-)

ric

Quoted 67 lines · Ric Wheeler

Quoted 51 lines · Lukas Czerner

Quoted 9 lines · Jan Kara

Quoted 9 lines · Greg Freemyer

And also, currently I am rewriting the patch do use rbtree instead of the
bitmap, because there were some concerns of memory consumption. It is a question whether or not the rbtree will be more memory friendly. Generally I think that in most "normal" cases it will, but there are some
extreme scenarios, where the rbtree will be much worse. Any comment on this ?

Quoted 12 lines

I see two possible improvements here:
a) At a cost of some code complexity, you can bound the worst case by combining
RB-trees with bitmaps. The basic idea is that when space to TRIM gets too fragmented (memory to keep to-TRIM blocks in RB-tree for a given group exceeds
the memory needed to keep it in a bitmap), you convert RB-tree for a problematic group to a bitmap and attach it to an appropriate RB-node. If you
track with a bitmap also a number of to-TRIM extents in the bitmap, you can
also decide whether it's benefitial to switch back to an RB-tree.

This sounds like a good idea, but I wonder if it is worth it :
1. The tree will have very short life, because with next ioctl all stored deleted extents will be trimmed and removed from the tree.
2. Also note, that the longer it lives the less fragmented it possibly became.
3. I do not expect, that deleted ranges can be too fragmented, and even if it is, it will be probably merged into one big extent very soon.

Quoted 15 lines

b) Another idea might be: When to-TRIM space is fragmented (again, let's say
in some block group), there's not much point in sending tiny trim commands anyway (at least that's what I've understood from this discussion). So you might as well stop maintaining information which blocks we need to trim for that group. When the situation gets better, you can always walk block bitmap and issue trim commands. You might even trigger this rescan from kernel - if you'd maintain number of free block extents for each block group
(which is rather easy), you could trigger the bitmap rescan and trim as soon
as ratio number of free blocks / number of extents gets above a reasonable threshold.

Quoted 2 lines

Honza

Quoted 7 lines

In what I am preparing now, I simple ignore small extents, which would be created by splitting the deleted extent into smaller pieces by chunks of used blocks. This, in my opinion, will prevent the fragmentation, which otherwise may occur in the longer term (between ioctl calls).

Thanks for suggestions.
-Lukas

I am not convinced that ignoring small extents is a good idea. Remember that for SSD's specifically, they remap *everything* internally so our "fragmentation" set of small spaces could be useful for them.

That does not mean that we should not try to send larger requests down to the target device which is always a good idea I think :-)

Quoted 2 lines

ric

That's right, so the other approach would be probably better. Merge small extents together into one, but there must be some limit, because I do not want two little extents at the beginning and the end of the group to force trimming whole group. The whole rbtree thing gets a little complicated :)

Create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have created new structure ext4_deleted_data which represents deleted extent in per-group rbtree. When blocks are freed, extents are stored in the tree (possibly merged with other extents). The ioctl then can walk through the tree, take out extents from the tree, compare them with the free extents and possibly trim them.

Note that there is support for setting minimum extent length in ioctl call, so it will not bother with shorter extents. Also, when the previously deleted range is taken from the tree and it is not entirely free, the free fragments are discarded and extents shorter than minlen are NOT returned back to the tree to avoid fragmentation of the tree which could lead to the big memory consumption.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents.

Signed-off-by Lukas Czerner <[email protected]>

Quoted 29 lines · Lukas Czerner

Create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have created new structure ext4_deleted_data which represents deleted extent in per-group rbtree. When blocks are freed, extents are stored in the tree (possibly merged with other extents). The ioctl then can walk through the tree, take out extents from the tree, compare them with the free extents and possibly trim them.

Note that there is support for setting minimum extent length in ioctl call, so it will not bother with shorter extents. Also, when the previously deleted range is taken from the tree and it is not entirely free, the free fragments are discarded and extents shorter than minlen are NOT returned back to the tree to avoid fragmentation of the tree which could lead to the big memory consumption.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents.

Quoted 2 lines

Signed-off-by Lukas Czerner <[email protected]>

For now it just ignores the small extents to avoid fragmentation. As I said before, I agree that they should not be ignored, I just need to figure out the way to do this efficiently.

Also it was not properly tested yet.

-Lukas.

Quoted 44 lines · Ric Wheeler

Quoted 43 lines · Greg Freemyer

Quoted 42 lines · Eric Sandeen

Quoted 41 lines · Mark Lord

Quoted 3 lines · Greg Freemyer

Mark,

This is the patch implementing the new discard logic.

..

Quoted 1 line

Signed-off-by Lukas Czerner<[email protected]>

..

Quoted 34 lines

Quoted 18 lines

(quoted diff) +18 -0

+void 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;
+
+       assert_spin_locked(ext4_group_lock_ptr(sb, group));
+
+       ex.fe_start = start;
+       ex.fe_group = group;
+       ex.fe_len = count;
+
+       mb_mark_used(e4b,&ex);
+       ext4_unlock_group(sb, group);
+
+       discard_block = (ext4_fsblk_t)group *
+                       EXT4_BLOCKS_PER_GROUP(sb)

Review

Quoted 10 lines

(quoted diff) +10 -0

+                       + start
+                       + le32_to_cpu(es->s_first_data_block);
+       trace_ext4_discard_blocks(sb,
+                       (unsigned long long)discard_block,
+                       count);
+       sb_issue_discard(sb, discard_block, count);
+
+       ext4_lock_group(sb, group);
+       mb_free_blocks(NULL, e4b, start, ex.fe_len);
+}

Mark, unless I'm missing something, sb_issue_discard() above is going to trigger a trim command for just the one range.  I thought the benchmarks you did showed that a collection of ranges needed to be built, then a single trim command invoked that trimmed that group of ranges.

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

..

Mmm.. If that's what it is doing, then this patch set would be a complete disaster.
It would take *hours* to do the initial TRIM.

Except it doesn't.  Lukas did provide numbers in his original email.

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 1 line

Lukas ?

I'm confused; do we have an interface to send a trim command for multiple ranges?

I didn't think so ...  Lukas' patch is finding free ranges (above a size threshold) to discard; it's not doing it a block at a time, if that's the concern.

Quoted 7 lines

Quoted 7 lines

Quoted 1 line

-Eric

Eric,

I don't know what kernel APIs have been created to support discard, but the ATA8 draft spec. allows for specifying multiple ranges in one trim command.

Well, sb_issue_discard is what ext4 is using, and that takes a single range.  I don't know if anyone has looked into adding a vectored API.

Quoted 5 lines

Greg,

We have full support for this in the "discard" support at the file system layer for several file systems.

Actually, we don't support what Greg is talking about, to my knowledge.

Quoted 7 lines

The block layer effectively muxes the "discard" into the right target device command. TRIM for ATA, WRITE_SAME (with unmap) or UNMAP for SCSI...

If your favourite fs supports this, you can enable this feature with "-o
discard" for fine grained discards,

Thanks, it's worth pointing out that TRIM is not the only backend to the discard API.  However, even if we do implement a vectored API, we can translate that to dumber commands if a given spec doesn't support it.

Getting back to the problem...

From the file system, you want to discard discrete ranges of blocks. The API to support this can either take care of the data integrity guarantees by itself, or make the upper layer ensure that trim and write do not pass each other.  The current implementation does the latter.  In order to do the former, there is the potential for a lot of overhead to be introduced into the block allocation layers for the file systems.

So, given the above, it is up to the file system to send down the biggest discard requests it can in order to reduce the overhead of the command.  If a vectored approach is made available, then that would be even better.  Christoph, is this something that's on your radar?

Cheers,
Jeff

Hi all,

I would like to present a new way to deal with TRIM in ext4 file system. The current solution is not ideal because of its bad performance impact. So basic idea to improve things is to avoid discarding every time some blocks are freed. and instead batching is together into bigger trims, which tends to be more effective.

The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further.

I have also benchmarked it a little. You can find results here:

people.redhat.com/jmoyer/discard/ext4_batched_discard/

comparison with current solution included. Keep in mind that ideal ioctl invocation interval is yet to be determined, so in benchmark I have used the performance-worst scenario - without any sleep between execution.

There are two patches for this. The first one just creates file system independent ioctl for this and the second one it the batched discard support itself.

I will very much appreciate any comment on this, your opinions, ideas to make this better etc. Thanks.

If you want to try it, just create EXT4 file system mount it and invoke ioctl on the mount point. You can use following code for this (I have taken this from xfs patch for the same thing). You can also see some debugging messages, but you may want to set EXT4FS_DEBUG for this.

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/ioctl.h>

#define FITRIM          _IOWR('X', 121, int)

int main(int argc, char **argv)
{
       int minsize = 4096;
       int fd;

       if (argc != 2) {
               fprintf(stderr, "usage: %s mountpoint\n", argv[0]); return 1;
       }

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

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

       return 0;
}

 fs/ioctl.c         |   31 +++++++++++++++++++++++++++++++ include/linux/fs.h |    2 ++

 2 files changed, 33 insertions(+), 0 deletions(-)

 fs/ext4/ext4.h    |    4 +
 fs/ext4/mballoc.c |  207 ++++++++++++++++++++++++++++++++++++++++++++++++++--- fs/ext4/super.c   |    1 +

 3 files changed, 202 insertions(+), 10 deletions(-)

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Adding Mark Lord in cc.

He wrote a preliminary discard solution last summer. I'm not sure how it has progressed.

Mark, you can find the 2 patches at:

http://patchwork.ozlabs.org/patch/50441/
http://patchwork.ozlabs.org/patch/50442/

Greg

Quoted 100 lines · Lukas Czerner

Hi all,

I would like to present a new way to deal with TRIM in ext4 file system. The current solution is not ideal because of its bad performance impact. So basic idea to improve things is to avoid discarding every time some blocks are freed. and instead batching is together into bigger trims, which tends to be more effective.

The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

This of course means, that with each invocation the ioctl must walk through whole file system, checking and discarding free extents, which is not very efficient. The best way to avoid this is to keep track of deleted (freed) blocks. Then the ioctl have to trim just those free extents which were recently freed.

In order to implement this I have added new bitmap into ext4_group_info (bb_bitmap_deleted) which stores recently freed blocks. The ioctl then walk through bb_bitmap_deleted, compare deleted extents with free extents trim them and then removes it from the bb_bitmap_deleted.

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further.

I have also benchmarked it a little. You can find results here:

people.redhat.com/jmoyer/discard/ext4_batched_discard/

comparison with current solution included. Keep in mind that ideal ioctl invocation interval is yet to be determined, so in benchmark I have used the performance-worst scenario - without any sleep between execution.

There are two patches for this. The first one just creates file system independent ioctl for this and the second one it the batched discard support itself.

I will very much appreciate any comment on this, your opinions, ideas to make this better etc. Thanks.

If you want to try it, just create EXT4 file system mount it and invoke ioctl on the mount point. You can use following code for this (I have taken this from xfs patch for the same thing). You can also see some debugging messages, but you may want to set EXT4FS_DEBUG for this.

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/ioctl.h>

#define FITRIM _IOWR('X', 121, int)

int main(int argc, char **argv)

{
       int minsize = 4096;
       int fd;

       if (argc != 2) {
               fprintf(stderr, "usage: %s mountpoint\n", argv[0]);
               return 1;
       }

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

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

       return 0;
}

 fs/ioctl.c         |   31 +++++++++++++++++++++++++++++++
 include/linux/fs.h |    2 ++
 2 files changed, 33 insertions(+), 0 deletions(-)

 fs/ext4/ext4.h    |    4 +
 fs/ext4/mballoc.c |  207 ++++++++++++++++++++++++++++++++++++++++++++++++++---
 fs/ext4/super.c   |    1 +
 3 files changed, 202 insertions(+), 10 deletions(-)

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 4 lines · Greg Freemyer

Adding Mark Lord in cc.

He wrote a preliminary discard solution last summer.  I'm not sure how it has progressed.

The difference here is that Mark's stuff wasn't as tightly integrated with the kernel, IIRC.  What I saw was more at a user level - make a big file, map it, discard all the blocks, unlink the file.

It was a good first step, but I think we can do a lot better by using fs-specific calls to be efficient & targeted about the discards.

Christoph has a similar approach for XFS, FWIW.

-Eric

Quoted 10 lines · Eric Sandeen

Quoted 4 lines · Greg Freemyer

Adding Mark Lord in cc.

He wrote a preliminary discard solution last summer. I'm not sure how it has progressed.

The difference here is that Mark's stuff wasn't as tightly integrated with the kernel, IIRC. What I saw was more at a user level - make a big file, map it, discard all the blocks, unlink the file.

Quoted 6 lines

It was a good first step, but I think we can do a lot better by using fs-specific calls to be efficient& targeted about the discards.

Christoph has a similar approach for XFS, FWIW.

-Eric

I haven't looked closely at this patch, but I recall Mark consolidated numerous discontinuous trim/discard/unmap ranges into a single command to the SSD drive.

That was why he felt he was getting superior performance. ie. There was an overhead per command to the drive that was eliminated if a single more complex command with multiple ranges went to the SSD drive.

But he's the one that did the work and the benchmarking, so I'll let him take it from here, especially if I mis-understood what he was doing.

Greg

Adding Mark Lord in cc.

Quoted 4 lines

The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

Quoted 6 lines

But you may notice, that there is one problem. bb_bitmap_deleted does not survive umount. To bypass the problem the first ioctl call have to walk through whole file system trimming all free extents. But there is a better solution to this problem. The bb_bitmap_deleted can be stored on disk an can be restored in mount time along with other bitmaps, but I think it is a quite big change and should be discussed further.

Quoted 1 line · Greg Freemyer

Adding Mark Lord in cc.

..

Quoted 2 lines

On Mon, Apr 19, 2010 at 6:55 AM, Lukas Czerner<[email protected]> wrote:

..

Quoted 5 lines

Quoted 5 lines

The basic idea behind my discard support is to create an ioctl which walks through all the free extents in each allocating group and discard those extents. As an addition to improve its performance one can specify minimum free extent length, so ioctl will not bother with shorter extents.

..

Perfect. I proposed exactly this last year, but never found time to work it further. Please proceed with it!

Taking care of mounted RAID / LVM filesystems requires in-kernel TRIM support, possibly exported via an ioctl().

Taking care of unmounted RAID / LVM filesystems is possible in userland, but would also benefit from in-kernel support, where layouts are defined and known better than in userland.

The XFS_TRIM was an idea that Cristoph floated, as a concept for examination.

I think something along those lines would be best, but perhaps with an interface at the VFS layer. Something that permits a userland tool to work like this (below) might be nearly ideal:

main() {
    int fd = open(filesystem_device);
    while (1) {
        int g, ngroups = ioctl(fd, GET_NUMBER_OF_BLOCK_GROUPS);
        for (g = 0; g < ngroups; ++g) {
            ioctl(fd, TRIM_ALL_FREE_EXTENTS_OF_GROUP, g);
        }
        sleep(3600);
    }
}

Not all filesystems have a "block group", or "allocation group" structure, but I suspect that it's an easy mapping in most cases.

With this scheme, the kernel is absolved of the need to track/coallesce TRIM requests entirely.

Something like that, perhaps.