On Fri, Oct 10, 2008 at 01:55:44PM -0400, Josef Bacik wrote:
> Hello,
>
> So there is an odd case where we can possibly return -ENOSPC when there is in
> fact space to be had. I think I finally have a hold on what the problem is, it
> only happens with Metadata writes, and happens _very_ infrequently. What has to
> happen is we have to allocate have allocated out of the first logical byte on
> the disk, which would set last_alloc to first_logical_byte(root, 0), so
> search_start == orig_search_start. We then need to allocate for normal
> metadata, so BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DUP. We will do a
> block lookup for the given search_start, block_group_bits() won't match and
> we'll go to choose another block group. However because search_start matches
> orig_search_start we go to see if we can allocate a chunk. If we are in the
> situation that we cannot allocate a chunk, we fail and ENOSPC. This is kind of
> a big flaw of the way find_free_extent works, as it along with find_free_space
> loop through _all_ of the block groups, not just the ones that we want to
> allocate out of. This patch completely kills find_free_space and rolls it into
> find_free_extent. I've introduced a sort of state machine into this, which will
> make it easier to get cache miss information out of the allocator, and will work
> well with my locking changes.
>
> The basic flow is this. We have the variable loop which is 0, meaning we are in
> the hint phase. We lookup the block group for the hint, and lookup the
> space_info for what we want to allocate out of. If the block group we were
> pointed at by the hint either isn't of the correct type, or just doesn't have
> the space we need, we set head to space_info->block_groups, so we start at the
> beginning of the block groups for this particular space info, and loop through.
> This is also where we add the empty_cluster to total_needed. At this point loop
> is set to 1 and we just loop through all of the block groups for this particular
> space_info looking for the space we need, just as find_free_space would have
> done, except we only hit the block groups we want and not _all_ of the block
> groups. If we come full circle we see if we can allocate a chunk. If we cannot
> of course we exit with -ENOSPC and we are good. If not we start over at
> space_info->block_groups and loop through again, with loop == 2. If we come
> full circle and haven't found what we need then we exit with -ENOSPC. I've been
> running this for a couple of days now and it seems stable, and I haven't yet hit
> a -ENOSPC when there was plenty of space left.
>
> Also I've made a groups_sem to handle the group list for the space_info. This
> is part of my locking changes, but is relatively safe and seems better than
> holding the space_info spinlock over that entire search time. Thanks,
>
> Signed-off-by: Josef Bacik <jbacik@xxxxxxxxxx>
>
>
Hello,
Had a slight bug that blows everything up if you ever have to start looping
through the space info's block groups. Not entirely sure why I didn't hit this
before. Here is the corrected patch below, thank you,
Josef
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 8559f39..fad58b9 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -508,6 +508,7 @@ struct btrfs_space_info {
/* for block groups in our same type */
struct list_head block_groups;
spinlock_t lock;
+ struct rw_semaphore groups_sem;
};
struct btrfs_free_space {
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 280ac1a..5f235fc 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -317,59 +317,6 @@ struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
return cache;
}
-static int noinline find_free_space(struct btrfs_root *root,
- struct btrfs_block_group_cache **cache_ret,
- u64 *start_ret, u64 num, int data)
-{
- int ret;
- struct btrfs_block_group_cache *cache = *cache_ret;
- struct btrfs_free_space *info = NULL;
- u64 last;
- u64 search_start = *start_ret;
-
- WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
- if (!cache)
- goto out;
-
- last = max(search_start, cache->key.objectid);
-
-again:
- ret = cache_block_group(root, cache);
- if (ret)
- goto out;
-
- if (cache->ro || !block_group_bits(cache, data))
- goto new_group;
-
- info = btrfs_find_free_space(cache, last, num);
- if (info) {
- *start_ret = info->offset;
- return 0;
- }
-
-new_group:
- last = cache->key.objectid + cache->key.offset;
-
- cache = btrfs_lookup_first_block_group(root->fs_info, last);
- if (!cache)
- goto out;
-
- *cache_ret = cache;
- goto again;
-
-out:
- return -ENOSPC;
-}
-
-static u64 div_factor(u64 num, int factor)
-{
- if (factor == 10)
- return num;
- num *= factor;
- do_div(num, 10);
- return num;
-}
-
static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
u64 flags)
{
@@ -384,6 +331,15 @@ static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
return NULL;
}
+static u64 div_factor(u64 num, int factor)
+{
+ if (factor == 10)
+ return num;
+ num *= factor;
+ do_div(num, 10);
+ return num;
+}
+
static struct btrfs_block_group_cache *
__btrfs_find_block_group(struct btrfs_root *root,
struct btrfs_block_group_cache *hint,
@@ -1446,6 +1402,7 @@ static int update_space_info(struct btrfs_fs_info *info, u64 flags,
list_add(&found->list, &info->space_info);
INIT_LIST_HEAD(&found->block_groups);
+ init_rwsem(&found->groups_sem);
spin_lock_init(&found->lock);
found->flags = flags;
found->total_bytes = total_bytes;
@@ -2208,19 +2165,22 @@ static int noinline find_free_extent(struct btrfs_trans_handle *trans,
u64 exclude_start, u64 exclude_nr,
int data)
{
- int ret;
- u64 orig_search_start;
+ int ret = 0;
struct btrfs_root * root = orig_root->fs_info->extent_root;
- struct btrfs_fs_info *info = root->fs_info;
u64 total_needed = num_bytes;
u64 *last_ptr = NULL;
- struct btrfs_block_group_cache *block_group;
+ struct btrfs_block_group_cache *block_group = NULL;
int chunk_alloc_done = 0;
int empty_cluster = 2 * 1024 * 1024;
int allowed_chunk_alloc = 0;
+ struct list_head *head = NULL, *cur = NULL;
+ int loop = 0;
+ struct btrfs_space_info *space_info;
WARN_ON(num_bytes < root->sectorsize);
btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
+ ins->objectid = 0;
+ ins->offset = 0;
if (orig_root->ref_cows || empty_size)
allowed_chunk_alloc = 1;
@@ -2239,152 +2199,132 @@ static int noinline find_free_extent(struct btrfs_trans_handle *trans,
else
empty_size += empty_cluster;
}
-
search_start = max(search_start, first_logical_byte(root, 0));
- orig_search_start = search_start;
-
search_start = max(search_start, hint_byte);
total_needed += empty_size;
-new_group:
- block_group = btrfs_lookup_block_group(info, search_start);
- if (!block_group)
- block_group = btrfs_lookup_first_block_group(info,
- search_start);
+ block_group = btrfs_lookup_block_group(root->fs_info, search_start);
+ space_info = __find_space_info(root->fs_info, data);
- /*
- * Ok this looks a little tricky, buts its really simple. First if we
- * didn't find a block group obviously we want to start over.
- * Secondly, if the block group we found does not match the type we
- * need, and we have a last_ptr and its not 0, chances are the last
- * allocation we made was at the end of the block group, so lets go
- * ahead and skip the looking through the rest of the block groups and
- * start at the beginning. This helps with metadata allocations,
- * since you are likely to have a bunch of data block groups to search
- * through first before you realize that you need to start over, so go
- * ahead and start over and save the time.
- */
- if (!block_group || (!block_group_bits(block_group, data) &&
- last_ptr && *last_ptr)) {
- if (search_start != orig_search_start) {
- if (last_ptr && *last_ptr) {
- total_needed += empty_cluster;
- *last_ptr = 0;
- }
- search_start = orig_search_start;
- goto new_group;
- } else if (!chunk_alloc_done && allowed_chunk_alloc) {
- ret = do_chunk_alloc(trans, root,
- num_bytes + 2 * 1024 * 1024,
- data, 1);
- if (ret < 0)
- goto error;
- BUG_ON(ret);
- chunk_alloc_done = 1;
- search_start = orig_search_start;
- goto new_group;
- } else {
- ret = -ENOSPC;
- goto error;
- }
- }
-
- /*
- * this is going to seach through all of the existing block groups it
- * can find, so if we don't find something we need to see if we can
- * allocate what we need.
- */
- ret = find_free_space(root, &block_group, &search_start,
- total_needed, data);
- if (ret == -ENOSPC) {
+ down_read(&space_info->groups_sem);
+ while (1) {
+ struct btrfs_free_space *free_space;
/*
- * instead of allocating, start at the original search start
- * and see if there is something to be found, if not then we
- * allocate
+ * the only way this happens if our hint points to a block
+ * group thats not of the proper type, while looping this
+ * should never happen
*/
- if (search_start != orig_search_start) {
- if (last_ptr && *last_ptr) {
- *last_ptr = 0;
- total_needed += empty_cluster;
- }
- search_start = orig_search_start;
+ if (unlikely(!block_group_bits(block_group, data)))
goto new_group;
- }
- /*
- * we've already allocated, we're pretty screwed
- */
- if (chunk_alloc_done) {
- goto error;
- } else if (!allowed_chunk_alloc && block_group &&
- block_group_bits(block_group, data)) {
- block_group->space_info->force_alloc = 1;
- goto error;
- } else if (!allowed_chunk_alloc) {
- goto error;
- }
+ ret = cache_block_group(root, block_group);
+ if (ret)
+ break;
- ret = do_chunk_alloc(trans, root, num_bytes + 2 * 1024 * 1024,
- data, 1);
- if (ret < 0)
- goto error;
+ if (block_group->ro)
+ goto new_group;
- BUG_ON(ret);
- chunk_alloc_done = 1;
- if (block_group)
- search_start = block_group->key.objectid +
+ free_space = btrfs_find_free_space(block_group, search_start,
+ total_needed);
+ if (free_space) {
+ u64 start = block_group->key.objectid;
+ u64 end = block_group->key.objectid +
block_group->key.offset;
- else
- search_start = orig_search_start;
- goto new_group;
- }
- if (ret)
- goto error;
+ search_start = stripe_align(root, free_space->offset);
- search_start = stripe_align(root, search_start);
- ins->objectid = search_start;
- ins->offset = num_bytes;
+ /* move on to the next group */
+ if (search_start + num_bytes >= search_end)
+ goto new_group;
- if (ins->objectid + num_bytes >= search_end) {
- search_start = orig_search_start;
- if (chunk_alloc_done) {
- ret = -ENOSPC;
- goto error;
+ /* move on to the next group */
+ if (search_start + num_bytes > end)
+ goto new_group;
+
+ if (exclude_nr > 0 &&
+ (search_start + num_bytes > exclude_start &&
+ search_start < exclude_start + exclude_nr)) {
+ search_start = exclude_start + exclude_nr;
+ /*
+ * if search_start is still in this block group
+ * then we just re-search this block group
+ */
+ if (search_start >= start &&
+ search_start < end)
+ continue;
+
+ /* else we go to the next block group */
+ goto new_group;
+ }
+
+ ins->objectid = search_start;
+ ins->offset = num_bytes;
+ /* we are all good, lets return */
+ break;
}
- goto new_group;
- }
+new_group:
+ /*
+ * Here's how this works.
+ * loop == 0: we were searching a block group via a hint
+ * and didn't find anything, so we start at
+ * the head of the block groups and keep searching
+ * loop == 1: we're searching through all of the block groups
+ * if we hit the head again we have searched
+ * all of the block groups for this space and we
+ * need to try and allocate, if we cant error out.
+ * loop == 2: we allocated more space and are looping through
+ * all of the block groups again.
+ */
+ if (loop == 0) {
+ head = &space_info->block_groups;
+ cur = head->next;
- if (ins->objectid + num_bytes >
- block_group->key.objectid + block_group->key.offset) {
- if (search_start == orig_search_start && chunk_alloc_done) {
- ret = -ENOSPC;
- goto error;
+ if (last_ptr && *last_ptr) {
+ total_needed += empty_cluster;
+ *last_ptr = 0;
+ }
+ loop++;
+ } else if (loop == 1 && cur == head) {
+ if (allowed_chunk_alloc && !chunk_alloc_done) {
+ up_read(&space_info->groups_sem);
+ ret = do_chunk_alloc(trans, root, num_bytes +
+ 2 * 1024 * 1024, data, 1);
+ if (ret < 0)
+ break;
+ down_read(&space_info->groups_sem);
+ loop++;
+ head = &space_info->block_groups;
+ cur = head->next;
+ chunk_alloc_done = 1;
+ } else if (!allowed_chunk_alloc) {
+ space_info->force_alloc = 1;
+ break;
+ } else {
+ break;
+ }
+ } else if (cur == head) {
+ break;
}
- search_start = block_group->key.objectid +
- block_group->key.offset;
- goto new_group;
- }
- if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
- ins->objectid < exclude_start + exclude_nr)) {
- search_start = exclude_start + exclude_nr;
- goto new_group;
+ block_group = list_entry(cur, struct btrfs_block_group_cache,
+ list);
+ search_start = block_group->key.objectid;
+ cur = cur->next;
}
- if (!(data & BTRFS_BLOCK_GROUP_DATA))
- trans->block_group = block_group;
+ /* we found what we needed */
+ if (ins->objectid) {
+ if (!(data & BTRFS_BLOCK_GROUP_DATA))
+ trans->block_group = block_group;
- ins->offset = num_bytes;
- if (last_ptr) {
- *last_ptr = ins->objectid + ins->offset;
- if (*last_ptr ==
- btrfs_super_total_bytes(&root->fs_info->super_copy))
- *last_ptr = 0;
+ if (last_ptr)
+ *last_ptr = ins->objectid + ins->offset;
+ ret = 0;
+ } else if (!ret) {
+ ret = -ENOSPC;
}
- ret = 0;
-error:
+ up_read(&space_info->groups_sem);
return ret;
}
@@ -2397,7 +2337,7 @@ static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
info->total_bytes - info->bytes_used - info->bytes_pinned -
info->bytes_reserved, (info->full) ? "" : "not ");
- spin_lock(&info->lock);
+ down_read(&info->groups_sem);
list_for_each(l, &info->block_groups) {
cache = list_entry(l, struct btrfs_block_group_cache, list);
spin_lock(&cache->lock);
@@ -2409,7 +2349,7 @@ static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
btrfs_dump_free_space(cache, bytes);
spin_unlock(&cache->lock);
}
- spin_unlock(&info->lock);
+ up_read(&info->groups_sem);
}
static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
@@ -5079,9 +5019,9 @@ int btrfs_free_block_groups(struct btrfs_fs_info *info)
rb_erase(&block_group->cache_node,
&info->block_group_cache_tree);
- spin_lock(&block_group->space_info->lock);
+ down_write(&block_group->space_info->groups_sem);
list_del(&block_group->list);
- spin_unlock(&block_group->space_info->lock);
+ up_write(&block_group->space_info->groups_sem);
kfree(block_group);
}
spin_unlock(&info->block_group_cache_lock);
@@ -5142,9 +5082,9 @@ int btrfs_read_block_groups(struct btrfs_root *root)
&space_info);
BUG_ON(ret);
cache->space_info = space_info;
- spin_lock(&space_info->lock);
- list_add(&cache->list, &space_info->block_groups);
- spin_unlock(&space_info->lock);
+ down_write(&space_info->groups_sem);
+ list_add_tail(&cache->list, &space_info->block_groups);
+ up_write(&space_info->groups_sem);
ret = btrfs_add_block_group_cache(root->fs_info, cache);
BUG_ON(ret);
@@ -5190,9 +5130,9 @@ int btrfs_make_block_group(struct btrfs_trans_handle *trans,
ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
&cache->space_info);
BUG_ON(ret);
- spin_lock(&cache->space_info->lock);
- list_add(&cache->list, &cache->space_info->block_groups);
- spin_unlock(&cache->space_info->lock);
+ down_write(&cache->space_info->groups_sem);
+ list_add_tail(&cache->list, &cache->space_info->block_groups);
+ up_write(&cache->space_info->groups_sem);
ret = btrfs_add_block_group_cache(root->fs_info, cache);
BUG_ON(ret);
@@ -5231,9 +5171,9 @@ int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
btrfs_remove_free_space_cache(block_group);
rb_erase(&block_group->cache_node,
&root->fs_info->block_group_cache_tree);
- spin_lock(&block_group->space_info->lock);
+ down_write(&block_group->space_info->groups_sem);
list_del(&block_group->list);
- spin_unlock(&block_group->space_info->lock);
+ up_write(&block_group->space_info->groups_sem);
/*
memset(shrink_block_group, 0, sizeof(*shrink_block_group));
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
