aboutsummaryrefslogtreecommitdiffstats
path: root/fs
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2008-02-18 12:12:38 -0500
committerChris Mason <chris.mason@oracle.com>2008-09-25 11:04:00 -0400
commitd7fc640e6fed46932f7c74e14f9b58b8637c66cf (patch)
tree525eda21f9e0d6d18bd55fd23d3a31814b224aa8 /fs
parent9afbb0b752ef30a429c45b9de6706e28ad1a36e1 (diff)
Btrfs: Allocator improvements
Reduce CPU time searching for free blocks by optimizing find_first_extent_bit Fix find_free_extent to make better use of the last_alloc hint. Before it was often finding blocks just before the hint. Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/btrfs/disk-io.c2
-rw-r--r--fs/btrfs/extent-tree.c34
-rw-r--r--fs/btrfs/extent_io.c38
-rw-r--r--fs/btrfs/extent_io.h11
4 files changed, 70 insertions, 15 deletions
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 6f0825b617d1..88e21bdbc478 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -951,7 +951,7 @@ void btrfs_throttle(struct btrfs_root *root)
951void btrfs_btree_balance_dirty(struct btrfs_root *root, unsigned long nr) 951void btrfs_btree_balance_dirty(struct btrfs_root *root, unsigned long nr)
952{ 952{
953 balance_dirty_pages_ratelimited_nr( 953 balance_dirty_pages_ratelimited_nr(
954 root->fs_info->btree_inode->i_mapping, 1); 954 root->fs_info->btree_inode->i_mapping, 1);
955} 955}
956 956
957void btrfs_set_buffer_defrag(struct extent_buffer *buf) 957void btrfs_set_buffer_defrag(struct extent_buffer *buf)
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index af5d4a085280..239e9d8669cb 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -188,9 +188,10 @@ static u64 noinline find_search_start(struct btrfs_root *root,
188{ 188{
189 int ret; 189 int ret;
190 struct btrfs_block_group_cache *cache = *cache_ret; 190 struct btrfs_block_group_cache *cache = *cache_ret;
191 struct extent_io_tree *free_space_cache;
192 struct extent_state *state;
191 u64 last; 193 u64 last;
192 u64 start = 0; 194 u64 start = 0;
193 u64 end = 0;
194 u64 cache_miss = 0; 195 u64 cache_miss = 0;
195 u64 total_fs_bytes; 196 u64 total_fs_bytes;
196 int wrapped = 0; 197 int wrapped = 0;
@@ -199,6 +200,8 @@ static u64 noinline find_search_start(struct btrfs_root *root,
199 goto out; 200 goto out;
200 } 201 }
201 total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy); 202 total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
203 free_space_cache = &root->fs_info->free_space_cache;
204
202again: 205again:
203 ret = cache_block_group(root, cache); 206 ret = cache_block_group(root, cache);
204 if (ret) 207 if (ret)
@@ -206,22 +209,27 @@ again:
206 209
207 last = max(search_start, cache->key.objectid); 210 last = max(search_start, cache->key.objectid);
208 211
212 spin_lock_irq(&free_space_cache->lock);
213 state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
209 while(1) { 214 while(1) {
210 ret = find_first_extent_bit(&root->fs_info->free_space_cache, 215 if (!state) {
211 last, &start, &end, EXTENT_DIRTY);
212 if (ret) {
213 if (!cache_miss) 216 if (!cache_miss)
214 cache_miss = last; 217 cache_miss = last;
218 spin_unlock_irq(&free_space_cache->lock);
215 goto new_group; 219 goto new_group;
216 } 220 }
217 221
218 start = max(last, start); 222 start = max(last, state->start);
219 last = end + 1; 223 last = state->end + 1;
220 if (last - start < num) { 224 if (last - start < num) {
221 if (last == cache->key.objectid + cache->key.offset) 225 if (last == cache->key.objectid + cache->key.offset)
222 cache_miss = start; 226 cache_miss = start;
227 do {
228 state = extent_state_next(state);
229 } while(state && !(state->state & EXTENT_DIRTY));
223 continue; 230 continue;
224 } 231 }
232 spin_unlock_irq(&free_space_cache->lock);
225 if (data != BTRFS_BLOCK_GROUP_MIXED && 233 if (data != BTRFS_BLOCK_GROUP_MIXED &&
226 start + num > cache->key.objectid + cache->key.offset) 234 start + num > cache->key.objectid + cache->key.offset)
227 goto new_group; 235 goto new_group;
@@ -1420,6 +1428,7 @@ static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1420 struct btrfs_block_group_cache *block_group; 1428 struct btrfs_block_group_cache *block_group;
1421 int full_scan = 0; 1429 int full_scan = 0;
1422 int wrapped = 0; 1430 int wrapped = 0;
1431 int empty_cluster;
1423 u64 cached_start; 1432 u64 cached_start;
1424 1433
1425 WARN_ON(num_bytes < root->sectorsize); 1434 WARN_ON(num_bytes < root->sectorsize);
@@ -1431,11 +1440,15 @@ static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1431 data = BTRFS_BLOCK_GROUP_MIXED; 1440 data = BTRFS_BLOCK_GROUP_MIXED;
1432 } 1441 }
1433 1442
1434 if (!data) 1443 if (!data) {
1435 last_ptr = &root->fs_info->last_alloc; 1444 last_ptr = &root->fs_info->last_alloc;
1445 empty_cluster = 128 * 1024;
1446 }
1436 1447
1437 if (data && btrfs_test_opt(root, SSD)) 1448 if (data && btrfs_test_opt(root, SSD)) {
1438 last_ptr = &root->fs_info->last_data_alloc; 1449 last_ptr = &root->fs_info->last_data_alloc;
1450 empty_cluster = 2 * 1024 * 1024;
1451 }
1439 1452
1440 if (last_ptr) { 1453 if (last_ptr) {
1441 if (*last_ptr) 1454 if (*last_ptr)
@@ -1443,8 +1456,9 @@ static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1443 else { 1456 else {
1444 hint_byte = hint_byte & 1457 hint_byte = hint_byte &
1445 ~((u64)BTRFS_BLOCK_GROUP_SIZE - 1); 1458 ~((u64)BTRFS_BLOCK_GROUP_SIZE - 1);
1446 empty_size += 2 * 1024 * 1024; 1459 empty_size += empty_cluster;
1447 } 1460 }
1461 search_start = max(search_start, hint_byte);
1448 } 1462 }
1449 1463
1450 search_end = min(search_end, 1464 search_end = min(search_end,
@@ -1476,7 +1490,7 @@ check_failed:
1476 if (last_ptr && *last_ptr && search_start != *last_ptr) { 1490 if (last_ptr && *last_ptr && search_start != *last_ptr) {
1477 *last_ptr = 0; 1491 *last_ptr = 0;
1478 if (!empty_size) { 1492 if (!empty_size) {
1479 empty_size += 2 * 1024 * 1024; 1493 empty_size += empty_cluster;
1480 total_needed += empty_size; 1494 total_needed += empty_size;
1481 } 1495 }
1482 search_start = find_search_start(root, &block_group, 1496 search_start = find_search_start(root, &block_group,
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 9262ab37a7cd..fb6400895ed6 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -255,7 +255,7 @@ static int merge_state(struct extent_io_tree *tree,
255 state->start = other->start; 255 state->start = other->start;
256 other->tree = NULL; 256 other->tree = NULL;
257 if (tree->last == other) 257 if (tree->last == other)
258 tree->last = NULL; 258 tree->last = state;
259 rb_erase(&other->rb_node, &tree->state); 259 rb_erase(&other->rb_node, &tree->state);
260 free_extent_state(other); 260 free_extent_state(other);
261 } 261 }
@@ -268,7 +268,7 @@ static int merge_state(struct extent_io_tree *tree,
268 other->start = state->start; 268 other->start = state->start;
269 state->tree = NULL; 269 state->tree = NULL;
270 if (tree->last == state) 270 if (tree->last == state)
271 tree->last = NULL; 271 tree->last = other;
272 rb_erase(&state->rb_node, &tree->state); 272 rb_erase(&state->rb_node, &tree->state);
273 free_extent_state(state); 273 free_extent_state(state);
274 } 274 }
@@ -397,8 +397,9 @@ static int clear_state_bit(struct extent_io_tree *tree,
397 if (delete || state->state == 0) { 397 if (delete || state->state == 0) {
398 if (state->tree) { 398 if (state->tree) {
399 clear_state_cb(tree, state, state->state); 399 clear_state_cb(tree, state, state->state);
400 if (tree->last == state) 400 if (tree->last == state) {
401 tree->last = NULL; 401 tree->last = extent_state_next(state);
402 }
402 rb_erase(&state->rb_node, &tree->state); 403 rb_erase(&state->rb_node, &tree->state);
403 state->tree = NULL; 404 state->tree = NULL;
404 free_extent_state(state); 405 free_extent_state(state);
@@ -962,6 +963,35 @@ out:
962} 963}
963EXPORT_SYMBOL(find_first_extent_bit); 964EXPORT_SYMBOL(find_first_extent_bit);
964 965
966struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
967 u64 start, int bits)
968{
969 struct rb_node *node;
970 struct extent_state *state;
971
972 /*
973 * this search will find all the extents that end after
974 * our range starts.
975 */
976 node = tree_search(tree, start);
977 if (!node || IS_ERR(node)) {
978 goto out;
979 }
980
981 while(1) {
982 state = rb_entry(node, struct extent_state, rb_node);
983 if (state->end >= start && (state->state & bits)) {
984 return state;
985 }
986 node = rb_next(node);
987 if (!node)
988 break;
989 }
990out:
991 return NULL;
992}
993EXPORT_SYMBOL(find_first_extent_bit_state);
994
965u64 find_lock_delalloc_range(struct extent_io_tree *tree, 995u64 find_lock_delalloc_range(struct extent_io_tree *tree,
966 u64 *start, u64 *end, u64 max_bytes) 996 u64 *start, u64 *end, u64 max_bytes)
967{ 997{
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index 151fdada4dc4..fcc4bb078c24 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -81,6 +81,15 @@ struct extent_buffer {
81 81
82struct extent_map_tree; 82struct extent_map_tree;
83 83
84static inline struct extent_state *extent_state_next(struct extent_state *state)
85{
86 struct rb_node *node;
87 node = rb_next(&state->rb_node);
88 if (!node)
89 return NULL;
90 return rb_entry(node, struct extent_state, rb_node);
91}
92
84typedef struct extent_map *(get_extent_t)(struct inode *inode, 93typedef struct extent_map *(get_extent_t)(struct inode *inode,
85 struct page *page, 94 struct page *page,
86 size_t page_offset, 95 size_t page_offset,
@@ -122,6 +131,8 @@ int set_extent_delalloc(struct extent_io_tree *tree, u64 start, u64 end,
122 gfp_t mask); 131 gfp_t mask);
123int find_first_extent_bit(struct extent_io_tree *tree, u64 start, 132int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
124 u64 *start_ret, u64 *end_ret, int bits); 133 u64 *start_ret, u64 *end_ret, int bits);
134struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
135 u64 start, int bits);
125int extent_invalidatepage(struct extent_io_tree *tree, 136int extent_invalidatepage(struct extent_io_tree *tree,
126 struct page *page, unsigned long offset); 137 struct page *page, unsigned long offset);
127int extent_write_full_page(struct extent_io_tree *tree, struct page *page, 138int extent_write_full_page(struct extent_io_tree *tree, struct page *page,