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