Commit | Line | Data |
---|---|---|
2e635a27 | 1 | #include <linux/module.h> |
fec577fb CM |
2 | #include "ctree.h" |
3 | #include "disk-io.h" | |
4 | #include "print-tree.h" | |
e089f05c | 5 | #include "transaction.h" |
fec577fb | 6 | |
e089f05c CM |
7 | static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
8 | *orig_root, u64 num_blocks, u64 search_start, u64 | |
9 | search_end, struct btrfs_key *ins); | |
10 | static int finish_current_insert(struct btrfs_trans_handle *trans, struct | |
11 | btrfs_root *extent_root); | |
e20d96d6 CM |
12 | static int del_pending_extents(struct btrfs_trans_handle *trans, struct |
13 | btrfs_root *extent_root); | |
fec577fb | 14 | |
31f3c99b CM |
15 | struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root, |
16 | struct btrfs_block_group_cache | |
17 | *hint, int data) | |
cd1bc465 CM |
18 | { |
19 | struct btrfs_block_group_cache *cache[8]; | |
31f3c99b | 20 | struct btrfs_block_group_cache *found_group = NULL; |
cd1bc465 CM |
21 | struct btrfs_fs_info *info = root->fs_info; |
22 | u64 used; | |
31f3c99b CM |
23 | u64 last = 0; |
24 | u64 hint_last; | |
cd1bc465 CM |
25 | int i; |
26 | int ret; | |
31f3c99b CM |
27 | int full_search = 0; |
28 | if (hint) { | |
29 | used = btrfs_block_group_used(&hint->item); | |
30 | if (used < (hint->key.offset * 2) / 3) { | |
31 | return hint; | |
32 | } | |
33 | radix_tree_tag_clear(&info->block_group_radix, | |
34 | hint->key.objectid + hint->key.offset - 1, | |
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 | } | |
cd1bc465 CM |
42 | while(1) { |
43 | ret = radix_tree_gang_lookup_tag(&info->block_group_radix, | |
44 | (void **)cache, | |
45 | last, ARRAY_SIZE(cache), | |
31f3c99b | 46 | BTRFS_BLOCK_GROUP_AVAIL); |
cd1bc465 CM |
47 | if (!ret) |
48 | break; | |
49 | for (i = 0; i < ret; i++) { | |
50 | used = btrfs_block_group_used(&cache[i]->item); | |
31f3c99b | 51 | if (used < (cache[i]->key.offset * 2) / 3) { |
cd1bc465 | 52 | info->block_group_cache = cache[i]; |
31f3c99b CM |
53 | found_group = cache[i]; |
54 | goto found; | |
cd1bc465 | 55 | } |
31f3c99b CM |
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); | |
cd1bc465 | 60 | last = cache[i]->key.objectid + |
31f3c99b | 61 | cache[i]->key.offset; |
cd1bc465 CM |
62 | } |
63 | } | |
31f3c99b CM |
64 | last = hint_last; |
65 | again: | |
cd1bc465 CM |
66 | while(1) { |
67 | ret = radix_tree_gang_lookup(&info->block_group_radix, | |
68 | (void **)cache, | |
69 | last, ARRAY_SIZE(cache)); | |
70 | if (!ret) | |
71 | break; | |
72 | for (i = 0; i < ret; i++) { | |
73 | used = btrfs_block_group_used(&cache[i]->item); | |
31f3c99b | 74 | if (used < cache[i]->key.offset) { |
cd1bc465 | 75 | info->block_group_cache = cache[i]; |
31f3c99b CM |
76 | found_group = cache[i]; |
77 | goto found; | |
cd1bc465 | 78 | } |
31f3c99b CM |
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); | |
cd1bc465 | 83 | last = cache[i]->key.objectid + |
31f3c99b | 84 | cache[i]->key.offset; |
cd1bc465 CM |
85 | } |
86 | } | |
87 | info->block_group_cache = NULL; | |
31f3c99b CM |
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; | |
cd1bc465 CM |
100 | } |
101 | ||
b18c6685 CM |
102 | int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans, |
103 | struct btrfs_root *root, | |
104 | u64 blocknr, u64 num_blocks) | |
02217ed2 | 105 | { |
5caf2a00 | 106 | struct btrfs_path *path; |
02217ed2 | 107 | int ret; |
e2fa7227 | 108 | struct btrfs_key key; |
234b63a0 CM |
109 | struct btrfs_leaf *l; |
110 | struct btrfs_extent_item *item; | |
e2fa7227 | 111 | struct btrfs_key ins; |
cf27e1ee | 112 | u32 refs; |
037e6390 | 113 | |
9f5fae2f CM |
114 | find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1, |
115 | &ins); | |
5caf2a00 CM |
116 | path = btrfs_alloc_path(); |
117 | BUG_ON(!path); | |
118 | btrfs_init_path(path); | |
02217ed2 CM |
119 | key.objectid = blocknr; |
120 | key.flags = 0; | |
62e2749e | 121 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); |
6407bf6d | 122 | key.offset = num_blocks; |
5caf2a00 | 123 | ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path, |
9f5fae2f | 124 | 0, 1); |
a429e513 CM |
125 | if (ret != 0) { |
126 | printk("can't find block %Lu %Lu\n", blocknr, num_blocks); | |
a28ec197 | 127 | BUG(); |
a429e513 | 128 | } |
02217ed2 | 129 | BUG_ON(ret != 0); |
5caf2a00 CM |
130 | l = btrfs_buffer_leaf(path->nodes[0]); |
131 | item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item); | |
cf27e1ee CM |
132 | refs = btrfs_extent_refs(item); |
133 | btrfs_set_extent_refs(item, refs + 1); | |
5caf2a00 | 134 | btrfs_mark_buffer_dirty(path->nodes[0]); |
a28ec197 | 135 | |
5caf2a00 CM |
136 | btrfs_release_path(root->fs_info->extent_root, path); |
137 | btrfs_free_path(path); | |
9f5fae2f | 138 | finish_current_insert(trans, root->fs_info->extent_root); |
e20d96d6 | 139 | del_pending_extents(trans, root->fs_info->extent_root); |
02217ed2 CM |
140 | return 0; |
141 | } | |
142 | ||
b18c6685 CM |
143 | static int lookup_extent_ref(struct btrfs_trans_handle *trans, |
144 | struct btrfs_root *root, u64 blocknr, | |
145 | u64 num_blocks, u32 *refs) | |
a28ec197 | 146 | { |
5caf2a00 | 147 | struct btrfs_path *path; |
a28ec197 | 148 | int ret; |
e2fa7227 | 149 | struct btrfs_key key; |
234b63a0 CM |
150 | struct btrfs_leaf *l; |
151 | struct btrfs_extent_item *item; | |
5caf2a00 CM |
152 | |
153 | path = btrfs_alloc_path(); | |
154 | btrfs_init_path(path); | |
a28ec197 | 155 | key.objectid = blocknr; |
6407bf6d | 156 | key.offset = num_blocks; |
62e2749e CM |
157 | key.flags = 0; |
158 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); | |
5caf2a00 | 159 | ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path, |
9f5fae2f | 160 | 0, 0); |
a28ec197 CM |
161 | if (ret != 0) |
162 | BUG(); | |
5caf2a00 CM |
163 | l = btrfs_buffer_leaf(path->nodes[0]); |
164 | item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item); | |
cf27e1ee | 165 | *refs = btrfs_extent_refs(item); |
5caf2a00 CM |
166 | btrfs_release_path(root->fs_info->extent_root, path); |
167 | btrfs_free_path(path); | |
a28ec197 CM |
168 | return 0; |
169 | } | |
170 | ||
c5739bba CM |
171 | int btrfs_inc_root_ref(struct btrfs_trans_handle *trans, |
172 | struct btrfs_root *root) | |
173 | { | |
b18c6685 | 174 | return btrfs_inc_extent_ref(trans, root, bh_blocknr(root->node), 1); |
c5739bba CM |
175 | } |
176 | ||
e089f05c | 177 | int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root, |
e20d96d6 | 178 | struct buffer_head *buf) |
02217ed2 CM |
179 | { |
180 | u64 blocknr; | |
e20d96d6 | 181 | struct btrfs_node *buf_node; |
6407bf6d CM |
182 | struct btrfs_leaf *buf_leaf; |
183 | struct btrfs_disk_key *key; | |
184 | struct btrfs_file_extent_item *fi; | |
02217ed2 | 185 | int i; |
6407bf6d CM |
186 | int leaf; |
187 | int ret; | |
a28ec197 | 188 | |
3768f368 | 189 | if (!root->ref_cows) |
a28ec197 | 190 | return 0; |
e20d96d6 | 191 | buf_node = btrfs_buffer_node(buf); |
6407bf6d CM |
192 | leaf = btrfs_is_leaf(buf_node); |
193 | buf_leaf = btrfs_buffer_leaf(buf); | |
e20d96d6 | 194 | for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) { |
6407bf6d CM |
195 | if (leaf) { |
196 | key = &buf_leaf->items[i].key; | |
197 | if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY) | |
198 | continue; | |
199 | fi = btrfs_item_ptr(buf_leaf, i, | |
200 | struct btrfs_file_extent_item); | |
236454df CM |
201 | if (btrfs_file_extent_type(fi) == |
202 | BTRFS_FILE_EXTENT_INLINE) | |
203 | continue; | |
b18c6685 | 204 | ret = btrfs_inc_extent_ref(trans, root, |
6407bf6d CM |
205 | btrfs_file_extent_disk_blocknr(fi), |
206 | btrfs_file_extent_disk_num_blocks(fi)); | |
207 | BUG_ON(ret); | |
208 | } else { | |
209 | blocknr = btrfs_node_blockptr(buf_node, i); | |
b18c6685 | 210 | ret = btrfs_inc_extent_ref(trans, root, blocknr, 1); |
6407bf6d CM |
211 | BUG_ON(ret); |
212 | } | |
02217ed2 CM |
213 | } |
214 | return 0; | |
215 | } | |
216 | ||
9078a3e1 CM |
217 | static int write_one_cache_group(struct btrfs_trans_handle *trans, |
218 | struct btrfs_root *root, | |
219 | struct btrfs_path *path, | |
220 | struct btrfs_block_group_cache *cache) | |
221 | { | |
222 | int ret; | |
223 | int pending_ret; | |
224 | struct btrfs_root *extent_root = root->fs_info->extent_root; | |
225 | struct btrfs_block_group_item *bi; | |
226 | struct btrfs_key ins; | |
227 | ||
228 | find_free_extent(trans, extent_root, 0, 0, (u64)-1, &ins); | |
229 | ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1); | |
230 | BUG_ON(ret); | |
231 | bi = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0], | |
232 | struct btrfs_block_group_item); | |
233 | memcpy(bi, &cache->item, sizeof(*bi)); | |
234 | mark_buffer_dirty(path->nodes[0]); | |
235 | btrfs_release_path(extent_root, path); | |
236 | ||
237 | finish_current_insert(trans, extent_root); | |
238 | pending_ret = del_pending_extents(trans, extent_root); | |
239 | if (ret) | |
240 | return ret; | |
241 | if (pending_ret) | |
242 | return pending_ret; | |
243 | return 0; | |
244 | ||
245 | } | |
246 | ||
247 | int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans, | |
248 | struct btrfs_root *root) | |
249 | { | |
250 | struct btrfs_block_group_cache *cache[8]; | |
251 | int ret; | |
252 | int err = 0; | |
253 | int werr = 0; | |
254 | struct radix_tree_root *radix = &root->fs_info->block_group_radix; | |
255 | int i; | |
256 | struct btrfs_path *path; | |
257 | ||
258 | path = btrfs_alloc_path(); | |
259 | if (!path) | |
260 | return -ENOMEM; | |
261 | ||
262 | while(1) { | |
263 | ret = radix_tree_gang_lookup_tag(radix, (void **)cache, | |
264 | 0, ARRAY_SIZE(cache), | |
265 | BTRFS_BLOCK_GROUP_DIRTY); | |
266 | if (!ret) | |
267 | break; | |
268 | for (i = 0; i < ret; i++) { | |
269 | radix_tree_tag_clear(radix, cache[i]->key.objectid + | |
270 | cache[i]->key.offset - 1, | |
271 | BTRFS_BLOCK_GROUP_DIRTY); | |
272 | err = write_one_cache_group(trans, root, | |
273 | path, cache[i]); | |
274 | if (err) | |
275 | werr = err; | |
31f3c99b | 276 | cache[i]->last_alloc = cache[i]->first_free; |
9078a3e1 CM |
277 | } |
278 | } | |
279 | btrfs_free_path(path); | |
280 | return werr; | |
281 | } | |
282 | ||
283 | static int update_block_group(struct btrfs_trans_handle *trans, | |
284 | struct btrfs_root *root, | |
285 | u64 blocknr, u64 num, int alloc) | |
286 | { | |
287 | struct btrfs_block_group_cache *cache; | |
288 | struct btrfs_fs_info *info = root->fs_info; | |
289 | u64 total = num; | |
290 | u64 old_val; | |
291 | u64 block_in_group; | |
292 | int ret; | |
293 | while(total) { | |
294 | ret = radix_tree_gang_lookup(&info->block_group_radix, | |
295 | (void **)&cache, blocknr, 1); | |
cd1bc465 CM |
296 | if (!ret) { |
297 | printk(KERN_CRIT "blocknr %Lu lookup failed\n", | |
298 | blocknr); | |
9078a3e1 | 299 | return -1; |
cd1bc465 | 300 | } |
9078a3e1 CM |
301 | block_in_group = blocknr - cache->key.objectid; |
302 | WARN_ON(block_in_group > cache->key.offset); | |
303 | radix_tree_tag_set(&info->block_group_radix, | |
304 | cache->key.objectid + cache->key.offset - 1, | |
305 | BTRFS_BLOCK_GROUP_DIRTY); | |
306 | ||
307 | old_val = btrfs_block_group_used(&cache->item); | |
308 | num = min(total, cache->key.offset - block_in_group); | |
309 | total -= num; | |
310 | blocknr += num; | |
cd1bc465 | 311 | if (alloc) { |
9078a3e1 | 312 | old_val += num; |
cd1bc465 CM |
313 | if (blocknr > cache->last_alloc) |
314 | cache->last_alloc = blocknr; | |
315 | } else { | |
9078a3e1 | 316 | old_val -= num; |
cd1bc465 CM |
317 | if (blocknr < cache->first_free) |
318 | cache->first_free = blocknr; | |
319 | } | |
9078a3e1 CM |
320 | btrfs_set_block_group_used(&cache->item, old_val); |
321 | } | |
322 | return 0; | |
323 | } | |
324 | ||
06a2f9fa CM |
325 | static int try_remove_page(struct address_space *mapping, unsigned long index) |
326 | { | |
327 | int ret; | |
328 | ret = invalidate_mapping_pages(mapping, index, index); | |
329 | return ret; | |
330 | } | |
331 | ||
e089f05c CM |
332 | int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct |
333 | btrfs_root *root) | |
a28ec197 | 334 | { |
8ef97622 | 335 | unsigned long gang[8]; |
06a2f9fa | 336 | struct inode *btree_inode = root->fs_info->btree_inode; |
88fd146c | 337 | u64 first = 0; |
a28ec197 CM |
338 | int ret; |
339 | int i; | |
8ef97622 | 340 | struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix; |
a28ec197 CM |
341 | |
342 | while(1) { | |
8ef97622 CM |
343 | ret = find_first_radix_bit(pinned_radix, gang, |
344 | ARRAY_SIZE(gang)); | |
a28ec197 CM |
345 | if (!ret) |
346 | break; | |
88fd146c | 347 | if (!first) |
8ef97622 | 348 | first = gang[0]; |
0579da42 | 349 | for (i = 0; i < ret; i++) { |
8ef97622 | 350 | clear_radix_bit(pinned_radix, gang[i]); |
06a2f9fa CM |
351 | try_remove_page(btree_inode->i_mapping, |
352 | gang[i] << (PAGE_CACHE_SHIFT - | |
353 | btree_inode->i_blkbits)); | |
0579da42 | 354 | } |
a28ec197 CM |
355 | } |
356 | return 0; | |
357 | } | |
358 | ||
e089f05c CM |
359 | static int finish_current_insert(struct btrfs_trans_handle *trans, struct |
360 | btrfs_root *extent_root) | |
037e6390 | 361 | { |
e2fa7227 | 362 | struct btrfs_key ins; |
234b63a0 | 363 | struct btrfs_extent_item extent_item; |
037e6390 CM |
364 | int i; |
365 | int ret; | |
1261ec42 CM |
366 | u64 super_blocks_used; |
367 | struct btrfs_fs_info *info = extent_root->fs_info; | |
037e6390 | 368 | |
cf27e1ee | 369 | btrfs_set_extent_refs(&extent_item, 1); |
037e6390 CM |
370 | ins.offset = 1; |
371 | ins.flags = 0; | |
62e2749e | 372 | btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY); |
5d0c3e60 | 373 | btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid); |
037e6390 | 374 | |
f2458e1d CM |
375 | for (i = 0; i < extent_root->fs_info->extent_tree_insert_nr; i++) { |
376 | ins.objectid = extent_root->fs_info->extent_tree_insert[i]; | |
1261ec42 CM |
377 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
378 | btrfs_set_super_blocks_used(info->disk_super, | |
379 | super_blocks_used + 1); | |
e089f05c CM |
380 | ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item, |
381 | sizeof(extent_item)); | |
037e6390 CM |
382 | BUG_ON(ret); |
383 | } | |
f2458e1d CM |
384 | extent_root->fs_info->extent_tree_insert_nr = 0; |
385 | extent_root->fs_info->extent_tree_prealloc_nr = 0; | |
037e6390 CM |
386 | return 0; |
387 | } | |
388 | ||
8ef97622 | 389 | static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending) |
e20d96d6 CM |
390 | { |
391 | int err; | |
78fae27e | 392 | struct btrfs_header *header; |
8ef97622 CM |
393 | struct buffer_head *bh; |
394 | ||
f4b9aa8d | 395 | if (!pending) { |
d98237b3 | 396 | bh = btrfs_find_tree_block(root, blocknr); |
2c90e5d6 CM |
397 | if (bh) { |
398 | if (buffer_uptodate(bh)) { | |
399 | u64 transid = | |
400 | root->fs_info->running_transaction->transid; | |
401 | header = btrfs_buffer_header(bh); | |
402 | if (btrfs_header_generation(header) == | |
403 | transid) { | |
404 | btrfs_block_release(root, bh); | |
405 | return 0; | |
406 | } | |
f4b9aa8d | 407 | } |
d6025579 | 408 | btrfs_block_release(root, bh); |
8ef97622 | 409 | } |
8ef97622 | 410 | err = set_radix_bit(&root->fs_info->pinned_radix, blocknr); |
f4b9aa8d CM |
411 | } else { |
412 | err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr); | |
413 | } | |
8ef97622 | 414 | BUG_ON(err); |
e20d96d6 CM |
415 | return 0; |
416 | } | |
417 | ||
fec577fb | 418 | /* |
a28ec197 | 419 | * remove an extent from the root, returns 0 on success |
fec577fb | 420 | */ |
e089f05c | 421 | static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
78fae27e | 422 | *root, u64 blocknr, u64 num_blocks, int pin) |
a28ec197 | 423 | { |
5caf2a00 | 424 | struct btrfs_path *path; |
e2fa7227 | 425 | struct btrfs_key key; |
1261ec42 CM |
426 | struct btrfs_fs_info *info = root->fs_info; |
427 | struct btrfs_root *extent_root = info->extent_root; | |
a28ec197 | 428 | int ret; |
234b63a0 | 429 | struct btrfs_extent_item *ei; |
e2fa7227 | 430 | struct btrfs_key ins; |
cf27e1ee | 431 | u32 refs; |
037e6390 | 432 | |
a28ec197 CM |
433 | key.objectid = blocknr; |
434 | key.flags = 0; | |
62e2749e | 435 | btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); |
a28ec197 CM |
436 | key.offset = num_blocks; |
437 | ||
e089f05c | 438 | find_free_extent(trans, root, 0, 0, (u64)-1, &ins); |
5caf2a00 CM |
439 | path = btrfs_alloc_path(); |
440 | BUG_ON(!path); | |
441 | btrfs_init_path(path); | |
5f26f772 | 442 | |
5caf2a00 | 443 | ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1); |
a28ec197 | 444 | if (ret) { |
2e635a27 | 445 | printk("failed to find %Lu\n", key.objectid); |
234b63a0 | 446 | btrfs_print_tree(extent_root, extent_root->node); |
2e635a27 | 447 | printk("failed to find %Lu\n", key.objectid); |
a28ec197 CM |
448 | BUG(); |
449 | } | |
5caf2a00 | 450 | ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0], |
123abc88 | 451 | struct btrfs_extent_item); |
a28ec197 | 452 | BUG_ON(ei->refs == 0); |
cf27e1ee CM |
453 | refs = btrfs_extent_refs(ei) - 1; |
454 | btrfs_set_extent_refs(ei, refs); | |
5caf2a00 | 455 | btrfs_mark_buffer_dirty(path->nodes[0]); |
cf27e1ee | 456 | if (refs == 0) { |
1261ec42 | 457 | u64 super_blocks_used; |
78fae27e CM |
458 | |
459 | if (pin) { | |
8ef97622 | 460 | ret = pin_down_block(root, blocknr, 0); |
78fae27e CM |
461 | BUG_ON(ret); |
462 | } | |
463 | ||
1261ec42 CM |
464 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
465 | btrfs_set_super_blocks_used(info->disk_super, | |
466 | super_blocks_used - num_blocks); | |
5caf2a00 | 467 | ret = btrfs_del_item(trans, extent_root, path); |
a28ec197 CM |
468 | if (ret) |
469 | BUG(); | |
9078a3e1 CM |
470 | ret = update_block_group(trans, root, blocknr, num_blocks, 0); |
471 | BUG_ON(ret); | |
a28ec197 | 472 | } |
5caf2a00 CM |
473 | btrfs_release_path(extent_root, path); |
474 | btrfs_free_path(path); | |
e089f05c | 475 | finish_current_insert(trans, extent_root); |
a28ec197 CM |
476 | return ret; |
477 | } | |
478 | ||
a28ec197 CM |
479 | /* |
480 | * find all the blocks marked as pending in the radix tree and remove | |
481 | * them from the extent map | |
482 | */ | |
e089f05c CM |
483 | static int del_pending_extents(struct btrfs_trans_handle *trans, struct |
484 | btrfs_root *extent_root) | |
a28ec197 CM |
485 | { |
486 | int ret; | |
e20d96d6 CM |
487 | int wret; |
488 | int err = 0; | |
8ef97622 | 489 | unsigned long gang[4]; |
a28ec197 | 490 | int i; |
8ef97622 CM |
491 | struct radix_tree_root *pending_radix; |
492 | struct radix_tree_root *pinned_radix; | |
493 | ||
494 | pending_radix = &extent_root->fs_info->pending_del_radix; | |
495 | pinned_radix = &extent_root->fs_info->pinned_radix; | |
a28ec197 CM |
496 | |
497 | while(1) { | |
8ef97622 CM |
498 | ret = find_first_radix_bit(pending_radix, gang, |
499 | ARRAY_SIZE(gang)); | |
a28ec197 CM |
500 | if (!ret) |
501 | break; | |
502 | for (i = 0; i < ret; i++) { | |
8ef97622 CM |
503 | wret = set_radix_bit(pinned_radix, gang[i]); |
504 | BUG_ON(wret); | |
505 | wret = clear_radix_bit(pending_radix, gang[i]); | |
506 | BUG_ON(wret); | |
d5719762 | 507 | wret = __free_extent(trans, extent_root, |
8ef97622 | 508 | gang[i], 1, 0); |
e20d96d6 CM |
509 | if (wret) |
510 | err = wret; | |
fec577fb CM |
511 | } |
512 | } | |
e20d96d6 | 513 | return err; |
fec577fb CM |
514 | } |
515 | ||
516 | /* | |
517 | * remove an extent from the root, returns 0 on success | |
518 | */ | |
e089f05c CM |
519 | int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
520 | *root, u64 blocknr, u64 num_blocks, int pin) | |
fec577fb | 521 | { |
9f5fae2f | 522 | struct btrfs_root *extent_root = root->fs_info->extent_root; |
fec577fb CM |
523 | int pending_ret; |
524 | int ret; | |
a28ec197 | 525 | |
fec577fb | 526 | if (root == extent_root) { |
8ef97622 | 527 | pin_down_block(root, blocknr, 1); |
fec577fb CM |
528 | return 0; |
529 | } | |
78fae27e | 530 | ret = __free_extent(trans, root, blocknr, num_blocks, pin); |
e20d96d6 | 531 | pending_ret = del_pending_extents(trans, root->fs_info->extent_root); |
fec577fb CM |
532 | return ret ? ret : pending_ret; |
533 | } | |
534 | ||
535 | /* | |
536 | * walks the btree of allocated extents and find a hole of a given size. | |
537 | * The key ins is changed to record the hole: | |
538 | * ins->objectid == block start | |
62e2749e | 539 | * ins->flags = BTRFS_EXTENT_ITEM_KEY |
fec577fb CM |
540 | * ins->offset == number of blocks |
541 | * Any available blocks before search_start are skipped. | |
542 | */ | |
e089f05c CM |
543 | static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root |
544 | *orig_root, u64 num_blocks, u64 search_start, u64 | |
545 | search_end, struct btrfs_key *ins) | |
fec577fb | 546 | { |
5caf2a00 | 547 | struct btrfs_path *path; |
e2fa7227 | 548 | struct btrfs_key key; |
fec577fb CM |
549 | int ret; |
550 | u64 hole_size = 0; | |
551 | int slot = 0; | |
e20d96d6 | 552 | u64 last_block = 0; |
037e6390 | 553 | u64 test_block; |
fec577fb | 554 | int start_found; |
234b63a0 | 555 | struct btrfs_leaf *l; |
9f5fae2f | 556 | struct btrfs_root * root = orig_root->fs_info->extent_root; |
f2458e1d | 557 | struct btrfs_fs_info *info = root->fs_info; |
0579da42 | 558 | int total_needed = num_blocks; |
f2458e1d CM |
559 | int total_found = 0; |
560 | int fill_prealloc = 0; | |
e20d96d6 | 561 | int level; |
31f3c99b CM |
562 | int update_block_group = 0; |
563 | struct btrfs_block_group_cache *hint_block_group; | |
fec577fb | 564 | |
b1a4d965 CM |
565 | path = btrfs_alloc_path(); |
566 | ins->flags = 0; | |
567 | btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY); | |
568 | ||
e20d96d6 | 569 | level = btrfs_header_level(btrfs_buffer_header(root->node)); |
31f3c99b CM |
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 | } | |
f2458e1d CM |
586 | if (num_blocks == 0) { |
587 | fill_prealloc = 1; | |
588 | num_blocks = 1; | |
308535a0 | 589 | total_needed = (min(level + 1, BTRFS_MAX_LEVEL) + 2) * 3; |
f2458e1d | 590 | } |
31f3c99b CM |
591 | if (1 || !search_start) { |
592 | trans->block_group = btrfs_find_block_group(root, | |
593 | trans->block_group, | |
594 | 0); | |
595 | if (trans->block_group->last_alloc > search_start) | |
596 | search_start = trans->block_group->last_alloc; | |
597 | update_block_group = 1; | |
598 | } | |
fec577fb | 599 | check_failed: |
5caf2a00 | 600 | btrfs_init_path(path); |
fec577fb CM |
601 | ins->objectid = search_start; |
602 | ins->offset = 0; | |
fec577fb | 603 | start_found = 0; |
5caf2a00 | 604 | ret = btrfs_search_slot(trans, root, ins, path, 0, 0); |
0f70abe2 CM |
605 | if (ret < 0) |
606 | goto error; | |
aa5d6bed | 607 | |
5caf2a00 CM |
608 | if (path->slots[0] > 0) |
609 | path->slots[0]--; | |
0579da42 | 610 | |
fec577fb | 611 | while (1) { |
5caf2a00 CM |
612 | l = btrfs_buffer_leaf(path->nodes[0]); |
613 | slot = path->slots[0]; | |
7518a238 | 614 | if (slot >= btrfs_header_nritems(&l->header)) { |
f2458e1d CM |
615 | if (fill_prealloc) { |
616 | info->extent_tree_prealloc_nr = 0; | |
617 | total_found = 0; | |
618 | } | |
5caf2a00 | 619 | ret = btrfs_next_leaf(root, path); |
fec577fb CM |
620 | if (ret == 0) |
621 | continue; | |
0f70abe2 CM |
622 | if (ret < 0) |
623 | goto error; | |
fec577fb CM |
624 | if (!start_found) { |
625 | ins->objectid = search_start; | |
f2458e1d | 626 | ins->offset = (u64)-1 - search_start; |
fec577fb CM |
627 | start_found = 1; |
628 | goto check_pending; | |
629 | } | |
630 | ins->objectid = last_block > search_start ? | |
631 | last_block : search_start; | |
f2458e1d | 632 | ins->offset = (u64)-1 - ins->objectid; |
fec577fb CM |
633 | goto check_pending; |
634 | } | |
e2fa7227 | 635 | btrfs_disk_key_to_cpu(&key, &l->items[slot].key); |
9078a3e1 CM |
636 | if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) |
637 | goto next; | |
e2fa7227 | 638 | if (key.objectid >= search_start) { |
fec577fb | 639 | if (start_found) { |
0579da42 CM |
640 | if (last_block < search_start) |
641 | last_block = search_start; | |
e2fa7227 | 642 | hole_size = key.objectid - last_block; |
28b8bb9e | 643 | if (hole_size >= num_blocks) { |
fec577fb | 644 | ins->objectid = last_block; |
037e6390 | 645 | ins->offset = hole_size; |
fec577fb CM |
646 | goto check_pending; |
647 | } | |
0579da42 | 648 | } |
fec577fb | 649 | } |
0579da42 | 650 | start_found = 1; |
e2fa7227 | 651 | last_block = key.objectid + key.offset; |
9078a3e1 | 652 | next: |
5caf2a00 | 653 | path->slots[0]++; |
fec577fb CM |
654 | } |
655 | // FIXME -ENOSPC | |
656 | check_pending: | |
657 | /* we have to make sure we didn't find an extent that has already | |
658 | * been allocated by the map tree or the original allocation | |
659 | */ | |
5caf2a00 | 660 | btrfs_release_path(root, path); |
fec577fb | 661 | BUG_ON(ins->objectid < search_start); |
06a2f9fa CM |
662 | if (ins->objectid >= btrfs_super_total_blocks(info->disk_super)) { |
663 | if (search_start == 0) | |
664 | return -ENOSPC; | |
665 | search_start = 0; | |
666 | goto check_failed; | |
667 | } | |
037e6390 | 668 | for (test_block = ins->objectid; |
f2458e1d CM |
669 | test_block < ins->objectid + num_blocks; test_block++) { |
670 | if (test_radix_bit(&info->pinned_radix, test_block)) { | |
037e6390 | 671 | search_start = test_block + 1; |
fec577fb CM |
672 | goto check_failed; |
673 | } | |
674 | } | |
f2458e1d CM |
675 | if (!fill_prealloc && info->extent_tree_insert_nr) { |
676 | u64 last = | |
677 | info->extent_tree_insert[info->extent_tree_insert_nr - 1]; | |
678 | if (ins->objectid + num_blocks > | |
679 | info->extent_tree_insert[0] && | |
680 | ins->objectid <= last) { | |
681 | search_start = last + 1; | |
682 | WARN_ON(1); | |
683 | goto check_failed; | |
684 | } | |
685 | } | |
686 | if (!fill_prealloc && info->extent_tree_prealloc_nr) { | |
687 | u64 first = | |
688 | info->extent_tree_prealloc[info->extent_tree_prealloc_nr - 1]; | |
689 | if (ins->objectid + num_blocks > first && | |
690 | ins->objectid <= info->extent_tree_prealloc[0]) { | |
691 | search_start = info->extent_tree_prealloc[0] + 1; | |
692 | WARN_ON(1); | |
693 | goto check_failed; | |
694 | } | |
695 | } | |
696 | if (fill_prealloc) { | |
697 | int nr; | |
698 | test_block = ins->objectid; | |
699 | while(test_block < ins->objectid + ins->offset && | |
700 | total_found < total_needed) { | |
701 | nr = total_needed - total_found - 1; | |
702 | BUG_ON(nr < 0); | |
cd1bc465 | 703 | info->extent_tree_prealloc[nr] = test_block; |
f2458e1d CM |
704 | total_found++; |
705 | test_block++; | |
706 | } | |
707 | if (total_found < total_needed) { | |
708 | search_start = test_block; | |
709 | goto check_failed; | |
710 | } | |
cd1bc465 CM |
711 | info->extent_tree_prealloc_nr = total_found; |
712 | } | |
31f3c99b CM |
713 | if (update_block_group) { |
714 | ret = radix_tree_gang_lookup(&info->block_group_radix, | |
715 | (void **)&trans->block_group, | |
716 | ins->objectid, 1); | |
717 | if (ret) { | |
718 | trans->block_group->last_alloc = ins->objectid; | |
719 | } | |
f2458e1d | 720 | } |
037e6390 | 721 | ins->offset = num_blocks; |
5caf2a00 | 722 | btrfs_free_path(path); |
fec577fb | 723 | return 0; |
0f70abe2 | 724 | error: |
5caf2a00 CM |
725 | btrfs_release_path(root, path); |
726 | btrfs_free_path(path); | |
0f70abe2 | 727 | return ret; |
fec577fb | 728 | } |
fec577fb CM |
729 | /* |
730 | * finds a free extent and does all the dirty work required for allocation | |
731 | * returns the key for the extent through ins, and a tree buffer for | |
732 | * the first block of the extent through buf. | |
733 | * | |
734 | * returns 0 if everything worked, non-zero otherwise. | |
735 | */ | |
4d775673 CM |
736 | int btrfs_alloc_extent(struct btrfs_trans_handle *trans, |
737 | struct btrfs_root *root, u64 owner, | |
c62a1920 | 738 | u64 num_blocks, u64 search_start, |
4d775673 | 739 | u64 search_end, struct btrfs_key *ins) |
fec577fb CM |
740 | { |
741 | int ret; | |
742 | int pending_ret; | |
1261ec42 CM |
743 | u64 super_blocks_used; |
744 | struct btrfs_fs_info *info = root->fs_info; | |
745 | struct btrfs_root *extent_root = info->extent_root; | |
234b63a0 | 746 | struct btrfs_extent_item extent_item; |
f2458e1d | 747 | struct btrfs_key prealloc_key; |
037e6390 | 748 | |
cf27e1ee | 749 | btrfs_set_extent_refs(&extent_item, 1); |
4d775673 | 750 | btrfs_set_extent_owner(&extent_item, owner); |
fec577fb | 751 | |
037e6390 | 752 | if (root == extent_root) { |
f2458e1d CM |
753 | int nr; |
754 | BUG_ON(info->extent_tree_prealloc_nr == 0); | |
037e6390 | 755 | BUG_ON(num_blocks != 1); |
037e6390 | 756 | ins->offset = 1; |
f2458e1d CM |
757 | info->extent_tree_prealloc_nr--; |
758 | nr = info->extent_tree_prealloc_nr; | |
759 | ins->objectid = info->extent_tree_prealloc[nr]; | |
760 | info->extent_tree_insert[info->extent_tree_insert_nr++] = | |
761 | ins->objectid; | |
9078a3e1 CM |
762 | ret = update_block_group(trans, root, |
763 | ins->objectid, ins->offset, 1); | |
764 | BUG_ON(ret); | |
fec577fb CM |
765 | return 0; |
766 | } | |
f2458e1d | 767 | /* do the real allocation */ |
e089f05c | 768 | ret = find_free_extent(trans, root, num_blocks, search_start, |
037e6390 CM |
769 | search_end, ins); |
770 | if (ret) | |
771 | return ret; | |
fec577fb | 772 | |
f2458e1d CM |
773 | /* then do prealloc for the extent tree */ |
774 | ret = find_free_extent(trans, root, 0, ins->objectid + ins->offset, | |
775 | search_end, &prealloc_key); | |
776 | if (ret) | |
777 | return ret; | |
778 | ||
1261ec42 CM |
779 | super_blocks_used = btrfs_super_blocks_used(info->disk_super); |
780 | btrfs_set_super_blocks_used(info->disk_super, super_blocks_used + | |
781 | num_blocks); | |
e089f05c CM |
782 | ret = btrfs_insert_item(trans, extent_root, ins, &extent_item, |
783 | sizeof(extent_item)); | |
037e6390 | 784 | |
e089f05c | 785 | finish_current_insert(trans, extent_root); |
e20d96d6 | 786 | pending_ret = del_pending_extents(trans, extent_root); |
037e6390 CM |
787 | if (ret) |
788 | return ret; | |
789 | if (pending_ret) | |
790 | return pending_ret; | |
9078a3e1 | 791 | ret = update_block_group(trans, root, ins->objectid, ins->offset, 1); |
037e6390 | 792 | return 0; |
fec577fb CM |
793 | } |
794 | ||
795 | /* | |
796 | * helper function to allocate a block for a given tree | |
797 | * returns the tree buffer or NULL. | |
798 | */ | |
e20d96d6 | 799 | struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans, |
31f3c99b | 800 | struct btrfs_root *root, u64 hint) |
fec577fb | 801 | { |
e2fa7227 | 802 | struct btrfs_key ins; |
fec577fb | 803 | int ret; |
e20d96d6 | 804 | struct buffer_head *buf; |
fec577fb | 805 | |
4d775673 | 806 | ret = btrfs_alloc_extent(trans, root, root->root_key.objectid, |
31f3c99b | 807 | 1, hint, (unsigned long)-1, &ins); |
fec577fb CM |
808 | if (ret) { |
809 | BUG(); | |
810 | return NULL; | |
811 | } | |
9078a3e1 | 812 | BUG_ON(ret); |
d98237b3 | 813 | buf = btrfs_find_create_tree_block(root, ins.objectid); |
df2ce34c | 814 | set_buffer_uptodate(buf); |
7c4452b9 | 815 | set_radix_bit(&trans->transaction->dirty_pages, buf->b_page->index); |
fec577fb CM |
816 | return buf; |
817 | } | |
a28ec197 | 818 | |
6407bf6d CM |
819 | static int drop_leaf_ref(struct btrfs_trans_handle *trans, |
820 | struct btrfs_root *root, struct buffer_head *cur) | |
821 | { | |
822 | struct btrfs_disk_key *key; | |
823 | struct btrfs_leaf *leaf; | |
824 | struct btrfs_file_extent_item *fi; | |
825 | int i; | |
826 | int nritems; | |
827 | int ret; | |
828 | ||
829 | BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur))); | |
830 | leaf = btrfs_buffer_leaf(cur); | |
831 | nritems = btrfs_header_nritems(&leaf->header); | |
832 | for (i = 0; i < nritems; i++) { | |
833 | key = &leaf->items[i].key; | |
834 | if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY) | |
835 | continue; | |
836 | fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item); | |
236454df CM |
837 | if (btrfs_file_extent_type(fi) == BTRFS_FILE_EXTENT_INLINE) |
838 | continue; | |
6407bf6d CM |
839 | /* |
840 | * FIXME make sure to insert a trans record that | |
841 | * repeats the snapshot del on crash | |
842 | */ | |
843 | ret = btrfs_free_extent(trans, root, | |
844 | btrfs_file_extent_disk_blocknr(fi), | |
845 | btrfs_file_extent_disk_num_blocks(fi), | |
846 | 0); | |
847 | BUG_ON(ret); | |
848 | } | |
849 | return 0; | |
850 | } | |
851 | ||
9aca1d51 CM |
852 | /* |
853 | * helper function for drop_snapshot, this walks down the tree dropping ref | |
854 | * counts as it goes. | |
855 | */ | |
e089f05c CM |
856 | static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root |
857 | *root, struct btrfs_path *path, int *level) | |
20524f02 | 858 | { |
e20d96d6 CM |
859 | struct buffer_head *next; |
860 | struct buffer_head *cur; | |
20524f02 CM |
861 | u64 blocknr; |
862 | int ret; | |
863 | u32 refs; | |
864 | ||
5caf2a00 CM |
865 | WARN_ON(*level < 0); |
866 | WARN_ON(*level >= BTRFS_MAX_LEVEL); | |
b18c6685 | 867 | ret = lookup_extent_ref(trans, root, bh_blocknr(path->nodes[*level]), |
6407bf6d | 868 | 1, &refs); |
20524f02 CM |
869 | BUG_ON(ret); |
870 | if (refs > 1) | |
871 | goto out; | |
9aca1d51 CM |
872 | /* |
873 | * walk down to the last node level and free all the leaves | |
874 | */ | |
6407bf6d | 875 | while(*level >= 0) { |
5caf2a00 CM |
876 | WARN_ON(*level < 0); |
877 | WARN_ON(*level >= BTRFS_MAX_LEVEL); | |
20524f02 | 878 | cur = path->nodes[*level]; |
2c90e5d6 CM |
879 | if (btrfs_header_level(btrfs_buffer_header(cur)) != *level) |
880 | WARN_ON(1); | |
7518a238 | 881 | if (path->slots[*level] >= |
e20d96d6 | 882 | btrfs_header_nritems(btrfs_buffer_header(cur))) |
20524f02 | 883 | break; |
6407bf6d CM |
884 | if (*level == 0) { |
885 | ret = drop_leaf_ref(trans, root, cur); | |
886 | BUG_ON(ret); | |
887 | break; | |
888 | } | |
e20d96d6 CM |
889 | blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur), |
890 | path->slots[*level]); | |
b18c6685 | 891 | ret = lookup_extent_ref(trans, root, blocknr, 1, &refs); |
6407bf6d CM |
892 | BUG_ON(ret); |
893 | if (refs != 1) { | |
20524f02 | 894 | path->slots[*level]++; |
e089f05c | 895 | ret = btrfs_free_extent(trans, root, blocknr, 1, 1); |
20524f02 CM |
896 | BUG_ON(ret); |
897 | continue; | |
898 | } | |
20524f02 | 899 | next = read_tree_block(root, blocknr); |
5caf2a00 | 900 | WARN_ON(*level <= 0); |
83e15a28 | 901 | if (path->nodes[*level-1]) |
234b63a0 | 902 | btrfs_block_release(root, path->nodes[*level-1]); |
20524f02 | 903 | path->nodes[*level-1] = next; |
e20d96d6 | 904 | *level = btrfs_header_level(btrfs_buffer_header(next)); |
20524f02 CM |
905 | path->slots[*level] = 0; |
906 | } | |
907 | out: | |
5caf2a00 CM |
908 | WARN_ON(*level < 0); |
909 | WARN_ON(*level >= BTRFS_MAX_LEVEL); | |
6407bf6d | 910 | ret = btrfs_free_extent(trans, root, |
7eccb903 | 911 | bh_blocknr(path->nodes[*level]), 1, 1); |
234b63a0 | 912 | btrfs_block_release(root, path->nodes[*level]); |
20524f02 CM |
913 | path->nodes[*level] = NULL; |
914 | *level += 1; | |
915 | BUG_ON(ret); | |
916 | return 0; | |
917 | } | |
918 | ||
9aca1d51 CM |
919 | /* |
920 | * helper for dropping snapshots. This walks back up the tree in the path | |
921 | * to find the first node higher up where we haven't yet gone through | |
922 | * all the slots | |
923 | */ | |
e089f05c CM |
924 | static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root |
925 | *root, struct btrfs_path *path, int *level) | |
20524f02 CM |
926 | { |
927 | int i; | |
928 | int slot; | |
929 | int ret; | |
234b63a0 | 930 | for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) { |
20524f02 | 931 | slot = path->slots[i]; |
e20d96d6 CM |
932 | if (slot < btrfs_header_nritems( |
933 | btrfs_buffer_header(path->nodes[i])) - 1) { | |
20524f02 CM |
934 | path->slots[i]++; |
935 | *level = i; | |
936 | return 0; | |
937 | } else { | |
e089f05c | 938 | ret = btrfs_free_extent(trans, root, |
7eccb903 | 939 | bh_blocknr(path->nodes[*level]), |
e089f05c | 940 | 1, 1); |
6407bf6d | 941 | BUG_ON(ret); |
234b63a0 | 942 | btrfs_block_release(root, path->nodes[*level]); |
83e15a28 | 943 | path->nodes[*level] = NULL; |
20524f02 | 944 | *level = i + 1; |
20524f02 CM |
945 | } |
946 | } | |
947 | return 1; | |
948 | } | |
949 | ||
9aca1d51 CM |
950 | /* |
951 | * drop the reference count on the tree rooted at 'snap'. This traverses | |
952 | * the tree freeing any blocks that have a ref count of zero after being | |
953 | * decremented. | |
954 | */ | |
e089f05c | 955 | int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root |
e20d96d6 | 956 | *root, struct buffer_head *snap) |
20524f02 | 957 | { |
3768f368 | 958 | int ret = 0; |
9aca1d51 | 959 | int wret; |
20524f02 | 960 | int level; |
5caf2a00 | 961 | struct btrfs_path *path; |
20524f02 CM |
962 | int i; |
963 | int orig_level; | |
964 | ||
5caf2a00 CM |
965 | path = btrfs_alloc_path(); |
966 | BUG_ON(!path); | |
967 | btrfs_init_path(path); | |
20524f02 | 968 | |
e20d96d6 | 969 | level = btrfs_header_level(btrfs_buffer_header(snap)); |
20524f02 | 970 | orig_level = level; |
5caf2a00 CM |
971 | path->nodes[level] = snap; |
972 | path->slots[level] = 0; | |
20524f02 | 973 | while(1) { |
5caf2a00 | 974 | wret = walk_down_tree(trans, root, path, &level); |
9aca1d51 | 975 | if (wret > 0) |
20524f02 | 976 | break; |
9aca1d51 CM |
977 | if (wret < 0) |
978 | ret = wret; | |
979 | ||
5caf2a00 | 980 | wret = walk_up_tree(trans, root, path, &level); |
9aca1d51 | 981 | if (wret > 0) |
20524f02 | 982 | break; |
9aca1d51 CM |
983 | if (wret < 0) |
984 | ret = wret; | |
20524f02 | 985 | } |
83e15a28 | 986 | for (i = 0; i <= orig_level; i++) { |
5caf2a00 CM |
987 | if (path->nodes[i]) { |
988 | btrfs_block_release(root, path->nodes[i]); | |
83e15a28 | 989 | } |
20524f02 | 990 | } |
5caf2a00 | 991 | btrfs_free_path(path); |
9aca1d51 | 992 | return ret; |
20524f02 | 993 | } |
9078a3e1 CM |
994 | |
995 | int btrfs_free_block_groups(struct btrfs_fs_info *info) | |
996 | { | |
997 | int ret; | |
998 | struct btrfs_block_group_cache *cache[8]; | |
999 | int i; | |
1000 | ||
1001 | while(1) { | |
1002 | ret = radix_tree_gang_lookup(&info->block_group_radix, | |
1003 | (void **)cache, 0, | |
1004 | ARRAY_SIZE(cache)); | |
1005 | if (!ret) | |
1006 | break; | |
1007 | for (i = 0; i < ret; i++) { | |
1008 | radix_tree_delete(&info->block_group_radix, | |
1009 | cache[i]->key.objectid + | |
1010 | cache[i]->key.offset - 1); | |
1011 | kfree(cache[i]); | |
1012 | } | |
1013 | } | |
1014 | return 0; | |
1015 | } | |
1016 | ||
1017 | int btrfs_read_block_groups(struct btrfs_root *root) | |
1018 | { | |
1019 | struct btrfs_path *path; | |
1020 | int ret; | |
1021 | int err = 0; | |
1022 | struct btrfs_block_group_item *bi; | |
1023 | struct btrfs_block_group_cache *cache; | |
1024 | struct btrfs_key key; | |
1025 | struct btrfs_key found_key; | |
1026 | struct btrfs_leaf *leaf; | |
1027 | u64 group_size_blocks = BTRFS_BLOCK_GROUP_SIZE / root->blocksize; | |
31f3c99b | 1028 | u64 used; |
9078a3e1 CM |
1029 | |
1030 | root = root->fs_info->extent_root; | |
1031 | key.objectid = 0; | |
1032 | key.offset = group_size_blocks; | |
1033 | key.flags = 0; | |
1034 | btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY); | |
1035 | ||
1036 | path = btrfs_alloc_path(); | |
1037 | if (!path) | |
1038 | return -ENOMEM; | |
1039 | ||
1040 | while(1) { | |
1041 | ret = btrfs_search_slot(NULL, root->fs_info->extent_root, | |
1042 | &key, path, 0, 0); | |
1043 | if (ret != 0) { | |
1044 | err = ret; | |
1045 | break; | |
1046 | } | |
1047 | leaf = btrfs_buffer_leaf(path->nodes[0]); | |
1048 | btrfs_disk_key_to_cpu(&found_key, | |
1049 | &leaf->items[path->slots[0]].key); | |
1050 | cache = kmalloc(sizeof(*cache), GFP_NOFS); | |
1051 | if (!cache) { | |
1052 | err = -1; | |
1053 | break; | |
1054 | } | |
1055 | bi = btrfs_item_ptr(leaf, path->slots[0], | |
1056 | struct btrfs_block_group_item); | |
1057 | memcpy(&cache->item, bi, sizeof(*bi)); | |
1058 | memcpy(&cache->key, &found_key, sizeof(found_key)); | |
31f3c99b CM |
1059 | cache->last_alloc = cache->key.objectid; |
1060 | cache->first_free = cache->key.objectid; | |
9078a3e1 CM |
1061 | key.objectid = found_key.objectid + found_key.offset; |
1062 | btrfs_release_path(root, path); | |
1063 | ret = radix_tree_insert(&root->fs_info->block_group_radix, | |
1064 | found_key.objectid + | |
1065 | found_key.offset - 1, | |
1066 | (void *)cache); | |
1067 | BUG_ON(ret); | |
31f3c99b CM |
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 | } | |
9078a3e1 CM |
1075 | if (key.objectid >= |
1076 | btrfs_super_total_blocks(root->fs_info->disk_super)) | |
1077 | break; | |
1078 | } | |
1079 | ||
1080 | btrfs_free_path(path); | |
1081 | return 0; | |
1082 | } |