Btrfs: more allocator enhancements

Signed-off-by: Chris Mason <chris.mason@oracle.com>

1 files changed, 238 insertions, 79 deletions

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index c5ae51893f78..2937fd9aba74 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -12,36 +12,88 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
                                btrfs_root *extent_root);
 
+static struct btrfs_block_group_cache *lookup_block_group(struct
+                                                          btrfs_fs_info *info,
+                                                          u64 blocknr)
+{
+        struct btrfs_block_group_cache *block_group;
+        int ret;
+
+        ret = radix_tree_gang_lookup(&info->block_group_radix,
+                                     (void **)&block_group,
+                                     blocknr, 1);
+        if (ret) {
+                if (block_group->key.objectid <= blocknr && blocknr <
+                    block_group->key.objectid + block_group->key.offset)
+                        return block_group;
+        }
+        ret = radix_tree_gang_lookup(&info->block_group_data_radix,
+                                     (void **)&block_group,
+                                     blocknr, 1);
+        if (ret) {
+                if (block_group->key.objectid <= blocknr && blocknr <
+                    block_group->key.objectid + block_group->key.offset)
+                        return block_group;
+        }
+printk("lookup_block_group fails for blocknr %Lu\n", blocknr);
+        return NULL;
+}
+
 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
                                                  struct btrfs_block_group_cache
-                                                 *hint, int data)
+                                                 *hint, u64 search_start,
+                                                 int data)
 {
         struct btrfs_block_group_cache *cache[8];
         struct btrfs_block_group_cache *found_group = NULL;
         struct btrfs_fs_info *info = root->fs_info;
+        struct radix_tree_root *radix;
         u64 used;
         u64 last = 0;
         u64 hint_last;
         int i;
         int ret;
         int full_search = 0;
-        if (!data && hint) {
+
+        if (data)
+                radix = &info->block_group_data_radix;
+        else
+                radix = &info->block_group_radix;
+
+        if (search_start) {
+                struct btrfs_block_group_cache *shint;
+                shint = lookup_block_group(info, search_start);
+                if (shint->data == data) {
+                        used = btrfs_block_group_used(&shint->item);
+                        if (used + shint->pinned <
+                            (shint->key.offset * 8) / 10) {
+                                return shint;
+                        }
+                }
+        }
+        if (hint && hint->data == data) {
                 used = btrfs_block_group_used(&hint->item);
-                if (used < (hint->key.offset * 2) / 3) {
+                if (used + hint->pinned < (hint->key.offset * 8) / 10) {
                         return hint;
                 }
-                radix_tree_tag_clear(&info->block_group_radix,
-                                     hint->key.objectid + hint->key.offset - 1,
-                                     BTRFS_BLOCK_GROUP_AVAIL);
-                last = hint->key.objectid + hint->key.offset;
+                if (used >= (hint->key.offset * 8) / 10) {
+                        radix_tree_tag_clear(radix,
+                                             hint->key.objectid +
+                                             hint->key.offset - 1,
+                                             BTRFS_BLOCK_GROUP_AVAIL);
+                }
+                last = hint->key.offset * 2;
+                if (hint->key.objectid >= last)
+                        last = max(search_start, hint->key.objectid - last);
+                else
+                        last = hint->key.objectid + hint->key.offset;
                 hint_last = last;
         } else {
-                hint_last = 0;
-                last = 0;
+                hint_last = search_start;
+                last = search_start;
         }
         while(1) {
-                ret = radix_tree_gang_lookup_tag(&info->block_group_radix,
-                                                 (void **)cache,
+                ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
                                                  last, ARRAY_SIZE(cache),
                                                  BTRFS_BLOCK_GROUP_AVAIL);
                 if (!ret)
@@ -49,65 +101,54 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
                 for (i = 0; i < ret; i++) {
                         last = cache[i]->key.objectid +
                                 cache[i]->key.offset;
-                        if (!full_search && !data &&
-                           (cache[i]->key.objectid & cache[i]->key.offset))
-                                continue;
-                        if (!full_search && data &&
-                           (cache[i]->key.objectid & cache[i]->key.offset) == 0)
-                                continue;
                         used = btrfs_block_group_used(&cache[i]->item);
-                        if (used < (cache[i]->key.offset * 2) / 3) {
-                                info->block_group_cache = cache[i];
+                        if (used + cache[i]->pinned <
+                            (cache[i]->key.offset * 8) / 10) {
                                 found_group = cache[i];
                                 goto found;
                         }
-                        radix_tree_tag_clear(&info->block_group_radix,
-                                           cache[i]->key.objectid +
-                                           cache[i]->key.offset - 1,
-                                           BTRFS_BLOCK_GROUP_AVAIL);
+                        if (used >= (cache[i]->key.offset * 8) / 10) {
+                                radix_tree_tag_clear(radix,
+                                                     cache[i]->key.objectid +
+                                                     cache[i]->key.offset - 1,
+                                                     BTRFS_BLOCK_GROUP_AVAIL);
+                        }
                 }
         }
         last = hint_last;
 again:
         while(1) {
-                ret = radix_tree_gang_lookup(&info->block_group_radix,
-                                                 (void **)cache,
-                                                 last, ARRAY_SIZE(cache));
+                ret = radix_tree_gang_lookup(radix, (void **)cache,
+                                             last, ARRAY_SIZE(cache));
                 if (!ret)
                         break;
                 for (i = 0; i < ret; i++) {
                         last = cache[i]->key.objectid +
                                 cache[i]->key.offset;
-                        if (!full_search && !data &&
-                           (cache[i]->key.objectid & cache[i]->key.offset))
-                                continue;
-                        if (!full_search && data &&
-                           (cache[i]->key.objectid & cache[i]->key.offset) == 0)
-                                continue;
                         used = btrfs_block_group_used(&cache[i]->item);
-                        if (used < cache[i]->key.offset) {
-                                info->block_group_cache = cache[i];
+                        if (used + cache[i]->pinned < cache[i]->key.offset) {
                                 found_group = cache[i];
                                 goto found;
                         }
-                        radix_tree_tag_clear(&info->block_group_radix,
-                                           cache[i]->key.objectid +
-                                           cache[i]->key.offset - 1,
-                                           BTRFS_BLOCK_GROUP_AVAIL);
+                        if (used >= cache[i]->key.offset) {
+                                radix_tree_tag_clear(radix,
+                                                     cache[i]->key.objectid +
+                                                     cache[i]->key.offset - 1,
+                                                     BTRFS_BLOCK_GROUP_AVAIL);
+                        }
                 }
         }
-        info->block_group_cache = NULL;
         if (!full_search) {
-                last = 0;
+                last = search_start;
                 full_search = 1;
                 goto again;
         }
-found:
         if (!found_group) {
-                ret = radix_tree_gang_lookup(&info->block_group_radix,
+                ret = radix_tree_gang_lookup(radix,
                                              (void **)&found_group, 0, 1);
                 BUG_ON(ret != 1);
         }
+found:
         return found_group;
 }
 
@@ -252,18 +293,20 @@ static int write_one_cache_group(struct btrfs_trans_handle *trans,
                 return ret;
         if (pending_ret)
                 return pending_ret;
+        if (cache->data)
+                cache->last_alloc = cache->first_free;
         return 0;
 
 }
 
-int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
-                                    struct btrfs_root *root)
+static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
+                                   struct btrfs_root *root,
+                                   struct radix_tree_root *radix)
 {
         struct btrfs_block_group_cache *cache[8];
         int ret;
         int err = 0;
         int werr = 0;
-        struct radix_tree_root *radix = &root->fs_info->block_group_radix;
         int i;
         struct btrfs_path *path;
 
@@ -285,35 +328,74 @@ int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
                                                     path, cache[i]);
                         if (err)
                                 werr = err;
-                        cache[i]->last_alloc = cache[i]->first_free;
                 }
         }
         btrfs_free_path(path);
         return werr;
 }
 
+int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
+                                   struct btrfs_root *root)
+{
+        int ret;
+        int ret2;
+        ret = write_dirty_block_radix(trans, root,
+                                      &root->fs_info->block_group_radix);
+        ret2 = write_dirty_block_radix(trans, root,
+                                      &root->fs_info->block_group_data_radix);
+        if (ret)
+                return ret;
+        if (ret2)
+                return ret2;
+        return 0;
+}
+
 static int update_block_group(struct btrfs_trans_handle *trans,
                               struct btrfs_root *root,
                               u64 blocknr, u64 num, int alloc)
 {
         struct btrfs_block_group_cache *cache;
         struct btrfs_fs_info *info = root->fs_info;
+        struct radix_tree_root *radix;
         u64 total = num;
         u64 old_val;
         u64 block_in_group;
         int ret;
+        if (num != 1)
+                radix = &info->block_group_data_radix;
+        else
+                radix = &info->block_group_radix;
         while(total) {
-                ret = radix_tree_gang_lookup(&info->block_group_radix,
-                                             (void **)&cache, blocknr, 1);
+                ret = radix_tree_gang_lookup(radix, (void **)&cache,
+                                             blocknr, 1);
                 if (!ret) {
                         printk(KERN_CRIT "blocknr %Lu lookup failed\n",
                                blocknr);
                         return -1;
                 }
                 block_in_group = blocknr - cache->key.objectid;
+                if (block_in_group > cache->key.offset || cache->key.objectid >
+                    blocknr) {
+                        if (radix == &info->block_group_data_radix)
+                                radix = &info->block_group_radix;
+                        else
+                                radix = &info->block_group_data_radix;
+                        ret = radix_tree_gang_lookup(radix, (void **)&cache,
+                                                     blocknr, 1);
+                        if (!ret) {
+                                printk(KERN_CRIT "blocknr %Lu lookup failed\n",
+                                       blocknr);
+                                return -1;
+                        }
+                        block_in_group = blocknr - cache->key.objectid;
+                        if (block_in_group > cache->key.offset ||
+                            cache->key.objectid > blocknr) {
+                                BUG();
+                        }
+                }
                 WARN_ON(block_in_group > cache->key.offset);
-                radix_tree_tag_set(&info->block_group_radix,
-                                   cache->key.objectid + cache->key.offset - 1,
+                radix_tree_tag_set(radix, cache->key.objectid +
+                                   cache->key.offset - 1,
                                    BTRFS_BLOCK_GROUP_DIRTY);
 
                 old_val = btrfs_block_group_used(&cache->item);
@@ -346,6 +428,7 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
 {
         unsigned long gang[8];
         struct inode *btree_inode = root->fs_info->btree_inode;
+        struct btrfs_block_group_cache *block_group;
         u64 first = 0;
         int ret;
         int i;
@@ -360,6 +443,14 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
                         first = gang[0];
                 for (i = 0; i < ret; i++) {
                         clear_radix_bit(pinned_radix, gang[i]);
+                        block_group = lookup_block_group(root->fs_info,
+                                                         gang[i]);
+                        if (block_group) {
+                                WARN_ON(block_group->pinned == 0);
+                                block_group->pinned--;
+                                if (gang[i] < block_group->last_alloc)
+                                        block_group->last_alloc = gang[i];
+                        }
                         try_remove_page(btree_inode->i_mapping,
                                         gang[i] << (PAGE_CACHE_SHIFT -
                                                     btree_inode->i_blkbits));
@@ -420,10 +511,16 @@ static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
                         btrfs_block_release(root, bh);
                 }
                 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
+                if (!err) {
+                        struct btrfs_block_group_cache *cache;
+                        cache = lookup_block_group(root->fs_info, blocknr);
+                        if (cache)
+                                cache->pinned++;
+                }
         } else {
                 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
         }
-        BUG_ON(err);
+        BUG_ON(err < 0);
         return 0;
 }
 
@@ -502,6 +599,7 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
         int i;
         struct radix_tree_root *pending_radix;
         struct radix_tree_root *pinned_radix;
+        struct btrfs_block_group_cache *cache;
 
         pending_radix = &extent_root->fs_info->pending_del_radix;
         pinned_radix = &extent_root->fs_info->pinned_radix;
@@ -513,7 +611,17 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
                         break;
                 for (i = 0; i < ret; i++) {
                         wret = set_radix_bit(pinned_radix, gang[i]);
-                        BUG_ON(wret);
+                        if (wret == 0) {
+                                cache = lookup_block_group(extent_root->fs_info,
+                                                           gang[i]);
+                                if (cache)
+                                        cache->pinned++;
+                        }
+                        if (wret < 0) {
+                                printk(KERN_CRIT "set_radix_bit, err %d\n",
+                                       wret);
+                                BUG_ON(wret < 0);
+                        }
                         wret = clear_radix_bit(pending_radix, gang[i]);
                         BUG_ON(wret);
                         wret = __free_extent(trans, extent_root,
@@ -563,6 +671,7 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
         int slot = 0;
         u64 last_block = 0;
         u64 test_block;
+        u64 orig_search_start = search_start;
         int start_found;
         struct btrfs_leaf *l;
         struct btrfs_root * root = orig_root->fs_info->extent_root;
@@ -572,6 +681,7 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
         int fill_prealloc = 0;
         int level;
         struct btrfs_block_group_cache *block_group;
+        int full_scan = 0;
 
         path = btrfs_alloc_path();
         ins->flags = 0;
@@ -583,10 +693,21 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
                 num_blocks = 1;
                 total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
         }
-        block_group = btrfs_find_block_group(root, trans->block_group, data);
+        if (search_start) {
+                block_group = lookup_block_group(info, search_start);
+                block_group = btrfs_find_block_group(root, block_group,
+                                                     search_start, data);
+        } else {
+                block_group = btrfs_find_block_group(root,
+                                                     trans->block_group, 0,
+                                                     data);
+        }
+
+check_failed:
+        if (block_group->data != data)
+                WARN_ON(1);
         if (block_group->last_alloc > search_start)
                 search_start = block_group->last_alloc;
-check_failed:
         btrfs_init_path(path);
         ins->objectid = search_start;
         ins->offset = 0;
@@ -639,6 +760,13 @@ check_failed:
                 }
                 start_found = 1;
                 last_block = key.objectid + key.offset;
+                if (last_block >= block_group->key.objectid +
+                    block_group->key.offset) {
+                        btrfs_release_path(root, path);
+                        search_start = block_group->key.objectid +
+                                block_group->key.offset * 2;
+                        goto new_group;
+                }
 next:
                 path->slots[0]++;
         }
@@ -650,16 +778,17 @@ check_pending:
         btrfs_release_path(root, path);
         BUG_ON(ins->objectid < search_start);
         if (ins->objectid >= btrfs_super_total_blocks(info->disk_super)) {
-                if (search_start == 0)
+                if (full_scan)
                         return -ENOSPC;
-                search_start = 0;
-                goto check_failed;
+                search_start = orig_search_start;
+                full_scan = 1;
+                goto new_group;
         }
         for (test_block = ins->objectid;
              test_block < ins->objectid + num_blocks; test_block++) {
                 if (test_radix_bit(&info->pinned_radix, test_block)) {
                         search_start = test_block + 1;
-                        goto check_failed;
+                        goto new_group;
                 }
         }
         if (!fill_prealloc && info->extent_tree_insert_nr) {
@@ -670,7 +799,7 @@ check_pending:
                     ins->objectid <= last) {
                         search_start = last + 1;
                         WARN_ON(1);
-                        goto check_failed;
+                        goto new_group;
                 }
         }
         if (!fill_prealloc && info->extent_tree_prealloc_nr) {
@@ -680,7 +809,7 @@ check_pending:
                     ins->objectid <= info->extent_tree_prealloc[0]) {
                         search_start = info->extent_tree_prealloc[0] + 1;
                         WARN_ON(1);
-                        goto check_failed;
+                        goto new_group;
                 }
         }
         if (fill_prealloc) {
@@ -696,14 +825,12 @@ check_pending:
                 }
                 if (total_found < total_needed) {
                         search_start = test_block;
-                        goto check_failed;
+                        goto new_group;
                 }
                 info->extent_tree_prealloc_nr = total_found;
         }
-        ret = radix_tree_gang_lookup(&info->block_group_radix,
-                                     (void **)&block_group,
-                                     ins->objectid, 1);
-        if (ret) {
+        block_group = lookup_block_group(info, ins->objectid);
+        if (block_group) {
                 block_group->last_alloc = ins->objectid;
                 if (!data)
                         trans->block_group = block_group;
@@ -711,6 +838,18 @@ check_pending:
         ins->offset = num_blocks;
         btrfs_free_path(path);
         return 0;
+
+new_group:
+        if (search_start >= btrfs_super_total_blocks(info->disk_super)) {
+                search_start = orig_search_start;
+                full_scan = 1;
+        }
+        block_group = lookup_block_group(info, search_start);
+        if (!full_scan)
+                block_group = btrfs_find_block_group(root, block_group,
+                                                     search_start, data);
+        goto check_failed;
+
 error:
         btrfs_release_path(root, path);
         btrfs_free_path(path);
@@ -794,7 +933,7 @@ struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
         struct buffer_head *buf;
 
         ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
-                                 1, 0, (unsigned long)-1, &ins, 0);
+                                 1, hint, (unsigned long)-1, &ins, 0);
         if (ret) {
                 BUG();
                 return NULL;
@@ -984,21 +1123,19 @@ int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
         return ret;
 }
 
-int btrfs_free_block_groups(struct btrfs_fs_info *info)
+static int free_block_group_radix(struct radix_tree_root *radix)
 {
         int ret;
         struct btrfs_block_group_cache *cache[8];
         int i;
 
         while(1) {
-                ret = radix_tree_gang_lookup(&info->block_group_radix,
-                                             (void **)cache, 0,
+                ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
                                              ARRAY_SIZE(cache));
                 if (!ret)
                         break;
                 for (i = 0; i < ret; i++) {
-                        radix_tree_delete(&info->block_group_radix,
-                                          cache[i]->key.objectid +
+                        radix_tree_delete(radix, cache[i]->key.objectid +
                                           cache[i]->key.offset - 1);
                         kfree(cache[i]);
                 }
@@ -1006,6 +1143,20 @@ int btrfs_free_block_groups(struct btrfs_fs_info *info)
         return 0;
 }
 
+int btrfs_free_block_groups(struct btrfs_fs_info *info)
+{
+        int ret;
+        int ret2;
+
+        ret = free_block_group_radix(&info->block_group_radix);
+        ret2 = free_block_group_radix(&info->block_group_data_radix);
+        if (ret)
+                return ret;
+        if (ret2)
+                return ret2;
+        return 0;
+}
+
 int btrfs_read_block_groups(struct btrfs_root *root)
 {
         struct btrfs_path *path;
@@ -1013,13 +1164,16 @@ int btrfs_read_block_groups(struct btrfs_root *root)
         int err = 0;
         struct btrfs_block_group_item *bi;
         struct btrfs_block_group_cache *cache;
+        struct btrfs_fs_info *info = root->fs_info;
+        struct radix_tree_root *radix;
         struct btrfs_key key;
         struct btrfs_key found_key;
         struct btrfs_leaf *leaf;
         u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
         u64 used;
+        u64 nr = 0;
 
-        root = root->fs_info->extent_root;
+        root = info->extent_root;
         key.objectid = 0;
         key.offset = group_size_blocks;
         key.flags = 0;
@@ -1030,7 +1184,7 @@ int btrfs_read_block_groups(struct btrfs_root *root)
                 return -ENOMEM;
 
         while(1) {
-                ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
+                ret = btrfs_search_slot(NULL, info->extent_root,
                                         &key, path, 0, 0);
                 if (ret != 0) {
                         err = ret;
@@ -1050,23 +1204,28 @@ int btrfs_read_block_groups(struct btrfs_root *root)
                 memcpy(&cache->key, &found_key, sizeof(found_key));
                 cache->last_alloc = cache->key.objectid;
                 cache->first_free = cache->key.objectid;
+                cache->pinned = 0;
+                cache->data = (nr & 1);
                 key.objectid = found_key.objectid + found_key.offset;
                 btrfs_release_path(root, path);
-                ret = radix_tree_insert(&root->fs_info->block_group_radix,
-                                        found_key.objectid +
+                if (nr & 1)
+                        radix = &info->block_group_data_radix;
+                else
+                        radix = &info->block_group_radix;
+                ret = radix_tree_insert(radix, found_key.objectid +
                                         found_key.offset - 1,
                                         (void *)cache);
                 BUG_ON(ret);
                 used = btrfs_block_group_used(bi);
-                if (used < (key.offset * 2) / 3) {
-                        radix_tree_tag_set(&root->fs_info->block_group_radix,
-                                           found_key.objectid +
+                if (used < (key.offset * 8) / 10) {
+                        radix_tree_tag_set(radix, found_key.objectid +
                                            found_key.offset - 1,
                                            BTRFS_BLOCK_GROUP_AVAIL);
                 }
                 if (key.objectid >=
-                    btrfs_super_total_blocks(root->fs_info->disk_super))
+                    btrfs_super_total_blocks(info->disk_super))
                         break;
+                nr++;
         }
 
         btrfs_free_path(path);