Btrfs: Stop using radix trees for the block group cache

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

1 files changed, 148 insertions, 214 deletions

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 74cfbee2ff33..4bc639565d1c 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -22,6 +22,10 @@
 #include "print-tree.h"
 #include "transaction.h"
 
+#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
+#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
+#define BLOCK_GROUP_DIRTY EXTENT_DIRTY
+
 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 				 btrfs_root *extent_root);
 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
@@ -127,25 +131,31 @@ struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 							 btrfs_fs_info *info,
 							 u64 blocknr)
 {
-	struct btrfs_block_group_cache *block_group;
+	struct extent_map_tree *block_group_cache;
+	struct btrfs_block_group_cache *block_group = NULL;
+	u64 ptr;
+	u64 start;
+	u64 end;
 	int ret;
 
-	ret = radix_tree_gang_lookup(&info->block_group_radix,
-				     (void **)&block_group,
-				     blocknr, 1);
+	block_group_cache = &info->block_group_cache;
+	ret = find_first_extent_bit(block_group_cache,
+				    blocknr, &start, &end,
+				    BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
 	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;
+		return NULL;
 	}
+	ret = get_state_private(block_group_cache, start, &ptr);
+	if (ret)
+		return NULL;
+
+	block_group = (struct btrfs_block_group_cache *)ptr;
+
+
+	if (block_group->key.objectid <= blocknr && blocknr <=
+	    block_group->key.objectid + block_group->key.offset)
+		return block_group;
+
 	return NULL;
 }
 
@@ -173,7 +183,7 @@ again:
 		last = end + 1;
 		if (end + 1 - start < num)
 			continue;
-		if (start + num > cache->key.objectid + cache->key.offset)
+		if (start + num >= cache->key.objectid + cache->key.offset)
 			goto new_group;
 		return start;
 	}
@@ -189,6 +199,7 @@ new_group:
 	cache = btrfs_find_block_group(root, cache,
 				       last + cache->key.offset - 1, data, 0);
 	*cache_ret = cache;
+	last = min(cache->key.objectid, last);
 	goto again;
 }
 
@@ -204,30 +215,32 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 						 *hint, u64 search_start,
 						 int data, int owner)
 {
-	struct btrfs_block_group_cache *cache[8];
+	struct btrfs_block_group_cache *cache;
+	struct extent_map_tree *block_group_cache;
 	struct btrfs_block_group_cache *found_group = NULL;
 	struct btrfs_fs_info *info = root->fs_info;
-	struct radix_tree_root *radix;
-	struct radix_tree_root *swap_radix;
 	u64 used;
 	u64 last = 0;
 	u64 hint_last;
-	int i;
+	u64 start;
+	u64 end;
+	u64 free_check;
+	u64 ptr;
+	int bit;
 	int ret;
 	int full_search = 0;
 	int factor = 8;
 	int data_swap = 0;
 
+	block_group_cache = &info->block_group_cache;
+
 	if (!owner)
 		factor = 5;
 
-	if (data) {
-		radix = &info->block_group_data_radix;
-		swap_radix = &info->block_group_radix;
-	} else {
-		radix = &info->block_group_radix;
-		swap_radix = &info->block_group_data_radix;
-	}
+	if (data)
+		bit = BLOCK_GROUP_DATA;
+	else
+		bit = BLOCK_GROUP_METADATA;
 
 	if (search_start) {
 		struct btrfs_block_group_cache *shint;
@@ -246,12 +259,6 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 		    div_factor(hint->key.offset, factor)) {
 			return hint;
 		}
-		if (used >= div_factor(hint->key.offset, 8)) {
-			radix_tree_tag_clear(radix,
-					     hint->key.objectid +
-					     hint->key.offset - 1,
-					     BTRFS_BLOCK_GROUP_AVAIL);
-		}
 		last = hint->key.offset * 3;
 		if (hint->key.objectid >= last)
 			last = max(search_start + hint->key.offset - 1,
@@ -267,51 +274,29 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 
 		last = hint_last;
 	}
-	while(1) {
-		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
-						 last, ARRAY_SIZE(cache),
-						 BTRFS_BLOCK_GROUP_AVAIL);
-		if (!ret)
-			break;
-		for (i = 0; i < ret; i++) {
-			last = cache[i]->key.objectid +
-				cache[i]->key.offset;
-			used = btrfs_block_group_used(&cache[i]->item);
-			if (used + cache[i]->pinned <
-			    div_factor(cache[i]->key.offset, factor)) {
-				found_group = cache[i];
-				goto found;
-			}
-			if (used >= div_factor(cache[i]->key.offset, 8)) {
-				radix_tree_tag_clear(radix,
-						     cache[i]->key.objectid +
-						     cache[i]->key.offset - 1,
-						     BTRFS_BLOCK_GROUP_AVAIL);
-			}
-		}
-		cond_resched();
-	}
-	last = hint_last;
 again:
 	while(1) {
-		ret = radix_tree_gang_lookup(radix, (void **)cache,
-					     last, ARRAY_SIZE(cache));
-		if (!ret)
+		ret = find_first_extent_bit(block_group_cache, last,
+					    &start, &end, bit);
+		if (ret)
 			break;
-		for (i = 0; i < ret; i++) {
-			last = cache[i]->key.objectid +
-				cache[i]->key.offset;
-			used = btrfs_block_group_used(&cache[i]->item);
-			if (used + cache[i]->pinned < cache[i]->key.offset) {
-				found_group = cache[i];
-				goto found;
-			}
-			if (used >= cache[i]->key.offset) {
-				radix_tree_tag_clear(radix,
-						     cache[i]->key.objectid +
-						     cache[i]->key.offset - 1,
-						     BTRFS_BLOCK_GROUP_AVAIL);
-			}
+
+		ret = get_state_private(block_group_cache, start, &ptr);
+		if (ret)
+			break;
+
+		cache = (struct btrfs_block_group_cache *)ptr;
+		last = cache->key.objectid + cache->key.offset;
+		used = btrfs_block_group_used(&cache->item);
+
+		if (full_search)
+			free_check = cache->key.offset;
+		else
+			free_check = div_factor(cache->key.offset, factor);
+
+		if (used + cache->pinned < free_check) {
+			found_group = cache;
+			goto found;
 		}
 		cond_resched();
 	}
@@ -321,23 +306,11 @@ again:
 		goto again;
 	}
 	if (!data_swap) {
-		struct radix_tree_root *tmp = radix;
 		data_swap = 1;
-		radix = swap_radix;
-		swap_radix = tmp;
+		bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
 		last = search_start;
 		goto again;
 	}
-	if (!found_group) {
-		ret = radix_tree_gang_lookup(radix,
-					     (void **)&found_group, 0, 1);
-		if (ret == 0) {
-			ret = radix_tree_gang_lookup(swap_radix,
-						     (void **)&found_group,
-						     0, 1);
-		}
-		BUG_ON(ret != 1);
-	}
 found:
 	return found_group;
 }
@@ -538,68 +511,55 @@ fail:
 
 }
 
-static int write_dirty_block_radix(struct btrfs_trans_handle *trans,
-				   struct btrfs_root *root,
-				   struct radix_tree_root *radix)
+int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
+				   struct btrfs_root *root)
 {
-	struct btrfs_block_group_cache *cache[8];
+	struct extent_map_tree *block_group_cache;
+	struct btrfs_block_group_cache *cache;
 	int ret;
 	int err = 0;
 	int werr = 0;
-	int i;
 	struct btrfs_path *path;
-	unsigned long off = 0;
+	u64 last = 0;
+	u64 start;
+	u64 end;
+	u64 ptr;
 
+	block_group_cache = &root->fs_info->block_group_cache;
 	path = btrfs_alloc_path();
 	if (!path)
 		return -ENOMEM;
 
 	while(1) {
-		ret = radix_tree_gang_lookup_tag(radix, (void **)cache,
-						 off, ARRAY_SIZE(cache),
-						 BTRFS_BLOCK_GROUP_DIRTY);
-		if (!ret)
+		ret = find_first_extent_bit(block_group_cache, last,
+					    &start, &end, BLOCK_GROUP_DIRTY);
+		if (ret)
 			break;
-		for (i = 0; i < ret; i++) {
-			err = write_one_cache_group(trans, root,
-						    path, cache[i]);
-			/*
-			 * if we fail to write the cache group, we want
-			 * to keep it marked dirty in hopes that a later
-			 * write will work
-			 */
-			if (err) {
-				werr = err;
-				off = cache[i]->key.objectid +
-					cache[i]->key.offset;
-				continue;
-			}
 
-			radix_tree_tag_clear(radix, cache[i]->key.objectid +
-					     cache[i]->key.offset - 1,
-					     BTRFS_BLOCK_GROUP_DIRTY);
+		last = end + 1;
+		ret = get_state_private(block_group_cache, start, &ptr);
+		if (ret)
+			break;
+
+		cache = (struct btrfs_block_group_cache *)ptr;
+		err = write_one_cache_group(trans, root,
+					    path, cache);
+		/*
+		 * if we fail to write the cache group, we want
+		 * to keep it marked dirty in hopes that a later
+		 * write will work
+		 */
+		if (err) {
+			werr = err;
+			continue;
 		}
+		clear_extent_bits(block_group_cache, start, end,
+				  BLOCK_GROUP_DIRTY, GFP_NOFS);
 	}
 	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, int mark_free,
@@ -610,7 +570,8 @@ static int update_block_group(struct btrfs_trans_handle *trans,
 	u64 total = num;
 	u64 old_val;
 	u64 block_in_group;
-	int ret;
+	u64 start;
+	u64 end;
 
 	while(total) {
 		cache = btrfs_lookup_block_group(info, blocknr);
@@ -619,9 +580,10 @@ static int update_block_group(struct btrfs_trans_handle *trans,
 		}
 		block_in_group = blocknr - cache->key.objectid;
 		WARN_ON(block_in_group > cache->key.offset);
-		radix_tree_tag_set(cache->radix, cache->key.objectid +
-				   cache->key.offset - 1,
-				   BTRFS_BLOCK_GROUP_DIRTY);
+		start = cache->key.objectid;
+		end = start + cache->key.offset - 1;
+		set_extent_bits(&info->block_group_cache, start, end,
+				BLOCK_GROUP_DIRTY, GFP_NOFS);
 
 		old_val = btrfs_block_group_used(&cache->item);
 		num = min(total, cache->key.offset - block_in_group);
@@ -630,25 +592,27 @@ static int update_block_group(struct btrfs_trans_handle *trans,
 				cache->last_alloc = blocknr;
 			if (cache->data != data &&
 			    old_val < (cache->key.offset >> 1)) {
-				cache->data = data;
-				radix_tree_delete(cache->radix,
-						  cache->key.objectid +
-						  cache->key.offset - 1);
+				int bit_to_clear;
+				int bit_to_set;
 
+				cache->data = data;
 				if (data) {
-					cache->radix =
-						&info->block_group_data_radix;
+					bit_to_clear = BLOCK_GROUP_DATA;
+					bit_to_set = BLOCK_GROUP_METADATA;
 					cache->item.flags |=
 						BTRFS_BLOCK_GROUP_DATA;
 				} else {
-					cache->radix = &info->block_group_radix;
+					bit_to_clear = BLOCK_GROUP_METADATA;
+					bit_to_set = BLOCK_GROUP_DATA;
 					cache->item.flags &=
 						~BTRFS_BLOCK_GROUP_DATA;
 				}
-				ret = radix_tree_insert(cache->radix,
-							cache->key.objectid +
-							cache->key.offset - 1,
-							(void *)cache);
+				clear_extent_bits(&info->block_group_cache,
+						  start, end, bit_to_clear,
+						  GFP_NOFS);
+				set_extent_bits(&info->block_group_cache,
+						start, end, bit_to_set,
+						GFP_NOFS);
 			}
 			old_val += num;
 		} else {
@@ -660,13 +624,6 @@ static int update_block_group(struct btrfs_trans_handle *trans,
 						 blocknr, blocknr + num - 1,
 						 GFP_NOFS);
 			}
-			if (old_val < (cache->key.offset >> 1) &&
-			    old_val + num >= (cache->key.offset >> 1)) {
-				radix_tree_tag_set(cache->radix,
-						   cache->key.objectid +
-						   cache->key.offset - 1,
-						   BTRFS_BLOCK_GROUP_AVAIL);
-			}
 		}
 		btrfs_set_block_group_used(&cache->item, old_val);
 		total -= num;
@@ -730,11 +687,8 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 				block_group->pinned--;
 				if (gang[i] < block_group->last_alloc)
 					block_group->last_alloc = gang[i];
-				if (!block_group->data) {
-					set_extent_dirty(free_space_cache,
-							 gang[i], gang[i],
-							 GFP_NOFS);
-				}
+				set_extent_dirty(free_space_cache,
+						 gang[i], gang[i], GFP_NOFS);
 			}
 		}
 	}
@@ -1059,8 +1013,8 @@ check_failed:
 			ins->offset = search_end - ins->objectid;
 			goto check_pending;
 		}
-
 		btrfs_item_key_to_cpu(l, &key, slot);
+
 		if (key.objectid >= search_start && key.objectid > last_block &&
 		    start_found) {
 			if (last_block < search_start)
@@ -1072,9 +1026,14 @@ check_failed:
 				goto check_pending;
 			}
 		}
-
-		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
+		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
+			if (!start_found) {
+				last_block = key.objectid;
+				start_found = 1;
+			}
 			goto next;
+		}
+
 
 		start_found = 1;
 		last_block = key.objectid + key.offset;
@@ -1120,9 +1079,6 @@ check_pending:
 	}
 	ins->offset = num_blocks;
 	btrfs_free_path(path);
-	if (0 && ins->objectid != cached_search_start) {
-printk("\tcached was %Lu found %Lu\n", cached_search_start, ins->objectid);
-	}
 	return 0;
 
 new_group:
@@ -1529,40 +1485,20 @@ out:
 	return ret;
 }
 
-static int free_block_group_radix(struct radix_tree_root *radix)
+int btrfs_free_block_groups(struct btrfs_fs_info *info)
 {
+	u64 start;
+	u64 end;
 	int ret;
-	struct btrfs_block_group_cache *cache[8];
-	int i;
 
 	while(1) {
-		ret = radix_tree_gang_lookup(radix, (void **)cache, 0,
-					     ARRAY_SIZE(cache));
-		if (!ret)
+		ret = find_first_extent_bit(&info->block_group_cache, 0,
+					    &start, &end, (unsigned int)-1);
+		if (ret)
 			break;
-		for (i = 0; i < ret; i++) {
-			radix_tree_delete(radix, cache[i]->key.objectid +
-					  cache[i]->key.offset - 1);
-			kfree(cache[i]);
-		}
+		clear_extent_bits(&info->block_group_cache, start,
+				  end, (unsigned int)-1, GFP_NOFS);
 	}
-	return 0;
-}
-
-int btrfs_free_block_groups(struct btrfs_fs_info *info)
-{
-	int ret;
-	int ret2;
-	u64 start;
-	u64 end;
-
-	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;
-
 	while(1) {
 		ret = find_first_extent_bit(&info->free_space_cache, 0,
 					    &start, &end, EXTENT_DIRTY);
@@ -1579,17 +1515,20 @@ int btrfs_read_block_groups(struct btrfs_root *root)
 	struct btrfs_path *path;
 	int ret;
 	int err = 0;
+	int bit;
 	struct btrfs_block_group_cache *cache;
 	struct btrfs_fs_info *info = root->fs_info;
-	struct radix_tree_root *radix;
+	struct extent_map_tree *block_group_cache;
 	struct btrfs_key key;
 	struct btrfs_key found_key;
 	struct extent_buffer *leaf;
 	u64 group_size_blocks;
-	u64 used;
+
+	block_group_cache = &info->block_group_cache;
 
 	group_size_blocks = BTRFS_BLOCK_GROUP_SIZE >>
-		root->fs_info->sb->s_blocksize_bits;
+		info->sb->s_blocksize_bits;
+
 	root = info->extent_root;
 	key.objectid = 0;
 	key.offset = group_size_blocks;
@@ -1617,35 +1556,30 @@ int btrfs_read_block_groups(struct btrfs_root *root)
 		read_extent_buffer(leaf, &cache->item,
 				   btrfs_item_ptr_offset(leaf, path->slots[0]),
 				   sizeof(cache->item));
-		if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
-			radix = &info->block_group_data_radix;
-			cache->data = 1;
-		} else {
-			radix = &info->block_group_radix;
-			cache->data = 0;
-		}
-
 		memcpy(&cache->key, &found_key, sizeof(found_key));
 		cache->last_alloc = cache->key.objectid;
 		cache->first_free = cache->key.objectid;
 		cache->pinned = 0;
 		cache->cached = 0;
 
-		cache->radix = radix;
-
 		key.objectid = found_key.objectid + found_key.offset;
 		btrfs_release_path(root, path);
 
-		ret = radix_tree_insert(radix, found_key.objectid +
-					found_key.offset - 1,
-					(void *)cache);
-		BUG_ON(ret);
-		used = btrfs_block_group_used(&cache->item);
-		if (used < div_factor(key.offset, 8)) {
-			radix_tree_tag_set(radix, found_key.objectid +
-					   found_key.offset - 1,
-					   BTRFS_BLOCK_GROUP_AVAIL);
+		if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
+			bit = BLOCK_GROUP_DATA;
+			cache->data = 1;
+		} else {
+			bit = BLOCK_GROUP_METADATA;
+			cache->data = 0;
 		}
+
+		/* use EXTENT_LOCKED to prevent merging */
+		set_extent_bits(block_group_cache, found_key.objectid,
+				found_key.objectid + found_key.offset - 1,
+				bit | EXTENT_LOCKED, GFP_NOFS);
+		set_state_private(block_group_cache, found_key.objectid,
+				  (u64)cache);
+
 		if (key.objectid >=
 		    btrfs_super_total_blocks(&info->super_copy))
 			break;