| Message ID | 1377858934-17187-1-git-send-email-miaox@cn.fujitsu.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
On Fri, 30 Aug 2013 18:35:34 +0800, Miao Xie wrote: > By the current code, if the requested size is very large, and all the extents > in the free space cache are small, we will waste lots of the cpu time to cut > the requested size in half and search the cache again and again until it gets > down to the size the allocator can return. In fact, we can know the max extent > size in the cache after the first search, so we needn't cut the size in half > repeatedly, and just use the max extent size directly. This way can save > lots of cpu time and make the performance grow up when there are only fragments > in the free space cache. > > According to my test, if there are only 4KB free space extents in the fs, > and the total size of those extents are 256MB, we can reduce the execute > time of the following test from 5.4s to 1.4s. > dd if=/dev/zero of=<testfile> bs=1MB count=1 oflag=sync > > Signed-off-by: Miao Xie <miaox@cn.fujitsu.com> > --- > Changelog v1 -> v2: > - address the problem that we return a wrong start position when searching > the free space in a bitmap. > --- > fs/btrfs/extent-tree.c | 29 ++++++++++++++------- > fs/btrfs/free-space-cache.c | 62 +++++++++++++++++++++++++++++++-------------- > fs/btrfs/free-space-cache.h | 5 ++-- > 3 files changed, 66 insertions(+), 30 deletions(-) This patch makes the xfstest generic/256 lock up. It's quite reliably reproducible on one of my test boxes, and not at all visible on a second test box. And yes, I'm using the V2 patch although you haven't tagged it as V2 in the subject line of the mail :) # reboot ... reboot done # cd ~/git/xfs/cmds/xfstests # export TEST_DEV=/dev/sdc1 # export TEST_DIR=/mnt2 # export SCRATCH_DEV=/dev/sdd1 # export SCRATCH_MNT=/mnt3 # umount $TEST_DIR $SCRATCH_MNT # mkfs.btrfs -f $TEST_DEV # mkfs.btrfs -f $SCRATCH_DEV # ./check generic/256 ...should be finished after 20s, but it isn't, therefore after 180s: # echo w > /proc/sysrq-trigger root: run xfstest generic/256 SysRq : Show Blocked State task PC stack pid father btrfs-flush_del D 000000001a6d0000 6240 31190 2 0x00000000 ffff880804dbfcb8 0000000000000086 ffff880804dbffd8 ffff8807ef218000 ffff880804dbffd8 ffff880804dbffd8 ffff88080ad44520 ffff8807ef218000 ffff880804dbfc98 ffff880784d3ca50 ffff880784d3ca18 ffff880804dbfce8 Call Trace: [<ffffffff81995da4>] schedule+0x24/0x60 [<ffffffffa05235c5>] btrfs_start_ordered_extent+0x85/0x130 [btrfs] [<ffffffff810ac170>] ? wake_up_bit+0x40/0x40 [<ffffffffa0523694>] btrfs_run_ordered_extent_work+0x24/0x40 [btrfs] [<ffffffffa0539d5f>] worker_loop+0x13f/0x5b0 [btrfs] [<ffffffff810b5ba3>] ? finish_task_switch+0x43/0x110 [<ffffffff81995880>] ? __schedule+0x3f0/0x860 [<ffffffffa0539c20>] ? btrfs_queue_worker+0x300/0x300 [btrfs] [<ffffffff810abd36>] kthread+0xd6/0xe0 [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 [<ffffffff8199f66c>] ret_from_fork+0x7c/0xb0 [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 xfs_io D ffff880784d3cbc0 5008 31241 31240 0x00000000 ffff8808036f3868 0000000000000082 ffff8808036f3fd8 ffff8807c9878000 ffff8808036f3fd8 ffff8808036f3fd8 ffffffff82010440 ffff8807c9878000 ffff8808036f3848 ffff880784d3cb18 ffff880784d3cb20 7fffffffffffffff Call Trace: [<ffffffff81995da4>] schedule+0x24/0x60 [<ffffffff81992dc4>] schedule_timeout+0x194/0x260 [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 [<ffffffff819951cf>] wait_for_completion+0xcf/0x110 [<ffffffff810bb650>] ? try_to_wake_up+0x310/0x310 [<ffffffffa0523b7a>] btrfs_wait_ordered_extents+0x1ea/0x260 [btrfs] [<ffffffffa0523ce5>] btrfs_wait_all_ordered_extents+0xf5/0x150 [btrfs] [<ffffffffa04f4b8d>] reserve_metadata_bytes+0x7bd/0xa30 [btrfs] [<ffffffffa04f516d>] btrfs_delalloc_reserve_metadata+0x16d/0x460 [btrfs] [<ffffffffa051dad6>] __btrfs_buffered_write+0x276/0x4f0 [btrfs] [<ffffffffa051df1a>] btrfs_file_aio_write+0x1ca/0x5a0 [btrfs] [<ffffffff8119a6db>] do_sync_write+0x7b/0xb0 [<ffffffff8119b463>] vfs_write+0xc3/0x1e0 [<ffffffff8119bad2>] SyS_pwrite64+0x92/0xb0 [<ffffffff8199f712>] system_call_fastpath+0x16/0x1b (gdb) list *(btrfs_start_ordered_extent+0x85) 0x4a545 is in btrfs_start_ordered_extent (fs/btrfs/ordered-data.c:747). 742 * for the flusher thread to find them 743 */ 744 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) 745 filemap_fdatawrite_range(inode->i_mapping, start, end); 746 if (wait) { 747 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, 748 &entry->flags)); 749 } 750 } 751 (gdb) list *(btrfs_wait_ordered_extents+0x1ea) 0x4aafa is in btrfs_wait_ordered_extents (fs/btrfs/ordered-data.c:610). 605 list_for_each_entry_safe(ordered, next, &works, work_list) { 606 list_del_init(&ordered->work_list); 607 wait_for_completion(&ordered->completion); 608 609 inode = ordered->inode; 610 btrfs_put_ordered_extent(ordered); 611 if (delay_iput) 612 btrfs_add_delayed_iput(inode); 613 else 614 iput(inode); # cat /proc/mounts | grep /mnt /dev/sdc1 /mnt2 btrfs rw,relatime,ssd,space_cache 0 0 /dev/sdd1 /mnt3 btrfs rw,relatime,ssd,space_cache 0 0 # btrfs fi show Label: none uuid: 3dbe59c8-f4a0-4014-85f6-a6e9f5707c3a Total devices 1 FS bytes used 1.44GiB devid 1 size 1.50GiB used 1.50GiB path /dev/sdd1 Label: none uuid: 60130e96-5fb6-4355-b81e-8113c6f5c517 Total devices 1 FS bytes used 32.00KiB devid 1 size 20.00GiB used 20.00MiB path /dev/sdc1 All partitions have a size of 20971520 blocks according to fdisk: Device Boot Start End Blocks Id System /dev/sdc1 2048 41945087 20971520 83 Linux With the currently pushed btrfs-next and the latest xfstests. > diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c > index 0236de7..d634dbc 100644 > --- a/fs/btrfs/extent-tree.c > +++ b/fs/btrfs/extent-tree.c > @@ -6065,10 +6065,13 @@ enum btrfs_loop_type { > /* > * walks the btree of allocated extents and find a hole of a given size. > * The key ins is changed to record the hole: > - * ins->objectid == block start > + * ins->objectid == start position > * ins->flags = BTRFS_EXTENT_ITEM_KEY > - * ins->offset == number of blocks > + * ins->offset == the size of the hole. > * Any available blocks before search_start are skipped. > + * > + * If there is no suitable free space, we will record the max size of > + * the free space extent currently. > */ > static noinline int find_free_extent(struct btrfs_trans_handle *trans, > struct btrfs_root *orig_root, > @@ -6082,6 +6085,7 @@ static noinline int find_free_extent(struct btrfs_trans_handle *trans, > struct btrfs_block_group_cache *block_group = NULL; > struct btrfs_block_group_cache *used_block_group; > u64 search_start = 0; > + u64 max_extent_size = 0; > int empty_cluster = 2 * 1024 * 1024; > struct btrfs_space_info *space_info; > int loop = 0; > @@ -6239,7 +6243,10 @@ have_block_group: > btrfs_get_block_group(used_block_group); > > offset = btrfs_alloc_from_cluster(used_block_group, > - last_ptr, num_bytes, used_block_group->key.objectid); > + last_ptr, > + num_bytes, > + used_block_group->key.objectid, > + &max_extent_size); > if (offset) { > /* we have a block, we're done */ > spin_unlock(&last_ptr->refill_lock); > @@ -6302,8 +6309,10 @@ refill_cluster: > * cluster > */ > offset = btrfs_alloc_from_cluster(block_group, > - last_ptr, num_bytes, > - search_start); > + last_ptr, > + num_bytes, > + search_start, > + &max_extent_size); > if (offset) { > /* we found one, proceed */ > spin_unlock(&last_ptr->refill_lock); > @@ -6344,7 +6353,8 @@ unclustered_alloc: > spin_unlock(&block_group->free_space_ctl->tree_lock); > > offset = btrfs_find_space_for_alloc(block_group, search_start, > - num_bytes, empty_size); > + num_bytes, empty_size, > + &max_extent_size); > /* > * If we didn't find a chunk, and we haven't failed on this > * block group before, and this block group is in the middle of > @@ -6451,7 +6461,8 @@ loop: > ret = 0; > } > out: > - > + if (ret == -ENOSPC) > + ins->offset = max_extent_size; > return ret; > } > > @@ -6517,8 +6528,8 @@ again: > hint_byte, ins, flags); > > if (ret == -ENOSPC) { > - if (!final_tried) { > - num_bytes = num_bytes >> 1; > + if (!final_tried && ins->offset) { > + num_bytes = min(num_bytes >> 1, ins->offset); > num_bytes = round_down(num_bytes, root->sectorsize); > num_bytes = max(num_bytes, min_alloc_size); > if (num_bytes == min_alloc_size) > diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c > index 7517285..229c8c1 100644 > --- a/fs/btrfs/free-space-cache.c > +++ b/fs/btrfs/free-space-cache.c > @@ -1434,13 +1434,19 @@ static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl, > ctl->free_space += bytes; > } > > +/* > + * If we can not find suitable extent, we will use bytes to record > + * the size of the max extent. > + */ > static int search_bitmap(struct btrfs_free_space_ctl *ctl, > struct btrfs_free_space *bitmap_info, u64 *offset, > u64 *bytes) > { > unsigned long found_bits = 0; > + unsigned long max_bits = 0; > unsigned long bits, i; > unsigned long next_zero; > + unsigned long extent_bits; > > i = offset_to_bit(bitmap_info->offset, ctl->unit, > max_t(u64, *offset, bitmap_info->offset)); > @@ -1449,9 +1455,12 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, > for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) { > next_zero = find_next_zero_bit(bitmap_info->bitmap, > BITS_PER_BITMAP, i); > - if ((next_zero - i) >= bits) { > - found_bits = next_zero - i; > + extent_bits = next_zero - i; > + if (extent_bits >= bits) { > + found_bits = extent_bits; > break; > + } else if (extent_bits > max_bits) { > + max_bits = extent_bits; > } > i = next_zero; > } > @@ -1462,38 +1471,41 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, > return 0; > } > > + *bytes = (u64)(max_bits) * ctl->unit; > return -1; > } > > +/* Cache the size of the max extent in bytes */ > static struct btrfs_free_space * > find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, > - unsigned long align) > + unsigned long align, u64 *max_extent_size) > { > struct btrfs_free_space *entry; > struct rb_node *node; > - u64 ctl_off; > u64 tmp; > u64 align_off; > int ret; > > if (!ctl->free_space_offset.rb_node) > - return NULL; > + goto out; > > entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1); > if (!entry) > - return NULL; > + goto out; > > for (node = &entry->offset_index; node; node = rb_next(node)) { > entry = rb_entry(node, struct btrfs_free_space, offset_index); > - if (entry->bytes < *bytes) > + if (entry->bytes < *bytes) { > + if (entry->bytes > *max_extent_size) > + *max_extent_size = entry->bytes; > continue; > + } > > /* make sure the space returned is big enough > * to match our requested alignment > */ > if (*bytes >= align) { > - ctl_off = entry->offset - ctl->start; > - tmp = ctl_off + align - 1;; > + tmp = entry->offset - ctl->start + align - 1; > do_div(tmp, align); > tmp = tmp * align + ctl->start; > align_off = tmp - entry->offset; > @@ -1506,10 +1518,15 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, > continue; > > if (entry->bitmap) { > - ret = search_bitmap(ctl, entry, &tmp, bytes); > + u64 size = *bytes; > + > + ret = search_bitmap(ctl, entry, &tmp, &size); > if (!ret) { > *offset = tmp; > + *bytes = size; > return entry; > + } else if (size > *max_extent_size) { > + *max_extent_size = size; > } > continue; > } > @@ -1518,7 +1535,7 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, > *bytes = entry->bytes - align_off; > return entry; > } > - > +out: > return NULL; > } > > @@ -2120,7 +2137,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) > } > > u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, > - u64 offset, u64 bytes, u64 empty_size) > + u64 offset, u64 bytes, u64 empty_size, > + u64 *max_extent_size) > { > struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; > struct btrfs_free_space *entry = NULL; > @@ -2131,7 +2149,7 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, > > spin_lock(&ctl->tree_lock); > entry = find_free_space(ctl, &offset, &bytes_search, > - block_group->full_stripe_len); > + block_group->full_stripe_len, max_extent_size); > if (!entry) > goto out; > > @@ -2141,7 +2159,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, > if (!entry->bytes) > free_bitmap(ctl, entry); > } else { > - > unlink_free_space(ctl, entry); > align_gap_len = offset - entry->offset; > align_gap = entry->offset; > @@ -2155,7 +2172,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, > else > link_free_space(ctl, entry); > } > - > out: > spin_unlock(&ctl->tree_lock); > > @@ -2210,7 +2226,8 @@ int btrfs_return_cluster_to_free_space( > static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, > struct btrfs_free_cluster *cluster, > struct btrfs_free_space *entry, > - u64 bytes, u64 min_start) > + u64 bytes, u64 min_start, > + u64 *max_extent_size) > { > struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; > int err; > @@ -2222,8 +2239,11 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, > search_bytes = bytes; > > err = search_bitmap(ctl, entry, &search_start, &search_bytes); > - if (err) > + if (err) { > + if (search_bytes > *max_extent_size) > + *max_extent_size = search_bytes; > return 0; > + } > > ret = search_start; > __bitmap_clear_bits(ctl, entry, ret, bytes); > @@ -2238,7 +2258,7 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, > */ > u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, > struct btrfs_free_cluster *cluster, u64 bytes, > - u64 min_start) > + u64 min_start, u64 *max_extent_size) > { > struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; > struct btrfs_free_space *entry = NULL; > @@ -2258,6 +2278,9 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, > > entry = rb_entry(node, struct btrfs_free_space, offset_index); > while(1) { > + if (entry->bytes < bytes && entry->bytes > *max_extent_size) > + *max_extent_size = entry->bytes; > + > if (entry->bytes < bytes || > (!entry->bitmap && entry->offset < min_start)) { > node = rb_next(&entry->offset_index); > @@ -2271,7 +2294,8 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, > if (entry->bitmap) { > ret = btrfs_alloc_from_bitmap(block_group, > cluster, entry, bytes, > - cluster->window_start); > + cluster->window_start, > + max_extent_size); > if (ret == 0) { > node = rb_next(&entry->offset_index); > if (!node) > diff --git a/fs/btrfs/free-space-cache.h b/fs/btrfs/free-space-cache.h > index 894116b..a701000 100644 > --- a/fs/btrfs/free-space-cache.h > +++ b/fs/btrfs/free-space-cache.h > @@ -94,7 +94,8 @@ void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl); > void btrfs_remove_free_space_cache(struct btrfs_block_group_cache > *block_group); > u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, > - u64 offset, u64 bytes, u64 empty_size); > + u64 offset, u64 bytes, u64 empty_size, > + u64 *max_extent_size); > u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root); > void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group, > u64 bytes); > @@ -106,7 +107,7 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, > void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster); > u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, > struct btrfs_free_cluster *cluster, u64 bytes, > - u64 min_start); > + u64 min_start, u64 *max_extent_size); > int btrfs_return_cluster_to_free_space( > struct btrfs_block_group_cache *block_group, > struct btrfs_free_cluster *cluster); > -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On fri, 06 Sep 2013 15:47:08 +0200, Stefan Behrens wrote: > On Fri, 30 Aug 2013 18:35:34 +0800, Miao Xie wrote: >> By the current code, if the requested size is very large, and all the extents >> in the free space cache are small, we will waste lots of the cpu time to cut >> the requested size in half and search the cache again and again until it gets >> down to the size the allocator can return. In fact, we can know the max extent >> size in the cache after the first search, so we needn't cut the size in half >> repeatedly, and just use the max extent size directly. This way can save >> lots of cpu time and make the performance grow up when there are only fragments >> in the free space cache. >> >> According to my test, if there are only 4KB free space extents in the fs, >> and the total size of those extents are 256MB, we can reduce the execute >> time of the following test from 5.4s to 1.4s. >> dd if=/dev/zero of=<testfile> bs=1MB count=1 oflag=sync >> >> Signed-off-by: Miao Xie <miaox@cn.fujitsu.com> >> --- >> Changelog v1 -> v2: >> - address the problem that we return a wrong start position when searching >> the free space in a bitmap. >> --- >> fs/btrfs/extent-tree.c | 29 ++++++++++++++------- >> fs/btrfs/free-space-cache.c | 62 +++++++++++++++++++++++++++++++-------------- >> fs/btrfs/free-space-cache.h | 5 ++-- >> 3 files changed, 66 insertions(+), 30 deletions(-) > > This patch makes the xfstest generic/256 lock up. It's quite reliably reproducible on one of my test boxes, and not at all visible on a second test box. > > And yes, I'm using the V2 patch although you haven't tagged it as V2 in the subject line of the mail :) According to my debug, the machine was not locked up, it seems the patch makes the test run very slow(90s ->850s on my machine). Could you try the v3 patch? Thanks Miao > > > # reboot > ... reboot done > # cd ~/git/xfs/cmds/xfstests > # export TEST_DEV=/dev/sdc1 > # export TEST_DIR=/mnt2 > # export SCRATCH_DEV=/dev/sdd1 > # export SCRATCH_MNT=/mnt3 > # umount $TEST_DIR $SCRATCH_MNT > # mkfs.btrfs -f $TEST_DEV > # mkfs.btrfs -f $SCRATCH_DEV > # ./check generic/256 > ...should be finished after 20s, but it isn't, therefore after 180s: > # echo w > /proc/sysrq-trigger > root: run xfstest generic/256 > SysRq : Show Blocked State > task PC stack pid father > btrfs-flush_del D 000000001a6d0000 6240 31190 2 0x00000000 > ffff880804dbfcb8 0000000000000086 ffff880804dbffd8 ffff8807ef218000 > ffff880804dbffd8 ffff880804dbffd8 ffff88080ad44520 ffff8807ef218000 > ffff880804dbfc98 ffff880784d3ca50 ffff880784d3ca18 ffff880804dbfce8 > Call Trace: > [<ffffffff81995da4>] schedule+0x24/0x60 > [<ffffffffa05235c5>] btrfs_start_ordered_extent+0x85/0x130 [btrfs] > [<ffffffff810ac170>] ? wake_up_bit+0x40/0x40 > [<ffffffffa0523694>] btrfs_run_ordered_extent_work+0x24/0x40 [btrfs] > [<ffffffffa0539d5f>] worker_loop+0x13f/0x5b0 [btrfs] > [<ffffffff810b5ba3>] ? finish_task_switch+0x43/0x110 > [<ffffffff81995880>] ? __schedule+0x3f0/0x860 > [<ffffffffa0539c20>] ? btrfs_queue_worker+0x300/0x300 [btrfs] > [<ffffffff810abd36>] kthread+0xd6/0xe0 > [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 > [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 > [<ffffffff8199f66c>] ret_from_fork+0x7c/0xb0 > [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 > xfs_io D ffff880784d3cbc0 5008 31241 31240 0x00000000 > ffff8808036f3868 0000000000000082 ffff8808036f3fd8 ffff8807c9878000 > ffff8808036f3fd8 ffff8808036f3fd8 ffffffff82010440 ffff8807c9878000 > ffff8808036f3848 ffff880784d3cb18 ffff880784d3cb20 7fffffffffffffff > Call Trace: > [<ffffffff81995da4>] schedule+0x24/0x60 > [<ffffffff81992dc4>] schedule_timeout+0x194/0x260 > [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 > [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 > [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 > [<ffffffff819951cf>] wait_for_completion+0xcf/0x110 > [<ffffffff810bb650>] ? try_to_wake_up+0x310/0x310 > [<ffffffffa0523b7a>] btrfs_wait_ordered_extents+0x1ea/0x260 [btrfs] > [<ffffffffa0523ce5>] btrfs_wait_all_ordered_extents+0xf5/0x150 [btrfs] > [<ffffffffa04f4b8d>] reserve_metadata_bytes+0x7bd/0xa30 [btrfs] > [<ffffffffa04f516d>] btrfs_delalloc_reserve_metadata+0x16d/0x460 [btrfs] > [<ffffffffa051dad6>] __btrfs_buffered_write+0x276/0x4f0 [btrfs] > [<ffffffffa051df1a>] btrfs_file_aio_write+0x1ca/0x5a0 [btrfs] > [<ffffffff8119a6db>] do_sync_write+0x7b/0xb0 > [<ffffffff8119b463>] vfs_write+0xc3/0x1e0 > [<ffffffff8119bad2>] SyS_pwrite64+0x92/0xb0 > [<ffffffff8199f712>] system_call_fastpath+0x16/0x1b > > (gdb) list *(btrfs_start_ordered_extent+0x85) > 0x4a545 is in btrfs_start_ordered_extent (fs/btrfs/ordered-data.c:747). > 742 * for the flusher thread to find them > 743 */ > 744 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) > 745 filemap_fdatawrite_range(inode->i_mapping, start, end); > 746 if (wait) { > 747 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, > 748 &entry->flags)); > 749 } > 750 } > 751 > > (gdb) list *(btrfs_wait_ordered_extents+0x1ea) > 0x4aafa is in btrfs_wait_ordered_extents (fs/btrfs/ordered-data.c:610). > 605 list_for_each_entry_safe(ordered, next, &works, work_list) { > 606 list_del_init(&ordered->work_list); > 607 wait_for_completion(&ordered->completion); > 608 > 609 inode = ordered->inode; > 610 btrfs_put_ordered_extent(ordered); > 611 if (delay_iput) > 612 btrfs_add_delayed_iput(inode); > 613 else > 614 iput(inode); > > # cat /proc/mounts | grep /mnt > /dev/sdc1 /mnt2 btrfs rw,relatime,ssd,space_cache 0 0 > /dev/sdd1 /mnt3 btrfs rw,relatime,ssd,space_cache 0 0 > > # btrfs fi show > Label: none uuid: 3dbe59c8-f4a0-4014-85f6-a6e9f5707c3a > Total devices 1 FS bytes used 1.44GiB > devid 1 size 1.50GiB used 1.50GiB path /dev/sdd1 > > Label: none uuid: 60130e96-5fb6-4355-b81e-8113c6f5c517 > Total devices 1 FS bytes used 32.00KiB > devid 1 size 20.00GiB used 20.00MiB path /dev/sdc1 > > All partitions have a size of 20971520 blocks according to fdisk: > Device Boot Start End Blocks Id System > /dev/sdc1 2048 41945087 20971520 83 Linux > > > With the currently pushed btrfs-next and the latest xfstests. > > >> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c >> index 0236de7..d634dbc 100644 >> --- a/fs/btrfs/extent-tree.c >> +++ b/fs/btrfs/extent-tree.c >> @@ -6065,10 +6065,13 @@ enum btrfs_loop_type { >> /* >> * walks the btree of allocated extents and find a hole of a given size. >> * The key ins is changed to record the hole: >> - * ins->objectid == block start >> + * ins->objectid == start position >> * ins->flags = BTRFS_EXTENT_ITEM_KEY >> - * ins->offset == number of blocks >> + * ins->offset == the size of the hole. >> * Any available blocks before search_start are skipped. >> + * >> + * If there is no suitable free space, we will record the max size of >> + * the free space extent currently. >> */ >> static noinline int find_free_extent(struct btrfs_trans_handle *trans, >> struct btrfs_root *orig_root, >> @@ -6082,6 +6085,7 @@ static noinline int find_free_extent(struct btrfs_trans_handle *trans, >> struct btrfs_block_group_cache *block_group = NULL; >> struct btrfs_block_group_cache *used_block_group; >> u64 search_start = 0; >> + u64 max_extent_size = 0; >> int empty_cluster = 2 * 1024 * 1024; >> struct btrfs_space_info *space_info; >> int loop = 0; >> @@ -6239,7 +6243,10 @@ have_block_group: >> btrfs_get_block_group(used_block_group); >> >> offset = btrfs_alloc_from_cluster(used_block_group, >> - last_ptr, num_bytes, used_block_group->key.objectid); >> + last_ptr, >> + num_bytes, >> + used_block_group->key.objectid, >> + &max_extent_size); >> if (offset) { >> /* we have a block, we're done */ >> spin_unlock(&last_ptr->refill_lock); >> @@ -6302,8 +6309,10 @@ refill_cluster: >> * cluster >> */ >> offset = btrfs_alloc_from_cluster(block_group, >> - last_ptr, num_bytes, >> - search_start); >> + last_ptr, >> + num_bytes, >> + search_start, >> + &max_extent_size); >> if (offset) { >> /* we found one, proceed */ >> spin_unlock(&last_ptr->refill_lock); >> @@ -6344,7 +6353,8 @@ unclustered_alloc: >> spin_unlock(&block_group->free_space_ctl->tree_lock); >> >> offset = btrfs_find_space_for_alloc(block_group, search_start, >> - num_bytes, empty_size); >> + num_bytes, empty_size, >> + &max_extent_size); >> /* >> * If we didn't find a chunk, and we haven't failed on this >> * block group before, and this block group is in the middle of >> @@ -6451,7 +6461,8 @@ loop: >> ret = 0; >> } >> out: >> - >> + if (ret == -ENOSPC) >> + ins->offset = max_extent_size; >> return ret; >> } >> >> @@ -6517,8 +6528,8 @@ again: >> hint_byte, ins, flags); >> >> if (ret == -ENOSPC) { >> - if (!final_tried) { >> - num_bytes = num_bytes >> 1; >> + if (!final_tried && ins->offset) { >> + num_bytes = min(num_bytes >> 1, ins->offset); >> num_bytes = round_down(num_bytes, root->sectorsize); >> num_bytes = max(num_bytes, min_alloc_size); >> if (num_bytes == min_alloc_size) >> diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c >> index 7517285..229c8c1 100644 >> --- a/fs/btrfs/free-space-cache.c >> +++ b/fs/btrfs/free-space-cache.c >> @@ -1434,13 +1434,19 @@ static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl, >> ctl->free_space += bytes; >> } >> >> +/* >> + * If we can not find suitable extent, we will use bytes to record >> + * the size of the max extent. >> + */ >> static int search_bitmap(struct btrfs_free_space_ctl *ctl, >> struct btrfs_free_space *bitmap_info, u64 *offset, >> u64 *bytes) >> { >> unsigned long found_bits = 0; >> + unsigned long max_bits = 0; >> unsigned long bits, i; >> unsigned long next_zero; >> + unsigned long extent_bits; >> >> i = offset_to_bit(bitmap_info->offset, ctl->unit, >> max_t(u64, *offset, bitmap_info->offset)); >> @@ -1449,9 +1455,12 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, >> for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) { >> next_zero = find_next_zero_bit(bitmap_info->bitmap, >> BITS_PER_BITMAP, i); >> - if ((next_zero - i) >= bits) { >> - found_bits = next_zero - i; >> + extent_bits = next_zero - i; >> + if (extent_bits >= bits) { >> + found_bits = extent_bits; >> break; >> + } else if (extent_bits > max_bits) { >> + max_bits = extent_bits; >> } >> i = next_zero; >> } >> @@ -1462,38 +1471,41 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, >> return 0; >> } >> >> + *bytes = (u64)(max_bits) * ctl->unit; >> return -1; >> } >> >> +/* Cache the size of the max extent in bytes */ >> static struct btrfs_free_space * >> find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, >> - unsigned long align) >> + unsigned long align, u64 *max_extent_size) >> { >> struct btrfs_free_space *entry; >> struct rb_node *node; >> - u64 ctl_off; >> u64 tmp; >> u64 align_off; >> int ret; >> >> if (!ctl->free_space_offset.rb_node) >> - return NULL; >> + goto out; >> >> entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1); >> if (!entry) >> - return NULL; >> + goto out; >> >> for (node = &entry->offset_index; node; node = rb_next(node)) { >> entry = rb_entry(node, struct btrfs_free_space, offset_index); >> - if (entry->bytes < *bytes) >> + if (entry->bytes < *bytes) { >> + if (entry->bytes > *max_extent_size) >> + *max_extent_size = entry->bytes; >> continue; >> + } >> >> /* make sure the space returned is big enough >> * to match our requested alignment >> */ >> if (*bytes >= align) { >> - ctl_off = entry->offset - ctl->start; >> - tmp = ctl_off + align - 1;; >> + tmp = entry->offset - ctl->start + align - 1; >> do_div(tmp, align); >> tmp = tmp * align + ctl->start; >> align_off = tmp - entry->offset; >> @@ -1506,10 +1518,15 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, >> continue; >> >> if (entry->bitmap) { >> - ret = search_bitmap(ctl, entry, &tmp, bytes); >> + u64 size = *bytes; >> + >> + ret = search_bitmap(ctl, entry, &tmp, &size); >> if (!ret) { >> *offset = tmp; >> + *bytes = size; >> return entry; >> + } else if (size > *max_extent_size) { >> + *max_extent_size = size; >> } >> continue; >> } >> @@ -1518,7 +1535,7 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, >> *bytes = entry->bytes - align_off; >> return entry; >> } >> - >> +out: >> return NULL; >> } >> >> @@ -2120,7 +2137,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) >> } >> >> u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, >> - u64 offset, u64 bytes, u64 empty_size) >> + u64 offset, u64 bytes, u64 empty_size, >> + u64 *max_extent_size) >> { >> struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; >> struct btrfs_free_space *entry = NULL; >> @@ -2131,7 +2149,7 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, >> >> spin_lock(&ctl->tree_lock); >> entry = find_free_space(ctl, &offset, &bytes_search, >> - block_group->full_stripe_len); >> + block_group->full_stripe_len, max_extent_size); >> if (!entry) >> goto out; >> >> @@ -2141,7 +2159,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, >> if (!entry->bytes) >> free_bitmap(ctl, entry); >> } else { >> - >> unlink_free_space(ctl, entry); >> align_gap_len = offset - entry->offset; >> align_gap = entry->offset; >> @@ -2155,7 +2172,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, >> else >> link_free_space(ctl, entry); >> } >> - >> out: >> spin_unlock(&ctl->tree_lock); >> >> @@ -2210,7 +2226,8 @@ int btrfs_return_cluster_to_free_space( >> static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, >> struct btrfs_free_cluster *cluster, >> struct btrfs_free_space *entry, >> - u64 bytes, u64 min_start) >> + u64 bytes, u64 min_start, >> + u64 *max_extent_size) >> { >> struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; >> int err; >> @@ -2222,8 +2239,11 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, >> search_bytes = bytes; >> >> err = search_bitmap(ctl, entry, &search_start, &search_bytes); >> - if (err) >> + if (err) { >> + if (search_bytes > *max_extent_size) >> + *max_extent_size = search_bytes; >> return 0; >> + } >> >> ret = search_start; >> __bitmap_clear_bits(ctl, entry, ret, bytes); >> @@ -2238,7 +2258,7 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, >> */ >> u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, >> struct btrfs_free_cluster *cluster, u64 bytes, >> - u64 min_start) >> + u64 min_start, u64 *max_extent_size) >> { >> struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; >> struct btrfs_free_space *entry = NULL; >> @@ -2258,6 +2278,9 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, >> >> entry = rb_entry(node, struct btrfs_free_space, offset_index); >> while(1) { >> + if (entry->bytes < bytes && entry->bytes > *max_extent_size) >> + *max_extent_size = entry->bytes; >> + >> if (entry->bytes < bytes || >> (!entry->bitmap && entry->offset < min_start)) { >> node = rb_next(&entry->offset_index); >> @@ -2271,7 +2294,8 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, >> if (entry->bitmap) { >> ret = btrfs_alloc_from_bitmap(block_group, >> cluster, entry, bytes, >> - cluster->window_start); >> + cluster->window_start, >> + max_extent_size); >> if (ret == 0) { >> node = rb_next(&entry->offset_index); >> if (!node) >> diff --git a/fs/btrfs/free-space-cache.h b/fs/btrfs/free-space-cache.h >> index 894116b..a701000 100644 >> --- a/fs/btrfs/free-space-cache.h >> +++ b/fs/btrfs/free-space-cache.h >> @@ -94,7 +94,8 @@ void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl); >> void btrfs_remove_free_space_cache(struct btrfs_block_group_cache >> *block_group); >> u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, >> - u64 offset, u64 bytes, u64 empty_size); >> + u64 offset, u64 bytes, u64 empty_size, >> + u64 *max_extent_size); >> u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root); >> void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group, >> u64 bytes); >> @@ -106,7 +107,7 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, >> void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster); >> u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, >> struct btrfs_free_cluster *cluster, u64 bytes, >> - u64 min_start); >> + u64 min_start, u64 *max_extent_size); >> int btrfs_return_cluster_to_free_space( >> struct btrfs_block_group_cache *block_group, >> struct btrfs_free_cluster *cluster); >> > > > -- > To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html > -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 09/09/2013 08:21, Miao Xie wrote: > On fri, 06 Sep 2013 15:47:08 +0200, Stefan Behrens wrote: >> On Fri, 30 Aug 2013 18:35:34 +0800, Miao Xie wrote: >>> By the current code, if the requested size is very large, and all the extents >>> in the free space cache are small, we will waste lots of the cpu time to cut >>> the requested size in half and search the cache again and again until it gets >>> down to the size the allocator can return. In fact, we can know the max extent >>> size in the cache after the first search, so we needn't cut the size in half >>> repeatedly, and just use the max extent size directly. This way can save >>> lots of cpu time and make the performance grow up when there are only fragments >>> in the free space cache. >>> >>> According to my test, if there are only 4KB free space extents in the fs, >>> and the total size of those extents are 256MB, we can reduce the execute >>> time of the following test from 5.4s to 1.4s. >>> dd if=/dev/zero of=<testfile> bs=1MB count=1 oflag=sync >>> >>> Signed-off-by: Miao Xie <miaox@cn.fujitsu.com> >>> --- >>> Changelog v1 -> v2: >>> - address the problem that we return a wrong start position when searching >>> the free space in a bitmap. >>> --- >>> fs/btrfs/extent-tree.c | 29 ++++++++++++++------- >>> fs/btrfs/free-space-cache.c | 62 +++++++++++++++++++++++++++++++-------------- >>> fs/btrfs/free-space-cache.h | 5 ++-- >>> 3 files changed, 66 insertions(+), 30 deletions(-) >> >> This patch makes the xfstest generic/256 lock up. It's quite reliably reproducible on one of my test boxes, and not at all visible on a second test box. >> >> And yes, I'm using the V2 patch although you haven't tagged it as V2 in the subject line of the mail :) > > According to my debug, the machine was not locked up, it seems the patch makes the test run very slow(90s ->850s on my machine). With v2, the xfstest generic/256 was still running after 2 1/2 days with the 'echo w > /proc/sysrq-trigger' output as reported. > Could you try the v3 patch? With v3, generic/256 always finishes after 26 seconds. The issue is fixed with v3. >> >> # reboot >> ... reboot done >> # cd ~/git/xfs/cmds/xfstests >> # export TEST_DEV=/dev/sdc1 >> # export TEST_DIR=/mnt2 >> # export SCRATCH_DEV=/dev/sdd1 >> # export SCRATCH_MNT=/mnt3 >> # umount $TEST_DIR $SCRATCH_MNT >> # mkfs.btrfs -f $TEST_DEV >> # mkfs.btrfs -f $SCRATCH_DEV >> # ./check generic/256 >> ...should be finished after 20s, but it isn't, therefore after 180s: >> # echo w > /proc/sysrq-trigger >> root: run xfstest generic/256 >> SysRq : Show Blocked State >> task PC stack pid father >> btrfs-flush_del D 000000001a6d0000 6240 31190 2 0x00000000 >> ffff880804dbfcb8 0000000000000086 ffff880804dbffd8 ffff8807ef218000 >> ffff880804dbffd8 ffff880804dbffd8 ffff88080ad44520 ffff8807ef218000 >> ffff880804dbfc98 ffff880784d3ca50 ffff880784d3ca18 ffff880804dbfce8 >> Call Trace: >> [<ffffffff81995da4>] schedule+0x24/0x60 >> [<ffffffffa05235c5>] btrfs_start_ordered_extent+0x85/0x130 [btrfs] >> [<ffffffff810ac170>] ? wake_up_bit+0x40/0x40 >> [<ffffffffa0523694>] btrfs_run_ordered_extent_work+0x24/0x40 [btrfs] >> [<ffffffffa0539d5f>] worker_loop+0x13f/0x5b0 [btrfs] >> [<ffffffff810b5ba3>] ? finish_task_switch+0x43/0x110 >> [<ffffffff81995880>] ? __schedule+0x3f0/0x860 >> [<ffffffffa0539c20>] ? btrfs_queue_worker+0x300/0x300 [btrfs] >> [<ffffffff810abd36>] kthread+0xd6/0xe0 >> [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 >> [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 >> [<ffffffff8199f66c>] ret_from_fork+0x7c/0xb0 >> [<ffffffff810abc60>] ? kthread_create_on_node+0x130/0x130 >> xfs_io D ffff880784d3cbc0 5008 31241 31240 0x00000000 >> ffff8808036f3868 0000000000000082 ffff8808036f3fd8 ffff8807c9878000 >> ffff8808036f3fd8 ffff8808036f3fd8 ffffffff82010440 ffff8807c9878000 >> ffff8808036f3848 ffff880784d3cb18 ffff880784d3cb20 7fffffffffffffff >> Call Trace: >> [<ffffffff81995da4>] schedule+0x24/0x60 >> [<ffffffff81992dc4>] schedule_timeout+0x194/0x260 >> [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 >> [<ffffffff8199513a>] ? wait_for_completion+0x3a/0x110 >> [<ffffffff810e61ed>] ? trace_hardirqs_on+0xd/0x10 >> [<ffffffff819951cf>] wait_for_completion+0xcf/0x110 >> [<ffffffff810bb650>] ? try_to_wake_up+0x310/0x310 >> [<ffffffffa0523b7a>] btrfs_wait_ordered_extents+0x1ea/0x260 [btrfs] >> [<ffffffffa0523ce5>] btrfs_wait_all_ordered_extents+0xf5/0x150 [btrfs] >> [<ffffffffa04f4b8d>] reserve_metadata_bytes+0x7bd/0xa30 [btrfs] >> [<ffffffffa04f516d>] btrfs_delalloc_reserve_metadata+0x16d/0x460 [btrfs] >> [<ffffffffa051dad6>] __btrfs_buffered_write+0x276/0x4f0 [btrfs] >> [<ffffffffa051df1a>] btrfs_file_aio_write+0x1ca/0x5a0 [btrfs] >> [<ffffffff8119a6db>] do_sync_write+0x7b/0xb0 >> [<ffffffff8119b463>] vfs_write+0xc3/0x1e0 >> [<ffffffff8119bad2>] SyS_pwrite64+0x92/0xb0 >> [<ffffffff8199f712>] system_call_fastpath+0x16/0x1b >> >> (gdb) list *(btrfs_start_ordered_extent+0x85) >> 0x4a545 is in btrfs_start_ordered_extent (fs/btrfs/ordered-data.c:747). >> 742 * for the flusher thread to find them >> 743 */ >> 744 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) >> 745 filemap_fdatawrite_range(inode->i_mapping, start, end); >> 746 if (wait) { >> 747 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, >> 748 &entry->flags)); >> 749 } >> 750 } >> 751 >> >> (gdb) list *(btrfs_wait_ordered_extents+0x1ea) >> 0x4aafa is in btrfs_wait_ordered_extents (fs/btrfs/ordered-data.c:610). >> 605 list_for_each_entry_safe(ordered, next, &works, work_list) { >> 606 list_del_init(&ordered->work_list); >> 607 wait_for_completion(&ordered->completion); >> 608 >> 609 inode = ordered->inode; >> 610 btrfs_put_ordered_extent(ordered); >> 611 if (delay_iput) >> 612 btrfs_add_delayed_iput(inode); >> 613 else >> 614 iput(inode); >> >> # cat /proc/mounts | grep /mnt >> /dev/sdc1 /mnt2 btrfs rw,relatime,ssd,space_cache 0 0 >> /dev/sdd1 /mnt3 btrfs rw,relatime,ssd,space_cache 0 0 >> >> # btrfs fi show >> Label: none uuid: 3dbe59c8-f4a0-4014-85f6-a6e9f5707c3a >> Total devices 1 FS bytes used 1.44GiB >> devid 1 size 1.50GiB used 1.50GiB path /dev/sdd1 >> >> Label: none uuid: 60130e96-5fb6-4355-b81e-8113c6f5c517 >> Total devices 1 FS bytes used 32.00KiB >> devid 1 size 20.00GiB used 20.00MiB path /dev/sdc1 >> >> All partitions have a size of 20971520 blocks according to fdisk: >> Device Boot Start End Blocks Id System >> /dev/sdc1 2048 41945087 20971520 83 Linux >> >> >> With the currently pushed btrfs-next and the latest xfstests. >> -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Sep 09, 2013 at 02:21:58PM +0800, Miao Xie wrote: > On fri, 06 Sep 2013 15:47:08 +0200, Stefan Behrens wrote: > > This patch makes the xfstest generic/256 lock up. It's quite > > reliably reproducible on one of my test boxes, and not at all > > visible on a second test box. > > > > And yes, I'm using the V2 patch although you haven't tagged it as V2 > > in the subject line of the mail :) > > According to my debug, the machine was not locked up, it seems the > patch makes the test run very slow(90s ->850s on my machine). The massive slowdown is present in current 3.12-rc code, which means V3 did not make it into the pull. Miao please send an incremental fix for rc2. thanks, david -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 17 Sep 2013 15:13:12 +0200, David Sterba wrote: > On Mon, Sep 09, 2013 at 02:21:58PM +0800, Miao Xie wrote: >> On fri, 06 Sep 2013 15:47:08 +0200, Stefan Behrens wrote: >>> This patch makes the xfstest generic/256 lock up. It's quite >>> reliably reproducible on one of my test boxes, and not at all >>> visible on a second test box. >>> >>> And yes, I'm using the V2 patch although you haven't tagged it as V2 >>> in the subject line of the mail :) >> >> According to my debug, the machine was not locked up, it seems the >> patch makes the test run very slow(90s ->850s on my machine). > > The massive slowdown is present in current 3.12-rc code, which means V3 > did not make it into the pull. > > Miao please send an incremental fix for rc2. This patch has not been merged into 3.12-rc, so the above problem should be introduced by other patch. Thanks Miao > > thanks, > david > -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Sep 18, 2013 at 12:04:30PM +0800, Miao Xie wrote: > On Tue, 17 Sep 2013 15:13:12 +0200, David Sterba wrote: > > On Mon, Sep 09, 2013 at 02:21:58PM +0800, Miao Xie wrote: > >> On fri, 06 Sep 2013 15:47:08 +0200, Stefan Behrens wrote: > > The massive slowdown is present in current 3.12-rc code, which means V3 > > did not make it into the pull. > > > > Miao please send an incremental fix for rc2. > > This patch has not been merged into 3.12-rc, so the above problem should be > introduced by other patch. Sorry, my oversight. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 0236de7..d634dbc 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -6065,10 +6065,13 @@ enum btrfs_loop_type { /* * walks the btree of allocated extents and find a hole of a given size. * The key ins is changed to record the hole: - * ins->objectid == block start + * ins->objectid == start position * ins->flags = BTRFS_EXTENT_ITEM_KEY - * ins->offset == number of blocks + * ins->offset == the size of the hole. * Any available blocks before search_start are skipped. + * + * If there is no suitable free space, we will record the max size of + * the free space extent currently. */ static noinline int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root *orig_root, @@ -6082,6 +6085,7 @@ static noinline int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_block_group_cache *block_group = NULL; struct btrfs_block_group_cache *used_block_group; u64 search_start = 0; + u64 max_extent_size = 0; int empty_cluster = 2 * 1024 * 1024; struct btrfs_space_info *space_info; int loop = 0; @@ -6239,7 +6243,10 @@ have_block_group: btrfs_get_block_group(used_block_group); offset = btrfs_alloc_from_cluster(used_block_group, - last_ptr, num_bytes, used_block_group->key.objectid); + last_ptr, + num_bytes, + used_block_group->key.objectid, + &max_extent_size); if (offset) { /* we have a block, we're done */ spin_unlock(&last_ptr->refill_lock); @@ -6302,8 +6309,10 @@ refill_cluster: * cluster */ offset = btrfs_alloc_from_cluster(block_group, - last_ptr, num_bytes, - search_start); + last_ptr, + num_bytes, + search_start, + &max_extent_size); if (offset) { /* we found one, proceed */ spin_unlock(&last_ptr->refill_lock); @@ -6344,7 +6353,8 @@ unclustered_alloc: spin_unlock(&block_group->free_space_ctl->tree_lock); offset = btrfs_find_space_for_alloc(block_group, search_start, - num_bytes, empty_size); + num_bytes, empty_size, + &max_extent_size); /* * If we didn't find a chunk, and we haven't failed on this * block group before, and this block group is in the middle of @@ -6451,7 +6461,8 @@ loop: ret = 0; } out: - + if (ret == -ENOSPC) + ins->offset = max_extent_size; return ret; } @@ -6517,8 +6528,8 @@ again: hint_byte, ins, flags); if (ret == -ENOSPC) { - if (!final_tried) { - num_bytes = num_bytes >> 1; + if (!final_tried && ins->offset) { + num_bytes = min(num_bytes >> 1, ins->offset); num_bytes = round_down(num_bytes, root->sectorsize); num_bytes = max(num_bytes, min_alloc_size); if (num_bytes == min_alloc_size) diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index 7517285..229c8c1 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c @@ -1434,13 +1434,19 @@ static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl, ctl->free_space += bytes; } +/* + * If we can not find suitable extent, we will use bytes to record + * the size of the max extent. + */ static int search_bitmap(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *bitmap_info, u64 *offset, u64 *bytes) { unsigned long found_bits = 0; + unsigned long max_bits = 0; unsigned long bits, i; unsigned long next_zero; + unsigned long extent_bits; i = offset_to_bit(bitmap_info->offset, ctl->unit, max_t(u64, *offset, bitmap_info->offset)); @@ -1449,9 +1455,12 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) { next_zero = find_next_zero_bit(bitmap_info->bitmap, BITS_PER_BITMAP, i); - if ((next_zero - i) >= bits) { - found_bits = next_zero - i; + extent_bits = next_zero - i; + if (extent_bits >= bits) { + found_bits = extent_bits; break; + } else if (extent_bits > max_bits) { + max_bits = extent_bits; } i = next_zero; } @@ -1462,38 +1471,41 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl, return 0; } + *bytes = (u64)(max_bits) * ctl->unit; return -1; } +/* Cache the size of the max extent in bytes */ static struct btrfs_free_space * find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, - unsigned long align) + unsigned long align, u64 *max_extent_size) { struct btrfs_free_space *entry; struct rb_node *node; - u64 ctl_off; u64 tmp; u64 align_off; int ret; if (!ctl->free_space_offset.rb_node) - return NULL; + goto out; entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1); if (!entry) - return NULL; + goto out; for (node = &entry->offset_index; node; node = rb_next(node)) { entry = rb_entry(node, struct btrfs_free_space, offset_index); - if (entry->bytes < *bytes) + if (entry->bytes < *bytes) { + if (entry->bytes > *max_extent_size) + *max_extent_size = entry->bytes; continue; + } /* make sure the space returned is big enough * to match our requested alignment */ if (*bytes >= align) { - ctl_off = entry->offset - ctl->start; - tmp = ctl_off + align - 1;; + tmp = entry->offset - ctl->start + align - 1; do_div(tmp, align); tmp = tmp * align + ctl->start; align_off = tmp - entry->offset; @@ -1506,10 +1518,15 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, continue; if (entry->bitmap) { - ret = search_bitmap(ctl, entry, &tmp, bytes); + u64 size = *bytes; + + ret = search_bitmap(ctl, entry, &tmp, &size); if (!ret) { *offset = tmp; + *bytes = size; return entry; + } else if (size > *max_extent_size) { + *max_extent_size = size; } continue; } @@ -1518,7 +1535,7 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, *bytes = entry->bytes - align_off; return entry; } - +out: return NULL; } @@ -2120,7 +2137,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) } u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, - u64 offset, u64 bytes, u64 empty_size) + u64 offset, u64 bytes, u64 empty_size, + u64 *max_extent_size) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; struct btrfs_free_space *entry = NULL; @@ -2131,7 +2149,7 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, spin_lock(&ctl->tree_lock); entry = find_free_space(ctl, &offset, &bytes_search, - block_group->full_stripe_len); + block_group->full_stripe_len, max_extent_size); if (!entry) goto out; @@ -2141,7 +2159,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, if (!entry->bytes) free_bitmap(ctl, entry); } else { - unlink_free_space(ctl, entry); align_gap_len = offset - entry->offset; align_gap = entry->offset; @@ -2155,7 +2172,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, else link_free_space(ctl, entry); } - out: spin_unlock(&ctl->tree_lock); @@ -2210,7 +2226,8 @@ int btrfs_return_cluster_to_free_space( static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, struct btrfs_free_cluster *cluster, struct btrfs_free_space *entry, - u64 bytes, u64 min_start) + u64 bytes, u64 min_start, + u64 *max_extent_size) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; int err; @@ -2222,8 +2239,11 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, search_bytes = bytes; err = search_bitmap(ctl, entry, &search_start, &search_bytes); - if (err) + if (err) { + if (search_bytes > *max_extent_size) + *max_extent_size = search_bytes; return 0; + } ret = search_start; __bitmap_clear_bits(ctl, entry, ret, bytes); @@ -2238,7 +2258,7 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, */ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, struct btrfs_free_cluster *cluster, u64 bytes, - u64 min_start) + u64 min_start, u64 *max_extent_size) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; struct btrfs_free_space *entry = NULL; @@ -2258,6 +2278,9 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, entry = rb_entry(node, struct btrfs_free_space, offset_index); while(1) { + if (entry->bytes < bytes && entry->bytes > *max_extent_size) + *max_extent_size = entry->bytes; + if (entry->bytes < bytes || (!entry->bitmap && entry->offset < min_start)) { node = rb_next(&entry->offset_index); @@ -2271,7 +2294,8 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, if (entry->bitmap) { ret = btrfs_alloc_from_bitmap(block_group, cluster, entry, bytes, - cluster->window_start); + cluster->window_start, + max_extent_size); if (ret == 0) { node = rb_next(&entry->offset_index); if (!node) diff --git a/fs/btrfs/free-space-cache.h b/fs/btrfs/free-space-cache.h index 894116b..a701000 100644 --- a/fs/btrfs/free-space-cache.h +++ b/fs/btrfs/free-space-cache.h @@ -94,7 +94,8 @@ void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl); void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group); u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, - u64 offset, u64 bytes, u64 empty_size); + u64 offset, u64 bytes, u64 empty_size, + u64 *max_extent_size); u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root); void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group, u64 bytes); @@ -106,7 +107,7 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster); u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, struct btrfs_free_cluster *cluster, u64 bytes, - u64 min_start); + u64 min_start, u64 *max_extent_size); int btrfs_return_cluster_to_free_space( struct btrfs_block_group_cache *block_group, struct btrfs_free_cluster *cluster);
By the current code, if the requested size is very large, and all the extents in the free space cache are small, we will waste lots of the cpu time to cut the requested size in half and search the cache again and again until it gets down to the size the allocator can return. In fact, we can know the max extent size in the cache after the first search, so we needn't cut the size in half repeatedly, and just use the max extent size directly. This way can save lots of cpu time and make the performance grow up when there are only fragments in the free space cache. According to my test, if there are only 4KB free space extents in the fs, and the total size of those extents are 256MB, we can reduce the execute time of the following test from 5.4s to 1.4s. dd if=/dev/zero of=<testfile> bs=1MB count=1 oflag=sync Signed-off-by: Miao Xie <miaox@cn.fujitsu.com> --- Changelog v1 -> v2: - address the problem that we return a wrong start position when searching the free space in a bitmap. --- fs/btrfs/extent-tree.c | 29 ++++++++++++++------- fs/btrfs/free-space-cache.c | 62 +++++++++++++++++++++++++++++++-------------- fs/btrfs/free-space-cache.h | 5 ++-- 3 files changed, 66 insertions(+), 30 deletions(-)