diff options
author | Chris Mason <chris.mason@oracle.com> | 2008-02-18 12:12:38 -0500 |
---|---|---|
committer | Chris Mason <chris.mason@oracle.com> | 2008-09-25 11:04:00 -0400 |
commit | d7fc640e6fed46932f7c74e14f9b58b8637c66cf (patch) | |
tree | 525eda21f9e0d6d18bd55fd23d3a31814b224aa8 | |
parent | 9afbb0b752ef30a429c45b9de6706e28ad1a36e1 (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>
-rw-r--r-- | fs/btrfs/disk-io.c | 2 | ||||
-rw-r--r-- | fs/btrfs/extent-tree.c | 34 | ||||
-rw-r--r-- | fs/btrfs/extent_io.c | 38 | ||||
-rw-r--r-- | fs/btrfs/extent_io.h | 11 |
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) | |||
951 | void btrfs_btree_balance_dirty(struct btrfs_root *root, unsigned long nr) | 951 | void 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 | ||
957 | void btrfs_set_buffer_defrag(struct extent_buffer *buf) | 957 | void 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 | |||
202 | again: | 205 | again: |
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 | } |
963 | EXPORT_SYMBOL(find_first_extent_bit); | 964 | EXPORT_SYMBOL(find_first_extent_bit); |
964 | 965 | ||
966 | struct 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 | } | ||
990 | out: | ||
991 | return NULL; | ||
992 | } | ||
993 | EXPORT_SYMBOL(find_first_extent_bit_state); | ||
994 | |||
965 | u64 find_lock_delalloc_range(struct extent_io_tree *tree, | 995 | u64 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 | ||
82 | struct extent_map_tree; | 82 | struct extent_map_tree; |
83 | 83 | ||
84 | static 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 | |||
84 | typedef struct extent_map *(get_extent_t)(struct inode *inode, | 93 | typedef 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); |
123 | int find_first_extent_bit(struct extent_io_tree *tree, u64 start, | 132 | int 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); |
134 | struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree, | ||
135 | u64 start, int bits); | ||
125 | int extent_invalidatepage(struct extent_io_tree *tree, | 136 | int extent_invalidatepage(struct extent_io_tree *tree, |
126 | struct page *page, unsigned long offset); | 137 | struct page *page, unsigned long offset); |
127 | int extent_write_full_page(struct extent_io_tree *tree, struct page *page, | 138 | int extent_write_full_page(struct extent_io_tree *tree, struct page *page, |