Btrfs: allocate the free space by the existed max extent size when ENOSPC

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

Changelog v2 -> v3:
- fix the problem that we skip the block group with the space which is
  less than we need.

Changelog v1 -> v2:
- address the problem that we return a wrong start position when searching
  the free space in a bitmap.

Signed-off-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>

1 files changed, 24 insertions, 9 deletions

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index cfb3cf711b34..2f03181b777f 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -6117,10 +6117,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_root *orig_root,
                                      u64 num_bytes, u64 empty_size,
@@ -6133,6 +6136,7 @@ static noinline int find_free_extent(struct btrfs_root *orig_root,
         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;
@@ -6292,7 +6296,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);
@@ -6355,8 +6362,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);
@@ -6391,13 +6400,18 @@ unclustered_alloc:
                 if (cached &&
                     block_group->free_space_ctl->free_space <
                     num_bytes + empty_cluster + empty_size) {
+                        if (block_group->free_space_ctl->free_space >
+                            max_extent_size)
+                                max_extent_size =
+                                        block_group->free_space_ctl->free_space;
                         spin_unlock(&block_group->free_space_ctl->tree_lock);
                         goto loop;
                 }
                 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
@@ -6515,7 +6529,8 @@ loop:
                 ret = 0;
         }
 out:
-
+        if (ret == -ENOSPC)
+                ins->offset = max_extent_size;
         return ret;
 }
 
@@ -6573,8 +6588,8 @@ again:
                                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)