1 files changed, 98 insertions, 40 deletions
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 62051a36664a..8b8cbe25fffb 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -12,42 +12,57 @@ 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 int find_search_start(struct btrfs_root *root, int data)
+struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
+                                                 struct btrfs_block_group_cache
+                                                 *hint, 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;
        u64 used;
-        u64 last;
+        u64 last = 0;
+        u64 hint_last;
        int i;
        int ret;
+        int full_search = 0;
-        cache[0] = info->block_group_cache;
+        if (hint) {
-        if (!cache[0])
+                used = btrfs_block_group_used(&hint->item);
-                goto find_new;
+                if (used < (hint->key.offset * 2) / 3) {
-        used = btrfs_block_group_used(&cache[0]->item);
+                        return hint;
-        if (used < (cache[0]->key.offset * 3 / 2))
+                }
-                return 0;
+                radix_tree_tag_clear(&info->block_group_radix,
-find_new:
+                                     hint->key.objectid + hint->key.offset - 1,
-        last = 0;
+                                     BTRFS_BLOCK_GROUP_AVAIL);
+                last = hint->key.objectid + hint->key.offset;
+                hint_last = last;
+        } else {
+                hint_last = 0;
+                last = 0;
+        }
        while(1) {
                ret = radix_tree_gang_lookup_tag(&info->block_group_radix,
                                                 (void **)cache,
                                                 last, ARRAY_SIZE(cache),
-                                                 BTRFS_BLOCK_GROUP_DIRTY);
+                                                 BTRFS_BLOCK_GROUP_AVAIL);
                if (!ret)
                        break;
                for (i = 0; i < ret; i++) {
                        used = btrfs_block_group_used(&cache[i]->item);
-                        if (used < (cache[i]->key.offset * 3 / 2)) {
+                        if (used < (cache[i]->key.offset * 2) / 3) {
                                info->block_group_cache = cache[i];
-                                cache[i]->last_alloc = cache[i]->first_free;
+                                found_group = cache[i];
-                                return 0;
+                                goto found;
                        }
+                        radix_tree_tag_clear(&info->block_group_radix,
+                                           cache[i]->key.objectid +
+                                           cache[i]->key.offset - 1,
+                                           BTRFS_BLOCK_GROUP_AVAIL);
                        last = cache[i]->key.objectid +
-                                cache[i]->key.offset - 1;
+                                cache[i]->key.offset;
                }
        }
-        last = 0;
+        last = hint_last;
+again:
        while(1) {
                ret = radix_tree_gang_lookup(&info->block_group_radix,
                                                 (void **)cache,
@@ -56,17 +71,32 @@ find_new:
                        break;
                for (i = 0; i < ret; i++) {
                        used = btrfs_block_group_used(&cache[i]->item);
-                        if (used < (cache[i]->key.offset * 3 / 2)) {
+                        if (used < cache[i]->key.offset) {
                                info->block_group_cache = cache[i];
-                                cache[i]->last_alloc = cache[i]->first_free;
+                                found_group = cache[i];
-                                return 0;
+                                goto found;
                        }
+                        radix_tree_tag_clear(&info->block_group_radix,
+                                           cache[i]->key.objectid +
+                                           cache[i]->key.offset - 1,
+                                           BTRFS_BLOCK_GROUP_AVAIL);
                        last = cache[i]->key.objectid +
-                                cache[i]->key.offset - 1;
+                                cache[i]->key.offset;
                }
        }
        info->block_group_cache = NULL;
-        return 0;
+        if (!full_search) {
+                last = 0;
+                full_search = 1;
+                goto again;
+        }
+found:
+        if (!found_group) {
+                ret = radix_tree_gang_lookup(&info->block_group_radix,
+                                             (void **)&found_group, 0, 1);
+                BUG_ON(ret != 1);
+        }
+        return found_group;
 }
 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
@@ -243,6 +273,7 @@ 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);
@@ -322,10 +353,6 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
                                                    btree_inode->i_blkbits));
                }
        }
-        if (root->fs_info->block_group_cache) {
-                root->fs_info->block_group_cache->last_alloc =
-                        root->fs_info->block_group_cache->first_free;
-        }
        return 0;
 }
@@ -532,22 +559,43 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
        int total_found = 0;
        int fill_prealloc = 0;
        int level;
+        int update_block_group = 0;
+        struct btrfs_block_group_cache *hint_block_group;
        path = btrfs_alloc_path();
        ins->flags = 0;
        btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
        level = btrfs_header_level(btrfs_buffer_header(root->node));
+        /* find search start here */
+        if (0 && search_start && num_blocks) {
+                u64 used;
+                ret = radix_tree_gang_lookup(&info->block_group_radix,
+                                             (void **)&hint_block_group,
+                                             search_start, 1);
+                if (ret) {
+                        used = btrfs_block_group_used(&hint_block_group->item);
+                        if (used > (hint_block_group->key.offset * 9) / 10)
+                                search_start = 0;
+                        else if (search_start < hint_block_group->last_alloc)
+                                search_start = hint_block_group->last_alloc;
+                } else {
+                        search_start = 0;
+                }
+        }
        if (num_blocks == 0) {
                fill_prealloc = 1;
                num_blocks = 1;
                total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
        }
-        find_search_start(root, 0);
+        if (1 || !search_start) {
-        if (info->block_group_cache &&
+                trans->block_group = btrfs_find_block_group(root,
-            info->block_group_cache->last_alloc > search_start)
+                                                            trans->block_group,
-                search_start = info->block_group_cache->last_alloc;
+                                                            0);
+                if (trans->block_group->last_alloc > search_start)
+                        search_start = trans->block_group->last_alloc;
+                update_block_group = 1;
+        }
 check_failed:
        btrfs_init_path(path);
        ins->objectid = search_start;
@@ -662,11 +710,13 @@ check_pending:
                }
                info->extent_tree_prealloc_nr = total_found;
        }
-        ret = radix_tree_gang_lookup(&info->block_group_radix,
+        if (update_block_group) {
-                                     (void **)&info->block_group_cache,
+                ret = radix_tree_gang_lookup(&info->block_group_radix,
-                                     ins->objectid, 1);
+                                             (void **)&trans->block_group,
-        if (ret) {
+                                             ins->objectid, 1);
-                info->block_group_cache->last_alloc = ins->objectid;
+                if (ret) {
+                        trans->block_group->last_alloc = ins->objectid;
+                }
        }
        ins->offset = num_blocks;
        btrfs_free_path(path);
@@ -747,14 +797,14 @@ int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
 * returns the tree buffer or NULL.
 */
 struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
-                                           struct btrfs_root *root)
+                                           struct btrfs_root *root, u64 hint)
 {
        struct btrfs_key ins;
        int ret;
        struct buffer_head *buf;
        ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
-                                 1, 0, (unsigned long)-1, &ins);
+                                 1, hint, (unsigned long)-1, &ins);
        if (ret) {
                BUG();
                return NULL;
@@ -975,6 +1025,7 @@ int btrfs_read_block_groups(struct btrfs_root *root)
        struct btrfs_key found_key;
        struct btrfs_leaf *leaf;
        u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
+        u64 used;
        root = root->fs_info->extent_root;
        key.objectid = 0;
@@ -1005,8 +1056,8 @@ int btrfs_read_block_groups(struct btrfs_root *root)
                                    struct btrfs_block_group_item);
                memcpy(&cache->item, bi, sizeof(*bi));
                memcpy(&cache->key, &found_key, sizeof(found_key));
-                cache->last_alloc = 0;
+                cache->last_alloc = cache->key.objectid;
-                cache->first_free = 0;
+                cache->first_free = cache->key.objectid;
                key.objectid = found_key.objectid + found_key.offset;
                btrfs_release_path(root, path);
                ret = radix_tree_insert(&root->fs_info->block_group_radix,
@@ -1014,6 +1065,13 @@ int btrfs_read_block_groups(struct btrfs_root *root)
                                        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 +
+                                           found_key.offset - 1,
+                                           BTRFS_BLOCK_GROUP_AVAIL);
+                }
                if (key.objectid >=
                    btrfs_super_total_blocks(root->fs_info->disk_super))
                        break;

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 62051a36664a..8b8cbe25fffb 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c
@@ -12,42 +12,57 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct
12	static int del_pending_extents(struct btrfs_trans_handle *trans, struct	12	static int del_pending_extents(struct btrfs_trans_handle *trans, struct
13	btrfs_root *extent_root);	13	btrfs_root *extent_root);
14		14
15	static int find_search_start(struct btrfs_root *root, int data)	15	struct btrfs_block_group_cache btrfs_find_block_group(struct btrfs_root root,
		16	struct btrfs_block_group_cache
		17	*hint, int data)
16	{	18	{
17	struct btrfs_block_group_cache *cache[8];	19	struct btrfs_block_group_cache *cache[8];
		20	struct btrfs_block_group_cache *found_group = NULL;
18	struct btrfs_fs_info *info = root->fs_info;	21	struct btrfs_fs_info *info = root->fs_info;
19	u64 used;	22	u64 used;
20	u64 last;	23	u64 last = 0;
		24	u64 hint_last;
21	int i;	25	int i;
22	int ret;	26	int ret;
23		27	int full_search = 0;
24	cache[0] = info->block_group_cache;	28	if (hint) {
25	if (!cache[0])	29	used = btrfs_block_group_used(&hint->item);
26	goto find_new;	30	if (used < (hint->key.offset * 2) / 3) {
27	used = btrfs_block_group_used(&cache[0]->item);	31	return hint;
28	if (used < (cache[0]->key.offset * 3 / 2))	32	}
29	return 0;	33	radix_tree_tag_clear(&info->block_group_radix,
30	find_new:	34	hint->key.objectid + hint->key.offset - 1,
31	last = 0;	35	BTRFS_BLOCK_GROUP_AVAIL);
		36	last = hint->key.objectid + hint->key.offset;
		37	hint_last = last;
		38	} else {
		39	hint_last = 0;
		40	last = 0;
		41	}
32	while(1) {	42	while(1) {
33	ret = radix_tree_gang_lookup_tag(&info->block_group_radix,	43	ret = radix_tree_gang_lookup_tag(&info->block_group_radix,
34	(void **)cache,	44	(void **)cache,
35	last, ARRAY_SIZE(cache),	45	last, ARRAY_SIZE(cache),
36	BTRFS_BLOCK_GROUP_DIRTY);	46	BTRFS_BLOCK_GROUP_AVAIL);
37	if (!ret)	47	if (!ret)
38	break;	48	break;
39	for (i = 0; i < ret; i++) {	49	for (i = 0; i < ret; i++) {
40	used = btrfs_block_group_used(&cache[i]->item);	50	used = btrfs_block_group_used(&cache[i]->item);
41	if (used < (cache[i]->key.offset * 3 / 2)) {	51	if (used < (cache[i]->key.offset * 2) / 3) {
42	info->block_group_cache = cache[i];	52	info->block_group_cache = cache[i];
43	cache[i]->last_alloc = cache[i]->first_free;	53	found_group = cache[i];
44	return 0;	54	goto found;
45	}	55	}
		56	radix_tree_tag_clear(&info->block_group_radix,
		57	cache[i]->key.objectid +
		58	cache[i]->key.offset - 1,
		59	BTRFS_BLOCK_GROUP_AVAIL);
46	last = cache[i]->key.objectid +	60	last = cache[i]->key.objectid +
47	cache[i]->key.offset - 1;	61	cache[i]->key.offset;
48	}	62	}
49	}	63	}
50	last = 0;	64	last = hint_last;
		65	again:
51	while(1) {	66	while(1) {
52	ret = radix_tree_gang_lookup(&info->block_group_radix,	67	ret = radix_tree_gang_lookup(&info->block_group_radix,
53	(void **)cache,	68	(void **)cache,
@@ -56,17 +71,32 @@ find_new:
56	break;	71	break;
57	for (i = 0; i < ret; i++) {	72	for (i = 0; i < ret; i++) {
58	used = btrfs_block_group_used(&cache[i]->item);	73	used = btrfs_block_group_used(&cache[i]->item);
59	if (used < (cache[i]->key.offset * 3 / 2)) {	74	if (used < cache[i]->key.offset) {
60	info->block_group_cache = cache[i];	75	info->block_group_cache = cache[i];
61	cache[i]->last_alloc = cache[i]->first_free;	76	found_group = cache[i];
62	return 0;	77	goto found;
63	}	78	}
		79	radix_tree_tag_clear(&info->block_group_radix,
		80	cache[i]->key.objectid +
		81	cache[i]->key.offset - 1,
		82	BTRFS_BLOCK_GROUP_AVAIL);
64	last = cache[i]->key.objectid +	83	last = cache[i]->key.objectid +
65	cache[i]->key.offset - 1;	84	cache[i]->key.offset;
66	}	85	}
67	}	86	}
68	info->block_group_cache = NULL;	87	info->block_group_cache = NULL;
69	return 0;	88	if (!full_search) {
		89	last = 0;
		90	full_search = 1;
		91	goto again;
		92	}
		93	found:
		94	if (!found_group) {
		95	ret = radix_tree_gang_lookup(&info->block_group_radix,
		96	(void **)&found_group, 0, 1);
		97	BUG_ON(ret != 1);
		98	}
		99	return found_group;
70	}	100	}
71		101
72	int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,	102	int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
@@ -243,6 +273,7 @@ int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
243	path, cache[i]);	273	path, cache[i]);
244	if (err)	274	if (err)
245	werr = err;	275	werr = err;
		276	cache[i]->last_alloc = cache[i]->first_free;
246	}	277	}
247	}	278	}
248	btrfs_free_path(path);	279	btrfs_free_path(path);
@@ -322,10 +353,6 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
322	btree_inode->i_blkbits));	353	btree_inode->i_blkbits));
323	}	354	}
324	}	355	}
325	if (root->fs_info->block_group_cache) {
326	root->fs_info->block_group_cache->last_alloc =
327	root->fs_info->block_group_cache->first_free;
328	}
329	return 0;	356	return 0;
330	}	357	}
331		358
@@ -532,22 +559,43 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
532	int total_found = 0;	559	int total_found = 0;
533	int fill_prealloc = 0;	560	int fill_prealloc = 0;
534	int level;	561	int level;
		562	int update_block_group = 0;
		563	struct btrfs_block_group_cache *hint_block_group;
535		564
536	path = btrfs_alloc_path();	565	path = btrfs_alloc_path();
537	ins->flags = 0;	566	ins->flags = 0;
538	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);	567	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
539		568
540	level = btrfs_header_level(btrfs_buffer_header(root->node));	569	level = btrfs_header_level(btrfs_buffer_header(root->node));
		570	/* find search start here */
		571	if (0 && search_start && num_blocks) {
		572	u64 used;
		573	ret = radix_tree_gang_lookup(&info->block_group_radix,
		574	(void **)&hint_block_group,
		575	search_start, 1);
		576	if (ret) {
		577	used = btrfs_block_group_used(&hint_block_group->item);
		578	if (used > (hint_block_group->key.offset * 9) / 10)
		579	search_start = 0;
		580	else if (search_start < hint_block_group->last_alloc)
		581	search_start = hint_block_group->last_alloc;
		582	} else {
		583	search_start = 0;
		584	}
		585	}
541	if (num_blocks == 0) {	586	if (num_blocks == 0) {
542	fill_prealloc = 1;	587	fill_prealloc = 1;
543	num_blocks = 1;	588	num_blocks = 1;
544	total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;	589	total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3;
545	}	590	}
546	find_search_start(root, 0);	591	if (1 \|\| !search_start) {
547	if (info->block_group_cache &&	592	trans->block_group = btrfs_find_block_group(root,
548	info->block_group_cache->last_alloc > search_start)	593	trans->block_group,
549	search_start = info->block_group_cache->last_alloc;	594	0);
550		595	if (trans->block_group->last_alloc > search_start)
		596	search_start = trans->block_group->last_alloc;
		597	update_block_group = 1;
		598	}
551	check_failed:	599	check_failed:
552	btrfs_init_path(path);	600	btrfs_init_path(path);
553	ins->objectid = search_start;	601	ins->objectid = search_start;
@@ -662,11 +710,13 @@ check_pending:
662	}	710	}
663	info->extent_tree_prealloc_nr = total_found;	711	info->extent_tree_prealloc_nr = total_found;
664	}	712	}
665	ret = radix_tree_gang_lookup(&info->block_group_radix,	713	if (update_block_group) {
666	(void **)&info->block_group_cache,	714	ret = radix_tree_gang_lookup(&info->block_group_radix,
667	ins->objectid, 1);	715	(void **)&trans->block_group,
668	if (ret) {	716	ins->objectid, 1);
669	info->block_group_cache->last_alloc = ins->objectid;	717	if (ret) {
		718	trans->block_group->last_alloc = ins->objectid;
		719	}
670	}	720	}
671	ins->offset = num_blocks;	721	ins->offset = num_blocks;
672	btrfs_free_path(path);	722	btrfs_free_path(path);
@@ -747,14 +797,14 @@ int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
747	* returns the tree buffer or NULL.	797	* returns the tree buffer or NULL.
748	*/	798	*/
749	struct buffer_head btrfs_alloc_free_block(struct btrfs_trans_handle trans,	799	struct buffer_head btrfs_alloc_free_block(struct btrfs_trans_handle trans,
750	struct btrfs_root *root)	800	struct btrfs_root *root, u64 hint)
751	{	801	{
752	struct btrfs_key ins;	802	struct btrfs_key ins;
753	int ret;	803	int ret;
754	struct buffer_head *buf;	804	struct buffer_head *buf;
755		805
756	ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,	806	ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
757	1, 0, (unsigned long)-1, &ins);	807	1, hint, (unsigned long)-1, &ins);
758	if (ret) {	808	if (ret) {
759	BUG();	809	BUG();
760	return NULL;	810	return NULL;
@@ -975,6 +1025,7 @@ int btrfs_read_block_groups(struct btrfs_root *root)
975	struct btrfs_key found_key;	1025	struct btrfs_key found_key;
976	struct btrfs_leaf *leaf;	1026	struct btrfs_leaf *leaf;
977	u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;	1027	u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize;
		1028	u64 used;
978		1029
979	root = root->fs_info->extent_root;	1030	root = root->fs_info->extent_root;
980	key.objectid = 0;	1031	key.objectid = 0;
@@ -1005,8 +1056,8 @@ int btrfs_read_block_groups(struct btrfs_root *root)
1005	struct btrfs_block_group_item);	1056	struct btrfs_block_group_item);
1006	memcpy(&cache->item, bi, sizeof(*bi));	1057	memcpy(&cache->item, bi, sizeof(*bi));
1007	memcpy(&cache->key, &found_key, sizeof(found_key));	1058	memcpy(&cache->key, &found_key, sizeof(found_key));
1008	cache->last_alloc = 0;	1059	cache->last_alloc = cache->key.objectid;
1009	cache->first_free = 0;	1060	cache->first_free = cache->key.objectid;
1010	key.objectid = found_key.objectid + found_key.offset;	1061	key.objectid = found_key.objectid + found_key.offset;
1011	btrfs_release_path(root, path);	1062	btrfs_release_path(root, path);
1012	ret = radix_tree_insert(&root->fs_info->block_group_radix,	1063	ret = radix_tree_insert(&root->fs_info->block_group_radix,
@@ -1014,6 +1065,13 @@ int btrfs_read_block_groups(struct btrfs_root *root)
1014	found_key.offset - 1,	1065	found_key.offset - 1,
1015	(void *)cache);	1066	(void *)cache);
1016	BUG_ON(ret);	1067	BUG_ON(ret);
		1068	used = btrfs_block_group_used(bi);
		1069	if (used < (key.offset * 2) / 3) {
		1070	radix_tree_tag_set(&root->fs_info->block_group_radix,
		1071	found_key.objectid +
		1072	found_key.offset - 1,
		1073	BTRFS_BLOCK_GROUP_AVAIL);
		1074	}
1017	if (key.objectid >=	1075	if (key.objectid >=
1018	btrfs_super_total_blocks(root->fs_info->disk_super))	1076	btrfs_super_total_blocks(root->fs_info->disk_super))
1019	break;	1077	break;